2012 | OriginalPaper | Chapter
Efficient Techniques for Near-Optimal Instrumentation in Time-Triggered Runtime Verification
Authors : Samaneh Navabpour, Chun Wah Wallace Wu, Borzoo Bonakdarpour, Sebastian Fischmeister
Published in: Runtime Verification
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Time-triggered
runtime verification aims at tackling two defects associated with runtime overhead normally incurred in event-triggered approaches:
unboundedness
and
unpredictability
. In the time-triggered approach, a monitor runs in parallel with the program and periodically samples the program state to evaluate a set of properties. In our previous work, we showed that to increase the sampling period of the monitor (and hence decrease involvement of the monitor), one can employ auxiliary memory to build a history of state changes between subsequent samples. We also showed that the problem of optimization of the size of history and sampling period is NP-complete.
In this paper, we propose a set of heuristics that find near-optimal solutions to the problem. Our experiments show that by employing negligible extra memory at run time, we can solve the optimization problem significantly faster, while maintaining a similar level of overhead as the optimal solution. We conclude from our experiments that the NP-completeness of the optimization problem is not an obstacle when applying time-triggered runtime verification in practice.