Towards WCET Estimation of Graph Queries@Run.time

Recent approaches in runtime monitoring and live data analytics have started to use expressive graph queries at runtime to capture and observe properties of interest at a high level of abstraction. However, in a critical context, such applications often require timeliness guarantees, which have not been investigated yet for query-based solutions due to limitations of existing static worst-case execution time (WCET) analysis techniques. One limitation is the lack of support for dynamic memory allocation, which is required by the dynamically evolving runtime models on which the queries are evaluated. Another open challenge is to compute WCET for asynchronously communicating programs such as distributed monitors. This paper introduces our vision about how to assess such timeliness properties and how to provide tight WCET estimates for query execution at runtime over a dynamic model. Furthermore, we present an initial solution that combines state-of-the-art parametric WCET estimations with model statistics and search plans of queries.