Abstract
In this paper, we demonstrate how model checking can be utilized for the verification of security protocols through a logic of belief. We model principals as processes capable of maintaining beliefs, employing an approach that treats temporal evolution and the belief aspects of principals separately. In this framework, belief formulae are treated as atomic propositions during temporal evolution, while a principal's beliefs about another agent are modeled by granting access to a representation of that agent as a process. We apply this framework to formalize and analyze the Andrew protocol as a motivating example.
Introduction
Security protocols, particularly those designed for authentication and key exchange, are fundamental to secure digital communication. However, verifying their correctness is notoriously difficult. Traditional model checking excels at verifying temporal properties—ensuring that certain states follow others in a specific order. Yet, security is often not just about the sequence of messages but about the internal state of belief of the participants. For instance, after a successful handshake, Principal A should not only possess a session key but should also believe that the key is fresh and believe that Principal B shares this belief.
While "Logics of Belief" (such as BAN logic) provide powerful tools for reasoning about trust, they often lack the automated, state-based verification capabilities of model checkers. This paper bridges that gap by introducing a formal framework that allows standard model checking tools to reason about epistemic properties.
The MAFSM Framework
The authors propose a new theoretical framework called MultiAgent Finite State Machines (MAFSM). The core innovation lies in the separation of temporal evolution from belief, treating them as orthogonal dimensions of the system.
The View Hierarchy
Instead of a single, monolithic state machine, the system is modeled as a tree of "views." The root of this tree, denoted as $\epsilon$, represents the perspective of an external observer. Each subsequent node represents a specific agent's perspective or a nested belief.
In this hierarchy:
- View $B_A$ represents Principal A’s beliefs.
- View $B_A B_B$ represents what Principal A believes Principal B believes.
This structure allows the model to remain finite and checkable, as most security protocols only require reasoning about two or three levels of nested belief.
Explicit vs. Implicit Beliefs
The framework distinguishes between two types of beliefs to maintain computational efficiency:
- Explicit Beliefs: These are treated as simple labels (atomic propositions) within a specific state machine. They represent facts that an agent holds to be true at a given time.
- Implicit Beliefs: These are verified by "jumping" from one state machine to another. To determine if Principal A implicitly believes a proposition $\phi$, the algorithm checks if $\phi$ holds in all states of the $B_A$ view that are compatible with A's current situation.
By treating belief and time as orthogonal, the system can model how a principal's state changes over time while treating their beliefs as "black box" labels that are only expanded into full state-space explorations when necessary.
Case Study: The Andrew Protocol
To validate the framework, the authors formalized the Andrew Protocol, a well-known authentication handshake intended to share a secret key. Despite its design, the protocol is famously vulnerable to freshness attacks, where an attacker replays an old message to trick a principal into using an expired key.
Using the MAFSM framework and the NuSMV model checker, the authors were able to automatically identify this vulnerability. The model checker proved that the protocol fails to satisfy a critical security property: after the final message exchange, Principal A cannot definitively believe that Principal B believes the new session key is valid and fresh. The failure occurs because the principal cannot distinguish between a truly fresh message and a replayed one, modeled here as a lack of belief in the "freshness" variable.
Conclusion and Future Work
This research demonstrates that belief-based verification can be integrated into existing model checking technology with minimal variations. By keeping the number of "views" finite and utilizing explicit belief atoms, the authors provide a scalable way to prove whether a protocol achieves mutual trust.
However, limitations remain. The current approach requires a finite nesting of beliefs and necessitates manual definition of belief atoms and invariants for each view. Future work will focus on automating the translation from high-level protocol descriptions to these specific FSMs and exploring the scalability of the approach in environments with many principals and more complex nested belief structures.
Summary updated