一句话：将多种精度递增的函数指针解析算法协同编排成工作流，在近似精度下首次把高精度调用图扩展到数百万行 C 代码。
针对现代 C 软件调用图构建在精度与可扩展性上的两难，本文首先对五个流行开源系统中的 5355 处间接调用进行实证研究，发现函数指针的使用模式多样，过去的统一处理并不划算。基于此，作者提出「鸡尾酒」式方法：把多个精度递增的函数指针解析算法协同编排为统一工作流，先用各类廉价方法尽可能精确地消解间接调用，只把真正困难的少数指针留给昂贵的上下文敏感精化，其思想类似医学上的鸡尾酒疗法。原型系统 Coral 在达到与 field-/flow-/context-sensitive Andersen 风格分析相近精度的同时，首次将此类高精度调用图扩展到数百万行代码。在 use-after-free 检测、thin slicing 与定向灰盒模糊测试等下游客户端上，Coral 显著提升效果，并在 MariaDB 等流行系统中发现 12 个已确认缺陷（其中 6 个受间接调用影响），跨越多个历史版本。
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.
@article{paperbot1829,
title = {A Cocktail Approach to Practical Call Graph Construction},
author = {Yuandao Cai and Charles Zhang},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {OOPSLA2},
year = {2023},
doi = {10.1145/3622833}
}