增加数据竞争检测效率的混合算法

梁帅帅 李兰英

摘  要：针对多线程程序同时读写同一块内存产生的数据竞争，已有的检测方法漏检率和误检率较高，文章结合静态RELAY法和动态Eraser锁集法，利用数据流的静态法对共同锁集的判断和动态法对共同锁集的保护，有效地降低误检率和漏检率。为减少因重复交织出现的冗余，提出使用重复检测器减少重复检测的数据竞争，提升了检测性能，降低了检测开銷。

关键词：数据竞争;动静态检测;重复检测器

中图分类号：TP311.5      文献标识码：A 文章编号：2096-4706（2020）17-0069-03

Abstract：In view of the data competition generated by multi-threading programs reading and writing the same memory at the same time，the existing detection methods have high miss detection rate and false detection rate. This paper combines the static RELAY method and dynamic ERASER lock set method，uses the static method of data flow to judge the common lock set and the dynamic method to protect the common lock set，so as to effectively reduce the false detection rate and missed detection rate. In order to reduce the redundancy caused by repeated interleaving，the use of duplicate detector to reduce the data competition of repeated detection is proposed，which improves the detection performance and reduces the detection overhead.

Keywords：data race;dynamic and static detection;repetitive detector

0  引  言

程序中并发性bug越来越多，常见的bug有四种类型：死锁、数据竞争、原子性违背和顺序违背。数据竞争指在非线程安全的情况下，多线程对同一个地址空间进行写操作，需花费大量时间进行调试和修复，很多学者提出了很多检测方法，静态检测方法主要使用RELAY[1]、Locksmith、RacerX等;本文所述动态检测主要使用锁级法、先发生于算法。

因很难确定程序操作实际影响到哪些内存、被访问的值是局部范围还是全局范围、是否通过参数传递到函数中，RELAY、Locksmith等方法能调用上下文敏感分析来确定访问内存的实际位置，但每个位置上持有哪些锁，程序操作获取和释放了哪些锁，这些锁是否有可能通过参数传入的结构派生而来的都无法确定。RELAY、Locksmith等方法在两个不同访问处，锁持有的锁集的交集进行判断是否为可疑数据竞争。Flanagan等人的先发生于算法提出更新时钟向量，通过时钟向量状态判断相关读写访问信息。

为提升并发缺陷相关方向的效率，降低漏检和误检率，加强程序的正确性和可操作性，校内相关国家自然基金课题也对并发缺陷数据竞争进一步研究，根据学者提出的算法，本人进行复现、改进。研究时基于数据流分析和锁集REALY方法，先进行上下文敏感分析，计算函数相对锁集和保护访问集，然后判断相关锁集是否有交集，再使用Eraser[2]方法对相关锁集进行保护，如果有可疑的数据竞争将被进行删除，随后再根据检测过程中检测出的可疑竞争所在位置的程序段进行分步骤重复检测，本文动静结合检测方法减少了动态检测的漏检率和静态检测的误检率，并解决了一些数据竞争重复检测的问题。在检测并发缺陷后，使用重复检测器再一次进行筛选，时间、空间开销会有所减少。

1  FPX的算法描述

首先静态RELAY法对符号执行的局部和全局传入值跟踪内存位置中包含的值，使用元变量x∈X表示局部和全局，符号值的集合V表示符号分析计算的值，整数init（x）是x的局部值;must（x）表示一个必须指向x的值;may（x）表示一个可能指向x中的任何左值。符号执行跟踪每个程序点上的符号映射，并使用函数更新这个符号映射。简单赋值x：= e的函数，将当前映射中的e计算为一个符号值，然后更新映射中的x。对于通过指针进行的赋值，也就是?x：=e，函数将x计算为一个符号值v1，将e计算为一个符号值v2，存储中更新哪些x取决于值v1。

锁集的结果存储为XLock（f）∈L，表示函数末尾的相对锁集。将锁和解锁操作为锁集函数调用，修改锁集函数调用e（a）。lock（l）函数为（{l}，{ }）的相对锁集摘要，unlock（l）函数为（{ }，{l}）的相对锁集摘要，相对锁集产生的摘要表从开始执行到返回的锁集中的变化。查找调用f后的相对锁集，将更新后的锁集信息传入的相对锁集[3]。锁集分析完成对给定函数的所有程序点的相对锁集的计算，保护访问使用这些信息来计算函数执行的保护访问集合。保护访问集合是一个triple a=（x，L，k），x值被访问，l∈L是当前锁的访问，k代表锁的类型即读锁或写锁;访问设置更新（s，L）。

当处理完函数中的所有语句后，最后的保护访问集将成为函数的访问摘要。最终能计算出该线程的入口函数的保护访问集，对于共享变量v的来自不同线程T1和T2的2个保护访问（o，，k）和（o′，，k′），其中，o是左值被访问，L+是进程所获取的锁的集合，L-是进程所释放的锁的集合。获取保护它们的锁集的交集，如果交集为空，则这2个访问就构成一个可疑的数据竞争。使用静态检测的数据竞争误检率高，所以使用动态检测降低误检率，如下述使用Eraser锁集算法动态检测在静态检测锁集和保护访问集结果的基础上对共享变量的保护访问应受到共同锁集的保护，并不断更新锁集向量时钟[4]的信息，通过线程调度发现真实数据竞争，然后剔除数据竞争，从而降低误检率。

Eraser lockset algorithm

Input：thread t's lock set and sharevarable v's candidate lock set

Output：null or a race warning

Let Lt be the set of locks held by thread t;

For each shared variable v，CL（v） stands v's candidate locks

namely the set of locks consistently protecting v.Initially， CL（v） is set to be all locks;

Let prev be the previous access to v before the current access to v.Initially，prev is nil;

Let mode（x）be a map from access x to its type，namely READ or WRITE;

foreach access a to v by thread t do

CL（v）←CL（v）∩Lt;

if CL（v）=0&&！（mode（a）=READ&&mode

（prev）=READ） then

return a race warning（v，prev，a）;

return;

算法检测后有大量的数据竞争重复检测，在上述动静态检测后加一个检测器，来过滤重复检测，描述如下：检测器由多个步骤组成，最重要的步骤是预测步骤和验证步骤。预测步骤检查动态的执行，基于动态检测模式预测潜在的重复数据竞争;验证步骤主动控制线程调度[5]，验证许多重新执行中的数据竞争。第一步可能会产生许多重复的数据竞争，给第二步带来许多重复的新执行，这将影响并发性数据竞争检测的效率。在第一步中预测潜在的竞争（两个数据竞争），如果S1->S3->S2之间的潜在竞争已经被检测，则无需再次检测S1->S3和S3->S2之间的其他两个潜在竞争。比如S1-> S3->S2的实例iS1->iS3->iS2表示两个线程之间的三个内存访问事件，S1->S3的实例iS1->iS3表示两个线程之间的两个内存访问事件，而实例iS1->iS3无需检测，因为另一iS1->iS3->iS2已经包含了这个实例。如果S1->S3和S3-> S2在检测时没有进行重复检测，那么效率会得到明显提高。检测器算法描述如下：

Dynamic detector after Eraser detect Event 1、Event 2、Event 3.

Let detect the set of lock by FPX

For search Datarace in the set lock and detect repeat

If search （Event 1—>Event 3）∩（Event 1—>Event 2—> Event 3） = Event 1—> Event 3

Return Event 1—>Event 2—>Event 3

Break repeat lock

Elseif Event 2—>Event 3∩（Event 1—> Event 2—>Event 3） = Event 2—> Event 3

Return Event 1—>Event 2—>Event 3

Break repeat lock

Return Event 1—>Event 2—>Event 3

2  实验结果分析

RELAY算法能检测数据竞争，误检率高，但相对于一般检测方法漏检率低，检测出程序中的数据竞争即报错。针对误检问题动态使用Eraser锁集算法，因对锁集的时钟向量信息不断更新，最终获取时钟信息判断数据竞争，因此误检率较低。

对相关论文重新实现了这些检测工具和算法。对比实验在同一环境下进行，保证了实验结果具有可比性。对FPX、RaceChecker和RaceFuzzer进行验证，结果如表1所示，其中前三列表示检测工具RaceChecker、FPX、RaceFuzzer检测出的数据竞争对数目，RC、FPX、RF表示RC和FPX、RaceFuzzer检测过程中的潜在可疑的数据竞争对数。为评测和对比分析FPX对目标程序的性能影响，在fft、lu、radix等程序上分别运行来检测验证RaceFuzzer[6]、RaceChecker和FPX。

表2是在动静态检测方法检测前的重复数据竞争数量和使用重復数据竞争检测器检测后的数据竞争数量对比表，其中检测工具检测程序5 000行左右，在检测器下，检测重复数据竞争前和检测重复数据竞争后的数据对比。

为了更能清晰地看出重复检测器检测效率的提升，如图1所示，没有检测前的数据竞争数量和使用重复检测器后的数据竞争的数量效率对比，在多种检测方法下，针对三种不同的检测器重复检测出的数据竞争数目有所减少，开销效率提升4%，但还存在一些问题有待继续研究，例如检测器检测的数据竞争，在必要条件非常高的时候，有检测器的开销是否比没有检测器的开销还要大。