Sparse Analysis Framework

For precise, sound, global, yet also scalable static analysis

Hakjoo Oh, Kihong Heo, Wonchan Lee, Woosuk Lee, and Kwangkeun Yi
Programming Research Lab, ROSAEC Center, Seoul National University


Our sparse analysis framework provides a general method for achieving global static analyzers that are precise, sound, yet also scalable. Our method, on top of the abstract interpretation framework, is a general sparse analysis technique that supports relational as well as non-relational semantics properties for various programming languages. Analysis designers first use the abstract interpretation framework to have a global and correct static analyzer whose scalability is unattended. Upon this underlying sound static analyzer, analysis designers add our generalized sparse analysis techniques to improve its scalability while preserving the precision of the underlying analysis. Our method prescribes what to prove to guarantee that the resulting sparse version should preserve the precision of the underlying analyzer.

What is Sparse Analysis?

Look at the following slides to capture the key idea of sparse analysis and what's different from the conventional non-sparse analysis.




Our theoretical framework has also a practical significance. Based on the framework, we have derived a sparse version of Sparrow and found that the sparse Sparrow is 175x more scalable than the baseline in terms of lines of code. Furthermore, the sparse Sparrow is 1500x faster than the initial version of the Sparrow.

What's different from the conventional sparse analysis?



For general questions regarding Sparse Analysis, please send email to sparse _at_


This work was supported by the Engineering Research Center of Excellence Program of Korea Ministry of Education, Science and Technology(MEST) / National Research Foundation of Korea(NRF) (Grant 2012-0000468) and the Brain Korea 21 Project, School of Electrical Engineering and Computer Science, Seoul National University in 2011.