New evolutionary search method automates diagnosis of cyber-physical system failures

Engineers working on cyber-physical systems—software that controls physical processes like autonomous vehicles or industrial robots—face a persistent challenge: when a system behaves in ways that violate its safety or performance requirements, they need to quickly identify what went wrong. A new technique proposes using evolutionary algorithms to automate this diagnostic process.

The Problem: Understanding Trace Violations#

Cyber-physical systems work by executing a sequence of operations whose behavior can be recorded as an execution trace. Requirements for these systems are often expressed as temporal logic properties—formal statements about what should (or should not) happen over time. When a recorded trace violates one of these requirements, engineers must manually analyze the execution to find the root cause. This process, known as the trace diagnostic problem, is time-consuming and error-prone, especially as systems grow in complexity.

A New Search-Based Approach#

Researchers have developed search-based trace diagnostic (SBTD), a technique that treats diagnosis as a search problem solvable through evolutionary computation. Rather than exhaustively analyzing traces, SBTD generates candidate diagnoses and iteratively refines them using mutation, recombination, and selection—standard operations from genetic algorithms. A fitness function evaluates which diagnoses best explain the observed violation, and the process continues until high-quality explanations emerge.

Implementation and Results#

The team built Diagnosis, a tool implementing SBTD for signal-based temporal logic requirements expressed in Hybrid Logic of Signals (HLS). Testing on 34 experiments spanning 17 trace-requirement pairs, the tool achieved diagnoses that aligned with expert judgment in 29 of 34 cases and successfully handled the full HLS benchmark dataset—a scope that exceeded prior automated approaches.

The technique's flexibility proved valuable too. By treating trace-checking as a replaceable component, the researchers swapped their HLS checker for an alternative temporal logic monitor (RTAMT) and achieved comparable results with 100–1000 times lower computational cost per check.