Accountable intersection management protocols

Abstract

Los protocolos de gestión de intersecciones son una propuesta moderna para enfrentar las deficiencias de los métodos convencionales dedicados a esta tarea, tales como semáforos y señaléticas. Principalmente orientados a vehículos autónomos, estos protocolos se basan en la existencia de un dispositivo de cómputo a bordo de cada vehículo, el cual mediante el uso de comunicación V2V (vehicle-to-vehicle) logra coordinar con sus pares una estrategia eficiente de cruce. Un problema latente en este tipo de protocolos, es la existencia de una componente física, es decir, cada participante de la interacción vehicular puede tomar la decisión de ignorar la estrategia acordada en el protocolo y seguir un comportamiento malicioso que lleve a resultados subóptimos e incluso de peligro.

En esta tesis estudiamos la seguridad de algoritmos de coordinación vehicular bajo adversarios del tipo descrito, donde la acción maliciosa es esencialmente imposible de prevenir. Inspirados en los métodos utilizados por redes sociales, estudiamos un sistema de reportes como medida disuasiva, que incentive el buen comportamiento. De este modo, un vehículo malicioso deberá enfrentar las consecuencias punitivas asociadas a su acción.

Como punto de partida, presentamos un modelo genérico para protocolos de gestión de intersecciones, basado en comunicación síncrona organizada en rondas. Dicho modelo admite comportamiento malicioso físico, permitiendo construir una simplificación realista de una interacción real, sobre la cual puedan ser analizados diferentes protocolos. En base a lo anterior, abstraemos cada protocolo de gestión de intersecciones como una máquina de estados, la cual define de forma precisa los escenarios de comportamiento malicioso mediante estados especiales catalogados como "maliciosos". El sistema de reportes propuesto, se basa en demostrar que el acusado gatilló un estado malicioso dentro de este sistema.

Presentamos dos técnicas generales para construir de protocolos de reportes. La primera se enfoca únicamente en la verificabilidad del reporte, mientras que la segunda apunta además a preservar la privacidad de la interacción vehicular. Para lograr esto último, hacemos uso de una poderosa herramienta criptográfica llamada zk-SNARK, cuyo nombre deriva de zero-knowledge Succint ARgument of knowledge, la cual nos permite generar demostraciones eficientes de que una aseveración es verdadera. Las propiedades de las técnicas presentadas son argumentadas mediante demostraciones matemáticas, basadas en técnicas estándares criptográficas.

El trabajo concluye con una discusión de estrategias para mejorar la eficiencia de protocolos de reporte como el presentado.

Intersection management protocols are a modern response to the shortcomings of conventional methods of vehicle coordination, such as traffic lights and signaling. Oriented to autonomous vehicles, these protocols are based on the existence of a computing device on board each vehicle, which through the use of V2V (vehicle-to-vehicle) communication manages to coordinate with its peers an efficient crossing strategy. A latent problem in this type of protocols is the existence of a physical component, i.e., each participant in the vehicular interaction may decide to ignore the strategy prescribed by the protocol and follow a malicious behavior that leads to suboptimal and even dangerous results. In this thesis, we study the security of vehicular coordination algorithms under adversaries of the type described, where malicious action is essentially impossible to prevent. Inspired by the methods used by social networks, we study a reporting system as a deterrent measure, which encourages good behavior. In this way, a malicious vehicle will have to face the punitive consequences associated with its action. As a starting point, we present a generic model for intersection management protocols, based on synchronous communication organized in rounds. This model captures physical malicious behavior, allowing to build a realistic simplification of a real interaction, on which different protocols can be analyzed. Based on the above, we abstract each intersection management protocol as a state machine, which allows us to define malicious behavior scenarios as special (“malicious”) states. In our proposed reporting system, vehicles simply prove that the alleged offender triggered a malicious state within this system. We present two general techniques for constructing reporting protocols. The first uniquely focuses on the verifiability of the report, while the second also aims to preserve the privacy of the vehicular interaction. To achieve the latter, we utilize a powerful cryptographic tool called zk-SNARK, which stands for zero-knowledge Succinct ARgument of Knowledge. This tool allows us to generate efficient proofs that a given statement is true. The properties of the presented techniques are supported by mathematical proofs based on standard cryptographic methods. This thesis concludes with a discussion of strategies to improve the efficiency of reporting protocols such as the one presented.