Donut domains—efficient non-convex domains for abstract interpretation
First Claim
1. A computer implemented method for computer program analysis comprising the steps of:
- generating 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;
generating 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
generating a set of possible program errors using abstract interpretation over the difference between the two regions.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
15 Claims
-
1. A computer implemented method for computer program analysis comprising the steps of:
-
generating 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; generating 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 generating a set of possible program errors using abstract interpretation over the difference between the two regions. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A computer implemented method for determining a maximal inner polyhedron τ
- ={x ε
RP |Tx ≦
c of a giventemplate matrix T that lies within a given non-empty polyhedron P=[x ε
RP|Ax≦
b], comprising the steps of;computing an auxiliary matrix Λ
with non-negative elements Λ
T=A,computing c such that Λ
c≦
b and Tx≦
c is consistent,and outputting such inner polyhedron τ
. - View Dependent Claims (11, 12, 13, 14, 15)
- ={x ε
Specification