.png){kind=icon}
返回
Universal Scalability in Declarative Program Analysis (with Choice-Based Combination Pruning)
.png){kind=icon}
PRE
AI
DOI：10.1145/3763129.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
过去几十年中，用于固定点计算的Datalog引擎为静态程序分析带来了巨大的益处。分析的Datalog规范允许声明式、易于维护的规范，而不会牺牲性能，实际上通常与手工编码的算法相比实现显著的加速。然而，这些益处伴随着一定的控制损失。Datalog计算是自底向上的，这意味着从一组初始事实出发的所有推理都被执行，并且所有它们的结论都是计算结果。实践中，几乎每个用Datalog表达的程序分析对于某些输入变得不可扩展，这是由于计算所有结果的最坏情况爆炸，即使部分答案已经完全令人满意。在本工作中，我们提出了一种简单、统一且优雅的解决方案，具有极大的实际效果，并适用于几乎任何基于Datalog的分析。该方法利用了现代Datalog引擎（如Soufflé）原生支持的choice构造。choice构造允许定义关系中的函数依赖，并已被用于表达工作表算法。我们展示了一种近乎通用的构造，允许choice构造灵活地限制谓词的计算。该技术适用于几乎任何可想象的分析架构，因为它在（程序员控制的）关系投影超过所需基数时自适应地修剪计算结果。我们将该技术应用于可能存在最大的、预存的Datalog分析框架：Doop（用于Java字节码）和来自Gigahorse框架的主客户端分析（用于以太坊智能合约）。无需理解现有的分析逻辑，并且只需最小、仅局部的更改，每个框架的性能都显著提高，对于最难的输入提高超过20倍，而完整性的牺牲几乎可以忽略不计。
Keyword:
Static analysis
program analysis
logic programming
datalog
optimization
期刊
P
IF:
2.8
论文数:
308
被引数:
4.7K