State Estimation of Non-monotonic, Partially Non-deterministic Software with Sparse Probing using an Unscented Kalman Filter combined with Logic Reasoning

Abstract

This report describes a technique for assessing the state of a general-purpose system using partial probing. The technique utilizes an Unscented Kalman Filter (UKF) combined with in-process and post-process reasoning. While Kalman Filters (KF) Extended Kalman Filres (EKF), and UKF are typically applied to state-space systems, where an underlying theory provides the a-priori knowledge, this report suggests the application of UKF to monitor general-purpose software systems that do not have an underlying first-principles theory. The suggested technique uses a reasoning component compute the a-priori evaluation. An important aspect differentiating state-space systems from general-purpose software is that the latter is often concurrent, with a plurality or concurrently executing threads, processes, or devices. As a result, relative execution time of these components (and the derivative state space) is for all intents and purposes non-deterministic. In addition, the suggested technique enables monitoring with probing that is sparse in time and space namely, probing that occurs only one in n cycles or probing that only probes a subset of the software-systems state-space