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

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

能分析的程序.例如,LOCKSMITH 只能分析前 4 个程序,GUARD 分析它们的平均时间为 9.25s,平均内存消耗是
250.25MB,所以 GUARD 针对 LOCKSMITH 的分析速度提升了 5 倍,降低了 2.1 倍的内存开销.同理,GUARD 针
对 LDruid、Relay、Goblint 的分析速度分别提升了 43 倍、0.72 倍和 1.8 倍;在内存开销上,GUARD 针对 LDruid、
Relay、Goblint 的内存开销增加了 0.09 倍、6.7 倍和 1.92 倍.由于 GUARD 同时引入了上下文、流、路径敏感
的分析方法,所以 GUARD的分析开销会高于较低精度的分析方法.虽然 GUARD的内存开销只比 LOCKSMITH
低,但是,由于其分析速度超过了 3 个工具,所以 GUARD 的整体分析效率依旧是比较高的.
Table 3 Tool comparison: Efficiency
表 3 工具比较:效率
Size LOCKSMITH LDruid Relay Goblint GUARD
Programs
(KLOC) T (s) Mem (MB) T (s) Mem (MB) T (s) Mem (MB) T (s) Mem (MB) T (s) Mem (MB)
aget 0.83 1 325 1 29 3 17 1 27 1 42
ctrace 1.2 1 214 1 37 3 16 1 17 1 58
smtprc 3.2 60 1 081 53 151 3 26 4 53 4 268
bzip2smp 4.2 160 1 448 1 464 804 4 41 1 38 31 633
memcached 10.9 TO NA 1 740 593 1 34 15 117 37 769
cherokee 64.5 Crash NA TO NA TO NA 457 914 97 1 641
icecast 20.9 NA OOM TO NA 8 164 Crash NA 4 536

GUARD 在保证分析精度的前提下保持高分析效率的原因为:首先,它使用 TFG 并合并了具有相同 MHP 关
系的节点,从而缩短了 MHP 分析和查询的时间;其次,为数据竞争所使用的 source-sink 模式避免了从程序入口
开始分析数据竞争;最后,GUARD 只在最后一步进行了重量级路径敏感分析以验证数据竞争的可能性.但是,由
于预处理部分(即构建 TFG、收集路径约束等)需要时间,GUARD 在检测小规模的项目时效率会有所降低.
总之,从实验结果可以看出 GUARD 是高效的,大部分程序都能在可接受的时间内完成分析.表 3 中对不同
工具的比较表明,GUARD 在处理大规模程序时总体上比其他工具更快.
5.3 GUARD的有效性

表 2 的最后两列列出了竞争检测结果.第 9 列是静态分析结果,它展示了警报的数量.最后一列是人工核验
的结果.在本次实验中,误报率的几何平均为 16.0%.此外,我们向开发者报告了 12 个不同的数据竞争漏洞,并且
其中 8 个已经得到了确认,其余正在等待确认.确认的漏洞中有 7 个已被开发者修复.
表 4 列出了各种工具检测准确性的比较情况.#Warning 是竞争检测器报告的警报数量,#Bug 代表人工确认
的漏洞数量.从表 4 中可以看出,GUARD 尽管不是最高效的检测工具,但其检测数据竞争的精度是最高的.在大
多数情况下,5 种工具都能检测出实际存在的数据竞争,但是另外 4 种工具会产生更多的误报.GUARD 的误报率
相较而言是最低的.具体而言,LOCKSMITH、LDruid、Relay、Goblint 和 GUARD 误报率的几何平均值(由于有
0,故每个值加 1,将求得几何平均值减 1 以得到最终的平均值)为 84%、80%、93%、97%和 37%.由此可见,GUARD
的误报率是最低的,而且报告的数目相对较少,确认缺陷的人工开销也相对较少.值得一提的是,除了 GUARD 和
Relay 以外,其他工具会报告包含对一个共享变量所有可能的数据访问,对这些数据方法的组合进行确认,比只
确认一条包含两个数据访问的路径需要花费更多的精力.对于所有人工确认的报告,没有发现 GUARD 漏报.

Table 4 Tool comparison: Effectiveness
表 4 工具比较:有效性
LOCKSMITH LDruid Relay Goblint GUARD
Programs
#Warning #Bug #Warning #Bug #Warning #Bug #Warning #Bug #Warning #Bug
aget 62 3 41 3 24 4 51 3 27 12
ctrace 3 1 2 2 40 5 16 1 6 6
smtprc 9 1 7 1 130 1 29 1 2 2
bzip2smp 60 0 149 0 154 0 41 0 3 0
memcached NA NA 68 1 9 1 468 1 1 1
cherokee NA NA NA NA NA NA 1 127 0 0 0
icecast NA NA NA NA 2 197 0 NA NA 0 0

从结果中也可以看出,GUARD 仍然会产生误报.通过进一步检查测试用例程序,我们发现了如下导致误报