Abstract
Runtime verification (RV) is a successful technique to monitor system behavior at runtime and potentially take compensating actions in case of deviation from a specification. For the usage in safety critical systems the question of reliability of RV components arises since in existing approaches RV components are not verified and may themselves be erroneous.
In this paper, we present work towards a framework for certified RV components. We present a solution for implementations of transition functions of RV monitors and prove them correct using the Coq proof assistant. We extract certified executable OCaml code and use it inside RV monitors. We investigate an application scenario in the domain of automotive embedded systems and present performance evaluation for some monitored properties.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allan, C., Avgustinov, P., Christensen, A.S., Hendren, L., Kuzins, S., Lhoták, O., de Moor, O., Sereni, D., Sittampalam, G., Tibble, J.: Adding trace matching with free variables to AspectJ. SIGPLAN Notices (October 2005)
Arden, D.N.: Delayed-logic and finite-state machines, pp. 133–151. IEEE (1961)
Barringer, H., Goldberg, A., Havelund, K., Sen, K.: Rule-Based Runtime Verification. In: Steffen, B., Levi, G. (eds.) VMCAI 2004. LNCS, vol. 2937, pp. 44–57. Springer, Heidelberg (2004)
Barringer, H., Groce, A., Havelund, K., Smith, M.: Formal analysis of log files. Journal of Aerospace Computing, Information, and Communication (2010)
Barringer, H., Havelund, K.: TraceContract: A Scala DSL for Trace Analysis. In: Butler, M., Schulte, W. (eds.) FM 2011. LNCS, vol. 6664, pp. 57–72. Springer, Heidelberg (2011)
Barringer, H., Rydeheard, D., Havelund, K.: Rule systems for run-time monitoring: from EAGLE to RuleR. Journal of Logic and Computation (June 2010)
Blech, J.O., Grégoire, B.: Certifying compilers using higher-order theorem provers as certificate checkers. Formal Methods in System Design (2011)
Colombo, C., Pace, G.J., Schneider, G.: Larva — safer monitoring of real-time Java programs (tool paper). In: Software Engineering and Formal Methods (SEFM 2009), pp. 33–37. IEEE Computer Society (2009)
The Coq development team. The coq proof assistant reference manual v8.4 (2012), http://coq.inria.fr
Falcone, Y., Fernandez, J.-C., Mounier, L.: Runtime Verification of Safety-Progress Properties. In: Bensalem, S., Peled, D.A. (eds.) RV 2009. LNCS, vol. 5779, pp. 40–59. Springer, Heidelberg (2009)
FlexRay communications system protocol specification version 2.1, FlexRay Consortium (May 2005)
Havelund, K., Goldberg, A.: Verify Your Runs. In: Meyer, B., Woodcock, J. (eds.) VSTTE 2005. LNCS, vol. 4171, pp. 374–383. Springer, Heidelberg (2008)
Kaiser, R., Wagner, S.: The PikeOS Concept: History and Design. SysGO AG White Paper, http://www.sysgo.com
Kim, M., Viswanathan, M., Lee, I., Ben-Abdellah, H., Kannan, S., Sokolsky, O.: Formally Specified Monitoring of Temporal Properties. In: European Conference on Real-Time Systems (ECRTS) (1999)
Kopetz, H.: TTP - A time-triggered protocol for fault-tolerant real-time systems. In: Fault-Tolerant Computing. IEEE (1993)
Lee, I., Kannan, S., Kim, M., Sokolsky, O., Viswanathan, M.: Runtime Assurance Based On Formal Specifications. In: International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas (1999)
Meredith, P., Jin, D., Griffith, D., Chen, F., Roşu, G.: An overview of the MOP runtime verification framework. International Journal on Software Tools for Technology Transfer (2011)
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)
Rosu, G., Chen, F.: Semantics and Algorithms for Parametric Monitoring. Logical Methods in Computer Science (2012)
Rushby, J.: Runtime Certification. In: Leucker, M. (ed.) RV 2008. LNCS, vol. 5289, pp. 21–35. Springer, Heidelberg (2008)
Steinbach, T., Korf, F., Schmidt, T.C.: Comparing time-triggered Ethernet with FlexRay: An evaluation of competing approaches to real-time for invehicle networks. In: 8th IEEE International Workshop on Factory Communication Systems (2010)
Stolz, V., Bodden, E.: Temporal assertions using AspectJ. In: Proc. of the 5th Int. Workshop on Runtime Verification, RV 2005. ENTCS, vol. 144(4). Elsevier (2006)
Sridhar, M., Hamlen, K.W.: Flexible in-lined reference monitor certification: challenges and future directions. In: Programming Languages meets Program Verification. ACM (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blech, J.O., Falcone, Y., Becker, K. (2012). Towards Certified Runtime Verification. In: Aoki, T., Taguchi, K. (eds) Formal Methods and Software Engineering. ICFEM 2012. Lecture Notes in Computer Science, vol 7635. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34281-3_34
Download citation
DOI: https://doi.org/10.1007/978-3-642-34281-3_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34280-6
Online ISBN: 978-3-642-34281-3
eBook Packages: Computer ScienceComputer Science (R0)