Efficient Techniques for Near-optimal Instrumentation in Time-triggered Runtime Verification

TitleEfficient Techniques for Near-optimal Instrumentation in Time-triggered Runtime Verification
Publication TypeConference Paper
Year of Publication2011
AuthorsNavabpour, S., C. Wah Wallac Wu, B. Bonakdarpour, and S. Fischmeister
Conference NameProc. of the 2nd International Conference on Runtime Verification (RV)
Date PublishedSeptember
Conference LocationSan Francisco, USA
KeywordsRuntime verification, TTRV

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.

Refereed DesignationRefereed
Related files: 


Looking for motivated students (undergrads and grads) interested in working on embedded software and systems research. Mail Sebastian Fischmeister for further information.