POPL 2027
Sun 10 - Sat 16 January 2027 Mexico City, Mexico

Abstract interpretation provides sound over-approximations for static program analysis, but soundness often comes with imprecision. Distance-based partial completeness quantifies this imprecision by measuring the distance between the precise abstract image and the result computed by an analyzer. Existing techniques mainly derive upper bounds on this imprecision, which certify how imprecise the analysis may be but do not reveal how much imprecision is unavoidable. This paper develops a two-sided framework that, given a program, an input set, and an abstract-domain distance, derives an interval [l,u] enclosing the exact imprecision. The upper bound u is tightened by replacing generator-only propagation with representative concrete states that better preserve structure under later restrictions. The lower bound l is propagated compositionally and can be improved using false-positive feedback as semantic constraints. We instantiate the framework in a two-dimensional numerical setting where convex hulls model abstract elements and area difference measures imprecision. Experiments show that representative-state selection substantially tightens upper bounds over generator-only propagation, while posterior information raises initially conservative lower bounds.