A decision procedure for the existence of a rank function

Article type: Research Article

Authors: Heather, James | Schneider, Steve

Affiliations: Department of Computing, University of Surrey, Guildford, Surrey, GU2 7XH, UK. E-mail: j.heather@surrey.ac.uk, s.schneider@surrey.ac.uk

Abstract: Schneider's work on rank functions [IEEE TSE 24(9) (1998)] provides a formal approach to verification of certain properties of a security protocol. However, he illustrates the approach only with a protocol running on a small network; and no help is given with the somewhat hit-and-miss process of finding the rank function that underpins the central theorem. In this paper, we develop the theory to allow for an arbitrarily large network, and give a clearly defined decision procedure by which one may either construct a rank function, proving correctness of the protocol, or show that no rank function exists. We briefly discuss the implications of the absence of a rank function, and the open question of completeness of the rank function theorem.

DOI: 10.3233/JCS-2005-13204

Journal: Journal of Computer Security, vol. 13, no. 2, pp. 317-344, 2005