Search

Safety-critical embedded systems must maintain their functionality even in the presence of single permanent hardware failure. Naive redundancy of hardware is often unaffordable and impractical, therefore alternative strategies must be explored for minimal cost fault tolerance. The objective of this article is to propose a methodology to evaluate formally safety strategies using satisfiability modulo theory solvers. Practically, the approach consists in providing a bounded model checking demonstration applied to the formal model of hardware. We show the capabilities of the approach on an efficient hardware accelerator designed to perform parallel computations of matrix multiplications and convolutions. [ABSTRACT FROM AUTHOR]

Digital systems are nowadays ubiquitous and often comprise an extremely high level of complexity. Guaranteeing the correct behavior of such systems has become an ever more pressing need for manufacturers. The correctness of digital systems can be addressed resorting to formal verification techniques, such as model checking. Currently, it is usually impossible to determine a priori the best algorithm to use given a verification task and, thus, portfolio approaches have become the de facto standard in model checking verification suites. This paper describes the most relevant algorithms and techniques, at the foundations of bit-level SAT-based model checking itself. [ABSTRACT FROM AUTHOR]

Modeling and verification are crucial in designing traffic light control systems, guaranteeing these systems meet desired operational properties and handle dynamic traffic conditions effectively. The design process involves addressing complexities such as route intricacy, congestion, timing, and prioritization, especially important in areas with multiple interconnected intersections. A key aspect of this process is developing a scalable model, essential for adapting to various traffic scenarios and intersection configurations. This paper presents a method using UPPAAL, a timed-automata tool, for modeling and verifying smart traffic light systems. We focus on creating scalable models, facilitating effective synchronization across intersections. Our approach includes templates and frameworks to assist in formalizing traffic light designs, emphasizing verification of safety, structural integrity, and performance. The results of our study reveal a significant usability in verification approaches through the use of formal model templates. Additionally, the model’s phases and stages, complete with adaptable time schedules, show flexibility in environments with variable parameters.

Proving that an unbounded distributed protocol satisfies a given safety property amounts to finding a quantified inductive invariant that implies the property for all possible instance sizes of the protocol. Existing methods for solving this problem can be described as search procedures for an invariant whose quantification prefix fits a particular template. We propose an alternative constructive approach that does not prescribe, a priori, a specific quantifier prefix. Instead, the required prefix is automatically inferred without any enumerative search by carefully analyzing the spatial and temporal regularity of the protocol. The key insight underlying this approach is that structural regularity and quantification are closely related concepts that express protocol invariance under different re-arrangements of its components and its unbounded evolution over time. We extended the finite-domain IC3/PDR algorithm to use these regularities and boost clause learning to automatically derive the required quantified inductive invariant by exploiting the connection between structural regularities and quantification. We also describe a procedure to automatically find a minimal finite size, the cutoff, that yields a quantified invariant proving safety for any size. Our approach is implemented in IC3PO, a new verifier for distributed protocols that significantly outperforms the state of the art, scales orders of magnitude faster, and robustly derives compact inductive invariants fully automatically. [ABSTRACT FROM AUTHOR]

The study of business process analysis and optimisation has attracted significant scholarly interest in the recent past, due to its integral role in boosting organisational performance. A specific area of focus within this broader research field is process mining (PM). Its purpose is to extract knowledge and insights from event logs maintained by information systems, thereby discovering process models and identifying process-related issues. On the other hand, statistical model checking (SMC) is a verification technique used to analyse and validate properties of stochastic systems that employs statistical methods and random sampling to estimate the likelihood of a property being satisfied. In a seamless business setting, it is essential to validate and verify process models. The objective of this paper is to apply the SMC technique in process mining for the verification and validation of process models with stochastic behaviour and large state space, where probabilistic model checking is not feasible. We propose a novel methodology in this research direction that integrates SMC and PM by formally modelling discovered and replayed process models and apply statistical methods to estimate the results. The methodology facilitates an automated and proficient evaluation of the extent to which a process model aligns with user requirements and assists in selecting the optimal model. We demonstrate the effectiveness of our methodology with a case study of a loan application process performed in a financial institution that deals with loan applications submitted by customers. The case study highlights our methodology's capability to identify the performance constraints of various process models and aid enhancement efforts. [ABSTRACT FROM AUTHOR]

In recent years, Model‐Based Systems Engineering (MBSE) practices have been applied in various industries to design, simulate and verify complex systems. The verification and validation (V&V) of such systems engineering models are crucial to develop high‐quality systems. However, this is a challenging problem due to the complexity of the models and semantic differences in how different tools interpret the models, which can undermine the validity of the obtained results if they go undiscovered. To address these issues, we propose (i) a subset of the SysML language for which the practical semantic integrity of tools can be achieved and (ii) a cloud‐based V&V framework for this subset, lifting verification to an industrial scale. We demonstrate the feasibility of our approach on an industrial‐scale model from the aerospace domain and summarize the lessons learned during transitioning formal verification tools to an industrial context. [ABSTRACT FROM AUTHOR]

Digital systems are nowadays ubiquitous and often comprise an extremely high level of complexity. Guaranteeing the correct behavior of such systems has become an ever more pressing need for manufacturers. The correctness of digital systems can be addressed resorting to formal verification techniques, such as model checking. Currently, it is usually impossible to determine a priori the best algorithm to use given a verification task and, thus, portfolio approaches have become the de facto standard in model checking verification suites. This paper describes the most relevant algorithms and techniques, at the foundations of bit-level SAT-based model checking itself.

Model‐Based Systems Engineering (MBSE) has been utilized in practice to design and behavioral modeling cyber‐physical systems. The Vee model helps frame MBSE's lifecycle approach, with system verification a vital aspect of the qualification process. However, popular modeling language tools in MBSE, such as Systems Modeling Language (SysML), are incapable of formally verifying these systems. Model checking allows for the development of formal system models similar in abstraction to SysML models for automatically checking if these formal models satisfy formal specifications. We propose an approach to translate behavioral diagrams in SysML, such as state‐machine diagrams, to the popular symbolic model checker NuSMV for formal verification. As a case study, we apply this process to autonomous multi‐differential drive robots (DDR). Subsequently, the NuSMV model is verified against some formal operational specifications obtained from the requirements diagram of the DDR. This system verification approach can help System Engineers identify design flaws or incorrect modeling or specifications that could be missed during the design phase through the results of the model checking process. [ABSTRACT FROM AUTHOR]

Verification of chatbot conversational flows is paramount to capturing and understanding chatbot behavior and predicting problems that would cause the entire flow to be restructured from scratch. The literature on chatbot testing is scarce, and the few works that approach this subject do not focus on verifying the communication sequences in tandem with the functional requirements of the conversational flow itself. However, covering all possible conversational flows of context-oriented chatbots through testing is not feasible in practice given the many ramifications that should be covered by test cases. Alternatively, model checking provides a model-based verification in a mathematically precise and unambiguous manner. Moreover, it can anticipate design flaws early in the software design phase that could lead to incompleteness, ambiguities, and inconsistencies. We postulate that finding design flaws in chatbot conversational flows via model checking early in the design phase may overcome quite a few verification gaps that are not feasible via current testing techniques for context-oriented chatbot conversational flows. Therefore, in this work, we propose a modeling strategy to design and verify chatbot conversational flows via the Uppaal model checking tool. Our strategy is materialized in the form of templates and a mapping of chatbot elements into Uppaal elements. To evaluate this strategy, we invited a few chatbot developers with different levels of expertise. The feedback from the participants revealed that the strategy is a great ally in the phases of conversational prototyping and design, as well as helping to refine requirements and revealing branching logic that can be reused in the implementation phase. [ABSTRACT FROM AUTHOR]

Automation systems within nuclear laboratories are intended to work under harsh operating conditions. Selective Production of Exotic Species (SPES) is a nuclear research facility currently under construction by the Istituto Nazionale di Fisica Nucleare, dedicated to the production and study of radioactive ion beams. Isotopes are produced within the target ion source unit, a vacuum vessel that must be replaced on a regular basis. The highly radioactive environment necessitates the deployment of a set of automated systems dedicated to the unit's remote management. To meet high-level security standards, the design of such instrumentation and control systems must include extensive verification. Based on specific safety requirements, model checking can be used to assess the systems' correctness. This article describes how to employ an integrated toolchain to design, simulate, formally verify, and deploy the control software for the Horizontal Handling Machine, a safety-critical remote handling system in operation at SPES. The IEC 61499 standard's adoption led to a redesign of the control logic. Following a preliminary online simulation, the closed-loop system has been formally verified using the NuSMV symbolic model checker, with the help of the FB2SMV converter. In addition, the Function Blocks Modeling Environment tool was used for automating verification and analyzing counterexamples.

In an article published in IEEE Access in 2020, researchers present an approach to using TLA+ for the formal verification of whether a network of SDN (Software-Defined Networking) switches implements the filtering rules of a given monolithic firewall. The distributed as well as monolithic firewalls are specified with TLA+. It is shown that the correctness of the former with respect to the latter can be verified automatically by using the TLC model checker. The main contributions of this paper are the following improvements of that approach. Firstly, by specifying switches without using any variables, the time needed for the model checking is reduced significantly. For example, the verification of the same networks takes a few seconds with the new approach and does not end after several hours with the previous one. Secondly, the following problem is solved. With the latter, if a monolithic firewall allows a packet to pass through, all the paths in the distributed firewall which the packet is routed on must allow the same. Otherwise, the model checker proclaims the distributed firewall to be in error. We present an additional approach to the verification, which gives a positive answer if at least one of the paths allows the packet to pass through.

We show how to construct temporal testers for the logic MITL, a prominent linear-time logic for real-time systems. A temporal tester is a transducer that inputs a signal holding the Boolean value of atomic propositions and outputs the truth value of a formula along time. Here we consider testers over continuous-time Boolean signals that use clock variables to enforce duration constraints, as in timed automata. We first rewrite the MITL formula into a “simple” formula using a limited set of temporal modalities. We then build testers for these specific modalities and show how to compose testers for simple formulae into complex ones. Temporal testers can be turned into acceptors, yielding a compositional translation from MITL to timed automata. This construction is much simpler than previously known and remains asymptotically optimal. It supports both past and future operators and can easily be extended. [ABSTRACT FROM AUTHOR]

As technology advances, hardware-centric systems are rapidly moving towards software-centric ones, and their complexity is rapidly increasing. In particular, systems directly related to safety require thorough verification. Model checking exhaustively explores the state space of the abstracted system to check whether properties written in a logical formula are achieved. In this paper, the control algorithm of the controller is verified using model checking to discover risk scenarios during the STPA steps. Two case studies are conducted using the widely used model checkers NuSMV and UPPAAL. We then explain the empirical results and compare two model checkers based on their characteristics. Finally, we discuss the benefits of applying model checking in the process of STPA. [ABSTRACT FROM AUTHOR]

Software development for robotic systems is traditionally performed based on simulations, manual code implementation, and testing. However, this software development approach can cause safety issues in some scenarios, including multiple robots sharing a workspace. When different robots are executing individual planned tasks, they may collide when not adequately coordinated. Safety problems related to coordination between robots may not be encountered during testing, depending on timing, but may occur during the system's operation. In this case, formal verification methods can provide a more reliable means to ensure the safety of robotic systems. This paper uses the formal method of model checking for the safety verification of multiple industrial robot manipulators with path conflicts. We give comparative results of two model-checking tools applied to a system with two robot manipulators. Whole workflows, from requirement specification to testing, are presented. [ABSTRACT FROM AUTHOR]

The hundreds of electronic control devices used in an automotive system can effectively communicate with one another, thanks to an in-vehicle network (IVN) like FlexRay. Even though every node in the network will be running on its local clock, a global notion of time is essential. The clock synchronisation algorithm accomplishes this global time between the nodes in FlexRay. In this era of self-driving cars, the vehicle’s safety is paramount. For the vehicle to operate safely and smoothly, timely communication of information is critical, and the clock synchronisation algorithm plays a vital role in this. It is essential to formally test the clock synchronisation algorithm’s correctness. This paper attempts to model and verify the clock synchronisation algorithm of FlexRay using formal methods, which in turn enhance the reliability of safety-critical automotive systems. The clock synchronisation is modelled as a network of six timed automata in the UPPAAL model checker. Three system models were developed, a model for an ideal clock, another for a drifting clock, and a third model considering propagation delay. The precision of the clocks is verified to be within the prescribed limits. Simulation studies are also conducted on the model to ensure that the clock’s drift is always within the precision. [ABSTRACT FROM AUTHOR]

Copyright of Automatisierungstechnik is the property of De Gruyter and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Graph neural networks have proven their effectiveness across a wide spectrum of graph-based tasks. Despite their successes, they share the same limitations as other deep learning architectures and pose additional challenges for their formal verification. To overcome these problems, we proposed a specification language, μ G , that can be used to program graph neural networks. This language has been implemented in a Python library called libmg that handles the definition, compilation, visualization, and explanation of μ G graph neural network models. We illustrate its usage by showing how it was used to implement a Computation Tree Logic model checker in our previous work, and evaluate its performance on the benchmarks of the Model Checking Contest. In the future, we plan to use μ G to further investigate the issues of explainability and verification of graph neural networks. [ABSTRACT FROM AUTHOR]

The study of business process analysis and optimisation has attracted significant scholarly interest in the recent past, due to its integral role in boosting organisational performance. A specific area of focus within this broader research field is process mining (PM). Its purpose is to extract knowledge and insights from event logs maintained by information systems, thereby discovering process models and identifying process-related issues. On the other hand, statistical model checking (SMC) is a verification technique used to analyse and validate properties of stochastic systems that employs statistical methods and random sampling to estimate the likelihood of a property being satisfied. In a seamless business setting, it is essential to validate and verify process models. The objective of this paper is to apply the SMC technique in process mining for the verification and validation of process models with stochastic behaviour and large state space, where probabilistic model checking is not feasible. We propose a novel methodology in this research direction that integrates SMC and PM by formally modelling discovered and replayed process models and apply statistical methods to estimate the results. The methodology facilitates an automated and proficient evaluation of the extent to which a process model aligns with user requirements and assists in selecting the optimal model. We demonstrate the effectiveness of our methodology with a case study of a loan application process performed in a financial institution that deals with loan applications submitted by customers. The case study highlights our methodology’s capability to identify the performance constraints of various process models and aid enhancement efforts.

This article is devoted to verification of the bully election algorithm for distributed systems with TLA+ and PlusCal. In this work, we show an overview of the basic information about distributed systems, then we show definition of election algorithms for distributed systems, after that we provide a full description of the bully election algorithm for distributed systems. Later in this article, we show the model of the distributed algorithm created with TLA+ and PlusCal. Then we describe the main parts of this model. Next, we illustrate results of verification of this model. The verification was done using TLC ‒ a model checker and simulator for executable TLA+ specifications. As a result of the verification, it was possible to establish that the declared properties of safety and liveness are fully satisfied for all possible states of the system.

Finite-state models are widely used in software engineering, especially in the development of control systems. In control applications, such models are often developed manually, which can make it difficult to keep them up to date. To simplify the maintenance process, an automatic approach can be used to infer models from behavior examples and temporal specification. As an example of a specific control systems development application, we focus on inferring finite-state models of function blocks (FBs) defined by the IEC 61499 international standard for distributed automation systems. In this paper, we propose a method for inferring FB models from behavior examples based on reduction to the Boolean satisfiability problem (SAT). Additionally, we take into account linear temporal properties using counterexample-guided synthesis. The developed tool, fbSAT, implementing the proposed method is evaluated in three case studies: inferring a finite-state controller for a Pick-and-Place manipulator, reconstructing randomly generated automata, and minimizing transition systems. In contrast to existing approaches, the suggested method is more efficient and produces finite-state models that are minimal in terms of both the number of states and the complexity of guard conditions.

The graphical modeling language GRAFCET is used as a formal specification language in industrial control design. To use these formal specifications for model-driven development of control code it is beneficial to ensure their syntactical and semantic correctness. Therefore in this paper, a detailed meta-model for GRAFCET is presented, which takes so-called terms into account, i.e. logical and arithmetic expressions in conditions and assignments. The meta-model and additionally proposed invariants allow the creation of syntactically correct GRAFCET instances. Based on this, a translation of GRAFCET to Guarded Action Language (GAL) is presented. The resulting transition system in GAL forms the basis for a semantic analysis of the GRAFCET instances by means of model checking in future research. Finally, the models are then employed for automatic code generation in Structured Text.

This study presents a framework that procedurally generates maze-like levels and leverages an automated verification technique called model checking to verify and produce a winning action sequence for that level. By leveraging the counterexample generation feature of the SPIN model checker, one or more solutions to the level-in-test are found, and the solutions are animated using a video game description language, PyVGDL. The framework contains four behavioral templates developed to model the logic of maze-like puzzle games in the modeling language of SPIN. These models automatically are tailored according to the level-in-test. To show the proposed methodology’s effectiveness, we conducted five different experiments. These experiments include performance comparisons in level-solving between the proposed and existing methodologies —A* Search and Monte Carlo Tree Search—and demonstrations of the use of the proposed approach to check a game level with respect to requirements. This study also proposes a pipeline to generate maze-like puzzle levels with two levels of cellular automata.

When verifying the validity of a formula in a system model by a model checker, a common feature is the generation of a linear witness or counterexample, which is a computation path usually showing a single reason why the formula is valid or, respectively, not. For systems represented with Labeled Transition Systems (LTS) and a subset of ACTLW (Action-based Computation Tree Logic with Unless operator) formulae, a procedure exists for the generation of witness automata, which contain all the interesting finite linear witnesses, thus revealing all the reasons of the validity of a formula. Although this procedure uses a symbolic representation of LTSs, transitions of a given LTS are traversed one by one. In this paper, we propose a procedure which exploits the symbolic representation efficiently to traverse several transitions at once. We evaluate the procedure on models of a communication protocol from industry and a biological system. The results show it to be at least several times faster than the former one. Witness automata were first introduced to allow for compositional generation of test sequences. We propose two more possible uses. One is for the detection of multiple errors in a model by exploring the witness automaton for a formula, instead of only one, which is usually the case with a single witness. The other one is for the detection of previously unknown system properties. As witness automata can be rather large, we show how some existing tools could help in examining them through visualization and simulation.

Verification techniques play an essential role in detecting undesirable behaviors in many applications like spectrum auctions. By verifying an auction design, one can detect the least favorable outcomes, e.g., the lowest revenue of an auctioneer. However, verification may be infeasible in practice, given the vast size of the state space on the one hand and the large number of properties to be verified on the other hand. To overcome this challenge, we leverage machine-learning techniques. In particular, we create a dataset by verifying properties of a spectrum auction first. Second, we use this dataset to analyze and predict outcomes of the auction and characteristics of the verification procedure. To evaluate the usefulness of machine learning in the given scenario, we consider prediction quality and feature importance. In our experiments, we observe that prediction models can capture relationships in our dataset well, though one needs to be careful to obtain a representative and sufficiently large training dataset. While the focus of this article is on a specific verification scenario, our analysis approach is general and can be adapted to other domains.

Smart contracts are the key software components to realize blockchain applications, from single encrypted digital currency to various fields. Due to the immutable nature of blockchain, any bugs or errors will become permanent once published and could lead to huge economic losses. Recently, a great number of security problems have been exposed in smart contracts. It is important to verify the correctness of smart contracts before they are deployed on the blockchain. This paper aims to verify the correctness of smart contracts in Ethereum transactions, and the model checker Spin is adopted for the formal verification of smart contracts in order to ensure their execution with respect to parties' willingness, as well as their reliable interaction with clients. In this direction, we propose a formal method to construct the models for smart contracts. Then, the method is applied to a study case in the Ethereum commodity market. Finally, a case model is implemented in Spin, which can simulate the process's execution and verify the properties that are abstracted from the requirements. Compared with existing techniques, formal analysis can verify whether smart contracts comply with the specifications for given behaviors and strengthen the credibility of smart contracts in the transaction. [ABSTRACT FROM AUTHOR]