Taint analysis with access paths

Patent metadata

Field	Value
Publication number	US-10789362-B2
Application number	US-201816050160-A
Country	US
Kind code	B2
Filing date	Jul 31, 2018
Priority date	Jul 31, 2018
Publication date	Sep 29, 2020
Grant date	Sep 29, 2020

Abstract

A method that involves generating, for source code, a set of nodes for a set of statements comprising a first statement and a second statement, wherein each node of the set of nodes comprises a dataflow fact and a statement of the set of statements; identifying a source node and a sink node of the set of nodes; determining that the source node is backward reachable from the sink node by analyzing an incoming access path; and, in response to the determination, identifying a potential taint flow from the source node to the sink node.

First claim

What is claimed is:

1. A method being executed on a processor, the method comprising:
generating, for source code, a supergraph comprising a set of nodes for a set of statements comprising a first statement and a second statement,
wherein the supergraph is generated from control flow graph nodes of a control flow graph with as many exploded nodes as dataflow facts exist to form the set of nodes from the exploded nodes, and
wherein each node of the set of nodes comprises a dataflow fact and a statement of the set of statements;

identifying a source node and a sink node of the set of nodes;
identifying an incoming access path comprising a base variable and a set of fields;
determining that the source node is backward reachable from the sink node by analyzing the incoming access path; and
in response to the determination, identifying a potential taint flow from the source node to the sink node.

2. The method of claim 1 , further comprising:
generating a security alert.

3. The method of claim 2 ,
wherein the security alert indicates that the source code is susceptible to one of a structured query language (SQL) injection attack and a cross site scripting (XSS) attack.

4. The method of claim 1 ,
wherein the source node corresponds to the second statement,
wherein the sink node corresponds to the first statement,
wherein the source node is backward reachable from the sink node via a dataflow path through the supergraph, and
wherein the dataflow path includes a number of store statements, load statements, assignment statements, function calls, and function returns.

5. The method of claim 1 , wherein determining whether the source node is backward reachable comprises:
computing a summary when a statement of a node of the set of nodes comprises an inter-procedural call, wherein the statement corresponds to the incoming access path; and
analyzing the statement when the statement does not comprise an inter-procedural call.

6. The method of claim 5 , wherein analyzing the statement comprises:
when the statement is an allocation statement, not propagating the incoming access path,
when the statement is an assignment statement, replacing the base variable of the incoming access path with a second base variable to which a value is assigned by the statement,
when the statement is an assignment statement associated with the source node, replacing the incoming access path with a symbol indicating the presence of potentially tainted data,
when the statement is a load statement, prepending, to the incoming access path, a field of an access path associated with the load statement and replacing the base variable of the incoming access path with a third base variable of an access path of the load statement, and
when the statement is a store statement with a store access path matching a prefix of the incoming access path, replacing the prefix with the stored value.

7. A system comprising:
a memory, coupled to a processor, comprising a repository comprising:
source code comprising a set of statements comprising a first statement and a second statement; and
a supergraph comprising a set of nodes,
wherein the supergraph is generated from control flow graph nodes of a control flow graph with as many exploded nodes as dataflow facts exist to form the set of nodes from the exploded nodes, and
wherein each node of the set of nodes comprises a dataflow fact and a statement of the set of statements; and

an access path propagator executing on the processor and using the memory, configured to:
generate the set of nodes for the set of statements;
identify a source node and a sink node of the set of nodes;
identify an incoming access path comprising a base variable and a set of fields;
determine that the source node is backward reachable from the sink node by analyzing the incoming access path; and
in response to the determination, identify a potential taint flow from the source node to the sink node.

8. The system of claim 7 , further comprising an alert generator executing on the processor configured to:
generate a security alert.

9. The system of claim 8 ,
wherein the security alert indicates that the source code is susceptible to one of a structured query language (SQL) injection attack and a cross site scripting (XSS) attack.

10. The system of claim 7 ,
wherein the source node corresponds to the second statement,
wherein the sink node corresponds to the first statement, and
wherein the source node is backward reachable from the sink node via a dataflow path through Flail the supergraph, and
wherein the dataflow path includes a number of store statements, load statements, assignment statements, function calls, and function returns.

11. The system of claim 7 , further comprising a summarizer executing on the processor and using the memory, configured to:
compute a summary when a statement of a node of the set of nodes comprises an inter-procedural call, wherein the statement corresponds to the incoming access path; and
analyze the statement when the statement does not comprise an inter-procedural call.

12. The system of claim 11 , wherein the access path propagator is further configured to:
when the statement is an allocation statement, not propagate the incoming access path,
when the statement is an assignment statement, replace the base variable of the incoming access path with a second base variable to which a value is assigned by the statement,
when the statement is an assignment statement associated with the source node, replace the incoming access path with a symbol indicating the presence of potentially tainted data,
when the statement is a load statement, prepend, to the incoming access path, a field of an access path associated with the load statement and replace the base variable of the incoming access path with a third base variable of an access path of the load statement, and
when the statement is a store statement with a store access path matching a prefix of the incoming access path, replace the prefix with the stored value.

13. A non-transitory computer readable medium comprising computer readable program code for:
generating, for source code, a supergraph comprising a set of nodes for a set of statements comprising a first statement and a second statement,
wherein the supergraph is generated from control flow graph nodes of a control flow graph with as many exploded nodes as dataflow facts exist to form the set of nodes from the exploded nodes, and
wherein each node of the set of nodes comprises a dataflow fact and a statement of the set of statements;

identifying a source node and a sink node of the set of nodes;
determining that the source node is backward reachable from the sink node by analyzing an incoming access path; and
in response to the determination, identifying a potential taint flow from the source node to the sink node.

14. The non-transitory computer readable medium of claim 13 , further comprising computer readable program code for:
generating a security alert.

15. The non-transitory computer readable medium of claim 14 ,
wherein the security alert indicates that the source code is susceptible to one of a structured query language (SQL) injection attack and a cross site scripting (XSS) attack.

16. The non-transitory computer readable medium of claim 13 ,
wherein the source node corresponds to the second statement,
wherein the sink node corresponds to the first statement,
wherein the source node is backward reachable from the sink node via a dataflow path through the supergraph, and
wherein the dataflo

Assignees

• Oracle Int Corp

Inventors

• Allen Nicholas
• Gauthier Francois
• Jordan Alexander

Classifications

• G06F21/566 Primary

  Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities · CPC title

• G06F8/10

  Requirements analysis; Specification techniques · CPC title

• G06F8/433

  Dependency analysis; Data or control flow analysis · CPC title

• H04L63/1466

  Active attacks involving interception, injection, modification, spoofing of data unit addresses, e.g. hijacking, packet injection or TCP sequence number attacks · CPC title

• G06F21/554

  involving event detection and direct action · CPC title