Pick Your Call Graphs Well: On Scaling IFDS-Based Data-Flow Analyses
Recent works on scaling IFDS-based analyses propose sophisticated techniques ranging from sparsification and disk-assisted computing to intelligent garbage collection. Yet, they choose a fixed call graph, thereby disregarding its implications on scalability.
This work presents an empirical evaluation of call graph precision's impact on the precision and scalability of the IFDS framework. To this end, we build QCG, a call graph generation tool for Android that extends the Qilin pointer analysis framework, and integrate it with FlowDroid, a state-of-the-art IFDS-based taint analysis solver. We assess the precision of 27 call graphs built with QCG and 4 default call graphs in FlowDroid, on the TaintBench benchmark of Android malware. We then evaluate how increasing the call-graph precision impacts FlowDroid's runtime performance and memory consumption on real-world apps.
We report that the time invested in building precise context-sensitive call graphs pays off: They significantly reduce IFDS analyses' runtimes while also improving their precision. However, there appears to be a sweet spot in the trade-off between the call graph construction time and the reduction in total analysis runtime.
Mon 16 JunDisplayed time zone: Seoul change
10:30 - 12:00 | |||
10:30 20mTalk | Scalable Language Agnostic Taint Tracking using Explicit Data Dependencies SOAP Sedick David Baker Effendi Stellenbosch University, Xavier Pinho StackGen, Andrei Michael Dreyer Whirly Labs, Fabian Yamaguchi Whirly Labs DOI Pre-print File Attached | ||
10:50 20mTalk | Pick Your Call Graphs Well: On Scaling IFDS-Based Data-Flow Analyses SOAP Kadiray Karakaya Heinz Nixdorf Institute at Paderborn University, Palaniappan Muthuraman Heinz Nixdorf Institute at Paderborn University, Eric Bodden Heinz Nixdorf Institute at Paderborn University; Fraunhofer IEM DOI | ||
11:10 20mTalk | Universal High-Performance CFL-Reachability via Matrix Multiplication SOAP DOI | ||
11:30 20mTalk | Beyond Affine Loops: A Geometric Approach to Program SynthesisRecorded SOAP DOI |