ECE PhD Dissertation Defense: Kacper Wardega

Title: Securing Multi-Robot Systems with Inter-robot Observations and Accusations

Presenter: Kacper Wardega

Advisor: Professor Wenchao Li

Chair: Professor Brian Kulis

Committee: Professor Wenchao Li, Professor Roberto Tron, Professor David Starobinski, Professor Christos Cassandras

Abstract: Multi-robot systems (MRSs) are becoming increasingly popular in various industries, such as manufacturing, logistics, agriculture, defense, search and rescue, and transportation. These systems consist of multiple robots that work together to achieve a common goal, either autonomously or under the supervision of a human operator. However, emerging MRSs operate in uncertain or even adversarial environments, and the sensors and actuators of each robot may be error-prone. MRSs are, therefore, vulnerable to faults and security threats unique to MRSs that cannot be detected or mitigated using classical techniques from distributed systems. This dissertation proposes novel techniques to improve the security and fault-tolerance of MRSs through inter-robot observations and accusations.

First, I propose a fundamental security property for MRSs that ensures the detection of forbidden deviations from a desired multi-robot motion plan by the system supervisor. I demonstrate that relying solely on self-reported motion information from the robots for monitoring deviations can leave the system vulnerable to attacks from a single compromised robot. To address this issue, I introduce the concept of co-observations, which are additional data reported to the supervisor to supplement the self-reported motion information. I formalize co-observation-based detection as a method of identifying deviations from the expected motion plan based on discrepancies in the sequence of co-observations reported. I then formulate an optimal deviation-detecting motion planning problem that achieves all the original application objectives while guaranteeing that all forbidden plan-deviation attacks trigger co-observation-based detection by the supervisor. As a proof-of-concept, I propose a secure motion planner based on constraint solving to implement the deviation-detecting security property.

Second, I further improve the security and resilience of MRSs against plan deviation attacks by limiting the information available to attackers. I investigate the attack planning problem and establish that how the motion plan is announced to the robots determines the attacker's ability to compute an attack that the supervisor will not detect. Leveraging this fact, I propose an efficient algorithm that verifies the inability of an attacker to stealthily perform forbidden plan deviation attacks with a given motion plan and announcement scheme. Such announcement schemes are referred to as horizon-limiting. I then formulate an optimal horizon-limiting planning problem that maximizes planning lookahead while maintaining the announcement scheme as horizon-limiting. Experimental results demonstrate the efficiency and scalability of co-observations and horizon-limiting announcements in protecting MRSs, including systems with hundreds of robots, as evidenced by a case study in a warehouse setting.

Finally, this dissertation introduces the Decentralized Blocklist Protocol (DBP), a method for designing Byzantine-resilient decentralized MRSs. DBP is based on inter-robot accusations and allows cooperative robots to identify misbehavior through co-observations and share this information through the network. It is adaptive to the number of faulty robots and is widely applicable to various decentralized MRS applications. Furthermore, the method permits fast information propagation, requires fewer cooperative observers of application-specific variables, and reduces the worst-case connectivity requirement, making it more scalable than existing methods. Empirical results demonstrate the scalability and effectiveness of DBP in cooperative target tracking, time synchronization, and localization case studies with hundreds of robots.

This dissertation provides new techniques to enhance the security and fault-tolerance of MRSs operating in uncertain and adversarial environments. Furthermore, these techniques will aid in developing secure MRSs for emerging applications.