Difference between revisions of "Reachability Logic"

From FSL
Jump to: navigation, search
Line 14: Line 14:
 
<private>== Submitted to LICS'13 ==
 
<private>== Submitted to LICS'13 ==
 
<pubbib id='rosu-stefanescu-ciobaca-moore-2013-lics-submission' template='PubDefaultWithAbstractAndTitle' draft/>
 
<pubbib id='rosu-stefanescu-ciobaca-moore-2013-lics-submission' template='PubDefaultWithAbstractAndTitle' draft/>
 +
== Submitted to ICALP'13 ==
 +
<pubbib id='stefanescu-ciobaca-moore-serbanuta-rosu-2013-icalp-submission' template='PubDefaultWithAbstractAndTitle'/>
 +
== Submitted to MFCS'13 ==
 +
<pubbib id='stefanescu-ciobaca-moore-serbanuta-rosu-2013-mfcs-submission' template='PubDefaultWithAbstractAndTitle'/>
 
== Submitted to ESOP'13 ==
 
== Submitted to ESOP'13 ==
 
<pubbib id='rosu-stefanescu-ciobaca-moore-2013-esop-submission' template='PubDefaultWithAbstractAndTitle' draft/>
 
<pubbib id='rosu-stefanescu-ciobaca-moore-2013-esop-submission' template='PubDefaultWithAbstractAndTitle' draft/>

Revision as of 16:08, 12 August 2017


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

Personal tools
Namespaces

Variants
Actions
Navigation