research-article

Judge: identifying, understanding, and evaluating sources of unsoundness in call graphs

Authors:

Florian Kübler,

Michael Eichberg,

Mira MeziniAuthors Info & Claims

ISSTA 2019: Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis

Pages 251 - 261

https://doi.org/10.1145/3293882.3330555

Published: 10 July 2019 Publication History

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.

References

[1]

{Online; accessed 20-January-2019}. Doop’s commit id: cdc59ce71d6510198da396cf6a7d20d73c6466d9.

[2]

{Online; accessed 20-January-2019}. OPAL’s commit id: 3107c45c8a00de0e132691a6275d39b5a4aa415b.

[3]

Karim Ali and Ondřej Lhoták. 2012. Application-only call graph construction. In European Conference on Object-Oriented Programming. Springer, 688–712.

Digital Library

[4]

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.

Digital Library

[5]

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.

Digital Library

[6]

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.

Digital Library

[7]

Steven Arzt, Siegfried Rasthofer, Christian Fritz, Eric Bodden, Alexandre Bartel, Jacques Klein, Yves Le Traon, Damien Octeau, and Patrick McDaniel. 2014.

Digital Library

[8]

Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps. Acm Sigplan Notices 49, 6 (2014), 259–269.

Digital Library

[9]

David F Bacon and Peter F Sweeney. 1996. Fast static analysis of C++ virtual function calls. ACM Sigplan Notices 31, 10 (1996), 324–341.

Digital Library

[10]

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.

Digital Library

[11]

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.

Digital Library

[12]

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.

Digital Library

[13]

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.

Digital Library

[14]

JB Dietrich, Henrik Schole, Li Sui, and Ewan Tempero. 2017. XCorpus–An executable Corpus of Java Programs. (2017).

[15]

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.

Digital Library

[16]

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.

Digital Library

[17]

Kotlin Foundation. {Online; accessed 24-August-2018}. Kotlin Language. https: //kotlinlang.org/.

[18]

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.

Digital Library

[19]

J Gosling, B Joy, G Steele, G Bracha, A Buckely, and D Smith. 2018. The Java Virtual Machine Specification, 2018. Oracle Ameria.

[20]

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.

Digital Library

[21]

Rich Hickey. {Online; accessed 24-August-2018}. Clojure Language.

[22]

IBM. {Online; accessed 19-April-2018}. WALA - Static Analysis Framework for Java. http://wala.sourceforge.net/.

[23]

Artima Inc. {Online; accessed 24-August-2018}. ScalaTest. http://www.scalatest. org/.

[24]

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.

[25]

École Polytechnique Fédérale Lausanne. {Online; accessed 24-August-2018}. Scala Language. https://www.scala-lang.org/.

[26]

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.

Digital Library

[27]

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.

Digital Library

[28]

B. Livshits. {Online; accessed -August-2018}. SecuriBench Micro. https://suif. stanford.edu/~livshits/work/securibench-micro/.

[29]

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.

Digital Library

[30]

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.

Digital Library

[31]

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.

Digital Library

[32]

MvnRepository. {Online; accessed 15-July-2018}. Maven - Popular Projects.a. https://mvnrepository.com/popular.

[33]

The Apache Groovy project. {Online; accessed 24-August-2018}. Groovy Language. http://groovy-lang.org/.

[34]

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.

Digital Library

[35]

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.

Digital Library

[36]

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.

Digital Library

[37]

Olin Shivers. 1988. Control flow analysis in scheme. In ACM SIGPLAN Notices, Vol. 23. ACM, 164–174.

Digital Library

[38]

Yannis Smaragdakis. {Online; accessed 23-August-2018}. DOOP - Framework for Java Pointer and Taint Analysis. https://bitbucket.org/yanniss/doop/.

[39]

Yannis Smaragdakis. {Online; accessed 23-August-2018}. DOOP Benchmarks. https://bitbucket.org/yanniss/doop-benchmarks/.

[40]

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.

[41]

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.

[42]

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.

[43]

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.

Digital Library

[44]

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.

Digital Library

[45]

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.

Digital Library

[46]

Frank Tip and Jens Palsberg. 2000. Scalable propagation-based call graph construction algorithms. Vol. 35. ACM.

Digital Library

Cited By

Zhang HPei YLiang SXing ZTan SChristakis MPradel M(2024)Characterizing and Detecting Program Representation Faults of Static Analysis FrameworksProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680398(1772-1784)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680398
Samhi JJust RBissyandé TErnst MKlein JChristakis MPradel M(2024)Call Graph Soundness in Android Static AnalysisProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680333(945-957)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680333
Helm DKeidel SKampkötter ADüsing JRoth THermann BMezini MChristakis MPradel M(2024)Total Recall? How Good Are Static Call Graphs Really?Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652114(112-123)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652114
Show More Cited By

Index Terms

Judge: identifying, understanding, and evaluating sources of unsoundness in call graphs
1. General and reference
  1. Cross-computing tools and techniques
    1. Evaluation
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Polymorphism

Recommendations

Systematic evaluation of the unsoundness of call graph construction algorithms for Java
ISSTA '18: Companion Proceedings for the ISSTA/ECOOP 2018 Workshops

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 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 Analysis

Android 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA 2019: Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis

July 2019

451 pages

ISBN:9781450362245

DOI:10.1145/3293882

General Chair:
Dongmei Zhang
Microsoft Research, China
,
Program Chair:
Anders Møller
Aarhus University, Denmark

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSTA '19

Sponsor:

SIGSOFT

ISSTA '19: 28th ACM SIGSOFT International Symposium on Software Testing and Analysis

July 15 - 19, 2019

Beijing, China

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
627
Total Downloads

Downloads (Last 12 months)128
Downloads (Last 6 weeks)16

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang HPei YLiang SXing ZTan SChristakis MPradel M(2024)Characterizing and Detecting Program Representation Faults of Static Analysis FrameworksProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680398(1772-1784)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680398
Samhi JJust RBissyandé TErnst MKlein JChristakis MPradel M(2024)Call Graph Soundness in Android Static AnalysisProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680333(945-957)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680333
Helm DKeidel SKampkötter ADüsing JRoth THermann BMezini MChristakis MPradel M(2024)Total Recall? How Good Are Static Call Graphs Really?Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652114(112-123)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652114
Helm DRoth TKeidel SReif MMezini MChristakis MPradel M(2024)Unimocg: Modular Call-Graph Algorithms for Consistent Handling of Language FeaturesProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3652109(51-62)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3652109
Santos JMirakhorli MShokri A(2024)Seneca: Taint-Based Call Graph Construction for Java Object DeserializationProceedings of the ACM on Programming Languages10.1145/36498518:OOPSLA1(1125-1153)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649851
Mir AKeshani MProksch SSpinellis DConstantinou EBacchelli A(2024)On the Effectiveness of Machine Learning-based Call Graph Pruning: An Empirical StudyProceedings of the 21st International Conference on Mining Software Repositories10.1145/3643991.3644897(457-468)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643991.3644897
Bouzenia IKrishan BPradel M(2024)DyPyBench: A Benchmark of Executable Python SoftwareProceedings of the ACM on Software Engineering10.1145/36437421:FSE(338-358)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3643742
Keidel SHelm DRoth TMezini M(2024)A Modular Soundness Theory for the Blackboard Analysis ArchitectureProgramming Languages and Systems10.1007/978-3-031-57267-8_14(361-390)Online publication date: 6-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57267-8_14
Tan TLi YJust RFraser G(2023)Tai-e: A Developer-Friendly Static Analysis Framework for Java by Harnessing the Good Designs of ClassicsProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598120(1093-1105)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598120
Lehmann DThalakottur MTip FPradel MJust RFraser G(2023)That’s a Tough Call: Studying the Challenges of Call Graph Construction for WebAssemblyProceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3597926.3598104(892-903)Online publication date: 12-Jul-2023
https://dl.acm.org/doi/10.1145/3597926.3598104
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents