Search

The finite-state verification techniques such as model checking allow for automated checking whether system model described with automata satisfy temporal properties, or not. The temporal properties should be typically specified in temporal logic formulae, which is a difficult task for programmers who aren't verification experts. Therefore, there is a few of research to propose description languages with which non-experts can accurately express temporal requirements on system's behaviors and the methods transforming them automatically into temporal property specification of particular model checker. We analyzed various researches aimed at the construction of property specifications, that is, machine translation from natural language to temporal logical formula, property specification pattern and graphical scenarios for specifying property, and so on. Based on the analysis, in this paper, we present a visual language called TimeLineDepic, which is a user-friendly graphical notation for temporal property description and whose expressive power is same as other languages. And we propose a method to transform TimeLineDepic to buchi automata (never claim) and insert it in promela-based model for model checker SPIN. [ABSTRACT FROM AUTHOR]

Formal approaches and tools have been defined, implemented and successfully applied to support the design and development of Collective Adaptive Systems. These tools are highly specialised in their fields, and their integration requires an effort. In this paper, we introduce Sibilla , a Java modular tool that facilitates the integration of multiple specification languages for supporting quantitative analysis of systems. After a description of the general architecture of Sibilla , the main features of the tool are discussed via simple examples. • Sibilla is a modular framework for specification and analysis of Collective Systems. • Sibilla integrates tools for simulation and statistical analysis/model-checking. • Sibilla simplifies the integration of new languages and tools. • Sibilla can be easily deployed on multiple platforms and Cloud Services. [ABSTRACT FROM AUTHOR]

This paper discusses a Unified Modelling Language (UML) based formal verification methodology for early error detection in the model-based software development cycle. Our approach proposes a UML-based formal verification process utilising functional and behavioural modelling artifacts of UML. It reinforces these artifacts with formal model transition and property verification. The main contribution is a UML to Labelled Transition System (LTS) Translator application that automatically converts UML Statecharts to formal models. Property specifications are derived from system requirements and corresponding Computational Tree Logic (CTL)/Linear Temporal Logic (LTL) model checking procedure verifies property entailment in LTS. With its ability to verify CTL and LTL specifications, the methodology becomes generic for verifying all types of embedded system behaviours. The steep learning curve associated with formal methods is avoided through the automatic formal model generation and thus reduces the reluctance of using formal methods in software development projects. A case study of an embedded controller used in military applications validates the methodology. It establishes how the methodology finds its use in verifying the correctness and consistency of UML models before implementation. [ABSTRACT FROM AUTHOR]

One of the many different purposes of software architecture descriptions is contributing to an early analysis of the architecture with respect to quality attributes. The critical nature of many software systems calls for formal approaches aiming at precisely verifying if their designed architectures can meet important properties such as consistency, completeness, and correctness. In this context, it is worthwhile investigating the role of architecture descriptions to support the formal verification of software architectures to ensure their quality, as well as how such a process happens and is supported by existing languages and verification tools. To evaluate the research landscape on this subject, we have carried out a systematic mapping study in which we collected and analyzed studies available at the literature on formal verification of architecture descriptions. This work contributes with (i) a structured overview and taxonomy of the current state of the art on this topic and (ii) the elicitation of important issues to be addressed in future research.

The first distributed snapshot algorithm was invented by Chandy and Lamport: Chandy-Lamport distributed snapshot algorithm (CLDSA). Distributed snapshot algorithms are crucial components to make distributed systems fault tol- erant. Such algorithms are extremely important because many modern key software systems are in the form of distributed systems and should be fault tolerant. There are at least two desired properties such algorithms should satisfy: 1) the distributed snapshot reachability property (called the DSR property) and 2) the ability to run concurrently with, but not alter, an underlying distributed system (UDS). This paper identifies subtle errors in a paper on formalization of the DSR property and shows how to correct them. We give a more faithful formal definition of the DSR property; the definition involves two state machines - one state machine MUDS that formalizes a UDS and the other MCLDSA that formalizes the UDS on which CLDSA is superimposed (UDS-CLDSA) - and can be used to more precise model checking of the DSR property for CLDSA. We also prove a theorem on equivalence of our new definition and an existing one that only involves MCLDSA to guarantee the validity of the existing model checking approach. Moreover, we prove the second property, namely that CLDSA does not alter the behaviors of UDS. [ABSTRACT FROM AUTHOR]

Testing in the automotive industry is supposed to guarantee that vehicles are shipped without any flaw. Respective processes are complex, due to the variety of components and electronic devices in modern vehicles. To achieve error-free processes, their formal analysis is required. Specifying and maintaining properties the processes must satisfy in a user-friendly way is a core requirement on any verification system. We have observed that there are few property templates that testing processes must adhere to, and we describe these templates. They depend on the context of the processes, e.g., the components of the vehicle or testing stations. We have developed a framework that instantiates the templates of properties at verification time and then verifies the process against these instances. To allow an automatic verification we develop a transformation of the commissioning process to a Petri net. Using a novel approach, we are able to report the found violations to the user in a user-friendly way. Our empirical evaluation with the industrial partner has shown that our framework does detect property violations in processes. From expert interviews we conclude that our framework is user-friendly and well suited to operate in a real production environment. [ABSTRACT FROM AUTHOR]

Although a significant body of research in the area of formal verification and model checking tools of software and hardware systems exists, the acceptance of these tools by industry and end-users is rather limited. Beside the technical problem of state space explosion, one of the main reasons for this limited acceptance is the unfamiliarity of users with the required specification notation. Requirements have to be typically expressed as temporal logic formalisms and notations. Property specification patterns were successfully introduced to bridge this gap between users and model checking tools. They also enable non-experts to write formal specifications that can be used for automatic model checking. In this paper, we propose an abstract high level pattern-based approach to the description of property specifications based on Use Case Maps (UCM). We present a set of commonly used properties with their specifications that are described in terms of occurrence, ordering and temporal scopes of actions. Furthermore, our approach also supports the description of properties with respect to their architectural scope. We provide a mapping of our UCM property specification patterns in terms of CTL, TCTL and Architectural TCTL (ArTCTL), an extension to TCTL, introduced in this research that provides temporal logics with architectural scopes. We illustrate the use of our pattern system for requirement specifications of an IP Header compression feature. [ABSTRACT FROM AUTHOR]

The application domain, such as communication networks and embedded controllers for telephony, automobiles, trains and avionics systems, requires very high quality reactive systems, so an important phase in the development of reactive systems is the verification of their conceptual models before implementation. Normally in the requirement analysis phase, system property can be represented as an input and output labeled transition system (IOLTS), which is a transition system labeled by inputs and outputs between the system and the environment. This paper describes an attempt to propose an approach to verify Statechart specifications for reactive systems given IOLTS property specifications. We develop a suitable semantics model — observable semantics, an abstract semantics model only which describes outside observable behavior and suffers from less state explosion problem by reducing infinite or large state spaces to small ones. Then we propose two methods to verify the conformance between a given IOLTS property specification and a Statechart specification: two-phase verification and on-the-fly verification. Compared with two-phase verification, on-the-fly verification needs less storage and computation-time, especially when the target Statechart specification is very large or likely to have many errors. [ABSTRACT FROM AUTHOR]

This paper presents an approach to support run-time verification of software systems that combines two existing tools, Prospec and Java-MaC, into a single framework. Prospec can be used to clarify natural language specifications for sequential, concurrent, and nondeterministic behavior. In addition, Prospec assists the user in reading, writing, and understanding formal specifications through the use of property patterns and visual abstractions. Prospec automatically generates specifications written in Future Interval Logic (FIL). Java-MaC monitors Java programs at runtime to ensure adherence to a set of formally specified properties. Safety properties of a program are specified in the formal language Meta-Event Definition Language (MEDL). Java-MaC generates runtime components from specifications. The components are used to instrument the target program and determine whether the execution of the program violates any of the safety properties. This paper describes an algorithm for translating FIL formulas into MEDL formulas. It provides the transformation rules used by this algorithm, and it demonstrates the general correctness of the translation. [ABSTRACT FROM AUTHOR]

Model checking method is a widely used formal method for proving whether or not a given model satisfies properties, and for producing counter examples if the model does not satisfy properties. In this paper, we show model checking methods can be used for resource utilization analysis of systems. We specify system utilization properties using temporal logic called LTL, and find a bottleneck of system performance using model checking. [ABSTRACT FROM AUTHOR]

Prospec is a tool that assists practitioners in the elicitation and specification of system properties. Practitioners are guided by questions, definitions, and graphics. Prospec introduces the use of composite propositions to identify intended behavior when multiple conditions or events are considered. Multiple conditions or events may represent behavior such as sequences, concurrency, and non-determinism and may define the boundaries of scopes or type of patterns. Prospec is built upon the Specification Pattern System. The tool assists the analyst in making informed decisions about aspects of a specification that may have multiple interpretations. The end product of the tool is a formal specification in Future Interval Logic, Linear Temporal Logic, or Meta Event Definition Language. [ABSTRACT FROM AUTHOR]

We present a method and a tool for the verification of causal and temporal properties for embedded systems. We analyze trace streams resulting from the execution of virtual prototypes that combine simulated hardware and embedded software. The main originality lies in the use of logical clocks to abstract away irrelevant information from the trace. We propose a model-based approach that relies on domain specific languages (DSL). A first DSL, called TISL (trace item specification language), captures the relevant data structures. A second DSL, called STML (simulation trace mapping language), abstracts the simulation raw data into logical clocks, abstracting simulation data into relevant observation probes and thus reducing the trace streams size. The third DSL, called TPSL, defines a set of behavioral patterns that include widely used temporal properties. This is meant for users who are not familiar with temporal logics. Each pattern is transformed into an automata. All the automata are executed concurrently and each one raises an error if and when the related TPSL property is violated. The contribution is the integration of this pattern-based property specification language into the SimSoC virtual prototyping framework without requiring to recompile all the simulation models when the properties evolve. We illustrate our approach with experiments that show the possibility to use multi-core platforms to parallelize the simulation and verification processes, thus reducing the verification time. [ABSTRACT FROM AUTHOR]