Dynamic Crowd Vetting: Collaborative Detection of Malicious Robots in Dynamic Communication Networks

摘要

Coordination in a large number of networked robots is a challenging task, especially when robots are continuously moving around the environment and there are malicious attacks within the network. Various approaches in the literature exist for detecting malicious robots, such as message sampling or suspicious behavior analysis. However, these approaches require every robot to sample or observe every other robot in the network, leading to a slow detection process that degrades team performance. This paper introduces a method that significantly decreases the detection time for legitimate robots to identify malicious robots in a scenario where legitimate robots are randomly moving around the environment. Our method leverages a concept that we refer to as “Dynamic Crowd Vetting;’ whereby, by utilizing observations from random encounters in combination with trusted neighboring robots' opinions, legitimate robots can quickly improve the accuracy of detecting malicious robots. The key intuition is that as long as each legitimate robot accurately estimates the legitimacy of at least some fixed subset of the team, the second-hand information they receive from trusted neighbors is enough to correct any misclassifications and provide accurate trust estimations of the rest of the team. We show that the size of this fixed subset can be characterized as a function of fundamental graph and random walk properties. Furthermore, we formally show that the detection time remains constant with respect to team size for a fixed ratio of legitimate to malicious robots. We develop a closed form expression for the critical number of time-steps required for our algorithm to successfully identify the true legitimacy of each robot to within a specified failure probability. Our theoretical results are validated through simulations demonstrating significant reductions in detection time when compared to previous works that do not leverage trusted neighbor information.