Software Technology Group @ TU Darmstadt

Systematic Evaluation of the Unsoundness of Call Graph Construction Algorithms for Java

by Michael Reif, Florian Kübler, Michael Eichberg, and Mira Mezini

Abstract: Call graphs are at the core of many static analyses ranging from the detection of unused methods to advanced control- and data-flow analyses. Therefore, a comprehensive under- standing of the precision and recall of the respective graphs is crucial to enable an assessment which call-graph construction algorithms are suited in which analysis scenario. For example, malware is often obfuscated and tries to hide its intent by using Reflection. Call graphs that do not represent reflective method calls are, therefore, of limited use when analyzing such apps. In general, the precision is well understood, but the recall is not, i.e., in which cases a call graph will not contain any call edges. In this paper, we discuss the design of a compre- hensive test suite that enables us to compute a fingerprint of the unsoundness of the respective call-graph construction algorithms. This suite also enables us to make a comparative evaluation of static analysis frameworks. Comparing Soot and WALA shows that WALA currently has better support for new Java 8 features and also for Java Reflection. However, in some cases both fail to include expected edges.



@inproceedings {RKEM,
  title = {{Systematic Evaluation of the Unsoundness of Call Graph Construction Algorithms for Java}},
  author = {Reif, Michael and Kübler, Florian and Eichberg, Michael and Mezini, Mira},
  booktitle = {{Proceeding ISSTA '18 Companion Proceedings for the ISSTA/ECOOP 2018 Workshops}},
  series = {SOAP 2018},
  pages = {107-112},
  year = {2018},
  doi = {10.1145/3236454.3236503},
  url = {},