DONUT DOMAINS - EFFICIENT NON-CONVEX DOMAINS FOR ABSTRACT INTERPRETATION

• US 20120246626A1
• Filed: 03/23/2012
• Published: 09/27/2012
• Est. Priority Date: 03/23/2011
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: MAEDA, Naoto, GHORBAL, Khalil, IVANCIC, Franjo, BALAKRISHNAN, Gogul
• Granted Patent: US 8,719,790 B2
• Time in Patent Office: Days
• US Class Current: 717/132
• CPC Class Codes: G06F 11/3608 using formal methods, e.g. model checking, abstract interpretation theorem proving G06N5/013

Abstract

A computer implemented program analysis method employing a set of new abstract domains applicable to non-convex invarients. The method analyzes programs statically using abstract interpretation while advantageously considering non-convex structures and in particular those situations in which an internal region of an unreachable state exists within a larger region of reachable states. The method employs a new set of non-convex domains (donut domains) based upon the notion of an outer convex region of reachable states (Domain D1) and an inner region of unreachable states (Domain D2) which advantageously permits capture of non-convex properties by using convex regions and operations.

Claims

3-1. The method of claim 3 wherein said regions are ones selected from the group consisting of:

intervals, octagons, and polyhedra.

6. The method of claim 6 further comprising the step of using an LP-solver to find matrix Λ

.

8. The method of claim 6 further comprising the step of determining the saturation of Λ

c≦

b, namely Λ

c=b.

9. The method of claim 6 wherein the output polyhedron is used for computer program analysis.

10. A computer implemented method for determining a maximal inner polyhedron ={x ∈

^p|Tx≦

c} of a given template matrix T that lies within a given non-empty polyhedron ={x ∈

^p|Ax≦

b}, comprising the steps of;

computing an auxiliary matrix A with non-negative elements and Λ

T=A,

computing c such that Λ

c≦

b and Tx≦

c is consistent,

and outputting such inner polyhedron .

11. The method of claim 10 further comprising the step of using an LP-solver to find matrix Λ

.

12. The method of claim 10 further comprising the step of determining the saturation of Λ

c≦

b, namely Λ

c=b.

13. The method of claim 10 wherein the output polyhedron is used for computer program analysis.

14. The method of claim 10 wherein the output polyhedron is used for test vector generation.

15. The method of claim 10 wherein the output polyhedron is used for computer graphics applications.

16. A computer system comprising program instructions adapted to be executed for computer program analysis, said instructions being stored in computer-readable memory, and when executed by the computer system cause the computer system to be operable to:

generate an outer convex region of all reachable states for the computer program wherein the outer region (D1) represents an over-approximation of all of the reachable states;

generate an inner convex region of all unreachable states for the computer program wherein the inner region (D2) represents an under-approximation of all of the unreachable states; and

generate a set of possible program errors using abstract interpretation over the difference between the two regions.

17. The computer system of claim 16 wherein the under-approximated inner region is instantiated as a powerset domain of an elementary domain.

18. The computer system of claim 16 further operable to:

construct a control flow graph of the computer program;

propagate region D1 along a control flow graph;

propagate region D2 along a control flow graph;

determining the differences between the two propagations; and

generate a set of reachable states from the difference so determined.

19. The computer system of claim 18 wherein said regions are ones selected from the group consisting of:

intervals, octagons, and polyhedra.

20. The computer system of claim 16 further operable to:

determing a maximal inner polyhedron ={x ∈

^p|Tx≦

c} of a given template matrix T that lies within a given non-empty polyhedron ={x ∈

^p|Zx≦

b}, by;

compute an auxiliary matrix Λ

with non-negative elements and Λ

T=A,

compute c such that Λ

c≦

b and Tx≦

c is consistent,

and output such inner polyhedron .