Adversarial memory for detecting destructive races
Adversarial memory for detecting destructive races
复制标题
用于检测破坏性种族的对抗性记忆
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Stephen N. Freund
中科院分区：
文献类型：
--
作者：
C. Flanagan;Stephen N. Freund
众所周知，多线程程序容易出现竞争条件，广泛采用具有复杂内存模型和缓存一致性协议的多核处理器加剧了这个问题。先前的许多工作都集中在种族检测的静态和动态分析上，但是这些算法通常无法区分导致错误行为的破坏性种族和不会导致错误行为的良性种族。手动执行这种分类非常困难、耗时且容易出错。
Multithreaded programs are notoriously prone to race conditions, a problem exacerbated by the widespread adoption of multi-core processors with complex memory models and cache coherence protocols. Much prior work has focused on static and dynamic analyses for race detection, but these algorithms typically are unable to distinguish destructive races that cause erroneous behavior from benign races that do not. Performing this classification manually is difficult, time consuming, and error prone.
This paper presents a new dynamic analysis technique that uses adversarial memory to classify race conditions as destructive or benign on systems with relaxed memory models. Unlike a typical language implementation, which may only infrequently exhibit non-sequentially consistent behavior, our adversarial memory implementation exploits the full freedom of the memory model to return older, unexpected, or stale values for memory reads whenever possible, in an attempt to crash the target program (that is, to force the program to behave erroneously). A crashing execution provides concrete evidence of a destructive bug, and this bug can be strongly correlated with a specific race condition in the target program.
Experimental results with our Jumble prototype for Java demonstrate that adversarial memory is highly effective at identifying destructive race conditions, and in distinguishing them from race conditions that are real but benign. Adversarial memory can also reveal destructive races that would not be detected by traditional testing (even after thousands of runs) or by model checkers that assume sequential consistency.