Search results for "Model Checking"
showing 10 items of 27 documents
Domain specific language for securities settlement systems
2012
Actual problems during design, implementation and maintenance of securities settlement systems software are achieving complementarity of several different, connected, asynchronously communicating settlement systems and verification of this complementarity. The aim of this paper is to create domain specific language for modeling of settlement systems and their interactions. Then use models to calculate settlement systems behavior. Specific of settlement systems requires that they perform accordingly to business rules in any situation. This makes use of model checking a very desirable step in development process of settlement systems. Defining a domain specific language and creating editor su…
A Detailed Account of The Inconsistent Labelling Problem of Stutter-Preserving Partial-Order Reduction
2021
One of the most popular state-space reduction techniques for model checking is partial-order reduction (POR). Of the many different POR implementations, stubborn sets are a very versatile variant and have thus seen many different applications over the past 32 years. One of the early stubborn sets works shows how the basic conditions for reduction can be augmented to preserve stutter-trace equivalence, making stubborn sets suitable for model checking of linear-time properties. In this paper, we identify a flaw in the reasoning and show with a counter-example that stutter-trace equivalence is not necessarily preserved. We propose a stronger reduction condition and provide extensive new correc…
Verification of Well-Formed Communicating Recursive State Machines
2008
AbstractIn this paper we introduce a new (non-Turing equivalent) formal model of recursive concurrent programs called well-formed communicating recursive state machines (CRSM). CRSM extend recursive state machines (RSM) by allowing a restricted form of concurrency: a state of a module can be refined into a finite collection of modules (working in parallel) in a potentially recursive manner. Communication is only possible between the activations of modules invoked on the same fork. We study the model-checking problem of CRSM with respect to specifications expressed in a temporal logic that extends CaRet with a parallel operator (ConCaRet). We propose a decision algorithm that runs in time ex…
ATL model checking in the cloud
2015
This paper gives an overview of our recent work on implementing a new interactive ATL model checker for verification of open systems. In verification based on model checking, we need to provide a model of the system and also write down the properties (ATL formulas) that we require the system to satisfy. Traditionally, the semantics of ATL is given in terms of concurrent game structures. In contrast to previous approaches, our tool permits an interactive design of the ATL models as state-transition graphs, and is based on client/server architecture. The server part, published as Web service in OpenShift cloud platform, embeds the core of the ATL model checker, and the client provides an intu…
Implementing an ATL model checker tool using relational algebra concepts
2014
Alternating-Time Temporal Logic (ATL) is a branching-time temporal logic that naturally describes computations of open systems. An open system interacts with its environment and its behavior depends on the state of the system as well as the behavior of the environment. ATL model-checking is a well-established technique for verifying that a formal model representing such a system satisfies a given property. In this paper we describe a new interactive model checker environment based on algebraic approach. Our tool is implemented in client-server paradigm. The client part allows an interactive construction of ATL models represented by concurrent game structures as directed multi-graphs. The se…
Survey of Formal Verification Methods for Smart Contracts on Blockchain
2019
Due to the immutable nature of distributed ledger technology such as blockchain, it is of utter importance that a smart contract works as intended before employment outside test network. This is since any bugs or errors will become permanent once published to the live network, and could lead to substantial economic losses; as manifested in the infamous DAO smart contract exploit hack in 2016. In order to avoid this, formal verification methods can be used to ensure that the contract behaves according to given specifications. This paper presents a survey of the state of the art of formal verification of smart contracts. Being a relatively new research area, a standard or best practice for fo…
Minimal Büchi Automata for Certain Classes of LTL Formulas
2009
In this paper we calculate the minimal number of states of Buchi automata which encode some classes of linear temporal logic (LTL) formulas that are frequently used in model checking. Our results may be used for verification of the quality of algorithms which automatically translate LTL formulas into Buchi automata and for improving the quality and speed of such translators. In the last section of this paper we compare our lower-bound estimations to Buchi automata generated by two currently used translators: LTL2BA and SPOT.
Verification of scope-dependent hierarchical state machines
2008
AbstractA hierarchical state machine (Hsm) is a finite state machine where a vertex can either expand to another hierarchical state machine (box) or be a basic vertex (node). Each node is labeled with atomic propositions. We study an extension of such model which allows atomic propositions to label also boxes (Shsm). We show that Shsms can be exponentially more succinct than Shsms and verification is in general harder by an exponential factor. We carefully establish the computational complexity of reachability, cycle detection, and model checking against general Ltl and Ctl specifications. We also discuss some natural and interesting restrictions of the considered problems for which we can …
Verifying a medical protocol with temporal graphs: the case of a nosocomial disease.
2014
Abstract Objective Our contribution focuses on the implementation of a formal verification approach for medical protocols with graphical temporal reasoning paths to facilitate the understanding of verification steps. Materials and methods Formal medical guideline specifications and background knowledge are represented through conceptual graphs, and reasoning is based on graph homomorphism. These materials explain the underlying principles or rationale that guide the functioning of verifications. Results An illustration of this proposal is made using a medical protocol defining guidelines for the monitoring and prevention of nosocomial infections. Such infections, which are acquired in the h…
Formal Modeling and Discrete-Time Analysis of BPEL Web Services
2008
International audience; Web services are increasingly used for building enterprise information systems according to the Service Oriented Architecture (SOA) paradigm. We propose in this paper a tool-equipped methodology allowing the formal modeling and analysis of Web services described in the BPEL language. The discrete-time transition systems modeling the behavior of BPEL descriptions are obtained by an exhaustive simulation based on a formalization of BPEL semantics using the Algebra of Timed Processes (ATP). These models are then analyzed by model checking value-based temporal logic properties using the CADP toolbox. The approach is illustrated with the design of a Web service for GPS na…