Safe Collaborative driving Systems
The objective of this project has been to apply the techniques developed for communications networks to collaborative, intelligent vehicles. The techniques are applied to a lane merge protocol that assists a driver who is merging between two vehicles in an adjacent lane.
The previous work that has been reported on this project includes: a multiple stack, layered architecture; a strategy for using synchronized clocks; and the probabilistic verification of protocols.
The architecture is similar to the layered architectures that are commonly used in communications networks. The objective is to partition a complex problem into manageable pieces. The layers have well defined interfaces that allow us to modify layers without modifying adjacent layers. The principle difference between communications networks and vehicles is the number and type of interactions with the physical world. Communications networks interact with the physical world through a communications channel, while vehicles also interact with the physical movement of the vehicle, a variety of sensors, and are time critical. The architecture has a separate stack for each interaction with the physical world. As in the communications architecture, the physical operations are at the bottom of the stacks and the intelligent operations are in the higher layers.
Clock synchronization is used to simplify the coordination of interacting vehicles and to create a new set of protocols. Clocks can be accurately synchronized because of the wide spread deployment of GPS, low cost crystal oscillators, and standardized synchronization protocols. The clocks simplify the testing of protocols by assuming that vehicles can perform operations simultaneously, or in a specified order, rather than considering many ordering of events. Two new protocols that have been invented are a broadcast protocol with a unique message that cannot be lost, and a lock protocol in which locks are released simultaneously, even after communications is lost.
In the broadcast protocol each participant is scheduled to transmit at specified times. The unique message is a scheduled message that is not transmitted. This message cannot be lost – a message is not received if it isn’t sent. This message has been used to abort operations and return the vehicle to a safe state – for instance moving from a collaborative operation to a defensive, self-driving mode. Whenever a vehicle aborts an operation, all of the vehicles abort the operation. The lock protocol is used to guarantee that a vehicle participates in at most one collaborative operation at a time. This allows us to test the safety of collaborative operations separately, instead of considering multiple maneuvers that may occur.
Probabilistic verification bounds the probability of accidents by testing the most likely sequences of operations that may occur. Operations are divided into bins, for instance highly likely and less likely operations, to determine which sequences are tested first. The requirements for vehicle safety are especially demanding. Unacceptable failures, such as the ignition problem in GM vehicles, occur as infrequently as once every 10’s or 100’s of years. These failures are unlikely to be detected using test tracks or standard simulations, but are detected using probabilistic verification. The lane merge protocol has been shown to fail less than once every 5*10^13 protocol invocations. Within the architecture we test the components separately. When a component has a nonzero failure probability, the components that depend upon it must take this into account. We have developed design rules for component dependencies to guarantee that failures can be bounded.
This year we have investigated conformance testing and protection against malicious users. Conformance testing has been reduced to a previous problem, and is solved. The solutions for malicious users have been divided into two categories, punishment for malicious acts and prevention of malicious acts.
Conformance testing is used to test the implementations from different providers to guarantee that they will interoperate. We assume that the protocol is correct, and are only concerned with whether or not a provider has completely and accurately implemented the protocol. This problem was first addressed at Bell Labs in the 1990’s to guarantee that advanced telecommunications equipment, such as ISDN phones, from different manufacturers would all operate together. The strategy constructed a finite state model (FSM) of the protocol and determined if each implementation contained all of the states and transitions of the model. By testing each implementation against the model, rather than testing each implementation against all others, the number of tests is more reasonable when there are a large number of implementations. Bell Labs developed a package, the Postman Package, that uses an analogy to a rural postman tour to construct short testing sequences.
The problem with the Postman package is that is does not deal well with timing constraints that are common in intelligent driving applications. Instead of solving the problem, we avoided it. We redesigned our protocols so that all time related operations are performed in the timing stack. There are no timers or time related tests in any of the protocols. Protocols can send messages to the timing stack to request messages at specified times. All time related events become messages, which fit well with the FSM model of the postman package. The Postman package has been used to generate test sequences for the lane merge protocol.
Malicious users may cause accidents, or may just prevent collaborative operations from occurring. The difference between consumer applications and military applications is that malicious users are criminals and can be punished. All of the messages are signed. If messages from a particular user causes an accident or prevents collaborations from occurring, the user can be identified.
In addition to punishing a malicious user, we want to stop malicious users from causing accidents. Instead of having a general communications interface that allows a hack to gain access to the software, interactions occur between FSM’s with restricted message sets. Software updates on the intelligent vehicle should only be performed in a controlled environment. There should also be a firewall between the intelligent vehicle software and any other communications from the vehicle.
There are two types of messages between intelligent vehicles, data messages and control messages. The data messages are used to exchange sensor readings, synchronize clocks, … , and the control messages change the state of the FSM’s. A malicious user can insert inaccurate data messages. For instance, the malicious user may report a larger gap between vehicles than exists. We can prevent a single malicious, or faulty user from causing an accident by requiring all measurements to be corroborated by multiple vehicles. When there is a disagreement, the collaborative operation is aborted.
The finite set of control messages between vehicles can be completely examined to determine if it is possible for a malicious user to cause an accident. We start by itemizing the set of states that might result in an accident. For instance, two vehicles being given permission to enter the same gap. As in many security applications, we only prevent the attacks that we expect. The security mechanisms become stronger as we identify more of the attacks.
We assume that a malicious user may transmit any of the allowable control messages in any order. We conduct a depth first search of a composite FSM in which all of the participants, except one, transmits messages according to the protocol, and the malicious user may transmit any of the permissible messages. An accident may occur if the malicious user can force the system into any of the set of states that we have identified.
We have manually applied the depth first search to our current system, and have modified the lock protocol. Our verification procedures assume that vehicles only participate in one collaborative operation at a time. The original lock protocol assumes that a vehicle will not take part in a second collaboration. A malicious user can take part in multiple merge protocols. The lock protocol is being modified to broadcast the lock state of vehicles so that vehicles cannot participate in multiple locks with nearby vehicles. During the current year we will automate the depth first search.