Optimistic Hybrid Analysis: Accelerating Dynamic Analysis through Predicated Static Analysis
Optimistic Hybrid Analysis: Accelerating Dynamic Analysis through Predicated Static Analysis
复制标题
乐观混合分析：通过预测静态分析加速动态分析
DOI：
10.1145/3173162.3177153
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Narayanasamy, Satish
中科院分区：
文献类型：
--
作者：
Devecsery, David;Chen, Peter M.;Flinn, Jason;Narayanasamy, Satish
动态分析工具，如检测数据竞争、验证内存安全性和识别信息流的工具，已经成为测试和调试复杂软件系统的重要组成部分。虽然这些工具功能强大，但它们的缓慢速度往往限制了它们在实践中的部署效率。混合分析通过使用静态分析来减少在动态分析期间执行的工作，从而加快了这些工具的速度。在这篇文章中，我们认为，当前的混合分析不必要地受到一个不正确的假设的阻碍，即保持动态分析的合理性需要潜在的健全的静态分析。我们观察到，即使在不合理的静态分析的情况下，也有可能对落入静态考虑的状态集合内的执行实现合理的动态分析。这将我们引向一种新的方法，称为乐观混合分析。我们首先分析一小部分执行，并生成一组在大多数(但不一定是所有)执行中都成立的可能不变量。接下来，我们应用更精确的静态分析，假定这些不变量成立。最后，我们推测性地运行生成的动态分析，同时验证假设的不变量在特定执行期间是否成立；如果不成立，则使用传统的混合分析重新执行程序。乐观混合分析与传统的动态分析一样精确和可靠，但通常要快得多，因为(1)不可靠的静态分析可以比可靠的静态分析更快地加速动态分析，以及(2)验证很少失败。我们将乐观混合分析应用于种族检测和程序切片，在经过传统混合分析优化的最先进的种族检测器(FastTrack)上实现了1.8倍的性能，在混合反向切片器(GIRI)上实现了8.3倍的性能。
Dynamic analysis tools, such as those that detect data-races, verify memory safety, and identify information flow, have become a vital part of testing and debugging complex software systems. While these tools are powerful, their slow speed often limits how effectively they can be deployed in practice. Hybrid analysis speeds up these tools by using static analysis to decrease the work performed during dynamic analysis. In this paper we argue that current hybrid analysis is needlessly hampered by an incorrect assumption that preserving the soundness of dynamic analysis requires an underlying sound static analysis. We observe that, even with unsound static analysis, it is possible to achieve sound dynamic analysis for the executions which fall within the set of states statically considered. This leads us to a new approach, calledoptimistic hybrid analysis.We first profile a small set of executions and generate a set of likely invariants that hold true during most, but not necessarily all, executions. Next, we apply a much more precise, butunsound,static analysis that assumes these invariants hold true. Finally, we run the resulting dynamic analysis speculatively while verifying whether the assumed invariants hold true during that particular execution; if not, the program is reexecuted with a traditional hybrid analysis. Optimistic hybrid analysis is as precise and sound as traditional dynamic analysis, but is typically much faster because (1) unsound static analysis can speed up dynamic analysis much more than sound static analysis can and (2) verifications rarely fail. We apply optimistic hybrid analysis to race detection and program slicing and achieve 1.8x over a state-of-the-art race detector (FastTrack) optimized with traditional hybrid analysis and 8.3x over a hybrid backward slicer (Giri).
登录
查看更多内容
DOI：
10.1007/978-3-642-27940-9_18
发表时间：
2012
期刊：
Proceedings of 30th Annual International Symposium on Microarchitecture
影响因子：
--
作者：
Johannes Kinder;Dmitry Kravchenko
通讯作者：
Dmitry Kravchenko
价值剖析
DOI：
10.1109/micro.1997.645816
发表时间：
1997
期刊：
Proceedings of 30th Annual International Symposium on Microarchitecture
影响因子：
--
作者：
B. Calder;P. Feller;A. Eustace
通讯作者：
A. Eustace
静态检查的不变推理：
DOI：
10.1145/587051.587054
发表时间：
2002
期刊：
ACM Trans. Softw. Eng. Methodol.
影响因子：
--
作者：
Jeremy W. Nimmer;Michael D. Ernst
通讯作者：
Michael D. Ernst
JavaScript 实用混合污点分析
DOI：
--
发表时间：
2013
期刊：
International Symposium on Software Testing and Analysis
影响因子：
--
作者：
Shiyi Wei;B. Ryder
通讯作者：
B. Ryder
BigFoot：用于动态种族检测的静态检查位置
DOI：
10.1145/3062341.3062350
发表时间：
2017
期刊：
Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation
影响因子：
--
作者：
Dustin Rhodes;C. Flanagan;Stephen N. Freund
通讯作者：
Stephen N. Freund