Monitorability Over Unreliable Channels

In Runtime Verification (RV), monitoring a program means checking an execution trace of the program for satisfactions and violations of properties.  The question of which properties can be effectively monitored over ideal channels has mostly been answered by prior work.  However, program monitoring is often deployed for remote systems where communications may be unreliable.

In this work, we address the question of what properties are monitorable over an unreliable communication channel.  We describe the different types of mutations that may be introduced to an execution trace and examine their effects on program monitoring.  We propose a fixed-parameter tractable algorithm for determining the immunity of a finite automaton to a trace mutation and show how it can be used to classify omega-regular properties as monitorable over channels with that mutation.