Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCompositional Verification for Timed Systems Based on Automatic Invariant Generation
142
0
0.0
(
0
)
Added by
Lacramioara Astefanoaei
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We propose a method for compositional verification to address the state space explosion problem inherent to model-checking timed systems with a large number of components. The main challenge is to obtain pertinent global timing constraints from the timings in the components alone. To this end, we make use of auxiliary clocks to automatically generate new invariants which capture the constraints induced by the synchronisations between components. The method has been implemented in the RTD-Finder tool and successfully experimented on several benchmarks.
rate research
Read More
Time-Sensitive Distributed Systems (TSDS), such as applications using autonomous drones, achieve goals under possible environment interference (eg, winds). Moreover, goals are often specified using explicit time constraints which must be satisfied by the system emph{perpetually}. For example, drones carrying out the surveillance of some area must always have emph{recent pictures}, ie, at most $M$ time units old, of some strategic locations. This paper proposes a Multiset Rewriting language with explicit time for specifying and analysing TSDSes. We introduce two properties, emph{realizability} (some trace is good) and emph{survivability} (where, in addition, all admissible traces are good). A good trace is an infinite trace in which goals are perpetually satisfied. We propose a class of systems called emph{progressive timed systems} (PTS), where intuitively only a finite number of actions can be carried out in a bounded time period. We prove that for this class of systems both the realizability and the survivability problems are PSPACE-complete. Furthermore, if we impose a bound on time (as in bounded model-checking), we show that for PTS, realizability becomes NP-complete, while survivability is in the $Delta_2^p$ class of the polynomial hierarchy. Finally, we demonstrate that the rewriting logic system Maude can be used to automate time bounded verification of PTS.
The paper presents our research on quantifier elimination (QE) for compositional reasoning and verification. For compositional reasoning, QE provides the foundation of our approach, serving as the calculus for composition to derive the strongest system-property in a single step, from the given component atomic-properties and their interconnection relation. We first developed this framework for time-independent properties, and later extended it to time-dependent property composition. The extension requires, in addition, shifting the given properties along time to span the time horizon of interest, he least of which for the strongest system-property is no more than the total time horizons of the component level atomic-properties. The system-initial-condition is also composed from atomic-initial-conditions of the components the same way. It is used to verify a desired system-level property, alongside the derived strongest system-property, by way of induction. Our composition approach is uniform regardless of the composition types (cascade/parallel/feedback) for both time-dependent and time-independent properties. We developed a new prototype verifier named ReLIC (Reduced Logic Inference for Composition) that implements our above approaches. We demonstrated it through several illustrative and practical examples. Further, we advanced the $k$-induction based model-checking with QE capabilities, by formulating its base and inductive steps into QE problems where all the variables are universally quantified. Our integration of the QE solver Redlog with the $k$-induction based model-checking tool JKind, shows the successful solving of a non-linear problem that the SMT capable JKind failed to resolve. Finally, we also showcase the recent adoption of our approaches within an industrial V&V tool suite for augmented static analysis of Simulink models and Deep Neural Networks (DNNs).
Software engineering of modular robotic systems is a challenging task, however, verifying that the developed components all behave as they should individually and as a whole presents its own unique set of challenges. In particular, distinct components in a modular robotic system often require different verification techniques to ensure that they behave as expected. Ensuring whole system consistency when individual components are verified using a variety of techniques and formalisms is difficult. This paper discusses how to use compositional verification to integrate the various verification techniques that are applied to modular robotic software, using a First-Order Logic (FOL) contract that captures each components assumptions and guarantees. These contracts can then be used to guide the verification of the individual components, be it by testing or the use of a formal method. We provide an illustrative example of an autonomous robot used in remote inspection. We also discuss a way of defining confidence for the verification associated with each component.
Runtime verification is checking whether a system execution satisfies or violates a given correctness property. A procedure that automatically, and typically on the fly, verifies conformance of the systems behavior to the specified property is called a monitor. Nowadays, a variety of formalisms are used to express properties on observed behavior of computer systems, and a lot of methods have been proposed to construct monitors. However, it is a frequent situation when advanced formalisms and methods are not needed, because an executable model of the system is available. The original purpose and structure of the model are out of importance; rather what is required is that the system and its model have similar sets of interfaces. In this case, monitoring is carried out as follows. Two black boxes, the system and its reference model, are executed in parallel and stimulated with the same input sequences; the monitor dynamically captures their output traces and tries to match them. The main problem is that a model is usually more abstract than the real system, both in terms of functionality and timing. Therefore, trace-to-trace matching is not straightforward and allows the system to produce events in different order or even miss some of them. The paper studies on-the-fly conformance relations for timed systems (i.e., systems whose inputs and outputs are distributed along the time axis). It also suggests a practice-oriented methodology for creating and configuring monitors for timed systems based on executable models. The methodology has been successfully applied to a number of industrial projects of simulation-based hardware verification.
We define a pi-calculus variant with a costed semantics where channels are treated as resources that must explicitly be allocated before they are used and can be deallocated when no longer required. We use a substructural type system tracking permission transfer to construct coinductive proof techniques for comparing behaviour and resource usage efficiency of concurrent processes. We establish full abstraction results between our coinductive definitions and a contextual behavioural preorder describing a notion of process efficiency w.r.t. its management of resources. We also justify these definitions and respective proof techniques through numerous examples and a case study comparing two concurrent implementations of an extensible buffer.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
