Darren C. Atkinson, “Call graph extraction in the presence of function pointers,” in Proceedings of the 2002 International Conference on Software Engineering Research and Practice, pp. 579–584, June 2002.
Abstract
Software engineers need to understand programs in order to efficiently and effectively maintain them. The call graph, which presents the relationships between calling and called functions, is a useful representation of a program that can greatly aid understanding. For programs without the use of function pointers, the call graph can be extracted during a simple parse of the program. However, for programs with function pointers, call graph extraction is nontrivial. Many commonly used C programs utilize function pointers for efficiency and ease of implementation.
We present different techniques for extracting the call graph in the presence of function pointers. We demonstrate our techniques on several commonly available C programs. Our results show that unless function pointers are taken into account, the call graphs of these programs are erroneously small. We also show that performing a simple, conservative pointer analysis yields call graphs that are too large to be generally useful. However, both filtering of the points-to sets and the use of run-time pointer data can be used to obtain a closer approximation to the true call graph.
[Full text in PDF]