基于程序执行轨迹的动态切片系统

摘要

本发明涉及一种基于程序执行轨迹的动态切片系统，包括系统获得程序的执行路径信息、对Java的.class文件进行静态分析、对程序执行轨迹中每个序列的每条语句的附加变量集进行分析、对源程序中每条语句直接控制依赖结点的获取、对程序执行轨迹中每个序列的每条语句进行附加控制依赖工作及完成对Java过程内程序进行动态切片的功能。在程序切片的过程中不需要对程序进行回溯，大大提高了算法的效率，根据控制依赖关系和变量的定义引用信息提高了切片的精度。

主权项

基于程序执行轨迹的动态切片方法，其特征是：包括如下步骤：（1）调试器获得程序的执行路径信息，即Path Analysis，获取当前执行语句的信息；针对当前执行语句的信息，对这些信息进行数据依赖分析，即DefVars or UseVars Analysis，得到当前执行语句的定义变量集DefVars和使用变量集UseVars；（2）对Java的.class文件进行静态分析，实现了对Java源文件中每条语句中定义变量集DefVars和使用变量集UseVars的获取功能；对Java的.class文件进行静态分析包括如下子步骤：（2a）首先，初始化Soot，完成Soot的初始设置工作；（2b）完成Soot初始化工作后，接着需要做的便是获取需要分析的类和方法；（2c）通过方法体SootBody，数据依赖分析DefVars or UseVars Analysis模块可以获得该方法中任一语句，用三地址格式的中间表示语句Jimple表示的Soot实例；（2d）在处理获得定义变量集DefVars和使用变量集UseVars时，还需要将在Jimple中间表示中产生的不属于Java源代码的临时变量去除掉；（3）对程序执行轨迹中每个序列的每条语句的附加变量集进行分析，该附加变量集包括DefVars和UseVars；变量类型分析Variable Types Analysis模块对Path Analysis和DefVars or UseVars Analysis两个模块的结果进行解析，分别获取必须的信息，并将这些信息按结构有规律、有顺序的组合在一起，形成可供中间分析的结果；对程序执行轨迹中每个序列的每条语句的附加变量集进行分析包括如下子步骤：（3a）变量类型分析Variable Types Analysis模块实现对程序执行轨迹中每个序列的每条语句的附加变量集进行DefVars和UseVars处理工作；（3b）Variable Types Analysis模块将Path Analysis和DefVars or UseVars Analysis两个模块的结果文件读入到内存中，分别保存在DocDA和DocSA中，同时在内存中生成自己的结构DocVTA；（4）控制依赖分析Control Dependence Analysis模块是基于Soot开发的一个模块，它对java的.class文件进行静态分析，实现了对源程序中每条语句直接控制依赖结点的获取功能；控制依赖分析包括如下步骤：（4a）控制依赖分析Control Dependence Analysis模块首先获取待分析的类，生成待分析类的Soot实例SootClass，再从中获取待分析的方法，即类中的main方法，生成待分析方法的Soot实例SootMethod，并为SootMethod建立方法体SootBody，通过Soot提供的BriefUnitGraph类为方法建立控制流图CFG；（4b）在完成CFG流图的建立后，接下来需要做的就是寻找控制流图中各个结点的控制依赖关系；（5）对程序执行轨迹中每个序列的每条语句进行附加控制依赖工作；中间分析Intermediate Analysis模块对变量类型分析Variables Type Analysis和控制依赖分析Control Dependence Analysis两个模块的结果进行解析，分别获取必须的信息，并将这些信息按结构有规律、有顺序的组合在一起，形成可供切片的最终中间结果；对程序执行轨迹中每个序列的每条语句进行附加控制依赖工作包括如下步骤：（5a）首先计算程序执行序列，获得本次执行序号ExecutionNum，将ExecutionNum记录到DocInterA中；（5b）通过类名ClassName和行号LineNum信息，中间分析Intermediate Analysis模块在DocVTA和DocCDA中分别查找到相应元素的信息；（6）系统完成对Java过程内程序进行动态切片的功能；切片slice模块对中间分析Intermediate Analysis的结果进行解析，获取切片必要的信息；对Intermediate Analysis的结果进行解析包括如下步骤：（6a）首先，获取中间分析结果Intermediate Analysis Results的一次执行的信息，这些信息保存在一个执行序号ExecutionNum元素中，从信息中模块可以获得行号信息LineNum，此时模块就可以对序号为ExecutionNum行号为LineNum的语句结点做节点切片NodeSlice；（6b）将语句行号加入到NodeSlice中；（6c）NodeSlice完成后，需要修改或添加结点中所有定义变量的切片。