基于选择性混合执行和细粒度距离计算的定向模糊测试方法及系统

本发明涉及软件安全测试与漏洞挖掘，具体涉及一种面向目标代码区域的定向模糊测试技术，用于提升目标程序中指定代码位置或目标路径的到达效率以及漏洞触发效率。

背景技术：

1、随着软件系统规模不断扩大以及开源软件的广泛应用，各类基础库、第三方组件和开源框架已被大量集成到操作系统、网络服务、工业控制及智能终端等软件系统中。与此同时，软件漏洞数量持续增加，且漏洞传播范围更广、影响更大，一旦底层开源组件存在安全缺陷，往往会通过依赖关系扩散至多个应用场景，因此亟需高效的自动化漏洞挖掘技术。

2、模糊测试作为一种重要的软件安全测试方法，具有自动化程度高、实际漏洞发现能力强、工程适用性好的优点，已被广泛应用于漏洞挖掘领域。传统模糊测试通常以提升程序整体覆盖率为目标，通过不断变异输入并依据执行反馈探索更多路径。但该类方法缺乏针对特定目标代码区域的引导能力，在面对已知高风险代码、补丁相关代码或待验证漏洞位置时，容易出现测试资源分散、目标到达效率低和漏洞触发速度慢的问题。

3、为提高对指定目标位置的测试效率，研究人员提出了定向模糊测试技术。该技术通常结合程序静态分析信息，计算程序位置到目标位置的距离，并据此引导种子调度和能量分配。然而，现有方法大多基于控制流图或调用图中的结构信息进行距离计算，难以准确刻画复杂控制流、循环结构及跨过程路径对目标可达性的真实影响，导致引导效果有限。

4、此外，当目标路径包含复杂条件约束时，仅依靠随机变异往往难以快速构造满足条件的输入。虽然部分方法引入符号执行以增强路径求解能力，但现有将模糊测试与符号执行结合方案普遍存在符号化范围过大、执行开销较高以及与测试协同不足等问题，容易产生大量与目标无关的冗余开销。因此，亟需一种面向目标代码区域、兼具精确引导能力和高效协同机制的漏洞挖掘方法。

技术实现思路

1、本发明的目的在于，针对现有定向模糊测试方法中存在的目标距离建模不够精确、复杂路径条件下目标代码到达效率较低，以及模糊测试与混合执行协同不足、导致漏洞挖掘效率受限等问题，提出一种面向目标代码区域的混合定向模糊测试方法及系统。该方法能够在保证测试开销可控的前提下，提高测试用例对目标代码位置的到达效率，增强对复杂约束路径的探索能力，并提升目标相关漏洞的触发效率与整体漏洞挖掘效率。

2、本发明的具体技术方案是：

3、基于选择性混合执行和细粒度距离计算的定向模糊测试方法，包括以下步骤：

4、s1、目标相关代码段提取：对待测程序进行静态分析，构建待测程序的控制流图和调用图，并对其中的间接调用关系进行分析，以获得较完整的跨过程控制流信息，并提取待测程序中的数据依赖关系；基于控制流关系和数据依赖关系，识别能够影响目标代码到达的控制流相关基本块，以及能够影响漏洞触发状态的数据流相关基本块；以控制流相关基本块和数据流相关基本块作为目标相关代码段，通过混合执行编译器对待测程序进行选择性插桩，生成被选择性混合执行插桩的待测程序。

5、s2、计算基于概率的细粒度距离：从控制流图中提取存在循环依赖或回边关系的冲突基本块，并以各冲突基本块为根节点构建对应的冲突树，将多棵冲突树组合形成冲突森林；对每一棵冲突树进行静态分析，确定叶节点概率贡献以及冲突基本块之间的依赖关系，并据此构建线性方程组；通过求解线性方程组获得各冲突基本块的目标可达概率，并在消除循环依赖后递归计算其他基本块的可达概率；将可达概率按照预设映射规则转换为距离值，形成用于后续种子调度和目标引导的细粒度距离信息；

6、s3、进行模糊测试：在测试开始前，初始化模糊测试所需的全局变量、共享变量、队列状态以及运行时参数，并创建子进程用于处理需要混合执行的种子；在模糊测试变异阶段，将需要进行混合执行的种子复制到共享内存区域，并通过同步机制通知混合执行模块执行一轮混合执行；混合执行模块接收到信号后，从共享内存池中读取对应种子文件，对其执行混合执行分析并生成新的测试用例；模糊测试生成的测试用例和混合执行生成的测试用例均被提交至处理队列，模糊测试引擎根据覆盖反馈、距离反馈和执行结果进行筛选，并将具有新覆盖、目标接近性或继续探索价值的重要测试用例保存至种子队列，用于下一轮模糊测试。

7、作为优选实施例，所述步骤s1中，控制流相关基本块和数据流相关基本块的识别包括：基于控制流图和调用图，以目标基本块为起点分析能够到达目标基本块的基本块和跨函数调用点，将其标记为控制流相关基本块；基于变量定义关系和使用关系，以目标基本块中的相关变量为起点进行前向依赖分析和后向依赖分析，将能够影响目标基本块执行状态或者受目标基本块执行结果影响的基本块标记为数据流相关基本块；

8、控制流依赖基本块是指位于任一通向目标基本块的潜在控制流路径上的基本块，形式化地，设 表示从基本块 出发，在经过 条控制流边以内可达的基本块集合，则控制流依赖基本块集合定义为：

9、，

10、只要某一基本块的后继可达集合中至少包含一个目标基本块，则该基本块即属于，保留所有可能影响程序朝向目标执行路径推进的基本块，以供后续插桩使用；

11、对于跨过程控制依赖，若函数中包含一个调用点，该调用点调用被调函数，且中存在属于的基本块，则中对应的调用点基本块同样被标记为控制流依赖基本块，其定义如下：

12、，

13、通过该传播机制，能够捕获跨越多个函数的控制依赖关系，从而保留所有通向目标的跨过程路径；

14、对于跨过程数据依赖，分析进一步扩展至函数参数、指针解引用以及返回值，

15、设为程序变量集合，为基本块集合，对于任意基本块，定义其变量定义集合为，变量使用集合为，进一步地，定义数据依赖关系为：

16、，

17、上述关系表示：若某一变量在基本块中被定义，并在基本块中被使用，则构成一条数据依赖关系，通过对该关系递归应用，可以得到其传递闭包，用于表征经由中间变量或中间定义所形成的间接依赖关系；

18、在此基础上，从目标基本块 出发定义其数据流依赖闭包为：

19、，

20、其中，条件 表示所有会影响目标基本块 的基本块，即后向依赖；条件 表示所有受到目标基本块 影响的基本块，即前向依赖，针对全部目标基本块，其全局数据流依赖基本块集合定义为：

21、，

22、上述形式化定义对程序中的数据流关系给出了统一表示，其可被理解为一种静态的污点传播近似模型，即同时覆盖程序范围内的后向依赖链与前向依赖链。

23、作为优选实施例，所述步骤s1中，选择性插桩包括：将控制流相关基本块和数据流相关基本块合并为目标相关代码段；通过混合执行编译器仅对目标相关代码段插入混合执行所需的符号化逻辑、约束记录逻辑和运行时辅助逻辑；对目标无关代码段保持具体执行，以减少无关路径约束构建和混合执行开销。

24、作为优选实施例，所述步骤s2中，冲突基本块提取包括：遍历控制流图中的基本块及其后继关系，判断基本块是否能够经过一条或多条控制流边重新到达自身；若能够重新到达自身，则将该基本块标记为冲突基本块，用于对循环、回边或非结构化跳转产生的循环依赖进行概率建模；

25、待测程序首先被表示为由基本块和控制流边构成的控制流图，设表示目标基本块集合，表示从基本块出发，在经过不超过条控制流边后可达的基本块集合，其中，若某一基本块能够经过一个或多个控制流转移再次到达其自身，则说明该基本块位于循环结构或回边结构中，为处理该类循环依赖，定义冲突基本块集合如下：

26、，

27、其中，表示所有冲突基本块的集合，对于属于的基本块，其目标可达概率不能简单地按照无环图中的递归方式直接计算，否则会产生循环依赖，因此，首先对冲突基本块进行单独处理，再对其余无环部分进行递归概率传播；

28、对于每一个冲突基本块，构建以为根节点的冲突树，该冲突树用于表示从冲突基本块 出发沿控制流向前传播时可能到达的基本块路径，直至到达叶节点为止，若某一基本块不存在后继基本块，或者属于预定义概率基本块集合，或者再次属于冲突基本块集合，则该基本块被作为冲突树中的叶节点，叶节点集合定义为：

29、，

30、其中，表示概率值已经能够直接确定的基本块集合，该集合主要包括目标基本块集合以及调用点基本块集合，其定义如下：

31、，

32、对于目标基本块，其目标可达概率被定义为 ，表示该基本块已经到达目标位置；对于无法到达目标的终止基本块，其目标可达概率被定义为 ；对于调用点基本块，其概率由被调函数入口基本块的概率决定，将目标位置、终止位置以及跨函数调用位置统一纳入概率传播框架中；

33、在冲突树中，设表示基本块的后继基本块数量，表示基本块在冲突树中的层级，表示该层级上所有基本块后继数量的最小公倍数，对于冲突树中的叶节点，其叶系数记为，用于表示该叶节点对根节点的概率贡献，所有叶节点的系数可以组成如下向量：

34、，

35、同时，设冲突树的根节点归一化系数为，其用于对不同层级传播过程中产生的概率系数进行统一归一化，若表示冲突树的最大深度，则有：

36、，

37、通过上述叶系数与根节点归一化系数，可以将每一棵冲突树中叶节点对根节点的概率贡献表示为线性关系，由于不同冲突基本块之间可能相互依赖，全部冲突树共同形成冲突森林，记为：

38、，

39、基于该冲突森林，可以建立全局线性方程组：

40、，

41、其中， 表示所有冲突基本块的目标可达概率向量， 表示冲突基本块之间由循环结构产生的概率依赖关系矩阵， 表示由目标基本块、终止基本块以及预定义概率基本块贡献的常数项，通过求解该线性方程组，即可得到每一个冲突基本块的目标可达概率，能够在存在循环、回边或非结构化跳转的情况下，对基本块的目标可达性进行一致且细粒度的建模。

42、作为优选实施例，所述步骤s2中，冲突树构建包括：以冲突基本块作为根节点，沿控制流后继方向展开可达路径；当路径到达无后继基本块、预定义概率基本块或另一冲突基本块时停止展开；将停止展开的基本块作为叶节点，并记录叶节点对根节点目标可达概率的贡献关系，多棵冲突树共同构成冲突森林。

43、作为优选实施例，所述步骤s2中，线性方程组构建包括：对每一棵冲突树进行静态分析，计算叶节点对根节点的概率贡献系数；根据不同冲突基本块之间的依赖关系形成系数矩阵；将目标基本块、终止基本块和预定义概率基本块对应的已知概率作为常数项，构建用于求解冲突基本块目标可达概率的线性方程组。

44、作为优选实施例，所述步骤s2中，递归概率传播包括：在求解得到冲突基本块的目标可达概率后，将冲突基本块概率作为已知值；对于不存在循环依赖的基本块，根据其直接后继基本块的目标可达概率进行递归传播；对于调用点基本块，根据被调函数入口基本块的目标可达概率更新调用点基本块的目标可达概率；

45、在完成冲突基本块概率求解后，剩余控制流图可以视为无环结构，并可采用递归方式计算一般基本块的目标可达概率，设表示基本块到达任一目标基本块的概率，对于任意基本块 ，其概率计算规则定义如下：

46、，

47、其中，表示基本块已经确定的常数概率值，当属于目标基本块、调用点基本块或冲突基本块时，直接使用其预定义或已求解的概率值；否则，基本块 的概率由其所有直接后继基本块的概率平均得到；

48、对于跨函数调用关系，在调用图上进行概率传播，设函数 中存在调用点，其调用函数 ，则该调用点基本块的概率由被调函数 的入口基本块概率决定，即：

49、，

50、通过该定义，函数内部控制流概率与函数间调用概率能够被统一到同一计算框架中；

51、在获得基本块的目标可达概率后，进一步将概率值转换为距离值，以便与定向模糊测试中的种子调度和能量分配机制相结合，对于任意基本块，其距离定义如下：

52、，

53、其中，当时，表示基本块 已经是目标基本块或等价于目标位置，因此其距离定义为 ；当 时，表示该基本块无法到达目标位置，因此其距离被设置为实现中的最大值 ；当 时，其距离定义为概率的倒数，该定义保证了目标可达概率与距离之间具有单调对应关系，即可达概率越高，距离越小；可达概率越低，距离越大，该特性符合定向模糊测试中利用距离信息引导测试输入逐步靠近目标代码的需求；

54、函数级距离可以由函数入口基本块的距离表示，即：

55、，

56、在模糊测试执行过程中，对于某一测试输入，其执行路径可能经过多个函数和多个基本块，若测试输入 在一次执行过程中经过的函数集合为 ，则其输入级距离可表示为：

57、，

58、由此，距离值较小的测试输入表示其执行路径整体上更接近目标代码区域，模糊测试引擎可在后续测试过程中优先选择该类输入进行变异和调度；距离值较大的测试输入则表示其与目标代码区域相对较远，可相应降低其调度优先级。

59、作为优选实施例，所述步骤s3中，同步机制包括：在测试开始前创建共享内存区域并初始化同步变量或信号量；在模糊测试变异阶段，模糊测试引擎将需要进行混合执行的种子写入共享内存区域，并通过同步变量或信号量通知混合执行模块；混合执行模块接收到通知后读取共享内存中的种子文件并执行混合执行，生成新的测试用例。

60、作为优选实施例，所述步骤s3中，模糊测试与混合执行的信息交互包括：模糊测试引擎与混合执行模块共享种子状态、覆盖反馈、距离反馈和执行结果；混合执行生成的测试用例与模糊测试变异生成的测试用例被提交至统一处理队列，并由模糊测试引擎基于全局覆盖信息、目标距离信息和执行结果进行筛选，将具有新覆盖、目标接近性或继续探索价值的测试用例保存至种子队列。

61、基于选择性混合执行和细粒度距离计算的定向模糊测试系统，用于执行所述定向模糊测试方法，包括静态分析器、符号化编译器、模糊测试编译器和模糊测试引擎，系统对待测程序进行静态分析，构建控制流图和调用图，分析间接调用关系并提取数据依赖关系；基于控制流关系和数据依赖关系，识别影响目标代码到达的控制流相关基本块以及影响漏洞触发状态的数据流相关基本块，并通过混合执行编译器对相关基本块进行选择性插桩，生成被选择性混合执行插桩的待测程序；系统从控制流图中提取冲突基本块，构建冲突树和冲突森林，并通过线性方程组求解冲突基本块的目标可达概率，在此基础上递归计算其他基本块的可达概率，并转换为细粒度距离信息；测试时，系统初始化共享变量和运行时状态，将需要混合执行的种子写入共享内存并通知混合执行模块生成测试用例，随后由模糊测试引擎统一筛选模糊测试和混合执行生成的测试用例，并将重要测试用例保存至种子队列用于下一轮测试。

62、本发明核心技术原理：基于选择性混合执行和细粒度距离计算的定向模糊测试方法，由静态分析器、符号化编译器、模糊测试编译器和模糊测试引擎等软件实现，首先，通过静态分析提取关键程序信息，静态分析器接收待测程序源代码、目标代码位置信息以及编译中间表示，对程序进行控制流分析、调用关系分析和目标相关性分析。首先，从目标基本块所在函数出发，沿调用图反向搜索所有能够到达目标函数的调用链，提取与目标代码可达性相关的关键函数集合；进一步，在关键函数范围内识别目标基本块以及调用关键函数和目标函数的调用点基本块，作为后续分析的初始参考节点。然后，基于控制流图分析程序中能够到达所述参考节点的相关基本块，构建目标相关代码区域。最后，在目标相关代码区域内结合基本块之间的可达关系、跨过程调用关系以及路径传播特性，计算各基本块到目标代码的细粒度距离值，并输出关键代码段信息和距离信息。关键代码段信息用于限定符号化处理范围，所述距离信息用于后续模糊测试过程中的种子调度、能量分配和目标引导。

63、其次，选择性符号化编译，符号化编译器根据静态分析器输出的关键代码段信息，对待测程序执行选择性符号化编译。具体地，仅对与目标代码到达和漏洞触发过程相关的关键基本块、关键分支条件、关键比较操作以及相关输入变量传播链上的程序语句插入符号化逻辑，使与目标相关的路径条件能够在运行时被提取和求解。对于与目标无关或对目标到达贡献较低的代码区域，则保持其原有执行方式。

64、再次，模糊测试编译，模糊测试编译器根据静态分析器生成的细粒度距离信息，对待测程序执行面向模糊测试的插桩编译。系统在程序各目标相关基本块、边或分支位置插入运行时监测逻辑，用于记录测试输入的覆盖路径、路径命中情况以及执行过程中对应的距离值变化；同时，将各基本块的距离值映射到程序运行时可访问的数据结构中，使模糊测试引擎能够实时获取当前输入与目标代码之间的接近程度。除此之外，还在编译阶段插入模糊测试所需的运行时支持代码，包括共享内存数据结构、执行状态记录变量、种子调度辅助变量、距离反馈变量以及与混合执行协同所需的通信接口。

65、最后混合执行过程，模糊测试引擎加载经符号化编译和模糊测试插桩后的待测程序，并以初始种子集作为输入开始迭代测试。测试过程中，模糊测试引擎首先对种子进行选择和变异，生成候选测试用例并驱动程序执行；在每轮执行后，根据运行时反馈获取输入的覆盖信息、路径命中情况以及与目标代码相关的距离变化，并据此评估当前输入对目标代码的接近程度。对于能够缩短目标距离、覆盖关键代码区域或表现出较高潜力的测试输入，模糊测试引擎提高其调度优先级并分配更多变异能量，以引导后续测试朝向目标代码区域收敛。当检测到某些输入在关键分支处长期受阻、仅依靠随机变异难以继续逼近目标时，模糊测试引擎触发混合执行模块，对相关关键路径条件进行求解，生成满足约束的新测试用例，并将其重新加入模糊测试队列中继续执行。

66、有益效果：

67、1）本发明通过将选择性混合执行与定向模糊测试相结合，能够更高效地引导测试输入逼近目标代码区域，从而提升目标相关漏洞的挖掘效率。

68、2）本发明能够触发同一漏洞对应的多种不同执行路径下的异常行为，从而生成具有多样性的漏洞触发样本，为后续漏洞利用分析、成因定位及修复验证提供支持。

69、3）本发明采用细粒度距离计算方法，能够更准确地刻画程序位置与目标代码之间的接近程度，并且相较于现有距离计算方式具有更好的引导效果和性能表现。

70、4）本发明构建了高集成度的混合执行协作机制，使混合执行器与模糊测试器之间能够实现运行时资源共享与测试信息共享，并通过复用测试框架与执行流程减少额外开销，从而提高整体测试效率。