DARS 2017

Second Workshop on Design and Analysis of Robust Systems
July 22, 2017, Heidelberg, Germany
Co-located with CAV 2017

The DARS Series
DARS 2017 is the 2nd international workshop in a series dedicated to the Design and Analysis of Robust Systems. Robustness refers to the ability of a system to behave reliably in the presence of perturbation in the system parameters or irregularities in the system's operating environment. This is particularly important in the context of embedded systems and software, which interact with a physical environment through sensors and actuators and communicate over wired or wireless networks. Such systems are routinely subject to deviations arising from sensor or actuation noise, quantization and sampling of data, uncertainty in the physical environment, and delays or packet drops over unreliable network channels. When deployed in safety critical applications, system robustness in the presence of uncertainty is not just desirable, but crucial.

The goal of DARS is to foster dialogue and exchange of ideas and techniques across several disciplines with an interest in robustness such as formal verification, programming languages, fault-tolerance, control theory and hybrid systems.

Domains of interest include, but are not limited to: reactive, timed, hybrid or probabilistic programs/circuits/systems/networks, approximate computing and fault tolerance of distributed systems.

Important Dates
All deadlines are AOE (Anywhere on Earth)

Extended abstract submission May 5, 2017
Paper registration April 28, 2017
Author notification May 25, 2017
Workshop July 22, 2017

Submission URL
Easy Chair

Extended abstract submission
We solicit extended abstracts of no more than 3 pages including references that provide an overview of recently published work of the authors or work in progress. We expect that the extended abstracts will focus on providing intuitions (main results and their implications), rather than technical details (formal definitions). The extended abstracts along with a one paragraph abstract (for announcement on the webpage, if accepted) can be uploaded to Easychair using the above link.

Program Chairs:

Pavithra Prabhakar
Roopsha Samanta

Program Committee:

Swarat Chaudhuri, Rice University
Georgios Fainekos, Arizona State University
Barbara Jobstmann, EPFL and Cadence Design Systems
Petr Novotny, IST Austria
Necmiye Ozay, University of Michigan
Pavithra Prabhakar, Kansas State University
Roopsha Samanta, Purdue University
Paulo Tabuada, UCLA
Thomas Wahl, Northeastern University
Robustness, Mori-Zwanzig Model Reduction, and Statistical Validation of Hybrid Systems.
Geir E. Dullerud, University of Illinois
Analyzing Neural Network Robustness with Constraints
Dimitrios Vytiniotis, Microsoft
Robust Linear Temporal Logic.
Paulo Tabuada and Daniel Neider.
Abstract: Although it is widely accepted that every system should be robust, in the sense that "small" violations of environment assumptions should lead to "small" violations of system guarantees, it is less clear how to make this intuitive notion of robustness mathematically precise. In our work, we address the problem of how to specify robustness in temporal logic. Our solution is a robust version of Linear Temporal Logic, which we term Robust Linear Temporal Logic (rLTL). Formulas in this logic are syntactically identical to LTL formulas but are endowed with a many-valued semantics that encodes robustness. In particular, the semantics of the rLTL formula \phi implies \psi is such that a "small" violation of the environment assumption \phi is guaranteed to only produce a "small" violation of the system guarantee \psi. In addition to the definition of rLTL, we study the corresponding verification and synthesis problems. Similarly to LTL, we show that both problems are decidable, with the verification problem being solvable in exponential time and the synthesis problem being solvable in doubly exponential time.
Stabilizing Numeric Programs against Platform Uncertainties.
Yijia Gu and Thomas Wahl.
Abstract: Floating-point arithmetic (FPA) is a loosely standardized approximation of real arithmetic available on many computers today. The use of approximation incurs commonly underestimated risks for the reliability of numeric software, including reproducibility issues caused by the relatively large degree of freedom for FPA implementers offered by the IEEE 754 standard. If left untreated, such problems can seriously interfere with program portability.
In this paper we discuss numeric programs' lack of robustness against platform variations, including irreproducible control flow and invariants that hold on some platforms but not others. We also demonstrate how, using information on the provenance of platform dependencies, such reproducibility violations can be repaired, which results in stabilized program execution. We illustrate the use of this technique on decision-making and other numeric programs, and present an outlook to its applicability to solving reproducibility issues among CPU and GPU versions of kernel support vector machines.
Based in part on work published at EUROPAR 2015 and VMCAI 2017.
Recent Advances in Designing Robust Probabilistic Systems.
Radu Calinescu, Milan Ceska, Simos Gerasimou, Marta Kwiatkowska and Nicola Paoletti.
Abstract: Robust systems are of great interest because they can withstand changes in the system parameters and do not expose users to large variations in quality attributes. This paper presents our recent results on automating the design of robust probabilistic systems. We integrate search-based design strategies with formal analysis of parametric Markov models, and introduce sensitivity-aware synthesis of Pareto-optimal sets of designs providing useful tradeoffs between quality attributes and sensitivity. The synthesis algorithms are implemented in our publicly available tool RODES and evaluated on several case studies from different domains. The experiments demonstrate that our approach provides unique insights into how the parameters affect the system dynamics and robustness.
Martingales for Probabilistic Termination and Safety.
Krishnendu Chatterjee, Petr Novotný and Djordje Zikelic.
Abstract: We address the problem of automated proofs of reachability and safety properties for linear-arithmetic probabilistic programs with nondeterminism. We define the notion of stochastic invariants, which are constraints along with a probability bound that the constraints hold. We introduce a concept of repulsing supermartingales. First, we show that repulsing supermartingales can be used to obtain bounds on the probability of the stochastic invariants. Second, we show the effectiveness of repulsing supermartingales in the following three ways: (1)~With a combination of ranking and repulsing supermartingales we can compute lower bounds on the probability of termination; (2)~repulsing supermartingales provide witnesses for refutation of almost-sure termination; and (3)~with a combination of ranking and repulsing supermartingales we can establish persistence properties of probabilistic programs.
We also present results on related computational problems and an experimental evaluation of our approach on academic examples.
A CEGAR approach for stability verification of linear hybrid systems
Miriam García Soto.
Abstract: This document summarizes results related to an algorithmic approach for stability analysis of linear hybrid systems. Classical approaches rely on Lyapunov function search and suffer from numerical issues. In addition, an unsuccessful template for the Lyapunov function does not provide insights on the choice of a better template. To overcome these issues, we present a counterexample guided-abstraction refinement (\cegar) approach which iteratively searches for a stability certification over an abstract system, and provides insights to obtain more accurate abstract systems if needed.