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.
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.
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