Boolean Consensus and Intrusion Detection for Secure Distributed Robotics

This Thesis focuses on Distributed Robotics and Cooperating Objects and addresses a problem of Security in these research fields. Distributed robotic systems are normally meant to be used in application scenarios that lack of a centralized infrastructure, and where agents of the system are not secured from malicious intervention. This fact, along with the availability of local intelligence, in terms of sensing, processing, and actuation, may represent a potential strength for an attacker willing to damage the system. Broadly speaking, an attacker may be an agent that has simply stopped working, due to spontaneous failure, but also any entity that can arbitrarily deviates for the system’s specification. These types of issues are studied in Security, a branch of Computer Science, where malicious software agents are called intruders, and their threat is attacked by the use of an Intrusion Detection System (IDS). In this setting, the work proposes the paradigm of a distributed IDS for realizing secure multi–agent systems. In a robotic system, misbehavior of an agent may concern both its physical actions and the correctness of any data that it processes and exchanges with the rest of the system. The proposed paradigm consists of two major contributions. The first is a synthesis technique for the construction of a local IDS, that endows every agent with the capability to detect misbehavior in the actions of other neighboring agents, only using local information. The property that makes our solution appealing is the fact that the local IDS can be systematically synthesized once the agents’ dynamics and the rules according to which they should interact are given. The second ma jor contribution is an agreement mechanism which allows every agent to consent on the presence of misbehaviors among their common neighbors. With this respect, outputs from local IDSs are typically continuous sets, representing e.g. regions where the presence or the absence of an agent is required, that are of a different type from conventional consensus protocols. This motivates the definition of a novel form of consensus, where agents are able to exchange data representing sets or intervals. In this vein, we consider an abstraction to the problem of reaching consensus on sets and focus on distributed estimation of a logical function. This problem is solved by exploiting so–called logical consensus protocols, that are systems where agents of a communication network are able to exchange logical values representing their local estimate of a quantity of interest. Their realization builds upon known results on cellular automata and convergence of finite–state iteration maps. An ambitious ob jective in this context would be to develop a design technique for a logical consensus system that can be as systematic as it is for the well–known linear case. In this work, we provide algorithms to generate optimal and robust logical consensus systems, under suitable joint conditions on the visibility of agents and their communication capability. Application of these results in the original context of the IDS endows the local monitors with the capability to tolerate incorrect information, injected by a potential intruder that may falsely report its own position, invent a non–existing neighbor, omit an existing one, or pretend that it is elsewhere with the aim of impairing safety or causing denial of service. The final main contribution of the work is a unified framework for achieving consensus on sets as well as on logical functions. Both classes of problems involve indeed types of data and operations that are instances of Boolean algebras. The framework can build upon general Boolean dynamic system theory and allows us to uniformly address both cases. Finally, as it is shown in the very last chapter, the framework is suitable for addressing other distributed estimation problems, such as clock synchronization in wireless sensor networks