Reachability Logic

From FSL
Jump to: navigation, search

OOPSLA'16

Semantics-Based Program Verifiers for All Languages
Andrei Stefanescu and Daejun Park and Shijiao Yuwen and Yilong Li and Grigore Rosu
OOPSLA'16, ACM, pp 74-91. 2016
Abstract. We present a language-independent verification framework that can be instantiated with an operational semantics to automatically generate a program verifier. The framework treats both the operational semantics and the program correctness specifications as reachability rules between matching logic patterns, and uses the sound and relatively complete reachability logic proof system to prove the specifications using the semantics. We instantiate the framework with the semantics of one academic language, KernelC, as well as with three recent semantics of real-world languages, C, Java, and JavaScript, developed independently. We evaluate our approach empirically and show that the generated program verifiers can check automatically the full functional correctness of challenging heap-manipulating programs implementing operations on list and tree data structures, like AVL trees. This is the first approach that can turn the operational semantics of real-world languages into correct-by-construction automatic verifiers.
PDF, Slides(PDF), Matching Logic, DOI, OOPSLA'16, BIB


RTA'14

All-Path Reachability Logic
Andrei Stefanescu and Stefan Ciobaca and Radu Mereuta and Brandon Moore and Traian Florin Serbanuta and Grigore Rosu
RTA'14, LNCS 8560, pp 425-440. 2014
Abstract. This paper presents a language-independent proof system for reachability properties of programs written in non-deterministic (e.g. concurrent) languages, referred to as *all-path reachability logic*. It derives partial-correctness properties with all-path semantics (a state satisfying a given precondition reaches states satisfying a given postcondition on all terminating execution paths). The proof system takes as axioms any unconditional operational semantics, and is sound (partially correct) and (relatively) complete, independent of the object language; the soundness has also been mechanized (Coq). This approach is implemented in a tool for semantics-based verification as part of the K framework.
PDF, Slides(PPTX), Matching Logic, DOI, RTA'14, BIB


Technical Report

Reachability Logic in K
Andrei Stefanescu and Stefan Ciobaca and Brandon Moore and Traian Florin Serbanuta and Grigore Rosu
Technical Report http://hdl.handle.net/2142/46296, Nov 2013
Abstract. This paper presents a language-independent proof system for reachability properties of programs written in non-deterministic (concurrent) languages, referred to as reachability logic. The proof system derives partial-correctness properties with either all-path or one-path semantics, i.e., that states satisfying a given precondition reach states satisfying a given postcondition on all execution paths, respectively on one execution path. Reachability logic takes as axioms any unconditional operational semantics, and is sound (i.e., partially correct) and (relatively) complete, independent of the object language; the soundness has also been mechanized. The proof system is implemented in a tool for semantics-based verification as part of the K framework, and evaluated on a few examples.
PDF, Matching Logic, DOI, BIB

LICS'13

One-Path Reachability Logic
Grigore Rosu and Andrei Stefanescu and Stefan Ciobaca and Brandon Moore
LICS'13, IEEE, pp 358-367. 2013
Abstract. This paper introduces *reachability logic*, a language-independent proof system for program verification, which takes an operational semantics as axioms and derives *reachability rules*, which generalize Hoare triples. This system improves on previous work by allowing operational semantics given with *conditional* rewrite rules, which are known to support all major styles of operational semantics. In particular, Kahn's big-step and Plotkin's small-step semantic styles are newly supported. The reachability logic proof system is shown sound (i.e., partially correct) and (relatively) complete. Reachability logic thus eliminates the need to independently define an axiomatic and an operational semantics for each language, and the non-negligible effort to prove the former sound and complete w.r.t. the latter. The soundness result has also been formalized in Coq, allowing reachability logic derivations to serve as formal proof certificates that rely only on the operational semantics.
PDF, Slides(PPTX), Reachability Logic, LICS'13, BIB


Technical Report

Reachability Logic
Grigore Rosu and Andrei Stefanescu and Stefan Ciobaca and Brandon Moore
Technical Report http://hdl.handle.net/2142/32952, Jul 2012
Abstract. This paper introduces *reachability logic*, a language-independent seven-rule proof system for deriving reachability properties of systems. The key ingredients of *reachability logic* are its sentences, which are called *reachability rules* and generalize the transitions of operational semantics and the Hoare triples of axiomatic semantics, and the *Circularity* proof rule, which generalizes invariant proof rules for iterative and recursive constructs in axiomatic semantics. The target transition system is described as a set of reachability rules, which are taken as axioms in a reachability logic proof. Typical definition styles which can be read as collections of reachability rules include conventional small-step and big-step operational semantics. The reachability logic proof system is shown sound (in the sense of partial correctness) and relatively complete. The soundness result has also been formalized in Coq, allowing to convert reachability logic proofs into proof certificates depending only on the operational semantics and the unavoidable domain reasoning. Reachability logic thus eliminates the need to independently define an axiomatic and an operational semantics for each language, and the non-negligible effort to prove the former sound and complete w.r.t the latter.
PDF, Reachability Logic, DOI, BIB

OOPSLA'12

Checking Reachability using Matching Logic
Grigore Rosu and Andrei Stefanescu
OOPSLA'12, ACM, pp 555-574. 2012
Abstract. This paper presents a verification framework that is parametric in a (trusted) operational semantics of some programming language. The underlying proof system is language-independent and consists of eight proof rules. The proof system is proved partially correct and relatively complete (with respect to the programming language configuration model). To show its practicality, the generic framework is instantiated with a fragment of C and evaluated with encouraging results.
PDF, Slides(PPTX), Slides(PDF), Matching Logic, DOI, OOPSLA'12, BIB


FM'12

From Hoare Logic to Matching Logic Reachability
Grigore Rosu and Andrei Stefanescu
FM'12, LNCS 7436, pp 387-402. 2012
Abstract. Matching logic reachability has been recently proposed as an alternative program verification approach. Unlike Hoare logic, where one defines a language-specific proof system that needs to be proved sound for each language separately, matching logic reachability provides a *language-independent* and *sound* proof system that directly uses the trusted operational semantics of the language as axioms. Matching logic reachability thus has a clear practical advantage: it eliminates the need for an additional semantics of the same language in order to reason about programs, and implicitly eliminates the need for tedious soundness proofs. What is not clear, however, is whether matching logic reachability is as powerful as Hoare logic. This paper introduces a technique to mechanically translate Hoare logic proof derivations into equivalent matching logic reachability proof derivations. The presented technique has two consequences: first, it suggests that matching logic reachability has no theoretical limitation over Hoare logic; and second, it provides a new approach to prove Hoare logics sound.
PDF, Slides(PPTX), Slides(PDF), Matching Logic, DOI, FM'12, BIB


ICALP'12

Towards a Unified Theory of Operational and Axiomatic Semantics
Grigore Rosu and Andrei Stefanescu
ICALP'12, LNCS 7392, pp 351-363. 2012
Abstract. This paper presents a nine-rule *language-independent* proof system that takes an operational semantics as axioms and derives program reachability properties, including ones corresponding to Hoare triples. This eliminates the need for language-specific Hoare-style proof rules to verify programs, and, implicitly, the tedious step of proving such proof rules sound for each language separately. The key proof rule is *Circularity*, which is coinductive in nature and allows for reasoning about constructs with repetitive behaviors (e.g., loops). The generic proof system is shown sound and has been implemented in the MatchC verifier.
PDF, Slides(PPTX), Slides(PDF), Matching Logic, DOI, ICALP'12, BIB


Technical Reports

Towards a Unified Theory of Operational and Axiomatic Semantics
Grigore Rosu and Andrei Stefanescu
Technical Report http://hdl.handle.net/2142/30827, May 2012
Abstract. This paper presents a nine-rule *language-independent* proof system that takes an operational semantics as axioms and derives program reachability properties, including ones corresponding to Hoare triples. This eliminates the need for language-specific Hoare-style proof rules to verify programs, and, implicitly, the tedious step of proving such proof rules sound for each language separately. The key proof rule is *Circularity*, which is coinductive in nature and allows for reasoning about constructs with repetitive behaviors (e.g., loops). The generic proof system is shown sound and has been implemented in the MatchC verifier.
PDF, Matching Logic, TR@UIUC, BIB

K'11

MatchC: A Matching Logic Reachability Verifier Using the K Framework
Andrei Stefanescu
K'11, ENTCS 304. 2011
Abstract. This paper presents MatchC, a matching logic reachability verifier using the K framework. K is a rewriting-based framework for defining and analyzing programming languages. Matching logic is a logic designed to state and reason about structural properties over arbitrary program configurations. Matching logic reachability is a unifying framework for operational and axiomatic semantics of programing languages. The MatchC verifier (http://matching-logic.org/) checks reachability properties of programs written in a deterministic fragment of C and is implemented in the K framework. This paper discusses the correctness of the implementation of the matching logic reachability proof system in MatchC. The main contributions of this paper are the implementation of the verifier, with emphasis on using K for program verification, and the evaluation of the tool on a large number of programs, including complex ones, like programs implementing the AVL trees data structure and the Schorr-Waite graph marking algorithm.
PDF, Matching Logic, DOI, BIB

Personal tools
Namespaces

Variants
Actions
Navigation