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

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

An integrated automatic test data generation system

The Godzilla automatic test data generator is an integrated collection of tools that implements a relatively new test data generation method—constraint-based testing—that is based on mutation analysis. Constraint-based testing integrates mutation analysis with several other testing techniques, including statement coverage, branch coverage, domain perturbation, and symbolic evaluation. Because Godzilla uses a rule-based approach to generate test data, it is easily extendible to allow new testing techniques to be integrated into the current system. This article describes the system that has been built to implement constraint-based testing. Godzilla's design emphasizes orthogonality and modularity, allowing relatively easy extensions. Godzilla's internal structure and algorithms are described with emphasis on internal structures of the system and the engineering problems that were solved during the implementation.Parts of this research were supported by Contract F30602-85-C-0255 through Rome Air Development Center while the author was a graduate student at the Georgia Institute of Technology.     

面向路径的测试数据生成框架及应用

测试数据生成是软件测试的核心与关键,本文介绍了迭代松弛法以及对迭代松弛法进行改进,改进后的方法比原方法生成测试数据的能力更强,不仅能够用于白盒测试数据的自动生成,还能够用于黑盒测试数据的自动生成。在此基础上提出一个面向路径的测试数据生成框架。并讨论该框架在单元测试、组装测试中的应用。     

基于演化算法的结构测试数据自动生成方法评述

结构测试数据自动生成是结构测试结构测试数据自动生成方法后,重点对基于演化算法的结构测试数据自动生成方法加以评述.归纳了该方法的基本思想和基本流程,按照适应度函数构造方式的不同将其划分为面向覆盖法、面向距离法和综合法三大类,并结合相关文献分析了这三类方法各自的技术特点,比较了各自的优劣.最后,指出了存在的不足,探讨了发展方向.     

符号执行中高语句覆盖率的路径调度

符号执行和约束求解相结合的软件测试方法采用深度优先搜索的路径调度算法会造成测试路径聚居性问题,实际软件中存在路径爆炸,使得采用该算法的测试语句覆盖率低下。提出一种新的PSHC路径调度算法。先将路径分为前缀和后缀两部分,每次测试总是试图寻找这样的路径,该路径与已存在的路径具有最短的相同前缀,并且包含尽可能多的尚未被访问过的基本块作为其后缀。基于Phoenix漏洞发掘工具的实验结果表明,PSHC算法可以迅速提高测试的语句覆盖率到100%,有效解决由于深度优先搜索的路径聚居性导致的测试代码的局部性问题,PSHC算法产生的路径数与循环深度无关,软件规模越大,该算法的表现越好。     

Generating test sequences using symbolic execution for event-driven real-time systems

Real-time software, often used to control event-driven process control systems, is usually structured as a set of concurrent and interacting tasks. Therefore, output values of real-time software depend not only on the input values but also on internal and nondeterministic execution patterns caused by task synchronization. In order to test real-time software effectively, one must generate test cases which include information on both the event sequences and the times at which various events occur. However, previous research on real-time software testing focused on generating the latter information. Our paper describes a method of generating test sequences from a Modechart specification using symbolic execution technique. Based on the notion of symbolic system configurations and the equivalence definitions between them, we demonstrate, using the railroad crossing system, how to construct a time-annotated symbolic execution tree and generate test sequences according to the selected coverage criteria.     

Issues in using model checkers for test case generation

The use of model checkers for automated software testing has received some attention in the literature: It is convenient because it allows fully automated generation of test suites for many different test objectives. On the other hand, model checkers were not originally meant to be used this way but for formal verification, so using model checkers for testing is sometimes perceived as a “hack”. Indeed, several drawbacks result from the use of model checkers for test case generation. If model checkers were designed or adapted to take into account the needs that result from the application to software testing, this could lead to significant improvements with regard to test suite quality and performance. In this paper we identify the drawbacks of current model checkers when used for testing. We illustrate techniques to overcome these problems, and show how they could be integrated into the model checking process. In essence, the described techniques can be seen as a general road map to turn model checkers into general purpose testing tools.     

An empirical investigation into branch coverage for C programs using CUTE and AUSTIN

Automated test data generation has remained a topic of considerable interest for several decades because it lies at the heart of attempts to automate the process of Software Testing. This paper reports the results of an empirical study using the dynamic symbolic-execution tool, CUTE, and a search based tool, AUSTIN on five non-trivial open source applications. The aim is to provide practitioners with an assessment of what can be achieved by existing techniques with little or no specialist knowledge and to provide researchers with baseline data against which to measure subsequent work. To achieve this, each tool is applied ‘as is’, with neither additional tuning nor supporting harnesses and with no adjustments applied to the subject programs under test. The mere fact that these tools can be applied ‘out of the box’ in this manner reflects the growing maturity of Automated test data generation. However, as might be expected, the study reveals opportunities for improvement and suggests ways to hybridize these two approaches that have hitherto been developed entirely independently.     

基于蚁群算法的软件测试数据自动生成

提出了一种基于蚁群算法的测试数据自动生成方法。该方法采用位串形式编码,实现了被测程序输入空间到蚂蚁路径网络的映射模型。根据程序插装函数定义的路径信息素轨迹强度,蚂蚁进行群体协作搜索最佳路径,生成测试数据。在基本蚁群算法基础上,通过引入变异算子和自适应挥发系数,提高了蚂蚁路径的多样性,克服了早熟停滞的缺陷。和模拟退火遗传算法进行了对比实验研究,结果表明了该方法的可行性,生成测试数据的效率优于模拟退火遗传算法。     

基于深度学习的混合模糊测试方法

随着软件技术的快速发展,面向领域的软件系统在广泛使用的同时带来了研究与应用上的新挑战.由于领域应用对安全性、可靠性有着很高的要求,而符号执行和模糊测试等技术在保障软件系统的安全性、可靠性方面已经发展了数十年,许多研究和被发现的缺陷表明了它们的有效性.但是,由于两者的优劣各有不同,将这两者相结合仍是近期热门研究的话题.目...     

Heuristics-based infeasible path detection for dynamic test data generation

Automated test data generation plays an important part in reducing the cost and increasing the reliability of software testing. However, a challenging problem in path-oriented test data generation is the existence of infeasible program paths, where considerable effort may be wasted in trying to generate input data to traverse the paths. In this paper, we propose a heuristics-based approach to infeasible path detection for dynamic test data generation. Our approach is based on the observation that many infeasible program paths exhibit some common properties. Through realizing these properties in execution traces collected during the test data generation process, infeasible paths can be detected early with high accuracy. Our experiments show that the proposed approach efficiently detects most of the infeasible paths with an average precision of 96.02% and a recall of 100% of all the cases.     

Validation and automatic test generation on UML models: the AGATHA approach

The related economic goals of test generation are quite important for software industry. Manufacturers ever seeking to increase their productivity need to avoid malfunctions at the time of system specification: the later the defaults are detected, the greater the cost is. Consequently, the development of techniques and tools able to efficiently support engineers who are in charge of elaborating the specification constitutes a major challenge whose fallout concerns not only sectors of critical applications but also all those where poor conception could be extremely harmful to the brand image of a product.This article describes the design and implementation of a set of tools allowing software developers to validate UML (the Unified Modeling Language) specifications. This toolset belongs to the AGATHA environment, which is an automated test generator, developed at CEA/LIST.The AGATHA toolset is designed to validate specifications of communicating concurrent units described using an EIOLTS formalism (Extended Input Output Labeled Transition System). The goal of the work described in this paper is to provide an interface between UML and an EIOLTS formalism giving the possibility to use AGATHA on UML specifications.In this paper we describe first the translation of UML models into the EIOLTS formalism, and the translation of the results of the behavior analysis, provided by AGATHA, back into UML. Then we present the AGATHA toolset; we particularly focus on how AGATHA overcomes several problems of combinatorial explosion. We expose the concept of symbolic calculus and detection of redundant paths, which are the main principles of AGATHA's kernel. This kernel properly computes all the symbolic behaviors of a system specified in EIOLTS and automatically generates tests by way of constraint solving. Eventually we apply our method to an example and explain the different results that are computed.     

基于内存建模的复杂结构类型测试数据自动生成方法

针对链表、树和图等这类复杂结构类型的测试数据自动生成问题,提出一种面向路径的基于内存建模的测试数据生成方法.采用一种将结构变量和数值变量分别建模的抽象内存模型,并利用此模型辅助符号执行被测路径;把路径执行过程中语句的语义操作映射到对抽象内存的操作,解决指针引起的别名问题,并且在抽象内存中精准地记录了路径的约束条件;最后通过约束求解得到测试数据.文中方法已应用于自主开发的自动单元测试系统——UATS,通过实验证明了该方法的可行件.     

An overview on test generation from functional requirements

Despite the fact that the test phase is described in the literature as one of the most relevant for quality assurance in software projects, this test phase is not usually developed, among others, with enough resources, time or suitable techniques.To offer solutions which supply the test phase, with appropriate tools for the automation of tests generation, or even, for their self-execution, could become a suitable way to improve this phase and reduce the cost constraints in real projects.This paper focuses on answering a concrete research question: is it possible to generate test cases from functional requirements described in an informal way? For this aim, it presents an overview of a set of relevant approaches that works in this field and offers a set of comparative analysis to determine which the state of the art is.     

基于符号执行的自动利用生成系统

在本文中,我们提出BAEG,一个自动寻找二进制程序漏洞利用的系统.BAEG为发现的每一个漏洞产生一个控制流劫持的利用,因此保证了它所发现的漏洞都是安全相关并且可利用的.BAEG针对输入造成程序崩溃的情况进行分析,面临的挑战主要有两点：1）如何重现崩溃路径,获取崩溃状态;2）如何自动生成控制流劫持利用.对于第一点,本论文提出路径导向算法,将崩溃输入作为符号值,重现崩溃路径.对于第二点,我们总结多种控制流劫持的利用原理,建立对应的利用产生模型.此外,对于非法符号读、写操作,BAEG还可以让程序从崩溃点继续执行,探索程序深层次代码,检测崩溃路径逻辑深处是否还有利用点.     

Automatic, evolutionary test data generation for dynamic software testing

This paper proposes a dynamic test data generation framework based on genetic algorithms. The framework houses a Program Analyser and a Test Case Generator, which intercommunicate to automatically generate test cases. The Program Analyser extracts statements and variables, isolates code paths and creates control flow graphs. The Test Case Generator utilises two optimisation algorithms, the Batch-Optimistic (BO) and the Close-Up (CU), and produces a near to optimum set of test cases with respect to the edge/condition coverage criterion. The efficacy of the proposed approach is assessed on a number of programs and the empirical results indicate that its performance is significantly better compared to existing dynamic test data generation methods.