全路径剖析方法

路径剖析是动态分析的一项重要技术,通过获取和分析程序中各条路径的执行次数,在编译优化、软件调试和测试等诸多方面发挥重要作用.针对现有技术剖析能力不足的情况(即只能或者剖析非循环路径,或者首先界定循环体执行次数的上限、然后对于执行循环体不多于该次数的路径进行剖析),对使用单个探针变量剖析过程内路径的方法进行了改进,提出了全路径剖析PAP方法,利用探针插装和回溯过程获取路径的执行次数,可以剖析过程内包含任意有限长度的路径;进一步地,针对PAP方法所需探针数目多于EPP方法的问题,通过对控制流图中包含的可规约无环子图实施EPP方法,可以减少PAP方法所需探针的数目.另外,作为PAP方法的一个典型应用,还讨论了如何通过在方法调用图中添加返回边,再利用PAP方法获取方法层次的执行序列的基本思想,满足了某些方法级动态影响分析技术的需要.实验和实例分析表明,PAP在处理循环路径剖析的问题上是有效的,并有很好的效率.

Profiling All Paths

Path profiling,an important technique in dynamic program analysis,which collects the execution times of different paths,has been widely used in a variety of areas.However,existing intra-procedural profiling techniques have inadequate abilities in loops,i.e.,they can only either solve profiling acyclic paths,or limit loop iterations to a certain number first,and then profile paths under such a limitation.This paper presents a new profiling technique called PAP(profiling all paths),which can profile finite-length paths inside a procedural.PAP consists of two basic phases: one is the probe instrumentation which assigns a unique pathid for each path,and the other is backwalk which uses the pathids to determine the corresponding executed paths.Furthermore,breakpoints are introduced to store the probe value which may overflow during long executions,and the probe amount is reduced base on the integration of PAP with an existing profiling technique.Besides,this paper also discusses how to use PAP to profile executed sequences on the method level.As shown in the results of the case study and experiments,PAP is effective and efficient in profiling cyclic paths.