一种面向有环兴趣路径的过程内剖析方法

路径剖析技术用于获取和分析程序中各条路径的执行次数.路径剖析采用在待剖析程序中插装探针的方式以跟踪执行,并使用对路径进行编码的方式以高效地获取剖析结果.选择性剖析是针对用户感兴趣的一部分路径,在非选择性剖析技术的基础上进行优化,以尽可能低的耗费来完成剖析.现有的选择性剖析技术采用的优化措施局限于减少探针数目和压缩路径编码空间,而且其允许的用户兴趣路径局限于无环路径.文中提出了一种新的选择性剖析方法 PSP(Profiling Selected Paths),可以精确的剖析带有循环的兴趣路径,并使用了在执行过程中对非兴趣路径进行检测和提前终止的技术来降低耗费.理论分析和实验评估表明PSP方法能够精确地剖析兴趣路径,并使用兴趣路径来提升剖析效率.     

回归测试中路径覆盖生成方法研究及其应用

基于边覆盖的路径覆盖估测法可获取用于回归测试用例选择的数据信息,但存在估测精确率不高、对重叠路径的识别能力差以及循环结构对可执行路径数目的影响等缺陷.针对这些缺陷,提出一种新的路径覆盖生成方法来获取程序执行的路径信息,该方法包括CFG图到DAG图的转换和还原、利用DFS深度优先策略构造DAG图的chord生成树等,然后设计了基于该方法的测试数据集生成方法.最后,对该方法进行实验验证和数据分析,证明了该方法的有效性.     

基于改进的Z路径覆盖策略的路径生成算法

针对汇编语言程序非结构化的特点,提出了基于改进的Z路径覆盖策略的汇编语言程序结构测试方法和路径自动生成算法。该算法采用正则表达式来表示程序控制流结构,从控制流分段．正则表达式生成、路径片段生成和路径片段连接4个步骤完成了路径生成的过程,提出了矩阵递归算法MRA以解决路径片段连接问题。该算法能够生成覆盖在循环处执行循环体的0次、1次和2次循环的路径集,该路径集覆盖语句覆盖、判定覆盖和循环覆盖准则的同时,其路径数量又可以接受。     

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

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

基于循环的指令高速缓存访问预测方法

为了减少高速缓存访问功耗,提出了一种针对循环的基于历史访问路径的指令高速缓存访问预测方法。该方法以循环作为高速缓存访问路预测行为开启的先决条件,通过指令高速缓存的历史访问路径训练预测器。当循环体再次进入时选择对应的访问路径预测器,获取目标指令高速缓存的路进行访问,降低访问功耗。并进一步提出多路径路预测方法,以得到更高的预测准确率。基于Powerstone测试基准的实验结果表明,该预测方法能达到99%的预测准确率。相比传统的指令高速缓存,使用本方法的高速缓存可平均降低65%的访问功耗,仅增加约0.2%的平均指令高速缓存访问周期。     

Java自动化基本路径测试研究

针对Java单元测试自动化程度和测试效率较低的问题,对基于Java程序的基本路径测试方法进行研究,提出了基于Java代码的基本路径生成方法和程序插桩方法,给出了插桩节点和控制流图节点的定义。首先,通过对Java源代码进行分析,构建程序的控制流图,进而对控制流图进行遍历生成基本路径集合;然后,对被测程序进行插桩,以获取程序的执行路径,插桩过程中保持节点和基本路径中的节点一致,使得插桩后的被测程序执行时得到的路径能够和基本路径集合进行自动化比对;最后,通过以测试数据为输入执行被测程序,对执行路径和基本路径进行比较,判断测试数据集对基本路径的覆盖度。通过实验,验证了所提出方法的有效性。     

谓词抽象技术中循环反例的解决方法研究

为了解决谓词抽象技术面临的程序中循环体的每次迭代都至少需要一个谓词来实现的难题,提出了一个两阶段的不完全判定过程,用来对一个包含循环的反例进行可行性模拟.通过给出的循环探测算法来从抽象模型中提取出包含循环的反例,并用循环迭代的数量作为参数来确定模拟实例.实验结果表明,该方法在典型的缓冲溢出实例中的表现优于传统的抽象求精方法.     

基于改进RRT*的移动机器人路径规划算法

RRT~*算法在路径规划过程中确保了其概率完备性和渐进最优性,但仍存在收敛速度慢且产生大而密集的采样空间等问题。为此,在RRT~*的基础上提出一种新的离线路径规划算法。在开始采样前快速瞄准目标区域,生成包含起始点与目标点的有界连通性区域。采用人工势场法优化采样过程,减少计算量,在势场合力的作用下有界区域内执行目标偏差采样,调整采样区域,在较短时间内生成较优路径。实验结果表明,当生成的路径成本相同时,该算法所需的迭代次数和执行时间远小于RRT~*算法,算法效率更高。     

一种对象代理数据库的跨类查询优化方法

对象代理数据库中跨类查询可以充分发挥对象代理模型的灵活性,为用户提供个性化数据服务,其执行效率十分重要。然而在处理多个跨类属性查询时,现有基于路径表达式的跨类查询实现存在对公共路径节点对象进行重复获取的情形,执行效率较低。针对跨类查询中加快获取终点对象的问题,优化核心思想是减少对路径上节点对象的重复与不必要的遍历,包括两个关键策略:首先是将路径节点整体作为虚拟路径视图统一获取节点对象,避免了多跨类属性查询下公共路径节点的冗余遍历;其次是针对路径复杂过长的跨类查询,依据代价估计策略选择物化查询涉及起点与终点对象,利用缓存减少执行时路径上中间节点的遍历。分别在属性数目与结果集规模两方面进行了对比实验,实验结果表明了优化方法的有效性。     

面向C程序插装的路径提取

路径测试法是软件测试的一种基本方法。将C程序按照控制结构进行分类,结合路径测试特点进行插装,在设置探针的同时提取函数静态信息,算法采用先获取局部路径,再进一步获取全局路径的方法。实验结果表明,基于插装的路径获取技术,具有较高的准确率和效率,尤其适用于基于函数的路径提取。     

Profiling selected paths with loops

Path profiling records the frequency of each path in an executed program.To accomplish profiling,probes are instrumented in the program and executed as the program runs.So,the number of probes has a significant impact on the efficiency of a profiling technique.By profiling only the interesting paths,existing techniques try to improve the profiling efficiency by reducing the number of probes and optimize path encodings for efficient storage.However,they lack accuracy,waste time on running uninteresting paths,and can mainly deal with acyclic paths.In this article,a novel technique called Profiling Selected Paths(PSP)is introduced to profile selected paths,which enables custom selection for both acyclic and cyclic paths and increases the execution efficiency by early termination on uninteresting paths.Theoretical analysis and experimental evaluation indicate that PSP performs better than existing techniques.     

Branch elimination by condition merging

Conditional branches are expensive. Branches require a significant percentage of execution cycles since they occur frequently and cause pipeline flushes when mispredicted. In addition, branches result in forks in the control flow, which can prevent other code‐improving transformations from being applied. In this paper we describe profile‐based techniques for replacing the execution of a set of two or more branches with a single branch on a conventional scalar processor. These sets of branches can include tests of multiple variables. For instance, the test if (p1 != 0 && p2 != 0) , which is testing for NULL pointers, can be replaced with if (p1 & p2 != 0) . Program profiling is performed to target condition merging along frequently executed paths. The results show that eliminating branches by merging conditions can significantly reduce the number of conditional branches executed in non‐numerical applications. Copyright © 2004 John Wiley & Sons, Ltd.     

动态二进制翻译中热路径优化的软件实现

在动态二进制翻译中，热路径的识别和生成是提高二进制翻译器效率的重要环节。为了提高热路径预测的命中率，必须在程序的运行中搜集较为详细的信息，这必然增加系统的开销。因此，在准确率和开销之间做出权衡十分必要。该文在研究现有热路径算法的基础上，提出了一种改进的基于路径的热路径识别和优化算法，并对结果进行了分析。     

一种基于文件传输路径的分布式程序实时性评估方法

首先根据分布式系统实时性评估的基本思想，结合分布式程序执行的特点，对分布式程序的实时性评估进行理论分析．然后．根据分布式程序在系统中所处的位置、程序执行时所需的数据文件和数据文件的传输路径，确定每个数据文件的最小传输时间和最大传输时间．在此基础上，计算出程序的最早响应时间和最迟响应时间，从而形成一种基于文件传输路径的分布式程序实时性评估方法、通过实例评估和模拟分析，说明了这种评估方法是有效性的．     

汇编代码中的热路径搜寻工具

介绍并实现了一种热路径搜索算法,它能在汇编代码中搜寻出执行频率最高的若干条路径。编译器开发人员可以专注精力分析热路径上的代码,大大节省了工作量。该工具配合ORC编译器的开发,为改善性能做出了重要贡献。     

Automatic generation of basis test paths using variable length genetic algorithm

Path testing is the strongest coverage criterion in white box testing. Finding target paths is a key challenge in path testing. Genetic algorithms have been successfully used in many software testing activities such as generating test data, selecting test cases and test cases prioritization. In this paper, we introduce a new genetic algorithm for generating test paths. In this algorithm the length of the chromosome varies from iteration to another according to the change in the length of the path. Based on the proposed algorithm, we present a new technique for automatically generating a set of basis test paths which can be used as testing paths in any path testing method. The proposed technique uses a method to verify the independency of the generated paths to be included in the basis set of paths. In addition, this technique employs a method for checking the feasibility of the generated paths. We introduce new definitions for the key concepts of genetic algorithm such as chromosome representation, crossover, mutation, and fitness function to be compatible with path generation. In addition, we present a case study to show the efficiency of our technique. We conducted a set of experiments to evaluate the effectiveness of the proposed path generation technique. The results showed that the proposed technique causes substantial reduction in path generation effort, and that the proposed GA algorithm is effective in test path generation.     

Dynamic branch speculation in a speculative parallelization architecture for computer clusters

This article describes a technique for path unfolding for conditional branches in parallel programs executed on clusters. Unfolding paths following control structures makes it possible to break the control dependencies existing in the code and consequently to obtain a high degree of parallelism through the use of idle CPUs. The main challenge of this technique is to deal with sequences of control statements. When a control statement appears in a path after a branch, a new conditional block needs to be opened, creating a new code split before the previous one is resolved. Such subsequent code splits increase the cost of speculation management, resulting in reduced profits. Several decision techniques have been developed for improving code splitting and speculation efficiency in single machine architecture. The main contribution of this paper is to apply such techniques to a cluster of single processor systems and evaluate them in such an environment. Our results demonstrate that code splitting in conjunction with branch speculation and the use of statistical information improves the performance measured by the number of processes executed in a time unit. This improvement is particularly significant when the parallelized programs contain iterative structures in which conditions are repeatedly executed. Copyright © 2012 John Wiley & Sons, Ltd.     

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

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

Data Generation for Path Testing

We present two stochastic search algorithms for generating test cases that execute specified paths in a program. The two algorithms are: a simulated annealing algorithm (SA), and a genetic algorithm (GA). These algorithms are based on an optimization formulation of the path testing problem which include both integer- and real-value test cases. We empirically compare the SA and GA algorithms with each other and with a hill-climbing algorithm, Korel's algorithm (KA), for integer-value-input subject programs and compare SA and GA with each other on real-value subject programs. Our empirical work uses several subject programs with a number of paths. The results show that: (a) SA and GA are superior to KA in the number of executed paths, (b) SA tends to perform slightly better than GA in terms of the number of executed paths, and (c) GA is faster than SA; however, KA, when it succeeds in finding the solution, is the fastest.     

基于分支覆盖的回归测试路径选择

回归测试是迭代式软件开发的重要环节,测试数据生成是回归测试的前提.传统的回归测试方法,从已有的测试数据中选择部分测试数据,并生成一些新的测试数据,以验证程序的正确性.但是,该方法容易生成冗余的测试数据,从而降低了回归测试的效率.研究了回归测试的分支覆盖问题,通过利用已有测试数据的路径覆盖信息,并选择一定个数的路径,以覆盖所有的目标分支.首先,以若干路径形成的集合作为决策变量,以路径最少、覆盖的分支最多以及包含的未覆盖路径最少为目标,建立路径选择问题的3目标优化模型;然后,采用遗传算法求解上述模型时,设计了基于目标重要性的个体评价策略;最后,基于已有的测试数据与选择的路径之间的覆盖关系,确定需要生成的测试数据.将所提方法应用于6个基准工业程序测试中,并与其他方法比较.实验结果表明,采用该方法选择的路径,能够覆盖更多的分支,需要生成的测试数据更少,回归测试消耗的时间更短.