0 引言

随着多线程并发程序的广泛应用，并发程序的测试变得越来越重要。变异测试^[1-2]作为一种基于故障植入的测试方法，通过对被测程序的符号或语句进行简单修改以植入故障，以此来评估测试用例检测这些植入故障的能力。并发变异测试是将变异测试应用到多线程并发程序中，通过并发变异算子对多线程并发程序植入并引发并发故障，用来评估并发程序测试用例，检测并发故障的能力。目前，并发程序变异测试研究还处于起步阶段，主要集中在并发变异算子的研究方面。例如: Bradbury等^[3]针对Java(J2SE 5.0)并发特性，设计了25种变异算子，但是并没有通过实验对提出的变异算子进行分析评价; Wu等^[4]则认为已有的变异算子存在一定的局限性，不能生成一些细微的并发故障，甚至一些变异算子可能无法产生任何变异体, 为此，他们通过组合已有的一阶变异算子给出了6种二阶变异算子，并验证了其二阶变异算子确实能够生成一些一阶变异算子不能生成的并发故障; Gligoric等^[5]根据变异体的数目和变异得分对一阶变异算子进行了评估，即根据变异体是否被杀死，分析变异算子的有效性，但没有评估生成的变异体引发特定并发故障的情况。

综上所述，目前在并发程序变异测试的研究中，对并发变异算子生成的变异体只是依据检测到其植入故障的测试用例数对变异体进行评估，没有对生成的变异体引发数据竞争、死锁等常见并发故障的能力进行分析评价；且并发变异算子大都根据等待集、并发方法调用等结构特性设计，因而其触发数据竞争并发故障的能力较低。针对特定并发故障的特性，进行变异策略研究，设计有针对性的并发变异算子，可以使此类故障得到快速有效的检测。

数据竞争故障是常见的一类并发故障，多个线程对共享数据的读写访问不当时，会导致软件行为异常甚至造成系统崩溃。本文针对数据竞争故障，分析已有并发变异算子触发数据竞争故障的能力，在此基础上，结合数据竞争故障的特性，给出了针对数据竞争故障的变异策略，从并发变异算子设计的角度出发，探讨面向锁对象的变异策略(Lock-oriented Mutation Strategy，LMS)和面向共享变量的变异策略(Shared-variable-oriented Mutation Strategy，SMS)，设计重置同步锁(Synchronized Lock Resting Operator, SLRO)和移出共享变量操作(Move Shared Variable Operator, MSVO)两个并发变异算子。从变异点选取的角度出发，给出了一种同步关系对的变异点选取策略(Synchronized relationship pair Mutation Point Selection Strategy，SMPSS)，以提高新设计的并发变异算子触发数据竞争故障的能力。

本文选取12个并发程序作为被测程序，采用SLRO和MSVO变异算子，对SMPSS选取出的变异点进行变异体生成，以此来检测SLRO和MSVO并发变异算子触发数据竞争故障的能力。结果显示，SLRO和MSVO算子分别生成了121和122个有效变异体，有效性分别达到95.28%和99.19%。

本文的主要贡献有：1)给出通过变异算子触发有效并发故障来评估变异算子有效性的方法；2)从变异算子设计的角度出发，通过分析数据竞争故障的特征，给出了面向锁对象的变异策略(LMS)和面向共享变量的变异策略(SMS)，设计了SLRO和MSVO并发变异算子; 3)从变异点选取的角度出发，给出了一种同步关系对的变异点选取策略(SMPSS), 应用新设计的并发变异算子针对SMPPS选取出的变异点进行变异，生成变异体，使得新设计的并发变异算子能有效触发数据竞争故障; 4)实验验证了新设计的变异算子能有效触发数据竞争故障，能较好地评估测试用例检测数据竞争故障的能力。

1 数据竞争故障与同步机制

并发程序的多个线程执行存在不确定性，即多次执行同一并发程序，因线程的调度序列不同，程序的执行结果可能不同。如果并发程序中线程的调度序列不当，可能会导致并发程序出现死锁^[6]、原子性违反^[7]和数据竞争等并发故障。

数据竞争故障^[8-9]是指多个并发执行的线程同时访问某一块内存，并且这些访问中至少有一个是写操作时，对共享数据的不当操作而引发的数据读写错误。

为保证并发程序多个线程对共享数据的有序访问，不会对共享数据造成破坏，并发程序引入了同步机制^[10]。同步语句是同步机制的具体体现，其作用的范围称为同步语句的作用域，具体而言，是指从同步语句获取锁对象到释放锁对象的语句范围。例如，图 1所示的Java并发程序，线程T1中Synchronized(G)为一个同步语句，其中G为锁对象，其作用域为a7~a11。不同线程之间通过共用一个锁对象来保证对共享变量的互斥访问，即当有多个线程都要访问某个共享数据时，只有获得锁对象G的线程才能对共享数据进行操作，其他线程则需要等待。

多线程并发程序对共享变量的操作可分为读操作和写操作两种。为保证对共享变量读写的正确，通常将共享变量的读写操作置于同步语句的作用域中。例如，图 1程序中，线程T1对共享变量V2的写操作处于同步语句a7的作用域范围a7~a11内。为此定义同步关系对如下。

定义1 同步关系对。对于两个属于不同线程而锁对象相同的同步语句，若这两个同步语句没有特定的先后执行顺序，其作用域中分别存在对同一个共享变量的访问操作，且其中至少有一个为写操作，则称这两个同步语句为一个同步关系对。

例如，图 1所示程序中，共用一个锁对象L1的同步语句a1、b1分别属于T1、T2线程，a1和b1之间没有特定的先后执行顺序，且对共享变量V1的写/读操作分别处于a1和b1的作用域内，则a1和b1构成一个同步关系对。而对于同步语句a1、a4，虽然其作用域内分别存在对变量V1写/读操作，但由于a1、a4属于同一线程T1，存在特定的执行顺序，因此，a1和a4不属于同步关系对。

多个同步语句之间可能存在嵌套结构，即一个同步语句存在于另一个同步语句作用域范围内，为此定义嵌套同步关系对如下。

定义2 嵌套同步关系对。存在由两个同步语句(A和B)构成的一个同步关系对，且同步语句A、B分别处于另外两个持相同锁对象的同步语句(C和D)的作用域中，则称同步语句A、B为嵌套同步关系对。

例如，图 1程序中，a8和b5为一个同步关系对，且a8和b5分别处于持相同锁对象G的同步语句a7和b4的作用域中，则a7(a8)和b4(b5)构成一个嵌套同步关系对。

2 面向锁对象的变异策略

面向锁对象的变异策略从变异算子设计的角度出发，针对同步语句锁对象的特征，设计相应的变异操作，使得新设计的变异算子能有效触发数据竞争故障。具体而言，并发程序中，不同线程之间通过共用一个锁对象来保证对共享变量的互斥访问。若对同步语句中的锁对象进行重新设置，则可能致使多个线程同时访问共享变量，打破线程原有的访问顺序，从而导致程序引发数据竞争故障。为此，本文设计了一种重置同步锁(SLRO)并发变异算子，针对同步语句中的锁对象，通过对其进行重置，使多个线程对共享变量的互斥访问限制被打破。原本只有一个线程能获取锁对象并对共享变量进行读写操作，其他线程则只能等待其执行完毕后，才能获得锁对象。当锁对象被重置后，一个线程在对共享变量进行读写操作时，其他线程也可以获得锁对象，对共享变量进行操作。当多个线程同时对共享变量进行访问时，可能致使共享变量发生读写错误，引发数据竞争故障。

因此，重置锁SLRO变异算子操作如下：

1) 对于同步语句中能直接被重置的锁对象，则在同步语句作用域内对锁对象进行重置，并将重置语句置于共享变量读/写操作前。同时，若同步语句作用域中存在Wait、Notify等线程操作消息原语时，为使得SLRO变异算子生成的变异体只引发数据竞争故障而不导致程序崩溃，将重置锁对象的操作语句置于线程操作消息原语语句之后。

2) 若同步语句中的锁对象(如This锁、类锁等)不能直接进行重置，则先用能直接被重置的锁对象(如对象锁)将其替换后，再按操作1)中的规则进行锁对象重置。

3) 对于嵌套关系同步语句，由于同步语句嵌套的限制，为打破多个线程互斥访问的限制，使得多个线程能同时对共享变量进行操作，需要对嵌套同步语句中的内、外层同步语句同时按照操作1)和2)进行锁对象重置。

例如，图 1所示并发程序P中的同步语句a1和b1，其作用域内分别存在对共享变量V1的写/读操作，同步语句a1和b1分别属于线程T1和T2。假定并发程序P对变量V1的访问应为先写后读，即线程T1先获取到同步语句a1中的锁对象L1，并在完成对共享变量V1的写操作后释放L1，线程T2再获取锁对象L1，对V1进行读操作，线程调度序列为a1-a2-a3-b1-b2-b3。应用重置锁对象SLRO并发变异算子对线程T1中的同步语句进行变异，对其锁对象进行重置，如线程T1中使用L1=new L1()重置锁语句，生成的变异体如图 2所示，则变异体程序在执行时，至少存在一种调度序列a1-a2-b1-b2-b3-a3-a4，使变异体程序发生数据读写错误，引发数据竞争故障。具体分析如下：

线程T1执行语句a1-a2，在图 2的SLRO变异体中，线程T1获得同步语句的锁对象L1，对其进行了重置操作后，准备对共享变量V1进行写操作(图 2中的虚线a3-v1)时，线程切换，线程T2开始执行。

线程T2执行语句b1-b2-b3，由于T1对锁对象L1的重置操作，打破了线程T1和T2互斥访问共享变量V1的限制，使得T2能够在T1持有锁对象L1后还能再次获得L1，从而进一步对共享变量V1进行读操作，导致程序对变量V1的读操作语句b2先于写操作语句a3执行。然后发生线程切换，线程T1执行。

线程T1执行语句a3-a4，线程T1对共享变量V1执行写操作后，释放锁对象L1。

由以上分析可知，原本线程T2应读取到线程T1对变量V1进行写操作后的数值v1(图 2中的虚线v1-b2)，但实际读取到的是T1进行写操作前的数值v(图 2中的实线v-b2)。因此，线程T1和T2对共享变量V1的操作发生了读写错误，引发数据竞争故障。

对于含有嵌套结构的同步语句，如图 1所示并发程序P中的嵌套同步语句a7(a8)和b4(b5)，其作用域内分别对共享变量V2进行写/读操作，其中嵌套同步语句a7(a8)、b4(b5)分别属于线程T1和T2。假定并发程序P对共享变量V2的访问应为先写后读，即线程T1先获取锁对象G和L2，在完成对共享变量V2的写操作后释放了G和L2，线程T2再获取锁对象G和L2，对V2进行读操作，线程调度序列应为a7-a8-a9-a10-a11-b4-b5-b6-b7-b8。使用重置锁SLRO变异算子对线程T1中的嵌套同步语句a7(a8)进行变异，即对同步语句a7和a8的锁对象G和L2同时进行重置，如使用G=new G()和L2=new L2()重置锁语句，生成的变异体如图 3所示，则变异体程序在执行时，至少存在一种调度序列a7-a8-a9-a10-b4-b5-b6-b7-b8-a11-a12-a13，使变异体程序对共享变量V2的读操作语句b6先于写操作语句a11执行。

原本线程T2应读取到T1对V2进行写操作后的数值v2(图 3中的虚线v2-b6)，但实际读取到的是T1进行写操作前的数值v(图 3中的实线v-b6)。因此，线程T1和T2对共享变量V2的操作发生了读写错误，引发数据竞争故障。

3 面向共享变量的变异策略

面向共享变量的变异策略针对同步语句作用域中的共享变量，设计相应的变异操作，使得新设计的变异算子能有效地触发数据竞争故障。具体而言，为保证对共享变量读写的正确性，并发程序对共享变量的操作语句置于同步语句作用域内。多个线程对共享变量的访问操作只能按照一定的次序进行。若将共享变量的读写操作语句从同步语句作用域中移出，那么多个线程对共享变量的访问操作将会失去限制，可能致使多个线程同时访问共享变量，从而引发数据竞争故障。为此，本文设计了一种移出共享变量操作(MSVO)并发变异算子，即对同步语句作用域中共享变量的读写操作语句，将其移出到同步语句作用域范围之外，使共享变量的读写操作失去同步语句的保护，致使多个线程可以实现不经同步语句直接对共享变量进行访问。当线程按不恰当的调度序列访问共享变量时，使得对共享变量的读写操作发生错误，引发数据竞争故障。

移出共享变量MSVO变异算子的具体操作如下：

1) 若共享变量读写操作的语句位于同步语句作用域的首部或尾部时，则直接将共享变量的读写操作语句移出到同步语句的作用范围之外。

2) 若共享变量的读写操作语句位于同步语句作用域的中间位置时，为使原程序语句顺序不改变，则将同步语句的作用域分为两部分，分别由作用域开始到共享变量读写操作语句和该读写语句到作用域尾组成，并由相同的同步语句控制。

3) 对于嵌套同步语句，则将共享变量的读写操作语句直接移到嵌套的最外层同步语句作用域之外。

例如，同样对于图 1所示并发程序P中的同步语句a1和b1。假定并发程序P对变量V1的访问应为先写后读，线程调度序列为a1-a2-a3-b1-b2-b3。采用移出共享变量操作MSVO变异算子对线程T2中共享变量V1的读操作语句进行变异，将其从同步语句作用域中移出，生成的变异体程序如图 4所示，则变异体程序在执行时，至少存在一种调度序列b1-b2-a1-b3-b4-b5-a2-a3，使得数据读写发生错误，引发数据竞争故障。具体分析如下：

线程T2执行语句b1-b2，在图 4的MSVO变异体中，线程T2获得同步语句的锁对象L1，执行其他语句后释放了L1。此时线程发生切换，线程T1开始执行。

线程T1执行语句a1，线程T1获得同步语句中的锁对象L1，准备对共享变量V1执行写操作时(图 4中的虚线a2-v1)，线程切换，T2执行。

线程T2执行语句b3-b4-b5，在MSVO变异体中，由于共享变量V1的读操作语句被移出同步语句作用域之外，失去同步语句的保护，使得线程T2可以直接对共享变量V1进行读操作，导致程序对共享变量V1的读操作语句b3先于写操作语句a2执行。再次发生线程切换，线程T1执行。

线程T1执行语句a2-a3，线程T1对共享变量V1执行写操作后，释放锁对象L1。

从上述分析可知，原本线程T2应读取到T1对共享变量V1进行写操作后的数值v1(图 4中的虚线v1-b3)，但实际读取到的是T1写操作前的数值v(图 4中的实线v-b3)。因此，线程T1、T2对共享变量V1的操作发生了读写错误，引发数据竞争故障。

对于含有嵌套结构的同步语句，同样对于图 1并发程序P中嵌套同步语句a7(a8)和b4(b5)。假定并发程序P对共享变量V2的访问应为先写后读，线程调度序列应为a7-a8-a9-a10-a11-b4-b5-b6-b7-b8。使用移出共享变量操作MSVO变异算子对线程T2中共享变量V2的读操作语句进行变异，将其移出到外层同步语句作用域之外，生成的变异体程序如图 5所示，则变异体程序在执行时，至少存在一种调度序列b4-b5-b6-b7-a7-a8-b8-a9-a10-a11，使得变异体程序对共享变量V2的读操作语句b8先于写操作语句a9执行。

原本线程T2应读取到T1对变量V2进行写操作后的数值v2(图 5中的虚线v2-b8)，但实际读取到的是T1写操作前的数值v(图 5中的实线v-b8)。因此，线程T1和T2对共享变量V2的操作发生了读写错误，引发数据竞争故障。

4 基于同步关系对的变异点选取策略

变异点选取指的是变异体生成之前，通过分析数据竞争故障与同步语句之间的关系，选取能导致数据竞争故障的变异点。采用并发变异算子针对选取出的变异点生成变异体，以提高并发变异算子触发数据竞争故障的能力。

数据竞争故障是由多个线程对共享变量操作不当引起的。两个线程对共享变量的读写操作组合有读写、写写、写读和读读。除了读读外，当两个线程以其他三种方式对共享变量进行操作时，若操作不当，则导致并发程序引发数据竞争故障。并发程序将对共享变量的操作置于同步语句作用域内，根据两个同步语句作用域中对共享变量进行读写操作的访问方式，可以将这两个同步语句组合成：读写同步对、写写同步对、写读同步对和读读同步对，其中读读关系不会导致数据竞争故障。由同步关系对的定义可知，同步关系对是指读写同步对、写写同步对和写读同步对。针对同步关系对中的同步语句进行变异，生成的变异体程序可能会引发数据竞争故障。因此，基于同步关系对的变异点选取策略(SMPSS)即为选取出并发程序中的同步关系对。在此基础上，应用LMS和SMS变异策略生成变异体。

为了获得并发程序同步语句与共享变量之间的关系，能快速选取出并发程序中的同步关系对，本文设计了一种能体现同步语句与共享变量访问关系的同步关系图(Synchronized Relationship Graph, SRG)，然后通过对SRG的遍历，选取并发程序中的同步关系对，以此作为变异点。同步关系对的变异点选取策略的基本流程如下：

1) 使用静态分析方法获取并发程序的相关信息，如线程数、线程包含的同步语句集合和共享变量集合等。

2) 构造并发程序同步关系图SRG。

3) 根据同步关系对变异点选取算法SMPSA遍历图中同步语句与共享变量之间的关系，选取出并发程序中的(嵌套)同步关系对，以此作为变异点。

4.1 同步关系图

同步关系图(SRG)用来描述并发程序中不同线程对共享变量的读/写操作关系，表示为SRG=〈N, E〉，其中节点N代表并发程序中所有的共享变量和同步语句，又分为共享变量节点和同步语句节点，边E代表并发程序中同步语句间的执行和共享变量的读/写访问操作，又分为执行边Ee和读/写边Er/Ew。

1) 共享变量节点。表示并发程序中被各个线程访问的共享变量，在同步关系图中使用实线圆形表示。例如，图 1所示的程序P中的V1共享变量，在同步关系图 6中使用V1标识的实线圆形表示。

2) 同步语句节点。表示并发程序中的同步语句，在同步关系图中使用实线矩形表示，并记录有同步语句的锁对象信息。例如，图 1程序P中T1线程的同步语句a1，在同步关系图 6中使用带锁对象L1标识的实线矩形表示。若同步语句之间存在嵌套结构，除了在外层同步语句节点处记录自身锁对象信息外，还在内层同步语句节点记录有相同的锁对象信息，并且内层同步语句用虚线矩形表示。如图 1程序T1线程的嵌套同步语句a7(a8)的锁对象为G和L2，在同步关系图 6中，内层同步语句a8记录的锁对象信息为(G, L2)，同时采用虚线矩形表示。

3) 执行边。表示不同的同步语句之间被线程调用的先后次序，用带箭头的实线表示。若同步语句S(A)在程序中先于S(B)被线程调用执行，则从同步语句节点S(A)到节点S(B)之间存在一条执行边，记作Ee〈S(A), S(B)〉。例如，图 1程序P中T1线程的同步语句a1和a4，a1先于a4执行，因此，在同步关系图 6中，存在一条从同步语句节点a1到a4节点的执行边Ee〈a1, a4〉。

4)读/写边。表示并发程序同步语句作用域范围内共享变量的读写操作语句，用带箭头的虚线表示，即若对共享变量V的写操作处于同步语句S(A)的作用域范围内，则从同步语句节点S(A)到共享变量节点V之间存在一条写操作边，记作Ew〈S(A), V〉。若同步语句S(B)的作用域中存在对变量V的读操作语句，则从同步语句节点S(B)到共享变量节点V之间存在一条读操作边，记作Er〈S(B), V〉。例如，图 1程序中，同步语句a1和a4的作用域内分别存在对变量V1进行写和读操作语句，则在同步关系图 6中，同步语句a1与变量V1之间存在一条写操作边Ew〈a1, V1〉，a4与V1之间存在一条读操作边Er〈a4, V1〉。

对于一个并发程序P，其同步关系图可按如下步骤构建：

1) 确定SRG的节点。针对并发程序P，使用静态分析可获得其线程集合TS、线程包含的同步语句集合SS、共享变量集合VS，以此确定其共享变量节点和同步语句节点。

2) 确定SRG的执行边Ee。在同步语句集合SS={S₁, S₂, …, S_k}中，各个同步语句的出现顺序代表其被线程调用的先后次序。通过一个线程的同步语句集合可获得属于该线程的执行边集合EeS={〈S₁, S₂〉, 〈S₂, S₃〉, …, 〈S_k-1, S_k〉}。依次分析所有线程调用同步语句的次序，便可得到SRG中的所有执行边Ee。

3) 确定SRG的读/写操作边Er/Ew。通过共享变量和同步语句的信息找到其在程序中的具体位置，确定同步语句作用域中存在的共享变量，并通过共享变量操作语句确定其读/写操作，以此获得读/写边集合ErS/EwS。依次考虑所有线程的同步语句，便可得到SRG中的所有读/写操作边Er/Ew。

例如，根据以上描述步骤，对于图 1中的程序P，随机选择线程T1作为开始，通过分析可知，T1中包含4个依次执行的同步语句a1、a4、a7和a8。因此，这4个同步语句节点之间分别存在一条执行边Ee〈a1, a4〉、Ee〈a4, a7〉和Ee〈a7, a8〉。其中同步语句a7、a8存在嵌套关系，因此a8节点用虚线矩形表示，并在节点处记录同步语句a7的锁对象G。此外，由于同步语句a1、a8的作用域内分别存在对共享变量V1、V2的写操作，a4作用域内存在对共享变量V1的读操作。因此，在同步语句节点a1、a8和共享变量节点V1之间分别存在一条写操作边Ew〈a1, V1〉、Ew〈a8, V1〉，同步语句节点a4与变量节点V1之间存在一条读操作边Er〈a4, V1〉。同理，线程T2、T3中的同步语句之间存在执行边Ee〈b1, b4〉和Ee〈b4, b5〉，同步语句节点和共享变量节点之间存在读操作边Er〈b1, V1〉、Er〈b5, V2〉和Er〈c1, V1〉，最终得到并发程序P的同步关系图，如图 6所示。

4.2 同步关系对变异点选取算法

多线程并发程序P的同步关系图中包含了线程集合TS、线程中的同步语句集合SS、共享变量集合VS等信息，通过对SRG的遍历，可以选取出并发程序中的同步关系对和嵌套同步关系对，即并发程序中能触发数据竞争故障的变异点。同步关系对变异点选取算法(SMPSA)如算法1所示，算法以同步关系图SRG作为输入，以同步关系对集合和嵌套同步关系对集合为输出。具体步骤如下：

1) 选择SRG中的一个线程作为开始，根据线程t的同步语句集合，找到线程t执行的第一个同步语句。

2) 如果同步语句A的作用域中存在对某一共享变量的写操作边，则优先遍历写操作边，通过写操作边找到该共享变量节点，依次遍历其读/写操作边(属于其余线程)，找到相应的同步语句B。根据同步语句节点上的信息，对比A、B中的锁对象，若A、B中的锁对象相同，则将同步语句A、B置于同步关系对集合；若同步语句A、B属于嵌套同步语句，且内、外层同步语句的锁对象都分别相同，则将A、B置于嵌套同步关系对集合。

3) 如果同步语句A中存在多条写操作边，则需要按照步骤2依次进行遍历。

4) 当同步语句A中的写操作边被遍历完全，则通过线程t的执行边找到下一个同步语句B，按照步骤2、3的方式进行遍历。以此类推，直到遍历完该线程的所有同步语句。

5) 最后，通过步骤1、2、3和4依次遍历同步关系图中的所有线程，得到并发程序中的同步关系对集合和嵌套同步关系对集合，即选取出程序中能触发数据竞争故障的变异点。

算法1 同步关系对变异点选取算法。

输入 同步关系图SRG;

输出  (嵌套)同步关系对集合。

TS, SS, VS, EeS, EwS, ErS ← GetInformation (SRG)

//根据SRG获得TS、SS和VS等集合

SBSet=∅, NSBSet=∅//初始化(嵌套)同步关系对集合为空

WHILE(TS≠∅) DO          //存在未被遍历的线程

  tp ← RandomSelertThread(TS)           //随机选取线程

  WHILE(SS≠∅) DO      //线程tp的同步语句集合不为空

    S_i ← GetSynchronized(EeS, SS)

    WHILE(EwS(S_i, Vj)≠∅) DO       //写边集合不为空

      Ew〈S_i, Vj〉 ← GetEw(EwS〈S_i, Vj〉)

      Vj← GetSharedVariable(Ew〈S_i, Vj〉)

      WHILE(ErS〈S_k, Vj〉≠∅ OR EwS(S_k, Vj〉≠∅) DO

        //变量Vj的读/写集合不为空。

        S_k ← GetSynchronized (Er〈S_k, Vj〉 OR Ew(S_k, Vj〉)

//通过共享变量获取同步语句

        IF(S_i(Lock)==S_k(Lock))

          //若两个同步语句的锁对象相同

          SBSet.add(S_i, S_k)

        END IF

        IF(S_i(Lock1, Lock2)==S_k(Lock1, Lock2))

          //若两个同步语句的内、外层锁对象都相同

          NSBSet.add(S_i, S_k)

        END IF

      END WHILE

    END WHILE

  END WHILE

END WHILE

例如，对于图 6所示的同步关系图，不失一般性，选择线程T1作为开始线程，其第一个同步语句为a1，通过a1节点与共享变量节点V1之间写操作边Ew〈a1, V1〉获得变量V1，依次遍历变量V1的所有读/写操作边(不属于线程T1)，得到同步语句b1和c1。由于共用了锁对象L1的同步语句a1和b1分别属于不同的线程，a1和b1之间不存在特定的先后执行顺序，且在a1的作用域内存在对变量V1的写操作，在b1的作用域内存在对变量V1的读操作，因此a1和b1构成一个同步关系对。同理可知，a1和c1构成一个同步关系对。

算法继续沿执行边Ee〈a1, a4〉遍历到同步语句a4，其存在一条读取操作边Er〈a4, V1〉。由于a4作用域内没有对共享变量的写操作，继续根据执行边Ee〈a4, a7〉和Ee〈a7, a8〉遍历到同步语句a8，其作用域中存在共享变量V2的写操作语句。通过写操作边Ew〈a8, V2〉获得节点变量V2，遍历V2的所有读/写操作边(属于其余线程)，得到同步语句b5。同步语句a8和b5构成一个同步关系对，且a8和b5分别位于另外两个含有相同锁对象G的同步语句a7和b4的作用域范围内。因此，嵌套同步语句a7(a8)和b4(b5)属于嵌套同步关系对。以此类推，遍历线程T2和T3中的同步语句，最终可得到并发程序P的同步关系对集合{(a1, b1)，(a1, c1)}和嵌套同步关系对集合{[a7(a8), b4(b5)]}。

5 实验

为进行数据竞争故障变异测试相关实验研究，本文采用了ASM类技术在开源变异测试工具Javalanche^[11]上进行二次开发，使得其可以实现并发变异算子对并发程序的故障植入，生成变异体程序。实验还借助JPF(Java Path Finder)^[12]--一种Java字节码模型检验工具来分析生成的变异体引发数据竞争故障的能力。为验证本文给出的数据竞争故障变异策略的有效性，定义变异算子有效性度量公式如下：

$ 变异算子的有效性 = \frac{{变异算子生成有效变异体数}}{{变异算子生成变异体的总数}} $

(1)

其中能引发数据竞争故障的变异体称为有效变异体。为进一步对数据竞争故障变异测试进行研究，本文拟从以下几个研究问题进行实验研究：

1) 已有的变异算子触发数据竞争故障的能力如何？变异算子的有效性又如何？

2) 面向锁对象SLRO变异算子和面向共享变量MSVO变异算子触发数据竞争故障的能力如何？有效性如何？

3) 同步关系对的变异点选取策略(SMPSS)是否能有效地提高新设计变异算子触发数据竞争故障的能力？

4) SLRO和MSVO并发变异算子生成的变异体是否能有效地对测试用例进行评估？

5.1 实验环境与对象

实验从Java SIR库中选取了12个并发测试普遍使用的并发程序作为基准^[13-14]，相关信息如表 1所示。其中:P表示被测程序名称，Loc表示被测程序的代码行数，PF为程序功能，TCs表示测试用例数。在12个被测程序中，Pool与Log4j程序是两个规模较大的真实Apache开源程序。实验在Window7环境下运行，基本配置为：Intel Core i5-2400 CPU 3.10 GHz、4 GB内存、64位操作系统，JPF版本为V6。

5.2 已有变异算子有效性分析

实验选出14个占主导地位的并发变异算子在12基准被测并发程序(表 1)上进行变异，并通过JPF工具来检测生成的变异体程序能否引发数据竞争故障，以此来分析已有并发变异算子的有效性。

实验结果表明，14个已有变异算子中能生成能引发数据竞争故障的变异体只有4个，有效性从高到低依次排列为：RSB、RSK、SHCR、MSP，其余10个变异算子没有生成有效变异体。表 2和3中给出了这4个变异算子在12个被测程序上生成变异体的情况(空格表示相对应的地方没有数据, 下同)，其中:VM表示有效变异体数，IM表示无效变异体数，Eff表示变异算子的有效性，空表示对应的选项没有变异体生成。14个已有变异算子中RSB变异算子的有效性最高，对12个被测并发程序共生成了168个变异体，其中能触发数据竞争故障的变异体为92个，变异算子的有效性为54.76%。其余三个变异算子的有效性都低于50%。特别是MSP变异算子，生成的变异体数目较多，对12个被测程序共生成了173个变异体，但有效变异体只有39个，有效性只有22.54%。

上述实验结果显示，已有的大部分变异算子不能引发数据竞争故障，即使少数能引发数据竞争故障的并发变异算子，其触发数据竞争故障的能力也较低。

5.3 基于LMS与SMS的数据竞争故障触发能力分析

为分析重置同步锁SLRO变异算子和移出共享变量操作MSVO变异算子触发数据竞争故障的能力，实验以相同的12个Java并发程序作为被测程序，采用SLRO、MSVO变异算子对12个并发程序进行变异，借助JPF工具检测生成的变异体是否能引发数据竞争故障，并计算变异算子的有效性。

实验结果如表 4所示，SLRO、MSVO变异算子在12个被测程序上分别生成了160和132个变异体，有效性分别为80.63%和92.43%。其中，SLRO变异算子对9个被测程序都生成了有效变异体，算子的有效性除了Buffer程序的66.67%外，对其余8个被测程序的SLRO算子有效性都超过了80%。MSVO算子对8个被测程序的算子有效性都超过了90%。特别对于实际的大型Apache开源程序Pool和Log4j，SLRO算子生成有效变异体的数目分别为65和46；MSVO算子生成有效变异体的数目分别为68和39。综上所述，新设计的SLRO和MSVO变异算子能有效地触发数据竞争故障。

5.4 基于SMPSS的数据竞争故障能力分析

应用SLRO与MSVO变异算子对12个被测程序进行变异，变异算子的有效性都超过了80%，但还是生成了部分无效的变异体。这是由于SLRO与MSVO变异算子没有对变异点有选择地生成变异体程序，因此导致了无效变异体的生成。为此，实验应用SMPSS策略对被测程序的变异点进行选取，仅在选取出的变异点上应用SLRO和MSVO算子进行变异，并分析SLRO和MSVO算子触发数据竞争故障的能力。

实验结果如表 5所示，SLRO和MSVO变异算子在12个被测程序上分别生成了127和123个变异体，有效性分别达到了95.28%和99.19%。通过对比表 5的实验结果得知，应用SMPSS指导SLRO和MSVO变异算子进行变异操作，对12个被测并发程序分别少生成了33和9个变异体，没有生成的42个变异体中，有效变异体有8个，无效变异体有34个；MSVO算子没有生成的9个变异体都属于无效变异体。由此可知，SMPSS策略能有效地提高变异算子触发数据竞争故障的能力，SLRO和MSVO算子的有效性分别从80.63%、92.43%提高到了95.28%、99.19%。

并发程序变异测试通过并发变异算子对多线程并发程序植入故障，以此来评估并发程序测试用例集检测并发故障的能力。因此，为对比应用SMPSS策略前后，SLRO和MSVO变异算子生成的变异体是否能有效地对测试用例集进行评估。实验首先应用SMPSS指导SLRO和MSVO变异算子对7个存在实际数据竞争故障的被测程序进行变异，然后采用生成的有效变异体去评估测试用例，并筛选出能检测到这些有效变异体的测试用例。最后，采用筛选出来的测试用例去检测7个被测程序中真实存在的22个数据竞争故障，以此分析变异算子评估测试用例的效果。

实验结果如表 6和7所示，其中:RF表示实际故障数，VM为生成的有效变异体数，STCs为有效变异体筛选出的测试用例数，DF表示测试用例检测到的故障数，RFD为故障检测率(DF/RF)。由实验结果可知，SLRO、MSVO变异算子对7个被测程序分别生成了119、120个有效变异体。采用这些有效变异体对测试用例进行评估，筛选出能检测到有效变异体的测试用例数分别为235和247。对于22个实际数据竞争故障，SLRO、MSVO变异算子筛选出的测试用例能检测到的故障数分别为20和19，故障检测率分别为90.91%和86.36%。由此可知，应用SMPSS指导SLRO、MSVO变异算子生成的变异体能有效地评估测试用例集。

由表 4与表 5可知，应用SMPSS策略后SLRO变异算子少生成了8个有效变异体。因此，为了分析SMPSS是否会影响变异算子评估测试用例的效果，实验选取这8个有效变异体对测试用例进行评估，使用筛选出来的测试用例检测实际的数据竞争故障。实验结果如表 8所示，通过这8个有效变异体筛选出来的测试用例检测出1个实际数据竞争故障，但此故障属于表 7中检测出的20个实际故障之一。由此可知，SMPSS在不影响SLRO和MSVO变异算子评估测试用例效果的同时，能有效地减少无效变异体的生成。

为进进行对比实验，本文选取了14个已有变异算子中有效性最高的RSB变异算子进行实验。实验结果如表 9所示，针对22个实际的数据竞争故障，RSB变异算子筛选出的测试用例能检测到的故障数为14，故障检测率只有63.64%。

6 结语

针对并发程序数据竞争故障变异测试，本文通过12个被测程序分析了已有变异算子触发数据竞争故障的能力。在此基础上，针对数据竞争故障的特性，给出了面向锁对象的变异策略、面向共享变量的变异策略和基于同步关系对的变异点选取策略，分别从变异算子设计和变异点选取这两个方面来提高并发变异算子触发数据竞争故障的能力。

实验结果表明，已有的变异算子大部分不能触发数据竞争故障，即使是少数能触发数据竞争故障的并发变异算子，其触发数据竞争故障的能力也较低。新设计的面向锁对象SLRO和面向共享变量MSVO变异算子能有效地触发数据竞争故障，变异算子的有效性分别为80.63%和92.43%。应用SMPSS策略后，SLRO和MSVO变异算子的有效性分别提高到了95.28%和99.19%，且SLRO、MSVO变异算子生成的有效变异体能较好地评估测试用例检测数据竞争故障的能力，为数据竞争故障变异测试提供有力支持。