Quantified data automata for linear data structures: a register automaton model with applications to learning invariants of programs manipulating arrays and lists

摘要

We propose a new automaton model, called quantified data automata (QDA) over words, that can model quantified invariants over linear data structures, and study their theory, including closure properties, canonical minimality, and decidability of emptiness. We build poly-time active learning algorithms for them, where the learner is allowed to query the teacher with membership and equivalence queries. In order to express invariants in decidable logics, we invent a decidable subclass of QDAs, called elastic QDAs, and show translations to decidable theories of arrays and lists. We also prove that every QDA has a unique minimally-over-approximating elastic QDA, showing a robust technique for abstracting QDA-expressible properties to the decidable fragments expressed by elastic QDAs. We then give an application of these theoretically sound and efficient active learning algorithms to program verification by building a passive learning framework that efficiently learns adequate quantified linear data structure invariants from samples obtained from dynamic executions for a class of programs.