Michael Reif
Michael Eichberg
Mira Mezini
ABSTRACT
Call graphs are widely used; in particular for advanced control- and data-flow analyses. Even though many call graph algorithms with different precision and scalability properties have been proposed, a comprehensive understanding of sources of unsoundness, their relevance, and the capabilities of existing call graph algorithms in this respect is missing. To address this problem, we propose Judge, a toolchain that helps with understanding sources of unsoundness and improving the soundness of call graphs. In several experiments, we use Judge and an extensive test suite related to sources of unsoundness to (a) compute capability profiles for call graph implementations of Soot, WALA, DOOP, and OPAL, (b) to determine the prevalence of language features and APIs that affect soundness in modern Java Bytecode, (c) to compare the call graphs of Soot, WALA, DOOP, and OPAL – highlighting important differences in their implementations, and (d) to evaluate the necessary effort to achieve project-specific reasonable sound call graphs. We show that soundness-relevant features/APIs are frequently used and that support for them differs vastly, up to the point where comparing call graphs computed by the same base algorithms (e.g., RTA) but different frameworks is bogus. We also show that Judge can support users in establishing the soundness of call graphs with reasonable effort.
- {Online; accessed 20-January-2019}. Doop’s commit id: cdc59ce71d6510198da396cf6a7d20d73c6466d9.Google Scholar
- {Online; accessed 20-January-2019}. OPAL’s commit id: 3107c45c8a00de0e132691a6275d39b5a4aa415b.Google Scholar
- Karim Ali and Ondřej Lhoták. 2012. Application-only call graph construction. In European Conference on Object-Oriented Programming. Springer, 688–712. Google ScholarDigital Library
- Karim Ali and Ondřej Lhoták. 2013. Averroes: Whole-program analysis without the whole program. In European Conference on Object-Oriented Programming. Springer, 378–400. Google ScholarDigital Library
- Karim Ali, Marianna Rapoport, Ondřej Lhoták, Julian Dolby, and Frank Tip. 2014. Constructing call graphs of Scala programs. In European Conference on Object-Oriented Programming. Springer, 54–79. Google ScholarDigital Library
- Karim Ali, Marianna Rapoport, Ondřej Lhoták, Julian Dolby, and Frank Tip. 2015. Type-Based Call Graph Construction Algorithms for Scala. ACM Trans. Softw. Eng. Methodol. 25, 1, Article 9 (Dec. 2015), 43 pages. Google ScholarDigital Library
- Steven Arzt, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick McDaniel. 2014.Google ScholarDigital Library
- Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps. Acm Sigplan Notices 49, 6 (2014), 259–269. Google ScholarDigital Library
- David F Bacon and Peter F Sweeney. 1996. Fast static analysis of C++ virtual function calls. ACM Sigplan Notices 31, 10 (1996), 324–341. Google ScholarDigital Library
- Paulo Barros, René Just, Suzanne Millstein, Paul Vines, Werner Dietl, Michael D Ernst, et al. 2015. Static analysis of implicit control flow: Resolving Java reflection and Android intents (T). In Automated Software Engineering (ASE), 2015 30th IEEE/ACM International Conference on. IEEE, 669–679. Google ScholarDigital Library
- Stephen M Blackburn, Robin Garner, Chris Hoffmann, Asjad M Khang, Kathryn S McKinley, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z Guyer, et al. 2006. The DaCapo benchmarks: Java benchmarking development and analysis. In ACM Sigplan Notices, Vol. 41. ACM, 169–190. Google ScholarDigital Library
- Eric Bodden, Andreas Sewe, Jan Sinschek, Hela Oueslati, and Mira Mezin. 2011. Taming reflection. In Proceeding of the 33rd international conference on Software engineering - ICSE ’11. ACM Press, New York, New York, USA, 241. Google ScholarDigital Library
- Jeffrey Dean, David Grove, and Craig Chambers. 1995. Optimization of objectoriented programs using static class hierarchy analysis. In European Conference on Object-Oriented Programming. Springer, 77–101. Google ScholarDigital Library
- JB Dietrich, Henrik Schole, Li Sui, and Ewan Tempero. 2017. XCorpus–An executable Corpus of Java Programs. (2017).Google Scholar
- Lisa Nguyen Quang Do, Michael Eichberg, and Eric Bodden. 2016. Toward an automated benchmark management system. In Proceedings of the 5th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis. ACM, 13–17. Google ScholarDigital Library
- Michael Eichberg, F Kübler, D Helm, M Reif, G Salvaneschi, and M Mezini. 2018. Lattice Based Modularization of Static Analyses. In ISSTA Companion/ECOOP Companion. ACM. Google ScholarDigital Library
- Kotlin Foundation. {Online; accessed 24-August-2018}. Kotlin Language. https: //kotlinlang.org/.Google Scholar
- George Fourtounis, George Kastrinis, and Yannis Smaragdakis. 2018. Static Analysis of Java Dynamic Proxies. In Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2018). ACM, New York, NY, USA, 209–220. Google ScholarDigital Library
- J Gosling, B Joy, G Steele, G Bracha, A Buckely, and D Smith. 2018. The Java Virtual Machine Specification, 2018. Oracle Ameria.Google Scholar
- David Grove and Craig Chambers. 2001. A framework for call graph construction algorithms. ACM Transactions on Programming Languages and Systems (TOPLAS) 23, 6 (2001), 685–746. Google ScholarDigital Library
- Rich Hickey. {Online; accessed 24-August-2018}. Clojure Language.Google Scholar
- IBM. {Online; accessed 19-April-2018}. WALA - Static Analysis Framework for Java. http://wala.sourceforge.net/.Google Scholar
- Artima Inc. {Online; accessed 24-August-2018}. ScalaTest. http://www.scalatest. org/.Google Scholar
- Xiaoni Lai, Zhaoyi Luo, Karim Ali, Ondřej Lhoták, Julian Dolby, and Frank Tip. 2015. Evaluating Call Graph Construction for JVM-hosted Language Implementations. Technical Report CS-2015-03. University of Waterloo, David R. Cheriton School of Computer Science.Google Scholar
- École Polytechnique Fédérale Lausanne. {Online; accessed 24-August-2018}. Scala Language. https://www.scala-lang.org/.Google Scholar
- Ondvrej Lhoták. 2007. Comparing call graphs. In Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering - PASTE ’07. ACM Press, New York, New York, USA, 37–42. Google ScholarDigital Library
- Ondřej Lhoták and Laurie Hendren. 2003. Scaling Java points-to analysis using S park. In International Conference on Compiler Construction. Springer, 153–169. Google ScholarDigital Library
- B. Livshits. {Online; accessed -August-2018}. SecuriBench Micro. https://suif. stanford.edu/~livshits/work/securibench-micro/.Google Scholar
- Benjamin Livshits, Manu Sridharan, Yannis Smaragdakis, Ondřej Lhoták, J Nelson Amaral, Bor-Yuh Evan Chang, Samuel Z Guyer, Uday P Khedker, Anders Møller, and Dimitrios Vardoulakis. 2015. In defense of soundiness: a manifesto. Commun. ACM 58, 2 (2015), 44–46. Google ScholarDigital Library
- Luis Mastrangelo, Luca Ponzanelli, Andrea Mocci, Michele Lanza, Matthias Hauswirth, and Nathaniel Nystrom. 2015. Use at Your Own Risk: The Java Unsafe API in the Wild. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2015). ACM, New York, NY, USA, 695–710. Google ScholarDigital Library
- Gail C Murphy, David Notkin, William G Griswold, and Erica S Lan. 1998. An empirical study of static call graph extractors. ACM Transactions on Software Engineering and Methodology (TOSEM) 7, 2 (1998), 158–191. Google ScholarDigital Library
- MvnRepository. {Online; accessed 15-July-2018}. Maven - Popular Projects.a. https://mvnrepository.com/popular.Google Scholar
- The Apache Groovy project. {Online; accessed 24-August-2018}. Groovy Language. http://groovy-lang.org/.Google Scholar
- Michael Reif, Michael Eichberg, Ben Hermann, Johannes Lerch, and Mira Mezini. 2016. Call graph construction for java libraries. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering. ACM, 474–486. Google ScholarDigital Library
- Michael Reif, Michael Eichberg, Ben Hermann, and Mira Mezini. 2017. Hermes: assessment and creation of effective test corpora. In Proceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis. ACM, 43–48. Google ScholarDigital Library
- Michael Reif, Florian Kübler, Michael Eichberg, and Mira Mezini. 2018. Systematic evaluation of the unsoundness of call graph construction algorithms for Java. In Companion Proceedings for the ISSTA/ECOOP 2018 Workshops. ACM, 107–112. Google ScholarDigital Library
- Olin Shivers. 1988. Control flow analysis in scheme. In ACM SIGPLAN Notices, Vol. 23. ACM, 164–174. Google ScholarDigital Library
- Yannis Smaragdakis. {Online; accessed 23-August-2018}. DOOP - Framework for Java Pointer and Taint Analysis. https://bitbucket.org/yanniss/doop/.Google Scholar
- Yannis Smaragdakis. {Online; accessed 23-August-2018}. DOOP Benchmarks. https://bitbucket.org/yanniss/doop-benchmarks/.Google Scholar
- Yannis Smaragdakis, George Balatsouras, George Kastrinis, and Martin Bravenboer. 2015. More sound static handling of Java reflection. In Asian Symposium on Programming Languages and Systems. Springer, 485–503.Google ScholarCross Ref
- Johannes Späth, Lisa Nguyen Quang Do, Karim Ali, and Eric Bodden. 2016. Boomerang: Demand-Driven Flow- and Context-Sensitive Pointer Analysis for Java. In 30th European Conference on Object-Oriented Programming (ECOOP 2016) (Leibniz International Proceedings in Informatics (LIPIcs)), Shriram Krishnamurthi and Benjamin S. Lerner (Eds.), Vol. 56. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 22:1–22:26.Google Scholar
- Li Sui, Jens Dietrich, Michael Emery, Shawn Rasheed, and Amjed Tahir. 2018. On the Soundness of Call Graph Construction in the Presence of Dynamic Language Features-A Benchmark and Tool Evaluation. In Asian Symposium on Programming Languages and Systems. Springer, 69–88.Google Scholar
- Vijay Sundaresan, Laurie Hendren, Chrislain Razafimahefa, Raja Vallée-Rai, Patrick Lam, Etienne Gagnon, and Charles Godin. 2000. Practical virtual method call resolution for Java. Vol. 35. ACM. Google ScholarDigital Library
- Ewan Tempero, Craig Anslow, Jens Dietrich, Ted Han, Jing Li, Markus Lumpe, Hayden Melton, and James Noble. 2010. The Qualitas Corpus: A curated collection of Java code for empirical studies. In Software Engineering Conference (APSEC), 2010 17th Asia Pacific. IEEE, 336–345. Google ScholarDigital Library
- Ricardo Terra, Luis Fernando Miranda, Marco Tulio Valente, and Roberto S Bigonha. 2013. Qualitas. class Corpus: A compiled version of the Qualitas Corpus. ACM SIGSOFT Software Engineering Notes 38, 5 (2013), 1–4. Google ScholarDigital Library
- Frank Tip and Jens Palsberg. 2000. Scalable propagation-based call graph construction algorithms. Vol. 35. ACM. Google ScholarDigital Library
Index Terms
- Judge: identifying, understanding, and evaluating sources of unsoundness in call graphs
Recommendations
Systematic evaluation of the unsoundness of call graph construction algorithms for Java
ISSTA '18: Companion Proceedings for the ISSTA/ECOOP 2018 WorkshopsCall 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 understanding of the precision and recall of the respective graphs is crucial to ...
On the unsoundness of static analysis for Android GUIs
SOAP 2016: Proceedings of the 5th ACM SIGPLAN International Workshop on State Of the Art in Program AnalysisAndroid software presents exciting new challenges for the static analysis community. However, static analyses for Android are typically unsound. This is due to the lack of specification of the Android framework, the continuous evolution of framework ...
Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation
We present Paddle, a framework of BDD-based context-sensitive points-to and call graph analyses for Java, as well as client analyses that use their results. Paddle supports several variations of context-sensitive analyses, including call site strings ...
Comments