A lightweight approach for sound call graph approximation
Aharon Abadi, Bar Makovitzki, Ron Shemer, Shmuel S. Tyszberowicz · Proceedings of the 37th ACM/SIGAPP Symposium on Applied Computing · 2022
Interprocedural analysis refers to gathering information about the entire program rather than for a single procedure only, as in intraprocedural analysis. It enables a more precise analysis; however, it is complicated due to the difficulty of constructing an accurate program call graph. Algorithms for constructing sound call graphs must trade-off precision against scalability. Many precise call graph techniques are complex and are difficult to scale due to the kind of type-inference analysis they use, in particular the use of some variations of points-to analysis. This forces use cases that require both soundness and scale such as vulnerability propagation analysis to resort to simpler variants such as Class Hierarchy Analysis. These kinds of analyses have no sound equivalent for dynamically typed languages such as Python and JavaScript that gained more popularity over recent years. To address this problem, we propose NoCFG, a new sound and scalable method for approximating a call graph that supports a wide variety of programming languages. A key property of NoCFG is that it works on a coarse abstraction of the program, discarding many of the programming language constructs. Due to the coarse program abstraction, extending it to support also other languages is easy. We evaluate NoCFG for real-world projects written in both Python and C# and the results demonstrate a high precision rate of ≥ 89% and scalability through a security use-case over projects with up to 2 million lines of code.