Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems

K. Karakaya, E. Bodden, in: Proceedings of the IEEE/ACM 46th International Conference on Software Engineering, ACM, 2024.

Download
No fulltext has been uploaded.
Conference Paper | Published | English
Abstract
Previous work has shown that one can often greatly speed up static analysis by computing data flows not for every edge in the program’s control-flow graph but instead only along definition-use chains. This yields a so-called sparse static analysis. Recent work on SparseDroid has shown that specifically taint analysis can be “sparsified” with extraordinary effectiveness because the taint state of one variable does not depend on those of others. This allows one to soundly omit more flow-function computations than in the general case. In this work, we now assess whether this result carries over to the more generic setting of so-called Interprocedural Distributive Environment (IDE) problems. Opposed to taint analysis, IDE comprises distributive problems with large or even infinitely broad domains, such as typestate analysis or linear constant propagation. Specifically, this paper presents Sparse IDE, a framework that realizes sparsification for any static analysis that fits the IDE framework. We implement Sparse IDE in SparseHeros, as an extension to the popular Heros IDE solver, and evaluate its performance on real-world Java libraries by comparing it to the baseline IDE algorithm. To this end, we design, implement and evaluate a linear constant propagation analysis client on top of SparseHeros. Our experiments show that, although IDE analyses can only be sparsified with respect to symbols and not (numeric) values, Sparse IDE can nonetheless yield significantly lower runtimes and often also memory consumptions compared to the original IDE.
Publishing Year
Proceedings Title
Proceedings of the IEEE/ACM 46th International Conference on Software Engineering
LibreCat-ID

Cite this

Karakaya K, Bodden E. Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems. In: Proceedings of the IEEE/ACM 46th International Conference on Software Engineering. ACM; 2024. doi:10.1145/3597503.3639092
Karakaya, K., & Bodden, E. (2024). Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems. Proceedings of the IEEE/ACM 46th International Conference on Software Engineering. https://doi.org/10.1145/3597503.3639092
@inproceedings{Karakaya_Bodden_2024, title={Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems}, DOI={10.1145/3597503.3639092}, booktitle={Proceedings of the IEEE/ACM 46th International Conference on Software Engineering}, publisher={ACM}, author={Karakaya, Kadiray and Bodden, Eric}, year={2024} }
Karakaya, Kadiray, and Eric Bodden. “Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems.” In Proceedings of the IEEE/ACM 46th International Conference on Software Engineering. ACM, 2024. https://doi.org/10.1145/3597503.3639092.
K. Karakaya and E. Bodden, “Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems,” 2024, doi: 10.1145/3597503.3639092.
Karakaya, Kadiray, and Eric Bodden. “Symbol-Specific Sparsification of Interprocedural Distributive Environment Problems.” Proceedings of the IEEE/ACM 46th International Conference on Software Engineering, ACM, 2024, doi:10.1145/3597503.3639092.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar