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

高凤娟 等:高精度的大规模程序数据竞争检测方法 2047

精确的指针分析,然后,给定一条特定的路径,它会收集该路径的约束条件来进行精确的指针分析.
算法 2 展示了基于 Source-Sink 的检测框架,该框架提供了对 source 和 sink 的配置.setSource、setSink 和
checkSourceSinkPair 函数是由特定的漏洞检测器定义的.setSource 定义了哪些变量是 source;setSink 定义了哪
些变量为 sink;checkSourceSinkPair 则依据缺陷类型分析每条 source-sink 路径,如果该 source-sink 匹配特定的
漏洞模式,GUARD 就会将其报告出来.以内存泄露检测为例,source 设为每个内存分配函数,sink 设为内存回收
函数.所以每个内存分配函数(source)应该对应某条路径中的内存回收函数(sink),以此避免内存泄漏.关于数据
竞争的 source 和 sink,我们在下一节给出定义.retrieveCalleeSummary 函数将被调用者的 source 和 sink 信息传
递给调用者,因此 sources 和 sinks 包含了被调用者的 source 和 sink 信息.被调用者的 source 和 sink 通过参数传
播(全局变量被视作参数,详见第 4.1 节),因此调用者需要能够获取被调用者已经分析的值流信息.由于 source 和
sink 可能不在同一函数中,buildPath 函数通过调用链提取出从 source 到 sink 的路径.注意,从 source 到 sink 可能
不止一条路径,因此,变量 paths 可能会包含多条路径.最后,如果漏洞路径是可达的,那么,reportBugWithPath 就会
报告该漏洞.
该框架按逆拓扑序分析程序(第 1 行),这意味着它将依据函数调用图自底向上地分析函数.在分析过程中收
集 source 以及它们对应的 sink,当找到一个 source-sink 对时,该算法会检查 source 和 sink 是否都满足特定的漏
洞特征模式,如果是,报告此 source-sink 对以及路径信息,否则,忽略它(第 7 行~第 12 行).可以看出,GUARD 总结
source-sink 信息(第 6 行)并检查每个 source-sink 对的可行性(第 11 行),因而该步骤是上下文敏感、路径敏感的.
值得注意的是,一个 source-sink 路径 p 可以被分为两条路径 p 1 和 p 2 ,且 p 1 和 p 2 有相同的起点且分别在 source
和 sink 中结束,即 p  {,p p 2 }, 其中, p  1 ( ,...,n j n source ), p  2 ( ,...,n j n sink ).
1
算法 2. Source-Sink based detection algorithm.
Input: Program;
Output: Race Bugs.
(1) for fun in reversedTopologicalOrder(Program) do
(2) sources=setSource(fun);
(3) sinks=setSink(fun);
(4) //The following function retrieves summarized sources
(5) //and sinks from fun’s callees.
(6) retrieveCalleeSummary(sources,sinks);
(7) for source in sources do
(8) for sink in sinks do
(9) //verify each sink in variable sinks.
(10) paths=buildPath(source,sink);
(11) isFeasible=checkSourceSinkPair(source,sink,paths);
(12) reportBugWithPath(source, sink, paths, isFeasible);
3.3 竞争检测
基于 MHP 分析和 source-sink 框架,GUARD 使用算法 3 通过 source-sink 模式检测数据竞争.首先,GUARD
会检查 source 和 sink 是否满足数据竞争的一个条件,即其中至少有一个写操作(第 1 行).为了避免报告读-读的
数据访问对,GUARD 添加了一个访问检查(第 2 行~第 3 行).接下来,通过 isPathOrderReversed、isReachable 和
isMHP 精化竞争检测.isPathOrderReversed 检测一个 source-sink 路径(即 p)是否是逆序的,以此来消除重复的报
告.GUARD 将 source 和 sink 都设为读或写,因而一个 source 可能也是一个 sink,反之亦然,这将导致,如果忽略顺
序,一个漏洞可能会被报告两次.在检测完路径顺序之后,GUARD 会验证 source-sink 路径是否可达.isRechable
提取出从 source 到 sink 的路径约束并调用自定义的约束求解器筛除“简单但矛盾”的路径,之后,通过如下规则
确认 source-sink 路径是否是 MHP 的.