时间：2022-08-18 08:28:02
摘 要：程序插桩技术是一种基本的测试手段，在软件测试中被广泛的应用。插装方式是指在程序源码中插入一些语句，通过这些语句可以获得所需要的信息，在死锁规避的静态分析中需要通过程序插装的方式记录下一些信息。程序插装按照源程序的结构分为顺序结构的插装，分支结构的插装和循环结构的插装。在对源程序进行词法语法分析的基础上建立抽象语法树和控制流图，根据控制流图获取程序可能执行的所有路径信息，接着根据路径信息决定插装的内容。
关键词：词法分析；语法分析；抽象语法树；程序插装
中图分类号：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&&T2&&T3成立
21 VertexStatus[i]=1；//标记i块状态为入栈
22 VrcStatus[elem][i]=1；//标记（elem，i）边为入栈状态
23 mystack.push（i）；//将i点入栈
24 else
25 VertexStatus[elem]=0；//标记elem块状态为入栈
26 mystack.pop（）；//将栈顶元素出栈
27 UpdateArcStatus（）；//更新ArcStatus[][]
28 endif
29 endif
30 endwhile
31 return Paths；
算法1中，变量的初始化表示将起始块号N放入栈中，更新点的状态集合，并且开始算法，整个算法是在一个大的循环中；并且只要栈不为空，程序则继续循环。进入循环体之后首先判断栈顶元素是否为0，也就是最后一块Exit：如果是的话说明栈中的所有块是一条符合要求的完整路径，接下来需记录下这个路径并且更新边的状态集合，最后将栈顶元素出栈；如果不是，说明栈内的元素还不是一条符合要求的路径，即需要继续改变栈中元素。改变栈中元素就是判定从栈顶元素开始到Exit块是否还有新的路径产生，为此定义了一个判断条件T1&&T2&&T3，同时结合点的状态集合，边的状态集合和原始的有向图，进而判断：如果在控制流图中还存在点使T1&&T2&&T3条件满足的话，这就说明从栈顶元素到最后有新的路径，随即将更新点状态集合和边状态集合，并且将栈顶元素的后继入栈；否则也就说明从栈顶元素到最后已经没有新的路径，如此将更新点的状态集合，将栈顶元素出栈，更新边的状态集合。同时在路径敏感分析算法完整执行后，Paths中保存的就是两点之间的所有路径。
2 面向不同结构源程序的插装方法
2.1 顺序结构插装
程序插装是静态分析的最后一步，未来锁集就是根据静态分析时插装的信息计算而得来的。插装的方式对于程序的不同结构有不同的方法。在这里插装的内容为加锁解锁信息。具体插入的语句为入栈语句，入栈元素包含锁的名称和该锁是否执行加锁。例如“Push（ps，Mutex1，1，mutex）”，表示向栈ps中加入一个锁的信息，这个信息指明为锁Mutex1实施加锁，其中最后一个mutex参数表示Mutex1是一个互斥锁，主要是为了区别读写锁而设立的。算法2给出顺序结构插装的算法描述。
算法2：对源码为顺序结构的程序插装的算法
输入：顺序结构的源码对应的控制流图
输出：插装之后的源码对应的控制流图
1 对输入的源码建立控制流图G
2 for G中的每条语句s
3 if s为加锁操作
4 while 以s为起点遍历控制流图中的每条语句t
5 if t不是对应s的解锁操作并且为加锁解锁语句
6 记录加锁语句t中的信息
7 endif
8 endwhile
9 endif
10 将所记录的所有锁信息插装到s之前，更新G
11 if s为自定义函数调用
12 while 以语句s为起点遍历G的每条语句t直到控制流图结束
13 记录下所有加锁解锁操作
14 endwhile
15 endif
16 将记录的锁信息插装到s之前， 更新G
17 在s之后插装相应的出栈语句，更新G
18 endif
19 endfor
20 return G；
2.2 分支结构的插装
基于未来锁集的死锁规避算法中主要包含着一个“提前“的思想，当算法执行到加锁操作时，如果能知道加锁操作之后执行的其他加锁解锁操作的话，就可以根据这些信息判断所遇到的加锁操作是不是可以执行。本文研究的插装就是将加锁之后执行的锁信息提前。但是这里存在一个问题，在路径分析时可能获得的是两点之间的所有路径，而在实际执行的过程中执行路径却只有一条。也就是说，在程序运行之前终将无法确定程序运行时的真实执行路径。图1所示为采用将分支条件提前的方法插装带有分支结构的源码。
图1 采用将分支条件提前的方法插装带有分支结构的源码
Fig.1 Instrumentate source code with branch structure using the method that put the branch condition in front
图1展示了两个简化后的控制流图，其中省略了Entry和Exit块。图中箭头右边的控制流图采用了将分支条件提前的方法，插装带有分支结构的程序。源程序为一个分支结构，分支条件为T，需要插装的语句为S1，S2，S3，且都是加锁语句。具体地，S2，S3只有一条路径可以执行，其插装代码分别为In3、In4和In5，In6及In7。而对于S1来说，则有两条路径可以执行；此时为了确定执行路径，即将分支条件提前，所以插装的语句为条件语句In1和In2。
针对将分支条件提前这一方法，虽然可以精准确定程序执行的路径，但是符合这种方法的条件却过于苛刻。如果遇到分支条件不能提前的情况，这种方法将不能使用，比如用户输入，或者分支条件中的变量定义在加锁操作之后等情况。如图2所示，为使图2中的B3块发生变化，分支条件中的变量定义改动在加锁条件之后，只是如此插装之后就会出现语法错误。图3则为分支条件中的变量需要用户输入导致不能将分支条件提前。
图2分支条件中的变量定义在加锁操作之后导致插装错误
Fig.2 The variable in the branch condition that define after the lock operation lead to the error of instrumentation
图3 分支条件中的变量需要用户输入导致插装错误
Fig.3 The variable in the branch condition that require user input lead to the error of instrumentation
在图3中，由于分支条件中的变量a，b是在加锁操作S1之后定义的，当插装完成后，插装语句中的变量a，b就成为未定义的变量，因而这段代码将无法顺利通过编译。在图4中真正确定分支条件的变量是需要用户输入，而用户输入的语句却是在加锁操作S1之后，这就使得虽然插装后的代码可以运行，但却不能有效确定执行路径。
在插装时，为了有效确定程序的执行路径而采用将分支条件提前的方法虽然可以准确找到执行路径，但其适用范围并不大，而且也无法判断程序的分支条件是否可以提前，综上所述即使插装代码中产生了诸多错误。在此，提出另一种方法将会遍历所有可能的执行路径，按照算法3的插装方法就可将所有应该插装的锁信息入栈，并将重复的去掉。如下的算法3就是这种分支结构插装方法的算法描述。
算法3：对源码为分支结构的程序插装的算法
输入：分支结构的源码对应的控制流图
输出：插装之后的源码对应的控制流图
1 对输入的源码建立控制流图G
2 for G中的每条语句s
3 if s为加锁操作or自定义函数调用操作
4 以s所在的基本块为起点Exit块为终点进行路径敏感分析
5 获得路径集合Paths
6 for 遍历Paths中的每条路径path
7 将path中的块连接起来当作顺序结构的源码
8 使用算法2是对s进行插装，更新G
9 endfor
10 将s前插装的语句做去重处理
11 endif
12 endfor
13 return G；
这种方法虽然损失掉一些程序执行效率，但却适用于所有情况，并且不会向源码中引入错误。图4就列举了一个分支结构的源码对应的控制流图，并且给出使用算法3插装之后的控制流图。
图4 遍历所有可能路径的插装方法
Fig.4 Instrumentation method of traversing all the possible paths
如图4所示，对于S1的插装是分别遍历了左分支和右分支之后将所有插装信息插入，再去掉重复的，所以在栈中会同时出现加锁mutex2和加锁mutex3。
2.3 循环结构的插桩
前文已经介绍了对于顺序结构和分支结构的插装方式，并且在路径分析时将所有的循环结构都转化成了分支结构，那么如果在循环体中出现了自定义函数调用或者加锁操作的话，相应地也可将循环结构转化成循环体只可能执行一遍的分支结构。
在实际的编程过程中，如果循环体中存在单独的加锁操作而没有对应的解锁操作的话，一旦循环体重复执行，就极有可能发生自锁的情况。这样的编程方式是不符合规范的。但是在循环体中只要加锁操作和解锁操作能够呈现对应设计，那么插装之后，即使循环体重复执行，插装的内容也会是一样的，算法4给出循环结构的插装算法描述。
算法4：对源码为循环结构的程序插装的算法
输入：循环结构的源码对应的控制流图
输出：插装之后的源码对应的控制流图
1 对输入的源码建立控制流图G
2 for G中的每个基本块b
3 if 基本块b的后继块号大于本块号，说明存在回边
4 b块的前驱块为preb
5 b块的后继为succb
6 将preb的后继块设置为succb的除了preb的后继块
7 删除基本块b
8 endif
9 endfor
10 将G作为算法3的输入进行插装
11 return G；
如图5所示，控制流图中带有环的结构G1，在去环之后转化成为图G2，使用插装算法插装之后则为图G3。G1中的块B3，B2和B0，构成了一个环状结构，其中B2是一个空块。在去环的过程中将B2删除，形成G2所示的控制流图，在G2插装的过程中只要按照分支结构插装的算法进行就可以了。最终的插装结果即为G3所示的控制流图。
图5 对于循环结构的插装方法
Fig.5 Method of instrumentation of a circular structure
3 实验
Flider对于静态插装的测试分为顺序结构的源码，分支结构的源码和循环结构的源码。下面以循环结构为例，如图6为循环结构的一段源码，图7为该段代码插装之后的部分结果。
图6 循环结构的源代码
Fig.6 Source code of a circular structure
图7 由于对rwlock1锁的加锁操作而插装的语句
Fig.7 The statement that is instrumentated because of the rwlock1 lock operation
在图6中的源码中存在两个加锁语句rwlock1与rwlock2，图7所示的是对于rwlock1插装的结果。插装的语句为入栈语句，是根据加锁操作后面执行的代码所确定的，按照算法4，图7对于循环结构的插装是正确的。
4 结束语
本文使用Clang作为词法语法分析工具，建立抽象语法树，控制流图并且在控制流图的基础上进行路径分析获取源程序可能执行的所有路径。同时，根据获得的路径信息将语句插装进源码。这项工作为基于未来锁集的死锁规避方法提供了锁集信息，可以用于基于未来锁集的死锁规避方法的静态分析部分。
参考文献：
[1] GERAKIOS P， PAPASPYROU N， SAGONAS K， et al. Dynamic deadlock avoidance in systems code using statically inferred effects[C]//Proceedings of the 6th Workshop on Programming Languages and Operating Systems， New York， NY， USA：ACM， 2011： 5
[2] 白哥乐. 基于静态源码分析的多线程死锁检测方法研究 [D]. 北京：北京邮电大学，2010.
[3] BERGER E D， YANG T， LIUiu T， et al. Grace： safe multithreaded programming for C/C++[J]. ACM Sigplan Notices， 2009， 44（10）： 81-96.
[4] RABIN M O， SCOTT D. Finite automata and their decision problems[J]. IBM journal of research and development， 1959， 3（2）： 114-125.
BERGER E， YANG T， LUYiu T， et al. Grace： Safe and efficient concurrent programming[C]//Object-Oriented Programming， Systems， Languages & Applications， Orlando， Florida：ACM，2009：123-137.
[5] JULA H， CANDEA G. A scalable， sound， eventually-complete algorithm for deadlock immunity[C]//Runtime Verification. Berlin Heidelberg：Springer， 2008： 119-136.
[6] 苏小红，禹 振，王甜甜，等. 并发缺陷暴露、检测与规避研究综述[J]. 计算机学报，2014，37（103）：1-19