Demanded abstract interpretation
Demanded abstract interpretation
复制标题
要求抽象解释
DOI：
10.1145/3453483.3454044
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Sridharan, Manu
中科院分区：
文献类型：
--
作者：
Stein, Benno;Chang, Bor-Yuh Evan;Sridharan, Manu
我们考虑的问题，使表现力的静态分析器交互。正式的静态分析作为一种验证和错误查找工具越来越广泛地被采用，但即使有强大的云基础设施，在代码更改后也可能需要几分钟或几小时才能获得批分析结果。虽然现有的技术为某些类别的分析提供了一些需求驱动或增量方面，但我们所面临的根本挑战是为任意抽象解释器做这两件事。我们的技术，需要抽象的解释，电梯程序语法和分析状态的动态演变的图形结构，在该程序编辑，客户端发出的查询，和评估的抽象语义都是统一对待。我们的方法解决的关键困难是一般的增量计算技术的应用程序的复杂，循环依赖结构引起的抽象解释循环与扩大运营商。我们证明了理想的抽象解释元属性，包括健全性和终止，保留在我们的方法，并要求的分析结果是等于那些计算出的批处理抽象解释。实验结果表明，承诺的原型要求抽象的解释框架：通过结合增量和需求驱动的技术，我们的框架始终提供分析结果的交互速度，回答95%的查询在1.2秒内。
We consider the problem of making expressive static analyzers interactive. Formal static analysis is seeing increasingly widespread adoption as a tool for verification and bug-finding, but even with powerful cloud infrastructure it can take minutes or hours to get batch analysis results after a code change. While existing techniques offer some demand-driven or incremental aspects for certain classes of analysis, the fundamental challenge we tackle is doing both for arbitrary abstract interpreters. Our technique, demanded abstract interpretation, lifts program syntax and analysis state to a dynamically evolving graph structure, in which program edits, client-issued queries, and evaluation of abstract semantics are all treated uniformly. The key difficulty addressed by our approach is the application of general incremental computation techniques to the complex, cyclic dependency structure induced by abstract interpretation of loops with widening operators. We prove that desirable abstract interpretation meta-properties, including soundness and termination, are preserved in our approach, and that demanded analysis results are equal to those computed by a batch abstract interpretation. Experimental results suggest promise for a prototype demanded abstract interpretation framework: by combining incremental and demand-driven techniques, our framework consistently delivers analysis results at interactive speeds, answering 95% of queries within 1.2 seconds.
登录
查看更多内容
语法导向编辑器的最佳时间增量语义分析
影响因子：
3.6
作者：
T. Reps
通讯作者：
T. Reps
DOI：
10.4230/lipics.ecoop.2016.22
发表时间：
2016-07
期刊：
--
影响因子：
--
作者：
Johannes Späth;Lisa Nguyen Quang Do;Karim Ali;E. Bodden
通讯作者：
Johannes Späth;Lisa Nguyen Quang Do;Karim Ali;E. Bodden
DOI：
10.1145/232627.232638
发表时间：
1996
期刊：
Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis
影响因子：
--
作者：
M. Abadi;B. Lampson;J. Lévy
通讯作者：
J. Lévy
数据流分析
影响因子：
0.6
作者：
Uday P. Khedker
通讯作者：
Uday P. Khedker
lambda 演算的增量减少
DOI：
10.1145/91556.91679
发表时间：
1990
期刊：
Proceedings of the 36th International Conference on Software Engineering
影响因子：
--
作者：
J. Field;T. Teitelbaum
通讯作者：
T. Teitelbaum