Affiliations: [a] Department of Computer Science, UC Berkeley, Berkeley, CA 94720, USA. E-mail: dawnsong@cs.berkeley.edu, perrig@cs.berkeley.edu | [b] Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA. E-mail: berez@cs.cmu.edu
Correspondence:
[*]
Corresponding author.
Note: [1] This research is supported in part by the Defence Advanced Research Projects Agency under DARPA contract N6601-99-28913 (under supervision of the Space and Naval Warfare Systems Center San Diego), by the National Science foundation under grant FD99-79852, and by the United States Postal Service under grant USPS 1025 90-98-C-3513. Views and conclusions contained in this document are those of the authors and do not necessarily represent the official opinion or policies, either expressed or implied of the US government or any of its agencies, DARPA, NSF, USPS.
Abstract: We propose a new efficient automatic verification technique, Athena, for security protocol analysis. It uses a new efficient representation – our extension to the Strand Space Model, and utilizes techniques from both model checking and theorem proving approaches. Athena is fully automatic and is able to prove the correctness of many security protocols with arbitrary number of concurrent runs. The run time for a typical protocol from the literature, like the Needham–Schroeder protocol, is often a fraction of a second. Athena exploits several different techniques that enable it to analyze infinite sets of protocol runs and achieve such efficiency. Our extended Strand Space Model is a natural and efficient representation for the problem domain. The security properties are specified in a simple logic which permits both efficient proof search algorithms and has enough expressive power to specify interesting properties. The automatic proof search procedure borrows some efficient techniques from both model checking and theorem proving. We believe that it is the right combination of the new compact representation and all the techniques that actually makes Athena successful in fast and automatic verification of security protocols.
