基于符号执行与模糊测试的混合测试方法

软件测试是保障软件质量的常用方法,如何获得高覆盖率是测试中十分重要且具有挑战性的研究问题.模糊测试与符号执行作为两大主流测试技术已被广泛研究并应用到学术界与工业界中,这两种技术都具有一定的优缺点：模糊测试随机变异生成测试用例并动态执行程序,可以执行并覆盖到较深的分支,但其很难通过变异的方法生成覆盖到复杂条件分支的测试用例.而符号执行依赖约束求解器,可以生成覆盖复杂条件分支的测试用例,但在符号化执行过程中往往会出现状态爆炸问题,因此很难覆盖到较深的分支.有工作已经证明,将符号执行与模糊测试相结合可以获得比单独使用模糊测试或者符号执行更好的效果.分析符号执行与模糊测试的优缺点,提出了一种基于分支覆盖将两种方法结合的混合测试方法——Afleer,结合双方优点从而可以生成具有更高分支覆盖率的测试用例.具体来说,模糊测试（例如AFL）为程序快速生成大量可以覆盖较深分支的测试用例,符号执行（例如KLEE）基于模糊测试的覆盖信息进行搜索,仅为未覆盖到的分支生成测试用例.为了验证Afleer的有效性,选取标准程序集LAVA-M以及实际项目oSIP作为评测对象,以漏洞检测能力以及覆盖能力作为评测指标.实验结果表明：（1）在漏洞检测能力上,Afleer总共可以发现755个漏洞,而AFL仅发现1个;（2）在覆盖能力上,Afleer在标准程序集上以及实际项目中都有不同程度的提升.其中,在oSIP中,Afleer比AFL在分支覆盖率上提高2.4倍,在路径覆盖率上提升6.1倍.除此之外,Afleer在oSIP中还检测出一个新的漏洞.     

符号执行研究综述

符号执行作为一种重要的程序分析方法,可以为程序测试提供高覆盖率的测试用例,以触发深层的程序错误。首先,介绍了经典符号执行方法的原理;然后,阐述了基于符号执行发展形成的混合测试、执行生成测试和选择性符号执行方法,同时,对制约符号执行方法在程序分析中的主要因素进行了分析,并讨论了缓解这些问题和提高符号执行可行性的主要方法;随后,介绍了当前主流的符号执行分析工具,并比较分析了其优缺点;最后,总结并讨论了符号执行的未来发展方向。     

遗传算法辅助的动态符号执行测试方法

动态符号执行是一种有效的软件测试方法,但由于受到约束求解器求解能力的限制,在面对较为复杂的程序和路径条件时,动态符号执行的路径覆盖率还有待提升。针对上述问题,提出了一种遗传算法辅助的动态符号执行测试方法,并基于此方法实现了原型工具JDart-Ga。该方法结合遗传算法的优势,生成约束求解器无法求解的约束条件对应测试输入,从而提升动态符号执行的路径覆盖率。实验结果表明,在测试存在动态符号执行无法覆盖路径的3个实验对象时,所提出方法的路径覆盖率与JDart相比分别提升了16%至23%。     

基于参数约束的分支覆盖符号执行优化算法

软件质量检测常用的方法是软件测试,符号执行作为主流的测试技术已被广泛应用于学术界与工业界中。但是随着程序规模的增大和函数调用的增加,因某些路径约束条件的特殊性,而难以生成正确的测试用例,从而导致符号执行不能对所有路径做到全覆盖。为了提高符号执行在特殊约束条件对路径的覆盖率等问题,本文提出了基于参数约束的符号执行优化算法。首先,该算法通过搜索收集程序代码中函数的特殊参数,然后利用这些特殊参数作为约束条件,最后将约束条件添加到路径的约束集中。该算法使符号执行生成的测试用例更加精确,从而实现覆盖特殊约束条件下的路径分支,以提高符号执行的精确性和路径覆盖率。在开源符号执行平台CREST中实验并验证上述优化算法,验证及测试结果表明本文提出的算法能够提高符号执行在特殊约束条件下对路径的覆盖率。     

二进制代码的漏洞挖掘技术研究

基于网络信息安全漏洞问题越来越受重视,针对漏洞研究中测试代码覆盖率和漏洞挖掘效率问题,设计并实现了基于混合符号执行的Fuzzing测试系统;该系统采用了指令动态追踪、混合符号执行、约束求解、测试用例生成及动态测试5个模块,通过对系统各个环节优化处理提高效率,并实验验证系统代码覆盖率较传统Fuzzing测试工具也有较大提高,得出了该系统能适用于大型应用软件测试的结论。     

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

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

SymFuzz:一种复杂路径条件下的漏洞检测技术

当前漏洞检测技术可以实现对小规模程序的快速检测,但对大型或路径条件复杂的程序进行检测时其效率低下。为实现复杂路径条件下的漏洞快速检测,文中提出了一种复杂路径条件下的漏洞检测技术SymFuzz。SymFuzz将导向式模糊测试技术与选择符号执行技术相结合,通过导向式模糊测试技术对程序路径进行过滤,利用选择符号执行技术对可能触发漏洞的路径进行求解。该技术首先通过静态分析获取程序漏洞信息;然后使用导向式模糊测试技术,快速生成可以覆盖漏洞函数的测试用例;最后对漏洞函数内可以触发漏洞的路径进行符号执行,生成触发程序漏洞的测试用例。文中基于AFL与S2E等开源项目实现了SymFuzz的原型系统。实验结果表明,SymFuzz与现有的模糊测试技术相比,在复杂路径条件下的漏洞检测效果提高显著。     

自动化白盒模糊测试技术研究

软件的安全性分析和漏洞检测是软件工程和信息安全领域的一个研究热点和难点问题。采用程序分析的方法对软件进行安全性测试,日益受到广泛的关注和重视。首先概述了有关软件安全性测试的基本概念;随后,详细介绍了3种基于程序分析的安全性测试方法:模糊测试、符号执行和自动化白盒模糊测试,并比较了这3种方法的优缺点;最后,给出了自动化白盒模糊测试的分布式模型。     

ADFuzz：使用异常检测筛选低频路径高效模糊测试

基于覆盖率引导的模糊测试（Fuzzing）是当前最有效的漏洞自动挖掘技术.目前大部分的模糊测试工具对于新产生的测试用例实施全追踪策略.但是随着时间的流逝,模糊工具生成的测试用例都集中在程序的高频路径,使能够产生新覆盖的测试用例远少于已生成测试用例的总数,以至于全追踪策略花费了大量无意义的时间成本和运行开销.因此提出基于异常检测模型的模糊测试工具ADFuzz,筛选低频路径以减少高频路径的执行次数,从而加速模糊测试,持续引导模糊测试朝着低频路径方向变异运行,并扩大程序覆盖.通过ADFuzz,AFL,Untracer在12个真实程序上运行24 h的实验结果显示,相比AFL,ADFuzz平均速度提升23.8%,平均覆盖率增加11.78%,最高增加25.8%;相比Untracer,ADFuzz平均速度降低较少,但是漏洞数量和覆盖率都有较大提升.     

基于静态分析的Android GUI遍历方法

针对传统软件安全测试方法（例如：符号执行、模糊测试、污点分析等）无法获得较高的Android程序图形用户界面（GUI）覆盖率的问题,提出动态和静态相结合的Android程序测试方法。该方法在静态分析Android应用程序数据流的基础之上,构建程序活动转换图和函数调用图,解析程序GUI元素,进而编写测试脚本动态遍历应用程序GUI元素。将该方法应用于订票日历、WiFi万能钥匙和360天气应用的实际测试,结果表明：Activity的平均覆盖率达到76%,明显高于人工测试的平均值30.08%和基于控件树遍历的42.05%~61.29%,该方法能够有效遍历Android应用程序GUI元素。     

Deep Learning-Based Hybrid Fuzz Testing

With the rapid development of software techniques, domain-driven software raises new challenges in software security and robustness. Symbolic execution and fuzzing have been rapidly developed in recent decades, demonstrating their ability in detecting software bugs. Enormous detected and fixed bugs prove the feasibility of the two methods. However, it is still a challenging task to combine the two methods due to their respective weaknesses. State-of-the-art techniques focus on incorporating the two methods such as using symbolic execution to solve paths when fuzzing gets stuck in complex paths. Unfortunately, such methods are inefficient because they have to switch to fuzzing (resp. symbolic execution) when performing symbolic execution (resp. fuzzing). This paper presents a novel deep learning-based hybrid testing method using symbolic execution and fuzzing. The method tries to predict paths that are suitable for fuzzing (resp. symbolic execution) and use the fuzzing (resp. symbolic execution) to reach the paths. To further enhance effectiveness, this paper also proposes a hybrid mechanism to make them interact with each other. The proposed approach is evaluated on the programs in LAVA-M, and the results are compared with those in the case of using symbolic execution or fuzzing independently. It achieves more than 20\% increase in branch coverage and 1 to 13 times increase in the path number and uncovers 929 more bugs.     

SimFuzz: Test case similarity directed deep fuzzing

Fuzzing is widely used to detect software vulnerabilities. Blackbox fuzzing does not require program source code. It mutates well-formed inputs to produce new ones. However, these new inputs usually do not exercise deep program semantics since the possibility that they can satisfy the conditions of a deep program state is low. As a result, blackbox fuzzing is often limited to identify vulnerabilities in input validation components of a program. Domain knowledge such as input specifications can be used to mitigate these limitations. However, it is often expensive to obtain such knowledge in practice. Whitebox fuzzing employs heavy analysis techniques, i.e., dynamic symbolic execution, to systematically generate test inputs and explore as many paths as possible. It is powerful to explore new program branches so as to identify more vulnerabilities. However, it has fundamental challenges such as unsolvable constraints and is difficult to scale to large programs due to path explosion. This paper proposes a novel fuzzing approach that aims to produce test inputs to explore deep program semantics effectively and efficiently. The fuzzing process comprises two stages. At the first stage, a traditional blackbox fuzzing approach is applied for test data generation. This process is guided by a novel test case similarity metric. At the second stage, a subset of the test inputs generated at the first stage is selected based on the test case similarity metric. Then, combination testing is applied on these selected test inputs to further generate new inputs. As a result, less redundant test inputs, i.e., inputs that just explore shallow program paths, are created at the first stage, and more distinct test inputs, i.e., inputs that explore deep program paths, are produced at the second stage. A prototype tool SimFuzz is developed and evaluated on real programs, and the experimental results are promising.     

Using symbolic execution to guide test generation

Although a number of weaknesses of symbolic execution, when used for software testing, have been highlighted in the literature, the recent resurgence of strongly‐typed languages has created opportunities for re‐examining symbolic execution to determine whether these shortfalls can be overcome. This paper discusses symbolic execution in general and makes two contributions: (a) overcoming one of the key problems, analysing programs with indexed arrays; and (b) describing the incorporation of a symbolic execution module for test case generation into an integrated testing tool. For methods which index arrays, a new approach determines all the possible values of each array index, allowing the generation of equivalence classes for every possible combination of array element aliases. An incremental simplification approach, which converts path expressions to canonical forms in order to identify infeasible paths at the earliest opportunity and thus reduce the analysis time, is also described. Symbolic execution is most effective when included in an integrated test and analysis environment: a component test bench was built with a symbolic execution module integrated into it, providing a toolbox of software component test and code analysis methods aimed at programmers at all levels. Copyright © 2000 John Wiley & Sons, Ltd.     

ovAFLow: Detecting Memory Corruption Bugs with Fuzzing-Based Taint Inference

Grey-box fuzzing is an effective technology to detect software vulnerabilities, such as memory corruption. Previous fuzzers in detecting memory corruption bugs either use heavy-weight analysis, or use techniques which are not customized for memory corruption detection. In this paper, we propose a novel memory bug guided fuzzer, ovAFLow. To begin with, we broaden the memory corruption targets where we frequently identify bugs. Next, ovAFLow utilizes light-weight and effective methods to build connections between the fuzzing inputs and these corruption targets. Based on the connection results, ovAFLow uses customized techniques to direct the fuzzing process closer to memory corruption. We evaluate ovAFLow against state-of-the-art fuzzers, including AFL (american fuzzy lop), AFLFast, FairFuzz, QSYM, Angora, TIFF, and TortoiseFuzz. The evaluation results show better vulnerability detection ability of ovAFLow, and the performance overhead is acceptable. Moreover, we identify 12 new memory corruption bugs and two CVEs (common vulnerability exposures) with the help of ovAFLow.     

Hunter:一种指令集体系结构无关的二进制级动态测试用例生成技术

动态测试用例生成技术是一类新兴的软件测试技术。由于使用该类技术无需任何人工干预,也无需验证人员具备任何专业知识,同时该类技术能够无误地发现程序错误,越来越多的研究者采用该技术查找预发布的二进制级软件错误。然而,已有的该类技术及其实现系统不具有可重定向性,只能处理面向某种特定指令集体系结构(ISA)的二进制代码,进行测试用例的生成与查错。本文提出了一种全新的指令集体系结构无关的二进制级动态测试用例生成技术,以及实现该技术的系统Hunter。与已有的动态测试用例生成技术不同,Hunter具有极强的可重定向性,可对任何指令集体系结构的二进制代码进行查错,定向地为其生成指向不同执行路径的测试用例。Hunter定义了一套元指令集体系结构(MetaISA),将在二进制代码执行过程中收集到的所有执行信息映射为MetaISA,并对生成的MetaISA序列进行符号化执行、约束收集、约束求解以及测试用例生成,从而使整个过程与ISA无关。我们实现了Hunter,将其重定向至32位x86、PowerPC和Sparc ISA,并使用该系统为6个含有已知错误的测试程序查错。实验结果表明,由于MetaISA的引入,只需很小的开销,Hunter系统即可容易且有效地重定向至不同的ISA,并且Hunter能够有效地发现面向32位x86、PowerPC和Sparc ISA编写的二进制应用中隐藏极深的错误。     

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

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

支持形状分析的符号执行引擎的设计与实现

目前提高软件可靠性的方法有3种:动态测试、静态分析和程序验证。动态测试的结果依赖于测试集的设计,误报率低,漏报率高,分析结果不稳定。程序验证可以对程序的各种性质进行完备的验证。但目前程序验证通常都需要手动证明,分析成本最高。而程序静态分析可以更早、更全面、较高效和低成本地检测到程序中的缺陷。其中符号执行技术是一种比较有应用前景的静态分析技术,可以很好地控制 精确度。针对符号执行可伸缩性差和容易产生路径爆炸的问题,在符号执行过程中利用形状分析技术实现自动推导循环不变式和构建函数行为规范,实现了一个较为实用的C程序分析工具。     

Combining static concurrency analysis with symbolic execution

Static concurrency analysis detects anomalous synchronization patterns in concurrent programs, but may also report spurious errors involving infeasible execution paths. Integrated application of static concurrency analysis and symbolic execution sharpens the results of the former without incurring the full costs of the latter when applied in isolation. Concurrency analysis acts as a path selection mechanism for symbolic execution, while symbolic execution acts as a pruning mechanism for concurrency analysis. Methods of combining the techniques follow naturally from explicit characterization and comparison of the state spaces explored by each, suggesting a general approach for integrating state-based program analysis techniques in a software development environment