一种基于调用链的Java程序数据竞争静态检测算法＊

宋东海 陈二虎

（1.92493部队88分队 葫芦岛 125001）（2.92515部队 葫芦岛 125001）

1 引言

随着多核技术的出现和GUI程序的广泛应用，为有效利用计算资源，提高系统效率，而广泛采用并发程序设计。虽然Java编程语言为编写多线程程序提供了强大的语言支持，但是编写正确高效的多线程并发程序仍然比较困难。在多线程程序中，当两个线程在无时序约束的情况下访问同一内存位置并且至少有一个是写访问时，就会导致数据竞争［1］。粗粒度的保守机制可以避免数据竞争，但与此同时可能会产生死锁，并发多线程编程导会致许多特定的优化和检错问题。高效、精确的竞争检测对于提高软件可靠性，增强系统的稳定性具有重要意义。

2 Java数据竞争检测

2.1 竞争检测技术研究现状

按照竞争检测的时机，数据竞争检测可分为竞争动态检测、竞争静态检测。竞争动态检测主要有基于发生序（happen－before order）［2～3］、基于锁集（lock－set）［4～5］以及其混合方法［6～7］，采用插桩技术能获得变量和别名的准确信息，准确捕获共享内存访问的发生序和锁集信息，几乎不产生误报（false－positive），但依赖于程序输入，只分析与程序执行路径有关的代码，会漏报（false－negative）一些真正的数据竞争并且开销很大。竞争静态检测是程序编译时或者编译后对源程序或者目标代码进行检测，需要分析整个程序，不像动态竞争检测，无需插桩，不需占用程序的运行时间，不受程序规模限制。但因静态分析的不可判定性［8］，对于任何一个有一定规模的软件，希望获得关于它的完备描述通常是不现实的［9］，往往采用不完备的近似算法，静态分析的结果比较保守。

由于并发程序中线程调度的不确定性，精确的数据竞争检测是一个NP－hard［1］问题，数据竞争很难被发现和重现，并且数据竞争不像死锁，不会导致程序的突然失效，无法继续运行，大量的误报会使得使用者对静态分析工具失去信心和耐心。含有数据竞争错误的程序调试是非常困难的，为了提高分析精度，减少误报，便于调试程序，有必要提高数据竞争静态检测的精度。

2.2 Java内存模型

内存模型描述的是程序中变量（实例域、静态域、数组元素等）之间的关系，以及在实际计算机系统中将变量存储到内存和从内存取出变量的底层细节。

JMM（Java memory model）是JVM的内存模型，规范了线程之间通过内存的交互原则。JMM定义了一个统一的内存管理模型，屏蔽了底层平台内存管理细节，具体由各个虚拟机来实现对内存的动态管理，包括对内存的分配以及回收。JMM将线程能访问的内存分为主内存（main memory）与工作内存（working memory），Java中所有类实例域、静态域、数组都储存在主内存中，对于所有线程都是共享的。每个线程都有自己的工作内存，工作内存中保存的是主内存中某些变量的拷贝和临时变量，线程内对所有变量的操作都是在工作内存中进行，线程之间无法相互直接访问，变量传递均需要通过主内存完成，数据竞争只可能出现在主内存变量上。

2.3 Java语言数据竞争静态检测

Java程序竞争静态检测主要有流非敏感的类层次型约束的系统，流敏感的基于锁集合算法的静态检测，路径敏感的模型检测器。Choi［10］等人将竞争检测分成一系列分析阶段，包括逃逸分析阶段、别名分析阶段、竞争检测阶段。在此基础上斯坦福Naik［11］等人提出了一种K－对象敏感、上下文敏感Java程序竞争静态检测算法，算法分为五个阶段：1）可达竞争对检测（originalRaces）；2）别名竞争对检测（aliasingRaces）；3）逃逸竞争对检测（escapingRaces）；4）并发竞争对检测（paralleRaces）；5）未加锁竞争对检测（unlockedRaces）。该算法随着各阶段的进行，逐渐缩小检测范围，采用了自适应 K－对象敏感（k－object－sensitive）的上下文信息，提高了静态分析的精度。张昱［7］等人基于即时编译器（just－in time，JIT）采用增量式竞争检测技术，提高了竞争检测的精度。

2.4 并发程序静态切片

程序切片作为一种对程序结构进行分析的技术，可以用在程序信息分析方面，从而增强对程序的理解、调试、测试和确认。1993年，J.Cheng［12］最早考虑了并发程序的静态切片，并提出了一种基于程序依赖网（PDN）的并发程序切片方法。1998年，J.Krinke［13］针对多线程程序提出了一种新的静态切片算法，引入了线程控制流图、线程程序依赖图，同时提出了线程证据的概念，用来描述多线程程序的执行路径。对程序的分析主要考虑程序数据依赖和控制依赖关系。Ranganath［14］于2003年又提出了并发程序干扰依赖（Interference Dependence）和现成依赖（Ready Dependence）的概念。2007年，戚晓芳［15］提出了线程交互可达图，构建了以程序状态和语句二元组为节点的并发程序依赖图。随着Java等语言并发程序的应用越来越多，多线程程序的分析、调试、测试比传统单线程程序更复杂。并发程序切片工具可以使并发程序的理解和维护等工作更容易完成。

3 类层次的Java竞争静态检测算法（Class－lever DC）

虽然竞争静态检测作为一种有效的数据竞争检测方法，但是竞争静态检测受到线程交互、动态数据分配、别名信息、流信息、路径信息、数组元素的影响，很难有精确的实现。为了提高检测竞争检测的有效性并且方便程序理解，需要对竞争静态检测的结果进行确认，但是对数据竞争结果进行确认费时费力。

本文将竞争静态检测技术和静态程序切片技术结合起来，提出了一种类层次的Java数据竞争静态检测算法。该算法首先以函数调用链为上下文信息对类域进行分析，找出可能数据竞争，然后通过对函数调用链静态切片分析，并结合数据竞争的必要条件，去掉不可能数据竞争。

3.1 数据竞争必要条件

用五元组（t，p，v，e，ls）表示线程t在程序点p 对变量v进行访问e（e为读r或写w），ls表示在程序点p变量v访问时拥有的锁集，如果线程t在程序点p对变量v进行访问e时，v没有被锁保护，则ls为∅。数据对（t1，p1，v1，e1，ls1），（t2，p2，v2，e2，ls2）为数据竞争的必要条件：

1）t1≠t2；

2）alias（v1，v2）＝true；

3）程序点p1、p2处对变量v1、v2的访问语句能够并发执行，不具有发生序；

4）e1，e2至少一个为写操作；

5）∀l1∈ls1，∀l2∈ls2，alias（l1，l2）＝false（v1，v2在程序点p不被同一别名锁保护）。

3.2 竞争检测算法描述

Narayanasamy［16］发现程序中的绝大部分数据竞争是无害的。通过对Java并发程序进行分析，可以发现产生数据竞争的类是非常少的，需要更加重视频繁使用以及更值得关注的类，因此本文提出了类层次的Java程序数据竞争静态检测算法。

3.2.1 类层次的Java数据竞争静态检测算法

类层次的Java程序数据竞争静态检测算法包含两个部分：类层次数据竞争预测部分和以函数调用链的数据竞争确认部分。

类层次的Java程序数据竞争静态检测算法：

类层次的Java程序数据竞争静态检测算法的数据竞争预测部分对一个类的每个字段进行分析，找出一对可能产生数据竞争的程序语句。记一个待分析类的字段集合F（包含实例字段和静态字段）、函数集合M，启动线程集T（T表示启动线程集合，包含main函数和start函数启动的线程。满足关系；T＝｛（［］，main）｝∪｛（o，start）｝），字段操作E（E＝｛r，w｝），函数调用链L（L为 m1－m2－m3…mn－1mn，表示函数 mn调用 mn－1，…，m3调用 m2，m2调用m1），则函数m中对字段f操作记为f－e－m∈F×E×M，线程t中调用函数m记为m－l－t∈M×L×T。因此f－e－m－l－t∈F×E×M×L×T表示线程t以l为调用链的方法m内对类字段f进行e操作，用OP表示这些操作的集合。

如图1所示，我们从类Class的代码中可以获得类的F×E×M集合，从程序函数调用图中可以获得M×L×T集合。根据数据竞争必要条件4），利用笛卡尔积运算可以计算待分析类上的数据竞争〈f－w／r－m1－l1－t1，f－wm2－l2－t2〉。

图1 数据竞争预测

图2 数据竞争确认

如图2所示，〈f－e－m1－l1－t1，f－e－m2－l2－t2〉表示一个可能的数据竞争对，以函数调用链的数据竞争确认部分对类层次的数据竞争预测部分产生的数据竞争进行确认。通过MHP（可能并行执行）分析［17］，根据数据竞争必要条件3）去掉不能并发执行的语句对；通过TLO（线程局部对象）分析［18］，根据数据竞争必要条件1）去掉不能被多个线程访问变量的语句对；最后进行别名锁分析，根据数据竞争必要条件2）和5），更进一步对竞争结果进行确认，判断两个引用变量是否可能别名，如果不可能的话，则说明不可能产生数据竞争。如果两个引用变量可能别名，则在此基础上判断它们是否被相同锁保护，如果被同一锁保护，则说明对共享变量的访问被同步保护，不会产生数据竞争，否则说明可能产生数据竞争。

3.2.2 算法分析

A和B为待分析的两个类，其中类A有字段f1，类B有字段f2，类B上的可能数据竞争对记为〈B.f2－e－B.mi－l1－t1，B.f2－e－B.mj－l2－t2〉，类B 的函数mi访问（直接或间接）类A的字段f1，类B的函数mj访问（直接或间接）类A的字段f1，因此，类A上的可能数据竞争对可以记为〈A.f1－e－A.mp－mp＋1－…－B.mi－l1－t1，A.f1－e－A.mq－mq＋1－B.mj－l2－t2〉。消除类A 上数据竞争〈A.f1－e－A.mp－mp＋1－…－B.mi－l1－t1，A.f1－e－A.mq－mq＋1－B.mj－l2－t2〉的同时可以消除与之关联的类B上的数据竞争〈B.f2－e－B.mi－l1－t1，B.f2－e－B.mj－l2－t2〉，即消除一个类上的数据竞争同时可以消除与之有关联类上的相应数据竞争。类A上的函数相对于类B上的函数处于函数调用链的底层，类层次的数据竞争算法预测部分以类为基础对程序进行数据竞争预测，使得我们可以根据类之间的关系来安排类上数据竞争检测的顺序，可以首先分析类层次较低的类（一般它的函数处于函数调用链的底层）或者更需要关注的类（程序中频繁使用的类或对任务关键的类）。

在以函数调用链为上下文的数据竞争确认部分，利用数据竞争的必要条件，对以类为层次的数据竞争预测部分产生的可能数据竞争进行确认，逐步求精，最后可以获得较精确的数据竞争检测结果，但由于静态程序分析的不可判定性，由于是根据数据竞争的必要条件进行判断，检测结果有一定的误报率。

可以通过对程序中的每个类执行一次算法，就会获得整个程序的数据竞争。并且以函数调用链为上下文，缩小了程序分析的范围，易于理解竞争出现的原因，让程序员关注函数调用链上的代码，便于指导修复程序中的竞争缺陷。

4 竞争检测实例分析

本节将通过一个Java多线程程序实例详细介绍了竞争静态检测原型工具的分析执行过程。以附录1程序进行实例分析。我们对类A进行分析，首先获得F＝｛f4｝，M＝｛A.init，A.set，A.get｝（其中init为类的构造函数），F－EM＝｛f4－r－A.get，f4－w－A.init，f4－w－A.get｝。

从附录1程序的函数调用图中可以获得M－L－T＝｛A.get－B.get－T.main，A.get－B.get－T.run，A.set－B.set－T.main，A.init－B.init－T.main，A.set－B.set－T.run｝，为了方便后面阐述，F－E－M－L－T记为：

防疫部门应加大对疫情的监测力度，并制定一套完善的疫情预警报告制度，时刻留意牧区羊群的生长状况。一旦发现存在疑似感染小反刍兽疫病的羊只，应在第一时间内进行隔离，待其恢复健康后，才能继续同群饲养。因此，积极做好对牧区疫情的监测工作是控制小反刍兽疫病毒肆意传播的重要举措。

①f4－r－A.get－B.get－T.main；②f4－r－A.get－B.get－T.run；

③f4－w－A.set－B.set－T.main；④f4－w－A.init－B.init－T.main；⑤f4－w－A.set－B.set－T.run（其中⑤属于多个线程）

如表1所示，对于可能竞争〈①，⑤〉，通过对调用链①，⑤分析，调用链①，⑤分别对v1.v8.f4（即同一内存快）进行读写，并且他们没有被锁保护，会产生数据竞争。

表1 竞争详细信息

如表2所示，可以对类层次生成的其他可能数据竞争进行分析。

表2 竞争检测

通过对调用链②，③分析，v2，v7属于别名，并且被别名锁（v2，v7）保护，则不会产生数据竞争。对于可能竞争〈②，④〉，通过对调用链②，④分析，调用链②先于④执行，他们不会产生数据竞争。对于可能竞争〈②，⑤〉，通过对调用链②，⑤分析，调用链②，⑤分别对v1.v8.f4，v2.v8.f4进行读写，但是v1，v2属于不同对象，则不会产生数据竞争。对于可能竞争〈③，⑤〉，通过对调用链③，⑤分析，调用链③，⑤分别对v1.v8.f4，v2.v8.f4进行读写，但是v1，v2属于不同对象，则不会产生数据竞争。对于可能竞争〈④，⑤〉，通过对调用链④，⑤分析，调用链④先于调用链⑤执行，则不会产生数据竞争。对于可能竞争〈⑤，⑤〉，调用链⑤，⑤分别对v1.v8.f4（即同一内存快）进行读写，并且他们没有被锁保护，会产生数据竞争。

表3 竞争检测结果

同理，对类B，T进行分析，可以获得整个程序的数据竞争。通过对每个类进行分析，我们发现类A〈①f4－r－A.get－B.get－T.main，⑤f4－w－A.set－B.set－T.run〉上的数据竞争与类B〈①f3－r－B.get－T.main，⑤f3－w－B.set－T.run〉上的数据竞争是有关联的，实际上是由于对类B的A类型实例字段f3的访问导致的。可以通过对类A的访问进行保护，消除类A，类B上的数据竞争。同理可以消除类T的数据竞争。

5 结语

数据竞争不会导致程序的突然失效，而未受到开发人员的重视，虽然现在的数据竞争检测主要是以动态竞争检测为主，但是由于静态竞争检测不需要对运行程序进行插装，不会影响系统运行。随着静态竞争检测技术分析结果精度的不断提高，静态竞争检测越来越受到重视。本文通过引入切片技术，提出了一种类层次基于调用链的Java数据竞争静态检测算法。通过实例分析，发现类之间的数据竞争是有关联的，对一个类进行修改，不仅可以消除这个类上的数据竞争，还能消除与之有关联的类上的部分数据竞争。实例表明，该算法是可行的，我们对整个程序进行数据竞争检测分析，可以首先对待分析的各个类按照使用频率和重要程度进行排序，然后对各个类进行数据竞争检测，由于各个类上的数据竞争是有关联的，并且对于修复程序中的竞争缺陷具有指导意义。下一步可以进一步研究类之间的关系与其上数据竞争分布的规律，安排类之间竞争检测的顺序，在保证软件质量的同时，尽可能的节约测试成本。

［1］Netzer R H B，Miller B P.What are race conditions？some issues and formalizations［J］.ACM Letters on Programming Languages and Systems，1992，1（1）：74－88.

［2］Adve S V，Hill M D，Miller B P，et al.Detecting data races on weak memory systems［C］／／Proceedings of the 18th Annual International Symposium on Computer Architecture（ISCA'91）.Toronto，Canada，1991：234－243.

［3］Christiaens M，Brosschere K.TRaDe：A topological approach to on－the－fly race detection in Java programs［C］／／Proceedings of the 1st Java Virtual Machine Research and Technology Symposium（JVM'01）.Monterey，California，USA，2001：105－116.

［4］Agarwal R，Sasturkar A，Wang L，et al.Optimized run－time race detection and atomicity checking using partial discovered types［C］／／Proceedings of the 20th IEEE／ACM International Conference on Automated Software Engineering（ASE 2005），Long Beach，USA，November，2005：233－242.

［5］Cheng G，Feng M，Leiserson C，et al.Detecting data races in Cilk programs that use locks［C］／／Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures（SPAA'98），Puerto Vallarta，Mexico，1998：298－309.

［6］Yu Y，Rodeheffer T，Chen W.RaceTrack：Efficient detection of data race conditions via adaptive tracking［C］／／Proceedings of the 20th ACM Symposium on Operating Systems Principles（SOSP'05），Brighton，United Kingdom，2005：221－234.

［7］张昱，郝允允.Java程序数据竞争的增量式检测［J］.西安交通大学学报，2009，43（8）：22－27.

［8］Landi W.Undecidability of static analysis［J］.ACM Letters on Programming Languages and Systems，1992，1（4）：323－337.

［9］梅宏，王千祥，张路，等.软件分析技术进展［J］.计算机学报，2009，32（9）：1697－1710.

［10］Choi J D，Loginov A，Sarkar K.Static datarace analysis for multithreaded object－oriented programs［R］.IBM Research：Technical Report RC22146，2001.

［11］Naik M.Effective static race detection for java［D］.Stanford University，2008.

［12］Cheng J.Slicing concurrent program s－A graph theoretical approach［C］／／The First International Workshop on Automated and Algorithmic Debugging.Link ping，Sweden，1993：223－240.

［13］Krnke J.Static slicing of threaded programs［J］.ACM SIGPLAN Notices，1998，33（7）：35－42.

［14］Ranganath V P，Hatcliff J.Slicing concurrent Java programs using Indus and Kaveri［J］.International Journal on Software Tools for Technology Transfer（STTT），2007，9（5－6）：489－504.

［15］戚晓芳，徐宝文，周晓宇.一种基于程序可达图的并发程序依赖性分析方法［J］.电子学报，2007，35（2）：287－291.

［16］Narayanasamy S，Wang Z，Tigani J，et al.Automatically classifying benign and harmful data races using replay analysis［C］／／Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation（PLDI）.San Diego，California，USA，2007：22－31.

［17］Li L.A practical MHP information computation for concurrent Java programs［D］.Montreal，Canada：McGill University，2004.

［18］Halpert R.Static lock allocation［D］.Montreal，Canada：McGill University，2008.

附录1：Java多线程样例程序EX1（该程序出自文献［1］Naik M的学位论文第13页）