Parameter Searching and Partition with Probabilistic Coverage Guarantees

Abstract

The use of machine learning components has posed significant challenges for the verification of cyber-physical systems due to its complexity, nonlinearity, and large space of parameters. In this work, we propose a novel probabilistic verification framework for learning-enabled CPS which can search over the entire (infinite) space of parameters, to figure out the ones that lead to satisfaction or violation of specification that are captured by Signal Temporal Logic (STL) formulas. Our technique is based on conformal regression, a technique for constructing prediction intervals with marginal coverage guarantees using finite samples, without making assumptions on the distribution and regression model. Our verification framework, using conformal regression, can predict the quantitative satisfaction values of the system's trajectories over different sets of the parameters and use those values to quantify how well/bad the system with the parameters can satisfy/violate the given STL property. We use three case studies of learning-enabled CPS applications to demonstrate that our technique can be successfully applied to partition the parameter space and provide the needed level of assurance.