Petri-Net-Based Model Checking for Privacy-Critical Multiagent Systems

Leifeng He, Guanjun Liu, MengChu Zhou

Abstract

Computation tree logic of knowledge (CTLK) can be used to specify many properties related to privacy of multiagent systems (MASs). Our previous work defined knowledge-oriented Petri nets (KPNs) to formally describe both the interacting/collaborating process of multiagents and their epistemic evolutions. Our KPN-based verification of CTLK required to obtain all reachable states, the transition relation of all states, and the equivalence relations of all states with respect to knowledge, which resulted in a serious state explosion problem and thus only fit some small-scale systems. This article adopts reduced ordered binary decision diagram (ROBDD) to deal with this problem. Especially, the ROBDD technique is used to encode and store all reachable states but not to encode and store any transition relation or equivalence relation. However, when verifying a CTLK formula, the transition relation and equivalence relation of some states must be known. To solve this problem, we design the related algorithms to compute only those required relations and prove their correctness. We design the related model checking algorithms and develop a tool. A number of experiments are done by using a famous benchmark about the privacy problem of MAS: the dining cryptographers protocol (DCP), and the results illustrate the advantages of our methods. For example, our tool running with a general PC spends less than 14 h to verify the DCP with 1200 cryptographers, which involves about $10^{1080}$ states and two CTLK formulas with more than 6000 atomic propositions and more than 3600 operators. This represents a significant advance in the field of model checking.

Introduction

In modern multi-agent systems (MAS), ensuring privacy and security is a critical challenge. Formal verification allows researchers to prove that a system adheres to specific security properties, such as anonymity. To specify these requirements, researchers often use Computation Tree Logic of Knowledge (CTLK), which captures both temporal behavior (how the system evolves) and epistemic states (what an agent knows at any given time).

However, verifying CTLK properties faces the notorious state explosion problem. As the number of agents or variables grows, the possible system states increase exponentially. Traditional tools like MCMAS often struggle because they require pre-calculating every possible transition and knowledge-equivalence relation before verification begins. This research introduces a high-performance symbolic model checking approach that leverages Petri nets and optimized Binary Decision Diagrams to overcome these scalability limits.

Modeling with Knowledge-Oriented Petri Nets (KPN)

The framework utilizes Knowledge-oriented Petri Nets (KPN) to model agent interactions. Unlike traditional modeling languages that often rely on a central environment agent to coordinate behavior, KPNs use the inherent graphical structure of Petri nets—places and transitions—to intuitively represent agent behaviors and their shared knowledge.

Knowledge-oriented Petri Net (KPN) for a communication protocol between Alice and Bob.

As shown in Figure 1, the KPN structure allows for a clear mapping of local agent states and the communication channels between them. This structural clarity is not just for human readability; it provides a topological "map" that the verification algorithms use to optimize data storage.

Symbolic Verification and ROBDD Optimization

To handle the massive state spaces of complex MAS, the authors employ Reduced Ordered Binary Decision Diagrams (ROBDDs). Their approach introduces two major innovations to standard symbolic analysis:

  1. Structural Heuristic Ordering: Finding the optimal variable order for an OBDD is NP-hard. The authors developed a heuristic that uses the Petri net's topology to keep "dependent" variables close together in the diagram, significantly reducing memory consumption.
  2. Dynamic Relation Computation: Instead of pre-computing the entire transition and equivalence relation graph (which causes memory overflows in other tools), the proposed algorithms compute only the specific relations required by the CTLK formula being checked. This "on-the-fly" approach allows the tool to handle state spaces that were previously unreachable.
Reachability graph of the KPN, demonstrating the complex state transitions that lead to the state explosion problem.

Figure 3 illustrates the reachability graph generated from a KPN. In large systems, this graph becomes too massive to store explicitly. By encoding these states symbolically and calculating transitions lazily, the verification remains feasible even as the graph grows to astronomical sizes.

Experimental Results

The authors evaluated their tool, KPNer, using the Dining Cryptographers Protocol (DCP), a standard benchmark for anonymity. The results demonstrate unprecedented scalability:

  • Massive Scalability: KPNer successfully verified a DCP instance with 1,200 agents, involving a state space of approximately $10^{1080}$. For context, this number is vastly larger than the number of atoms in the observable universe.
  • Efficiency: The 1,200-agent verification was completed in less than 14 hours on a standard PC. In smaller tests (100 agents), KPNer finished in just 3 minutes, while the state-of-the-art tool MCMAS timed out after 12 hours.
  • Logic Complexity: The tool handled CTLK formulas with over 6,000 atomic propositions and 3,600 logical operators, proving its robustness for complex real-world specifications.

Conclusion and Future Work

This work represents a significant leap in the scalability of MAS verification. By combining the intuitive modeling of Petri nets with the efficiency of dynamic ROBDD analysis, the authors have provided a path toward verifying large-scale, privacy-critical systems. Future work includes automating the translation of CTLK formulas and extending the framework to support probabilistic logic, which would allow for the verification of "soft" security properties where absolute certainty is not required.

Summary updated

Abstract

Computation tree logic of knowledge (CTLK) can be used to specify many properties related to privacy of multiagent systems (MASs). Our previous work defined knowledge-oriented Petri nets (KPNs) to formally describe both the interacting/collaborating process of multiagents and their epistemic evolutions. Our KPN-based verification of CTLK required to obtain all reachable states, the transition relation of all states, and the equivalence relations of all states with respect to knowledge, which resulted in a serious state explosion problem and thus only fit some small-scale systems. This article adopts reduced ordered binary decision diagram (ROBDD) to deal with this problem. Especially, the ROBDD technique is used to encode and store all reachable states but not to encode and store any transition relation or equivalence relation. However, when verifying a CTLK formula, the transition relation and equivalence relation of some states must be known. To solve this problem, we design the related algorithms to compute only those required relations and prove their correctness. We design the related model checking algorithms and develop a tool. A number of experiments are done by using a famous benchmark about the privacy problem of MAS: the dining cryptographers protocol (DCP), and the results illustrate the advantages of our methods. For example, our tool running with a general PC spends less than 14 h to verify the DCP with 1200 cryptographers, which involves about 101080 states and two CTLK formulas with more than 6000 atomic propositions and more than 3600 operators. This represents a significant advance in the field of model checking.
BibTeX
@article{he2022petri,
  author = {Leifeng He and Guanjun Liu and MengChu Zhou},
  title = {{Petri-Net-Based Model Checking for Privacy-Critical Multiagent Systems}},
  journal = {IEEE Transactions on Computational Social Systems},
  year = {2022},
  doi = {10.1109/tcss.2022.3164052},
}
Figure