On the relationships between models in protocol verification

We formally investigate the relationships between several models that are widely used in protocol verification, namely variants of the inductive model of message traces inspired by Paulson’s approach, and models based on rewriting. More precisely, we prove several over-approximation relationships between models, i.e. that one model allows strictly more traces or reachable states than the other. This is common in verification: often an over-approximation is easier to prove correct than the original model, and proving that the over-approximation is safe implies that the original model is safe—provided that the models are indeed in an over-approximation relation. We then show that some over-approximations are not sound with respect to a common formalization of authentication goals based on exchanged messages. The precise formal account that we give on the relation of the models allows us to correct the situation.