Redefining Indirect Call Analysis with KallGraph

Call graph construction is a crucial prerequisite for a wide range of static analysis applications. State-of-the-art methods minimize precise but expensive pointer tracking by falling back to so-called “type analysis” which scales well to large programs such as the Linux kernel. In this paper, we undertake an in-depth evaluation and analysis of type-based methods that reveal new insights into flaws due to their adhoc nature. First, we find that in a number of cases, the soundness claims of recent type-based methods do not hold, resulting in missing indirect call targets. Second, we find the analysis is overly conservative in multiple aspects, leading to a large number of false indirect call targets. Based on these insights, we make the observation that such type-based methods can be converted into a hybrid pointer analysis framework that unifies the traditional pointer tracking methods and type-based methods. Based on such a framework, we develop a practical indirect call analysis that addresses both soundness and precision limitations. Our results demonstrate a remarkable level of soundness and precision improvements. KallGraph simultaneously improves precision and soundness by pruning up to 90% of indirect call targets and eliminating hundreds to thousands of missed indirect calls. Finally, KallGraph is fully parallelizable and can complete the analysis of Linux kernels in times ranging from tens of minutes to a few hours.