Call Graph Construction for Program Analysis

This paper considers a task of call graph construction for programs written in different programming languages including C, C++, Java, Kotlin, Scala, Go, Python. We evaluate the characteristics of various open-source call graph construction tools and then present the design and implementation of our own tool, which supports all these languages. Our approach details key implementation strategies, such as build interception, intermodular linkage, and devirtualization. Finally, we provide experimental results that compare the performance of our tool with that of similar open-source solutions.

1. Polyakov S.A., Borodin A.E. Deadlock Detection using Static Analysis. In Proceedings of the Institute for System Programming of the RAS 32.5 (2020), pp. 21-34.

2. Ding B. et al. MEA2: A Lightweight Field- Sensitive Escape Analysis with Points-to Calculation for Golang. In Proceedings of the ACM on Programming Languages 8.OOPSLA2 (2024), pp. 1362-1389.

3. Visual Studio Code. Available at: https://code.visualstudio.com/, accessed 10.04.2025.

4. IntelliJ IDEA. Available at: https://www.jetbrains.com/idea/, accessed 11.07.2025.

5. Ivannikov V.P. et al. Static analyzer Svace for finding defects in a source program code. In Programming and Computer Software 40.5 (2014), pp. 265-275.

6. Borodin A.E., Belevantsev A.A. A static analysis tool Svace as a collection of analyzers with various complexity levels. In Proceedings of the Institute for System Programming of the RAS 27.6 (2015), pp. 111-134.

7. Bacon D. F., Sweeney P. F. 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. San Jose, California, USA: Association for Computing Machinery, 1996, pp. 324-341. ISBN: 089791788X. DOI: 10.1145/236337.236371.

8. Sõnajalg S. Program analysis techniques for method call devirtualization in object-oriented languages. 2009. Available at: http://www.cs.ut.ee/varmo/seminar/-sem09S/final/s6najalg.pdf, accessed 01.02.2025.

9. Anderson P. et al. Flow insensitive points-to sets. In Information and Software Technology 44.13 (2002). Special Issue on Source Code Analysis and Manipulation (SCAM), pp. 743-754. ISSN: 0950-5849. DOI: 10.1016/S0950-5849(02)00105-2.

10. Linux. Available at: https://www.linux.org/, accessed 11.07.2025.

11. Production-Grade Container Scheduling and Management. Available at: https://github.com/kubernetes/kubernetes, accessed 11.01.2025.

12. The Kotlin Programming Language. Available at: https://github.com/JetBrains/kotlin, accessed 11.01.2025.

13. The LLVM Compiler Infrastructure project. Available at: https://llvm.org/, accessed 11.07.2025.

14. LLVM Optimizer. Available at: https://llvm.org/docs/CommandGuide/opt.html, accessed 11.07.2025.

15. Kadiray Karakaya et al. Sootup: A redesign of the soot static analysis framework. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Springer. 2024, pp. 229-247.

16. Watson T.J. Libraries for Analysis, with front ends for Java, Android, and JavaScript, and many common static program analyses. Available at: https://github.com/wala/WALA, accessed 11.01.2025.

17. Karim A. et al. A study of call graph construction for jvm-hosted languages. In IEEE transactions on software engineering 47.12 (2019), pp. 2644-2666.

18. Cytron R. et al. Efficiently computing static single assignment form and the control dependence graph. In ACM Transactions on Programming Languages and Systems (TOPLAS) 13.4 (1991), pp. 451-490.

19. Go Tools. Available at: https://godoc.org/golang.org/x/tools, accessed 09.05.2025.

20. Variable Type Analysis (VTA) Algorithm. Available at: https://golang.org/x/tools/go/callgraph/vta, accessed 11.01.2025.

21. Package pointer implements Andersen’s analysis. Available at: https://pkg.go.dev/golang.org/x/tools/go/pointer, accessed 09.05.2025.

22. x/tools/go/pointer: isolate, tag, and delete the pointer analysis. Available at: https://github.com/golang/go/issues/59676, accessed 09.05.2025.

23. Go callgraph. Available at: https://godoc.org/golang.org/x/tools, accessed 09.05.2025.

24. go-callvis. Available at: https://github.com/ondrajz/go- callvis, accessed 09.05.2025.

25. gocyto. Available at: https://github.com/protolambda/gocyto, accessed 09.05.2025.

26. Salis V. et al. Pycg: Practical call graph generation in python. In 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE). IEEE. 2021, pp. 1646-1657.

27. python-call-graph. Available at: https://pypi.org/project/python-call-graph/, accessed 11.07.2025.

28. pyan3. Available at: https://pypi.org/project/pyan3/, accessed 11.07.2025.

29. CodeQL. Available at: https://codeql.github.com/, accessed 11.01.2025.

30. Open-source code analysis platform for C/C++/Java/Binary/Javascript/Python/Kotlin based on code property graphs. Available at: https://github.com/joernio/joern, accessed 11.01.2025.

31. Belevantsev A.A., Izbyshev A.O., Zhurikhin D.M. Monitoring program builds for Svace static analyzer. In System administrator 7-8 (2017), pp. 135-139.

32. Belevantsev A.A. Multilevel static analysis for improving program quality. In Programming and Computer Software 6 (2017), pp. 3-25.

33. strip(1) Linux manual page. Available at: https://man7.org/linux/man-pages/man1/strip.1.html, accessed 11.07.2025.

34. ranlib(1) Linux manual page. Available at: https://man7.org/linux/man-pages/man1/ranlib.1.html, accessed 11.07.2025.

35. Steensgaard B. Points-to analysis in almost linear time. In Proceedings of the 23rd ACM SIGPLAN/SIGACT symposium on Principles of programming languages. 1996, pp. 32-41.

36. Das M. Unification-based pointer analysis with directional assignments. In Acm Sigplan Notices 35.5 (2000), pp. 35-46.

37. Cooper K. D. and Kennedy K. Fast interprocedural alias analysis. In Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. 1989, pp. 49-59.

38. Whaley J., Lam M.S. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 conference on Programming Language Design and Implementation, 2004, pp. 131-144.

39. Galustov A.L., Borodin A.E., Belevantsev A.A. Devirtualization for static analysis with low level intermediate representation. In 2022 Ivannikov Ispras Open Conference (ISPRAS). IEEE, 2022, pp. 18 23.

40. The Java Virtual Machine Specification. Java SE 21 Edition. Available at: https://docs.oracle.com/javase/specs/jvms/se21/html, accessed 11.01.2025.

41. Merkulov A.P., Polyakov S.A., Belevantsev A.A. Supporting Java programming in the Svace static analyzer. In Proceedings of the Institute for System Programming of the RAS 29.3 (2017), pp. 57-74.

42. Afanasyev V.O. et al. Kotlin from the perspective of a static analyzer developer. In Proceedings of the Institute for System Programming of the RAS 33.6 (2021), pp. 67-82.

43. Afanasyev V.O., Borodin A.E., Belevantsev A.A. Static Analysis for Scala. In Proceedings of the Institute for System Programming of the RAS 36.3 (2024), pp. 9-20.

44. Karim A. et al. Constructing call graphs of Scala programs. In European Conference on Object-Oriented Programming. Springer. 2014, pp. 54-79.

45. Dvortsova V. et al. Static Analysis for Go: Build Interception. In 2023 Ivannikov Ispras Open Conference (ISPRAS). IEEE. 2023, pp. 52-57.

46. Ssadump. Available at: https://pkg.go.dev/golang.org/x/tools/cmd/ssadump, accessed 10.05.2025.

47. Go interface types. Available at: https://go.dev/ref/spec#Interface_types, accessed 11.01.2025.

48. Package reflect. Available at: https://pkg.go.dev/reflect#sectiondocumentation, accessed 11.01.2025.

49. Go import path syntax. Available at: https://pkg.go.dev/cmd/go#hdr-Import_path_syntax, accessed 11.01.2025.

50. TinyMUX. Available at: https://tinymux.org, accessed 11.07.2025.

51. Kodi. Available at: https://kodi.tv/, accessed 11.07.2025.

52. Apache Commons Lang. Available at: https://github.com/apache/commons-lang, accessed 11.01.2025.

53. A PDF processor written in Go. Available at: https://github.com/pdfcpu/pdfcpu, accessed 10.04.2025.

54. eBPF-based Networking, Security, and Observability. Available at: https://github.com/cilium/cilium, accessed 10.04.2025.

55. The Python micro framework for building web applications. Available at: https://github.com/pallets/flask, accessed 10.04.2025.

56. Tensors and Dynamic neural networks in Python with strong GPU acceleration. Available at: https://github.com/pytorch/pytorch, accessed 10.04.2025.