Driverless vehicles are expected to form the foundation of future connected transport infrastructure. A key weakness of connected vehicles is their vulnerability to physical-proximity attacks such as sensor saturation attacks. It is natural to study whether such attacks can be used to disrupt swarms of autonomous vehicles used as part of a large fleet providing taxi and courier delivery services. In this paper, we start to examine the strategic options available to attackers and defenders (autonomous-fleet operators) in such conflicts. We find that attackers have the upper hand in most cases and are able to carry out crippling denial-of-service attacks on fleets, by leveraging the inherent deficiencies of road networks identified by techniques from graph analysis. Experimental results on ten cities using real-world courier traces shows that most cities will require upgraded infrastructure to defend driverless vehicles against denial-of-service attacks. We found several hidden costs that impact equipment designers and operators of driverless vehicles - not least, that road-networks need to be redesigned for robustness against attacks thus raising some fundamental questions about the benefits.
The game-theoretic background to the problem at hand lies in the search game within predator-prey games, also known as hider-seeker games. This is a zero sum game between a single predator and a single mobile prey. The predator and prey move about in a search region. The game ends with positive payoff to the predator when it meets the prey. As a bio-inspired example, the blancardella wasp finds larvae by searching for visible evidence of leaf-mining. Wasps are attracted by the appearance of holes or other leaf deformation created bythe leaf-mining larvae. The game begins when the wasp lands on the leaf to search for the larvae, who in turn is alerted by the vibrations caused by the landing wasp triggering evasive behaviour by larvae. When the wasp encounters a feeding hole, it repeatedly inserts its ovipositor violently in the area to ambush the prey. The game ends either with the wasp paralysing the larvae or abandoning the leaf. The formalisation of this problem is well studied within pursuit-evasion games @cite_8 .
@cite_8
1978547141
We analyse a randomized pursuit-evasion game played by two players on a graph, a hunter and a rabbit. Let @math be any connected, undirected graph with @math nodes. The game is played in rounds and in each round both the hunter and the rabbit are located at a node of the graph. Between rounds both the hunter and the rabbit can stay at the current node or move to another node. The hunter is assumed to be restricted to the graph @math : in every round, the hunter can move using at most one edge. For the rabbit we investigate two models: in one model the rabbit is restricted to the same graph as the hunter, and in the other model the rabbit is unrestricted, i.e., it can jump to an arbitrary node in every round.We say that the rabbit is caught as soon as hunter and rabbit are located at the same node in a round. The goal of the hunter is to catch the rabbit in as few rounds as possible, whereas the rabbit aims to maximize the number of rounds until it is caught. Given a randomized hunter strategy for @math , the escape length for that strategy is the worst case expected number of rounds it takes the hunter to catch the rabbit, where the worst case is with regard to all (possibly randomized) rabbit strategies. Our main result is a hunter strategy for general graphs with an escape length of only @math against restricted as well as unrestricted rabbits. This bound is close to optimal since @math is a trivial lower bound on the escape length in both models. Furthermore, we prove that our upper bound is optimal up to constant factors against unrestricted rabbits.