Input-Output Robustness of Software Systems

pdf

Abstract

A robust system is one that only modestly deviates from the nominal correct behavior upon the occurrence of small disturbances. Although it is accepted that engineered systems should be robust, it is less clear how to define robustness for Cyber-Physical Systems.

In this poster, we sketch a theory of robustness for software systems. Our starting point is the research on robustness in continuous control theory, where one designs a controller for a “nominal” behavior assuming no disturbances and provides two guarantees: bounded disturbances have bounded consequences, and “nom- inal” behavior is eventually resumed after disturbances disappear. We adapt this view of robustness to the discrete setting by taking an input-output perspective of discrete systems. We define systems as transducers f : Σ∗ Λ∗ mapping streams over an alphabet of inputs Σ = Σc × Σd to streams over an alphabet of outputs Λ. The alphabet Σc represents system inputs (also called control inputs) and the alphabet Σd represents dis- turbances. Typically, the designer designs the system assuming a nominal model of the environment, modeled by the stream ⊥∗ for a special symbol ⊥∈ Σd. Disturbances represent deviations from the nominal model due to mismatches between the assumptions made about the environment at design time and the environment at run time. What goal should a robust design have? In keeping with robust continuous control, we postulate the following two natural requirements. First, every small disturbance should lead to a small deviation from the nominal behavior. Second, we require the effect of a sporadic disturbance to disappear over time. That is, if the environment deviates from the nominal for one step and subsequently follows the nominal environment, we require the effect of the deviation to disappear in finitely many steps. In this poster, we sketch a theory of robustness that captures both requirements. In particular, we show that, when the transducer f and costs I and O are modeled using finite-state automata, we can verify robustness in polynomial time. In case a system is not robust, we give a procedure to synthesize a controller enforcing robustness, again in polynomial time.

The proposed notion of robustness for software systems, when combined with existing results on robustness of continuous systems, will enable the analysis and design of robust Cyber-Physical Systems.

Award ID: 1035916

  • CPS Domains
  • Control
  • Modeling
  • Systems Engineering
  • Resilient Systems
  • Validation and Verification
  • CPS Technologies
  • Foundations
  • National CPS PI Meeting 2012
  • 2012
  • Poster
  • Academia
  • CPS PI MTG 12 Posters & Abstracts
Submitted by Paulo Tabuada on Sat, 10/06/2012 - 23:29