Statistical verification of autonomous system controllers under timing uncertainties

Software in autonomous systems like autonomous cars, robots or drones is often implemented on resource-constrained embedded systems with heterogeneous architectures. At the heart of such software are multiple feedback control loops, whose dynamics not only depend on the control strategy being used, but also on the timing behavior the control software experiences. But performing timing analysis for safety critical control software tasks, particularly on heterogeneous computing platforms, is challenging. Consequently, a number of recent papers have addressed the problem of stability analysis of feedback control loops in the presence of timing uncertainties (cf., deadline misses). In this paper, we address a different class of safety properties, viz., whether the system trajectory with timing uncertainties deviates too much from the nominal trajectory. Verifying such quantitative safety properties involves performing a reachability analysis that is computationally intractable, or is too conservative. To alleviate these problems we propose to provide statistical guarantees over the behavior of control systems with timing uncertainties. More specifically, we present a Bayesian hypothesis testing method that estimates deviations from a nominal or ideal behavior. We show that our analysis can provide, with high confidence, tighter estimates of the deviation from nominal behavior than using known reachability analysis methods. We also illustrate the scalability of our techniques by obtaining bounds in cases where reachability analysis fails, thereby establishing the practicality of our proposed method.