Complex Event Processing for Design-Space Exploration (MSc thesis)

Context

Whether a cyber-physical system behaves correctly often depends on its operating context: the environment, how components are deployed, and how they communicate. Model-driven engineering captures this with time-evolving graph models, and high-level requirements can be written as runtime monitors that watch the graph change over time. In autonomous driving, for example, a runtime model holds the vehicle and the other actors in the scene, and monitors detect traffic-rule violations.

Testing such systems needs test sequences, trajectories of graphs, that exercise both the system and its monitors. There are too many behaviours to write these by hand, exhaustive enumeration takes far too long, and random exploration rarely finds the interesting cases.

Approach

The thesis uses design-space exploration (DSE) heuristics to derive test sequences automatically, and reuses the runtime monitors themselves to steer the search:

1. Formalism. I extended parametric timed automata (PTA) with graph pattern matching. This gives a common background formalism for runtime monitors, covering complex event processing (CEP) and temporal-logic monitors that can express metric temporal graph logic (MTGL) specifications.
2. Guidance. A dedicated objective function based on the monitoring automata guides the exploration towards relevant sequences until the behaviours are sufficiently covered.
3. Implementation. The monitors are integrated into the open-source Refinery graph-processing framework, both for runtime execution and for DSE.
4. Evaluation. The applicability and scalability were evaluated on several case studies, including scenario generation for autonomous vehicles.

Result

Engineers can write one high-level specification as monitor automata and use it for both testing complex context-dependent systems and monitoring them at runtime.

Looking back

This is where the ideas behind my PhD started: graph models of traffic scenes, monitors as oracles, and search guided by coverage. The PhD moved them from roads to the sea and from heuristic coverage to functional completeness.