SOSP - 2019 - Efficient Scalable Thread-Safety-Violation Detection - Finding thousands of concurrency bugs during testing
论文链接：https://www.microsoft.com/en-us/research/uploads/prod/2019/09/sosp19-final193.pdf
项目地址：https://github.com/microsoft/TSVD
会议 PPT：https://sosp19.rcs.uwaterloo.ca/slides/li.pptx
本篇文章是 SOSP 2019 两篇 best paper 之一，出自芝加哥大学的 Shan Lu 教授所带领的研究组，对于 Shan Lu 教授感兴趣的可以查看她的个人主页：http://cs.uchicago.edu/~shanlu/
主要内容
一般来说，并发漏洞是非常难以检测、重现和调试的，而且在内部测试中也很难找到并发漏洞，但并发漏洞一旦引爆，极有可能造成生产环境的大规模停机等糟糕后果。现有的并发漏洞检测工具不能很好地集成到现有测试环境中的原因在于没有很好地解决以下几个问题：如何处理庞大代码库中，风格各异的同步机制？如何降低工具的误报？如何尽可能的少占用测试资源？
为了解决上诉问题带来的挑战，本篇工作提出了 TSVD，一款全新的并发漏洞检测工具。不同于先前工作采用运行时随机注入延迟时间的检测策略或者是采用开销巨大的静态同步检测方案来处理各种复杂的同步机制，TSVD 提出了一种轻量级的 near-miss tracking 策略来初步识别可能存在并发漏洞的线程不安全调用，然后结合本文新提出的 happens-before(HB) inferencing 技术，TSVD 能在测试过程中有效地从这些潜在不安全调用中发现真正存在并发漏洞的调用，并且排除掉不可能存在并发漏洞的调用，从而实现较低的误报。
作者在.NET平台上实现了TSVD的原型，包括两部分：TSVD runtime library，实现了 TSVD 核心算法；TSVD instrumenter，通过静态插桩的方式在 .NET 应用中集成 TSVD runtime library。
最终TSVD在实验中找到了 1134 个并发漏洞，其中80个漏洞和相应的开发者联系后得到确认，包括了77个开发者之前未发现的并发漏洞。
背景知识
TSV(Thread-Safety Violation)
本文将类库自身规定的在多线程下的使用规范称为 thread-safety contract，而如果这种规范被违反，则称之为 Thread-Safety Violation。
以类 Dictionary 为例，读操作 ContainsKey 可以被多线程同时调用，但写操作 Add 则只能在一个互斥的上下文内完成，看下面这段代码，线程 1 访问的 key1 和线程 2 访问的 key2 可能是同一个变量，因此这里存在着 TSV。
// Dictionary dict
// Thread 1:
dict.Add(key1, value)
// Thread 2:
dict.ContainsKey(key2)
happens-before
这里介绍一下 Java 中的 happens-before：
- 如果一个操作 happens-before 另一个操作，那么第一个操作的执行结果将对第二个操作可见，而且第一个操作的执行顺序排在第二个操作之前。
- 两个操作之间存在 happens-before 关系，并不意味着 Java 平台的具体实现必须要按照 happens-before 关系指定的顺序来执行。
happens-before 原则可以用来判断数据是否存在竞争、线程是否安全。
Inject Delay
有没有一种能降低 false positive 的方法？当然有，只要我们在 bug 触发的时候定位到这个 bug，那当然不存在任何的 false positive。那么如何触发 bug？一个很直接的思路就是向一个线程注入一定的延迟，增加两个线程同时访问一个变量，触发并发漏洞的可能性，示意图如下：
已有工作的缺点
已有工作存在着很大的 overhead，其原因主要有以下两点：
- 比如 DataCollider 会在所有可能的地方插入 delay，但需要多次运行以触发 bug，同时需要插入 delay 的位置多了本身就会带来巨大的 overhead
- 第二种思路，如 RaceFuzzer 则是使用先动静态结合的分析工具，找到合适的插入 delay 的位置再精准插入。虽然该方法会减少总共需要插入 delay 的数目，但在分析阶段的 overhead 同样也很大。
如下图所示，不同的工具在不同的侧重点上有着很大的 overhead，而 TSVD 的设计目的，就是尽可能地降低在识别和运行过程中的 overhead。
设计实现
为了找到真实存在的并发漏洞，首先，TSVD 会用一个轻量级的分析工具定位出所有可能造成 TSV 的调用点，称为 trap set，随后会在这些调用点进行插桩并调用以下 OnCall 函数。调用 OnCall 函数主要有两个目的：1.通过向一个线程注入 delay 的方式来放大出现 TSV 的概率；2.记录线程信息、对象信息、操作信息等要点来判断是否发生TSV，如果两个线程对一个对象进行了操作，而且其中有一个是写操作，则可以判断发生了 TSV。
很明显，这种记录动态过程中触发的 bug 的机制在设计上不会有任何的 false positive，问题的关键在于不能在所有的调用点都进行 delay，这会带来很大的 overhead。这里作者提出了两个巧妙的思路来进行 should_delay 的判断。
Identifying near misses
该思路本质是通过“**close-by physical”**来找到“concurrent logical”。并发漏洞出现在多线程对一个变量的访问上，而逻辑上的并发在时间上的表现就是重合或者是相近，因此作者认为如果观察到两个线程对同一个变量的访问在时间上相近，而且其中有一个是写操作的话，他们就有可能是一组并发访问，就可以把它标记为需要 delay 的调用点。
Inferring likely HB relationship
上一阶段找到的两个调用点虽然在时间上相近，但并不代表绝对会出现TSV，比如 happens-before 关系就是一个反面例子。happens-before 关系确保了一个操作执行的结果对另一个操作的可见性，而且这种可见性是跨线程的，所以存在 happens-before 关系的两个线程不可能出现并发漏洞。
由于同步机制的复杂程度，采用传统的静态分析技术，往往不能很高效的检测出这些 happens-before 关系。作者在这里又提出了一个很巧妙的思路：虽然种类繁多的同步机制实现各不相同，但同步机制的效果是相似的。同步机制的存在会使得对一个线程的 delay 传播到其他线程，因此可以利用这种逻辑上的联系帮助推断是否存在可能的同步关系。
以下图为例，比如在 thread 1 插入了一定的延迟，如果两个线程的访问存在着 happens-before 关系的话，可以观察到 thread 2 也同样地发生了一定比例的延迟。
implementation
TSVD 实现在 .NET 平台上，由两部分组成，其中 TSVD Runtime 实现了前文的核心算法，而 TSVD Instrumenter 会针对 C# 上的 14 个类，59 个写操作函数，64 个读操作函数进行代码插桩，插桩前后代码的差异见下图：
实验评估
Overall
实验使用的 benchmark 如下：
-
large benchmark：微软开发的 1657 个项目中使用的 43000 个模块，包含了约 122000 个多线程单元测试和约 89000 个二进制文件
-
small benchmark：从 large benchmark 中随机选取的 1000 个模块
其中 large benchmark 用一台配置有 Intel(R) Xeon(R) E5-2650 CPU，128G 内存以及 6T SSD 的服务器进行测试，而 small benchmark 用一台搭载 Intel(R) Xeon(R) E5-1620 CPU，16G 内存和 1T SSD 的服务器进行测试。
最终 TSVD 在 large benchmark 中找到了 1134 个 TSV，在提交开发者验证确认的 bug 中，有 96% 的 bug 是之前未发现的 bug，并且有 47% 的 bug 会导致严重的问题**。**
和其他工具的对比
通过在 small benchmark 上的测试结果可以看出，同其它工具相比，TSVD 找到的 bug 更多，overhead 更小：
同时，多次运行对 TSVD 找到 bug 同样有帮助作用。如下图展示的实验结果，在多次运行了 TSVD 和其它对比工具后，虽然不同工具找到的 bug 数目都有一定上升，但 TSVD 检出的 bug 数目依旧多于其他工具：
在开源数据集上的评估
为了证明 TSVD 也可以应用到除了 Microsoft 外的其它开源 C# 项目上，作者从 Github 上随机选取了 9 个开源项目进行测试，测试结果如下图所示，同样证明了 TSVD 的高效准确。
总结
作为 SOSP 19 的 best paper，TSVD 基于用“推断”代替“分析”的两个 idea 都非常有意思而且高效可行，最后也取得了相当不错的效果。不过仍需注意的是， TSVD 还是牺牲了完备性来保证了精确度，即不保证找到全部的 bug，但确保所有找到的 bug 都是 true positive，所以 TSVD 自然有一个无法解决的问题就是 false negative。这里有一个值得思考的点是，和学术界有时候可能追求工具的完备性相比，其实工业界更看重工具的精度和开销。有些工具在学术研究过程中，跑几小时甚至一两天都是合理的，但在工业界的代码量级和需求下，更快开销更低的工具可能更贴近应用场景。