Method and apparatus for incremental analysis of one or more properties of a program
View Patent ↗Methods and apparatus are provided for incremental analysis of one or more properties of a program. According to one aspect of the invention, at least one property of a software program is evaluated, given one or more changes to the software program. Nodes in a derivation graph are identified corresponding to changed edges in a control flow graph representation of the software program, wherein the derivation graph describes an earlier evaluation of the software program. In addition, at least one of the identified nodes in the derivation graph is updated and the derivation graph is traversed outward from a location of a change. The revised derivation graph can optionally be further processed to remove false errors.
1. A method for evaluating at least one property of a software program given one or more changes to said software program, said method comprising the steps of:
identifying nodes in an automaton-based derivation graph corresponding to changed edges in a control flow graph representation of said software program, wherein said automaton-based derivation graph describes an earlier evaluation of said software program; and
updating at least one of said identified nodes in said automaton-based derivation graph and traversing said automaton-based derivation graph outward from a location of a change, wherein said updating step further comprises the steps of:
computing a strongly connected component (SCC) decomposition of a function call graph in said software program;
identifying an SCC having an unprocessed program change and a lowest position in said SCC decomposition;
performing a forward incremental analysis on said identified SCC to process said program change in said SCC;
evaluating one or more interfaces of said identified SCC to identify one or more additional SCCs affected by said program change until no interfaces are affected; and
repeating said identifying, performing and evaluating steps for a next SCC having an unprocessed program change and a lowest position in said software program.
2. The method of claim 1 , further comprising the step of generating a revised automaton-based derivation graph describing an analysis of said software program incorporated with said given one or more changes.
3. The method of claim 2 , wherein said revised automaton-based derivation graph maintains less information than a full automaton-based derivation graph.
4. The method of claim 2 , further comprising the step of processing said revised automaton-based derivation graph to remove false errors.
5. The method of claim 4 , wherein said false errors are associated with unreachable errors.
6. The method of claim 1 , wherein said software program is expressed as a collection of said control flow graphs.
7. The method of claim 1 , wherein said one or more changes to said software program comprise a modification, addition or deletion of one or more program statements.
8. The method of claim 1 , wherein said property is the presence of a program bug detectable by a checking automaton.
9. An apparatus for evaluating at least one property of a software program given one or more changes to said software program, the apparatus comprising:
a memory; and
at least one processor, coupled to the memory, operative to:
identify nodes in a automaton-based derivation graph corresponding to changed edges in a control flow graph representation of said software program, wherein said automaton-based derivation graph describes an earlier evaluation of said software program; and
update at least one of said identified nodes in said automaton-based derivation graph and traversing said automaton-based derivation graph outward from a location of a change,
wherein said processor is further configured to:
compute a strongly connected component (SCC) decomposition of a function call graph in said software program;
identify an SCC having an unprocessed program change and a lowest position in said SCC decomposition;
perform a forward incremental analysis on said identified SCC to process said program change in said SCC;
evaluate one or more interfaces of said identified SCC to identify one or more additional SCCs affected by said program change until no interfaces are affected; and
repeat said identifying, performing and evaluating steps for a next SCC having an unprocessed program change and a lowest position in said software program.
10. The apparatus of claim 9 , processor is further configured to generate a revised automaton-based derivation graph describing an analysis of said software program incorporated with said given one or more changes.
11. The apparatus of claim 10 , wherein said revised automaton-based derivation graph maintains less information than a full automaton-based derivation graph.
12. The apparatus of claim 10 , processor is further configured to process said revised automaton-based derivation graph to remove false errors.
13. The apparatus of claim 12 , wherein said false errors are associated with unreachable errors.
14. The apparatus of claim 9 , wherein said software program is expressed as a collection of said control flow graphs.
15. The apparatus of claim 9 , wherein said one or more changes to said software program comprise a modification, addition or deletion of one or more program statements.
16. The apparatus of claim 9 , wherein said property is the presence of a program bug detectable by a checking automaton.
17. An article of manufacture for evaluating at least one correctness property of a software program given one or more changes to said software program, comprising a non-transitory machine readable storage medium containing one or more programs which when executed implement the steps of:
identifying nodes in a automaton-based derivation graph corresponding to changed edges in a control flow graph representation of said software program, wherein said automaton-based derivation graph describes an earlier evaluation of said software program; and
updating at least one of said identified nodes in said automaton-based derivation graph and traversing said automaton-based derivation graph outward from a location of a change, wherein said non-transitory machine readable storage medium contains one or more programs which when executed further implement the steps of:
computing a strongly connected component (SCC) decomposition of a function call graph in said software program;
identifying an SCC having an unprocessed program change and a lowest position in said SCC decomposition;
performing a forward incremental analysis on said identified SCC to process said program change in said SCC;
evaluating one or more interfaces of said identified SCC to identify one or more additional SCCs affected by said program change until no interfaces are affected; and
repeating said identifying, performing and evaluating steps for a next SCC having an unprocessed program change and a lowest position in said software program.