AsyncClock: Scalable Inference of Asynchronous Event Causality
AsyncClock: Scalable Inference of Asynchronous Event Causality
复制标题
AsyncClock：异步事件因果关系的可扩展推理
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Gilles A. Pokam
中科院分区：
文献类型：
--
作者：
Chun;S. Narayanasamy;Essam Muhammad Idris Khan;C. Pereira;Gilles A. Pokam
异步编程模型通常用于移动的系统和Web 2.0环境中。与传统的数据竞争检测器相比，异步竞争检测器使用的算法具有数量级的性能和空间效率。我们解决这个问题，确定和解决两个重要的问题，在推理异步事件之间的因果关系。与传统的信号等待操作，建立两个异步事件之间的因果顺序是从根本上更具挑战性的，因为没有共同的句柄，他们operationon.We提出了一个新的原语命名为AsyncClock，明确地跟踪因果关系先前的事件，解决了这个问题，并显示AsyncClock可以处理各种各样的异步因果关系模型。我们还解决了重要的可扩展性问题，有效地识别继承人的事件，其元数据可以回收。我们使用我们的算法构建了第一个单通道、非基于图的Android竞赛检测器，并将其应用于20个流行应用程序中查找错误。我们的工具产生了大约6倍的性能开销，比最先进的解决方案效率高出数倍。它还可以很好地扩展执行长度。我们使用我们的工具找到了147个以前未知的有害种族。
Asynchronous programming model is commonly used in mobile systems and Web 2.0 environments. Asynchronous race detectors use algorithms that are an order of magnitude performance and space inefficient compared to conventional data race detectors. We solve this problem by identifying and addressing two important problems in reasoning about causality between asynchronous events. Unlike conventional signal-wait operations, establishing causal order between two asynchronous events is fundamentally more challenging as there is no common handle they operate on. We propose a new primitive named AsyncClock that addresses this problem by explicitly tracking causally preceding events, and show that AsyncClock can handle a wide variety of asynchronous causality models. We also address the important scalability problem of efficiently identifying heirless events whose metadata can be reclaimed. We built the first single-pass, non-graph-based Android race detector using our algorithm and applied it to find errors in 20 popular applications. Our tool incurs about 6x performance overhead, which is several times more efficient than the state-of-the-art solution. It also scales well with the execution length. We used our tool to find 147 previously unknown harmful races.