Parallel data flow analysis processing to stage automated vulnerability research

1. A method for data flow analysis, comprising:

obtaining, by a processing circuitry, an execution trace of a software program;

dividing, by the processing circuitry, the execution trace into a plurality of sections, each section identifying a sequence of instructions of the software program;

generating a plurality of definition-and-usage chains, at least some of the definition-and-usage chain being generated by different processors, at least some of the definition-and-usage chains being generated based on different sections of the execution trace, at least two of the definition-and-usage chains being generated in parallel with one another;

combining, by the processing circuitry, the plurality of definition-and-usage chains to produce a data flow graph, the definition-and-usage chains being combined based on information provided by at least one of the processors that are used to generate the definition-and-usage chains, the information indicating one or more unresolved memory locations that are accessed by respective operations corresponding to one or more incomplete usage nodes in the definition-and-usage chains; and

providing, by the processing circuitry, the data flow graph for further use in detecting vulnerabilities in the software program,

wherein any of the unresolved memory locations includes a memory location that is assigned a definition that is at least one of (A) produced by a first operation identified in one of the sections of the execution trace, and retrieved by a second operation identified in another one of the sections of the execution trace or (B) produced by a first operation corresponding to a first node in one of the definition-and-usage chains and retrieved by a second operation corresponding to a second node in another one of the definition-and-usage chains.

2. The method of claim 1 , wherein combining the plurality of definition-and-usage chains includes generating one or more cross-chain edges, each of the cross-chain edges connecting a first node in one of the definition-and-usage chains to a second node in another one of the definition-and-usage chains.

3. The method of claim 1 , wherein combining the plurality of definition-and-usage chains includes generating a data structure that includes a plurality of placeholders for nodes in any of the definition-and-usage chains and resolving each of the placeholders by replacing the placeholder with an identifier of a corresponding node in one of the definition-and-usage chains.

4. The method of claim 1 , wherein any of the incomplete usage nodes includes a first node in a first one of the definition-and-usage chains, the first node corresponding to a first operation that has retrieved a definition generated by a second operation corresponding to a second node in a second one of the definition-and-usage chains.

5. The method of claim 1 , wherein:

any of the unresolved memory locations includes one of a location in random-access memory (RAM) or a memory register;

any of the definition-and-usage chains includes a connected directed acyclic graph,

the data flow graph includes a disconnected directed acyclic graph, and

providing the data flow graph includes one of storing the data flow graph in a memory or transmitting the data flow graph over a communications network.

6. A system comprising:

a memory; and

a processing circuitry operatively coupled to the memory, the processing circuitry being configured to perform the operations of:

obtaining an execution trace of a software program;

dividing the execution trace into a plurality of sections, each section identifying a sequence of instructions of the software program;

generating a plurality of definition-and-usage chains, at least some of the definition-and-usage chain being generated by a different processor, at least some of the definition-and-usage chains being generated based on different sections of the execution trace, at least two of the definition-and-usage chains being generated in parallel with one another;

combining the plurality of definition-and-usage chains to produce a data flow graph, the definition-and-usage chains being combined based on information provided by at least one of the processors that are used to generate the definition-and-usage chains, the information indicating one or more unresolved memory locations that are accessed by respective operations corresponding to one or more incomplete usage nodes in the definition-and-usage chains; and

providing the data flow graph for further use in detecting vulnerabilities in the software program,

wherein any of the unresolved memory locations includes a memory location that is assigned a definition that is at least one of (A) produced by a first operation identified in one of the sections of the execution trace, and retrieved by a second operation identified in another one of the sections of the execution trace or (B) produced by a first operation corresponding to a first node in one of the definition-and-usage chains and retrieved by a second operation corresponding to a second node in another one of the definition-and-usage chains.

7. The system of claim 6 , wherein combining the plurality of definition-and-usage chains includes generating one or more cross-chain edges, each of the cross-chain edges connecting a first node in one of the definition-and-usage chains to a second node in another one of the definition-and-usage chains.

8. The system of claim 6 , wherein combining the plurality of definition-and-usage chains includes generating a data structure that includes a plurality of placeholders for nodes in any of the definition-and-usage chains and resolving each of the placeholders by replacing the placeholder with an identifier of a corresponding node in one of the definition-and-usage chains.

9. The system of claim 6 , wherein any of the incomplete usage nodes includes a first node in a first one of the definition-and-usage chains, the first node corresponding to a first operation that has retrieved a definition generated by a second operation corresponding to a second node in a second one of the definition-and-usage chains.

10. The system of claim 6 , wherein:

any of the unresolved memory locations includes one of a location in random-access memory (RAM) or a memory register;

any of the definition-and-usage chains includes a connected directed acyclic graph,

the data flow graph includes a disconnected directed acyclic graph,

the system includes a computing cluster, and

providing the data flow graph includes one of storing the data flow graph in a memory or transmitting the data flow graph over a communications network.

11. A non-transitory computer-readable medium storing one or more processor-executable instructions, which when executed by at least one processor cause the at least one processor to perform the operations of:

obtaining an execution trace of a software program;

dividing the execution trace into a plurality of sections, each section identifying a sequence of instructions of the software program;

generating a plurality of definition-and-usage chains, at least some of the definition-and-usage chain being generated by different processors, at least some of the definition-and-usage chains being generated based on different sections of the execution trace, at least two of the definition-and-usage chains being generated in parallel with one another;

combining the plurality of definition-and-usage chains to produce a data flow graph, the definition-and-usage chains being combined based on information provided by at least one of the processors that are used to generate the definition-and-usage chains, the information indicating one or more unresolved memory locations that are accessed by respective operations corresponding to one or more incomplete usage nodes in the definition-and-usage chains; and

providing the data flow graph for further use in detecting vulnerabilities in the software program,

wherein any of the unresolved memory locations includes a memory location that is assigned a definition that is at least one of (A) produced by a first operation identified in one of the sections of the execution trace, and retrieved by a second operation identified in another one of the sections of the execution trace or (B) produced by a first operation corresponding to a first node in one of the definition-and-usage chains and retrieved by a second operation corresponding to a second node in another one of the definition-and-usage chains.

12. The non-transitory computer-readable medium of claim 11 , wherein combining the plurality of definition-and-usage chains includes generating one or more cross-chain edges, each of the cross-chain edges connecting a first node in one of the definition-and-usage chains to a second node in another one of the definition-and-usage chains.

13. The non-transitory computer-readable medium of claim 11 , wherein combining the plurality of definition-and-usage chains includes generating a data structure that includes a plurality of placeholders for nodes in any of the definition-and-usage chains and resolving each of the placeholders by replacing the placeholder with an identifier of a corresponding node in one of the definition-and-usage chains.

14. The non-transitory computer-readable medium of claim 11 , wherein any of the incomplete usage nodes includes a first node in a first one of the definition-and-usage chains, the first node corresponding to a first operation that has retrieved a definition generated by a second operation corresponding to a second node in a second one of the definition-and-usage chains.