Abstract
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 |
| Pages | 1867-1881 |
| Number of pages | 15 |
| ISBN (Electronic) | 9781450367479 |
| DOIs | |
| 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 |
Publication series
| Name | Proceedings of the ACM Conference on Computer and Communications Security |
|---|---|
| ISSN (Print) | 1543-7221 |
Conference
| Conference | 26th ACM SIGSAC Conference on Computer and Communications Security, CCS 2019 |
|---|---|
| Country/Territory | United Kingdom |
| City | London |
| Period | 11/11/19 → 11/15/19 |
Bibliographical note
Funding 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.
Publisher Copyright:
© 2019 Association for Computing Machinery.
Keywords
- CFI
- Function pointers
- Indirect-call targets
- Layered type analysis