Probabilistic Conditional System Invariant Generation with Bayesian Inference

Meriel von Stein, Sebastian G. Elbaum, Lu Feng, Shili ShengarXiv 2020 · arXiv

Abstract

Autonomous systems operate in uncertain environments where traditional global invariants often fail to capture complex, state-dependent behaviors. This paper presents a Bayesian framework for mining conditional probabilistic invariants from execution traces. By incorporating prior knowledge and updating beliefs through Bayesian inference, the approach identifies significant system properties that manifest under specific conditions, even in the presence of noise and stochasticity.

Introduction

In software engineering, invariants are properties that remain true throughout a program's execution. While tools like Daikon are effective for traditional software, autonomous robotics present unique challenges. First, robotic behavior is often highly dependent on the current state (e.g., a drone's velocity profile differs significantly between "sweeping" and "landing" phases). Second, sensors and actuators are inherently noisy, meaning properties are rarely 100% true. To address these issues, we propose a method to mine conditional probabilistic invariants of the form $P(Outcome | Given) > \text{threshold}$.

Methodology

The proposed framework processes system traces to infer conditional probabilities using Bayesian Inference. Unlike frequentist methods, this approach allows for the integration of prior beliefs and incremental updates as new data becomes available.

Figure 2: Overview of the Bayesian framework for invariant generation.

Framework Components

The architecture consists of several key stages:

  • Predicate Specification: Developers define a grammar-based configuration of variables (e.g., missionPhase, sensorStatus) to explore.
  • Inference Engine: This core component calculates $P(Outcome | Given)$ using Bayes' Theorem. It supports predicates such as Equality, Range, and Trend.
  • Ranking via "Surprise": To identify the most informative invariants, the tool ranks them by a Surprise Ratio—the ratio of the posterior probability to the prior probability. High surprise indicates a significant shift in understanding based on the observed data.
  • Model Selection: The Bayesian Information Criterion (BIC) is employed to penalize complexity, favoring simpler, more interpretable invariants.
Figure 4: Example of an execution trace processed into conditional outcomes.

As illustrated in Figure 4, the system evaluates specific conditions (the "Given") against desired results (the "Outcome") across time steps to build the probabilistic model.

Evaluation and Results

The framework was evaluated using two distinct datasets: a Drone ISR Scenario involving 34 real-world missions of a DJI Tello drone, and an Autonomous Driving Simulator study with 19 participants focusing on human trust.

Key Findings

  • Discovery of Contextual Invariants: The tool successfully identified thousands of invariants that global frequentist tools missed. For instance, it captured specific throttle behaviors that only occurred when a pedestrian was detected during autonomous mode.
  • Comparison with Daikon: While Daikon effectively identified global variable ranges, it failed to capture the stateful "Given" conditions that explain why variables change.
  • Efficiency and Convergence: The Bayesian approach demonstrated linear scaling with trace length and showed that confidence in inferred invariants converges as more data is processed.

Discussion

The use of "Surprise" as a metric provides a powerful filter for developers, highlighting critical deviations from expected behavior that are essential for safety analysis. Furthermore, the incremental nature of Bayesian learning makes the tool computationally efficient for evolving systems, as it does not require re-processing historical data from scratch. However, the approach faces challenges with search space explosion. Future work will focus on automating variable selection and supporting more complex temporal or geometric predicates.

Summary updated

Abstract

Invariants are a set of properties over program attributes that are expected to be true during the execution of a program. Since developing those invariants manually can be costly and challenging, there are a myriad of approaches that support automated mining of likely invariants from sources such as program traces. Existing approaches, however, are not equipped to capture the rich states that condition the behavior of autonomous mobile robots, or to manage the uncertainty associated with many variables in these systems. This means that valuable invariants that appear only under specific states remain uncovered. In this work we introduce an approach to infer conditional probabilistic invariants to assist in the characterization of the behavior of such rich stateful, stochastic systems. These probabilistic invariants can encode a family of conditional patterns, are generated using Bayesian inference to leverage observed trace data against priors gleaned from previous experience and expert knowledge, and are ranked based on their surprise value and information content. Our studies on two semi-autonomous mobile robotic systems show how the proposed approach is able to generate valuable and previously hidden stateful invariants.
BibTeX
@misc{stein2020probabilistic,
  author = {Meriel von Stein and Sebastian G. Elbaum and Lu Feng and Shili Sheng},
  title = {{Probabilistic Conditional System Invariant Generation with Bayesian Inference}},
  year = {2020},
  eprint = {2012.06615},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2012.06615},
}
Figure