MATE: hunting for bugs in C and C++ code using Code Property Graphs

by do son · November 22, 2022

MATE

MATE is a suite of tools for interactive program analysis with a focus on hunting for bugs in C and C++ code. MATE unifies application-specific and low-level vulnerability analysis using code property graphs (CPGs), enabling the discovery of highly application-specific vulnerabilities that depend on both implementation details and the high-level semantics of target C/C++ programs.

MATE primarily finds vulnerabilities by static program analysis over the target’s CPG, which combines representations of a program’s syntax, control-flow, and dependencies into a unified graph structure that can be queried to identify potential flaws. The MATE CPG consists of the target’s:

abstract syntax tree (AST)
call graph (CG)
control-flow graph (CFG)
inter-procedural control-flow graph (ICFG)
inter-procedural dataflow-graph (DFG)
control-dependence graph (CDG)
points-to graph (PTG)
source-code to machine-code mapping
memory layout and DWARF type graph

At a very high level, here’s how MATE is used:

The user inputs the source code of a C or C++ program
MATE compiles and analyzes the program, creating one CPG per binary
The user attempts to find vulnerabilities in the program by using the MATE tools

MATE Tools

MATE provides several tools for exploring and analyzing the program’s code property graph (CPG).

Flowfinder

Flowfinder is an interactive, graphical, browser-based user interface for exploring a program’s CPG. Given a potential vulnerability discovered via MATE’s automated analyses, Flowfinder displays relevant fragments of the CPG that explain relationships between program inputs, outputs, and computations. Similar to other program analysis tools such as IDA Pro, Binary Ninja, and angr management, Flowfinder is designed to help answer questions such as “How does this data get from here to there and how is it changed along the way” or “If I can control this buffer, what effect can I have on the execution of the program?” By leveraging the detailed information in the MATE CPG, Flowfinder is intended to enable an interprocedural analysis of program dataflows at a relatively high level of abstraction. Rather than navigating by scrolling or jumping between detailed level views of the program’s disassembly or source code, Flowfinder is designed to support expanding and contracting representations of code and data as needed and creating and manipulating visualizations of high-level flows between different components.

POI Queries

MATE ships with a number of automated analyses that detect potential vulnerabilities, called Points of Interest (POIs). These detectors are written using the MATE Python query API; it’s easy to write additional application-, domain-, or API-specific detectors. Potential vulnerabilities found by these queries can be viewed in Flowfinder for collaboration and triage.

Notebooks

MATE has a Python API for querying the CPG and exposes browser-based, interactive Jupyter notebooks with this query interface pre-loaded. These notebooks can be used to write complex, recursive, whole-program queries that answer detailed questions like “What sequences of function calls can lead from point A to point B in this program?” or “Can user input flow into a memory location with a specific struct type, and from there to some particular function without passing through one of these three sanitization routines?” These notebooks can be used for one-off explorations, or as a platform for users to build reusable apps on the MATE platform (such as UsageFinder).

Under-Constrained Manticore

MATE provides a web UI for exploring programs with the Manticore symbolic execution engine in an under-constrained mode. Unlike traditional symbolic execution which begins at the program entry point and executes until the program exits, under-constrained symbolic execution starts at an arbitrary function. This specificity means that under-constrained symbolic execution can analyze parts of programs that would be too large or complex for traditional symbolic execution.

Symbolic execution enables bit-precise local reasoning about memory and arithmetic, which complements MATE’s higher-level inter-procedural data- and control-flow analyses.