Abstract
We introduce a general approach to cryptographic protocol verification based on answer set programming. In our approach, cryptographic protocols are represented as extended logic programs where the answer sets correspond to traces of protocol runs. Using queries, we can find attacks on a protocol by finding the answer sets for the corresponding logic program. Our encoding is modular, with different modules representing the message passing environment, the protocol structure and the intruder model. We can easily tailor each module to suit a specific application, while keeping the rest of the encoding constant. As such, our approach is more flexible and elaboration tolerant than related formalizations. The present system is intended as a first step towards the development of a compiler from protocol specifications to executable programs; such a compiler would make verification a completely automated process. This work is also part of a larger project in which we are exploring the advantages of explicit, declarative representations of protocol verification problems.
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
Aiello, L.C., Massacci, F.: Verifying security protocols as planning in logic programming. ACM Trans. Comput. Logic 2(4), 542–580 (2001)
Alberti, M., Chesani, F., Gavanelli, M., Lamma, E., Mello, P., Torroni, P.: Security protocols verification in abductive logic programming: A case study. In: Dikenelli, O., Gleizes, M.-P., Ricci, A. (eds.) ESAW 2005. LNCS (LNAI), vol. 3963, pp. 106–124. Springer, Heidelberg (2006)
Baral, C., Brewka, G., Schlipf, J. (eds.): LPNMR 2007. LNCS (LNAI), vol. 4483. Springer, Heidelberg (2007)
Burrows, M., Abadi, M., Needham, R.: A logic of authentication. ACM Transactions on Computer Systems 8(1), 18–36 (1990)
Delgrande, J.P., Hunter, A., Grote, T.: Modelling cryptographic protocols in a theory of action. In: Proceedings of the Ninth International Symposium on Logical Formalizations of Commonsense Reasoning (2009)
Dolev, D., Yao, A.: On the security of public key protocols. IEEE Transactions on Information Theory 29(2), 198–208 (1983)
Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning about Knowledge. MIT Press, Cambridge (1995)
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., Thiele, S.: Engineering an incremental ASP solver. In: Garcia de la Banda, M., Pontelli, E. (eds.) ICLP 2008. LNCS, vol. 5366, pp. 190–205. Springer, Heidelberg (2008)
Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: clasp: A conflict-driven answer set solver. In: Baral et al [3], pp. 260–265
Gebser, M., Schaub, T., Thiele, S.: Gringo: A new grounder for answer set programming. In: Baral et al [3], pp. 266–271
Gelfond, M.: Answer sets. In: Handbook of Knowledge Representation, pp. 285–316. Elsevier, Amsterdam (2007)
Gelfond, M., Lifschitz, V.: Action languages. Electronic Transactions on AIÂ 3 (1998)
Hernández-Orallo, J., Pinto, J.: Formal modelling of cryptographic protocols in situation calculus (Published in Spanish as: Especificación formal de protocolos criptográficos en Cálculo de Situaciones, Novatica, 143, pp. 57–63, 2000) (1997)
Levesque, H.J., Pirri, F., Reiter, R.: Foundations for the situation calculus. Linköping Electronic Articles in Computer and Information Science 3(18) (1998)
Lowe, G.: Breaking and fixing the needham-schroeder public-key protocol using FDR. In: Margaria, T., Steffen, B. (eds.) TACAS 1996. LNCS, vol. 1055, pp. 147–166. Springer, Heidelberg (1996)
Wang, S., Zhang, Y.: A logic programming based framework for security protocol verification. In: An, A., Matwin, S., Ras, Z.W., Slezak, D. (eds.) Foundations of Intelligent Systems. LNCS (LNAI), vol. 4994, pp. 638–643. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Delgrande, J.P., Grote, T., Hunter, A. (2009). A General Approach to the Verification of Cryptographic Protocols Using Answer Set Programming. In: Erdem, E., Lin, F., Schaub, T. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2009. Lecture Notes in Computer Science(), vol 5753. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04238-6_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-04238-6_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04237-9
Online ISBN: 978-3-642-04238-6
eBook Packages: Computer ScienceComputer Science (R0)