# US 2021/0232377 A1 · Encoding dependencies in call graphs

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

- Number: US 2021/0232377 A1
- Document ID: US20210232377A1
- Status: Published application
- Kind: A1
- Application number: 16/775,120
- Filed: 2020-01-28
- Published: 2021-07-29
- Earliest claimed: 2020-01-28
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Sora Bae; Nathan Robert Albert Keynes; Cristina Cifuentes
- Web page: https://patentgrep.com/patent/US20210232377A1

## CPC

- G06F 8/433: {Dependency analysis; Data or control flow analysis}
- G06F 21/52: during program execution, e.g. stack integrity {; Preventing unwanted data erasure; Buffer overflow}
- G06F 21/51: at application loading time, e.g. accepting, rejecting, starting or inhibiting executable software based on integrity or source reliability
- G06F 21/563: {by source code analysis}
- G06F 21/577: {Assessing vulnerabilities and evaluating computer system security}
- G06F 2221/033: Test or assess software
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for modifying a call graph may include identifying, in source code, a first call site including a first predicate and a call from a first function to a second function. The first call site may correspond to a first edge of the call graph. The first edge may connect a first node corresponding to the first function and a second node corresponding to the second function. The method may further include modifying the call graph by labelling the first edge with a first encoding of the first predicate, and identifying, in the source code, a second call site including a second predicate and a call from a third function to the first function. The method may further include in response to determining that the first predicate is unsatisfied, modifying the call graph by labelling the second edge with a second encoding of a violation of the first predicate.

## Claims

### Claim 1

A method for modifying a call graph, comprising:
identifying, in source code, a first call site comprising a first predicate and a call from a first function to a second function, the first call site corresponding to a first edge of the call graph, the first edge connecting a first node corresponding to the first function and a second node corresponding to the second function, the first predicate comprising a Boolean expression, the call graph generated for the source code;
modifying the call graph by labelling the first edge with a first encoding of the first predicate;
identifying, in the source code, a second call site comprising a second predicate and a call from a third function to the first function, the second call site corresponding to a second edge of the call graph;
determining, using the second call site, that the first predicate is unsatisfied; and
in response to determining that the first predicate is unsatisfied, modifying the call graph by labelling the second edge with a second encoding of a violation of the first predicate.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
determining, using the modified call graph, the feasibility of a call path comprising the second function.

### Claim 3 (depends on 2)

The method of claim 2, wherein determining the feasibility of the call path comprises:
determining whether the call path comprises an edge labeled with an encoding of a predicate and an edge labeled with an encoding of a violation of the predicate.

### Claim 4 (depends on 2)

The method of claim 2, further comprising:
detecting a taint flow in response to determining the feasibility of the call path, wherein the call path comprises a potentially tainted function, and wherein the second function is security-sensitive.

### Claim 5 (depends on 2)

The method of claim 2, further comprising:
receiving a query based on the second function, wherein the feasibility of the call path is determined in response to receiving the query.

### Claim 6 (depends on 1)

The method of claim 1, wherein the first predicate comprises a parameter, wherein the third function calls the first function with an argument, and wherein determining that the first predicate is unsatisfied comprises:
modifying the first predicate by replacing the parameter with the argument to obtain a modified first predicate; and
determining that the conjunction of the modified first predicate and the second predicate is unsatisfied.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
recursively modifying the call graph by adding, to a worklist, a plurality of nodes of the call graph.

### Claim 8 (depends on 1)

The method of claim 1, wherein the first encoding is based on a location of the first predicate in the source code.

### Claim 9

A system for modifying a call graph, comprising:
a computer processor;
a repository configured to store:
source code comprising:
a first call site comprising a first predicate and a call from a first function to a second function, the first call site corresponding to a first edge of the call graph, the first edge connecting a first node corresponding to the first function and a second node corresponding to the second function, the first predicate comprising a Boolean expression, and
a second call site comprising a second predicate and a call from a third function to the first function, the second call site corresponding to a second edge of the call graph,
wherein the call graph is generated for the source code;
a constraint solver, executing on the computer processor and configured to determine, using the second call site, that the first predicate is unsatisfied; and
a code analyzer, executing on the computer processor and configured to:
identify, in the source code, the first call site,
modify the call graph by labelling the first edge with a first encoding of the first predicate,
identifying, in the source code, the second call site, and
in response to determining that the first predicate is unsatisfied, modify the call graph by labelling the second edge with a second encoding of a violation of the first predicate.

### Claim 10 (depends on 9)

The system of claim 9, wherein the system further comprises a path analyzer, executing on the computer processor and configured to determine, using the modified call graph, the feasibility of a call path comprising the second function.

### Claim 11 (depends on 10)

The system of claim 10, wherein the path analyzer is further configured to:
determine whether the call path comprises an edge labeled with a predicate and an edge labeled with a violation of the predicate.

### Claim 12 (depends on 10)

The system of claim 10, wherein the code analyzer is further configured to:
detect a taint flow in response to determining the feasibility of the call path, wherein the call path comprises a potentially tainted function, and wherein the second function is security-sensitive.

### Claim 13 (depends on 10)

The system of claim 10, further comprising a graphical user interface (GUI), executing on the computer processor and configured to:
receive a query based on the second function,
wherein the path analyzer determines the feasibility of the call path in response to receiving the query.

### Claim 14 (depends on 9)

The system of claim 9, wherein the constraint solver is further configured to determine that the first predicate is unsatisfied by:
modifying the first predicate by replacing the parameter with the argument to obtain a modified first predicate, and
determining that the conjunction of the modified first predicate and the second predicate is unsatisfied.

### Claim 15 (depends on 9)

The system of claim 9, wherein the code analyzer is further configured to:
recursively modify the call graph by adding, to a worklist, a plurality of nodes of the call graph.

### Claim 16

A non-transitory computer readable medium comprising instructions that, when executed by a computer processor, perform:
identifying, in source code, a first call site comprising a first predicate and a call from a first function to a second function, the first call site corresponding to a first edge of the call graph, the first edge connecting a first node corresponding to the first function and a second node corresponding to the second function, the first predicate comprising a Boolean expression, the call graph generated for the source code;
modifying the call graph by labelling the first edge with a first encoding of the first predicate;
identifying, in the source code, a second call site comprising a second predicate and a call from a third function to the first function, the second call site corresponding to a second edge of the call graph;
determining, using the second call site, that the first predicate is unsatisfied; and
in response to determining that the first predicate is unsatisfied, modifying the call graph by labelling the second edge with a second encoding of a violation of the first predicate.

### Claim 17 (depends on 16)

The non-transitory computer readable medium of claim 16, wherein the instructions further perform:
determining, using the modified call graph, the feasibility of a call path comprising the second function.

### Claim 18 (depends on 17)

The non-transitory computer readable medium of claim 17, wherein determining the feasibility of the call path comprises:
determining whether the call path comprises an edge labeled with an encoding of a predicate and an edge labeled with an encoding of a violation of the predicate.

### Claim 19 (depends on 17)

The non-transitory computer readable medium of claim 17, wherein the instructions further perform:
detecting a taint flow in response to determining the feasibility of the call path, wherein the call path comprises a potentially tainted function, and wherein the second function is security-sensitive.

### Claim 20 (depends on 16)

The non-transitory computer readable medium of claim 16, wherein the first predicate comprises a parameter, wherein the third function calls the first function with an argument, and wherein determining that the first predicate is unsatisfied comprises:
modifying the first predicate by replacing the parameter with the argument to obtain a modified first predicate; and
determining that the conjunction of the modified first predicate and the second predicate is unsatisfied.
