Generating Property-Directed Potential Invariants By Backward Analysis

Adrien Champion
(Onera / Rockwell Collins France)
Rémi Delmas
Michael Dierkes
(Rockwell Collins France)

This paper addresses the issue of lemma generation in a k-induction-based formal analysis of transition systems, in the linear real/integer arithmetic fragment. A backward analysis, powered by quantifier elimination, is used to output preimages of the negation of the proof objective, viewed as unauthorized states, or gray states. Two heuristics are proposed to take advantage of this source of information. First, a thorough exploration of the possible partitionings of the gray state space discovers new relations between state variables, representing potential invariants. Second, an inexact exploration regroups and over-approximates disjoint areas of the gray state space, also to discover new relations between state variables. k-induction is used to isolate the invariants and check if they strengthen the proof objective. These heuristics can be used on the first preimage of the backward exploration, and each time a new one is output, refining the information on the gray states. In our context of critical avionics embedded systems, we show that our approach is able to outperform other academic or commercial tools on examples of interest in our application field. The method is introduced and motivated through two main examples, one of which was provided by Rockwell Collins, in a collaborative formal verification framework.

In Peter Csaba Ölveczky and Cyrille Artho: Proceedings First International Workshop on Formal Techniques for Safety-Critical Systems (FTSCS 2012), Kyoto, Japan, November 12, 2012, Electronic Proceedings in Theoretical Computer Science 105, pp. 22–38.
Published: 29th December 2012.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: