Accountable intersection management protocols
Author
Professor Advisor
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.
xmlui.dri2xhtml.METS-1.0.item-notadetesis.item
Tesis para optar al grado de Magíster en Ciencias, Mención Computación Memoria para optar al título de Ingeniero Civil en Computación
Patrocinador
Este trabajo ha sido parcialmente financiado por ANID
Subdirección de Capital Humano, Magíster Nacional 2022
Identifier
URI: https://repositorio.uchile.cl/handle/2250/203862
Collections
The following license files are associated with this item: