Abstract
When monitoring a system wrt a property defined in some temporal logic, e.g., LTL, a major concern is to settle with an adequate interpretation of observable system events; that is, models of temporal logic formulae are usually infinite streams of events, whereas at runtime only prefixes are available.
This work defines a four-valued semantics for LTL over finite traces, which extends the classical semantics, and allows to infer whether a system behaves (1) according to the monitored property, (2) violates the property, (3) will possibly violate the property in the future, or (4) will possibly conform to the property in the future, once the system has stabilised. Notably, (1) and (2) correspond to the classical semantics of LTL, whereas (3) and (4) are chosen whenever an observed system behaviour has not yet lead to a violation or acceptance of the monitored property.
Moreover, we present a monitor construction for RV-LTL properties in terms of a Moore machine signalising the semantics of the so far obtained execution trace.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arafat, O., Bauer, A., Leucker, M., Schallhart, C.: Runtime verification revisited. Technical Report TUM-I0518, Technische Universität München (2005)
Bauer, A., Leucker, M., Schallhart, C.: Monitoring of real-time properties. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol. 4337, Springer, Heidelberg (2006)
d’Amorim, M., Rosu, G.: Efficient monitoring of omega-languages. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol. 3576, pp. 364–378. Springer, Heidelberg (2005)
Drusinsky, D.: The temporal rover and the atg rover. In: Havelund, K., Penix, J., Visser, W. (eds.) SPIN. LNCS, vol. 1885, pp. 323–330. Springer, Heidelberg (2000)
Eisner, C., Fisman, D., Havlicek, J., Lustig, Y., McIsaac, A., Campenhout, D.: Reasoning with temporal logic on truncated paths. In: Hunt Jr., W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 27–39. Springer, Heidelberg (2003)
Giannakopoulou, D., Havelund, K.: Automata-based verification of temporal properties on running programs. In: ASE, pp. 412–416. IEEE Computer Society, Los Alamitos (2001)
Giannakopoulou, D., Havelund, K.: Runtime analysis of linear temporal logic specifications. Technical Report 01.21, RIACS/USRA (2001)
Havelund, K., Rosu, G.: Monitoring Java Programs with Java PathExplorer. Electr. Notes Theor. Comp. Sci. 55(2) (2001)
Havelund, K., Rosu, G.: Monitoring programs using rewriting. In: ASE 2001. Proceedings of the 16th IEEE International Conference on Automated Software Engineering, Washington, DC, USA, p. 135. IEEE Computer Society, Los Alamitos (2001)
Havelund, K., Rosu, G.: Synthesizing Monitors for Safety Properties. Tools and Algorithms for Construction and Analysis of Systems, 342–356 (2002)
Lichtenstein, O., Pnueli, A., Zuck, L.: The Glory of the Past. In: Proceedings of the Conference on Logic of Programs, pp. 196–218 (1985)
Manna, Z., Pnueli, A.: Temporal Verification of Reactive Systems: Safety. Springer, Heidelberg (1995)
Pnueli, A.: The temporal logic of programs. In: Proceedings of the 18th IEEE Symposium on the Foundations of Computer Science (FOCS-77), pp. 46–57. IEEE, Los Alamitos (1977)
Pnueli, A., Zaks, A.: Psl model checking and run-time verification via testers. In: Misra, J., Nipkow, T., Sekerinski, E. (eds.) FM 2006. LNCS, vol. 4085, pp. 573–586. Springer, Heidelberg (2006)
Stolz, V., Bodden, E.: Temporal Assertions using AspectJ. In: Fifth Workshop on Runtime Verification (RV 2005). To be published in ENTCS, Elsevier, Amsterdam (2005)
Vardi, M.Y.: An Automata-Theoretic Approach to Linear Temporal Logic. In: Moller, F., Birtwistle, G. (eds.) Logics for Concurrency. LNCS, vol. 1043, pp. 238–266. Springer, Heidelberg (1996)
Vardi, M.Y., Wolper, P.: An automata-theoretic approach to automatic program verification. In: Symposium on Logic in Computer Science LICS 1986, pp. 332–345. IEEE Computer Society Press, Washington (1986)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bauer, A., Leucker, M., Schallhart, C. (2007). The Good, the Bad, and the Ugly, But How Ugly Is Ugly?. In: Sokolsky, O., Taşıran, S. (eds) Runtime Verification. RV 2007. Lecture Notes in Computer Science, vol 4839. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77395-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-77395-5_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77394-8
Online ISBN: 978-3-540-77395-5
eBook Packages: Computer ScienceComputer Science (R0)