Efficient Model to Query and Visualize the System States Extracted from Trace Data - Runtime Verification - page 233

proposed solution, we model the state values as intervals and store them in
an interval tree, called the history tree, which has special support for typical
interval queries. To fill the tree, every time a state change is reported, a state
interval is created and sent to state history database. However, by maintaining
a distinction between the creation of intervals and storage it is possible to easily
change the storage method, and even use different methods or chain several of
them. Comparisons with R-Trees and other experiments are undertaken, and the
results are provided.
This solution is designed to work with any trace format. We have tested our
solution with LTTng trace format in Linux and is accessible through Eclipse
TMF framework. However, adding the capability to work with other trace for-
mats (e. g. Dtrace, Event Tracing for Windows (ETW), etc) will be done as
a future work. Reading the event-state mapping from XML files and doing it
dynamically is another possible future work.
Acknowledgement. The support of the Natural Sciences and Engineering Re-
search Council of Canada (NSERC), Ericsson Software Research, and Defence
Research and Development Canada (DRDC) is gratefully acknowledged.
References
[CGK + 04] Cohen, I., Goldszmidt, M., Kelly, T., Symons, J., Chase, J.S.: Correlating
instrumentation data to system states: A building block for automated
diagnosis and control. In: Proceedings of the 6th Conference on Sympo-
sium on Operating Systems Design Implementation, vol. 6, p. 16. USENIX
Association, Berkeley (2004)
[CGL08] Chan, A., Gropp, W., Lusk, E.: An ecient format for nearly constant-
time access to arbitrary time intervals in large trace files. Scientific Pro-
gramming 16(2), 155-165 (2008)
[CZG + 05] Cohen, I., Zhang, S., Goldszmidt, M., Symons, J., Kelly, T., Fox, A.:
Capturing, indexing, clustering, and retrieving system history. SIGOPS
Operating Systems Review 39(5), 105-118 (2005)
[DD06] Desnoyers, M., Dagenais, M.R.: The LTTng tracer: A low impact per-
formance and behavior monitor for GNU/Linux. In: Proceedings of the
Ottawa Linux Symposium (2006)
[DD08] Desnoyers, M., Dagenais, M.: LTTng: Tracing across execution layers,
from the hypervisor to user-space. In: Proceedings of the Ottawa Linux
Symposium (2008)
[EJD12] Ezzati-Jivan, N., Dagenais, M.R.: A stateful approach to generate syn-
thetic events from kernel traces. In: Advances in Software Engineering
(April 2012)
[EJD13] Ezzati-Jivan, N., Dagenais, M.R.: A framework to compute statistics
of system parameters from very large trace files. SIGOPS Oper. Syst.
Rev. 47(1), 43-54 (2013)
[GDG + 11] Giraldeau,F.,Desfossez,J.,Goulet,D.,Dagenais,M.,Desnoyers,M.:Re-
covering system metrics from kernel trace. In: Linux Symposium, p. 109
(June 2011)