A Preparation Guide for Java Call Graph Comparison
Finding a Match for Your Methods
Abstract
Call graphs provide basis for numerous interprocedural analysers and tools, therefore it is crucial how precisely they are constructed. Developers need to know the features of a call graph builder before applying it to subsequent algorithms. The characteristics of call graph builders are best understood by comparing the generated call graphs themselves. The comparison can be done by matching the corresponding nodes in each graph and then analysing the found methods and calls.
In this paper, we developed a process for pairing the nodes of multiple call graphs produced for the same source code. As the six static analysers that we collected for call graph building handles Java language elements differently, it was necessary to refine the basic name-wise pairing mechanism in several steps. Two language elements, the anonymous and generic methods, needed extra consideration. We describe the steps of improvement and our final solution to achieve the best possible pairing through the analysis of the Apache Commons-Math project.
Downloads
References
Ahmad Bhat, Sajad. A practical and comparative study of call graph construction algorithms. IOSR Journal of Computer Engineering, 1:14-26, 01 2012. DOI: 10.9790/0661-0141426.
Andersen, Lars Ole. Program analysis and specialization for the C programming language. Technical Report May, 1994. 10.1.1.109.6502.
Apache BCEL Home Page. https://commons.apache.org/proper/commons-bcel>
Bacon, David F. and Sweeney, Peter F. Fast Static Analysis of C++ Virtual Function Calls. SIGPLAN Not., 31(10):324--341, October 1996. DOI: 10.1145/236338.236371.
Blondel, Vincent, Gajardo, Anahi, Heymans, Maureen, Senellart, Pierre, and Van Dooren, Paul. A measure of similarity between graph vertices: Applications to synonym extraction and web searching. SIAM Review, 46:647-666, 12 2004. DOI: 10.2307/20453570.
Call Hierarchy Printer GitHub Page. https://github.com/pbadenski/call-hierarchy-printer>
Champin, Pierre-Antoine and Solnon, Christine. Measuring the similarity of labeled graphs. In Ashley, Kevin D. and Bridge, Derek G., editors, Case-Based Reasoning Research and Development, pages 80--95, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
Christodorescu, Mihai and Jha, Somesh. Static analysis of executables to detect malicious patterns. In Proceedings of the 12th Conference on USENIX Security Symposium - Volume 12, SSYM'03, pages 12--12, Berkeley, CA, USA, 2003. USENIX Association.
Dean, Jeffrey, Grove, David, and Chambers, Craig. Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis. In Tokoro, Mario and Pareschi, Remo, editors, ECOOP'95 --- Object-Oriented Programming, 9th European Conference, Aarhus, Denmark, August 7--11, 1995, pages 77--101, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg.
Eclipse JDT Home Page. http://www.eclipse.org/jdt/>
Eclipse Home Page. http://www.eclipse.org/eclipse/>
Eshera, M. A. and Fu, K. A graph distance measure for image analysis. IEEE Transactions on Systems, Man, and Cybernetics, SMC-14(3):398-408, May 1984. DOI: 10.1109/TSMC.1984.6313232.
Feng, Yu, Anand, Saswat, Dillig, Isil, and Aiken, Alex. Apposcopy: Semantics-based detection of android malware through static analysis. In Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2014, pages 576--587, New York, NY, USA, 2014. ACM. DOI: 10.1145/2635868.2635869.
Grove, David and Chambers, Craig. A framework for call graph construction algorithms. ACM Trans. Program. Lang. Syst., 23(6):685--746, November 2001. DOI: 10.1145/506315.506316.
Grove, David, DeFouw, Greg, Dean, Jeffrey, and Chambers, Craig. Call Graph Construction in Object-oriented Languages. In Proceedings of the 12th ACM SIGPLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA '97, pages 108--124, New York, NY, USA, 1997. ACM. DOI: 10.1145/263698.264352.
Heymans, Maureen and Singh, Ambuj K. Deriving phylogenetic trees from the similarity analysis of metabolic pathways. Bioinformatics, 19 Suppl 1:i138-46, 2003.
Java Call Graph GitHub Page. https://github.com/gousiosg/java-callgraph>
JavaParser - for processing Java code Homepage. https://javaparser.org/>
Koutra, Danai, Parikh, Ankur, Ramdas, Aaditya, and Xiang, Jing. Algorithms for graph similarity and subgraph matching. 02 2019.
Lhoták, Ondrej. Comparing call graphs. In ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, pages 37-42, 2007.
Lhoták, Ondrej and Hendren, Laurie. Context-Sensitive Points-to Analysis: Is It Worth It?. In Mycroft, Alan and Zeller, Andreas, editors, Compiler Construction, pages 47--64, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg.
Macindoe, O. and Richards, W. Graph comparison using fine structure analysis. In 2010 IEEE Second International Conference on Social Computing, pages 193-200, Aug 2010. DOI: 10.1109/SocialCom.2010.35.
Melnik, Sergey, Garcia-Molina, Hector, and Rahm, Erhard. Similarity flooding: A versatile graph matching algorithm and its application to schema matching. pages 117 - 128, 02 2002. DOI: 10.1109/ICDE.2002.994702.
Murphy, Gail C., Notkin, David, Griswold, William G., and Lan, Erica S. An Empirical Study of Static Call Graph Extractors. ACM Trans. Softw. Eng. Methodol., 7(2):158--191, April 1998. DOI: 10.1145/279310.279314.
Nikolic, Mladen. Measuring similarity of graph nodes by neighbor matching. Intell. Data Anal., 16(6):865--878, November 2012. DOI: 10.3233/IDA-2012-00556.
OpenStaticAnalyzer GitHub Page. https://github.com/sed-inf-u-szeged/OpenStaticAnalyzer>
Pawlak, Renaud, Monperrus, Martin, Petitprez, Nicolas, Noguera, Carlos, and Seinturier, Lionel. Spoon: A Library for Implementing Analyses and Transformations of Java Source Code. Software: Practice and Experience, 46:1155-1179, 2015. DOI: 10.1002/spe.2346.
Sable *J Home Page. http://www.sable.mcgill.ca/starj/>
Sable/Soot GitHub Page. https://github.com/Sable/soot>
Sanfeliu, A. and Fu, K. A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13(3):353-362, May 1983. DOI: 10.1109/TSMC.1983.6313167.
Sundaresan, Vijay, Hendren, Laurie, Razafimahefa, Chrislain, Vallée-Rai, Raja, Lam, Patrick, Gagnon, Etienne, and Godin, Charles. Practical virtual method call resolution for java. SIGPLAN Not., 35(10):264--280, October 2000. DOI: 10.1145/354222.353189.
Tip, Frank and Palsberg, Jens. 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. DOI: 10.1145/353171.353190.
Tversky, Amos. Features of similarity. Psychological Review, 84(4):327--352, 1977. DOI: 10.1037/0033-295X.84.4.327.
Ullmann, J. R. An algorithm for subgraph isomorphism. J. ACM, 23(1):31--42, January 1976. DOI: 10.1145/321921.321925.
Wagner, Tim A., Maverick, Vance, Graham, Susan L., and Harrison, Michael A. Accurate static estimators for program optimization. SIGPLAN Not., 29(6):85--96, June 1994. DOI: 10.1145/773473.178251.
WALA Home Page. http://wala.sourceforge.net/wiki/index.php/Main_Page>
Weiser, Mark. Program slicing. In Proceedings of the 5th International Conference on Software Engineering, ICSE '81, pages 439--449, Piscataway, NJ, USA, 1981. IEEE Press.
Wicker, Nicolas, Nguyen, Canh Hao, and Mamitsuka, Hiroshi. A new dissimilarity measure for comparing labeled graphs. Linear Algebra and its Applications, 438(5):2331 - 2338, 2013. DOI: 10.1016/j.laa.2012.10.021.
Zager, Laura A. and Verghese, George C. Graph similarity scoring and matching. Applied Mathematics Letters, 21(1):86--94, jan 2008. DOI: 10.1016/j.aml.2007.01.006.
