Scalable data-flow analysis through sparsification and precise call graphs / Kadiray Karakaya ; Advisor Prof. Dr. Eric Bodden. Paderborn, 2025
Content
- Abstract
- Acknowledgments
- Contents
- 1 Introduction
- 2 Background
- 2.1 Data-Flow Analysis
- 2.2 Interprocedural Data-Flow Analysis
- 2.3 Call-Graph Construction
- 2.4 Demand-Driven Pointer Analysis
- 2.5 Sparse Data-Flow Analysis
- 3 SparseIDE: Symbol-Specific Sparsification of IDE Problems
- 3.1 Motivation
- 3.2 Contributions
- 3.3 Fact-Specific On-Demand Sparsification
- 3.4 Symbol-specific On-Demand Sparsificiation with SparseIDE
- 3.4.1 The Original IDE Algorithm
- 3.4.2 The SparseIDE Algorithm
- 3.4.3 Sparse IFDS Revisited
- 3.4.4 Fact-Specific Identity Transformers
- 3.4.5 Determining Symbol-Specific Identity
- 3.5 Application to Linear Constant Propagation
- 3.6 Evaluation
- 3.6.1 Experimental Setup
- 3.6.2 RQ1: Does Sparse IDE produce the same results as the original IDE?
- 3.6.3 RQ2: How does the sparsification impact the performance in terms of runtime and memory?
- 3.6.4 RQ3: To what extent does the number of propagations correlate with the performance impact?
- 3.6.5 Threats to Validity
- 3.7 Related Work
- 3.8 Conclusion
- 4 An Empirical Study on the Impact of Call-Graph Precision on the Scalability of Data-Flow Analysis
- 4.1 Motivation
- 4.2 Contributions
- 4.3 Foundations
- 4.3.1 Call Graph's Implications on IFDS
- 4.3.2 Call-Graph Generation using Pointer Information
- 4.3.3 Qilin
- 4.3.4 QCG
- 4.4 Study Design
- 4.5 Experimental Results
- 4.5.1 RQ1: How does call graph precision impact the precision of IFDS analyses?
- 4.5.2 RQ2: How does call graph precision impact the performance of IFDS analyses in terms of runtime and memory?
- 4.5.3 RQ3: How does the number of interprocedural edges correlate with the analysis runtime and memory consumption?
- 4.5.4 Discussion
- 4.5.5 Threats to Validity
- 4.6 Related Work
- 4.7 Conclusion
- 5 SparseBoomerang: Query-Specific Sparsification for Demand-Driven Pointer Analysis
- 5.1 Motivation
- 5.2 Contributions
- 5.3 Background
- 5.4 Demand-Driven Sparsification Strategies
- 5.5 SparseBoomerang
- 5.5.1 Implementation of Type-Aware Sparsification
- 5.5.2 Implementation of Alias-aware Sparsification
- 5.6 Evaluation
- 5.6.1 Experimental Setup
- 5.6.2 RQ1: Do the sparsification strategies cause precision loss?
- 5.6.3 RQ2: How do the sparsification strategies impact the performance of the demand-driven pointer analysis and its client?
- 5.6.4 RQ3: How does the degree of sparsification impact the SCFG construction time and its evaluation time?
- 5.6.5 Discussion and Threats to Validity
- 5.7 Related Work
- 5.8 Conclusion
- 6 Conclusion and Outlook
- Artifacts
- Bibliography
- List of Figures
- List of Tables