动态数据竞争检测方法实验分析（一）

之前的文章大致介绍了一下我们的动态数据竞争检测平台如何构建，这篇文章主要是在动态数据竞争检测平台上实现了之前介绍的数据竞争检测方法，我们扩展了其中的一些方法使得这些方法能够识别所有的Pthread库中的同步原语。

对比的方法主要如下：

: Eraser

: Djit+

: Helgrind+ (HG)

: FastTrack (FT)

: Loft

: Acculock (AL)

: MultiLock-HB (ML)

: SimpleLock (SL)

: SimpleLock+ (SL+)

上述10中方法在之前的文章中都简单介绍过，这里就不再重复介绍，如果有不太清楚的同学可以参考原始论文。

对这10种方法进行测评的目的主要想回答以下几个问题：

• 各个检测方法的检测能力如何？
• 各个检测方法对程序造成的影响如何？
• 各个检测方法的扩展性如何？

##各个动态数据竞争检测方法的检测能力

检测能力的测评主要包括，检测率、误检率、漏检率、正确率以及错误率。

这里我们选择Google的data-race-test测试集，该测试集包含在谷歌开源的ThreadSanitizer中，我们提取了其中的96个小示例程序，然后将这96个小程序组合成一个应用程序Unittest。Unittest中包含了非常多的场景，很多场景都具有欺诈性并且对于一般的数据竞争检测器来说很难发现。

这里为了方便描述，给出如下定义：

FP Case：即False positive示例，数据竞争检测方法报告出了该示例中不存在的数据竞争。

TP Case：即True positive示例，数据竞争检测方法报告出了该示例中至少一个真实的数据竞争并且没有报告出任何不存在的数据竞争。

FN Case：即False negative示例，数据竞争检测方法没有报告出任何该示例中真实存在的数据竞争。

TN Case：即True negative示例，数据竞争检测方法没有报告出任何该示例中不存在的数据竞争并且该示例中也不存在真实的数据竞争。

TPN Case：即TP Case或是TN Case。

FPN Case：即FP Case或是FN Case。

对Unittest进行实验结果分析如下所示：

动态数据竞争检测算法检测能力实验结果

首先对于TP Case项，我们从图表中能够比较清晰的发现ML、TS能够检测到的数据竞争相对其他8种方法来说更多。主要是由于这两种方法都保留了一定数量的锁集的集合，TS中保留了并发读和写的segment集合，而ML中保留了一定数量历史访问。其次的话，我们可以发现单纯使用happens-before关系来检测数据竞争的Djit+、FT以及Loft方法检测能力低于使用hybrid混合算法的动态数据竞争方法。主要是这三种方法对线程执行交错比较敏感，会遗漏部分数据竞争。最后，可以发现基于Lockset算法的Eraser能够检测到的数据竞争更少。

然后对于FP Case项，我们从图表中能够比较清晰的发现Eraser误报的最多，因为该方法不考虑除加锁解锁以外的其他同步原语。其次发现AL和ML的误报也很多，ML在AL的基础上改进了一部分，因此相比AL少一些误报。在这就是HG、TS、SL以及SL+这三种方法也有相当一部分数量的误报。这些hybrid动态数据竞争检测方法至少会有5个误检，其中主要是因为我们在实现的时候对于printf、fget等库函数或是系统调用没有进行动态监视。而Djit+、FT和Loft这三种方法由于使用happens-before关系来检测数据竞争，因此基本没有误检，唯一的误检是由于ad-hoc隐式同步类型导致的，这部分相关内容会在后序的文章中介绍。

对于FN Case项，我们从图表中也能够比较清晰的发现Djit+、FT和Loft单纯使用happens-before关系检测数据竞争的方法有很高的漏检。而使用lockset算法或是hybrid算法的检测方法漏检率要低一些。主要是锁集算法对线程调度不太敏感。

对于TPN Case项，也就是检测的正确示例数目，我们发现Djit+、HG、TS、ML以及SL+有着比较高的得分。

对于FPN Case项，我们分析了一下其中被误检或是漏检的示例，结果如下表所示：

这里写图片描述

在表的FN Case项中，我们可以发现No Locks（数据竞争的两个操作没有任何锁保护）的比例很多，其次是False Continuous Locks（数据竞争的两个操作都有所保护，但是没有公共的锁），最后是No Continuous Locks（数据竞争的两个操作中只有其中一个操作有锁保护）。

在表的FP Case项中，我们发现Customized的比例很多，也就是我们称之为的ad-hoc类型的隐式同步。也可以发现Eraser忽视了大部分的同步原语。

后序将介绍动态数据竞争检测方法对程序造成的影响以及可扩展性两个方面的实验分析。