ML Security PapersRandom Walk Learning and the Pac-Man Attack
Xingran Chen 1, Parimal Parag 2, Rohit Bhagat 1, Zonghong Liu 1, Salim El Rouayheb 1
Published on arXiv
2508.05663
Data Poisoning Attack
OWASP ML Top 10 — ML02
Key Finding
RW-SGD under the AC algorithm remains convergent even in the presence of Pac-Man adversaries, with a quantifiable and bounded deviation from the true global optimum
Average Crossing (AC)
Novel technique introduced
Random walk (RW)-based algorithms have long been popular in distributed systems due to low overheads and scalability, with recent growing applications in decentralized learning. However, their reliance on local interactions makes them inherently vulnerable to malicious behavior. In this work, we investigate an adversarial threat that we term the ``Pac-Man'' attack, in which a malicious node probabilistically terminates any RW that visits it. This stealthy behavior gradually eliminates active RWs from the network, effectively halting the learning process without triggering failure alarms. To counter this threat, we propose the Average Crossing (AC) algorithm--a fully decentralized mechanism for duplicating RWs to prevent RW extinction in the presence of Pac-Man. Our theoretical analysis establishes that (i) the RW population remains almost surely bounded under AC and (ii) RW-based stochastic gradient descent remains convergent under AC, even in the presence of Pac-Man, with a quantifiable deviation from the true optimum. Our extensive empirical results on both synthetic and real-world datasets corroborate our theoretical findings. Furthermore, they uncover a phase transition in the extinction probability as a function of the duplication threshold. We offer theoretical insights by analyzing a simplified variant of the AC, which sheds light on the observed phase transition.
Key Contributions
- Formalizes the Pac-Man attack — a stealthy Byzantine threat where malicious nodes probabilistically terminate visiting random walks to gradually halt decentralized RW-SGD
- Proposes the Average Crossing (AC) algorithm, a fully decentralized RW duplication mechanism that keeps the RW population almost surely bounded despite adversarial termination
- Proves convergence of RW-SGD under AC in the presence of Pac-Man adversaries and characterizes the bounded deviation from the true optimum, including a phase transition in extinction probability as a function of the duplication threshold
🛡️ Threat Analysis
The Pac-Man attack is a Byzantine participant attack in a decentralized/federated learning setting: malicious nodes disrupt the global learning process by terminating gradient-carrying random walks, degrading training without triggering alarms. The AC defense counters this by restoring learning convergence, analogous to Byzantine-fault-tolerant aggregation in FL.