We have described the proof score approach to analysis of e-commerce protocols, which has been developed and refined through several case studies conducted. As described in Section 1, compared to systems analysis using other existing interactive theorem provers such as Isabelle/HOL and Coq, the proof score approach to systems analysis has some advantages: (1) balanced human-computer interaction and (2) flexible but clear structure of proof scores. Moreover, thanks to our way of modeling messages and networks, we can express various properties such that some events always precede others in terms of invariants only. It is not necessary to introduce other constructs such as finite automata and filtering functions, which may make verification complicated.
As described in Section 1, the proof score approach to systems analysis is less rigorous than systems analysis using other existing interactive theorem provers such as Isabelle/HOL and Coq. To overcome this disadvantage, we have been developing some tools: Gateau60 and Cr`eme41,42,43. Given state predicates for case splitting and necessary lemmas, Gateau generates proof scores. Gateau has successfully gen-erated the proof scores to verify that some security properties hold for the NSLPK authentication protocol33,34 and the Otway-Rees authentication protocol56. Cr`eme is an automatic invariant verification tool for algebraic specifications of OTSs. We have verified fully automatically that some security properties hold for the NSLPK authentication protocol and the STS authentication protocol13. One piece of our future work is to apply those tools to analyses of e-commerce protocols.
To take advantage of model checkers, which are complementary to interactive theorem provers, we have also been developing some tools, which takes CafeOBJ specifications of OTSs and generates specifications that can be model-checked:
Chocolat/SMV55 and Cafe2Maude31. Chocolat/SMV translates CafeOBJ specifi-cations of OTSs into SMV specifispecifi-cations, which are model-checked with SMV38. Cafe2Maude translates CafeOBJ specifications of OTSs into Maude specifications that can be model-checked with the Maude model checker16. Another piece of our future work is to apply those tools to analyses of e-commerce protocols.
This paper only focuses on invariant properties. There must be, however, some security properties that cannot be expressed as invariant properties. The OTS/CafeOBJ method can deal with some class of liveness properties54. Therefore, it would be worth pursuing what kind of security properties should be expressed as liveness properties and extending the method described in this paper to deal with liveness properties.
There have been proposed some dedicated security analysis tools. It would be worth integrating the method described in this paper with such a tool.
Acknowledgement
The authors wish to thank anonymous referees who commented on drafts of this paper.
References
1. Giampaolo Bella, Fabio Massacci, and Lawrence C. Paulson. The verification of an industrial payment protocol: The SET purchase phase. In9th ACM CCS, pages 12–20, 2002.
2. Giampaolo Bella, Fabio Massacci, and Lawrence C. Paulson. Verifying the SET reg-istration protocols.IEEE J-SAC, 21:77–87, 2003.
3. M. Bellare, J. A. Garay, R. Hauser, A. Herzberg, H. Krawczyk, M. Steiner, G. Tsudik, E. Van Herreweghen, and M. Waidner. Design, implementation and deployment of the iKP secure electronic payment system.IEEE J-SAC, 18(4):611–627, 2000.
4. M. Bellare, J. A. Garay, R. Hauser, A. Herzberg, H. Krawczyk, M. Steiner, G. Tsudik, and M. Waidner.iKP – a family of secure electronic payment protocols. In1st USENIX EC, pages 89–106, 1995.
5. Yves Bertot and Pierre Cast´eran.Interactive Theorem Proving and Program Devel-opment – Coq’Art: The Calculus of Inductive Constructions. Springer, 2004.
6. Dominique Bolignano. Towards the formal verification of electronic commerce proto-cols. In10th IEEE CSFW, pages 133–146, 1997.
7. Michael Butler and Divakar Yadav. An incremental development of the Mondex sys-tem in Event-B.Formal Asp. Comput., 20(1):61–77, 2008.
8. Benjamin Cox, J. D. Tygar, and Marvin Sirbu. NetBill security and transaction pro-tocol. In1st USENIX EC, pages 77–88, 1995.
9. R˘azvan Diaconescu and Kokichi Futatsugi. CafeOBJ Report, volume 6 of AMAST Series in Computing. World Scientific, 1998.
10. R˘azvan Diaconescu and Kokichi Futatsugi. Behavioural coherence in object-oriented algebraic specification.J. UCS, 6:74–96, 2000.
11. R˘azvan Diaconescu, Kokichi Futatsugi, and Kazuhiro Ogata. CafeOBJ: Logical foun-dations and methodologies.Computing and Informatics, 22:257–283, 2003.
12. T. Dierks and C. Allen. The TLS protocol version 1.0. Request for Commnets: 2246, http://www.ietf.org/rfc/rfc2246.txt, 1999.
13. Whitfield Diffie, Paul C. van Oorschot, and Michael J. Wiener. Authentication and authenticated key exchanges.Designs, Codes and Cryptography, 2:107–125, 1992.
14. Danny Dolev and Andrew C. Yao. On the security of public key protocols. IEEE Trans. Info. Theory, IT-29:198–208, 1983.
15. Jr. Edmund M. Clarke, Orna Grumberg, and Doron A. Peled.Model Checking. The MIT Press, 2001.
16. Steven Eker, Jos´e Meseguer, and Ambarish Sridharanarayanan. The Maude LTL model checker. In4th WRLA, volume 71 ofENTCS, pages 162–187. Elsevier, 2002.
17. Leo Freitas and Jim Woodcock. Mechanising Mondex with Z/Eves.Formal Asp. Com-put., 20(1):117–139, 2008.
18. Kokichi Futatsugi, Joseph A. Goguen, and Kazuhiro Ogata. Verifying design with proof scores. InVSTTE 2005, volume 4171 ofLNCS, pages 277–290. Springer, 2008.
19. Chris George and Anne Elisabeth Haxthausen. Specification, proof, and model check-ing of the Mondex electronic purse uscheck-ing RAISE.Formal Asp. Comput., 20(1):101–116, 2008.
20. Joseph Goguen.Theorem Proving and Algebra. The MIT Press, (to appear).
21. Joseph Goguen and Grant Malcolm. A hidden agenda.TCS, 245:55–101, 2000.
22. Joseph Goguen and Grant Malcolm, editors. Software Engineering with OBJ: Alge-braic Specification in Action. Kluwer, 2000.
23. Dominik Haneberg, Gerhard Schellhorn, Holger Grandy, and Wolfgang Reif. Verifica-tion of Mondex electronic purses with KIV: from transacVerifica-tions to a security protocol.
Formal Asp. Comput., 20(1):41–59, 2008.
24. Nevin Heintze, J.D. Tygar, Jeannette Wing, and H. Chi Wong. Model checking elec-tronic commerce protocols. In2nd USENIX EC, pages 147–164, 1996.
25. Tony Hoare and Jayadev Misra. Verified software: Theories, tools, experiments vi-sion of a grand challenge project. In1st VSTTE, volume 4171 ofLNCS, pages 1–18.
Springer, 2008.
26. Gunther Horn and Bart Preneel. Authentication and payment in future mobile sys-tems. In5th ESORICS, volume 1485 ofLNCS, pages 277–293. Springer, 1998.
27. J. Hsiang and N. Dershowitz. Rewrite methods for clausal and nonclausal theorem proving. In10th ICALP, volume 154 ofLNCS, pages 331–346. Springer, 1983.
28. Florent Jacquemard, Michael Rusinowitch, and Laurent Vigneron. Compiling and verifying security protocols. In 7th LPAR, volume 1955 of LNCS, pages 131–160.
Springer, 2000.
29. Cliff B. Jones and Jim Woodcock, editors.Formal Aspects of Computing. Number 1 in 20. Springer, 2008.
30. Weiqiang Kong, Kazuhiro Ogata, and Kokichi Futatsugi. Algebraic approaches to formal analysis of the mondex electronic purse system. In6th IFM, volume 4591 of LNCS, pages 393–412. Springer, 2007.
31. Weiqiang Kong, Kazuhiro Ogata, Takahiro Seino, and Kokichi Futatsugi. A lightweight integration of theorem proving and model checking for system verifica-tion. In12th APSEC, pages 59–66. IEEE CS Press, 2005.
32. Mirco Kuhlmann and Martin Gogolla. Modeling and validating Mondex scenarios described in UML and OCL with USE.Formal Asp. Comput., 20(1):79–100, 2008.
33. Gavin Lowe. An attack on the Needham-Schroeder public-key authentication protocol.
IPL, 56:131–133, 1995.
34. Gavin Lowe. Breaking and fixing the Needham-Schroeder public-key protocol using FDR. In2nd TACAS, volume 1055 ofLNCS, pages 147–166. Springer, 1996.
35. Gavin Lowe. Casper: A compiler for the analysis of security protocols. In10th IEEE CSFW, pages 18–30, 1997.
36. Shiyong Lu and Scott A. Smolka. Model checking the Secure Electronic Transaction (SET) protocol. In6th MASCOTS, pages 358–365, 1999.
37. MasterCard/Visa. SET secure electronic transactions protocol – book 1: Business specifications; book 2: Technical specification; book 3: Formal protocol definition.
http://www.setco.org/set specifications.html, May 1997.
38. Kenneth L. McMillan.Symolic Model Checking: An Approach to the State Explosion Problem. Kluwer, 1993.
39. Jonathan K. Millen and Grit Denker. CAPSL and MuCAPSL.J. Telecomm. & Info.
Tech., 4:16–27, 2002.
40. John C. Mitchell, Vitaly Shmatikov, and Ulrich Stern. Finite-state analysis of SSL 3.0 and related protocols. InDIMACS Workshop on Design and Formal Verification of Security Protocols, 1997.
41. Masahiro Nakano, Kazuhiro Ogata, Masaki Nakamura, and Kokichi Futatsugi. Auto-matic verification of the STS authentication protocol with Cr`eme. In20th ITC-CSCC, pages 15–16, 2005.
42. Masahiro Nakano, Kazuhiro Ogata, Masaki Nakamura, and Kokichi Futatsugi. Au-tomating invariant verification of behavioral specifications. In6th QSIC, pages 49–56.
IEEE CS Press, 2006.
43. Masahiro Nakano, Kazuhiro Ogata, Masaki Nakamura, and Kokichi Futatsugi. Cr`eme:
An automatic invariant prover of behavioral specifications.IJSEKE, 17(6):783–804, 2007.
44. Roger M. Needham and Michael D. Schroeder. Using encryption for authentication in