软件漏洞模糊测试的关键分支探索及热点更新算法

摘 要：在软件开发及应用中，由于具有可复现性，模糊测试能够帮助发现漏洞和有针对性地对漏洞成因进行分析。为了解决模糊测试过程的效率及测试力度等问题，提出了软件漏洞模糊测试的关键分支探索及热点更新算法。该方法通过捕获、分析和利用受检程序在处理测试用例时的执行位置的关键信息，以指导模糊测试过程的探索方向和测试用例的生成。实验结果表明，提出的方法相较于传统随机发散的模糊测试方法在漏洞发现能力上有较大提升，在Otfcc、Swftools等14个开源程序中发现了100余个未被公布的漏洞，为模糊测试用于软件漏洞检测提供了新的可靠途径。

关键词：模糊测试；代码分析；关键分支；漏洞检测

中图分类号：TP301 文献标志码：A 文章编号：1001-3695（2024）07-036-2179-05

doi： 10.19734/j.issn.1001-3695.2023.11.0508

Algorithm of key branch exploration and hotspot update for software vulnerability fuzzy testing

Abstract：In software development and application， due to its reproducibility， fuzzy testing can help identify vulnerabilities and analyze the causes of vulnerabilities in a targeted manner. In order to address the issues of efficiency and testing intensity in the fuzzy testing process， this paper proposed a key branch exploration and hotspot update algorithm for software vulnerability fuzzy testing. This method guided the exploration direction of the fuzzy testing process and the generation of test cases by capturing， analyzing， and utilizing key information on the execution position of the inspected program when processing test cases. The experimental results show that the proposed method has a significant improvement in vulnerability detection ability compared to the traditional randomly divergent fuzzy testing methods， and more than 100 undisclosed vulnerabilities were found in 14 open source programs such as Otfcc and Swftools which providing a new and reliable approach for using fuzzy testing to detect software vulnerability.

Key words：fuzzy testing; code analysis; key branch; vulnerability detection

0 引言

模糊测试是一种通过向系统注入随机或异常数据来发现应用程序或系统中的潜在漏洞和软件缺陷的测试方法，已广泛应用于Web应用程序、移动应用程序、网络协议、操作系统与内核、数据库系统、物联网设备等领域的缺陷或潜在漏洞检测［1～6］。 作为典型的模糊测试工具，Google推出的基于代码覆盖率的AFL，使用测试用例所能触发到的受检程序功能代码与整体代码（插桩得到部分）的比值来衡量当前测试用例发现漏洞、程序安全违例事件的潜力，藉此考察测试用例是否应当保留，以用作后续突变产生新测试用例的母本，其核心思想在于基于测试所能覆盖到的代码体量占比越大，发现程序脆弱点的可能性越大［7］。基于该方法的模糊测试工具在过去很长时间被Google、Microsoft、Adobe等诸多公司或厂商付诸应用，实践证明了其有效性。一方面，AFL在编译受检程序时进行插桩处理，为每个插桩单元生成一个随机标识符来唯一标识当前程序位置［8］，同时通过捕获受检程序的分支执行情况来实现代码覆盖率的检测。另一方面，AFL测试用例的生成采用样本突变方式，其原生的突变操作包括byteflip 、bitflip、arithmetic inc/dec、interesting values、user extras、auto extras、random bytes、insert bytes、cross over等类型，执行测试用例后会记录该用例的执行路径覆盖情况，并且评估该测试用例，指导后续新的用例的生成［9］。

实际上，传统随机发散的模糊测试方法存在着一些不足，例如过于依赖代码覆盖率的样本质量评估指标，由于不能进入某些程序保护逻辑等原因，导致同样具备漏洞存在可能的部分程序代码的探索用时较长，或者测试力度不足以触发程序异常所带来的漏报率［10］。可能带来测试代码覆盖率问题的一段代码如下：

其中，第3行的if条件分支中的代码体量相对该处else分支的代码体量而言更大，在衡量测试用例质量的代码覆盖率关键指标上表现更优，存在使得模糊测试的测试方向倾向于分支条件为true的部分，而忽略了导致对该处分支条件为false的分支的发现，或者由于测试强度不足以触发这一分支下的错误（crash）而导致的发现效率低、漏报等情况。

Dinesh等人［11］认为程序模糊化对闭源二进制文件安全分析是可行的，基于代码覆盖率引导对二进制文件进行模糊化重写，并保证其在性能上与编译器插入的二进制文件相同。佘庚达等人［12］基于二进制程序静态分析提出了用于驱动程序运行信息监控和漏洞挖掘的模糊测试工具。Li等人［13］考虑到传统模糊测试方法面向多字节保护逻辑时，单字节枚举正确有利于测试，但因为无法体现代码覆盖率指标，导致诸多生成的测试用例无法针对这些保护逻辑进行测试而使效率低下，所以对相关位置代码进行重写，使得保护逻辑字段首字节的枚举正确性得以反映在用于指导fuzzer变异的代码覆盖率上，并将该有效样本送入下一轮的迭代再生成。Lemieux等人［14］提出一种自动识别稀有分支的方法，并结合一种新颖的突变掩码创建算法，该算法将突变偏向于生成命中给定稀有分支的输入。Ganesh等人［15］利用动态污点追踪来识别原始种子输入文件中影响关键程序攻击点所用值的区域，然后对这些区域进行模糊处理，生成新的测试输入文件，这些文件保留了原始种子输入文件的底层语法结构，并指出此技术对于测试具有复杂、高度结构化输入文件格式的程序效果显著。Ma等人［16］提出一种基于遗传算法和BI-LST神经网络的模糊测试样本生成框架，以获得一个同时具有代码覆盖率和漏洞挖掘能力的样本集，用于程序的关键执行路径，重点关注了路径深度探索能力评估指标，使探索能够发现原本无法发现的漏洞。总的来说，诸多研究方法仍然体现了如何在模糊测试过程中完成对受检程序内部代码的快速探索，以快速提升测试所能覆盖到的更广泛的代码，以及如何生成高效、高质量的测试用例是模糊测试技术在实践中存在的挑战。

本文借鉴AFL，通过对样本突变操作所生成新的测试用例的质量评估，保留具备更高潜力（主要体现在代码覆盖率上）的样本，并作为用于后续突变生成新的测试用例的母本的思路，提出面向软件漏洞模糊测试的关键分支探索及热点更新算法及应用方法，旨在解决针对受检程序内部关键分支的识别及其快速探索，以及高质量测试用例生成方法等问题。将程序保护逻辑及其相关指令作为关键特征分支，结合合法样本和非法样本两类样本，在受检程序内部的处理过程中捕获关键分支位置特征信息。通过比对这些指令位置的操作数、寄存器等执行信息的差异，筛查并快速探索价值相对较高的关键分支，进而使用程序局部性原理结合测试用例的评估结果与突变位置构建样本突变热点位记录模块，为样本突变阶段生成测试用例提供指导。

1 面向关键分支的软件漏洞模糊测试模型

为了有效地提升代码探索效率及漏洞检测能力，构建面向关键分支的软件漏洞模糊测试模型，如图1所示，主要包括关键分支筛选、分支内部快速探索和突变热点区域记录三个模块。首先，关键分支筛选负责完成对受检程序内部关键分支的筛选，利用静态分析并结合受检程序对测试用例的处理过程，具体地执行上下文信息，完成对程序敏感代码或执行检查的识别与定位。该模块的输出结果仅保留满足筛选条件的部分，即被认为对接收输入合法性敏感的、具有较高探索价值的分支选择指令。其次，分支内部快速探索是结合关键分支筛选模块的处理结果，负责对程序内部分支的快速探索，该探索过程中会对受检程序内部运行进行干预，目的在于提升受检程序内部分支的发现效率，同时，期望检测出程序内部更加隐蔽的漏洞，这是因为某些更加隐蔽、难以检出的安全漏洞更常与非常规程序执行流程或不正确的状态转换相关。最后，突变热点区域记录是在单个测试用例执行结束后的样本评估时执行，主要是利用当前测试用例的执行结果表现，根据程序局部性原理，去评估当前样本的突变位置在代码覆盖率、诱发受检程序出现安全违例事件的可能性等潜力设置样本热点位图，样本热点位图中的热度信息可为后续样本突变阶段的突变操作位置提供指导。

2 关键分支筛选

关键分支是指那些对接受输入合法性较为敏感的部分分支，所对应的选择指令典型的有checksum、magic bytes check等［17］。对于接收输入的合法性敏感，意味着这部分相应的内容在面向输入合法性存在差异的内容时，程序内部的执行上下文会存在不同程度的差异，进而表现出程序行为的差异。输入合法性是指程序预期进行处理的内容。模糊测试的基础思想正是通过生成大量的畸形数据，增加输入非法样本的可能产生比例，进而期望这些内容能够导致程序出现安全违例事件。分支筛选的目的，一方面是为了避免测试工作负担呈现指数型爆炸式增长，在牺牲部分探索价值不高的位置换取测试整体效率的提升；另一方面，价值不高的内容并非真正丢弃，模糊测试的基本方法仍可能覆盖未被选中的部分并完成测试。

首先，对关键分支位置的特征进行提取，由于其实施特征通常以cmp/转移指令、test/转移指令的方式出现，所以使用静态分析对满足条件的内容进行初步筛选。其次，为了确定那些对于接收输入合法性敏感的位置，通过提交给受检程序二类样本（合法样本和非法样本），根据转移指令je的逻辑，检测受检程序对这些样本的实际执行过程中具体的相关执行上下文的差异进行进一步筛查。要注意的是，je的实施逻辑与标志寄存器的内容高度相关。

算法1 关键分支筛选

算法1的第1、2行输入合法和非法两类样本并交付给受检程序执行，如果执行到静态分析初步筛选得出的关键分支标志转移指令所在位置时，记录相应的标志寄存器内容。记录的内容以hash表形式存放，键值以指令地址计算得出。第4行中，记录对非法与合法两类样本都覆盖的内容。后续算法将对当前的检查点（spot）进行特征检查，以je指令为例，对于合法样本和非法样本，算法会记录它们执行到检查点时的标志寄存器内容，并检查与je指令相关的标志位。如果存在差异（第7行），既当前的检查点是一个对于输入合法性比较敏感的校验位置，具有较高的探索价值，因此将其保存进入关键分支筛选结果checkPointArray，并作为算法输出。

3 分支内部快速探索

3.1 分支干预与探索

分支内部快速探索旨在完成受检程序内部快速探索的目的。通常，一些难以检测的安全漏洞常常与非常规程序执行流程或不正确的状态转换有关。因此，针对关键分支筛选模块的执行结果（即敏感位），分支内部快速模块干预程序的运行，即在这些位置对相应寄存器内容设定反值，以更改程序执行分支的陷入方向。通常，这些敏感位置与程序的执行分支选择密切相关。对受检程序内部的快速探索如图2所示。

干预可以视为非常规程序执行流程或不正确的状态转换。如果在受检程序的后续执行过程中发生崩溃，则修复相应的样本。传统模糊测试工具在评估样本质量时通常会保留表现优秀的测试用例作为后续突变的母本，同时丢弃表现差的样本。实际上，表现差的样本也具有突变母本的某些特质，因此，这类样本也可以作为操作对象，并且不会干扰主测试的进程。

算法2 分支内部快速探索

算法2的第2行，pickPosToTwist方法随机选择执行程序干预的位置，该操作可以先行降低后续可能启动的样本修复所导致的修复开销。第7行checkPointArray是通过算法1得出，与程序的执行分支转移和输入的合法性密切相关。选取通过关键分支筛选得出的敏感位置进行控制流程的干预，可以快速探索受检程序内部的逻辑，以及检出那些与非常规程序执行流程或不正确状态转换相关的、隐蔽性较好的漏洞。在实施干预分支陷入方向后，如果受检程序对当前测试用例的执行效果有提升（如crash或测试代码覆盖率有提升），则启动样本修复模块进行后续操作，否则视当前所干预的分支为冗余操作，通过执行第31行的rollback方法标记相应的分支转移位置，后续不再对其进行干预，该操作同样可以降低后续可能启动的样本修复所导致的资源开销。

3.2 样本修复

样本修复模块与分支内部快速探索模块协同工作，用于在快速探索模块中对关键分支转移位置实施干扰，并且修复因干预导致效益提升的样本。采用受限性引用符号执行技术，即仅针对实施干预部分的节点实施技术应用，这是由快速探索模块的策略决定的［18］。快速探索模块中，pickPosToTwist方法对干预位置的选择是随机的，也就是对checkPointArray中随机挑选部分位置实施干预，并非全部实施干预，使得符号执行应用过程中的求解工作量减少。

另一方面，算法2中的rollback方法对于无表现提升的干预位置进行回退操作，其目的也在于降低符号执行应用过程中的求解工作量。针对分支转移位置checkPoint cp进行干预的过程，如图3所示，原执行分支在该位置的转移目的分支被干预。如果对checkPoint cp实施干预未带来测试用例表现的提升，则执行rollback方法进行回退，因此不存在对该点的干预后果承担修复资源开销的情况。如果对checkPoint cp实施干预带来测试用例表现的提升，则需要进行修复，此时符号执行技术所需要修复的部分仅是相关的跃迁路径（branch_src， branch_dst），从而降低符号执行的求解复杂度。

4 突变热点区域记录

程序的执行，在一段时间内只限于程序中的某一部分，因此对于单次突变时选择的突变位置，如果在测试阶段执行结束后，样本质量评估阶段表现优异，则确认该突变位置有价值。为了标记这些突变位置，采取对输入用例的每个字节位置设置唯一标识符的方案，在突变过程中记录相应的突变位置。在样本评估阶段，根据执行结果的表现，将当前突变位置及其附近几个单元视为热度区域，构建样本热点位图，为后续的突变环节提供指导，帮助突变模块生成更高质量的测试用例，从而提高测试的效率。

算法3 突变热点更新

算法3根据突变位置的表现来更新热点区域，可以为后续的突变环节提供指导，使测试主要用在执行高效的突变操作上。其中，updateHotzone方法用于更新热点区域，它根据所关注的几种运行结果状态，有以下三种更新：

a）如果执行结果包含crash，则说明当前选中的样本Hotzone的突变位置curMutatePos作为样本突变阶段的操作对象，存在相关字段的突变，导致程序测试过程出现crash，因此当前突变位置的热度会相应地提升。

b）如果执行结果显示本次测试过程覆盖了新的代码路径，则说明当前选中的样本Hotzone的突变位置curMutatePos作为样本突变阶段的操作对象，对于提升代码覆盖率有探索价值，因此当前突变位置的热度会相应地提升。

c）如果执行结果显示本次测试过程对受检程序的代码覆盖率没有提升，则说明当前选中的样本Hotzone的突变位置curMutatePos作为样本突变阶段的操作对象，对于提升代码覆盖率没有探索价值，因此当前突变位置的热度会相应地下降。

5 实验结果与分析

实验环境是6核3.0 GHz的Intel i5-12500H CPU，16 GB RAM，Ubuntu LTS 18.04操作系统。实验选用Otfcc、Swftools、Xpdf、Swfmill、PNGdec等16个开源应用。初始样本的收集来自对应项目的以往issue的相关POC文件，以及网络收集的作为输入的样本集，样本集的收集阶段能够很好地提升测试任务的起点。

a）采用本文方法在14个目标程序中测试发现了100余个未被公布的漏洞，均已获得了CVE 编号（见https：//cve.mitre.org/）。方法在检测错误数（crash）、去重后错误数（unique）、错误检出效率（EDE）以及是否执行样本修复（repaired？）方面的情况如表1所示，其中，错误检出效率是指在对应测试应用中每小时发现的错误数量。

b）本文方法对受检应用进行模糊检测后发现的新漏洞（部分）及其安全等级和所属漏洞类型如表2所示，其中所涉及的漏洞类型包括heap buffer overflow、use after free、stack overflow、global buffer overflow、FPE、memory leak、segmentation violation等。

c）实验将本文方法与随机发散的模糊测试方法AFL［7］及其优化方案FairFuzz［14］进行了对比。检测出的去重（unique）后的漏洞情况如表3所示，从整体（覆盖了发现漏洞的14个受检目标程序）的漏洞发现情况来看，针对已检出的漏洞类型，本文方法在检出能力上均有所提升。在测试时间段内，相较于随机发散的AFL和FairFuzz方法未能检出use after free这类与程序操作的先后顺序、执行逻辑强相关的漏洞，本文方法则有着很好的检出效果。其原因在于，尽管一些难以检测的安全漏洞常常与非常规程序执行流程或不正确的状态转换有关，而本文方法利用关键分支筛选得出这些敏感位置并进行干预，继而通过分支内部快速探索算法，对这类特殊逻辑相关的漏洞却有较好的检出能力提升。

另外，以Otfcc测试项目为例，对比本文方法与AFL和FairFuzz的随测试时间发展的测试结果，如图2所示，在漏洞发现情况以及unique漏洞发现情况的评估指标上，本文方法的表现均优于AFL和FairFuzz。在测试用时50 h内，随着测试用时的增加，模糊测试的深度与广度都会相应加大，检出的错误或漏洞也呈递增趋势。由于代码内部逻辑作为类树结构在实际中不能全覆盖，同时，因为理论上有无穷多的随机输入组合，使得模糊测试在理论上不会停止，但随着测试用时的投入，新发现的概率会越来越少，即在测试用时16 h之后的检出漏洞数增长趋势变缓。通常在测试过程中，距离上次发现新的代码分支或程序异常已经过去5 h（即时间限制）、达到预设的测试用例数、达到预设的代码覆盖率或路径覆盖率、发现预设数量的漏洞或错误，或者资源消耗达到预设极限等就可以终止测试［19］。

6 结束语

本文主要通过筛选并评估受检程序内部存在的诸多分支，筛选有价值位置进行探索，对筛选位置所涉及的分支挖掘更高的漏洞发现能力。这些具有探索价值较高的分支，受限于传统模糊测试方法在测试用例上的突变随机性，不能总是在测试过程中被纳入测试范围，通过分支内部快速探索模块中的干预分支选择方式完成对这些分支的测试。在模糊器生成测试用例阶段，根据测试用例的执行结果更新并维护样本突变热点区域，指导测试用例突变操作所作用的位置，向那些能带来效益提升的位置倾斜。实验结果验证了本文方法的有效性，相比于AFL和FairFuzz均有较大的漏洞发现能力的提升。不足之处在于，通过构建样本突变热点区域的方式指导突变操作的位置，虽然去除了传统模糊测试方法的随机性，但可能使得一些低频、被判定探索价值低的程序逻辑被测试忽略，因此可能存在一定的漏报。样本突变热点区域的多样性及热点能力细分是下一步研究的方向。

参考文献：

［1］Kumar R，Baz A，Alhakami H，et al. A hybrid fuzzy rule-based multi-criteria framework for sustainable-security assessment of Web application ［J］. Ain Shams Engineering Journal，2021，12（2）： 2227-2240.

［2］Weng Le，Feng Chao， Shi Zhiyuan，et al. FASSFuzzer—an automated vulnerability detection system for android system services ［J］. Journal of Computers（Taiwan），2022，33（2）： 189-200.

［3］Liu Xinyao， Cui Baojiang， Fu Junsong，et al. HFuzz： towards automa-tic fuzzing testing of NB-IoT core network protocols implementations ［J］. Future Generation Computer Systems，2020，108： 390-400.

［4］肖天，江智昊，唐鹏，等. 基于深度强化学习的高性能导向性模糊测试方案 ［J］. 网络与信息安全学报，2023，9（2）： 132-142. （Xiao Tian，Jiang Zhihao，Tang Peng，et al. High-performance directional fuzzing scheme based on deep reinforcement learning ［J］. Chinese Journal of Network and Information Security，2023，9（2）： 132-142.）

［5］卢昊良，邹燕燕，彭跃，等. 基于物联网设备局部仿真的反馈式模糊测试技术 ［J］. 信息安全学报，2023，8（1）： 78-92.（Lu Hao-liang，Zou Yanyan，Peng Yue，et al. Feedback-driven fuzzing techno-logy based on partial simulation of IoT devices ［J］. Journal of Cyber Security，2023，8（1）： 78-92.）

［6］Trippel T，Shin K G，Chernyakhovsky A，et al. Fuzzing hardware like software ［C］// Proc of the 31st USENIX Security Symposium. Berkeley，CA： USENIX Association，2022： 3237-3254.

［7］Fioraldi A，Mantovani A，Maier D，et al. Dissecting American fuzzy lop： a FuzzBench evaluation ［J］. ACM Trans on Software Engineering and Methodology，2023，32（2）： 1-26.

［8］王明哲，姜宇，孙家广. 模糊测试中的静态插桩技术 ［J］. 计算机研究与发展，2023，60（2）： 262-273.（Wang Mingzhe，Jiang Yu，Sun Jiaguang. Static instrumentation techniques in fuzzing testing ［J］. Journal of Computer Research and Development，2023，60（2）： 262-273.）

［9］刘盈盈，杨秋辉，姚邦国，等. 基于依赖模型的REST接口测试用例生成方法研究 ［J］. 计算机科学，2023，50（9）： 101-107.（Liu Yingying，Yang Qiuhui，Yao Bangguo，et al. Study on REST API test case generation method based on dependency model ［J］. Computer Science，2023，50（9）： 101-107.）

［10］李贺，张超，杨鑫，等. 操作系统内核模糊测试技术综述 ［J］. 小型微型计算机系统，2019，40（9）： 1994-1999.（Li He，Zhang Chao，Yang Xin，et al. Survey of OS kernel fuzzing ［J］. Journal of Chinese Computer System，2019，40（9）： 1994-1999.）

［11］Dinesh S，Burow N，Xu Dongyan，et al. RetroWrite： statically instrumenting cots binaries for fuzzing and sanitization ［C］// Proc of the 41st IEEE Symposium on Security and Privacy. Piscataway，NJ： IEEE Press，2020： 1497-1511.

［12］佘庚达，付才，岑泽威，等. 基于适应度和输入约束模型的内核驱动漏洞挖掘 ［J］. 计算机应用研究，2023，40（7）： 2151-2156.（She Gengda，Fu Cai，Cen Zewei，et al. Kernel driver vulnerability mining based on fitness and input constraint model ［J］. Application Research of Computers，2023，40（7）： 2151-2156.）

［13］Li Yuekang， Chen Bihuan， Chandramohan M，et al. Steelix： program-state based binary fuzzing ［C］// Proc of the 11th Joint Meeting on Foundations of Software EnfX2igwv9iyZlYBGZ/wp3oUygL97nN0fLjMeVyvB3oAM=gineering. New York： ACM Press，2017： 627-637.

［14］Lemieux C，Sen K. FairFuzz： a targeted mutation strategy for increasing greybox fuzz testing coverage ［C］// Proc of the 33rd ACM/IEEE International Conference on Automated Software Engineering. Piscataway，NJ： IEEE Press，2018：475-485.

［15］Ganesh V，Leek T，Rinard M. Taint-based directed whitebox fuzzing ［C］// Proc of the 31st International Conference on Software Engineering. Washington DC： IEEE Computer Society，2009： 474-484.

［16］Ma Mingrui，Han Lansheng，Qian Yekui. CVDF DYNAMIC—a dynamic fuzzy testing sample generation framework based on BI-LSTM and genetic algorithm ［J］. Sensors，2022，22（3）： 1265.

［17］戴渭，陆余良，朱凯龙. 结合混合符号执行的导向式灰盒模糊测试技术 ［J］. 计算机工程，2020，46（8）： 190-196.（Dai Wei，Lu Yuliang，Zhu Kailong. Directed grey-box fuzzing test technology combining mixed symbolic execution ［J］. Computer Engineering，2020，46（8）： 190-196.）

［18］吴皓，周世龙，史东辉，等. 符号执行技术及应用研究综述 ［J］. 计算机工程与应用，2023，59（8）： 56-72.（Wu Hao，Zhou Shilong，Shi Donghui，et al. Review of symbolic execution technology and applications ［J］. Computer Engineering and Applications，2023，59（8）： 56-72.）

［19］Bohme M，Pham V T，Roychoudhury A. Coverage-based greybox fuz-zing as Markov chain ［J］. IEEE Trans on Software Engineering，2019，45（5）： 489-506.