Search

Algorithms and protocols with time dependent behavior are often specified formally using timed automata. For practical real-time systems, besides real-valued clock variables, these specifications typically contain discrete data variables with nontrivial data flow. In this paper, we propose a configurable lazy abstraction framework for the location reachability problem of timed automata that potentially contain discrete variables. Moreover, based on our previous work, we uniformly formalize in our framework several abstraction refinement strategies for both clock and discrete variables that can be freely combined, resulting in many distinct algorithm configurations. Besides the proposed refinement strategies, the configurability of the framework allows the integration of existing efficient lazy abstraction algorithms for clock variables based on $${\textit{LU}}$$ LU -bounds. We demonstrate the applicability of the framework and the proposed refinement strategies by an empirical evaluation on a wide range of timed automata models, including ones that contain discrete variables or diagonal constraints.

The increasing complexity of reactive systems can be mitigated with the use of components and composition languages in model-driven engineering. Designing composition languages is a challenge itself as both practical applicability (support for different composition approaches in various application domains), and precise formal semantics (support for verification and code generation) have to be taken into account. In our Gamma Statechart Composition Framework, we designed and implemented a composition language for the synchronous, cascade synchronous and asynchronous composition of statechart-based reactive components. We formalized the semantics of this composition language that provides the basis for generating composition-related Java source code as well as mapping the composite system to a back-end model checker for formal verification and model-based test case generation. In this paper, we present the composition language with its formal semantics, putting special emphasis on design decisions related to the language and their effects on verifiability and applicability. Furthermore, we demonstrate the design and verification functionality of the composition framework by presenting case studies from the cyber-physical system domain.

Since their invention, Petri nets have provided modelling and analysis methods to support the design of correct, reliable and robust systems. This motivated our work to develop PetriDotNet , a Petri net editor and analysis tool. In this paper we overview the supported modelling formalisms and the analysis methods included in PetriDotNet . Next, we present eight different industrial case studies, demonstrating the wide variety of scenarios where Petri nets and PetriDotNet can help the design, development and analysis of industrial systems. Our original goal with PetriDotNet was to provide an educational tool to our students, however our efforts led to a framework being able to serve both academic and industrial needs.

Efficient symbolic and explicit-state model checking approaches have been developed for the verification of linear time temporal logic (LTL) properties. Several attempts have been made to combine the advantages of the various algorithms. Model checking LTL properties usually poses two challenges: one must compute the synchronous product of the state space and the automaton model of the desired property, then look for counterexamples that is reduced to finding strongly connected components (SCCs) in the state space of the product. In case of concurrent systems, where the phenomenon of state space explosion often prevents the successful verification, the so-called saturation algorithm has proved its efficiency in state space exploration. This paper proposes a new approach that leverages the saturation algorithm both as an iteration strategy constructing the product directly, as well as in a new fixed-point computation algorithm to find strongly connected components on-the-fly by incrementally processing the components of the model. Complementing the search for SCCs, explicit techniques and component-wise abstractions are used to prove the absence of counterexamples. The resulting on-the-fly, incremental LTL model checking algorithm proved to scale well with the size of models, as the evaluation on models of the Model Checking Contest suggests.

The Gamma Statechart Composition Framework is an integrated tool to support the design, verification and validation as well as code generation for component-based reactive systems. The behavior of each component is captured by a statechart, while assembling the system from components is driven by a domain-specific composition language. Gamma automatically synthesizes executable Java code extending the output of existing statechart-based code generators with composition related parts, and it supports formal verification by mapping composite statecharts to a back-end model checker. Execution traces obtained as witnesses during verification are back-annotated as test cases to replay an error trace or to validate external code generators. Tool demonstration video: https://youtu.be/ng7lKd1wlDo

In this paper, we present Theta, a configurable model checking framework. The goal of the framework is to support the design, execution and evaluation of abstraction refinement-based reachability analysis algorithms for models of different formalisms. It enables the definition of input formalisms, abstract domains, model interpreters, and strategies for abstraction and refinement. Currently it contains front-end support for transition systems, control flow automata and timed automata. The built-in abstract domains include predicates, explicit values, zones and their combinations, along with various refinement strategies implemented for each. The configurability of the framework allows the integration of several abstraction and refinement methods, this way supporting the evaluation of their advantages and shortcomings. We demonstrate the applicability of the framework by use cases for the safety checking of PLC, hardware, C programs and timed automata models.

Statecharts are frequently used as a modeling formalism in the design of state-based systems. Formal verification techniques are also often applied to prove certain properties about the behavior of the system. One of the most efficient techniques for formal verification is Counterexample-Guided Abstraction Refinement (CEGAR), which reduces the complexity of systems by automatically building and refining abstractions. In our paper we present a novel adaptation of the CEGAR approach to hierarchical statechart models. First we introduce an encoding of the statechart to logical formulas that preserves information about the state hierarchy. Based on this encoding we propose abstraction and refinement techniques that utilize the hierarchical structure of statecharts and also handle variables in the model. The encoding allows us to use SMT solvers for the systematic exploration and verification of the abstract model, including also bounded model checking. We demonstrate the applicability and efficiency of our abstraction techniques with measurements on an industry-motivated example., In Proceedings FESCA 2017, arXiv:1703.06590

Prioritised Petri net is a powerful modelling language that often constitutes the core of even more expressive modelling languages such as GSPNs (Generalized Stochastic Petri nets). The saturation state space traversal algorithm has proved to be efficient for non-prioritised concurrent models. Previous works showed that priorities may be encoded into the transition relation, but doing so defeats the main idea of saturation by spoiling the locality of transitions. This paper presents an extension of saturation to natively handle priorities by considering the priority-related enabledness of transitions separately, adopting the idea of constrained saturation. To encode the highest priority of enabled transitions in every state we introduce edge-valued interval decision diagrams. We show that in case of Petri nets, this data structure can be constructed offline. According to preliminary measurements, the proposed solution scales better than previously known matrix decision diagram-based approaches, paving the way towards efficient stochastic analysis of GSPNs and the model checking of prioritised models.

Stochastic aspects of complex systems require more and more involved analysis approaches. Answering reachability and related analysis questions can often be reduced to steady-state, transient, reward or sensitivity value analysis of stochastic models. In this paper we introduce a configurable stochastic analysis framework which supports the user to combine explicit, symbolic and numerical algorithms to efficiently compute the measures of stochastic models. Beyond the well-known algorithms from the field, we also developed an experimental version of an Induced Dimensionality Reduction Stabilized numerical solver to compute steady-state probabilities of Markovian models. As far as we know, this is the first attempt to exploit this algorithm in stochastic analysis. We have conducted experiments on different combinations of the algorithms on various models to assess their advantages and disadvantages in the analysis. This information can be used by the user to choose the combination of algorithms being efficient solving the analysis problem.

PetriDotNet is an extensible Petri net editor and analysis tool originally developed to support the education of formal methods. The ease of use and simple extensibility fostered more and more algorithmic developments. Thanks to the continuous interest of developers (especially M.Sc. and Ph.D. students who choose PetriDotNet as the framework of their thesis project), by now PetriDotNet became an analysis platform, providing various cutting-edge model checking algorithms and stochastic analysis algorithms. As a result, industrial application of the tool also emerged in recent years. In this paper we overview the main features and the architecture of PetriDotNet, and compare it with other available tools.

Formal methods can effectively support the model driven develoment and analysis of IT applications in many domains. Typically, the domain-specific engineering models are transformed to formal analysis models (to compute measures that help the designer in verifying the design decisions) and verified models are mapped to test and implementation related software artefacts. An overview of four European projects demonstrates the use of support tools and tool integration facilities in development processes of systems having in sight the demand of certification according to domain-specific standards.

The paper introduces a method which allows quantitative dependability analysis of systems modeled by using the Unified Modeling Language (UML) statechart diagrams. The analysis is performed by transforming the UML model to stochastic reward nets (SRNs). A large subset of statechart model elements is supported including event processing, state hierarchy and transition priorities. The transformation is presented by a set of SRN patterns. Performance-related measures can be directly derived using SRN tools, while dependability analysis requires explicit modeling of erroneous states and faulty behavior.

Programmable logic controllers are typically programmed in one of the five languages defined in the IEC 61131 standard. While the ability to choose the appropriate language for each program unit may be an advantage for the developers, it poses a serious challenge to verification methods. In this paper we analyse and compare these languages to show that the ST programming language can efficiently and conveniently represent all PLC languages for formal verification purposes. Furthermore, we provide a translation method from IL to ST programming languages (for the Siemens implementation), together with a sketch of proof for its correctness. This allows the usage of the ST-based PLCverif model checking method for safety PLC programs.

The behavior of practical safety critical systems often combines real-time behavior with structured data flow. To ensure correctness of such systems, both aspects have to be modeled and formally verified. Time related behavior can be efficiently modeled and analyzed in terms of timed automata. At the same time, program verification techniques like abstract interpretation and software model checking can efficiently handle data flow. In this paper, we describe a simple formalism that represents both aspects of such systems in a uniform and explicit way, thus enables the combination of formal analysis methods for real-time systems and software using standard techniques.

Failure Mode and Effects Analysis (FMEA) is a systematic technique to explore the possible failure modes of individual components or subsystems and determine their potential effects at the system level. Applications of FMEA are common in case of hardware and communication failures, but analyzing software failures (SW-FMEA) poses a number of challenges. Failures may originate in permanent software faults commonly called bugs, and their effects can be very subtle and hard to predict, due to the complex nature of programs. Therefore, a behavior-based automatic method to analyze the potential effects of different types of bugs is desirable. Such a method could be used to automatically build an FMEA report about the fault effects, or to evaluate different failure mitigation and detection techniques. This paper follows the latter direction, demonstrating the use of a model checking-based automated SW-FMEA approach to evaluate error detection and fault tolerance mechanisms, demonstrated on a case study inspired by safety-critical embedded operating systems.

Due to their distributed/parallel and data-driven nature, control systems can easily be modeled according to a data flow approach. Control systems are very often real-time systems; therefore, a formalism able to capture timing is required. In this paper we introduce a data flow model that includes time and priority for specifying real-time control systems and we give its formal semantics. The control system is specified by a data flow network which, beside the controller, may include the model of the plant at some abstraction level. Time is associated to any computational activity and time accounting is made directly in the model and not as a separate issue. Priorities allow to deal with events, as alarm signals, which cannot be delayed. A general framework for the indirect evaluation of the model is introduced, and a data flow network to timed Petri net transformation is defined allowing the utilization of the automatic tools of Petri nets for analyzing the temporal properties of the data flow network. The approach is illustrated by an example in which, after the application of the transformation, selected performance measures are computed. © 1998 Elsevier Science Ltd. All rights reserved.

International audience; Dealing with large, critical mobile systems and infrastructures where ongoing changes and resilience are paramount leads to very complex and difficult challenges for system evaluation. These challenges call for approaches that are able to integrate several evaluation methods for the quantitative assessment of QoS indicators which have been applied so far only to a limited extent. In this paper, we propose the holistic evaluation framework developed during the recently concluded FP6-HIDENETS project. It is based on abstraction and decomposition, and it exploits the interactions among different evaluation techniques including analytical, simulative, and experimental measurement approaches, to manage system complexity. The feasibility of the holistic approach for the analysis of a complete end-to-end scenario is first illustrated presenting two examples where mobility simulation is used in combination with stochastic analytical modeling, and then through the development and implementation of an evaluation workflow integrating several tools and model transformation steps.

System development processes are typically supported by dozens of different tools that assist the designer in various phases of development like modeling, verification, source code generation, testing. Tool-chains can be formed by the integration of tools that are related to the subsequent steps of the process. In this paper, we present a service-oriented, metamodel-driven, process-centric approach for the definition and execution of these tool-chains. Related data are handled as an important part of the process as the traceability of these is needed for the certification of the systems. The implementation is provided as an open, extensible framework. The approach is demonstrated using a model based test case generation process applied for automotive and railway systems.

Software testing is the process of evaluating the quality of the software under test (SUT) by controlled execution, with the primary aim to reveal inadequate behavior. Despite the automation offered by modern development environments, the process of test data generation remains a largely manual task. In this paper we present a model-based approach for the generation of test data, using searchbased software engineering technique.

A watchdog processor (WDP) is a relatively simple coprocessor built for concurrent, information compaction based error detection in the main program control flow. A new algorithm called SEIS (Signature Encoded Instruction Stream) is presented for assigning signatures to high level-instructions. The main idea of this method is to embed the information necessary to the program flow check into the signatures themselves, thus avoiding large reference databases in the WDP and allowing high operational speed. Solutions for a fault-tolerant multiprocessing and multi-tasking implementation are described as well.

The VIATRA (visual automated model transformations) framework is the core of a transformation-based verification and validation environment for improving the quality of systems designed using the Unified Modeling Language by automatically checking consistency, completeness, and dependability requirements. In the current paper, we present an overview of (i) the major design goals and decisions, (ii) the underlying formal methodology based on metamodeling and graph transformation, (iii) the software architecture based upon the XMI standard, and (iv) several benchmark applications of the VIATRA framework.

The work in this paper is devoted to the definition of a dependability modeling and model based evaluation approach based on UML models. It is to be used in the early phases of the system design to capture system dependability attributes like reliability and availabiUty, thus providing guidelines for the choice among different architectural and design solutions. We show how structural UML diagrams can be processed to filter out the dependability related information and how a system-wide dependability model is constructed. Due to the modular construction, this model can be refined later as more detailed information becomes available. We discuss the model refinement based on the General Resource Model, an extension of UML. We show that the dependability model can be constructed automatically by using graph transformation techniques.

Signature based error detection techniques (e.g. the application of watchdog processors) can be easily extended to support software debugging. The run-time sequence of signatures is stored in an extension of the traditional checker. As the signatures identify the states of the program, a trace of the statements executed by the checked processor is available. The signature buffer can be efficiently utilized if the signature sequence is compressed. In the paper, two real-time compression methods are presented and compared. The general method uses predefined dictionaries, while the other one utilizes the structural information encoded in the signatures.

The paper presents techniques that enable the modeling and analysis of redundancy schemes in distributed object-oriented systems. The replication manager, as a core part of the redundancy scheme, is modeled by using UML statecharts. The flexibility of the statechart-based modeling, which includes event processing and state hierarchy, enables an easy and efficient modeling of replication strategies as well as repair and recovery policies. The statechart is transformed to a Petri-net based dependability model, which also incorporates the models of the replicated objects. By the analysis of the Petri-net model the designer can obtain reliability and availability measures that can be used in the early phases of the design to compare alternatives and find dependability bottlenecks. Our approach is illustrated by an example.

The paper presents techniques to support the dependability modeling and analysis of distributed object-oriented applications that are designed according to the Fault Tolerant CORBA (FT-CORBA) specification. First the construction of a high-level dependability model is described. It is based on the architecture of the application and allows the analysis of the fault tolerance strategies and properties that are directly supported by the standard infrastructure. Then a technique to construct a refined dependability model is presented. It exploits the detailed behavioral model of the object responsible for replica maintenance. The UML statechart of this object is transformed to a stochastic Petri net that forms the core of the dependability model. In this way the designer is allowed to utilize the full power of statecharts to construct models of application-dependent replication strategies and recovery policies.

This paper describes methods and tools for automated safety analysis of UML statechart specifications. The general safety criteria described in the literature are reviewed and automated analysis techniques are proposed. The techniques based on OCL expressions and graph transformations are detailed and their limitations are discussed. To speed up the checker methods, a reduced form for UML statecharts is introduced. Using this form, the correctness and completeness of some checker methods can be proven. An example illustrates the application of the tools developed so far.

Statechart Diagrams are a notation for describing behaviours in the framework of UML, the Unified Modeling Language of object-oriented systems. UML is a semi-formal language, with a precisely defined syntax and static semantics but with an only informally specified dynamic semantics. UML Statechart Diagrams differ from classical statecharts, as defined by Harel, for which formalizations and results are available in the literature. This paper sets the basis for the development of a formal semantics for UML Statechart Diagrams based on Kripke structures. This forms the first step towards model checking of UML Statechart Diagrams. We follow the approach proposed by Mikk and others: we first map Statechart Diagrams to the intermediate format of extended hierarchical automata and then we define an operational semantics for these automata. We prove a number of properties of such semantics which reflect the design choices of UML Statechart Diagrams.

This paper deals with the automatic dependability analysis of systems designed using UML. An automatic transformations is defined for the generation of models to capture systems dependability attributes, like reliability. The transformation concentrates on structural UML views, available early in the design, to operate at different levels of refinement, and tries to capture only the information relevant for dependability to limit the size (state space) of the models. Due to the modular construction, these models can be refined later as more detailed, relevant information becomes available. Moreover a careful selection of those, critical, parts to be detailed allows to avoid explosion of the size. An implementation of the transformation is in progress and will be integrated in the toolsets available for rite ESPRIT LTR HIDE project.

Even though a thorough system specification improves the quality of the design, it is not sufficient to guarantee that a system will satisfy its reliability targets. Within this paper, we present an application example of one of the activities performed in the European ESPRIT project HIDE, aiming at the creation of an integrated environment where design toolsets based on UML are augmented with modeling and analysis tools for the automatic validation of the system under design. We apply an automatic transformation from UML diagrams to Timed Petri Nets for model based dependability evaluation. It allows a designer to use UML as a front-end for the specification of both the system and the user requirements, and to evaluate dependability figures of the system since the early phases of the design, thus obtaining precious clues for design refinement. The transformation completely hides the mathematical background, thus eliminating the need for a specific expertise in abstract mathematics and the tedious remodeling of the system for mathematical analysis.

The need of efficient implementation, safety and performance requires early validation in the design of computer control systems. The detailed timing and reachability analysis in the development process is particularly important if we design equipments or algorithms of high performance and availability. In this paper we present a case study related to the early validation of control systems modeled by data flow networks. The model is validated indirectly as it is transformed to Petri nets in order to be able to utilize the tools available for Petri nets.

A new control flow checking scheme, based on assigned-signature checking by a watchdog processor, is presented. This scheme is suitable for a multitasking, multiprocessor environment. The hardware overhead is comparatively low because of three reasons: first, hierarchically structured, the scheme uses only a single watchdog processor to monitor multiple processes or processors. Second, as an assigned-signature scheme it does not require monitoring the instruction bus of the processors. Third, the run-time and reference signatures are embedded into the checked program; thus, in the watchdog processor neither a reference database nor a time-consuming search and compare engine is required.

In this paper we introduce an approach of aspect-oriented modelling and analysis of information systems. First we give an overview of the concepts of Aspect Oriented Programming and provide an outlook to model aspect-oriented programs. On the basis of this introduction, we describe a method of using aspects at the modelling level and weaving them into a single integrated model. Finally, we extend this framework with the automatic construction of analysis models based on separate aspect models. In our example, fault tolerance structures are modelled by aspects and the analysis model is a dependability model that is used to determine the non-functional properties of the system like reliability and availability. In this way the separate design of the functionality and the dependability is supported and the design decisions concerning fault tolerance can be analysed on the basis of the dependability model.