Deconstructing Alice and Bob

Alice&Bob-notation is a simple notation for describing security protocols as sequences of message exchanges. We show that, despite the fact that Alice&Bob-notation does not include explicit control flow constructs, it is possible to make some of these aspects explicit when producing formal protocol models without having to resort to more expressive protocol description languages. We introduce a notion of incremental symbolic run to formally handle message forwarding and conditional abortion. In incremental symbolic runs, we use variables to represent messages that the principals cannot read, and we characterize each of the execution steps in order to build a collection of symbolic subruns of increasing lengths, reflecting the data possessed by the principals up to that point in the execution. We contrast this with the simpler (more standard) approach based on formalizing the behavior of principals by directly interpreting message exchanges as sequences of atomic actions. In particular, we provide a complete characterization of the situations where this simpler approach is adequate and prove that incremental symbolic runs are more expressive in general.