文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > ProbVerus probabilistic symbolic model checking
侵权投诉

ProbVerus probabilistic symbolic model checking

Abstract. Model checking can tell us whether a system is correct; probabilistic model checking can also tell us whether a system is timely and reliable. Moreover, probabilistic model checking allows one to verify properties that may not be true with probab

ProbVerus: Probabilistic Symbolic Model Checking

Vicky Hartonas-Garmhausen1, Sergio Campos2, Ed Clarke3

1Carnegie Mellon University, Department of Engineering and Public Policy,

5000 Forbes Avenue, Pittsburgh, PA 15213, USA

2Federal University of Minas, Gerais, Brasil

3Carnegie Mellon University, Department of Computer Science, hartonas@cs.cmu.eduscampos@dcc.ufmg.br

5000 Forbes Avenue, Pittsburgh, PA 15213, USA

emc@cs.cmu.edu

Abstract. Model checking can tell us whether a system is correct; probabilistic

model checking can also tell us whether a system is timely and reliable.

Moreover, probabilistic model checking allows one to verify properties that may

not be true with probability one, but may still hold with an acceptable probability.

The challenge in developing a probabilistic model checker able to handle realistic

systems is the construction of the state space and the necessity to solve huge

systems of linear equations. To address this problem, we have developed

ProbVerus, a tool for the formal verification of probabilistic real-time systems.

ProbVerus is an implementation of probabilistic computation tree logic (PCTL)

model checking using symbolic techniques. We present ProbVerus, demonstrate

its use with a simple manufacturing example, and report the current status of the

tool. With ProbVerus, we have been able to analyze, within minutes, the safety

logic of a railway interlocking controller with 1027 states.

1 Introduction

The large size and high complexity of real-world mission-critical systems makes theverification of these systems an extremely difficult problem. To study the completesystem, one must also include the system's interface with the environment. Physicalsystems are stochastic in nature and randomization makes the verification of probabi-listic systems even more difficult due to its nonintuitive effects. At the same time,industries such as the transportation, pharmaceutical, chemical, and nuclear, arerequired to meet this challenge being constantly under the scrutiny of process andproduct specification. There is a great need for industrial-strength formal methods aswell as real-world case studies that can demonstrate their feasibility.

Probabilistic model checking is a method for the formal verification of stochasticsystems. The state of the art in probabilistic verification research includes numeroustheoretical studies that have lead to efficient algorithms; for example, there is an LTLmodel checking algorithm which is exponential in the size of the formula and polyno-mial in the size of the Markov chain [9]. The bottleneck in developing a probabilisticmodel checker able to handle realistic systems is the construction of the state space andJ.-P. Katoen (Ed.): ARTS’99, LNCS 1601, pp. 96-110, 1999.

© Springer-Verlag Berlin Heidelberg 1999

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email