ML Security PapersSelf-Creating Random Walks for Decentralized Learning under Pac-Man Attacks
Xingran Chen 1, Parimal Parag 2, Rohit Bhagat 1, Salim El Rouayheb 1
Published on arXiv
2601.07674
Data Poisoning Attack
OWASP ML Top 10 — ML02
Key Finding
CIL guarantees non-extinction of the random walk population and convergence of distributed SGD with a quantifiable deviation from the optimum and at most linear time delay under Pac-Man attacks.
CREATE-IF-LATE (CIL)
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 CREATE-IF-LATE (CIL) algorithm, which is a fully decentralized, resilient mechanism that enables self-creating RWs and prevents RW extinction in the presence of Pac-Man. Our theoretical analysis shows that the CIL algorithm guarantees several desirable properties, such as (i) non-extinction of the RW population, (ii) almost sure boundedness of the RW population, and (iii) convergence of RW-based stochastic gradient descent even in the presence of Pac-Man with a quantifiable deviation from the true optimum. Moreover, the learning process experiences at most a linear time delay due to Pac-Man interruptions and RW regeneration. Our extensive empirical results on both synthetic and public benchmark datasets validate our theoretical findings.
Key Contributions
- Introduces the Pac-Man attack: a stealthy Byzantine behavior where malicious nodes probabilistically terminate visiting random walks, gradually causing RW extinction and halting decentralized learning without triggering explicit failure alarms.
- Proposes CREATE-IF-LATE (CIL), a fully decentralized self-creating random walk algorithm that provably prevents RW extinction under Pac-Man attacks.
- Provides theoretical guarantees for non-extinction, almost-sure bounded RW population, and convergence of RW-based SGD with at most linear time delay under Pac-Man.
🛡️ Threat Analysis
Pac-Man is a Byzantine attack in decentralized/distributed learning where malicious participant nodes disrupt the global learning protocol by probabilistically terminating random walks; the CIL defense is a Byzantine-fault-tolerant mechanism ensuring convergence — analogous to Byzantine-resilient aggregation in federated learning, but operating at the communication-protocol layer rather than the gradient-update layer.