Skip to Main content Skip to Navigation
Conference papers

Proving Partial-Correctness and Invariance Properties of Transition-System Models

Abstract : We propose a deductive verification approach for proving partial-correctness and invariance properties on transition-system models. Regarding partial correctness, we gen-eralise the recently introduced formalism of Reachability Logic, currently used as a language-parametric logic for programs, to transition systems. We propose a sound and relatively complete proof system for the resulting reachability logic. The soundness of the proof system is formally established in the Coq proof assistant, and the mechanised proof provides us with a Coq-certified Reachability-Logic prover for transition-system models. The relative completeness of the proof system, although theoretical in nature, also has a practical value, as it induces a proof strategy that is guaranteed to prove all valid formulas on a given transition system. The strategy reduces partial-correctness verification to invariance verification; for the latter we propose an incremental technique in order to deal with the case-explosion problem that affects it. All these techniques were instrumental in enabling us to prove, within reasonable time and effort limits, that the nontrivial algorithm implemented in security hypervisor that we designed in earlier work meets its expected functional requirements.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01816798
Contributor : Pal Dream <>
Submitted on : Monday, October 15, 2018 - 1:54:46 PM
Last modification on : Friday, September 27, 2019 - 1:10:41 PM
Long-term archiving on: : Wednesday, January 16, 2019 - 3:04:54 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Vlad Rusu, Gilles Grimaud, Michaël Hauspie. Proving Partial-Correctness and Invariance Properties of Transition-System Models. TASE 2018 - 12th International Symposium on Theoretical Aspects of Software Engineering, Aug 2018, Guangzhou, China. pp.60-67, ⟨10.1109/TASE.2018.00016⟩. ⟨hal-01816798⟩

Share

Metrics

Record views

213

Files downloads

351