Alias analysis using labelled access paths

Patent metadata

Field	Value
Publication number	US-11847044-B2
Application number	US-202117469713-A
Country	US
Kind code	B2
Filing date	Sep 8, 2021
Priority date	Sep 8, 2021
Publication date	Dec 19, 2023
Grant date	Dec 19, 2023

Abstract

A method may include detecting a first sub-flow, by executing a local defect analysis on code starting at a sink instruction, to a load instruction performing reading a first value using a first variable. The first sub-flow may include a first label of a first defect. The method may further include detecting a second sub-flow, by executing the local defect analysis on the code starting at a store instruction, to a load instruction performing writing a second value using a second variable. The second sub-flow may include a second label of a second defect. The method may further include determining that the first variable and the second variable are potential aliases by determining that the first label matches the second label, and obtaining, based on determining that the first variable and the second variable are potential aliases, a nonlocal flow by connecting the first sub-flow and the second sub-flow.

First claim

What is claimed is:

1. A method for executing a nonlocal defect analysis on code, comprising:
propagating, through the code, a first access path to a first series of instructions starting at a sink instruction until a load instruction is reached to identify a first sub-flow, the first access path comprising a first sequence of field identifiers,
wherein the sink instruction uses a first value of a first variable,
wherein the load instruction reads the first value using the first variable from a nonlocally accessible data structure, and
wherein the first sub-flow comprises a first label of a first defect;

propagating, through the code, a second access path to a second series of instructions starting at a store instruction until a source instruction is reached to identify a second sub-flow, the second access path comprising a second sequence of field identifiers,
wherein the store instruction writes a second value using a second variable to the nonlocally accessible data structure, and
wherein the second sub-flow comprises a second label of a second defect;

comparing, to obtain a match, the first label with the second label and comparing each field identifier in the first access path with a corresponding field identifier in the second access path, the match indicating that the first variable and the second variable are potential aliases referring to a same value in the nonlocally accessible data structure; and
generating a nonlocal flow connecting the first sub-flow and the second sub-flow responsive to the match wherein sub-flows comprising labels failing to match are excluded from nonlocal flow analysis.

2. The method of claim 1 , further comprising:
generating a report describing the first defect and the nonlocal flow.

3. The method of claim 1 , further comprising determining that the first sequence of field identifiers is a prefix of the second sequence of field identifiers.

4. The method of claim 1 , further comprising:
determining the first label using the sink instruction;
in response to determining the first label, adding the first label to the first sub-flow;
determining the second label using the source instruction; and
in response to determining the second label, adding the second label to the second sub-flow.

5. The method of claim 1 ,
wherein propagating the first access path is part of a taint analysis, and
wherein the first label and the second label are selected from a group consisting of code injection and cross-site scripting.

6. The method of claim 1 , further comprising:
determining that the first sub-flow excludes a modifier instruction performing: modifying the first value before the first variable reads the first value, wherein the modifier instruction corresponds to the first defect.

7. A system for executing a nonlocal defect analysis on code, comprising:
a computer processor;
a repository configured to store the code comprising a sink instruction, a source instruction, a load instruction, and a store instruction,
wherein the sink instruction uses a first value of a first variable,
wherein the load instruction reads the first value using the first variable from a nonlocally accessible data structure, and
wherein the store instruction writes a second value using a second variable to the nonlocally accessible data structure; and

a nonlocal flow detector, executing on the computer processor and configured to:
propagate, through the code, a first access path to a first series of instructions starting at the sink instruction until the load instruction is reached to identify a first sub-flow, the first access path comprising a first sequence of field identifiers,
wherein the first sub-flow comprises a first label of a first defect, propagate, through the code, a second access path to a second series of instructions starting at the store instruction until the source instruction is reached to identify a second sub-flow, the second access path comprising a second sequence of field identifiers,
wherein the second sub-flow comprises a second label of a second defect,

compare, to obtain a match, the first label and the second label and compare each field identifier in the first access path with a corresponding field identifier in the second access path, the match indicating that the first variable and the second variable are potential aliases referring to a same value in the nonlocally accessible data structure, and
generate a nonlocal flow connecting the first sub-flow and the second sub-flow responsive to the match,
wherein sub-flows comprising labels failing to match are excluded from nonlocal flow analysis.

8. The system of claim 7 , wherein the nonlocal flow detector is further configured to:
generate a report describing the first defect and the nonlocal flow.

9. The system of claim 7 , wherein the nonlocal flow detector is further configured to determine that the first sequence of field identifiers is a prefix of the second sequence of field identifiers.

10. The system of claim 7 , wherein the nonlocal flow detector is further configured to:
determine the first label using the sink instruction;
in response to determining the first label, add the first label to the first sub-flow;
determine the second label using the source instruction; and
in response to determining the second label, add the second label to the second sub-flow.

11. The system of claim 7 ,
wherein propagating the first access path is part of a taint analysis, and
wherein the first label and the second label are selected from a group consisting of code injection and cross-site scripting.

12. The system of claim 7 , wherein the nonlocal flow detector is further configured to:
determine that the first sub-flow excludes a modifier instruction performing: modifying the first value before the first variable reads the first value, wherein the modifier instruction corresponds to the first defect.

13. A method for executing a nonlocal defect analysis on code, comprising:
propagating, through the code, access paths to a first series of instructions starting at a sink instruction until a load instruction is reached to identify a first sub-flow,
wherein the sink instruction uses a first value of a first variable,
wherein the load instruction reads the first value using the first variable from a nonlocally accessible data structure, and
wherein the first sub-flow comprises a first label of a first defect added to the first sub-flow, the first label identified using the sink instruction,

propagating, through the code, access paths to a second series of instructions starting at a store instruction until a source instruction is reached to identify a second sub-flow,
wherein the store instruction writes a second value using a second variable to the nonlocally accessible data structure, and
wherein the second sub-flow comprises a second label of a second defect added to the second sub-flow, the second label identified using the source instruction,

comparing the first label and the second label to obtain a match indicating that the first variable and the second variable are potential aliases referring to a same value in the nonlocally accessible data structure,
generating a nonlocal flow connecting the first sub-flow and the second sub-flow responsive to the match,
wherein sub-flows comprising labels failing to match are excluded from nonlocal flow analysis.

14. The method of claim 13 ,
wherein the load instruction corresponds to a first access path,
wherein the store instruction corresponds to a second access path, and
wherein the method further comprises determining that the first access p

Assignees

• Oracle Int Corp

Inventors

• Krishnan Padmanabhan
• Zhao Yang

Classifications

• G06F11/3688 Primary

  for test execution, e.g. scheduling of test suites · CPC title

• G06F9/30043

  LOAD or STORE instructions; Clear instruction · CPC title

• G06F8/75 Primary

  Structural analysis for program understanding · CPC title

• G06F11/3604

  Analysis of software for verifying properties of programs (testing of software G06F11/3668) · CPC title