Reachability Analysis

A detailed generic model of the control design process is introduced and discussed. It is used for surveying different formal approaches in the context of PLC programming. The survey focuses on formal methods for verification and validation (V&V). The varying works in this area are categorized using three criteria: the general approach (A) to the task (model based, constraint based or without a model), the formalism (F) (Petri net, automata, etc.,) used to state the formal description, and the method (M) (model-checking, reachability analysis, etc.,) used to analyze the properties. Based on these three criteria (A-F-M) a three letter code for V&V approaches is introduced. Some works from the multitude of V&V research are presented and categorized using this new system

Databases are replicated to improve performance and availability. The notion of correctness that has commonly been adopted for concurrent access by transactions to shared, possibly replicated, data is serializability. However, serializability may be impractical in high-performance applications since it imposes too stringent a restriction on concurrency. When serializability is relaxed, the integrity constraints describing the data may be violated. By allowing bounded violations of the integrity constraints, however, we are able to increase the concurrency of transactions that execute in a replicated environment. In this article, we introduce the notion of an N-ignorant transaction, which is a transaction that may be ignorant of the results of at most N prior transactions, which is a transaction that may be ignorant of the results of at most N prior transactions. A system in which all transactions are N-ignorant can have an N + 1-fold increase in concurrency over serializable systems...

Predicate abstraction has emerged to be a powerful technique for extracting finite-state models from infinite-state discrete programs. Th is paper presents algorithms and tools for reachability analysis of hybrid systems by combining the notion of predicate abstraction with recent techniques for approximating the set of reachable states of linear systems using polyhedra.Giv en a hybrid system and a set of userde fined boolean predicates, we consider the finite discrete quotient whose states correspond to all possible truth assignments to the input predicates. T he tool performs an on-the-fly exploration of the abstract system. We demonstrate the feasibility of the proposed technique by analyzing a parametric timing-based mutual exclusion protocol and safety of a simple controller for vehicle coordination.

This thesis presents a novel visualization technique and web-based method for network-based reachability analysis. The challenge is to enable a broad range of easily accessible tools for displaying both generalized polygonal maps and complete, highly detailed transportation network infrastructures for web clients and mobile devices. The main problems associated with this task are: (1) the transmission of massive geodata sets, (2) the mapping and rendering of unfiltered and non-generalized networks in real-time, and (3) dynamic user interaction, stylization, and parameterization.

To undertake this challenge, a web-mapping framework is extended via a Web Graphics Library (WebGL) enabled renderer that receives data in the Graphics Library Transmission Format (glTF). The geodata are processed using a specialized backend server and packed in binary buffer objects that are passed directly to the rendering stage of a frontend client. The display of massive transportation networks is enabled by utilizing the Graphics Processing Units (GPUs) of the client’s device. The binary glTF greatly reduces the transmission bandwidth required, and it is directly readable by the GPU without requiring costly client-side mapping computation. Dynamic stylization is enabled in fragment shaders per user defined parameters.

This study includes a full technical specification of the backend services, required geographic projections, transmission format specifics, and client renderer details. A proof-of-concept application shows the feasibility of the proposed approach and allows for evaluation and comparison with existing techniques. A collaboration with a local startup provided insight into viable use cases for the technique. The present prototype is the first web-based tool of its kind to render complete, unfiltered transportation networks. The technique, however, is universally adaptable to any geographic network and is not limited to networks; i.e., it is potentially operable for points or polygonal features with slight modifications.

This paper introduces iterative relaxation abstraction (IRA), a new method for reachability analysis of LHA that aims to improve scalability by combining the capabilities of current tools for analysis of low-dimensional LHA with the power of linear programming (LP) for large numbers of constraints and variables. IRA is inspired by the success of counterexample guided abstraction refinement (CEGAR) techniques in verification of discrete systems. On each iteration, a low-dimensional LHA called a relaxation abstraction is constructed using a subset of the continuous variables from the original LHA. Hybrid system reachability analysis then generates a regular language called the discrete path abstraction containing all possible counterexamples (paths to the bad locations) in the relaxation abstraction. If the discrete path abstraction is non-empty, a particular counterexample is selected and LP infeasibility analysis determines if the counterexample is spurious using the constraints along the path from the original high-dimensional LHA. If the counterexample is spurious, LP techniques identify an irreducible infeasible subset (IIS) of constraints from which the set of continuous variables is selected for the the construction of the next relaxation abstraction. IRA stops if the discrete path abstraction is empty or a legitimate counterexample is found. The effectiveness of the approach is illustrated with an example.

Petri nets (PNs) are a reliable graphical and mathematical modeling tool for the formal modeling and validation of systems (W. Reisig, A Primer in Petri Net Design, Springer-Verlag: Berlin, Heidelberg, 1992). Applications of PNs include discrete event dynamic systems (DEDS) that are recognized as being concurrent, asynchronous, distributed, parallel, and/or nondeterministic. It is also a powerful formal method for the analysis of concurrent, embedded, and distributed finite state systems (K. Varpaaniemi, Series A: Research Reports, No. 26, Helsinki University of Technology, Digital Systems Laboratory, Oct. 1993). The reachability analysis of PNs is strategically significant as it captures the dynamic behavior of the system as well as providing efficient verification of the correctness of the model. Few linear programming (LP)-based methods can be found that address the reachability problem, and some of these are suitable for optimal control problems. However, due to an inherent state explosion they are difficult to implement; other methods run easily into deadlock as they lack appropriate mechanisms to avoid the firing of critical transitions (T. Matsumoto and A. Tarek, in Proceedings of the 35th IEEE Conference on Decision and Control, Kobe, Japan, 1996-12, pp. 4459–4468). In this paper an improved and easy to implement method is proposed that combines the Optimality Principle and Linear Programming (OP + LP) techniques to find an Optimal Legal Firing Sequence (OLFS) in PNs. This method can be applied to ordinary PNs with self-loops, avoids deadlocks, and can also be used for general PNs having cycles.

In bounded model checking (BMC)-based verifica- tion flows lack of reachability constraints often leads to false negatives. At present, it is daily practice of a verification engineer to identify the missing reachability constraints by manually inspecting the design code and by analyzing counterexamples. This, unfortunately, requires a lot of effort and is prone to errors. We propose an algorithm to

In this paper we present an approach to approximate reachability computation for nonlinear continuous systems. Rather than studying a complex nonlinear system x = g(x), we study an approximating system x = f(x) which is easier to handle. The class of approximating systems we consider in this paper is piecewise linear, obtained by interpolating g over a mesh. In order to be conservative, we add a bounded input in the approximating system to account for the interpolation error. We thus develop a reachability method for systems with input, based on the relation between such systems and the corresponding autonomous systems in terms of reachable sets. This method is then extended to the approximate piecewise linear systems arising in our construction. The final result is a reachability algorithm for nonlinear continuous systems which allows to compute conservative approximations with as great degree of accuracy as desired, and more importantly, it has good convergence rate. If g is a C 2 function, our method is of order 2. Furthermore, the method can be straightforwardly extended to hybrid systems.

Photonic Network Communications, 2:2, 185±198, 2000 © 2000 Kluwer Academic Publishers. Manufactured in The Netherlands. ... An Optical Layer Lightpath Management Protocol for WDM AONs ... Debashis Saha* Department of Computer Science & Engineering, ...

Predicate abstraction has emerged to be a powerful technique for extracting finite-state models from infinite-state discrete programs. Th is paper presents algorithms and tools for reachability analysis of hybrid systems by combining the notion of predicate abstraction with recent techniques for approximating the set of reachable states of linear systems using polyhedra.Giv en a hybrid system and a set of userde fined boolean predicates, we consider the finite discrete quotient whose states correspond to all possible truth assignments to the input predicates. T he tool performs an on-the-fly exploration of the abstract system. We demonstrate the feasibility of the proposed technique by analyzing a parametric timing-based mutual exclusion protocol and safety of a simple controller for vehicle coordination.

We consider verification of safety properties for concurrent real-timed systems modelled as timed Petri nets by performing symbolic forward reachability analysis. We introduce a formalism, called region generators, for representing sets of markings of timed Petri nets. Region generators characterize downward closed sets of regions and provide exact abstractions of sets of reachable states with respect to safety properties. We show that the standard operations needed for performing symbolic reachability analysis are computable for region generators. Since forward reachability analysis is necessarily incomplete, we introduce an acceleration technique to make the procedure terminate more often on practical examples. We have implemented a prototype for analyzing timed Petri nets and used it to verify a parameterized version of Fischer's protocol, Lynch and Shavit's mutual exclusion protocol and a producer-consumer protocol. We also used the tool to extract finite-state abstracti...

Adaptivity requires at least frequent, and ideally real-time, updates and also requires the ability to analyze, respond and reconfigure. Such network management flexibility requires several types of information and capabilities, which include response of the network to node failure, reachability of nodes, and boundary control. The first issue determines how the network will respond to a "problem", which might be caused by an internal defect of the node or by a failure caused by external faults through the environment, accidental user error, or malicious input. In this event, network analysis on reachability can provide input for routing around the disabled node in order to maintain connectivity for as much of the network as possible. Furthermore, up- front reachability analysis also helps to identify potential access which is unwanted and thus aids in intrusion avoidance. The problem is exacerbated when multiple nodes fail, e.g., distributed denial of service. In this case...

We present a methodology for characterizing, analyzing, and synthesizing swarm behaviors using both a macroscopic continuous model that represents a swarm as a continuum and a macroscopic discrete model that enumerates individual agents. Our methodology is applied to a dynamical model of ant house hunting, a decentralized process in which a colony attempts to emigrate to the best site among