【论文阅读】Efficient Scalable Thread-Safety-Violation Detection --- Finding thousands of concurrency bugs during testing 阅读 & 笔记

高效的可伸缩的多线程安全违规检测 — 在测试中发现数千个并发错误

摘要

一般来说,并发漏洞是非常难以检测、重现和调试的,而且在内部测试中也很难找到并发漏洞,但并发漏洞一旦引爆,极有可能造成生产环境的大规模停机等糟糕后果。现有的并发漏洞检测工具不能很好地集成到现有测试环境中的原因在于没有很好地解决以下几个问题:如何处理庞大代码库中,风格各异的同步机制?如何降低工具的误报?如何尽可能的少占用测试资源?

本文介绍了TSVD,这是一种线程安全违规检测器,它通过主动测试领域中的新设计点解决了这些挑战。与以前的随机注入延迟或使用昂贵的同步分析的技术不同,TSVD使用轻量级监视线程不安全方法的调用行为(而不是任何同步操作)来动态识别可疑对象。 然后,它注入相应的延迟,以使程序趋向于线程不安全的行为,从其能力或无能力中积极学习,并从一次测试运行到下一次测试持续进行。 TSVD已在Microsoft中部署并定期使用,它已经从数千个项目中发现了1000多个违反线程安全的行为。 它可以检测到比最新技术更多的错误,而且大多数情况下只需要进行一次测试即可。

为了解决上诉问题带来的挑战,本篇工作提出了TSVD,一款全新的并发漏洞检测工具(可扩展的并发漏洞检测器)。不同于先前工作采用运行时随机注入延迟时间的检测策略或者是采用开销巨大的静态同步检测方案来处理各种复杂的同步机制,TSVD提出了一种轻量级的near-miss tracking策略来初步识别可能存在并发漏洞的线程不安全调用,然后结合本文新提出的happens-before(HB) inferencing技术,TSVD能在测试过程中有效地从这些潜在不安全调用中发现真正存在并发漏洞的调用,并且排除掉不可能存在并发漏洞的调用,从而实现较低的误报。

TSVD已在Microsoft中部署并定期使用,作者在.NET平台上实现了TSVD的原型,包括两部分:TSVD runtime library,实现了TSVD核心算法;TSVD instrumenter,通过静态插桩的方式在.NET应用中集成TSVD runtime library。最终TSVD在实验中找到了1134个并发漏洞,其中80个漏洞和相应的开发者联系后得到确认,包括了77个开发者之前未发现的并发漏洞。 它可以检测到比最新技术更多的错误,而且大多数情况下只需要进行一次测试即可。

介绍

ppt:并发程序越来越多,并发漏洞也越来越多;

本文专门针对一类并发错误,我们称其为线程安全违规或者TLVs(threadsafety violations),库和类指定一个非正式的线程安全协定,该协定确定客户端何时可以和不能同时调用库/类。当客户端违反此协议的时候,就会产生TLV。

如下示例:

1
2
3
4
5
// Dictionary dict 
// Thread 1:
dict.Add(key1 , value)
// Thread 2:
dict.ContainsKey(key2) //判断字典里有没有key2

Dictionary类的实现允许多个线程同时调用读取操作(例如ContainsKey),但需要仅在互斥上下文中调用写入操作(例如Add)。 上面示例中即为这种情况,这种情况就包含了一个TLV bug

考虑到几乎没有虚假错误报告的目标,主动延迟注入的方法很有希望。 这种方法通过在运行时延迟策略位置的线程来引导程序线程进行冲突访问。 因此,此方法仅报告在运行时经过验证的错误,因此不是虚假的错误。

然而,考虑到具有较小开销的目标,现有的主动延迟注入技术不起作用。 为了更好地理解它们的局限性,我们可以根据固有的权衡将它们进行广泛的分类,即在注入过多延迟的成本选择延迟注入位置所需的复杂分析之间进行权衡

首先,TSVD执行轻量级险些跟踪,以识别潜在的线程安全违规。 它动态跟踪对彼此接近的同一对象调用冲突方法的线程,而无需监视或分析同步操作。

其次,TSVD使用先发生(HB)推理技术,该技术利用来自延迟注入的反馈来修剪可能由先发生关系[34]排序的调用对,因此不能当前执行。 关键的观察结果是,如果两个事件𝑎和𝑏之间存在Hb关系,那么延迟的𝑎将导致𝑏的延迟。 通过推断这种因果关系,TSVD避免了随后在这些已修剪的对上注入延迟。 注意,与由动态数据竞争检测器执行的HB分析不同,HB推断不需要在程序中建模、识别和分析同步操作,考虑到生产软件中的各种同步机制,这是昂贵和复杂的

DataCollider:几乎不进行任何分析,而是概率地在许多程序位置注入延迟。

数据竞争是一类重要的并发错误,其中两个线程在没有适当同步的情况下错误地访问共享内存位置。本文介绍了一种轻量级的、有效的动态检测内核模块中数据竞争的技术DataCollider。与现有的数据竞争检测技术不同,DataCollider忽略了程序用于保护共享内存访问的同步协议(如锁定规程)。对于使用无数复杂体系结构/设备特定同步机制的低级内核代码来说,这一点尤为重要。为了减少运行时开销,DataCollider随机抽取一小部分内存访问作为数据竞争检测的候选。DataCollider的主要新颖之处在于,它使用了许多硬件体系结构已经支持的断点功能,以实现微不足道的运行时开销。我们已经为Windows 7内核实现了DataCollider,并发现了25个确认错误的数据竞争,其中12个已经被修复。

RaceFuzzer and CTrigger :对程序中的内存访问和同步操作进行静态或动态分析,以识别潜在的错误位置,并仅在这些位置有选择地注入延迟。虽然这减少了注入的延迟数量,但这些技术承担了通过动态分析的运行时开销或识别潜在冲突访问所需的精确静态分析的不可扩展性来执行分析。

CTrigger提出了在大型程序中有效而有效地暴露原子违规漏洞的建议。 -以低发生概率,通常地识别(可能)可行的不可序列化的交错。 然后,CTrigger使用最小执行扰动来进行低概率干扰,并暴露难以捉住的原子违规行为

Motivation and Background

当两个线程同时访问同一个变量并且其中至少一个访问是写操作时,就会发生数据竞争。线程安全冲突是对对象和数据结构的数据竞争的一种概括。每个类或库有时隐式地指定一个线程安全协定,该协定确定程序中线程可以并发调用的函数集。例如,字典实现可能允许两个线程同时执行查找,而如果查找有时会触发“重新平衡”操作,则另一个实现可能不允许这样的调用。在极端情况下,无锁实现可能同时允许任何对调用。

当客户机未能满足类或库的线程安全约定时,就会发生线程安全冲突,如图1所示。虽然线程安全契约的概念可以更为一般,但本文假设一个数据结构的方法可以分为两个集合——读集合和写集合,这样,当且仅当其中至少一个方法属于写集合时,两个并发方法才会违反线程安全契约。本文研究的所有数据结构都具有这种性质。

然而,这些假设不适用于程序TSVD目标:
(1)这些程序动态地创建许多任务,远远多于线程的数量,并将它们分派到并发的后台线程上执行;
(2)数据访问的数量不再主导同步操作的数量,这包括频繁的任务创建和连接,因为数据访问是在线程不安全的方法调用的粒度上跟踪和检查的,因此在TSV检测中具有更小的数量;
(3)这些程序空间不再主导同步操作的数量,包括频繁的任务创建和连接,因为数据访问是在线程不安全的方法调用的粒度上跟踪和检查的,因此在TSV检测中的数量要小得多;

这样的范例不仅包括传统的线程库,如POSIX ThreadInc、Java的Threadclass和.NET中的System.Threading.还包括构建在此类原语之上的任务并行库,如java.util。 在C++中并发和std::Future。

例如,在.NET任务并行库(TPL)中,异步工作单元由Taskob-jects表示。 任务可以通过Task.Run等API显式分叉,也可以通过Parallel.ForEach等数据并行API隐式分叉,也可以通过C#Async/Await para-digm进行隐式分叉。 任何任务都可以使用各种机制与任何其他任务联接,例如显式Task.Waitor通过Task.Result隐式阻塞任务的结果。 因此,任务级并行是非结构化的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1 async  Task <double > getSqrt(double x,
2 Dict <double , double > dict) {
3 if (dict.ContainsKey(x)) {
4 return dict[x];// fetch from cache
5 } else {
6 Task <double > t = Task.Run(() =>
7 Math.sqrt(x)); // background work
8 double s = await t; // resume when done
9 dict.Add(x, s);// save to cache
10 return s; }}
11
12 /* Assumes`a`,`b`, and`dict`exist */
13 Task <double > sqrtA = getSqrt(a, dict);
14 Task <double > sqrtB = getSqrt(b, dict);
15 Console.WriteLine(sqrtA.Result // blocks
16 + sqrtB.Result ); // blocks

Figure 3.Example of task parallelism in C#. TSVs can occur due to concurrent accesses of dict

Alt text

图3的Happens-before图,假设dict中没有a和b。下标区分同一行的多次执行。

由上图的分析可以看到9a和9b并发了一个写写的TSV,3b和9a并发了一个读写的TSV。

前面的讨论可知道,在大型程序中,在分析之前精确地检测到它是比较困难的。

算法

我们假设一个静态分析,它将所有的调用站点标识为相关数据结构的方法,这些方法的线程安全性需要在代码中检查(第4节将提供在TSVD中使用的方法列表的更多详细信息)。这种分析很简单,它在不检查调用上下文的情况下报告调用站点(例如,即使它们在锁中使用也会被分析出来)。我们将参考这些呼叫站为TSVD点。我们还假设了一个检测框架,它可以检测程序在这些TSVD点调用TSVD时使用的陷阱机制。TSVD的唯一接口是带有参数的oncall,该参数显示生成thread_id的线程id、对象被访问的对象obj_id以及正在执行操作的op_id。

1
2
3
4
5
6
1 OnCall(thread_id , obj_id , op_id){  
2 check_for_trap(thread_id , obj_id , op_id)
3 if ( should_delay ( op_id )){
4 set_trap(thread_id , obj_id , op_id)
5 delay ()
6 clear_trap(thread_id , obj_id , op_id) }}

陷阱机制的工作原理如下。 考虑一个调用theOnCall方法的线程。 在第3行的should_delay函数选择的某些位置进行调用,线程通过在第4行的某个全局表中注册当前方法调用来设置陷阱。陷阱由线程,对象和操作的标识符三元组来标识。 线程调用delay方法休眠一段时间,在此期间“设置陷阱”。

进入OnCall上的每个其他线程都会检查它是否与当前在第2行注册的陷阱冲突。通常,如果设置了陷阱tid1,obj1,op1。 而另一个线程使用三元组tid2、obj2、op2进入该方法,这对将导致如果TSV if tid1不等于tid2、obj1 等于 obj2,并且两个操作1和2中的至少一个是写操作。

当发生此类冲突时,我们在两个线程都处于各自的程序计数器处时就捕获了这两个“红手”线程,从而使冲突的方法调用到一个公共对象。 我们可以报告从当前状态收集来的TSV足够的信息,以根除此bug,例如两个线程的堆栈跟踪。从理论上讲,我们可以报告其他相关信息,例如对象内容,但我们没有必要 到目前为止,根据我们对TSVD的经验,可以这样做。
当第一个线程从延迟中唤醒时,无论是否发现冲突,它都会清除第6行的陷阱并从OnCall方法返回。

TSVD及其变体对关于should_delay的两个关键设计问题的答案不同:

  1. 在哪里注入延迟? 哪些程序位置有资格应建议延迟注入
  2. 何时注入延迟? 在哪个程序中运行以及合格的延迟位置的哪些动态实例,should_delay建议延迟注入。

在做出上述设计决策时,我们必须牢记以下目标和约束:

  • 运行时开销–由于在每个OnCall函数中均应调用should_delay函数,因此限制其复杂度以减少运行时开销非常重要。 同时,如果此功能的选择性不够好,我们将注入过多的延迟,这反过来会增加运行时的开销。

  • 测试运行的次数–如果should_delay函数的选择性太强,那么它可能会遗漏错误或要求运行测试太多次,从而增加了测试资源的需求。

  • 准确性目标–要求没有误报率或很少有误报率; 在不消耗太多资源的情况下,需要很少的假阴性。

  • 复杂性约束–我们希望该工具能够跨许多工程团队的代码工作。 具体来说,该工具应处理开发人员可以用来防止TSV的各种同步机制。 此外,对任意C#进行复杂的静态分析也具有挑战性。 例如,有时只有一个物理线程可用时,ForEach.Parallel块有时可以转换为顺序循环,否则可以转换为并行循环。 静态确定这是一个难题。 对于本文,我们将自己局限于动态技术。 作为任何动态分析工具,TSVD不能保证在程序中找到所有TSV。 然而,通过保证不报告任何错误,它保证了“错误的健全性” [23]。

接下来,我们在图2中介绍在设计空间中采用不同设计点的变体。我们从图2左上角的两个简单变体开始,它们充当TSVD的基线。

动态随机

最简单的算法将每个TSVD点作为合格的延迟位置(where),并在随机时刻(when)注入延迟。 换句话说,对should_delay的调用以某些(small)概率返回true。 一旦决定延迟线程,该线程便会随机睡眠一段时间。

静态随机

以前使用延迟注入来暴露数据竞争的工作,例如DataCollider [14],观察到动态采样是无效的,因为它倾向于在热路径上插入更多的延迟,而忽略冷路径,在冷路径中可能会隐藏更多的错误。 为了避免在热路径上冗余地引入延迟并专注于冷路径,DataCollider会“静态地”对内存访问进行采样-也就是说,对静态程序位置进行统一采样,而与对特定位置进行采样的次数无关。 我们在StaticRandom变体中模拟了该算法,在该变体中,对相关数据结构的方法的静态调用站点进行了统一采样。

与DynamicRandom相比,在哪里注入延迟不会改变,仍然是所有TSVD点,但是何时注入延迟会区分代码路径和热路径。

TSVD

我们对TSVD的动机来自于在我们的环境中实施动态随机和静态随机的初步经验。 尽管这些变体正在发现错误,但许多错误需要运行相同的测试数十次,这在我们的设置中是不可接受的。进一步调查,我们发现,这些变异是注入一大部分的延迟在“错误”的地方——要么当程序执行在单线程环境中,当所有其他线程正在等待外部事件,或当程序访问的数据结构以“安全”的方式——比如说通过持有正确的锁。在这两种情况下,延迟直接转化为端到端减速,迫使我们降低延迟的概率以减少运行时开销。这反过来又会导致错过bug,或者按比例增加寻找真正bug的运行次数。

TSVD是专门为避免这些问题而设计的。如图2所示,TSVD探索了一个新的设计点。它使用本地插装,不进行同步建模,也不进行分析前发生,以减少运行时开销,同时识别潜在的延迟注入候选项。通过关注更有可能违反线程安全的候选对象,它可以实现更好的bug暴露能力,而不需要更多、更少的资源消耗。

True Positive (真正, TP)被模型预测为正的正样本; 正确率
True Negative(真负 , TN)被模型预测为负的负样本 ;
False Positive (假正, FP)被模型预测为正的负样本; 误报
False Negative(假负 , FN)被模型预测为负的正样本;漏报

在哪里注入延迟?

在高层次上,TSVD使用轻量级分析来动态维护一组称为trap的程序位置危险状态集,这些程序位置可能会导致线程安全违规,并且只在这些位置上注入延迟。

在测试运行期间,当TSVD发现新的危险对时,陷阱集的大小会增长,或者当TSVD删除现有的危险对时,陷阱集的大小会缩小

TSVD标识的项目地点一双危险如果(1)他们对应一个靠近TSV(identifying near misses),TSVD希望把之前的近距离脱靶变成真正的冲突,和(2)至少有一个运行在这两个位置与多个程序的活动线程并发阶段(Inferring Concurrent Phases )。

如果(1)TSVD推断出这两个位置之间可能发生了之前的关系(Inferring likely HB relationship ),因此这两个位置不太可能违反线程安全,或者(2)已经在这两个位置发现了违反,则从设置的陷阱中删除一个危险的对。

identifying near misses (识别出时间上相近的操作)

直观地说,如果一对程序位置在密集的测试环境中从未接近于创建线程安全冲突,那么由于底层的程序语义和同步操作,它们可能永远也无法创建线程安全冲突。另一方面来说,比如说一个访问在程序的loc1位置,该访问元组为(tid1、obj1、op1)并发生在时间 t1,而另一个访问在程序的loc2,访问元组为(tid2、obj2、op2),发生时间为t2。如果:tid1不等于tid2;obj1 = obj2;op1和op2有其中之一为写操作;而且t1与t2的差值小与某个定义好的时间阈值a;则TSVD认为这一对𝑙𝑜𝑐1,𝑙𝑜𝑐2是危险的一对。

为了做出此判断,TSVD会自前以来维护每个对象的访问列表。 为了实现简单起见,TSVD而不是将此状态存储在对象元数据中,而是维护一个全局哈希表,该哈希表由包含该先前访问列表的对象的哈希码索引。 在每次访问时,TSVD都会查询此列表以识别危险对。

Inferring Concurrent Phases (推断并发阶段)

同步操作,如fork、joins、barriers和locks,在并发程序的执行过程中,可能会导致顺序执行阶段,如初始化阶段、清理阶段、fork之后的join阶段等等,而这样一个顺序阶段中的TSVD点决不能与另一个TSVD点并行执行。

TSVD通过检查TSVD点的执行历史来推断并发执行阶段。具体来说,它使用固定数量的最近执行的TSVD点维护全局历史缓冲区。如果此缓冲区中的TSVD点来自多个线程,则TSVD将执行视为处于并发阶段。

用推断替代分析

Inferring likely HB relationship (推断可能存在的HB关系)

TSVD基于near misses 和Concurrent Phases的危险对识别可能是不正确的。例如,两个被同一个锁保护的访问可能发生在彼此靠近的地方。而且如果两个访问之间的动态happens-before (HB)关系,TSVD将无法将这些接近的miss转换为真正的冲突。TSVD没有使用跟踪同步来计算这种HB关系,而是使用下面的轻量级技术来推断可能的HB关系,这样可以大大地减少开销。

TSVD的动态HB推理基于以下关键的观察。如果𝑙𝑜𝑐1 happens-before 𝑙𝑜𝑐2 执行,然后推迟之前𝑙𝑜𝑐1会导致也会按照一定比例延迟𝑙𝑜𝑐2。如图6所示,考虑当𝑙𝑜𝑐1和𝑙𝑜𝑐2都始终都是有锁保护的状态和𝑙𝑜𝑐1首先发生。当在𝑙𝑜𝑐1之前注入一个延迟,发生这种延迟当线程执行𝑙𝑜𝑐1仍然持有的锁。因此,当线程执行𝑙𝑜𝑐2需要获得这把锁(访问𝑙𝑜𝑐2之前需要这把锁),它将会被阻止。通过动态跟踪程序位置之间的因果关系,TSVD从而推断出它们之间可能存在HB关系。

Alt text

追踪这种因果关系的过程如下。除了上面描述的每个对象的历史记录外,TSVD还维护每个线程最近访问的历史记录。正确考虑在访问loc1之前注入延迟d1,始于𝑡1start于𝑡1end结束。在𝑡2时后续在一个不同的线程𝑇ℎ𝑑2访问𝑙𝑜𝑐2 ,我们将检查𝑇ℎ𝑑2的上一个访问记录,标示为𝑡0,推断出动态的HB关系𝑙𝑜𝑐1和𝑙𝑜𝑐2if (1)还有很长的差距𝑙𝑜𝑐2和之前访问,𝑡2−𝑡0≥𝛿ℎ𝑏*𝑑𝑒𝑙𝑎𝑦_𝑡𝑖𝑚𝑒,因果延迟阈值 (2)重叠的时间间隔注射延迟,𝑡0≤𝑡1end。如果多个延迟{𝑑 at 𝑙𝑜𝑐}满足这个推断条件𝑇ℎ𝑑2和𝑙𝑜𝑐2,我们的贡献与最近完成的延迟之间存在2个较大的差距,并据此推断HB关系。 考虑到事前关系的传递性,线程2中的下一个访问也被认为是可能发生在1之后。 同样,𝑘ℎ𝑏是一个可调参数,我们将在评估部分评估其灵敏度。

Delay Decaying

当然,上面的所有推论,包括 near misses、Inferring Concurrent Phases和可信的HB -关系推断,仍然不能保证剪除所有非TSV对。因此,对于危险列表中的每个危险对{p1,p2},在任何一个延迟注入不管是p1或p2处的每次延迟注入都不能使𝑝1和𝑝2与所访问的同一对象并行执行,将导致TSVD衰减在𝑝1和𝑝2处未来延迟注入的概率。当一个位置的概率下降到0时,它的所有相关对都从trap集中移除。

When to inject delays?

TSVD与以前的工作不同,将延迟计划和延迟注入分离到不同的运行中或者使用许多运行来逐步将延迟注入所有计划的位置,TSVD在同一个运行中系统地进行延迟计划和注入,充分利用测试资源。

在同一运行中进行计划和注入 一旦TSVD识别出一对危险的程序位置(几乎彼此丢失),TSVD不会等到下一次运行时才暴露它们之间潜在的线程安全冲突。 理由是大多数指令执行不止一次,因此大多数错误都有多种表现形式。 我们在第5节中的实验结果证实了这一点,该结果表明TSVD多次击中同一个bug。 因此,TSVD仍可以尝试在初始未命中之后暴露错误。 具体来说,无论何时要执行程序位置,TSVD都会检查是否是当前陷阱集的一部分。 如果有问题,TSVD将“有可能”插入延迟。

Multiple testing runs如果TSVD观察到的接近未命中的情况实际上是暴露该bug的唯一机会,则上述延迟注入方案将错过一个bug。 即,如果危险的位置对在确定后就再也无法一起运行了。 如果测试资源允许,TSVD会再次运行该程序,并携带从第一次运行中获得的知识,以帮助发现这些错误。

在第一次运行期间,TSVD将其陷阱集记录在持久性陷阱文件中。 运行结束时,陷阱文件包含最后一组危险对。 在第二次运行的开始,TSVD从文件初始化其陷阱集,从而使其即使在第一次出现时也可以成对注入延迟。

** 并行延迟注入**在整个运行过程中仅注入一个延迟或多个延迟,并且一次只允许延迟一个或多个线程之间存在明显的权衡取舍:当注入多个延迟时,它们可以抵消彼此的影响; 当注入很少的延迟时,我们将需要太多的运行来测试所有可能的延迟情况。

TSVD决定以一种激进的方式进行延迟注入—严格按照危险对列表和衰减概率方案插入延迟,而不管是否已阻塞另一个线程。 请注意,尽管这种积极的策略可能会导致某些注入的延迟彼此重叠,但是这些重叠只是部分重叠,不太可能相互抵消。 这是因为不同的线程将在不同的时间被解除阻塞,并且我们的衰减概率方案还有助于避免同时阻塞太多的线程。 另一方面,严格避免延迟重叠的另一种设计将导致延迟注入太少,从而损害了我们在紧张的测试预算内暴露错误的机会,这将在评估部分进行演示。

TSVD with happens-before analysis

为了将TSVD与依赖于HB分析的现有技术进行比较,我们设计了一种TSVD变体,称为TSVDHB,它遵循RaceFuzzer的方法[58]。 请注意,TSVDHB根据目标错误的类型使用了一些优化来加速传统的HB分析

Where to inject delays? 就像在TSVD中一样,TSVDHB动态地维护陷阱集,出现在陷阱集中的每个程序单元都有一个延迟注入候选对象。 在运行时,如果对应访问访问𝑡𝑖𝑑1,𝑜𝑏𝑗1,𝑜𝑝1和𝑡𝑖𝑑1,𝑜𝑏𝑗1,𝑜𝑝1满足𝑡𝑖𝑑1不等于𝑡𝑖𝑑2,𝑜𝑏𝑗1=𝑜𝑏𝑗2,𝑜𝑝1和𝑜𝑝2冲突,并且最重要的是它们没有发生,则TSVDHB在陷阱集中添加一对程序位置{𝑙𝑜𝑐1,𝑙𝑜𝑐2} -在彼此建立关系之前。

TSVDHB监视同步操作,例如锁,派生和联接,并使用矢量时钟[18]计算访问之间的事前关联。

TSVDHB优化了传统的竞争检测以加快其HB分析,原因是观察到与传统的竞争检测不同,在传统的竞争检测中,执行跟踪包含很少的同步操作,但是有许多内存访问,TSVDHB面临许多同步操作(C#云中大量异步/等待 服务模块)但访问相对较少(例如,TSVD点-某些数据结构的线程不安全方法的调用)。

第一个优化是增加本地时间戳访问(TSVD点),与传统的种族检测[19]相对,该访问在运行时相对较少,但在同步操作中却相对不频繁[19]。

第二个优化是TSVDHB使用不可变的数据结构。 -AVL树形图-表示矢量时钟,这与使用可变数组或哈希表的传统实现不同。 对于具有组件的矢量时钟,消息发送(或其他类似类型的同步)事件需要使用传统的可变表进行“时间/内存复制”,而不变的时钟可以通过“ O1-时间”传递。 另一方面,TSVDHB需要Ologn时间/内存来执行递增操作,而可变时钟可以在 O1时间内就地更新。 幸运的是,TSVDHB仅将递增操作限制为不常见的TSVD点。 最后,消息接收(或其他类似类型的同步)事件在两个数据结构上都需要时间,因为必须计算逐个元素的最大值。幸运的是,在相对常见的情况下,任务fork和join而没有经过任何TSVD点,矢量时钟相关联 与连接消息和接收线程完全相同的对象;可以通过简单地检查引用相等性将这样的操作优化为O1。

何时添加延迟 与RaceFuzzer不同,RaceFuzzer使用许多针对特定的一对潜在数据竞争的运行,TSVDHB旨在像TSVD一样在少量测试运行中暴露错误。 因此,就像TSVD一样,TSVDHB在分析和陷阱集填充之前发生的相同运行中注入了延迟; 它可以同时延迟多个线程。 完成一个测试运行后,将记录陷阱集中的剩余对,并将它们馈送到测试运行中(如果有的话)。 与TSVD一样,TSVDHB使用概率衰减来修剪可能的虚假危险对。

Implementation

我们已经为.NET应用程序(例如C#和F#)实现了TSVD。 它具有两个关键组件:

(1)实现核心算法的TSVD运行时库
(2)给定.NET二进制文件的TSVD检测器,通过静态二进制检测自动将TSVD运行时库合并到其中。

我们选择了应用程序二进制文件的静态工具,因为这使我们能够在未经修改的现有测试管道中使用TSVD工具化的二进制文件(与框架工具[65]不同,后者需要使用工具化的公共语言运行时(CLR)或动态工具[2]更新测试管道, 需要修改测试环境)。 尽管我们的实现是特定于.NET的,但我们相信基础技术TSVD可以轻松实现其他语言和运行时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1 List <int > listObject = new List <int >(); 
2 listObject.Add(15);
(a) Original code

1 List <int > listObject = new List <int >();
2 int op_id = GetOpId();
3 Proxy_123(listObject , 15, op_id);
(b) Instrumented code

1 void Proxy_123(Object obj ,int x,int op_id) {
2 var thread_id = GetCurrentThreadId ();
3 var obj_id = obj.GetHashCode();
4 OnCall(thread_id , obj_id , op_id);
5 obj.Add(x); }
(c) Proxy method

Figure 7. TSVD instrumentation

TSVD Instrumenter 这将获取应用程序二进制文件列表和目标线程不安全API的列表。 在当前TSVD的原型中,我们专注于14个C#线程不安全类(例如,列表,字典),并手动将其中的59个API识别为写入API,将64个API识别为读取API。 对于这些数据结构类而言,此过程非常简单,并且成本低廉,可以通过将该列表重新用于所有C#程序测试来轻松摊销。 然后,它通过将每个线程不安全的API调用替换为自动生成的代理调用来检测二进制文件,如图7所示。 但是,在进行原始调用之前,它会调用TSVD运行时库中实现的OnCall方法(图5)。 TSVD使用Mono.Cecil [28]进行检测。

TSVD工具可以用作命令行工具,也可以与Visual Studio一起使用(作为构建后的步骤)。 为了使开发人员无需额外配置即可使用TSVD,TSVD在.NET标准库中随附了可扩展的线程不安全API列表。 该列表还包括有关API是读取API还是写入API的信息。

TSVD Runtime 这实现了OnCall方法,该方法执行核心TSVD算法(图5)。 此外,
(1) 在检测到错误时记录运行时上下文,包括错误位置(例如,方法名称和源代码行号)以及竞速线程的堆栈跟踪。
(2) 它跟踪每个线程和每个请求注入的总延迟,以便可以限制每个线程或请求的最大延迟。 这有助于避免测试超时。
(3) 跟踪已检测API的测试范围。
(4) 最后,它更新已检测的已签名二进制文件的签名。

在Microsoft中使用TSVD时,我们观察到许多使用async / await的异步程序在测试设置中同步运行,因此,当程序确实异步运行时,TSVD找不到可能在生产运行中体现的线程安全性错误。 我们发现,根本原因是.NET运行时优化,它可以同步执行快速异步功能。 这会影响许多用快速模拟实现替换异步I / O调用的测试。 为了解决这个问题,TSVD使用async / await代码来强制所有慢速或快速异步功能异步运行。 请注意,在我们的实验(第5节)中,此策略不仅将应用于TSVD,还将应用于将与TSVD进行比较的所有技术。

Evaluation

Methodology

基准 为了进行评估,我们从Microsoft进行中的1,657个项目中收集了大约43个软件模块。 我们以此为基准。 这些模块在集成的构建和测试环境中进行定期测试。 每个模块都包含单元测试的集合以及执行测试所需的所有二进制文件。 它们总共包含大约122个多线程单元测试和89个程序二进制文件。 为了使用TSVD测试模块,我们需要对其二进制文件进行检测并运行其现有的单元测试。2%的模块还包括长期运行的端到端测试,我们也可以运行它们。 在集成环境中可用的所有软件模块中,我们选择了以下模块:

a)用.NET语言编写的模块,例如C#或F#,因为目前已为.NET程序实现TSVD
b)通过了过去2个版本的所有测试,从而确保了这些模块是稳定且经过良好测试的
c)至少使用一次多线程原语或C#async / await机制。

我们将使用它来评估TSVD的错误暴露能力和性能。要针对其他设计和参数设置来评估TSVD,我们从Large基准测试中随机抽取了1000个模块。 我们称此为small Benchmarks。 该套件一起包含3350个多线程单元测试。

实验设置我们在带有Intel®Xeon®E5-1620 CPU,16G内存和1T SSD的小型服务器(S1)上运行小型基准测试套件。 由于所有测试的软件模块彼此独立,因此我们在S1上一次运行10个模块。 我们在大型服务器(S2)上运行大型套件,该服务器配备了Intel Xeon E5-2650 CPU,128G内存和6T SSD。 S1和S2均使用Windows10操作系统。

Overall Results

Alt text

漏洞的发现 在过去的几个月中,我们一直在大型基准测试中使用TSVD的变体。 表1总结了结果。 总的来说,我们发现了1,134个错误,这些错误是由参与TSV的一对静态程序位置唯一标识的,涉及1,180个唯一的静态程序位置。2其中1,009个错误是使用我们在本文中介绍的核心TSVD找到的。 而其余的错误则来自我们先前尝试使用TSVD的变体,即DynamicRandom和TSVDHB。
对于每个错误,TSVD都会生成一对堆栈跟踪,该跟踪显示了两个正在积极参与线程安全违规的线程。 请注意,同一错误可能会出现在多个堆栈跟踪对中。 另一方面,在具有相同程序位置对的低级数据结构中,高层数据结构中的多个错误可能会显示为冲突。 总体而言,我们在21,013个不同的堆栈跟踪对中发现了上述错误(即每个错误18.5个堆栈跟踪对)。 由于我们无法识别两个不同的堆栈跟踪对是否对应于同一“错误”,因此我们将保守的程序位置对用于唯一的错误计数。

平均来说,我们在9.8%的项目和1.9%的模块中至少发现了一个bug。运行开发人员提供的现有测试,当TSVD找到这些出现错误,注意TSVD不会报告错误报告。

漏洞验证 我们联系了微软的四个产品团队来验证TSVD在他们的软件中发现的所有漏洞(总共80个)。所有的漏洞都被证实是真的漏洞。其中77个是开发人员以前不知道的新bug,其余3个是通过其他方式同时发现的。我们还在联系其他团队。
漏洞质量 38个漏洞被确认为“高优先级”。漏洞的内部分类表明,如果这些漏洞出现在生产中,将导致客户面临停机,因此需要立即修复。开发人员立即修复了这些错误。22个漏洞属于“中等优先级”,其中18个已经修复。剩下的20个bug都是非关键代码,比如为单元测试而编写的测试驱动程序或模拟代码。虽然这些错误的优先级较低,但仍需要修复它们以防止不确定的测试失败。

**可操作的报告 ** 总体来说,开发人员发现错误报告是足够可操作的。两个冲突线程的堆栈跟踪提供了足够的详细信息,可以从根本上解决问题。在许多情况下,修复包括引入额外的同步或用线程安全的数据结构版本替换数据结构。
除了错误报告,TSVD还报告在任何上下文和并发上下文中测试期间命中的检测点的统计信息。一个团队发现这些“覆盖率”统计数据非常有用,并且在他们的测试中发现了一些盲点,比如只在单元测试期间的顺序上下文中调用的关键部分等等。
漏洞特别注意 所有这些软件团队都使用其通常的生产测试管道来发现各种类型的Bug。TSVD发现的漏洞已经在他们的系统中存在了好几个月,但仍然没有被测试管道发现。为了进一步确认TSVD发现的bug不容易找到,我们与其中一个团队密切合作,跟踪和比较TSVD发现的bug和他们通常的测试管道发现的bug。在3个月的时间里,TSVD在代码中发现了15个线程安全漏洞(均被确认为“第一优先级”,并立即修复),而测试管道在同一时间内均未发现这些漏洞。

漏洞特征 我们发现的1134个错误中有49%是由于线程不安全对象上的并发读写冲突造成的。这种错误的一个有趣的根本原因是只锁定对线程不安全对象的写操作,而不是读操作。70%的错误是由使用异步/等待任务并行库。这些错误中的许多都是从TSVD的检测设计中受益的,该设计强制所有异步函数(无论是慢速还是快速)异步运行。34%的错误是由于两个线程执行相同的操作造成的。测试代码中错误位置的平均堆栈深度为9.1,这表明许多错误都出现在生产代码的内部。请注意,同一个bug位置可能出现在多个bug中(计为位置对),同一个bug在同一测试运行期间可能出现多次。在我们的实验中,一个错误位置平均出现35.6次(中位数4次)。尽管反复出现,但在微软现有的测试技术中,错误的位置仍然没有被发现。超过一半的错误涉及字典数据结构。注意.NET的标准库包括线程安全的ConcurrentDictionary。然而,我们的结果表明,开发人员经常在多线程应用程序中使用线程不安全字典,而没有必要的同步原语。在与开发人员交谈时,我们发现这种不正确用法背后有一个有趣的原因:错误地假设只要键不同,两次写入字典都是线程安全的。

Comparison with other detection techniques(与其他检测技术的比较)

Alt text

我们比较了TSVD与数据对撞机以及第3节中讨论的使用1000模块小基准套件的其他检测技术。我们根据在两轮运行中发现的bug数量和开销对它们进行比较,开销是根据工具对未配置的基线测试运行施加的额外时间量计算的。结果总结在表2中(DynamicRandom在延迟注入中使用0.05概率)。

Alt text

发现的错误数TSVD发现的错误数最多:第一轮42个,第二轮11个。这11个bug中的每一个都包含一个TSVD点,该点在单元测试期间只执行一次,因此在第一次运行的未遂事件之后无法公开。DynamicRandom和DataCollider检测到的错误数量明显较少,因为它们在TSVD点注入延迟的概率很小(DynamicRandom为0.05)。他们可能会发现更多的漏洞,如果运行额外的回合,但是他们需要很多回合才能捕获TSVD的错误报告功能。TSVD优于TSVDHB,因为TSVDHB既可以在边之前发生丢失,也可以添加虚假的边,就像其他基于技术的动态发生之前一样[47]。TSVDHB巨大的分析开销也会在运行时干扰更多的bug暴露。

我们在8000个模块的更大基准中观察到类似的趋势。在两轮运行中,TSVD发现256个bug(第一轮为227个),TSVDHB发现192个bug,DynamicRandom发现79个bug。

表2的一个有趣的观察结果是,TSVD在第一轮中发现的bug比在两轮中发现的其他技术要多。此外,TSVD的第一轮发现了所有工具发现的所有错误的80%。这两个观察结果也适用于我们完整的基准测试套件。这证明了我们的设计没有将延迟规划和注入分离到不同的运行中。它还为使用TSVD提供了一个更节省资源的选项:当在严重的资源限制下进行测试时,可以选择只运行一轮TSVD,并且仍然捕获绝大多数的bug。注意,尽管TSVDHB在表2中发现的新bug比TSVD多,但他们都发现了总bug的可比数量:分别为41和53。

如表2所示,通过性能比较,TSVD不仅发现了最多的错误,而且开销也最少。TSVD的性能优势来自两个方面。与DynamicRandom相比,TSVD在多线程运行时注入的延迟最多。DynamicRandom在序列阶段注入了许多延迟,这些延迟永远不会检测到错误,但也会带来巨大的开销。与TSVDHB相比,TSVD和TSVDHB都在并发阶段注入延迟,而TSVDHB在分析运行时的前发生关系上花费了大量的时间,这平均带来了270%的运行时开销。
考虑到tsv的不确定性和其中一些技术的概率性,在多次运行之后的bug数量,我们使用小型基准测试套件运行了50次这些技术,以查看在最后可以找到多少个bug。如图8所示,即使经过多次运行,TSVD的bug检测优势仍然优于其他技术。这四种技术最终共发现79个漏洞,其中73个是TSVD发现的,54个是TSVDHB发现的,另外两个发现的更少。而且,这些漏洞中的大多数(接近70%)只需运行两次TSVD就可以被捕获!接下来我们将利用这些结果来帮助理解TSVD的假漏洞。

TSVD-TSVD的误报 不报告任何假的漏洞。TSVD报告的每一个漏洞都是一个真正的漏洞-线程安全冲突可以并且已经由TSVD触发。

TSVD的假报告 由于TSVs的不确定性和TSVD面临的测试预算紧张,TSVD不可避免地存在假报告。由于了解基准中存在多少TSV的基本事实是不切实际的,因此我们使用4个工具在图8中累积200次运行结束时发现的79个错误作为我们的最大努力的基本事实。我们分析了TSVD在仅仅两次测试中漏掉的26个错误,并将它们分为三类:

(1)near-miss 假的报告。对于19个bug,这两个racing操作仅在很少的调度(例如,资源使用和资源取消分配)下紧密执行。在大多数执行中,他们之间有很长的时间间隔,比如超过几秒钟。因此,TSVD中的未遂跟踪没有将它们识别为危险对,因此在两次运行中没有注入延迟来暴露错误。在运行TSVD 50次之后,这19个bug中有15个被捕获。

(2) 在推断假报告之前发生。对于两个bug,TSVD的HB推断错误地将两个并发操作视为顺序前发生的操作,因此失去了触发bug的机会。即使运行了50次,TSVD仍然无法检测到这两个错误。

(3) 延迟注射假报告。对于5个bug,两次测试运行期间的时间恰好是注入的延迟不足以触发bug。在运行了几次之后,这些bug都被TSVD发现了。最后,考虑到TSVD的设计目标,它自然会错过不是tsv的计时错误。例如,最近对Azure软件中真实事件的研究

TSVD实验所针对的一组类似的软件项目表明,与传统的单机系统相比,由定时错误引起的事件要多得多,其中大约一半与并发访问持久性数据有关。当前的TSVD原型只关注内存中的数据结构,因此无法检测到这些持久数据错误。未来的研究可以扩展TSVD的思想来检测其他类型的定时错误。

Evaluating TSVD parameters

TSVD的概率性质 由于TSVD以概率方式注入延迟,人们可能想知道TSVD的结果在不同的尝试中可能有多大的差异。图9(a)显示了12次尝试中检测到的错误数和TSVD的开销。在每次尝试中,TSVD都使用相同的默认参数设置,并应用于两次连续运行,如表2所示。正如我们在图中看到的,不同的尝试的结果确实有所不同,但只有一点:检测到的错误数量从52到54不等,开销在30%到35%之间,中间值为53个错误,开销为33%。

near-miss参数 TSVD使用两个参数来跟踪near-misses:TSVD为每个对象保留的接收次数和TSVD将两个访问视为near-miss的物理时间窗口。如图9(b)和(c)(x轴的notelog scale)所示,大致来说,bug 计数和开销都随着这两个参数的增加而增加。使用过小的值(例如,𝑁𝑛𝑚=1或𝑇𝑛𝑚=1𝑚𝑠)会由于未识别危险对而错过许多漏洞。TSVD的故障值𝑁𝑛𝑚=5和𝑇𝑛𝑚=100𝑚𝑠查找所有的错误,开销很小。较大的值不会显著地增加错误数,但会增加开销(特别是对于𝑁𝑛𝑚)。

HB推断参数 SVD使用两个参数进行HB推断:一个是因果延迟阻塞阈值𝛿ℎ𝑏和一个𝑘ℎ𝑏访问的推断窗口(第3.4.4节)。图9(d)显示了将𝛿ℎ𝑏从0变为0.8的效果。一个像0这样太小的值推断了许多不存在的HB关系,因此遗漏了许多错误;较大的值在推断HB关系时有更严格的约束条件。但是,管理费用和错误计数不会改变muchbeyond TSVD的默认值0.5。图9(e)显示了变化𝑘ℎ𝑏的影响。一个较大的值将转换为更多的hb关系,从而减少危险对的数量,并最终减少错误和开销的数量。Toolarge一个值大大减少了bug的数量。TSVD的故障值𝑘ℎ𝑏=5在错误计数和开销之间提供了一个最佳值。

Alt text

并发相位检测的缓冲区大小 图9(f)表明,开销和检测到的错误数量都随着全局历史缓冲区的大小而增长-如果缓冲区较大,TSVD可能会错误地将顺序操作视为并发操作,并生成不会导致任何错误的危险对;但是,如果缓冲区较小,真正的并发操作可能会被误认为是顺序的。TSVD使用默认大小16,在开销和错误计数之间给出了一个很好的折衷。

延迟注入 图9(g)显示了每个TSVD点衰减延迟注入概率的影响。一个特别糟糕的配置是当因子为0时,这意味着TSVD在这些TSVD点的所有出现中注入延迟而没有任何衰减。这种配置会带来太多的开销:对于3%的模块,零衰减的开销超过100%(我们观察到的最大开销是一个模块的6600%)。这些模块反复频繁地使用TSVD点(例如,它们在环路内)。图9(h)显示了一个陷阱点上TSVD注入延迟量的影响。正如预期的那样,更长的延迟会增加运行时开销,但也会为冲突操作在时间上重叠创造更多机会。TSVD使用100ms作为默认值。

各种TSVD技术的有效性 表3显示了TSVD在一次禁用其核心组件之一时的性能。(在“无窗口化”中,TSVD将整个历史中不同线程的冲突访问视为几乎未命中)结果显示,HB推断和窗口化是查找没有它们的错误的最关键技术,错误计数从53下降到45和46。开窗是减少开销的最重要因素,没有窗口化,开销从33%增加到143%。总的来说,所有的技术都是TSVD有效性所必需的。

TSVD CPU/Memory Consumption (CPU/内存消耗)

为了了解TSVD的详细资源消耗,我们在有和没有TSVD的小基准套件中运行每个单元测试,同时记录每次运行中的最大内存使用量和平均CPU使用量。在所有的单元测试中,最大内存的中位数增长是17%,平均中位数增长CPU利用率为82%。额外的内存主要用于保存未遂对和每个线程不安全对象的访问历史。额外的CPU实用程序主要是由于我们的指令插入强制所有异步函数异步运行,如第4节所述。相比之下,如果没有TSVD,.NET优化会使许多异步函数同时运行,使用的内核要少得多。

Examples of bugs found by TSVD

Alt text

设备管理器 如图10(a)所示,设备管理器使用字典GlobalStatus来维护每个客户机的状态,其中clientID是密钥,客户机状态是值。设备管理器有一个线程负责从多个客户端侦听。每当管理器从客户端收到消息时,此侦听线程将创建一个异步任务,如图10(a)所示,以更新相应客户端的状态,并继续其侦听。当两个客户端在相似的时间发送消息时,Dictionary类可能会发生并发写冲突,这可能会导致图中第4行的两次并发执行,从而导致两次并发字典写操作。结果,globalStatus字典将被静默地损坏。

网络验证 图10(b)显示了字典类上并发写入冲突的另一个检查示例,该类的代码模式与第一个示例截然不同。当网络服务启动时,验证器需要验证每个主机的配置信息,这包括读取主机的配置信息(第3行)并将其存储到conFigureCache字典以进行进一步验证。为了加快此过程,验证程序使用parallel.ForEach (第1行)来并行化不同主机的验证。parallel.ForEach 自动生成多个并发线程,当其中一些线程同时执行第4行时,会发生并发写冲突来损坏configureCache。

生产事件示例 这是一个关于两个线程试图在生产运行中同时对列表排序的错误。当两个线程同时执行此操作时,未受保护列表的排序结果是不确定的。这种不确定的行为传播了,最后导致服务中断了几个小时。TSVD可以在没有任何先验知识的情况下重现这个bug,帮助开发人员降低调试效果。

TSVD on Open Source Projects

为了评估TSVD是否可以在微软之外使用,我们将TSVD应用于9个开源C#项目(表4)。在没有任何现有的C#bug基准套件的情况下,我们使用“race condition”关键字搜索Github,并确定了这9个包含(1)关于标准库api上tsv的确认bug报告和(2)开发人员编写的测试用例。

使用与之前完全相同的参数,TSVD在最多2次运行中成功地检测并触发所有被测tsv。对于除了3个项目以外的所有项目,TSVD都使用错误软件发布的原始测试用例来检测这些错误-如果使用TSVD,这些错误将在代码发布之前被捕获。对于雷击卡车,TSVD检测到一个不是原始错误报告一部分的TSV。

我们还评估了TSVD在所有测试用例中的性能。系统开销大多小于20%,与之前的性能结果一致。两个项目的开销很大,因为它们有许多短时间运行的测试(<1 ms)。他们测试的平均减速实际上不到400毫秒。

数据竞争检测 由于在我们的上下文中对错误报告的容忍度较低,因此我们不关注静态数据竞争检测技术[13、16、36、66]。如第1节和图2所述。

TSVD与动态主动数据竞争检测技术密切相关[47,58]。动态被动检测技术[19、48、57、60、65]在分析、锁集分析或两者的组合之前执行,以预测是否可能出现数据竞争。最近的工作[27,32,61]通过泛化在当前执行之前发生的超越执行来推断更多的数据竞争。这些技术支付了监视同步操作的运行时成本,还遭受误报[30、45、58]。有几种技术使用采样来减少运行时开销[5,31,42],但是像DataCollider[14]一样,它们需要多次重复运行测试以暴露错误。

另一种类型的被动检测工具,如AVIO[38]和Bugaboo[39]在运行时发现并发错误。由于它们不预测或暴露尚未显示的bug(TSVD是这样做的),因此它们不需要在关系发生之前进行分析,但也基本上不适合构建和测试环境TSVD目标。
研究了异步事件驱动程序(如Android应用程序和Web应用程序)的竞争检测[25、26、40、53]。在那里,关键的挑战是建模和分析异步请求和响应之间的因果关系,这会导致巨大的运行时延迟。相反,TSVD会自动推断发生在关系之前。虽然不是本文的重点,但TSVD背后的技术可以用于这些工作所针对的应用。

系统测试 系统测试技术通过驱动程序走向不同的可能交错来发现并发错误[6,7,21,22,24,35,43]。这些技术要么以需要覆盖某个界限内的所有交错为指导[21、22、35、43],要么以覆盖概念为指导[6、24],要么提供查找错误的概率保证[7]。虽然这些技术可以发现一般的并发错误,但它们并不是为了在少量的运行中发现大多数错误而设计的。相反,TSVD是专门为在前几次运行中查找tsv而设计的,并且不需要支付控制线程调度程序的成本。

生成单元测试 工具被提议用来合成单元测试,以帮助暴露库函数中的并发错误[9,49,54,55]。假定多线程库允许安全的并发调用,这些工具将合成并发方法调用序列,以帮助暴露库实现中的错误。它们与TSVD是正交的:TSVD通过对使用线程不安全库的软件进行现有的单元测试,专注于提高暴露线程安全违规错误的效率。

时序假设 Snorlax[29]利用粗交错假设在生产并发错误中复制和诊断。Snorlax实验表明,导致并发错误的事件之间经过的时间介于154到3505微秒之间,在此基础上,Snorlax可以在不进行细粒度监视和记录的情况下重现并发错误。这种粗略的交错假设和TSVD的未遂跟踪着眼于并发bug的时间窗口特性的不同方面-Snorlax相信时间窗口并不像人们过去想象的那么小,TSVD认为小窗口中的冲突访问更有可能导致真正的bug,并以不同的方式利用这些特性。

Causality inference 在系统性能分析[1,10]和网络依赖性分析[8]的背景下,以往的工作是使用运行时跟踪分析来推断消息发送/接收操作或分布式系统任务之间的关系。由于使用场景的不同,TSVD的精确推理算法与以前的工具有很大的不同。以前的工具都需要大量未受干扰的系统跟踪,统计推断发生在关系之前,这是基于两个操作从未翻转执行顺序[10]还是始终以[8]之间几乎恒定的物理时间间隔执行。与以前的工具不同,TSVD工作在独特的测试环境中,系统跟踪包含了TSVD引入的许多扰动;TSVD还面临着在少量运行中发现错误的独特目标,因此不能等到大量跟踪可用。因此,TSVD发生在基于观察每次测试运行中的延迟的唯一推理设计之前。

结论

提出了一种新的线程安全违规检测技术TSVD。作为集成的构建和测试环境的一部分,TSVD为使用复杂的多线程和异步编程模型以及多种同步机制的.NET程序提供了一个按钮式的非假漏洞错误检测。TSVD为探索主动测试和资源意识延迟注入设计的广阔设计空间提供了一个起点。未来的研究可以进一步探索如何平衡缺陷暴露能力、准确性和成本。