Automatic Inference of Search Patterns for Taint-Style Vulnerabilities

Fabian Yamaguchi, Alwin Maier, Hugo Gascon, Konrad RieckIEEE Symposium on Security and Privacy 2015 · OpenReview

Abstract

Taint-style vulnerabilities are a persistent problem in software development, as the recently discovered "Heartbleed" vulnerability strikingly illustrates. In this class of vulnerabilities, attacker-controlled data is passed unsanitized from an input source to a sensitive sink. While simple instances of this vulnerability class can be detected automatically, more subtle defects involving data flow across several functions or project-specific APIs are mainly discovered by manual auditing. Different techniques have been proposed to accelerate this process by searching for typical patterns of vulnerable code. However, all of these approaches require a security expert to manually model and specify appropriate patterns in practice. In this paper, we propose a method for automatically inferring search patterns for taint-style vulnerabilities in C code. Given a security-sensitive sink, such as a memory function, our method automatically identifies corresponding source-sink systems and constructs patterns that model the data flow and sanitization in these systems. The inferred patterns are expressed as traversals in a code property graph and enable efficiently searching for unsanitized data flows -- across several functions as well as with project-specific APIs. We demonstrate the efficacy of this approach in different experiments with 5 open-source projects. The inferred search patterns reduce the amount of code to inspect for finding known vulnerabilities by 94.9% and also enable us to uncover 8 previously unknown vulnerabilities.

Introduction

Security researchers frequently hunt for taint-style vulnerabilities: scenarios where attacker-controlled data (the "source") reaches a sensitive function (the "sink," such as memcpy or sprintf) without undergoing proper sanitization. While basic instances are detectable with standard tools, modern software complexity—spanning multiple functions and utilizing project-specific APIs—often necessitates manual auditing. This process is traditionally slow, error-prone, and requires deep domain expertise.

This paper addresses this challenge by proposing a method to automatically infer search patterns from the codebase itself. By "learning" how a specific project handles data and identifying outliers where standard sanitization is missing, the system automates the generation of complex security queries.

Methodology: The Code Property Graph

The foundation of this approach is the Code Property Graph (CPG). The CPG is a unified data structure that merges Abstract Syntax Trees (AST), Control Flow Graphs (CFG), and Program Dependence Graphs (PDG) into a single, searchable graph database. This integration allows for complex queries that simultaneously consider syntax, execution paths, and data dependencies.

The Code Property Graph (CPG) integrates AST, CFG, and PDG edges to track data flow and control dependencies across function calls.

Interprocedural Extension and Pattern Inference

To track data flow across function boundaries, the authors enhanced the CPG with interprocedural analysis. A key challenge is identifying when a function call modifies its arguments (e.g., a read() call defining a buffer's content). The system employs Post-Dominator Trees to heuristically identify these definitions and the conditions governing them.

Post-dominator analysis helps identify when function calls modify arguments and the predicates that control execution flow.

The inference process involves several key steps:

  1. Extraction of Definition Graphs: For a given sink, the system extracts "slices" of code showing argument definitions and applied sanitizers.
  2. Clustering for Generalization: Using complete-linkage clustering, the system groups similar call sites to identify common "templates" for function usage.
  3. Automatic Traversal Generation: Clusters are converted into Gremlin graph traversals, which can then be executed against the entire codebase to find instances where expected sanitization patterns are absent.

Experimental Evaluation

The method was evaluated on five prominent open-source C projects: the Linux Kernel (3.11.4), OpenSSL (1.1.0f), Pidgin (2.10.7), VLC Media Player (2.0.1), and Poppler/Xpdf (0.24.1). These projects were selected for their maturity and history of subtle security defects.

Key Results

  • Audit Efficiency: The inferred patterns reduced the manual inspection workload by an average of 94.9%.
  • Heartbleed Detection: In OpenSSL, the tool analyzed 738 memcpy calls and narrowed the search to just 7 candidates, two of which were the Heartbleed vulnerability.
  • Vulnerability Discovery: The system uncovered 8 previously unknown vulnerabilities (including 5 in VLC), which have since been reported and fixed.
  • Performance: Pattern generation for large-scale projects took between 12 and 230 seconds, with search execution completing in seconds.

Discussion and Future Work

The core insight of this work is that vulnerabilities are often outliers—locations where a developer omitted a check present in the vast majority of similar call sites. By learning project-specific "sources" and "sanitizers" directly from the code, the tool avoids the limitations of hardcoded rule sets.

However, limitations remain. The method requires at least some correct sanitization examples to learn from. Furthermore, the current implementation does not track data flow through global variables or handle dynamic function calls effectively. Future work may involve integrating dynamic analysis to resolve these paths and extending support to other programming languages.

Summary updated

Abstract

Taint-style vulnerabilities are a persistent problem in software development, as the recently discovered "Heart bleed" vulnerability strikingly illustrates. In this class of vulnerabilities, attacker-controlled data is passed unsanitized from an input source to a sensitive sink. While simple instances of this vulnerability class can be detected automatically, more subtle defects involving data flow across several functions or project-specific APIs are mainly discovered by manual auditing. Different techniques have been proposed to accelerate this process by searching for typical patterns of vulnerable code. However, all of these approaches require a security expert to manually model and specify appropriate patterns in practice. In this paper, we propose a method for automatically inferring search patterns for taint-style vulnerabilities in C code. Given a security-sensitive sink, such as a memory function, our method automatically identifies corresponding source-sink systems and constructs patterns that model the data flow and sanitization in these systems. The inferred patterns are expressed as traversals in a code property graph and enable efficiently searching for unsanitized data flows -- across several functions as well as with project-specific APIs. We demonstrate the efficacy of this approach in different experiments with 5 open-source projects. The inferred search patterns reduce the amount of code to inspect for finding known vulnerabilities by 94.9% and also enable us to uncover 8 previously unknown vulnerabilities.
BibTeX
@inproceedings{yamaguchi2015automatic,
  author = {Fabian Yamaguchi and Alwin Maier and Hugo Gascon and Konrad Rieck},
  title = {{Automatic Inference of Search Patterns for Taint-Style Vulnerabilities}},
  booktitle = {IEEE Symposium on Security and Privacy},
  year = {2015},
  url = {https://openreview.net/forum?id=cbHYrW1YZUMT},
}
Figure