  Runtime monitoring plays a key role in the assurance of modern intelligent
cyber-physical systems, which are frequently data-intensive and
safety-critical. While graph queries can serve as an expressive yet formally
precise specification language to capture the safety properties of interest,
there are no timeliness guarantees for such auto-generated runtime monitoring
programs, which prevents their use in a real-time setting. While worst-case
execution time (WCET) bounds derived by existing static WCET estimation
techniques are safe, they may not be tight as they are unable to exploit
domain-specific (semantic) information about the input models. This paper
presents a semantic-aware WCET analysis method for data-driven monitoring
programs derived from graph queries. The method incorporates results obtained
from low-level timing analysis into the objective function of a modern graph
solver. This allows the systematic generation of input graph models up to a
specified size (referred to as witness models) for which the monitor is
expected to take the most time to complete. Hence the estimated execution time
of the monitors on these graphs can be considered as safe and tight WCET.
Additionally, we perform a set of experiments with query-based programs running
on a real-time platform over a set of generated models to investigate the
relationship between execution times and their estimates, and compare WCET
estimates produced by our approach with results from two well-known timing
analyzers, aiT and OTAWA.
