Where does it go? Refining indirect-call targets with multi-layer type analysis

Kangjie Lu, Hong Hu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationCCS 2019 - Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery
Pages1867-1881
Number of pages15
ISBN (Electronic)9781450367479
DOIs
StatePublished - Nov 6 2019
Event26th ACM SIGSAC Conference on Computer and Communications Security, CCS 2019 - London, United Kingdom
Duration: Nov 11 2019Nov 15 2019

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Conference

Conference26th ACM SIGSAC Conference on Computer and Communications Security, CCS 2019
CountryUnited Kingdom
CityLondon
Period11/11/1911/15/19

    Fingerprint

Keywords

  • CFI
  • Function pointers
  • Indirect-call targets
  • Layered type analysis

Cite this

Lu, K., & Hu, H. (2019). Where does it go? Refining indirect-call targets with multi-layer type analysis. In CCS 2019 - Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (pp. 1867-1881). (Proceedings of the ACM Conference on Computer and Communications Security). Association for Computing Machinery. https://doi.org/10.1145/3319535.3354244