Abstract
When monitoring system behavior to check compliance against a given policy, one is sometimes confronted with incomplete knowledge about system events. In IT systems, such incompleteness may arise from logging infrastructure failures and corrupted log files, or when the logs produced by different system components disagree on whether actions took place. In this paper, we present a policy language with a three-valued semantics that allows one to explicitly reason about incomplete knowledge and handle disagreements. Furthermore, we present a monitoring algorithm for an expressive fragment of our policy language. We illustrate through examples how our approach extends compliance monitoring to systems with logging failures and disagreements.
This work was partly supported by Google Inc.
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
The Health Insurance Portability and Accountability Act of 1996 (HIPAA), Public Law 104-191 (1996)
Gramm-Leach-Bliley Act of 1999 (GLBA), Public Law 106-102 (1999)
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley Longman Publishing Co., Inc., Boston (1995)
Barringer, H., Groce, A., Havelund, K., Smith, M.: Formal analysis of log files. J. Aero. Comput. Inform. Comm. 7, 365–390 (2010)
Basin, D., Harvan, M., Klaedtke, F., Zălinescu, E.: Monitoring usage-control policies in distributed systems. In: TIME 2011, pp. 88–95 (2011)
Basin, D., Harvan, M., Klaedtke, F., Zălinescu, E.: MONPOLY: Monitoring Usage-Control Policies. In: Khurshid, S., Sen, K. (eds.) RV 2011. LNCS, vol. 7186, pp. 360–364. Springer, Heidelberg (2012)
Basin, D., Klaedtke, F., Müller, S., Pfitzmann, B.: Runtime monitoring of metric first-order temporal properties. In: FSTTCS 2008. Leibniz International Proceedings in Informatics (LIPIcs), vol. 2, pp. 49–60 (2008)
Bauer, A., Leucker, M., Schallhart, C.: Comparing LTL semantics for runtime verification. J. Logic Comput. 20(3), 651–674 (2010)
Belnap Jr., N.D.: A useful four-valued logic. In: Dunn, J.M., Epstein, G. (eds.) Modern Uses of Multiple-Valued Logic. Episteme, vol. 2, pp. 7–37. D. Reidel Publishing Company (1977)
Blamey, S.: Partial logic. In: Gabbay, D.M., Guenthner, F. (eds.) Handbook of Philosophical Logic, vol. 5, pp. 261–353. Kluwer Academic Publishers (2002)
Boella, G., Broersen, J., van der Torre, L.: Reasoning about Constitutive Norms, Counts-As Conditionals, Institutions, Deadlines and Violations. In: Bui, T.D., Ho, T.V., Ha, Q.T. (eds.) PRIMA 2008. LNCS (LNAI), vol. 5357, pp. 86–97. Springer, Heidelberg (2008)
Broersen, J.: On the Logic of ’Being Motivated to Achieve ρ, Before δ′. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 334–346. Springer, Heidelberg (2004)
Bruns, G., Godefroid, P.: Model Checking Partial State Spaces with 3-Valued Temporal Logics. In: Halbwachs, N., Peled, D.A. (eds.) CAV 1999. LNCS, vol. 1633, pp. 274–287. Springer, Heidelberg (1999)
Bruns, G., Godefroid, P.: Model Checking with Multi-valued Logics. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 281–293. Springer, Heidelberg (2004)
Bruns, G., Huth, M.: Access control via Belnap logic: Intuitive, expressive, and analyzable policy composition. ACM Trans. Inform. Syst. Secur. 14(1) (2011)
Chechik, M., Devereux, B., Easterbrook, S., Gurfinkel, A.: Multi-valued symbolic model-checking. ACM Trans. Softw. Eng. Meth. 12(4), 371–408 (2003)
Chomicki, J.: Efficient checking of temporal integrity constraints using bounded history encoding. ACM Trans. Database Syst. 20(2), 149–186 (1995)
Crampton, J., Morisset, C.: PTaCL: A Language for Attribute-Based Access Control in Open Systems. In: Degano, P., Guttman, J.D. (eds.) POST 2012. LNCS, vol. 7215, pp. 390–409. Springer, Heidelberg (2012)
Dinesh, N., Joshi, A., Lee, I., Sokolsky, O.: Checking Traces for Regulatory Conformance. In: Leucker, M. (ed.) RV 2008. LNCS, vol. 5289, pp. 86–103. Springer, Heidelberg (2008)
Fitting, M.: Kleene’s logic, generalized. J. Log. Comput. 1(6), 797–810 (1991)
Garg, D., Jia, L., Datta, A.: Policy auditing over incomplete logs: Theory, implementation and applications. In: CCS 2011, pp. 151–162 (2011)
Groce, A., Havelund, K., Smith, M.: From scripts to specification: The evaluation of a flight testing effort. In: ICSE 2010, vol. 2, pp. 129–138 (2010)
Hallé, S., Villemaire, R.: Runtime enforcement of web service message contracts with data. IEEE Trans. Serv. Comput. 5(2), 192–206 (2012)
Hvitved, T., Klaedtke, F., Zălinescu, E.: A trace-based model for multiparty contracts. J. Log. Algebr. Program. 81(2), 72–98 (2012)
Kleene, S.C.: Introduction to Metamathematics. D. Van Nostrand, Princeton (1950)
Stoller, S.D., Bartocci, E., Seyster, J., Grosu, R., Havelund, K., Smolka, S.A., Zadok, E.: Runtime Verification with State Estimation. In: Khurshid, S., Sen, K. (eds.) RV 2011. LNCS, vol. 7186, pp. 193–207. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Basin, D., Klaedtke, F., Marinovic, S., Zălinescu, E. (2013). Monitoring Compliance Policies over Incomplete and Disagreeing Logs. In: Qadeer, S., Tasiran, S. (eds) Runtime Verification. RV 2012. Lecture Notes in Computer Science, vol 7687. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35632-2_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-35632-2_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35631-5
Online ISBN: 978-3-642-35632-2
eBook Packages: Computer ScienceComputer Science (R0)