MATE: Merged Analysis To prevent Exploits

DARPA’s Computers and Humans Exploring Software Security (CHESS) program aims to develop capabilities to discover and address vulnerabilities in a scalable, timely, and consistent manner.

Galois has partnered with Harvard University and Trail of Bits to develop MATE, which aims to unify application-specific and low-level vulnerability analysis using code property graphs, enabling the discovery of highly application-specific vulnerabilities that depend on both implementation details and the high-level semantics of target C/C++ programs.

Vulnerability detection today

Currently, large organizations such as the Department of Defense rely on a small but highly-skilled community of security experts to audit and repair vulnerabilities in the ever-growing base of software supporting their enterprise. The tools and techniques that these experts rely on for vulnerability discovery today are lacking. Tools that can discover high-level security flaws are not suitable for widespread application because they produce too many false positives that require substantial effort to triage, and are still only capable of discovering vulnerabilities common to a broad class of applications. Tools that can discover low-level flaws such as memory corruption are still limited in their ability to understand the broader context surrounding those flaws which determine whether or not they have real security impacts. As a result, identifying complex vulnerabilities can take months of effort and the limited availability of talented security experts means critical vulnerabilities often go undetected and unpatched.

MATE

MATE is a source-assisted cyber reasoning system for C/C++ that combines whole-program static analysis with established cyber reasoning techniques for low-level vulnerabilities. MATE aims to reason about high-level program design and implementation flaws with the automation and accuracy of existing cyber reasoning systems, detecting complex vulnerabilities that are beyond the reach of existing cyber reasoning systems.

To prevent users being overwhelmed by false positives, MATE aims to generate Proofs of Vulnerability (PoVs) that demonstrate the exploitability of discovered software flaws. Moreover, MATE will generate targeted patches that correct program behavior where possible or halt the program to prevent compromise. Reasoning at the source level will enable MATE to generate source level patches, which is key to practical adoption of our techniques in commercial software development.

Code property graphs

MATE aims to identify high level vulnerabilities using code property graphs. Code property graphs combine representations of a program’s syntax, control-flow, and dependencies into a unified graph structure that can be queried to identify potential flaws. Analysis of code property graphs has previously been used to identify access control errors, data misuse, API misuse, and logic errors. By first constructing a detailed, high-level representation of the target program, MATE aims to reason about a wide variety of vulnerability classes in parallel and efficiently reuse intermediate analysis results.

Unlike existing systems that use code property graphs, MATE aims to incorporate low-level implementation details extracted from compiled binaries and concrete executions. This additional information will enable the system to identify low-level vulnerabilities and, crucially, vulnerabilities that emerge from the interaction between low-level implementation details and the high-level purpose and design of a program.

MATE aims to address the following vulnerability classes:

• access control errors,
• authentication issues,
• cryptographic issues,
• data misuse,
• logic errors,
• information disclosure,
• memory corruption, and
• resource management errors.

A human-machine approach to detecting vulnerabilities

A distinguishing feature of MATE from past cyber reasoning and bug-finding systems is a hybrid human and machine approach to detecting application-specific vulnerabilities like misuse of security-critical APIs and access control errors. These vulnerabilities require human insight to fill information gaps describing the expected behavior of the program.

MATE will identify specific instances where these insights are required and query human participants to supply the required insight. To reduce the expertise required to answer these queries, MATE will use specification mining and other heuristics to generate candidate rules for how components should be used that can be refined by participants of all skill levels.

MATE will dramatically increase the efficiency of experts by allowing them to focus on understanding expected program behavior. Moreover, these techniques will allow even inexperienced users to find vulnerabilities. MATE will also leverage human insight to improve the scalability and precision of the system and assist in proof of vulnerability generation and patching.

Update: MATE is now open source! Learn more here: https://galoisinc.github.io/MATE/index.html

The project or effort depicted is sponsored by the Air Force Research Laboratory (AFRL) and DARPA under contract FA8750-19-C-0004.  

The views, opinions and/or findings expressed are those of the author and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.