# US 2021/0279338 A1 · Graph-based source code vulnerability detection system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0279338 A1
- Document ID: US20210279338A1
- Status: Published application
- Kind: A1
- Application number: 17/192,249
- Filed: 2021-03-04
- Published: 2021-09-09
- Earliest claimed: 2020-03-04
- Assignees: The George Washington University
- Applicants: The George Washington University
- Inventors: Benjamin Bowman; H. Howie Huang
- Web page: https://patentgrep.com/patent/US20210279338A1

## CPC

- G06F 21/577: {Assessing vulnerabilities and evaluating computer system security}
- G06F 8/30: Creation or generation of source code
- G06F 8/71: Version control (security arrangements therefor G06F21/57); Configuration management
- G06F 8/75: Structural analysis for program understanding
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F 2221/033: Test or assess software
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The graph-based source code vulnerability detection system that uses a code-similarity style technique to identify highly modified vulnerable code clones while remaining generic to all vulnerability types. The system abstracts vulnerabilities in source code to the graph domain, allowing it to identify key relationships between textual elements that are not directly discernible from the text alone. Additionally, the system analyzes the patched code in addition to the vulnerable code to identify specific relationships in the graph that are tied directly to the vulnerable code segment, the patched code segment, and the contextual code of a particular vulnerability. By separating the vulnerability representation into these three components, a matching algorithm identifies vulnerable code clones while tolerating modifications at each level independently, providing more robust detection of modified vulnerable code clones.

## Claims

### Claim 1

A method of determining whether target source code is likely to have a vulnerability, the method comprising:
identifying a vulnerable source code function having the vulnerability;
identifying a patched source code function representing the vulnerable source code function with the vulnerability having been patched;
generating a vulnerable code graph of the vulnerable source code function;
generating a patched code graph of the patched source code function;
converting the vulnerable code graph into vulnerable code property triplets;
converting the patched code property graph into patched code property triplets;
comparing the vulnerable code property triplets and the patched code property triplets to generate a vulnerability graph comprising:
positive triplets, found in the vulnerable code graph, that are not found in the patched code graph;
negative triplets, found in the patched code graph, that are not found in the vulnerable code graph; and
context triplets found in both the vulnerable code graph and the patched code graph;
generating a target code graph of the target source code;
converting the target code property graph into target triplets;
determining whether the target source code is likely to have the vulnerability by comparing the target triplets to the positive triplets, the negative triplets, and the context triplets.

### Claim 2 (depends on 1)

The method of claim 1, wherein identifying the vulnerable source code function comprises:
searching log messages of a source code repository having a version control system and log messages to identify a log message referring to the vulnerability; and
identifying a vulnerable source code version prior to the log message referring to the vulnerability.

### Claim 3 (depends on 2)

The method of claim 2, wherein identifying the patched source code function comprises identifying the patched source code version having the log message referring to the vulnerability.

### Claim 4 (depends on 3)

The method of claim 3, wherein identifying the vulnerable source code function and identifying the patched source code function further comprises parsing the vulnerable source code version and the patched source code version to identify a function that was patched.

### Claim 5 (depends on 1)

The method of claim 1, wherein generating each of the vulnerable code graph, the patched code graph, and the target code graph comprises:
generating an abstract syntax tree representing the abstract structure of the vulnerable source code function, the patched source code function, or the target source code; and
using the abstract syntax tree to identify a plurality of nodes, each node having a node property label identifying one of a plurality of node types, and directed edges between the nodes.

### Claim 6 (depends on 5)

The method of claim 5, wherein generating each of the vulnerable code graph, the patched code graph, and the target code graph further comprises:
generating a flow control graph representing the paths that may be traversed during execution of the vulnerable source code function, the patched source code function, or the target source code;
using the flow control graph to add flow control information to the nodes of the code property graph;
generating a program dependence graph representing the program dependence and the control dependence of the vulnerable source code function, the patched source code function, or the target source code; and
using the program dependence graph add information regarding the program dependence and the control dependence to the code property graph.

### Claim 7 (depends on 1)

The method of claim 1, wherein each of the vulnerable code property triplets, the patched code property triplets, and the target triplets include a source node, a destination node, and a relationship between the source node and the destination node.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
storing a dataset of vulnerability graphs generated using a plurality of vulnerable source code functions having a plurality of vulnerabilities and a plurality of patched source code functions; and
determining whether the target source code is likely to have one of the plurality of vulnerabilities by comparing the target triplets generated using the target source code to the dataset of vulnerability graphs.

### Claim 9

A graph-based source code vulnerability detection system, comprising:
a vulnerability mining module that:
identifies a vulnerable source code function having a vulnerability; and
identifies a patched source code function representing the vulnerable source code function with the vulnerability having been patched;
a graph generation module that:
generates a vulnerable code graph of the vulnerable source code function;
generates a patched code graph of the patched source code function; and
generates a target code graph of target source code;
a triplet sampling module that:
converts the vulnerable code graph into vulnerable code property triplets;
converts the patched code property graph into patched code property triplets; and
converts the target code property graph into target triplets;
a vulnerability graph generation module that compares the vulnerable code property triplets and the patched code property triplets to generate:
positive triplets, found in the vulnerable code graph, that are not found in the patched code graph;
negative triplets, found in the patched code graph, that are not found in the vulnerable code graph; and
context triplets found in both the vulnerable code graph and the patched code graph; and
a triplet matcher that determines whether the target source code is likely to have the vulnerability by comparing the target triplets to the positive triplets, the negative triplets, and the context triplets.

### Claim 10 (depends on 9)

The system of claim 9, wherein the vulnerability mining module identifies the vulnerable source code function by:
searching log messages of a source code repository having a version control system and log messages to identify a log message referring to the vulnerability; and
identifying a vulnerable source code version prior to the log message referring to the vulnerability.

### Claim 11 (depends on 10)

The system of claim 10, wherein the vulnerability mining module identifies the patched source code function by identifying the patched source code version having the log message referring to the vulnerability.

### Claim 12 (depends on 11)

The system of claim 11, wherein the vulnerability mining module identifies the vulnerable source code function and the patched source code function further by parsing the vulnerable source code version and the patched source code version to identify a function that was patched.

### Claim 13 (depends on 9)

The system of claim 9, wherein the graph generation module generates each of the vulnerable code graph, the patched code graph, and the target code graph by:
generating an abstract syntax tree representing the abstract structure of the vulnerable source code function, the patched source code function, or the target source code; and
using the abstract syntax tree to identify a plurality of nodes, each node having a node property label identifying one of a plurality of node types, and directed edges between the nodes.

### Claim 14 (depends on 13)

The system of claim 13, wherein the graph generation module generates each of the vulnerable code graph, the patched code graph, and the target code graph further by:
generating a flow control graph representing the paths that may be traversed during execution of the vulnerable source code function, the patched source code function, or the target source code;
using the flow control graph to add flow control information to the nodes of the code property graph;
generating a program dependence graph representing the program dependence and the control dependence of the vulnerable source code function, the patched source code function, or the target source code; and
using the program dependence graph add information regarding the program dependence and the control dependence to the code property graph.

### Claim 15 (depends on 9)

The system of claim 9, wherein each of the vulnerable code property triplets, the patched code property triplets, and the target triplets include a source node, a destination node, and a relationship between the source node and the destination node.

### Claim 16 (depends on 9)

The system of claim 9, further comprising:
a database of vulnerability graphs generated using a plurality of vulnerable source code functions having a plurality of vulnerabilities and a plurality of patched source code functions,
wherein the triplet matcher determines whether the target source code is likely to have one of the plurality of vulnerabilities by comparing the target triplets generated using the target source code to the dataset of vulnerability graphs.

### Claim 17

Non-transitory computer readable storage media (CRSM) storing instructions that, when executed by a computer processor, cause a graph-based source code vulnerability detection system to:
identify a vulnerable source code function having a vulnerability;
identify a patched source code function representing the vulnerable source code function with the vulnerability having been patched;
generate a vulnerable code graph of the vulnerable source code function;
generate a patched code graph of the patched source code function;
convert the vulnerable code graph into vulnerable code property triplets;
convert the patched code property graph into patched code property triplets;
compare the vulnerable code property triplets and the patched code property triplets to generate a vulnerability graph comprising:
positive triplets, found in the vulnerable code graph, that are not found in the patched code graph;
negative triplets, found in the patched code graph, that are not found in the vulnerable code graph; and
context triplets found in both the vulnerable code graph and the patched code graph;
generate a target code graph of target source code;
convert the target code property graph into target triplets;
determine whether the target source code is likely to have the vulnerability by comparing the target triplets to the positive triplets, the negative triplets, and the context triplets.

### Claim 18 (depends on 17)

The CRSM of claim 17, wherein the instructions cause the system to generate each of the vulnerable code graph, the patched code graph, and the target code graph by:
generating an abstract syntax tree representing the abstract structure of the vulnerable source code function, the patched source code function, or the target source code;
using the abstract syntax tree to identify a plurality of nodes, each node having a node property label identifying one of a plurality of node types, and directed edges between the nodes;
generating a flow control graph representing the paths that may be traversed during execution of the vulnerable source code function, the patched source code function, or the target source code;
using the flow control graph to add flow control information to the nodes of the code property graph;
generating a program dependence graph representing the program dependence and the control dependence of the vulnerable source code function, the patched source code function, or the target source code; and
using the program dependence graph add information regarding the program dependence and the control dependence to the code property graph.

### Claim 19 (depends on 17)

The CRSM of claim 17, wherein each of the vulnerable code property triplets, the patched code property triplets, and the target triplets include a source node, a destination node, and a relationship between the source node and the destination node.

### Claim 20 (depends on 17)

The CRSM of claim 17, wherein the instructions further cause the system to determine whether the target source code is likely to have one of a plurality of vulnerabilities by comparing the target triplets generated using the target source code to a dataset of vulnerability graphs generated using a plurality of vulnerable source code functions having a plurality of vulnerabilities and a plurality of patched source code functions.
