基于覆盖频率的模糊测试改进方法

模糊测试是当前检测程序错误的最主流、最有效的手段之一.模糊测试工具首先对种子文件进行变异,生成大量新输入文件,然后挑选新输入来执行目标程序,以触发程序中潜在的漏洞.当前对模糊测试的研究多着眼于改进变异算法,提高生成的新文件对目标程序代码的覆盖,忽略了备用种子文件的筛选策略对提高模糊测试覆盖率与测试效率的的贡献.针对该问题,我们提出了基于覆盖频率的种子文件筛选策略,在每次执行目标程序时,我们记录程序执行中覆盖过的路径边;根据边被执行次数的多少,我们将这些边分为低频边和高频边;对于包含了更多低频边且执行效率高的种子文件,我们给予更高的优先级.我们在模糊测试工具American Fuzzy Lop （AFL）实现了对应的算法,实验表明我们的算法有效提高了模糊测试的效率和代码覆盖率.     

可编程模糊测试技术

模糊测试是一种有效的漏洞挖掘技术.为改善模糊测试因盲目变异而导致的效率低下的问题,需要围绕输入特征、变异策略、种子样本筛选、异常样本发现与分析等方面不断定制模糊测试器,从而花费了大量的定制成本.针对通用型模糊测试器（即支持多类输入格式及目标软件的模糊测试器）的低成本定制和高可扩展性需求,本文首次提出了一种可编程模糊测试框架,基于该框架漏洞挖掘人员仅需编写模糊测试制导程序即可完成定制化模糊测试,在不降低模糊测试效果的基础上可大幅提高模糊测试器开发效率.该框架包含一组涉及变异、监控、反馈等环节的模糊测试原语,作为制导程序的基本语句;还包含一套编程规范（FDS）及FDS解析器,支持制导程序的编写、解析和模糊测试器的生成.基于实现的可编程模糊测试框架原型Puzzer,在26个模糊测试原语的支持下,漏洞挖掘人员平均编写54行代码即可实现当前主流的5款万级代码模糊测试器的核心功能,并可覆盖总计87.8%的基本操作.基于Puzzer实现的AFL等价模糊测试器,仅用51行代码即可达到与AFL相当的模糊测试效果,具有良好的有效性.     

基于深度学习的模糊测试种子生成技术

模糊测试被广泛应用于各种软件和系统的漏洞挖掘中.而模糊测试的效果与其采用的变异策略以及初始种子文件的代码覆盖率有直接的关系.本文提出了一种基于深度学习的种子文件生成方法,分析并学习初始种子文件和其在目标程序中的执行路径之间的关系,最终输出可能覆盖新执行路径的种子文件,从而提高初始种子文件集合的代码覆盖率.我们以PDF阅读器作为目标程序进行了实验,实验结果表明该方法所生成的种子文件保证了良好的通过率,而且明显提高了代码覆盖率.同时实验证明该方法在针对多种PDF阅读器进行模糊测试时都获得了更高的代码覆盖率.     

面向二进制程序的导向性模糊测试方法

为了解决当前模糊测试技术中变异存在一定的盲目性以及变异生成的样本大多经过相同的高频路径的问题，提出并实现了一种基于轻量级程序分析技术的二进制程序模糊测试方法。首先对目标二进制程序进行静态分析来筛选在模糊测试过程中阻碍样本文件深入程序内部的比较指令；随后对目标文件进行插桩来获取比较指令中操作数的具体值，并根据该具体值为比较指令建立实时的比较进度信息，通过比较进度衡量样本的重要程度；然后基于模糊测试过程中实时的路径覆盖信息为经过稀有路径的样本增加其被挑选进行变异的概率；最后根据比较进度信息并结合启发式策略有针对性地对样本文件进行变异，通过变异引导提高模糊测试中生成能够绕过程序规约检查的有效样本的效率。实验结果表明，所提方法发现crash及发现新路径的能力均优于模糊测试工具AFL-Dyninst。     

基于机器学习的模糊测试种子输入优化

模糊测试作为一种自动化检测应用程序漏洞的方法, 常常被用来检测各种软件以及计算机系统的漏洞挖掘中. 而种子文件质量的高低对于模糊测试的效果而言至关重要. 所以本文提出了一种基于机器学习的模糊测试种子输入的生成方法, 利用样本输入和基于机器学习的技术来学习样本输入的规则和语法. 并利用学到的规则和语法来生成全新的种子输入...     

基于模式生成的浏览器模糊测试技术

模糊测试被广泛应用于浏览器的漏洞挖掘,其效果好坏的决定因素之一是测试者编写的测试模式.针对特定测试模式实现成本高、生存时间短等问题,本文提出了一种基于模式生成的浏览器模糊测试器自动构造方法,通过解析已知漏洞触发样本,自动提取测试模式,对模式中每个模块应用传统的变异策略,完成畸形样本的自动生成.实验表明,针对5款浏览器的1089个已知漏洞触发样本,平均仅用时11.168秒即可完成1089个不同模糊测试器的自动构建,远低于人为编写的时间消耗;随机选取其中10个模糊测试器分别对IE 10、IE 11、Firefox 54.0的全补丁版本进行测试,共产生57个不同的崩溃样本,发现1个高危未知漏洞,证明本方法具有较好的未知漏洞发现能力.     

基于聚类和新覆盖信息的模糊测试改进

模糊测试在挖掘软件安全漏洞、提高软件安全性方面发挥着巨大的作用,本文针对模糊测试变异策略效率较低以及种子评分策略不合理的问题进行了讨论,提出了基于聚类的变异优化策略和基于新覆盖信息的能量分配策略.第1个改进策略通过产生新覆盖的非确定性变异提取有效的组合变异位置,然后利用聚类算法进一步确定有效变异的位置,在变异阶段对有效变异的位置进行细粒度确定性变异.本文第2个改进策略针对种子评分策略,种子产生的新覆盖信息与静态分析的分支转移信息作为种子评分的重要指标.我们将改进后的模糊测试工具-AgileFuzz与现有的模糊测试改进工具AFL 2.52b、AFLFast以及EcoFuzz进行比较,对binutils、libxmll2等开源程序进行了多次实验.实验结果表明, AgileFuzz在相同时间内发现了更多的程序分支覆盖,并且在测试过程中发现了fontforge、harfbuzz等开源软件中5个未知的漏洞.     

基于深度强化学习的高性能导向性模糊测试方案

随着移动互联网与信息技术的快速发展,越来越多的应用程序融入人们的生活,但这些应用程序中存在的漏洞严重威胁着用户隐私和信息安全。近年来,模糊测试作为流行的漏洞挖掘技术之一,因其漏洞易复现且误报率低的特点而被广泛地使用。它能随机生成测试用例并执行程序,通过覆盖率或样本生成方面的优化以检测更深的程序路径。但是模糊测试中的变异操作存在一定的盲目性,易使生成的测试样本执行相同程序路径。因此传统模糊测试普遍存在挖掘效率低、输入构造的随机性强、算法对程序结构针对性有限等问题。针对上述问题,提出了基于深度强化学习的高性能导向性模糊测试方案,通过程序插桩等方法获取程序运行时的信息,使用深度强化学习网络指导模糊测试选择测试样本,生成有针对性和导向性的测试样本以快速逼近并检验可能存在漏洞的程序路径,从而提高模糊测试的效率。实验表明,在LAVA-M测试集与真实应用程序LibPNG和Binutils上,所提方案比流行模糊测试工具AFL与AFLGO在漏洞检测与复现等方面有着更好的表现,因此该方案可为今后的漏洞挖掘和安全研究提供支撑。     

变异策略感知的并行模糊测试研究

模糊测试（fuzzing）具备自动化程度高、可重现性好及易扩展等特点,是软件漏洞挖掘的有效方法之一。针对其固有的测试盲目性和低效性,一批先进的灰盒模糊测试方法被提出并应用在AFL、AFLFast、Vuzzer等工具中。随着高性能芯片和云计算技术的发展,模糊测试可以充分利用其中蕴含的丰富并行计算能力、通过多实例并行的手段进一步提高单位时间内的综合测试效率,典型的代表如Xu等人提出的多核并行方法、谷歌的ClusterFuzz等。但现有并行模糊测试方法,由于不同测试实例在测试用例生成过程中缺少有效的控制,导致生成的畸形样本冗余高、测试综合覆盖率低等问题。针对该问题,本文提出了一种有效控制多测试实例间模糊测试过程的方案,该方案以变异策略为基本粒度进行并行化,定期同步不同测试实例间的有效畸形样本和优化变异策略应用比例,减少不同测试实例间的测试冗余,提高测试综合覆盖率。本文实现了一个变异策略感知的并行模糊测试框架,并选择AFL作为基本模糊测试器,使用5款开源软件及LAVA-M测试集的实验结果表明,相同测试时间内本文的方法比AFL默认调度方法提高目标覆盖率达132%、发现异常数量最多提高50余倍。     

基于LSTM和动态策略的定向灰盒模糊测试技术

定向模糊测试旨在快速生产测试用例,达到给定的程序目标位置区域并发现程序错误。但目前的定向模糊测试工具普遍存在测试效率较低的问题,为此提出了一种基于神经网络的定向灰盒模糊测试方法,通过学习过去的模糊探索输入文件中不同位置的变异模式以生成模型来预测当前种子能够产生输入增益的位置,从而指导模糊器进行优化突变。同时为了解决定向灰盒模糊器中探索与开发的权衡问题,引入了一种动态策略在模糊测试过程中自适应协调两个阶段。基于现有的模糊测试框架AFL实现了一个原型系统,命名为DYNFuzz,并在3个基准上对其进行了测试和评估,实验结果表明,DYNFuzz具有比其他模糊器更高的定向性能和测试效率,并且不会陷入由探索开发不平衡导致的局部困境。     

利用分支路径差异分析的故障定位研究

为了更加有效地定位软件故障可疑位置,考虑程序分支判断语句的行为状态及其之间的相互干扰,提出一种利用分支路径差异分析的故障定位方法。结合GCC编译器产生的中间文件做分析、转换得到程序抽象语法树,获取分支节点的执行信息,构造分支特征矩阵;提出聚类优化算法FCM-BP筛选合适路径,得到高度抗干扰的执行成功的路径代表和执行失败的路径代表;最后基于代表路径做差异分析生成故障可疑度排名报告。在Xerces等大型项目上进行实验分析并与Tarantula等经典实验对比后发现,利用分支路径差异的方法可以有效定位软件故障。     

一种快速程序最坏执行时间分析方法研究

给出一种带有路径冲突检测的程序最坏情况执行时间估计方法,这种方法首先检测程序中存在的分支约束,然后将程序中存在的分支约束信息转化为程序流程控制图（CFG图）中结点之间的语义冲突,并按照结点对的形式保存在相应的冲突数组里,在接下来的WCET计算阶段通过边搜索程序执行路径边检测冲突数组里保存的已有的冲突关系以便在搜索路径的同时排除非可行执行路径,最终在可行执行路径集中选择具有最大执行时间的执行路径。与以往的方法相比,在保持估计精度的前提下,本文的方法避免了穷举所有执行路径带来的复杂度,提高了搜索的效率。实验结果表明本文方法对于语句间语义依赖关系比较强的实时程序能够快速且有效地给出估计结果。     

相关路径静态分析中协同式逆向推理方法

相关路径生成,是程序动态分析中的一种重要方法.通过对目标执行路径的获取和分析来生成与其相关的近邻执行路径,在程序行为特征分析、编译优化和调试等研究方向有重要的作用.现有的方法主要通过改变路径节点序列来生成近邻的路径集合,由于缺乏关键节点的路径引导信息,导致生成大量冗余或者无效的路径集合.提出采用协同式逆向分析的近邻路径生成方法,针对目标路径的后置条件,采用逆向符号分析方法产生程序各个基本块的前置条件作为执行路径的引导信息.同时,通过调整距离因子k的取值,可以有针对性地生成与目标路径的编辑距离不超过k的近邻路径集合.实验结果表明:与现有方法相比,该方法在准确性和效率方面有明显的优势.     

Dynamic method for software test data generation

Test data generation in program testing is the process of identifying a set of test data which satisfies a given testing criterion. Existing pathwise test data generators proceed by selecting program paths that satisfy the selected criterion and then generating program inputs for these paths. One of the problems with this approach is that unfeasible paths are often selected; as a result, significant computational effort can be wasted in analysing those paths. In this paper, an approach to test data generation, referred to as a dynamic approach for test data generation, is presented. In this approach, the path selection stage is eliminated. Test data are derived based on the actual execution of the program under test and function minimization methods. The approach starts by executing a program for an arbitrary program input. During program execution for each executed branch, a search procedure decides whether the execution should continue through the current branch or an alternative branch should be taken. If an undesirable execution flow is observed at the current branch, then a real-valued function is associated with this branch, and function minimization search algorithms are used to locate values of input variables automatically, which will change the flow of execution at this branch.     

有效覆盖引导的定向灰盒模糊测试

定向灰盒模糊测试技术在度量种子对目标执行状态的搜索能力时,除了考虑种子逼近目标代码的程度之外,还需要分析种子对多样化执行状态的发现能力,从而避免陷入局部最优.现有的定向灰盒模糊测试主要根据全程序的覆盖统计来度量种子搜索多样化执行路径的能力.然而,目标执行状态仅依赖于部分程序代码.如果带来新覆盖的种子并未探索到目标状态计算所依赖的新执行状态,其不仅不能扩大种子队列对目标执行状态的搜索能力,而且会诱导测试目标无关的代码和功能,阻碍定向测试向目标代码的收敛.为了缓解该问题,从待发现目标执行状态依赖代码的覆盖统计着手,提出了一种有效覆盖引导的定向灰盒模糊测试方法.利用程序切片技术提取影响目标执行状态计算的代码.通过能量调度（即控制种子后代生成数量）,提升引发该部分代码控制流新覆盖变化的种子能量,降低其他冗余种子的能量,使定向灰盒模糊测试专注于搜索目标相关的执行状态.在测试集上的实验结果显示,该方法显著提升了目标状态发现效率.     

基于路径引导的回归测试用例集扩增方法

为了全面测试演化软件,回归测试通常需要生成新的测试用例。concolic测试是一种沿着具体执行路径进行符号执行的软件验证技术,通过生成测试数据来执行程序的所有可行路径。回归测试中,由于concolic测试关注于程序本身,没有利用已有测试用例和软件演化信息,导致生成大量无效测试数据,浪费资源和时间。为解决此问题,提出一种基于路径引导的回归测试用例集扩增方法。该方法将目标路径作为引导,根据软件演化信息选择有利于覆盖目标路径的测试用例,利用已有测试用例跳过重叠初始子路径,对后续目标子路径进行concolic测试并生成覆盖目标路径的测试数据。案例分析表明,本文方法相比传统concolic测试,本方法在覆盖程序可行路径的同时,可有效减少concolic测试路径,提高测试数据生成效率。     

Symbolic execution of floating‐point computations

Symbolic execution is a classical program testing technique which evaluates a selected control flow path with symbolic input data. A constraint solver can be used to enforce the satisfiability of the extracted path conditions as well as to derive test data. Whenever path conditions contain floating‐point computations, a common strategy consists of using a constraint solver over the rationals or the reals. Unfortunately, even in a fully IEEE‐754‐compliant environment, this leads not only to approximations but also can compromise correctness: a path can be labelled as infeasible although there exists floating‐point input data that satisfy it. In this paper, the peculiarities of symbolic execution of programs with floating‐point numbers are addressed. Issues in the symbolic execution of this kind of program are carefully examined and a constraint solver is described that supports constraints over floating‐point numbers. Preliminary experimental results demonstrate the value of the approach proposed. Copyright © 2005 John Wiley & Sons, Ltd.     

A multiple-population genetic algorithm for branch coverage test data generation

The software testing phase in the software development process is considered a time-consuming process. In order to reduce the overall development cost, automatic test data generation techniques based on genetic algorithms have been widely applied. This research explores a new approach for using genetic algorithms as test data generators to execute all the branches in a program. In the literature, existing approaches for test data generation using genetic algorithms are mainly focused on maintaining a single-population of candidate tests, where the computation of the fitness function for a particular target branch is based on the closeness of the input execution path to the control dependency condition of that branch. The new approach utilizes acyclic predicate paths of the program’s control flow graph containing the target branch as goals of separate search processes using distinct island populations. The advantages of the suggested approach is its ability to explore a greater variety of execution paths, and in certain conditions, increasing the search effectiveness. When applied to a collection of programs with a moderate number of branches, it has been shown experimentally that the proposed multiple-population algorithm outperforms the single-population algorithm significantly in terms of the number of executions, execution time, time improvement, and search effectiveness.