S-TaLiRo: A Tool for Temporal Logic Falsification for Hybrid Systems

An automated system repair framework with signal temporal logic

We present an automated system repair framework for cyber-physical systems. The proposed framework consists of three main steps: (1) system simulation and fault detection to generate a labeled dataset, (2) identification of the repairable temporal properties leading to the faulty behavior and (3) repairing the system to avoid the occurrence of the cause identified in the second step. We express the cause as a past time signal temporal logic (ptSTL) formula and present an efficient monotonicity-based method to synthesize a ptSTL formula from a labeled dataset. Then, in the third step, we modify the faulty system by removing all behaviors that satisfy the ptSTL formula representing the cause of the fault. We apply the framework to two rich modeling formalisms: discrete-time dynamical systems and timed automata. For both of them, we define repairable formulae, the corresponding repair procedures, and illustrate them over case studies.

Paracosm: A Test Framework for Autonomous Driving Simulations

Systematic testing of autonomous vehicles operating in complex real-world scenarios is a difficult and expensive problem. We present Paracosm, a framework for writing systematic test scenarios for autonomous driving simulations. Paracosm allows users to programmatically describe complex driving situations with specific features, e.g., road layouts and environmental conditions, as well as reactive temporal behaviors of other cars and pedestrians. A systematic exploration of the state space, both for visual features and for reactive interactions with the environment is made possible. We define a notion of test coverage for parameter configurations based on combinatorial testing and low dispersion sequences. Using fuzzing on parameter configurations, our automatic test generator can maximize coverage of various behaviors and find problematic cases. Through empirical evaluations, we demonstrate the capabilities of Paracosm in programmatically modeling parameterized test environments, and in finding problematic scenarios.

Extending Signal Temporal Logic with Quantitative Semantics by Intervals for Robust Monitoring of Cyber-physical Systems

Monitoring is the core procedure of runtime verification of cyber-physical systems (CPS) and provides an evaluation of a signal with respect to a given specification. For formally specifying requirements with time constraints for CPS, Signal Temporal Logic (STL) is a well-known specification language with powerful semantics. However, with existing semantics of STL it is not feasible to monitor signals with spatial deviation and time delay. Therefore, we introduce STL with Quantitative Interval Semantics to solve this problem. Based on this newly developed semantics, we derived an algorithm called RoMoTeS (Robust Monitoring for Temporal Specifications) to monitor a signal with finite length with respect to an STL formula. It provides a real-valued interval for every point in time, which contains all possible signed distances between the deviation polytope determined by the measured data point (exposed to deviation and delay) and the permissive space specified by an STL specification. Furthermore, it is proven that no satisfaction is reported when the signal is potentially falsifying such a specification. Finally, an automatic transmission controller model was used as a case study to show the applicability and usefulness of the proposed algorithm.

Monte Carlo Based Statistical Model Checking of Cyber-Physical Systems: A Review

The ever-increasing deployment of autonomous Cyber-Physical Systems (CPSs) (e.g., autonomous cars, UAV) exacerbates the need for efficient formal verification methods. In this setting, the main obstacle to overcome is the huge number of scenarios to be evaluated. Statistical Model Checking (SMC) is a simulation-based approach that holds the promise to overcome such an obstacle by using statistical methods in order to sample the set of scenarios. Many SMC tools exist, and they have been reviewed in several works. In this paper, we will overview Monte Carlo-based SMC tools in order to provide selection criteria based on Key Performance Indicators (KPIs) for the verification activity (e.g., minimize verification time or cost) as well as on the environment features, the kind of system model, the language used to define the requirements to be verified, the statistical inference approach used, and the algorithm implementing it. Furthermore, we will identify open research challenges in the field of (SMC) tools.

Conformance-Based Doping Detection for Cyber-Physical Systems

We present a novel and generalised notion of doping cleanness for cyber-physical systems that allows for perturbing the inputs and observing the perturbed outputs both in the time– and value–domains. We instantiate our definition using existing notions of conformance for cyber-physical systems. We show that our generalised definitions are essential in a data-driven method for doping detection and apply our definitions to a case study concerning diesel emission tests.

Quantitative monitoring of STL with edit distance

In cyber-physical systems (CPS), physical behaviors are typically controlled by digital hardware. As a consequence, continuous behaviors are discretized by sampling and quantization prior to their processing. Quantifying the similarity between CPS behaviors and their specification is an important ingredient in evaluating correctness and quality of such systems. We propose a novel procedure for measuring robustness between digitized CPS signals and signal temporal logic (STL) specifications. We first equip STL with quantitative semantics based on the weighted edit distance, a metric that quantifies both space and time mismatches between digitized CPS behaviors. We then develop a dynamic programming algorithm for computing the robustness degree between digitized signals and STL specifications. In order to promote hardware-based monitors we implemented our approach in FPGA. We evaluated it on automotive benchmarks defined by research community, and also on realistic data obtained from magnetic sensor used in modern cars.

Computational Modeling, Formal Analysis, and Tools for Systems Biology

As the amount of biological data in the public domain grows, so does the range of modeling and analysis techniques employed in systems biology. In recent years, a number of theoretical computer science developments have enabled modeling methodology to keep pace. The growing interest in systems biology in executable models and their analysis has necessitated the borrowing of terms and methods from computer science, such as formal analysis, model checking, static analysis, and runtime verification. Here, we discuss the most important and exciting computational methods and tools currently available to systems biologists. We believe that a deeper understanding of the concepts and theory highlighted in this review will produce better software practice, improved investigation of complex biological processes, and even new ideas and better feedback into computer science.