Search

This paper describes a toolkit that assists in the task of generating abstract approximations of process algebraic specifications written in the language μCRL. Abstractions are represented by Modal Labelled Transition Systems, which are mixed transition systems with may and must modalities. The approach permits to infer the satisfaction or refutation of safety and liveness properties expressed in the (action-based) μ-calculus. The tool supports the abstraction of states and action labels which allows to deal with infinitely branching systems.

Random graphs have the property that they are very predictable. Even by exploring a small part reliable observations are possible regarding their structure and size. An unfortunate observation is that standard models for random graphs, such as the Erdös-Rényi model, do not reflect the structure of the graphs that describe distributed systems and protocols. In this paper we propose to use the parallel composition of such random graphs to model ‘real’ state spaces. We show how we can use this structure to predict the size of state spaces, and we can use it to explain that software bugs are in practice far easier to find than predicted by the standard random graph models. By some practical experiments we show that our new random model is an improvement over the standard model in predicting properties of transition systems representing realistic systems. Keywords: Random graph, P-parallel random transition system, state space size

We present a fully automated approach to verifying safety properties of Executable UML models (xUML). Our tool chain consists of a model transformation program which translates xUML models to the process algebra mCRL2, followed by symbolic model checking using LTSmin. If a safety violation is found, an error trace is visualised as a UML sequence diagram. As a novel feature, our approach allows safety properties to be specified as UML state machines.

In this article, we show how scheduling problems can be modelled in untimed process algebra, by using special tick actions. A minimal-cost trace leading to a particular action, is one that minimises the number of tick steps. As a result, we can use any (timed or untimed) model checking tool to find shortest schedules. Instantiating this scheme to muCRL, we profit from a richer specification language than timed model checkers usually offer. Also, we can profit from efficient distributed state space generators. We propose a variant of breadth-first search that visits all states between consecutive tick steps, before moving to the next time slice. We experimented with a sequential and a distributed implementation of this algorithm. In addition, we experimented with beam search, which visits only parts of the search space, to find near-optimal solutions. Our approach is applied to find optimal schedules for test batches of a realistic clinical chemical analyser, which performs several kinds of tests on patient samples.

Developing test suites is a costly and error-prone process. Model-based test generation tools facilitate this process by automatically generating test cases from system models. The applicability of these tools, however, depends on the size of the target systems. Here, we propose an approach to generate test cases by combining data abstraction, enumerative test generation and constraint-solving. Given the concrete specification of a possibly infinite system, data abstraction allows to derive an abstract system, which is finite and thus suitable for the automatic generation of abstract test cases with enumerative tools. To execute abstract test cases, we have to instantiate them with concrete data. For data selection we make use of constraint-solving techniques.

We study a simple software architecture, in which components are coordinated by writing into and reading from a global set. This simple architecture is inspired by the industrial software architecture Splice. We present two results. First, a distributed implementation of the architecture is given and proved correct formally. In the implementation, local sets are maintained and data items are exchanged between these local sets. Next we show that the architecture is sufficiently expressive in principle. In particular, every global specification of a system's behaviour can be divided into components, which coordinate by read and write primitives on a global set only. We heavily rely on recent concepts and proof methods from process algebra.

Naarmate de hoeveelheid te testen software en het belang van goed geteste software toenemen, neemt de vraag naar testautomatisering toe. De praktijk van outsourcing en offshoring voegt hier nog extra uitdagingen aan toe. Voor testautomatisering is sinds kort een specifiek gestandaardiseerde programmeertaal beschikbaar: TTCN-3. Door de toenemende vraag naar testautomatisering en de huidige praktijk van outsourcing en offshoring is een gestandaardiseerde testtaal onontbeerlijk. Sinds kort is een specifiek voor testautomatisering gestandaardiseerde programmeertaal beschikbaar: TTCN-3. De taal en tools voor TTCN-3 zijn intensief in de praktijk getoetst. Hieruit blijkt dat TTCN-3 waarschijnlijk de toekomst van testautomatisering gaat bepalen.

Without abstract.

We propose two generalizations of innermost rewriting for which we prove that termination of innermost rewriting is equivalent to termination of generalized innermost rewriting. As a consequence, by rewriting in an arbitrary TRS certain non-innermost steps may be allowed by which the termination behavior and efficiency is often much better, but never worse than by only doing innermost rewriting.

We aim at improving the performance of distributed algorithms for model checking and state space reduction. To this end, we introduce a new distribution policy of states over workers. This policy reduces the number of transitions between states located at different workers. This in turn is expected to reduce the communication costs of the distributed algorithms.The main idea is to use Abstract Interpretation techniques to compute a small approximation of the state space, starting from some high level description of the system. Based on this approximation, the connectivity of concrete states is predicted. This information is used to distribute states with expected connectivity to the same worker. Experiments show a considerable reduction of cross transitions, at the expense of a modest unbalance of nodes per worker.

The logic of equality and uninterpreted functions (EUF) has been proposed for processor verification. This paper presents a new data structure called Binary Decision Diagrams for representing EUF formulas (EUF-BDDs). We define EUF-BDDs similar to BDDs, but we allow equalities between terms as labels instead of Boolean variables. We provide an approach to build a reduced ordered EUF-BDD (EUF-ROBDD) and prove that every path to a leaf is satisfiable by construction. Moreover, EUF-ROBDDs are logically equivalent representations of EUF-formulae, so they can also be used to represent state spaces in symbolic model checking with data.

The hybrid Chi (x) language is a formalism for modeling, simulation and verification of hybrid systems. One of the most widely known hybrid system formalisms is that of hybrid automata. The formal translation of x to hybrid automata enables verification of x specifications using existing hybrid automata based veri??cation tools. In this paper, we describe the translation from x to hybrid automata, and the relation between hybrid automata and the linear hybrid I/O automata that are used for the verification tool PHAVer (Polyhedral Hybrid Automaton Verifyer). In the case study, we translate a x specification to a linear hybrid I/O automaton, and use PHAVer to verify properties.

We prove the correctness of a sliding window protocol with an arbitrary finite window size n and sequence numbers modulo 2n. We show that the sliding window protocol is branching bisimilar to a queue of capacity 2n. The proof is given entirely on the basis of an axiomatic theory, and was checked with the help of PVS.

We describe a framework to generate modal abstract approximations from process algebraic specifications, written in the language µCRL. We allow abstraction of state variables and action labels. Moreover, we introduce a new format for process specifications called Modal Linear Process Equation (MLPE). Every transition step may lead to a set of abstract tates labelled with a set of abstract actions. We use MLPEs to characterize abstract interpretations of systems and to generate Modal Labelled Transition Systems, in which transitions may have two modalities may and must. We prove that the abstractions are sound for the full action-based µ-calculus. Finally, we apply the result to check some safety and liveness properties for the bounded retransmission protocol.

We prove the correctness of a sliding window protocol with an arbitrary finite window size n and sequence numbers modulo 2n. The correctness consists of showing that the sliding window protocol is branching bisimilar to a queue of capacity 2n. The proof is given entirely on the basis of an axiomatic theory, and has been checked in the theorem prover PVS.

datatypes can be viewed as sorted ground term algebras. Unification can be used to solve conjunctions of equations. We give a new algorithm to extend this to the full quantifier free fragment, i.e. including formulas with disjunction and negation. The algorithm is based on unification (to deal with equality) and DPLL (to deal with propositional logic). In this paper we present our algorithm as an instance of a generalized DPLL algorithm. We prove soundness and completeness of the class of generalized DPLL algorithms, in particular for the algorithm for ground term algebras.

We present an efficient algorithm to determine the maximal class of confluent Τ -transitions in a labelled transition system. Confluent Τ -transitions are inert with respect to branching bisimulation. This allows to use Τ -priorisation, which means that in a state with a confluent outgoing Τ -transition all other transitions can be removed, maintaining branching bisimulation. In combination with the removal of Τ-loops, and the compression of Τ-sequences this yields an efficient algorithm to reduce the size of large state spaces.

In this paper we propose a uniform description of basic BDD theory and algorithms by means of term rewriting. Since a BDD is a DAG instead of a tree we need a notion of shared rewriting and develop appropriate theory. A rewriting system is presented by which canonical forms can be obtained. Various reduction strategies give rise to different algorithms. A layerwise strategy is proposed having the same time complexity as the traditional apply- algorithm, and the lazy strategy is studied, which resembles the existing up-one-algorithm. We show that these algorithms have incomparable performance.

We provide a treatise about checking proofs of distributed systems by computer using general purpose proof checkers. In particular, we present two approaches to verifying and checking the verification of the Sequential Line Interface Protocol (SLIP), one using rewriting techniques and one using the so-called cones and foci theorem. Finally, we present an overview of literature containing checked proofs.