Analisys of Attacks to Automated Vehicular Coordination Systems at Intersections Benjamı́n Holloway Sandra Cespedes Alejandro Hevia benjamin@niclabs.cl scespedes@niclabs.cl ahevia@niclabs.cl Departamento de Departamento de Departamento de Ciencias de la Computación Ingenierı́a Eléctrica Ciencias de la Computación NIC Chile Research Labs NIC Chile Researc Labs NIC Chile Research Labs Universidad de Chile Universidad de Chile Universidad de Chile Abstract Automation of coordination at vehicular inter- section seems to be a desirable technology. It could improve the efficiency of vehicular traffic while reducing the amount of accidents that happens at intersections. There are previous Figura 1: Coordinación de intersección con semáforos works that demonstrate that such automation is possible; however, there is a lack of research pueden distraerse en el proceso de conducir el vehı́culo regarding the vulnerability of these systems in y producir accidentes. case of an attack in the network. In this work, Con el desarrollo de las telecomunicaciones, se we introduce and categorize the existent algo- han desarrollado tecnologı́as que permiten realizar co- rithms employed for automation of intersec- municación inter-vehicular, también conocidas como tions through vehicular communications, and Vehicle-to-Vehicle communications (V2V) donde es present the work in progress to identify the se- posible enviar información de cada vehı́culo (en la red curity vulnerabilities of such solutions in order vehicular ad-hoc) como su velocidad y posición actual. to propose possible mitigations. Esto, junto con tecnologı́as de conducción automáti- ca de vehı́culos, han permitido desarrollar sistemas de 1. Introducción conducción vehicular automática. El ejemplo tı́pico de La coordinación de vehı́culos en intersecciones es un uso es en las caravanas de vehı́culos equipados con problema cotidiano en las ciudades. Esta coordinación Cooperative Adaptive Cruise Control (CACC), las cua- involucra un ámbito de seguridad, de tal manera que les permiten que los vehı́culos viajen en grupos donde se busca que no hayan pérdidas ni materiales ni de se mantiene una velocidad objetivo resguardando una vidas humanas mientras ocurre la coordinación. En la distancia segura entre los autos. Este tipo de solucio- figura 1 se muestra un caso tı́pico de coordinación en nes incrementa el uso eficiente de autopistas a la vez una intersección utilizando semáforos. que reduce el consumo de combustible de los autos A pesar de que las formas actuales de coordinación participantes. vehicular funcionan, estas aún se pueden mejorar. Por La combinación de estas tecnologı́as se están apro- un lado, en cuanto a la eficiencia de la coordinación, vechando para desarrollar sistemas de coordinación con los semáforos puede ocurrir que los tiempos de vehicular en intersecciones, donde se busca mejorar las duración de las luces se descoordinen respecto al flujo falencias de los actuales sistemas de coordinación, es vehicular de la calle, produciendo tiempos ociosos. Por decir, mejorar la eficiencia del transporte urbano en in- otro lado, en cuanto a la seguridad en el transporte, tersecciones y disminuir la cantidad total de accidentes como los vehı́culos son manejados por personas, estas que se producen en estas. En la figura 2 se muestra un ejemplo en donde los vehı́culos, conectados a una red Copyright c 2015 by the paper’s authors. Copying permitted vehicular, se comunican entre ellos y cruzan en forma for private and academic purposes. This volume is published coordinada. and copyrighted by its editors. A continuación se presentan algunos trabajos que This work is partially funded by Project FONDECYT Iniciación No. 11140045. Proceedings of the Spring School on Networks, proponen sistemas de coordinación vehicular au- Santiago, Chile, November 2016, published at http://ceur- tomática en intersecciones. Todos estos consisten en ws.org algoritmos que buscan el orden para que los vehı́culos En [MWN15] se propone un algoritmo que con- siste en dos niveles. El primer nivel es de super- visión, que se encarga de asignar el orden en que cruzarán los vehı́culos la intersección. La segun- da fase consiste en que dado que un vehı́culo sepa después de quién tiene que pasar, se mantenga una distancia con ese vehı́culo de tal manera de cru- zar la intersección sin atravesarse en su camino. Figura 2: Coordinación de intersección automatizada El encargado del nivel de supervisión es solo una presentes en la intersección la crucen sin accidentes y entidad, mientras que el nivel de ejecución (man- en el menor tiempo posible: tener la distancia respecto al vehı́culo que se está siguiendo) es ejecutado por cada vehı́culo. En [ZR12] se plantea un algoritmo que, con teorı́a de juegos, busca optimizar el paso de vehı́culos en En este trabajo se busca identificar e implementar po- intersecciones. Para realizar esto, se busca mini- sibles ataques sobre uno de los algoritmos para siste- mizar el tiempo de cruce de cada vehı́culo mien- mas de coordinación en intersecciones, analizando su tras se evita que dos vehı́culos crucen por el mismo comportamiento cuando se encuentran bajo un ataque lugar al mismo tiempo. En las simulaciones reali- y comparándolo con el funcionamiento del sistema sin zadas se muestra que se pueden mejorar los tiem- ataques presentes. pos de espera en una intersección en 35 segundos por vehı́culo contra una intersección controlada por discos pare. Para el funcionamiento del algo- 2. Elección del Algoritmo a Analizar y ritmo, toda la información necesaria es enviada a Ataques a Realizar una infraestructura central de la intersección, la Para la elección del algoritmo sobre el que se reali- cual es la encargada de modificar las velocidades zarán los ataques, se realizó una comparación de acuer- de los vehı́culos. do a tres criterios: información necesaria para funcio- En [MMG14] el algoritmo planteado consiste en nar, entre quienes se realiza la comunicación y com- obtener la información de todos los vehı́culos en plejidad del algoritmo. Esta comparación se encuen- o acercándose a la intersección (i.e., posición, ve- tra en la Tabla 1. Al analizar los datos obtenidos, se locidad y aceleración actual). Primero se simu- puede ver que 3 de los 4 algoritmos presentan algún la cuánto se demorarı́a cada vehı́culo en cruzar grado de centralización en su funcionamiento. Tanto en condiciones ideales (si la intersección estuviese en [ZR12] como en [MMG14] cada vehı́culo está vacı́a), luego se establecen todas las permutacio- constantemente enviando y recibiendo información de nes posibles en que todos los vehı́culos podrı́an una entidad central, mientras que en [MWN15] cada cruzar la intersección y se calcula cuánto se de- vehı́culo, al llegar a la intersección, tiene que comuni- morarı́a cada vehı́culo para cada permutación. La carse con una entidad central para que ésta le indique demora total se obtiene mediante la suma de la de qué vehı́culo debe recibir información. El resto de demora de cada vehı́culo, la cual corresponde a tiempo cada vehı́culo recibe información de su vehı́cu- cuánto se demorarı́a respecto a la condición ideal. lo objetivo y envı́a información a cada vehı́culo que lo Finalmente, se escoge el orden que tome menor esté siguiendo. En [LW06] el algoritmo presentado es tiempo en ejecutarse. Para realizar este procedi- semi-centralizado, dado que no hay una entidad única miento se utiliza infraestructura de la intersección encargada de realizar la coordinación, si no que cada que recibe toda la información y realiza todos los vehı́culo está constantemente recolectando la informa- cálculos de demoras. ción de todos los vehı́culos presentes en la intersección, y es aquel que logra recolectar toda la información el En [LW06] se propone un algoritmo que genera to- que realiza la coordinación. das las permutaciones de orden en que los vehı́cu- El trabajo de [LW06] fue descartado dado que, a los pueden cruzar, descarta aquellas que no se pue- pesar de que presenta un gran nivel de descentraliza- den realizar (por ejemplo, que el último vehı́culo ción, el vehı́culo que debe realizar la coordinación rea- que llegó a la intersección cruce antes que los que liza una gran cantidad de cómputo en poco tiempo, lo están frente a él), calcula cuánto se demorarı́a ca- que no parece ser implementable. da permutación posible y ejecuta la que demore El algoritmo con el que se trabajará es el presentado menos. Todo este cálculo es realizado por el pri- en [MWN15]. Para trabajar con este algoritmo, pri- mer vehı́culo que obtenga toda la información de mero se propuso una implementación descentralizada todos los vehı́culos en la intersección. del nivel de supervisión. Esta consiste en elegir un lı́der Tabla 1: Comparación de algoritmos para coordinación automática de intersecciones Paper\Criterio Información necesaria para funcionar Entre quienes se comunican Complejidad [MWN15] Supervisory Level (No es simulado en el paper): Cada vehı́culo con el agente del supervisory La implementación del algoritmo puede -Vı́a de ingreso de cada vehı́culo level al ingresar a la zona de coordinación. volverse engorrosa con la parametrización -Intención de cada vehı́culo En cada iteración, cada vehı́culo con su de todas las posiciones Execution level: cada vehı́culo requiere: vehı́culo objetivo -Su propia posición -Posición, velocidad y aceleración de vehı́culo objetivo -Saber a que vehı́culo debe seguir [ZR12] Manager Agent (agente coordinador) requiere que cada Cada reactive agent se comunica con el El cálculo de la utilidad en cada iteración reactive agent (vehı́culo) le envı́e: manager agent y viceversa no está completamente especificada. -Caracterı́sticas fı́sicas de vehı́culo -Posición , velocidad y aceleración actual Cada reactive agent requiere del manager agent: -Actualización de velocidad. [MMG14] Agente coordinador requiere, por cada vehı́culo a 100m Cada vehı́culo se comunica con el agente Cada paso del algoritmo está descrito, de la intersección: coordinador y viceversa la implementación es directa -Posición y velocidad actual -Vı́a por la que se acerca a la intersección -Posición en la vı́a Agente coordinador manda a cada vehı́culo: -Actualización de velocidad [LW06] Cada vehı́culo comparte con los otros lo siguiente: Los vehı́culos se dividen en subgrupos de a El algoritmo está descrito paso a paso. -Id vehı́culo los más 3 miembros. La sección del algoritmo que implica -Tamaño vehı́culo Cada subgrupo posee un lı́der. escoger un orden puede ser compleja -Vı́a actual Este se comunica con los otros lı́deres de -Hacia dónde se dirige subgrupos y con los miembros de su -Variación de velocidad actual subgrupo -Plan de manejo de cada vehı́culo (después de haberse coordinado) -Posición (vı́a actual y distancia al cruce) de cada vehı́culo -Señal de emergencia si es necesaria para que realice la coordinación. Este lı́der realizará la automática de vehı́culos en intersección se pueden ver coordinación hasta que abandone el área de la inter- afectados por ataques de seguridad, causando ya sea sección, eligiéndose como nuevo lı́der al vehı́culo que pérdida materiales o de vidas humanas, y que exis- lleve menos tiempo en la caravana. Con este cambio, el ten mitigaciones que pueden evitar estas pérdidas, con nivel de descentralización del algoritmo es mayor, solo efecto en la eficiencia de los algoritmos. presentando este funcionamiento semi-centralizado en el vehı́culo encargado del nivel de supervisión. Referencias Para los ataques a estudiar, se iniciará con un ata- [LW06] Li Li and Fei-Yue Wang. Cooperative Dri- que del estilo fail-stop sobre el vehı́culo que tenga el ving at Blind Crossings Using Intervehi- nivel de supervisión, de tal manera que, en un inicio, cle Communication. IEEE Transactions deje de responder para realizar la coordinación pero sı́ on Vehicular Technology, 55(6):1712–1724, responda que es el lı́der de la caravana actualmente. nov 2006. Luego se implementarán ataques del tipo message forgery, ya sea interviniendo los mensajes enviados por [MMG14] Igor Moretti, Monica Menendez, and Ilgin los vehı́culos o la información misma que envı́an, mo- Guler. Car2X communications at intersec- dificando información esencial para el funcionamiento tions: Delay and emission minimizing al- del algoritmo, como la posición real del vehı́culo o su gorithms implemented in VISSIM. IEEE aceleración actual. Vehicular Networking Conference, 2014. [MWN15] Alejandro Ivan Morales Medina, Nathan 3. Conclusiones Van De Wouw, and Henk Nijmeijer. Au- tomation of a T-intersection Using Vir- En este trabajo se aborda el tema de la seguridad tual Platoons of Cooperative Autonomous en algoritmos de coordinación automática de vehı́cu- Vehicles. IEEE Conference on Intelli- los en intersecciones. Para esto, primero se realizó un gent Transportation Systems, Proceedings, estudio comparativo de algunos trabajos para encon- ITSC, 2015-Octob:1696–1701, 2015. trar cuál es el que mejor cumple con las caracterı́sticas necesarias para realizar este análisis. Luego de elegido [ZR12] Ismail H. Zohdy and Hesham Rakha. el trabajo, este se modificó para que funcione de un Game theory algorithm for intersection- modo descentralizado, planteándose luego algunos ti- based cooperative adaptive cruise control pos de ataques que son interesantes de estudiar sobre (CACC) systems. IEEE Conference on el algoritmo elegido. Intelligent Transportation Systems, Procee- En el trabajo a futuro se espera que los resultados dings, ITSC, pages 1097–1102, 2012. muestren que los algoritmos existentes de coordinación