Page 124 - 《软件学报》2021年第7期

2042 Journal of Software 软件学报 Vol.32, No.7, July 2021

总的来说,检测数据竞争漏洞存在许多挑战.第 1 个挑战在于检查数据访问是否可能并行发生.第 2 个挑战
在于通过识别出不可行路径来消除误报.通过分析路径约束,可以避免在分析现实世界应用程序时产生误报.与
此同时,静态分析工具应该提供路径信息以指明每条数据竞争可能的执行轨迹.与此相对,若工具只提供了所有
可能的执行路径,而没有考虑路径约束,则需要更多的人力来确认数据竞争警报.最后一个挑战是由复杂的线程
操作带来的,这些操作为程序引入了不同的线程语义信息.在本文的示例中使用到 thread_create 和 thread_join
这两个典型的线程操作.除此之外,GUARD 还建模了 4 个线程操作:thread_wait、thread_notify、thread_lock、
thread_unlock.不同的线程操作会引入不同的线程语义,这使得 MHP 分析变得更为复杂.
2.2 GUARD框架
为了更清晰地阐述 GUARD 的原理,本文将该方法分为 4 个组件.图 2 展示了 GUARD 及其 4 个组件的概
况:(1) TFG 构建.构建一个线程流图(TFG),用于表示整个程序的线程信息.(2) MHP 分析.利用 TFG 综合出 MHP
信息,为进一步的 MHP 查询作准备.(3) Source-Sink 框架.利用预定义的 source-sink 模式检测漏洞,且根据值流找
出从一次数据访问开始到另一次数据访问结束的子路径.(4) 数据竞争检查器.为数据竞争定义 source-sink 模
式,以此检测数据访问子路径.对于每条数据访问子路径,GUARD 查询 MHP 关系以避免误报.换言之,它会过滤
掉无法并发访问相同内存位置的数据访问对.最后,为了通过路径敏感达到更高精度,GUARD 调用约束求解器
来验证 MHP 分析和数据竞争检测器所得到的路径的可行性.

Fig.2 Overview of GUARD
图 2 GUARD 框架
TFG 构建.这一部分会构建 TFG.TFG 是一个全局的图结构,它连接了不同的函数调用、线程操作以及控制
流.GUARD 直接从程序指令构建函数级的 TFG,TFG 中的节点根据函数调用及控制流来构造.接着,基于线程操
作及函数调用信息连接各个函数级的 TFG.这与控制流图(CFG)的构建方式有些类似,所不同的是,GUARD 为线
程操作设计了一些特殊的语义,而不是将它们当作普通的函数调用进行处理.例如,对于一个 thread_create 函数
调用,GUARD 在 TFG 中创建一条从调用点指向被创建线程入口的边.另外,根据函数调用,GUARD 将一系列指
令(CFG 中的一个块)分割为 2 个或以上的节点,这是因为,在一次函数调用前后,MHP 关系可能会有所不同.与
CFG 相比,TFG 拥有 3 个特性:CFG 中的多个基本块如果有相同的 MHP 关系就可以合并为 TFG 中的一个节点;
一个块中的任意函数调用或线程操作都会将该块分为两个节点,且以函数调用或线程操作为分界;各个函数级
的 TFG 通过函数调用或线程操作连接在一起.因此,TFG 关注线程相关的操作以及部分控制流,而非仅仅是控制
流.上述特征使得 MHP 信息的计算更为高效.图 3 是对图 1 中案例的简化分析过程.该 TFG 包含 2 个函数级 TFG,
它们的入口节点以其函数名为开始,出口节点用(0)标出.图 3(a)是示例所对应的 TFG,节点中的 (,l  , )l 代表示
j
i
例中相应的代码行.因为 foo 中创建了一个新的执行 writer 函数的线程,所以 foo 所对应的 TFG 中的节点(2,3,4)
连到 writer 对应的 TFG 入口节点.节点(6,7,8)被 writer 所对应的 TFG 的出口节点所指向,这是因为,它对线程执
行了 join 操作.值得注意的是,由于第 6 行和第 7 行的分支拥有相同的 MHP 关系,TFG 将它们合并为了一个节
点.除此之外,在第 4 行和第 8 行的函数调用前后 MHP 关系发生了改变,于是 GUARD 根据这两个函数调用将程
序指令划分为了不同节点.其后继节点(即 node(9))包含指令 arg++.鉴于函数可能存在多条 return 指令,每个函数
中的终节点将函数的所有出口点进行了合并.总体而言,构建 TFG 的目的在于实行精确的 MHP 分析并且避免
冗余分析.