Interpretable Early Failure Detection via Machine Learning and Trace Checking-based Monitoring
This addresses the problem of scalable and interpretable failure detection for system monitoring, though it is incremental as it builds on existing trace checking and genetic programming techniques.
The paper tackles the computational inefficiency of runtime monitoring by reducing monitoring of specific Signal Temporal Logic fragments to polynomial-time trace checking, and develops a GPU-accelerated framework for interpretable early failure detection that shows a 2-10% net improvement in key performance metrics over state-of-the-art methods.
Monitoring is a runtime verification technique that allows one to check whether an ongoing computation of a system (partial trace) satisfies a given formula. It does not need a complete model of the system, but it typically requires the construction of a deterministic automaton doubly exponential in the size of the formula (in the worst case), which limits its practicality. In this paper, we show that, when considering finite, discrete traces, monitoring of pure past (co)safety fragments of Signal Temporal Logic (STL) can be reduced to trace checking, that is, evaluation of a formula over a trace, that can be performed in time polynomial in the size of the formula and the length of the trace. By exploiting such a result, we develop a GPU-accelerated framework for interpretable early failure detection based on vectorized trace checking, that employs genetic programming to learn temporal properties from historical trace data. The framework shows a 2-10% net improvement in key performance metrics compared to the state-of-the-art methods.