共查询到20条相似文献,搜索用时 15 毫秒
1.
Commonly, simulation by using an existing network simulation tool or a simulator developed from scratch is employed for validation of analytical network performance models. An analytical model of star-shaped wireless sensor networks has been proposed in the literature in which, upon receiving a query from the coordinator, each sensor node sends one data frame to it by executing the IEEE 802.15.4 unslotted carrier-sense multiple access with collision avoidance algorithm. The model consists of expressions for calculation of the probability of successful receipt of the data at a certain time and the like. The authors of the model have written a special simulation program in order to validate the expressions. Our aim was to employ probabilistic model checker PRISM instead. PRISM only requires the user to formally specify the network as a kind of state machine and the queries about the probabilities sought in the form of logical formulas. It finds the probabilities automatically and can present them on graphs. We show how to specify the networks formally in such a way that all the expressions from the analytical model can be validated with PRISM. For those networks containing a few nodes, the validation can be carried out by normal model checking, which, in contrast to the simulation, always checks all the possible network behaviors, whereas statistical model checking can be used for the larger networks. 相似文献
2.
In this paper we present efficient symbolic techniques for probabilistic model checking. These have been implemented in PRISM, a tool for the analysis of probabilistic models such as discrete-time Markov chains, continuous-time Markov chains and Markov decision processes using specifications in the probabilistic temporal logics PCTL and CSL. Motivated by the success of model checkers such as SMV which use BDDs (binary decision diagrams), we have developed an implementation of PCTL and CSL model checking based on MTBDDs (multi-terminal BDDs) and BDDs. Existing work in this direction has been hindered by the generally poor performance of MTBDD-based numerical computation, which is often substantially slower than explicit methods using sparse matrices. The focus of this paper is a novel hybrid technique which combines aspects of symbolic and explicit approaches to overcome these performance problems. For typical examples, we achieve a dramatic improvement over the purely symbolic approach. In addition, thanks to the compact model representation using MTBDDs, we can verify systems an order of magnitude larger than with sparse matrices, while almost matching or even beating them for speed. 相似文献
3.
Interaction among autonomous agents in Multi-Agent Systems (MASs) is a key aspect for agents to coordinate with one another. Social approaches, as opposed to the mental approaches, have recently received a considerable attention in the area of agent communication. They exploit observable social commitments to develop a verifiable formal semantics through which communication protocols can be specified. Developing and implementing algorithmic model checking for social commitments have been recently addressed. However, model checking social commitments in the presence of uncertainty is yet to be investigated.In this paper, we propose a model checking technique for verifying social commitments in uncertain settings. Social commitments are specified in a modal logical language called Probabilistic Computation Tree Logic of Commitments (PCTLC). The modal logic PCTLC extends PCTL, the probabilistic extension of CTL, with modalities for commitments and their fulfillments. The proposed verification method is a reduction-based model checking technique to the model checking of PCTL. The technique is based upon a set of reduction rules that translate PCTLC formulae to PCTL formulae to take benefit of existing model checkers such as PRISM. Proofs that confirm the soundness of the reduction technique are presented. We also present rules that transform our new version of interpreted systems into models of Markov Decision Processes (MDPs) to be suitable for the PRISM tool. We implemented our approach on top of the PRISM model checker and verified some given properties for the Oblivious Transfer Protocol from the cryptography domain. Our simulation demonstrates the effectiveness of our approach in verifying and model checking social commitments in the presence of uncertainty. We believe that the proposed formal verification technique will advance the literature of social commitments in such a way that not only representing social commitments in uncertain settings is doable, but also verifying them in such settings becomes achievable. 相似文献
4.
5.
Dragan Bošnački Stefan Edelkamp Damian Sulewski Anton Wijs 《International Journal on Software Tools for Technology Transfer (STTT)》2011,13(1):21-35
We present algorithms for parallel probabilistic model checking on general purpose graphic processing units (GPGPUs). Our improvements target the numerical components of the traditional sequential algorithms. In particular, we capitalize on the fact that in most of them operations like matrix–vector multiplication and solving systems of linear equations are the main complexity bottlenecks. Since linear algebraic operations can be implemented very efficiently on GPGPUs, the new parallel algorithms show considerable runtime improvements compared to their counterparts on standard architectures. We implemented our parallel algorithms on top of the probabilistic model checker PRISM. The prototype implementation was evaluated on several case studies in which we observed significant speedup over the standard CPU implementation of the tool. 相似文献
6.
Per Bjesse 《Formal Methods in System Design》2009,35(1):56-72
In this paper we present a word-level model checking method that attempts to speed up safety property checking of industrial
netlists. Our aim is to construct an algorithm that allows us to check both bounded and unbounded properties using standard
bit-level model checking methods as back-end decision procedures, while incurring minimum runtime penalties for designs that
are unsuited to our analysis. We do this by combining modifications of several previously known techniques into a static abstraction
algorithm which is guaranteed to produce bit-level netlists that are as small or smaller than the original bitblasted designs.
We evaluate our algorithm on several challenging hardware components. 相似文献
7.
The goal of this paper is to show how to use probabilistic model checking techniques in order to achieve quantitative performance evaluation of a real-time distributed simulation. A simulation based on the High Level Architecture (HLA) is modelled as a stochastic process, a Continuous Time Markov Chain (CTMC), using the stochastic algebra PEPA. Next a property representing a performance constraint is evaluated applying Continuous Stochastic Logic CSL formula on the CTMC model using the probabilistic model checker PRISM. Finally a first experiment is made to compare the model with a real case. 相似文献
8.
9.
10.
Electrocardiography (ECG) is a heart signal wave that is recorded using medical sensors, which are normally attached to the human body by the heart.
ECG waves have repetitive patterns that can be efficiently used in the diagnosis of heart problems as they carry several characteristics of heart operation.
Traditionally, the analysis of ECG waves is done using informal techniques, like simulation, which is in-exhaustive and thus the analysis results may lead
to ambiguities and life threatening scenarios in extreme cases. In order to overcome such problems, we propose to analyze ECG heart signals using
probabilistic model checking, which is a formal methods based quantitative analysis approach. This work presents the formal probabilistic analysis of ECG
signal abnormalities where the likelihood of abnormal patterns is studied and analyzed using the PRISM model checker. 相似文献
11.
概率模型检验建立在非概率模型检验技术的基础上,不仅能够对系统进行定性的验证,还能够定量判断系统满足相关性质的概率,具有广泛的适用性。LTL概率模型检验算法的复杂度较高,达到双重指数级别,现有的工具如PRISM与MRMC均不支持对LTL性质的验证。针对这个问题,通过对原有的LTL概率模型检验算法进行优化,实现了一个高效的LTL概率模型检验工具。通过对比实验验证了该工具的有效性。 相似文献
12.
Marta Kwiatkowska Gethin Norman David Parker 《Electronic Notes in Theoretical Computer Science》2006,153(2):5
Probabilistic model checking is a formal verification technique for establishing the correctness, performance and reliability of systems which exhibit stochastic behaviour. As in conventional verification, a precise mathematical model of a real-life system is constructed first, and, given formal specifications of one or more properties of this system, an analysis of these properties is performed. The exploration of the system model is exhaustive and involves a combination of graph-theoretic algorithms and numerical methods. In this paper, we give a brief overview of the probabilistic model checker PRISM (www.cs.bham.ac.uk/~dxp/prism) implemented at the University of Birmingham. PRISM supports a range of probabilistic models and specification languages based on temporal logic, and has been recently extended with costs and rewards. We describe our experience with using PRISM to analyse a number of case studies from a wide range of application domains. We demonstrate the usefulness of probabilistic model checking techniques in detecting flaws and unusual trends, focusing mainly on the quantitative analysis of a range of best, worst and average-case system characteristics. 相似文献
13.
概率时间自动机是在时间自动机的基础上加上各个状态迁移的概率以后形成的一种扩展的时间自动机,能用来对基于时间的随机协议、容错系统等进行建模,具有很强的实用性。本文针对概率时间自动机给出一种基于SMT的限界模型检测方法来验证该模型下的PTACTL性质,该方法由基于SMT的限界模型检测算法演变而来,通过将迁移时间和迁移概率融入ACTL性质中,改变模型的编码以及待验证性质的编码方式来实现对性质的验证。通过2个实例说明检测过程的有效性和高效性。 相似文献
14.
Action systems provide a formal approach to modelling parallel and reactive systems. They have a well established theory of refinement supported by simulation-based proof rules. This paper introduces an automatic approach for verifying action system refinements utilising standard CTL model checking. To do this, we encode each of the simulation conditions as a simulation machine, a Kripke structure on which the proof obligation can be discharged by checking that an associated CTL property holds. This procedure transforms each simulation condition into a model checking problem. Each simulation condition can then be model checked in isolation, or, if desired, together with the other simulation conditions by combining the simulation machines and the CTL properties. 相似文献
15.
Model checking, a prominent formal method used to predict and explain the behaviour of software and hardware systems, is examined
on the basis of reflective work in the philosophy of science concerning the ontology of scientific theories and model-based
reasoning. The empirical theories of computational systems that model checking techniques enable one to build are identified,
in the light of the semantic conception of scientific theories, with families of models that are interconnected by simulation
relations. And the mappings between these scientific theories and computational systems in their scope are analyzed in terms
of suitable specializations of the notions of model of experiment and model of data. Furthermore, the extensively mechanized
character of model-based reasoning in model checking is highlighted by a comparison with proof procedures adopted by other
formal methods in computer science. Finally, potential epistemic benefits flowing from the application of model checking in
other areas of scientific inquiry are emphasized in the context of computer simulation studies of biological information processing. 相似文献
16.
17.
Monte Carlo solution of structural dynamics 总被引:15,自引:0,他引:15
Masanobu Shinozuka 《Computers & Structures》1972,2(5-6):855-874
The recent advent of high speed digital computers has made it not only possible but also highly practical to apply the Monte Carlo techniques to a large variety of engineering problems. In this paper a technique of digital simulation of multivariate and/or multidimensional Gaussian random processes (homogeneous or nonhomogeneous) which can represent physical processes germane to structural engineering is presented. The paper also describes a method of digital simulation of envelope functions. Such simulations are accomplished in terms of a sum of cosine functions with random phase angles and used as the basic tool in a general Monte Carlo method of solution of a wide class of problems in structural engineering. Most important problems for which the method is found extremely useful includes (a) numerical analysis of dynamic response of nonlinear structures to random excitations, (b) time domain analysis of linear structures under random excitations performed for the purpose of obtaining a kind of information, such as first excursion probability and time history of a sample function, that is not obtainable from the standard frequency domain analysis, (c) numerical solution of structural problems involving randomly nonhomogeneous material property such as wave propagation through random medium, and (d) dynamic analysis of extremely complex systems such as those involving structure-fluid interaction. Numerical examples of some of these problems are presented. 相似文献
18.
Sieuwert van Otterloo Wiebe van der Hoek Michael Wooldridge 《Electronic Notes in Theoretical Computer Science》2004,85(2):152
The ultimate goal of our research is to develop techniques for model checking knowledge properties of multi-agent systems. ATEL, an extension of the Alternating-time Temporal Logic of Alur et al, is a logic for specifying epistemic and strategic properties of such systems. We present a technique for reducing the ATEL model checking problem to one of model checking in ATL, whereby epistemic relations are explicitly encoded in ATL models as as dynamic transitions. The techniques is illustrated by means of a knowledge game, which is used as a running example throughout the paper. 相似文献
19.
《Information and Computation》2006,204(9):1368-1409
Probabilistic verification of continuous-time stochastic processes has received increasing attention in the model-checking community in the past five years, with a clear focus on developing numerical solution methods for model checking of continuous-time Markov chains. Numerical techniques tend to scale poorly with an increase in the size of the model (the “state space explosion problem”), however, and are feasible only for restricted classes of stochastic discrete-event systems. We present a statistical approach to probabilistic model checking, employing hypothesis testing and discrete-event simulation. Since we rely on statistical hypothesis testing, we cannot guarantee that the verification result is correct, but we can at least bound the probability of generating an incorrect answer to a verification problem. 相似文献
20.
《Expert systems with applications》2014,41(14):6291-6304
Multi-Agent Systems (MASs) have long been modeled through knowledge and social commitments independently. In this paper, we present a new method that merges the two concepts to model and verify MASs in the presence of uncertainty. To express knowledge and social commitments simultaneously in uncertain settings, we define a new multi-modal logic called Probabilistic Computation Tree Logic of Knowledge and Commitments (PCTLkc in short) which combines two existing probabilistic logics namely, probabilistic logic of knowledge PCTLK and probabilistic logic of commitments PCTLC. To model stochastic MASs, we present a new version of interpreted systems that captures the probabilistic behavior and accounts for the communication between interacting components. Then, we introduce a new probabilistic model checking procedure to check the compliance of target systems against some desirable properties written in PCTLkc and report the obtained verification results. Our proposed model checking technique is reduction-based and consists in transforming the problem of model checking PCTLkc into the problem of model checking a well established logic, namely PCTL. So doing provides us with the privilege of re-using the PRISM model checker to implement the proposed model checking approach. Finally, we demonstrate the effectiveness of our approach by presenting a real case study. This framework can be considered as a step forward towards closing the gap of capturing interactions between knowledge and social commitments in stochastic agent-based systems. 相似文献