Michael Reif
Michael Eichberg
Ben Hermann
Mira Mezini
ABSTRACT
Today, every application uses software libraries. Yet, while a lot of research exists w.r.t. analyzing applications, research that targets the analysis of libraries independent of any application is scarce. This is unfortunate, because, for developers of libraries, such as the Java Development Kit (JDK), it is crucial to ensure that the library behaves as intended regardless of how it is used. To fill this gap, we discuss the construction of call graphs for libraries that abstract over all potential library usages. Call graphs are particularly relevant as they are a precursor of many advanced analyses, such as inter-procedural data-flow analyses.
We show that the current practice of using call graph algorithms designed for applications to analyze libraries leads to call graphs that, at the same time, lack relevant call edges and contain unnecessary edges. This motivates the need for call graph construction algorithms dedicated to libraries. Unlike algorithms for applications, call graph construction algorithms for libraries must take into consideration the goals of subsequent analyses. Specifically, we show that it is essential to distinguish between the scenario of an analysis for potential exploitable vulnerabilities from the scenario of an analysis for general software quality attributes, e.g., dead methods or unused fields. This distinction affects the decision about what constitutes the library-private implementation, which therefore, needs special treatment. Thus, building one call graph that satisfies all needs is not sensical. Overall, we observed that the proposed call graph algorithms reduce the number of call edges up to 30% when compared to existing approaches.
- K. Ali and O. Lhoták. Application-only call graph construction. In Proceedings of the 26th European Conference on Object-Oriented Programming, ECOOP’12, pages 688–712, Berlin, Heidelberg, 2012. Springer-Verlag. Google Scholar
Digital Library
- K. Ali and O. Lhoták. Averroes: Whole-program analysis without the whole program. In G. Castagna, editor, ECOOP 2013 - Object-Oriented Programming - 27th European Conference, Montpellier, France, July 1-5, 2013. Proceedings, volume 7920 of Lecture Notes in Computer Science, pages 378–400. Springer, 2013. Google ScholarDigital Library
- N. Allen, P. Krishnan, and B. Scholz. Combining type-analysis with points-to analysis for analyzing java library source-code. In Proceedings of the 4th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis, SOAP 2015, pages 13–18, New York, NY, USA, 2015. ACM. Google ScholarDigital Library
- S. Arzt, S. Rasthofer, C. Fritz, E. Bodden, A. Bartel, J. Klein, Y. Le Traon, D. Octeau, and P. McDaniel. Flowdroid: Precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android apps. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’14, pages 259–269, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- D. F. Bacon and P. F. Sweeney. Fast static analysis of c++ virtual function calls. In Proceedings of the 11th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’96, pages 324–341, New York, NY, USA, 1996. ACM. Google ScholarDigital Library
- M. Bartoletti, P. Degano, and G. Ferrari. Static analysis for stack inspection. Electronic Notes in Theoretical Computer Science, 54:69 – 80, 2001.Google Scholar
- ConCoord: International Workshop on Concurrency and Coordination (Workshop associated to the 13th Lipari School).Google Scholar
- F. Besson, T. Blanc, C. Fournet, and A. Gordon. From stack inspection to access control: a security analysis for libraries. In Computer Security Foundations Workshop, 2004. Proceedings. 17th IEEE, pages 61–75, June 2004. Google ScholarDigital Library
- B.-M. Chang. Static check analysis for java stack inspection. SIGPLAN Not., 41(3):40–48, Mar. 2006. Google ScholarDigital Library
- J. Dean, D. Grove, and C. Chambers. Optimization of object-oriented programs using static class hierarchy analysis. In M. Tokoro and R. Pareschi, editors, ECOOP’95 — Object-Oriented Programming, 9th European Conference, ˚ Aarhus, Denmark, August 7–11, 1995, volume 952 of Lecture Notes in Computer Science, pages 77–101. Springer Berlin Heidelberg, 1995. Google ScholarDigital Library
- J. Dietrich, N. Hollingum, and B. Scholz. Giga-scale exhaustive points-to analysis for java in under a minute. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, pages 535–551, New York, NY, USA, 2015. ACM. Google ScholarDigital Library
- M. Eichberg, B. Hermann, M. Mezini, and L. Glanz. Hidden truths in dead software paths. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2015, pages 474–484, New York, NY, USA, 2015. ACM. Google ScholarDigital Library
- J. Gosling, B. Joy, G. Steele, and G. Bracha. The Java Language Specification, 2000. Sun Microsystems, 2009.Google ScholarDigital Library
- D. Grove and C. Chambers. A framework for call graph construction algorithms. ACM Trans. Program. Lang. Syst., 23(6):685–746, Nov. 2001. Google ScholarDigital Library
- B. Hermann, M. Reif, M. Eichberg, and M. Mezini. Getting to know you: Towards a capability model for java. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2015, pages 758–769, New York, NY, USA, 2015. ACM. Google ScholarDigital Library
- S. Koivu. Java trusted method chaining (cve-2010-0840/zdi-10-056). http://slightlyrandombrokenthoughts.blogspot.de/ 2010/04/java-trusted-method-chaining-cve-2010.html, apr 2010.Google Scholar
- L. Koved, M. Pistoia, and A. Kershenbaum. Access rights analysis for java. In Proceedings of the 17th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’02, pages 359–372, New York, NY, USA, 2002. ACM. Google ScholarDigital Library
- W. Landi and B. G. Ryder. Pointer-induced aliasing: A problem classification. In Proceedings of the 18th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’91, pages 93–103, New York, NY, USA, 1991. ACM. Google ScholarDigital Library
- W. Landi and B. G. Ryder. A safe approximate algorithm for interprocedural aliasing. In Proceedings of the ACM SIGPLAN 1992 Conference on Programming Language Design and Implementation, PLDI ’92, pages 235–248, New York, NY, USA, 1992. ACM. Google ScholarDigital Library
- J. Lerch, B. Hermann, E. Bodden, and M. Mezini. Flowtwist: Efficient context-sensitive inside-out taint analysis for large codebases. In Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2014, pages 98–108, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- T. Reps, S. Horwitz, and M. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proceedings of the 22Nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’95, pages 49–61, New York, NY, USA, 1995. ACM. Google ScholarDigital Library
- A. Rountev and S. Chandra. Off-line variable substitution for scaling points-to analysis. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, PLDI ’00, pages 47–56, New York, NY, USA, 2000. ACM. Google ScholarDigital Library
- A. Rountev, A. Milanova, and B. G. Ryder. Fragment class analysis for testing of polymorphism in java software. IEEE Trans. Softw. Eng., 30(6):372–387, June 2004. Google ScholarDigital Library
- A. Rountev and B. G. Ryder. Points-to and side-effect analyses for programs built with precompiled libraries. In Proceedings of the 10th International Conference on Compiler Construction, volume 2027 of CC ’01, pages 20–36. Springer Berlin Heidelberg, 2001. Google ScholarDigital Library
- M. Sagiv, T. Reps, and S. Horwitz. Precise interprocedural dataflow analysis with applications to constant propagation. Theoretical Computer Science, 167(1–2):131 – 170, 1996. Google ScholarDigital Library
- O. Shivers. Control flow analysis in scheme. In Proceedings of the ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation, PLDI ’88, pages 164–174, New York, NY, USA, 1988. ACM. Google ScholarDigital Library
- S. Sinha, M. J. Harrold, and G. Rothermel. Interprocedural control dependence. ACM Trans. Softw. Eng. Methodol., 10(2):209–254, Apr. 2001. Google ScholarDigital Library
- M. Sridharan and R. Bod´ık. Refinement-based context-sensitive points-to analysis for java. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’06, pages 387–400, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- M. Sridharan, D. Gopan, L. Shan, and R. Bod´ık. Demand-driven points-to analysis for java. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’05, pages 59–76, New York, NY, USA, 2005. ACM. Google ScholarDigital Library
- B. Steensgaard. Points-to analysis in almost linear time. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’96, pages 32–41, New York, NY, USA, 1996. ACM. Google ScholarDigital Library
- V. Sundaresan, L. Hendren, C. Razafimahefa, R. Vallée-Rai, P. Lam, E. Gagnon, and C. Godin. Practical virtual method call resolution for java. In Proceedings of the 15th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’00, pages 264–280, New York, NY, USA, 2000. ACM. Google ScholarDigital Library
- F. Tip and J. Palsberg. Scalable propagation-based call graph construction algorithms. In Proceedings of the 15th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’00, pages 281–293, New York, NY, USA, 2000. ACM. Google ScholarDigital Library
- G. Xu and A. Rountev. Merging equivalent contexts for scalable heap-cloning-based context-sensitive points-to analysis. In Proceedings of the 2008 International Symposium on Software Testing and Analysis, ISSTA ’08, pages 225–236, New York, NY, USA, 2008. ACM. Google ScholarDigital Library
- G. Xu, A. Rountev, and M. Sridharan. Scaling cfl-reachability-based points-to analysis using context-sensitive must-not-alias analysis. In Proceedings of the 23rd European Conference on ECOOP 2009 — Object-Oriented Programming, Genoa, pages 98–122, Berlin, Heidelberg, 2009. Springer-Verlag. Google ScholarDigital Library
- Q. Zhang, X. Xiao, C. Zhang, H. Yuan, and Z. Su. Efficient subcubic alias analysis for c. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA ’14, pages 829–845, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
Index Terms
- Call graph construction for Java libraries
Recommendations
A framework for call graph construction algorithms
A large number of call graph construction algorithms for object-oriented and functional languages have been proposed, each embodying different tradeoffs between analysis cost and call graph precision. In this article we present a unifying framework for ...
Extracting Java library subsets for deployment on embedded systems
Software maintenance and reengineering (CSMR 99)Embedded systems provide means for enhancing the functionality delivered by small-sized electronic devices such as hand-held computers and cellular phones. Java is a programming language which incorporates a number of features that are useful for ...
Evaluating the Java Native Interface JNI: Leveraging Existing Native Code, Libraries and Threads to a Running Java Virtual Machine
This article aims to explore JNI features and to discover fundamental operations of the Java programming language, such as arrays, objects, classes, threads and exception handling, and to illustrate these by using various algorithms and code samples. ...
Comments