SWARMFLAWFINDER: Discovering and Exploiting Logic Flaws of Swarm Algorithms

摘要

Inspired by swarms in nature, swarm robotics have been developed to conduct various challenging tasks such as environmental monitoring, disaster recovery, logistics, and even military operations. Despite the significant potential impact of the swarm on society, relatively little attention is given to adversarial scenarios against swarm robotics. In this paper, we explore a systematic approach to find logical flaws of the swarm robotics algorithms that adversaries can exploit. Specifically, we develop an automated testing system, SWARMFLAWFINDER, for swarm algorithms. We identify and overcome various challenges in understanding and reasoning about the swarm algorithm execution. In particular, we propose a novel abstraction of robotics behavior, which we call the degree of causal contribution (DCC), based on the idea of counterfactual causality. Then, we build a feedback guided greybox fuzz testing system called SWARMFLAWFINDER, leveraging DCC as a feedback metric. We evaluate SWARMFLAWFINDER with four swarm algorithms conducting navigating, searching, and rescuing missions. SWARMFLAWFINDER discovers 42 logic flaws (and all of them have been acknowledged by the developers) in the swarm algorithms. Our analysis of the flaws reveals that the swarm algorithms have critical logic errors/bugs or suffer from incomplete implementations that can be exploited by adversaries.