基于路径覆盖插桩的可执行代码测试工具实现

为解决传统程序插桩技术存在代码膨胀和运行时间较长的问题,提出对可执行代码进行控制流路径覆盖消除冗余的插桩策略。依据该策略设计一种针对Java可执行代码的单元测试工具,完成程序执行路径跟踪和覆盖率分析。对测试工具进行功能验证和性能分析,结果表明,该策略能够有效减少插桩点数量,降低插桩对被测程序时间特性的影响。     

基于模型代数的基本路径集的自动生成

路径测试是一种根据路径设计测试用例的白盒测试技术,而 基本路径测试是其中运用最广泛的一种路径测试方法。基本路径测试是在被测程序的控制流图的基础上导出基本的可执行的路径集合,因此程序控制流图是基本路径集自动生成的关键。考虑到依赖程序控制流图生成基本路径集的低效性,提出基于模型代数的基本路径集的自动生成方法。该方法通过分析被测程序,自动生成程序的模型代数表达式,并在模型代数表达式的基础上生成基本路径集。最后通过经典案例证明了该方法的有效性。     

基于动态数据流分析的虚拟机保护破解技术

由于虚拟机采用虚拟化技术和代码混淆技术,采用传统的逆向分析方法还原被虚拟机保护的算法时存在较大困难。为此,提出一种基于动态数据流分析的虚拟机保护破解方法。以动态二进制插桩平台Pin作为支撑,跟踪记录被虚拟机保护的算法在动态执行过程中的数据流信息,对记录的数据流信息进行整理分析,获取虚拟机指令的解释执行轨迹,还原程序的控制流图,根据轨迹信息对数据生成过程进行分层次、分阶段还原,并由分析人员结合控制流图和数据生成过程进行算法重构。实验结果证明,该方法能够正确还原程序的控制流和数据生成过程,辅助分析人员完成被保护算法的重构。     

基于蜕变关系的多路径覆盖测试数据进化生成

提出一种基于蜕变关系的多路径覆盖测试数据生成方法。在多路径测试数据进化生成过程中,对于已生成的测试数据,利用被测程序的蜕变关系衍生新的测试数据,以新数据为输入执行被测程序,如果穿越的路径是未找到测试数据的目标路径,则该路径的测试数据同时被生成,从而提高多路径覆盖测试数据的进化生成效率。在典型三角形分类基准测试程序中的应用结果验证了该方法的有效性。     

一种基本路径集求解算法

McCabe提出的基本路径测试法被认为是动态白盒测试方法中严谨而有效的测试方法。如何提高基本路径测试的效率是人们一直在探索的问题。为此,从被测程序的基本结构出发,提出一种基于组合的基本路径求解算法。该算法首先创建一种基于Z路径覆盖的基本单元图;然后建立由基本单元图组合形成控制流图的组合规则;以此为基础,提出基本路径组合算法。该算法只需一次扫描程序得到程序基本结构的路径集,然后将这些路径进行组合生成被测程序的基本路径集。     

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

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

内存泄漏故障静态分析研究

目前研究人员主要采用静态测试技术实施对内存泄漏故障的检测,其基本思想就是依据待测程序的控制流图来设计特定的算法以检测内存泄漏问题,但这些方法的不足之处主要是控制流图的表示方式上未含有进一步可用信息,因此所设计的算法不能很好地执行该故障的检测任务.为此,定义了一种用于内存泄漏故障检测的控制流图,提出控制流图可达路径生成算法,然后根据生成的路径进行内存泄漏故障的检测与分析.实验证实,该方法取得了理想的效果.     

基于路径覆盖准则的AOP路径生成方法研究

在检验面向方面程序质量时,常常会依据路径覆盖准则对其进行测试,所以生成符合路径覆盖准则的AOP路径是很重要的。生成AOP路径,对AOP的控制流信息进行分析、表示,构造其单个模块、基本方面等的语句控制流图,确定类与方面之间交互的表示方法,构造出完整AOP语句控制流图;遍历完整AOP语句控制流图,得到从源节点到终节点的所有路径,这些路径中的可执行路径即是满足路径覆盖准则的测试路径。     

新的结构化测试数据自动生成方法

针对模拟退火算法,遗传算法应用于测试数据的自动生成的局限性,提出了一种基于GEMGA(基因表达散乱遗传算法)的结构化测试数据的自动生成的方法.讨论了路径的选择,提出了将控制流图与数据流图结合起来生成测试路径,通过TriType的分析结果说明了该方法的可行性.根据得到的测试路径将GEMGA应用到测试数据的自动生成,TdType的实验结果表明,GEMGA能生成更高质量的数据,并适用于较大规模的程序.     

基本路径测试用例设计算法

McCabe提出的基本路径测试法(McCABE T J. A complexity measure. IEEE Transactions on Software Engineering, 1976, SE-2(4): 308-320)是动态白盒测试技术中严谨而有效的方法,但存在测试用例设计效率较低的问题,影响了该方法在工程项目中的广泛应用。为了解决这一问题,从被测程序的基本结构出发,提出一种基于组合的基本路径测试用例设计方法。创建一种基于Z路径覆盖的基本单元图,构建由基本单元图组合形成控制流图的组合规则,以此为基础提出了基本路径组合算法,该算法只需一次扫描程序得到程序基本结构的路径集,将这些路径进行组合即可生成被测程序的基本路径集。该方法比McCabe所提出的方法构造过程简洁,能有效提高基本路径测试用例设计的效率。     

程序控制流图自动生成的算法

运用程序控制流图,可以方便地度量程序的逻辑复杂度,确定软件测试中控制结构独立路径的基本集合。文章提出了根据程序设计的伪码,自动生成程序控制流图的数据结构和详细的算法,为进行控制优化、软件基本路径测试以及程序控制相关性分析提供了良好的基础。     

Robustness testing of Java server applications

This paper presents a new compile-time analysis that enables a testing methodology for white-box coverage testing of error recovery code (i.e., exception handlers) of server applications written in Java, using compiler-directed fault injection. The analysis allows compiler-generated instrumentation to guide the fault injection and to record the recovery code exercised. (An injected fault is experienced as a Java exception.) The analysis 1) identifies the exception-flow "def-uses" to be tested in this manner, 2) determines the kind of fault to be requested at a program point, and 3) finds appropriate locations for code instrumentation. The analysis incorporates refinements that establish sufficient context sensitivity to ensure relatively precise def-use links and to eliminate some spurious def-uses due to demonstrably infeasible control flow. A runtime test harness calculates test coverage of these links using an exception def-catch metric. Experiments with the methodology demonstrate the utility of the increased precision in obtaining good test coverage on a set of moderately sized server benchmarks.     

距离与权重相结合的导向式灰盒模糊测试方法

导向式灰盒模糊测试是一种能够快速对程序指定位置进行测试的技术。通过对当前导向式灰盒模糊测试技术导向不够精确的问题进行分析,提出一种新的导向式灰盒模糊测试方法,并引入基本块权重与函数路径长度的概念。通过对被测程序的静态分析,构建被测程序的函数调用图和控制流程图,计算更准确的基本块距离并插桩到被测程序中。在模糊测试时通过插桩追踪并计算每个测试用例到指定目标的距离,模糊测试器依据该距离计算种子能量以实现对目标区域的导向,并基于该方法实现原型系统Afl-guide。实验结果表明,与现有的导向式模糊测试方法相比,该方法对目标区域导向更精确、路径覆盖更广,能够更快地生成覆盖程序指定位置的测试用例。     

带控制流的静态函数调用分析方法

提出一种带有控制流的静态函数调用分析的方法,通过建立模型,对源程序进行静态分析,得到程序中的控制流信息和函数调用信息。和已有的静态函数调用关系图分析工具calltree和Source Insight相比,该方法生成的函数调用流图不仅能展现函数间的调用次序,还可以了解程序设计的逻辑复杂度,有助于代码阅读和分析人员更快更好地理解程序结构以及设计流程,并为分析程序控制条件、设计路径覆盖测试用例和进行程序优化奠定基础。     

JP2: Call-site aware calling context profiling for the Java Virtual Machine

Calling context profiling fulfills programmers’ information needs to obtain a complete picture of a program’s inter- and intra-procedural control flow, which are important for workload characterization, debugging, profiling, program comprehension, and reverse engineering. Many existing calling context profilers for Java, however, resort to sampling or other incomplete instrumentation techniques; thus, they collect incomplete profiles only. In this article we present JP2, a new calling context profiler for the Java Virtual Machine, which collects profiles that are not only complete but also call-site aware; that is, JP2 is able to distinguish between multiple call sites within a single method. JP2 supports selective profiling of the dynamic extent of chosen methods and supports profiling of native method invocations. Moreover, produced profiles contain execution statistics at the level of individual basic blocks of code, thereby preserving the intra-procedural control flow of the profiled applications. We rigorously evaluate the overhead incurred by JP2. This overhead is acceptable in tasks such as workload characterization. JP2 is freely available under an Open Source license.     

Source Code Prioritization Using Forward Slicing for Exposing Critical Elements in a Program

Even after thorough testing,a few bugs still remain in a program with moderate complexity.These residual bugs are randomly distributed throughout the code.We have noticed that bugs in some parts of a program cause frequent and severe failures compared to those in other parts.Then,it is necessary to take a decision about what to test more and what to test less within the testing budget.It is possible to prioritize the methods and classes of an object-oriented program according to their potential to cause failures.For this,we propose a program metric called influence metric to find the influence of a program element on the source code.First,we represent the source code into an intermediate graph called extended system dependence graph.Then,forward slicing is applied on a node of the graph to get the influence of that node.The influence metric for a method m in a program shows the number of statements of the program which directly or indirectly use the result produced by method m.We compute the influence metric for a class c based on the influence metric of all its methods.As influence metric is computed statically,it does not show the expected behavior of a class at run time.It is already known that faults in highly executed parts tend to more failures.Therefore,we have considered operational profile to find the average execution time of a class in a system.Then,classes are prioritized in the source code based on influence metric and average execution time.The priority of an element indicates the potential of the element to cause failures.Once all program elements have been prioritized,the testing effort can be apportioned so that the elements causing frequent failures will be tested thoroughly.We have conducted experiments for two well-known case studies - Library Management System and Trading Automation System - and successfully identified critical elements in the source code of each case study.We have also conducted experiments to compare our scheme with a related scheme.The experimental studies justify that our approach is more accurate than the existing ones in exposing critical elements at the implementation level.     

基于符号约束的PLC程序正确性验证

符号约束描述了程序中的变量关系,被广泛运用于模型检测、符号执行等程序的静态分析方法中。将符号约束应用于可编程逻辑控制器(PLC)程序的正确性验证,能够发现程序中的逻辑错误。人工计算符号约束不仅冗杂枯燥,而且错误率高。针对语句表形式的PLC程序,提出一种基于符号约束的正确性验证方法,通过分析PLC源代码的控制流及数据流,构造程序的控制流图并将其转换为静态单赋值形式的三地址码,最后使用迭代计算的方法求出每个变量的符号约束。