论文翻译：快速检测多变量原子性违规的轻量级方法

原文：C.-H. Bae, E. Choi, Y.-K. Jun, and O.-K. Ha, “Lightweight Method for On-the-fly Detection of Multivariable Atomicity Violations,” in 2023 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Dublin, Ireland: IEEE, Apr. 2023, pp. 165–171. doi: 10.1109/ICSTW58534.2023.00039.

摘要: 在多线程程序中测试检测实时并发错误（如由多个共享变量引起的原子性违规）具有挑战性，因为需要考虑各种因素，包括变量之间的相关性和访问事件交错。本研究提出了一种在程序执行过程中检测违反原子性的改进方法。该方法采用一种直接的方法，将构成原子性的大量相关变量识别为一个单独的组和一个变量。这种增强型方法与测试工具类似，并使用一组合成程序进行了实验比较，这些程序模拟了七个具有代表性的多变量原子性违规行为的执行过程。结果表明，与测试程序的原始运行和最先进的检测方法相比，执行时间分别增加了 1.07 倍和 1.05 倍。这一结果包括了先前方法未检测到的所有多变量原子性违规行为的检测精度。

I. 导言

并行或多线程程序中的同步是一种强制机制，用于协调各种计算系统中的线程执行和管理共享数据。然而，测试程序以发现由非功能事实（如线程同步）引起的并发错误（如违反原子性）是相当具有挑战性的，因为这需要各种知识和诀窍，如并发线程的交错预判定和共享资源的竞争分析。原子性违规是严重的并发错误之一， 当两个或多个线程同时在一个临界区域内执行时，程序员会认为该临界区域将实现原子性。特别是，如果在预期实现原子性的区域内，对共享变量的访问中至少包括一次写入，就必须对其进行测试和检测，以提高软件系统的可靠性，因为这样会满足竞赛条件，并产生意想不到的后果。

以往检测原子性违规行为的研究确定观察到的程序执行是否与串行执行或串行化相同。技术[1]-[4]与支持静态检测的技术相比，即时检测原子性违规的技术会产生更多的误报。但仍可能造成误报和漏报。此外，它们可能无法检测到由多个变量引发的违反原子性的情况，因为它们只考虑了单个变量，而没有分析预期原子执行的关键部分中共享变量之间的相关性。

本研究提出了一种轻量级方法，该方法改进了多线程程序执行过程中检测原子性违规的最先进方法–预期不变（AI）[5]算法，考虑了临界区域中组成原子执行的多个变量。所提方法的关键点在于通过将与原子操作相关的多个共享变量分组为一个共享变量来检测违反原子性的情况。原子性违规行为是通过分析共享变量在执行过程中发生的方法来诊断的，这种方法基于程序员所希望的共享变量的接近顺序，反映了通过执行前收集的共享变量的相关性。实验中使用了一组合成程序，模拟了实际应用中出现的七种原子性违规行为的执行过程，比较了所介绍方法的准确性和效率。在实验结果中，与预期不变量不同的是，使用我们的增强型方法的测试工具能正确检测出所有七种情况。此外，与原始执行测试程序相比，该工具平均需要 10.7 次执行时间，仅增加了 6.8%；与预期不变量相比，平均需要 1.05 次执行时间，仅增加了 4.9%，从而有效地检测了由多个变量引起的违反原子性的情况。

本文的其余部分安排如下：第 2 节介绍了多线程程序中的并发错误，以及以往检测原子性违规的研究。第 3 节介绍了即时检测方法的设计和操作。第 4 节介绍了拟议方法的实现和实验，第 5 节给出了结论和未来研究。

II. 背景介绍

A. 并发错误

基于共享内存的多线程程序可能会产生并发错误，例如数据竞赛和原子性。在程序执行过程中，由于并发线程对共享变量的访问同步不当而造成的并发违规。众所周知，这些并发错误主要是调试和测试多线程程序时的麻烦缺陷，因为并发线程的交错是非确定性的。

根据 S. Lu 等人的研究[1]，并发错误可分为死锁错误和非死锁错误。在该研究调查的现实世界应用程序中，约 66% 的错误属于非死锁错误，即同时对共享资源执行 线程操作（如数据竞赛和原子性违规）所导致的竞赛错误。数据竞赛是具有代表性的竞赛错误，当两个线程同 时访问单个共享变量时就会发生，包括在没有适当同步的情况下至少写入一次。违反原子性是指线程在原子代码区域内同时访问共享变量时，意外违反了原子性，从 而发生竞赛错误。

图 1 是一个在 Apache 应用程序中发生并发错误的示例 [6]。图 1 (a) 是由于在两个并发线程上接近共享变量而导致并发错误的代码区域。Content 和 Content_len 是共享变量，如果 Content 的内容发生变 化，Content_len（保存在 Content 中的值的长度）也要更新。图 1(b)是(a)中的执行图示，箭头表示线程操作，圆圈表示每个共享变量的访问事件，圆圈中的 W 和 R 分别 表示写入和读取访问事件。

图 1 中的执行潜藏着两个共享变量之间的数据竞赛，因为两个不同的线程在没有适当同步的情况下访问了两 个共享变量中的每一个。利用数据竞赛检测技术（如 “发 生前分析”），可以诊断出线程 1 中的 W 和线程 2 中 的 R 分别在两个共享变量之间存在两个数据竞赛。图 2 (a) 显示了通过对每个共享变量使用相同的锁进行同步以 保持预期的访问顺序来消除数据竞赛的结果。

在 Content_len 受不同锁保护的情况下，竞赛问题依然存在，因为在值更新前可能会发生读取。这是线程 1 中两个 变量的两次写访问事件违反了程序员所希望的原子性的结果。如图 2 (b)所示，通过使用包含两个共享变量的单 个相同锁来保持两个变量的原子性，可以轻松解决图 2 (a) 中的原子性违规问题。

B. 以往的研究

众所周知，由于线程交错，并发性错误（如违反原子性）很难重现，而且一般的软件测试方法也很难检测出顺序程序中的错误。因此，并发错误的检测需要基于错误诊断规则或协议的自动程序的帮助。在程序执行过程中检测违反原子性的技术分为基于还原的方法（REM）[7]-[9]、基于访问模式的方法（APM）[5]、[10]-[12]和基于发生关系的方法（HRM）[13]-[15]。REM基于 Lipton 的还原理论[16]，探索访问共享变量的事件的换向属性，并分析原子性，以确定和检测每个线程的访问事件序列是否与获取的执行中定义的模式相匹配。APM 通过分析交错共享变量的访问事件是否与定义的非序列化模式相匹配，来检测违反原子性的情况。最后，HRM 利用预期执行原子性操作的执行区域中访问事件之间的顺序关系，分析和检测共享变量访问事件的冲突。虽然这些即时检测违反原子性的方法比通过静态分析确定的方法更复杂，检测性能也更优越，但它们仍然会引起误报和漏报。

考虑到现有研究的准确性和开销，AI（预期不变性） [5] 是一种基于 APM 的适用于多线程程序的方法。该研究利用预测试信息诊断并发错误，如违反原子性，并通过停滞诊断出错误的线程来处理并发错误。AI 是 J. Yu 等 人[17]方法的改进版。作者将数据结构中每个内存操作的 顺序定义为 PSet（前置集）。因此，AI 同样将每条指令 的顺序定义为 RPre（远程前置集）和 BSet（归属集）。 RPre 收集与分析共享变量并发访问相关的指令（$I_x$）， 如访问类型（读/写）、访问ID、线程ID、代码中的位置和内存地址。RPre 根据指令($I_x$)按以下规则更新信息：

• 它访问的地址与 $I_x$ 相同。
• 它是在另一个线程中执行的，而$I_x$不属于这个线程。
• 包括 RPre($I_x$) 的 BSet 根据动态指令 ($D_x$) 收集满足以下 条件的静态指令 (S ) ：x
• 它访问的地址与 $D_x$ 相同。
• 它在另一个线程中执行，而 $D_x$ 不属于该线程。
• 在 $D_x$ 之前访问的 $S_x$ 会被执行并存储。