论文部分内容阅读
摘 要：程序插桩技术是一种基本的测试手段，在软件测试中被广泛的应用。插装方式是指在程序源码中插入一些语句，通过这些语句可以获得所需要的信息，在死锁规避的静态分析中需要通过程序插装的方式记录下一些信息。程序插装按照源程序的结构分为顺序结构的插装，分支结构的插装和循环结构的插装。在对源程序进行词法语法分析的基础上建立抽象语法树和控制流图，根据控制流图获取程序可能执行的所有路径信息，接着根据路径信息决定插装的内容。
关键词：词法分析；语法分析；抽象语法树；程序插装
中图分类号：TP311 文献标识号：A
Deadlock Avoidance Oriented Path Sensitive Instrumentation
QI Peng， YU Zhen， SU Xiaohong， MA Peijun
（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）
Abstract：The instrumentation of the program is a basic test method， which is widely used in software testing. In instrumentation method is to insert some of the statements in the program source code， the required information is available through these statements， in static analysis of the deadlock avoidance through program instrumentation some information needs to be recorded. Procedures for the insertion into the structure of the source code structure is divided into the order of the structure of the insert， the branch structure of the insert and the structure of the loop. In this paper， on the basis of the lexical and syntax analysis of the source program to establish abstract syntax tree and control flow graph， according to the control flow graph to obtain the program may perform all path information， then according to the route information to decide the inserted content.
Keywords：Lexical Analysis； Syntax Analysis； Abstract Syntax Tree； Program Instrumentation
0 引 言
程序插桩（Program Instrumentation）技术是一种基本的测试手段，由J.G.Huang教授首次提出，并已在软件测试中获得了广泛的应用。其目的是在保障源程序的逻辑和功能不被破坏的情况下，向源程序插入一些语句，这些语句可以记录或者输出一些需要关注的信息，进一步通过这些信息了解执行过程中程序的一些动态特性。
Clang是一个支持 C，C ，Object-c及Object-c 等语言的编译器前端。在本文中即使用了Clang对源码经过词法语法分析，生成语法树，并在此基础上建立控制流图，方便之后的获取执行路径。使用Clang进行词法语法分析主要是由于Clang本身性能的优异，其生成语法树所消耗的内存仅仅是GCC的20%左右，同时编译时间快，错误输出明确，并且Clang支持在语法树的基础上建立控制流图，自动查找头文件，解析C语言在Linux下的头文件的功能。
在基于未来锁集的死锁规避算法[1]中程序插装的是记录锁集信息的关键步骤[2]，这也是基于未来锁集死锁规避算法与其它死锁规避算法[3-5]最大的不同，通常情况下程序插装的目的是获取程序的执行路径，或者关键的状态值等。虽然基于未来锁集的死锁规避算法也需要获取程序的执行路径，但却通过静态的分析方法获得程序可能的执行路径，而不是等到程序运行时获取真实的执行路径。所以本算法插装的目的是为了记录下相关的加锁操作的信息。只有获得了这些信息，才能根据这些信息添加规避逻辑[6]。
1 路径敏感分析
在基于未来锁集的死锁规避算法中程序的插装内容是根据程序的实际执行路径来确定的，然而在静态分析时却仍无法确定程序真实的执行路径，因此就需要找出程序所有的可能执行路径，并区分具体情况进行插装，这一过程就是路径敏感分析。
下面使用块号代表节点，将控制流图这个有向图转化成矩阵的存储形式Arcs[N][N]，N是所有节点的个数。在算法开始之前，需要首先引入一些变量定义：
（1）节点栈mystack。
（2）VertexStatus[]={0，0，0，1，1，…}当结点未进栈或者已经出栈，则其对应的状态为0，否则为1。
（3）ArcStatus[][]={0，0，1，0，1…..} 当且仅当边的两个结点都在栈外时，边的状态才为0，否则为1。 对以上变量实现其定义后，算法1给出了路径敏感分析算法的具体描述。
算法1：路径敏感分析算法
输入：控制流图的矩阵存储形式Arcs[N][N]
输出：控制流图中基本块N到基本块0的所有路径集合Paths
1 Paths={}//路径集合
2 VertexStatus[]={0}；//全部置0
3 ArcStatus[][]={0}；//全部置0
4 mystack.push（0）；// 节点栈
5 VertexStatus[N]=1；//将第N块入栈
6 while ！mystack.empty（）
7 elem= mystack.top（）；//获得栈顶元素
8 if elem==0
9 path=Traverse（mystack）；//遍历栈将栈中信息组成路径
10 Paths.add（path）；//将栈中的路径添加到路径集合Paths中
11 VertexStatus[elem]=0；
12 UpdateArcStatus（）；//更新ArcStatus[][]
13 mystack.pop（）；//移除栈顶元素
14 else
15 i=N
16 T1= VertexStatus[i]==0；//第i块不在栈中
17 T2= ArcStatus[elem][i]==0；//边（elem，i）不在栈中
18 T3= Arcs.contain（elem，i）；//控制流图中存在（elem，i）边
19 if 如果存在一个最大的数i使i在0～N，并且使
20 T1
关键词：词法分析；语法分析；抽象语法树；程序插装
中图分类号：TP311 文献标识号：A
Deadlock Avoidance Oriented Path Sensitive Instrumentation
QI Peng， YU Zhen， SU Xiaohong， MA Peijun
（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）
Abstract：The instrumentation of the program is a basic test method， which is widely used in software testing. In instrumentation method is to insert some of the statements in the program source code， the required information is available through these statements， in static analysis of the deadlock avoidance through program instrumentation some information needs to be recorded. Procedures for the insertion into the structure of the source code structure is divided into the order of the structure of the insert， the branch structure of the insert and the structure of the loop. In this paper， on the basis of the lexical and syntax analysis of the source program to establish abstract syntax tree and control flow graph， according to the control flow graph to obtain the program may perform all path information， then according to the route information to decide the inserted content.
Keywords：Lexical Analysis； Syntax Analysis； Abstract Syntax Tree； Program Instrumentation
0 引 言
程序插桩（Program Instrumentation）技术是一种基本的测试手段，由J.G.Huang教授首次提出，并已在软件测试中获得了广泛的应用。其目的是在保障源程序的逻辑和功能不被破坏的情况下，向源程序插入一些语句，这些语句可以记录或者输出一些需要关注的信息，进一步通过这些信息了解执行过程中程序的一些动态特性。
Clang是一个支持 C，C ，Object-c及Object-c 等语言的编译器前端。在本文中即使用了Clang对源码经过词法语法分析，生成语法树，并在此基础上建立控制流图，方便之后的获取执行路径。使用Clang进行词法语法分析主要是由于Clang本身性能的优异，其生成语法树所消耗的内存仅仅是GCC的20%左右，同时编译时间快，错误输出明确，并且Clang支持在语法树的基础上建立控制流图，自动查找头文件，解析C语言在Linux下的头文件的功能。
在基于未来锁集的死锁规避算法[1]中程序插装的是记录锁集信息的关键步骤[2]，这也是基于未来锁集死锁规避算法与其它死锁规避算法[3-5]最大的不同，通常情况下程序插装的目的是获取程序的执行路径，或者关键的状态值等。虽然基于未来锁集的死锁规避算法也需要获取程序的执行路径，但却通过静态的分析方法获得程序可能的执行路径，而不是等到程序运行时获取真实的执行路径。所以本算法插装的目的是为了记录下相关的加锁操作的信息。只有获得了这些信息，才能根据这些信息添加规避逻辑[6]。
1 路径敏感分析
在基于未来锁集的死锁规避算法中程序的插装内容是根据程序的实际执行路径来确定的，然而在静态分析时却仍无法确定程序真实的执行路径，因此就需要找出程序所有的可能执行路径，并区分具体情况进行插装，这一过程就是路径敏感分析。
下面使用块号代表节点，将控制流图这个有向图转化成矩阵的存储形式Arcs[N][N]，N是所有节点的个数。在算法开始之前，需要首先引入一些变量定义：
（1）节点栈mystack。
（2）VertexStatus[]={0，0，0，1，1，…}当结点未进栈或者已经出栈，则其对应的状态为0，否则为1。
（3）ArcStatus[][]={0，0，1，0，1…..} 当且仅当边的两个结点都在栈外时，边的状态才为0，否则为1。 对以上变量实现其定义后，算法1给出了路径敏感分析算法的具体描述。
算法1：路径敏感分析算法
输入：控制流图的矩阵存储形式Arcs[N][N]
输出：控制流图中基本块N到基本块0的所有路径集合Paths
1 Paths={}//路径集合
2 VertexStatus[]={0}；//全部置0
3 ArcStatus[][]={0}；//全部置0
4 mystack.push（0）；// 节点栈
5 VertexStatus[N]=1；//将第N块入栈
6 while ！mystack.empty（）
7 elem= mystack.top（）；//获得栈顶元素
8 if elem==0
9 path=Traverse（mystack）；//遍历栈将栈中信息组成路径
10 Paths.add（path）；//将栈中的路径添加到路径集合Paths中
11 VertexStatus[elem]=0；
12 UpdateArcStatus（）；//更新ArcStatus[][]
13 mystack.pop（）；//移除栈顶元素
14 else
15 i=N
16 T1= VertexStatus[i]==0；//第i块不在栈中
17 T2= ArcStatus[elem][i]==0；//边（elem，i）不在栈中
18 T3= Arcs.contain（elem，i）；//控制流图中存在（elem，i）边
19 if 如果存在一个最大的数i使i在0～N，并且使
20 T1