Directed Explicit Model Checking with HSF-SPIN

Stefan Edelkamp; Alberto Lluch Lafuente; Stefan Leue

doi:10.1007/3-540-45139-0_5

Directed Explicit Model Checking with HSF-SPIN

Stefan Edelkamp, Alberto Lluch Lafuente, Stefan Leue

University of Freiburg

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

We present the explicit state model checker HSF-SPIN which is based on the model checker SPIN and its Promela modeling language. HSF-SPIN incorporates directed search algorithms for checking safety and a large class of LTL-specified liveness properties. We start off from the A* algorithm and define heuristics to accelerate the search into the direction of a specified failure situation. Next we propose an improved nested depth-first search algorithm that exploits the structure of Promela Never-Claims. As a result of both improvements, counterexamples will be shorter and the explored part of the state space will be smaller than with classical approaches, allowing to analyze larger state spaces. We evaluate the impact of the new heuristics and algorithms on a set of protocol models, some of which are real-world industrial protocols.

Original language	English
Title of host publication	Model Checking Software : 8th International SPIN Workshop Toronto, Canada, May 19–20, 2001 Proceedings
Publisher	Springer Berlin Heidelberg
Publication date	2001
Pages	57-79
ISBN (Print)	978-3-540-42124-5
ISBN (Electronic)	978-3-540-45139-6
DOIs	https://doi.org/10.1007/3-540-45139-0_5
Publication status	Published - 2001
Externally published	Yes
Event	8^th International SPIN Workshop on Model Checking Software - Toronto, Canada Duration: 19 May 2001 → 20 May 2001 Conference number: 8

Workshop

Workshop	8^th International SPIN Workshop on Model Checking Software
Number	8
Country/Territory	Canada
City	Toronto
Period	19/05/2001 → 20/05/2001

Series	Lecture Notes in Computer Science
Volume	2057
ISSN	0302-9743

Access to Document

10.1007/3-540-45139-0_5

OpenUrl availability

Full text

Cite this

@inproceedings{8595306d7d4a43b9b65b9e372c89d30b,

title = "Directed Explicit Model Checking with HSF-SPIN",

abstract = "We present the explicit state model checker HSF-SPIN which is based on the model checker SPIN and its Promela modeling language. HSF-SPIN incorporates directed search algorithms for checking safety and a large class of LTL-specified liveness properties. We start off from the A* algorithm and define heuristics to accelerate the search into the direction of a specified failure situation. Next we propose an improved nested depth-first search algorithm that exploits the structure of Promela Never-Claims. As a result of both improvements, counterexamples will be shorter and the explored part of the state space will be smaller than with classical approaches, allowing to analyze larger state spaces. We evaluate the impact of the new heuristics and algorithms on a set of protocol models, some of which are real-world industrial protocols.",

author = "Stefan Edelkamp and {Lluch Lafuente}, Alberto and Stefan Leue",

year = "2001",

doi = "10.1007/3-540-45139-0_5",

language = "English",

isbn = "978-3-540-42124-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "57--79",

booktitle = "Model Checking Software",

note = "8<sup>th</sup> International SPIN Workshop on Model Checking Software, SPIN'01 ; Conference date: 19-05-2001 Through 20-05-2001",

}

Edelkamp, S, Lluch Lafuente, A & Leue, S 2001, Directed Explicit Model Checking with HSF-SPIN. in Model Checking Software: 8th International SPIN Workshop Toronto, Canada, May 19–20, 2001 Proceedings. Springer Berlin Heidelberg, Lecture Notes in Computer Science, vol. 2057, pp. 57-79, 8^th International SPIN Workshop on Model Checking Software, Toronto, Canada, 19/05/2001. https://doi.org/10.1007/3-540-45139-0_5

Directed Explicit Model Checking with HSF-SPIN. / Edelkamp, Stefan; Lluch Lafuente, Alberto; Leue, Stefan.
Model Checking Software: 8th International SPIN Workshop Toronto, Canada, May 19–20, 2001 Proceedings. Springer Berlin Heidelberg, 2001. p. 57-79 (Lecture Notes in Computer Science, Vol. 2057).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Directed Explicit Model Checking with HSF-SPIN

AU - Edelkamp, Stefan

AU - Lluch Lafuente, Alberto

AU - Leue, Stefan

N1 - Conference code: 8

PY - 2001

Y1 - 2001

N2 - We present the explicit state model checker HSF-SPIN which is based on the model checker SPIN and its Promela modeling language. HSF-SPIN incorporates directed search algorithms for checking safety and a large class of LTL-specified liveness properties. We start off from the A* algorithm and define heuristics to accelerate the search into the direction of a specified failure situation. Next we propose an improved nested depth-first search algorithm that exploits the structure of Promela Never-Claims. As a result of both improvements, counterexamples will be shorter and the explored part of the state space will be smaller than with classical approaches, allowing to analyze larger state spaces. We evaluate the impact of the new heuristics and algorithms on a set of protocol models, some of which are real-world industrial protocols.

AB - We present the explicit state model checker HSF-SPIN which is based on the model checker SPIN and its Promela modeling language. HSF-SPIN incorporates directed search algorithms for checking safety and a large class of LTL-specified liveness properties. We start off from the A* algorithm and define heuristics to accelerate the search into the direction of a specified failure situation. Next we propose an improved nested depth-first search algorithm that exploits the structure of Promela Never-Claims. As a result of both improvements, counterexamples will be shorter and the explored part of the state space will be smaller than with classical approaches, allowing to analyze larger state spaces. We evaluate the impact of the new heuristics and algorithms on a set of protocol models, some of which are real-world industrial protocols.

U2 - 10.1007/3-540-45139-0_5

DO - 10.1007/3-540-45139-0_5

M3 - Article in proceedings

SN - 978-3-540-42124-5

T3 - Lecture Notes in Computer Science

SP - 57

EP - 79

BT - Model Checking Software

PB - Springer Berlin Heidelberg

T2 - 8<sup>th</sup> International SPIN Workshop on Model Checking Software

Y2 - 19 May 2001 through 20 May 2001

ER -

Directed Explicit Model Checking with HSF-SPIN

Abstract

Workshop

Access to Document

OpenUrl availability

Fingerprint

Cite this