Feedback Control for Statistical Model Checking of Cyber-Physical Systems

Kenan Kalajdzic, Cyrille Jégourel, Anna Lukina, Ezio Bartocci, Axel Legay, Scott A. Smolka, Radu Grosu

TL;DR

This paper introduces "Feedback-Control Statistical Model Checking" (FC-SSC), a novel framework that treats model checking as a control problem. FC-SSC learns system models from data, estimates system states, and uses importance splitting to efficiently estimate the probability of rare events in complex cyber-physical systems (CPS), even when system models are unknown or too complex for traditional methods.

What Problem Does This Paper Address?

Cyber-physical systems (CPS) are increasingly complex, involving interactions between physical and computational components. Predicting their behavior, especially for rare but critical events (e.g., system failure), is extremely challenging due to state explosion in traditional model checking. While Statistical Model Checking (SMC) offers an alternative by using simulations, it struggles with estimating probabilities of rare events, requiring an impractically large number of samples. Existing SMC techniques also often assume a known system model and observable states, which is not always the case for real-world CPS. This paper tackles these limitations by proposing a feedback-controlled approach that learns system models and states on the fly.

Methods

FC-SSC integrates several key techniques:

  • Stochastic System Identification: It uses machine learning techniques, specifically the Expectation-Maximization (EM) algorithm, to learn a Hidden Markov Model (HMM) of the CPS from observed data. This addresses the challenge of unknown system models.
  • Importance Sampling (ISam) for State Estimation: ISam is employed to infer the current hidden state of the CPS, given the observed data and the learned HMM. This is crucial because CPS states are often not directly observable.
  • Importance Splitting (ISpl) for Rare Event Estimation and Control: ISpl is used to efficiently estimate the probability of rare events. It works by decomposing the rare event property into a series of "levels" and guiding the system's execution towards satisfying these levels. This effectively steers the system towards rare but important behaviors.
  • Feedback Control Loop: The learned HMM, ISam for state estimation, and ISpl for control form a feedback loop. ISam estimates the current state and level, while ISpl uses this information to control the CPS execution, aiming to efficiently estimate the rare event probability.

Datasets

The paper uses two running examples for evaluation:

  • Dining Philosophers: A classic multi-threaded problem adapted to illustrate rare events (a philosopher eating within a given time). The traces were collected from a C implementation.
  • Incrementer-or-Resetter: A nested sequential program where the rare event is reaching a specific counter value. Traces were generated by instrumenting the program to emit counter values.

These examples are chosen for their simplicity in illustration while capturing essential features of complex CPS.

Key Insights and Ideas

  • Model Checking as a Control Problem: The core idea of framing model checking as a control problem is novel. Instead of passively observing, FC-SSC actively steers the system to explore rare but important behaviors.
  • Synergistic Combination of ISam and ISpl: While ISam and ISpl are individually known for rare event estimation, their combined use within a feedback control loop is a key contribution. ISam provides state estimation, which ISpl then leverages for efficient control and probability estimation.
  • Learning Models from Data: The ability to learn an HMM model from observed traces is critical for analyzing systems where analytical models are unavailable or too complex. This makes the approach applicable to a wider range of real-world systems.
  • Efficient Rare Event Probability Estimation: FC-SSC significantly outperforms traditional SMC for rare events by intelligently guiding simulations, avoiding the need for an exhaustive number of samples.

Key Results

  • Dining Philosophers: For a property related to a philosopher eating within a short time frame (T=1s), FC-SSC showed that even with a significant number of samples, it was difficult to cross the first level boundary, suggesting the event is indeed rare and the approach correctly identifies this difficulty. For longer time frames (T=3s), it successfully estimated the probability.
  • Incrementer-or-Resetter: FC-SSC estimated the probability of reaching a specific counter value (12) with a mean of $1.204 \times 10^{-4}$ and a variance of $5.599 \times 10^{-8}$. This is a good estimate and provides a lower bound, which is valuable for systems that likely satisfy a qualitative property.
  • The paper demonstrates that FC-SSC can provide a good approximation of actual probabilities and effectively addresses the challenge of steering programs towards rare but successful paths.

Limitations and Future Work

  • Representative Process Limitation: The current approach relies on learning an HMM for a "representative process" or thread. This might limit the analysis to local behaviors.
  • Future Work: The authors suggest extending the approach by considering a representative process and its "neighborhood of influence" (e.g., direct neighbors in the Dining Philosophers example). This would allow for a broader analysis while still avoiding state explosion. They also mention the potential for incorporating timing information for time-bounded properties.

Summary updated

BibTeX
@inproceedings{kalajdzic2016feedback,
  author = {Kenan Kalajdzic and Cyrille Jégourel and Anna Lukina and Ezio Bartocci and Axel Legay and Scott A. Smolka and Radu Grosu},
  title = {{Feedback Control for Statistical Model Checking of Cyber-Physical Systems}},
  booktitle = {ISoLA},
  year = {2016},
  url = {https://openreview.net/forum?id=0hMf0UIxbC},
}

Loading related content...

Figure