Chianina: an evolving graph system for flow- and context-sensitive analyses of million lines of C code
Chianina: an evolving graph system for flow- and context-sensitive analyses of million lines of C code
复制标题
DOI：
10.1145/3453483.3454085
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Zhiqiang Zuo;Yiyu Zhang;Qiuhong Pan;S. Lu;Yue Li;Linzhang Wang;Xuandong Li;G. Xu
中科院分区：
文献类型：
--
作者：
Zhiqiang Zuo;Yiyu Zhang;Qiuhong Pan;S. Lu;Yue Li;Linzhang Wang;Xuandong Li;G. Xu
复杂的静态分析技术通常具有复杂的实现，其中大部分提供了调整和缩放而不是基本分析功能的逻辑。基本算法与特殊治疗可伸缩性的紧密耦合使得分析实现难以（1）正确，（2）理解/使用，以及（3）对其他客户的重复使用。本文介绍了Chianina，这是我们开发的图形系统，用于大型C程序的完全上下文和流动敏感分析。 Chianina通过允许开发人员仅提供分析的基本算法并将调整/缩放工作推向基础系统来克服这些挑战。 Chianina成功的关键是（1）流动敏感性的不断发展的图表和（2）核心外，磁盘支持的杠杆作用，以应对上下文灵敏度引起的内存爆炸。我们在基亚纳（Chianina）的顶部实施了三个上下文和流动敏感分析，并将其缩放到单个商品PC上的Linux（17m LOC）等大型C程序。
Sophisticated static analysis techniques often have complicated implementations, much of which provides logic for tuning and scaling rather than basic analysis functionalities. This tight coupling of basic algorithms with special treatments for scalability makes an analysis implementation hard to (1) make correct, (2) understand/work with, and (3) reuse for other clients. This paper presents Chianina, a graph system we developed for fully context- and flow-sensitive analysis of large C programs. Chianina overcomes these challenges by allowing the developer to provide only the basic algorithm of an analysis and pushing the tuning/scaling work to the underlying system. Key to the success of Chianina is (1) an evolving graph formulation of flow sensitivity and (2) the leverage of out-of-core, disk support to deal with memory blowup resulting from context sensitivity. We implemented three context- and flow-sensitive analyses on top of Chianina and scaled them to large C programs like Linux (17M LoC) on a single commodity PC.