Patent ID: 7926039

Claim:
An improvement to a computer-implemented method to perform a static analysis on a software program using a fix-point computation using pre-condition or post-condition operations, wherein said method employs an extrapolation operation to accelerate the convergence of the method, wherein said improvement is CHARACTERIZED IN THAT: the extrapolation employs a care-set that identifies one or more forbidden areas of extrapolation; and outputs an indication of those forbidden areas; wherein the extrapolation is performed on convex polyhedra, and P,Q are two polyhedra, and C is a powerset such that Q∩C=Ø wherein the extrapolation of P with respect to Q under the care set C is computed according to the following steps: building a new polyhedron P′ for each constraint c of P whose half-space does not contain Q, such that if P c ∩C=└ then c is dropped; building a new polyhedron Q′ by dropping any constraint c of Q whose half-space does not contain P′; and returning Q′ as the result of the extrapolation.