Unleashing the Power of Type-Based Call Graph Construction by Using Regional Pointer Information

When dealing with millions of lines of C code, we still cannot have the cake and eat it: type analysis for call graph construction is scalable yet highly imprecise. We address this precision issue through a practical observation: many function pointers are simple; they are not referenced by other pointers, nor do they derive their values by dereferencing other pointers. As a result, simple function pointers can be resolved with precise and affordable pointer aliasing information. In this work, we advocate Kelp with two concerted stages. First, instead of directly using type analysis, Kelp performs regional pointer analysis along def-use chains to early and precisely resolve the indirect calls through simple function pointers. Second, Kelp then leverages type analysis to handle the remaining indirect calls. The first stage is efficient as Kelp selectively reasons about simple function pointers, thereby avoiding prohibitive performance penalties. The second stage is precise as the candidate address-taken functions for checking type compatibility are largely reduced thanks to the first stage. Our experiments on twenty large-scale and popular software programs show that, on average, Kelp can reduce spurious callees by 54.2% with only a negligible additional time cost of 8.5% (equivalent to 6.3 seconds) compared to the previous approach. More excitingly, when evaluating the call graphs through the lens of three various downstream clients (i.e., thread-sharing analysis, value-flow bug detection, and directed grey-box fuzzing), Kelp can significantly enhance their effectiveness for better vulnerability understanding, hunting, and reproduction.