@inproceedings {76,
	title = {Time-triggered Program Self-monitoring},
	booktitle = {Proc. of 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)},
	year = {2012},
	pages = {260-269},
	address = {Seoul, Korea},
	abstract = {<p>Runtime monitoring aims at analyzing the well-being of a system at run time in order to detect errors and steer the system towards a healthy behavior. Such monitoring is a complementary technique to other approaches for ensuring correctness, such as formal verification and testing. In time-triggered runtime monitoring, a monitor runs as a separate process in parallel with an application program under scrutiny and samples the program\&rsquo;s state periodically to evaluate a set of properties. Applying this technique in a computing system results in obtaining bounded and predictable overhead. Gaining such characteristics for overhead is highly desirable for designing and engineering time-critical applications, such as safety-critical embedded systems. However, a time-triggered monitor requires certain synchronization features at operating system level and may suffer from various concurrency and synchronization dependencies and overheads as well as possible unreliability of synchronization primitives in a real-time setting. In this paper, we propose a new method, where the program under inspection is instrumented, so that it self-samples its state in a periodic fashion without requiring assistance from an external monitor or internal timer. We call this technique time-triggered self-monitoring. First, we formulate an optimization problem for minimizing the number of points in a program, where self-sampling instrumentation instructions must be inserted. We show that this problem is NP-complete. Consequently, we propose a SAT-based solution and a heuristic to cope with the exponential complexity. Our experimental results show that a time-triggered self-monitored program performs significantly better than the same program monitored by an external time-triggered monitor.</p>
},
	keywords = {Runtime verification, TTRV},
	doi = {10.1109/RTCSA.2012.16},
	author = {Borzoo Bonakdarpour and Johnson Thomas and Sebastian Fischmeister}
}
@inproceedings {66,
	title = {Efficient Techniques for Near-optimal Instrumentation in Time-triggered Runtime Verification},
	booktitle = {Proc. of the 2nd International Conference on Runtime Verification (RV)},
	year = {2011},
	month = {September},
	pages = {208-222},
	address = {San Francisco, USA},
	abstract = {<p>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.</p>
},
	keywords = {Runtime verification, TTRV},
	doi = {10.1007/978-3-642-29860-8_16},
	url = {http://www.springerlink.com/content/q8812w5u506844u6/},
	author = {Samaneh Navabpour and Chun Wah Wallace Wu and Borzoo Bonakdarpour and Fischmeister, Sebastian}
}
