Write a Blog >>
PLDI 2021
Sun 20 - Sat 26 June 2021 Virtual Conference

Sophisticated static analysis techniques often have complicated implementations, much of which provides logic for \emph{tuning and scaling} rather than \emph{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 \emph{evolving graph formulation} of flow sensitivity and (2) the leverage of \emph{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.