Partial (In)Completeness in Abstract Interpretation: Limiting the Imprecision in Program Analysis
Imprecision is inherent in any decidable (sound) approximation of undecidable program properties. In abstract interpretation this corresponds to the release of false alarms, e.g., when it is used for program analysis and program verification. As all alarming systems, a program analysis tool is credible when few false alarms are reported.
As a consequence, we have to live together with false alarms, but also we need methods to control them.
As for all approximation methods, also for abstract interpretation we need to estimate the accumulated imprecision during program analysis. In this paper we introduce a theory for estimating the error propagation in abstract interpretation, and hence in program analysis. We enrich abstract domains with a weakening of a metric distance. This enriched structure keeps coherence between the standard partial order relating approximated objects by their relative precision and the effective error made in this approximation.
An abstract interpretation is precise when it is complete.
We introduce the notion of partial completeness as a weakening of precision. In partial completeness the abstract interpreter may produce a bounded number of false alarms. We prove the key recursive properties of the class of programs for which an abstract interpreter is partially complete with a given bound of imprecision. Then, we introduce a proof system for estimating an upper bound of the error accumulated by the abstract interpreter during program analysis. Our framework is general enough to be instantiated to most known metrics for abstract domains.
Wed 19 JanDisplayed time zone: Eastern Time (US & Canada) change
13:30 - 14:45
Program AnalysisPOPL at Salon I
Chair(s): Gagandeep Singh University of Illinois at Urbana-Champaign; VMware
|Property-Directed Reachability as Abstract Interpretation in the Monotone TheoryRemote|
Yotam M. Y. Feldman Tel Aviv University, Mooly Sagiv Tel Aviv University, Sharon Shoham Tel Aviv University, James R. Wilcox CertoraDOI Media Attached
|Partial (In)Completeness in Abstract Interpretation: Limiting the Imprecision in Program AnalysisInPerson|
Marco Campion University of Verona, Mila Dalla Preda University of Verona, Roberto Giacobazzi University of VeronaDOI Media Attached
|Return of CFA: Call-Site Sensitivity Can Be Superior to Object Sensitivity Even for Object-Oriented ProgramsInPerson|
Minseok Jeon Korea University, Hakjoo Oh Korea UniversityDOI Media Attached