Butterfly analysis: adapting dataflow analysis to dynamic parallel monitoring
Butterfly analysis: adapting dataflow analysis to dynamic parallel monitoring
复制标题
DOI：
10.1145/1736020.1736050
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
Michelle L. Goodstein;Evangelos Vlachos;Shimin Chen;Phillip B. Gibbons;M. Kozuch;T. Mowry
中科院分区：
文献类型：
--
作者：
Michelle L. Goodstein;Evangelos Vlachos;Shimin Chen;Phillip B. Gibbons;M. Kozuch;T. Mowry
在线程序监视是检测运行中的应用程序中的错误和安全攻击的有效技术。扩展这些工具来监视并行程序是具有挑战性的，因为这些工具必须考虑线程间依赖和宽松的内存一致性模型。现有的工具假定顺序一致性，并且经常以数量级降低被监视程序的速度。在本文中，我们提出了一种新的方法，通过不依赖于强一致性模型或详细的线程间依赖跟踪来避免这些缺陷。相反，我们只假设所有线程上遥远过去的事件都是可见的；我们不假设（并避免了跟踪的开销）其他线程上最近事件的相对顺序。为了克服考虑最近事件之间所有可能顺序的潜在状态爆炸，我们将静态数据流分析（达到定义和达到表达式）的两种技术应用于动态并行监控的新领域。为了确保我们方法的正确性和效率，对这些技术进行了重大修改。我们将展示如何在两种流行的内存和安全工具中使用我们的适应性分析。我们证明了我们的方法不会遗漏错误，并且仅由于缺乏最近事件之间的相对顺序而牺牲精度。此外，我们对在硬件辅助日志平台上运行内存检查工具的一组Splash-2和Parsec 2.0基准测试进行了模拟研究，结果表明，用非常低的误报率来换取(i)减少开销和（ii）在宽松一致性模型上运行的能力的潜在好处。
Online program monitoring is an effective technique for detecting bugs and security attacks in running applications. Extending these tools to monitor parallel programs is challenging because the tools must account for inter-thread dependences and relaxed memory consistency models. Existing tools assume sequential consistency and often slow down the monitored program by orders of magnitude. In this paper, we present a novel approach that avoids these pitfalls by not relying on strong consistency models or detailed inter-thread dependence tracking. Instead, we only assume that events in the distant past on all threads have become visible; we make no assumptions on (and avoid the overheads of tracking) the relative ordering of more recent events on other threads. To overcome the potential state explosion of considering all the possible orderings among recent events, we adapt two techniques from static dataflow analysis, reaching definitions and reaching expressions, to this new domain of dynamic parallel monitoring. Significant modifications to these techniques are proposed to ensure the correctness and efficiency of our approach. We show how our adapted analysis can be used in two popular memory and security tools. We prove that our approach does not miss errors, and sacrifices precision only due to the lack of a relative ordering among recent events. Moreover, our simulation study on a collection of Splash-2 and Parsec 2.0 benchmarks running a memory-checking tool on a hardware-assisted logging platform demonstrates the potential benefits in trading off a very low false positive rate for (i) reduced overhead and (ii) the ability to run on relaxed consistency models.