System software commonly uses indirect calls to realize dynamic program behaviors. However, indirect-calls also bring challenges to constructing a precise control-flow graph that is a standard prerequisite for many static program-analysis and system-hardening techniques. Unfortunately, identifying indirect-call targets is a hard problem. In particular, modern compilers do not recognize indirect-call targets by default. Existing approaches identify indirect-call targets based on type analysis that matches the types of function pointers and the ones of address-taken functions. Such approaches, however, suffer from a high false-positive rate as many irrelevant functions may share the same types. In this paper, we propose a new approach, namely Multi-Layer Type Analysis (MLTA), to effectively refine indirect-call targets for C/C++ programs. MLTA relies on an observation that function pointers are commonly stored into objects whose types have a multilayer type hierarchy; before indirect calls, function pointers will be loaded from objects with the same type hierarchy “layer by layer”. By matching the multi-layer types of function pointers and functions, MLTA can dramatically refine indirect-call targets. MLTA is effective because multi-layer types are more restrictive than single-layer types. It does not introduce false negatives by conservatively tracking targets propagation between multi-layer types, and the layered design allows MLTA to safely fall back whenever the analysis for a layer becomes infeasible. We have implemented MLTA in a system, namely TypeDive, based on LLVM and extensively evaluated it with the Linux kernel, the FreeBSD kernel, and the Firefox browser. Evaluation results show that TypeDive can eliminate 86% to 98% more indirect-call targets than existing approaches do, without introducing new false negatives. We also demonstrate that TypeDive not only improves the scalability of static analysis but also benefits semantic-bug detection. With TypeDive, we have found 35 new deep semantic bugs in the Linux kernel.
|Original language||English (US)|
|Title of host publication||CCS 2019 - Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security|
|Publisher||Association for Computing Machinery|
|Number of pages||15|
|State||Published - Nov 6 2019|
|Event||26th ACM SIGSAC Conference on Computer and Communications Security, CCS 2019 - London, United Kingdom|
Duration: Nov 11 2019 → Nov 15 2019
|Name||Proceedings of the ACM Conference on Computer and Communications Security|
|Conference||26th ACM SIGSAC Conference on Computer and Communications Security, CCS 2019|
|Period||11/11/19 → 11/15/19|
Bibliographical noteFunding Information:
We thank the anonymous reviewers for their helpful feedback. Kangjie Lu was supported in part by the NSF award CNS-1815621. Hong Hu was supported in part by the ONR under grants N00014-17-1-2895 and N00014-18-1-2662. Any opinions, findings, conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of NSF or ONR.
- Function pointers
- Indirect-call targets
- Layered type analysis