A Cocktail Approach to Practical Call Graph Construction
Proceedings of the ACM on Programming Languages · 16.10.2023 · 7 (OOPSLA2) · 1001-1033
DOI: 10.1145/3622833 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 16.10.2023. Verfasst von Yuandao Cai und 1 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 114 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
After decades of research, constructing call graphs for modern C-based software remains either imprecise or inefficient when scaling up to the ever-growing complexity. The main culprit is the difficulty of resolving function pointers, as precise pointer analyses are cubic in nature and become exponential when considering calling contexts. This paper takes a practical stance by first conducting a comprehensive empirical study of function pointer manipulations in the wild. By investigating 5355 indirect calls in five popular open-source systems, we conclude that, instead of the past uniform treatments for function pointers, a cocktail approach can be more effective in “squeezing” the number of difficult pointers to a minimum using a potpourri of cheap methods. In particular, we decompose the costs of constructing highly precise call graphs of big code by tailoring several increasingly precise algorithms and synergizing them into a concerted workflow. As a result, many indirect calls can be precisely resolved in an efficient and principled fashion, thereby reducing the final, expensive refinements. This is, in spirit, similar to the well-known cocktail medical therapy. The results are encouraging — our implemented prototype called Coral can achieve similar precision versus the previous field-, flow-, and context-sensitive Andersen-style call graph construction, yet scale up to millions of lines of code for the first time, to the best of our knowledge. Moreover, by evaluating the produced call graphs through the lens of downstream clients (i.e., use-after-free detection, thin slicing, and directed grey-box fuzzing), the results show that Coral can dramatically improve their effectiveness for better vulnerability hunting, understanding, and reproduction. More excitingly, we found twelve confirmed bugs (six impacted by indirect calls) in popular systems (e.g., MariaDB), spreading across multiple historical versions.
Zitieren
APA
Cai, Y., & Zhang, C. (2023). A Cocktail Approach to Practical Call Graph Construction. Proceedings of the ACM on Programming Languages, 7(OOPSLA2), 1001-1033. https://doi.org/10.1145/3622833
Vancouver
Cai Y, Zhang C. A Cocktail Approach to Practical Call Graph Construction. Proceedings of the ACM on Programming Languages. 2023;7(OOPSLA2):1001-1033. doi:10.1145/3622833
BibTeX
@article{Cai2023,
author = {Cai, Yuandao and Zhang, Charles},
title = {A Cocktail Approach to Practical Call Graph Construction},
journal = {Proceedings of the ACM on Programming Languages},
year = {2023},
volume = {7},
number = {OOPSLA2},
pages = {1001--1033},
doi = {10.1145/3622833}
}
EUVIMED