Complexity and information in invariant inference
| Autor: | Yotam M. Y. Feldman, Mooly Sagiv, Neil Immerman, Sharon Shoham |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Programming Languages Theoretical computer science Computer science Inference 020207 software engineering 0102 computer and information sciences 02 engineering and technology 01 natural sciences Upper and lower bounds Rate of convergence Exponential growth 010201 computation theory & mathematics TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS Concept learning Transition system 0202 electrical engineering electronic engineering information engineering Invariant (mathematics) Safety Risk Reliability and Quality Computer Science::Databases Software Programming Languages (cs.PL) Counterexample |
| Zdroj: | Proceedings of the ACM on Programming Languages |
| ISSN: | 2475-1421 |
| DOI: | 10.1145/3371073 |
| Popis: | This paper addresses the complexity of SAT-based invariant inference, a prominent approach to safety verification. We consider the problem of inferring an inductive invariant of polynomial length given a transition system and a safety property. We analyze the complexity of this problem in a black-box model, called the Hoare-query model, which is general enough to capture algorithms such as IC3/PDR and its variants. An algorithm in this model learns about the system's reachable states by querying the validity of Hoare triples. We show that in general an algorithm in the Hoare-query model requires an exponential number of queries. Our lower bound is information-theoretic and applies even to computationally unrestricted algorithms, showing that no choice of generalization from the partial information obtained in a polynomial number of Hoare queries can lead to an efficient invariant inference procedure in this class. We then show, for the first time, that by utilizing rich Hoare queries, as done in PDR, inference can be exponentially more efficient than approaches such as ICE learning, which only utilize inductiveness checks of candidates. We do so by constructing a class of transition systems for which a simple version of PDR with a single frame infers invariants in a polynomial number of queries, whereas every algorithm using only inductiveness checks and counterexamples requires an exponential number of queries. Our results also shed light on connections and differences with the classical theory of exact concept learning with queries, and imply that learning from counterexamples to induction is harder than classical exact learning from labeled examples. This demonstrates that the convergence rate of Counterexample-Guided Inductive Synthesis depends on the form of counterexamples. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|