Patrolling adversarial environments exploiting an alarm system

Physical security is one of the most important challenges of our times. Due to the terrible events happened in the last decades all around the world, and especially nowadays in Europe, novel techniques and methods are being developed to face new threats and dangers. But security means also helping people and saving lives, e.g., detecting and rescuing desperate migrants that are moving across the Mediterranean Sea. Algorithmic Game Theory allows us to scientifically investigate these phenomena, modeling such interactions as mathematical problems and designing suitable algorithms to deal with these threats. When patrolling large environments or infrastructures, a crucial issue is to guarantee some level of protection to each area without being able to constantly surveil them. A common countermeasure is the usage of cheap but wide-ranged sensors, able to detect malicious events that may occur. In this thesis, we propose the first Security Game model with the presence of an alarm system able to trigger alarm signals, carrying the information about targets that can be under attack. Specifically, we focus on the exploitation of such information to improve the effectiveness of guards’ strategies. The dissertation is structured in three parts, according to the research lines along which the contributions are developed. First, we study the uncertainties that may affect the alarm system. We start considering spatial uncertainty, i.e., the signal sent to the Defender communicates that something suspicious is happening in an area, without specifying the exact location. We show that, without false positives and missed detections, the best patrolling strategy reduces to stay in a place, wait for a signal, and respond to it at best. Experimental results show that our approach could be adopted in real-world applications, e.g., the protection of Expo 2015. Then, we introduce a positive missed detection rate, i.e., no alarm signal is generated even though an attack is occurring. We show that the previous approach is no more optimal and provide the Defender with the best patrolling strategy to move her resource, showing that a deterministic approach is arbitrarily better than a randomized one. The second direction we investigate is the dimension of the problem, namely, the number of resources both the Defender and the Attacker can control. We tackle the problem of finding the minimum number of defending resources assuring non-null protection to every target, and then we study how the Defender should move them, providing algorithms to deal with three different levels of coordination among the resources. Then, we investigate the opportunities the Attacker can take when she can perform multiple attacks, simultaneously or sequentially. Unfortunately, computing the equilibrium strategies requires the knowledge on the number of Attacker’s resources. Since it is unlikely to have this information, we also provide two online algorithms to compute the best strategy when the Defender makes a guess about such number and plays her best strategy accordingly. The last line we explore introduces the notion of uncertainty in the type of the Attacker. We tackle the problem of facing an unknown adversary, whose profile is just known to be in a list of possible profiles she can assume. Here, a different approach is required: we want to learn the profile of the Attacker to exploit such information in the future to prevent her from performing other attacks. To do this, we design two algorithms and provide a regret analysis and show that our approach outperforms the online learning algorithms available in the state of the art.

Garantire protezione e sicurezza è una delle sfide attualmente più importanti. In seguito ai terribili eventi verificatisi negli ultimi decenni, e recentemente anche in Europa, si stanno sviluppando nuove tecniche e metodi innovativi per fronteggiare tali minacce. D'altra parte, fornire sicurezza significa anche aiutare le persone e salvare vite umane, ad esempio, individuando e mettendo in salvo migranti disperati che attraversano il Mediterraneo. La Teoria dei Giochi Algoritmica permette di investigare scientificamente tali fenomeni, modellando queste interazioni come problemi matematici e progettando algoritmi appropriati per gestire queste situazioni. Quando si effettua il pattugliamento di grandi ambienti o infrastrutture complesse, un aspetto cruciale è assicurare un determinato livello di protezione ad ogni area, senza avere la possibilità di sorvegliarla costantemente. Una contromisura tipica consiste nel posizionare nell’ambiente sensori economici ad ampio raggio, in grado di individuare possibili eventi anomali. In questa tesi, proponiamo il primo Security Game in cui introduciamo la presenza di un sistema di allarme in grado di generare dei segnali di allarme, che forniscono informazioni su un insieme di obiettivi sensibili potenzialmente sotto attacco. Più precisamente, ci concentriamo su come sfruttare al meglio tali informazioni per migliorare l'efficacia delle strategie di pattugliamento delle guardie poste a protezione dell’ambiente. La tesi è strutturata in tre parti, seguendo le linee di ricerca lungo cui si sviluppano i vari contributi. Inizialmente, studiamo diversi tipi di incertezza che possono colpire il sistema di allarme. Introduciamo l’incertezza spaziale, i.e., il segnale generato dal sistema di allarme comunica al Difensore che qualcosa di sospetto sta avvenendo in una certa area, senza però poterne specificare il punto esatto. Mostriamo che, quando il sistema non è influenzato da falsi positivi o negativi, la miglior strategia di pattugliamento risulta essere quella di stare fermi in un’area dell’ambiente finchè non si riceve un segnale di allarme e, solo allora, muoversi nel modo più efficace ed efficiente per controllare i nodi potenzialmente sotto attacco. I risultati sperimentali che abbiamo ottenuto mostrano come il nostro approccio possa essere adottato in applicazioni realistiche, e.g., la protezione di Expo 2015. Successivamente, introduciamo la possibilità che il sistema generi un falso negativo, i.e., vi è la possibilità che non venga generato alcun segnale di allarme anche se vi sia un attacco in corso. Dimostriamo che stare fermi ad attendere un segnale di allarme non è più ottimale e forniamo al Difensore la miglior strategia di pattugliamento per muovere la propria risorsa, mostrando che un approccio deterministico è arbitrariamente migliore di uno randomizzato. La seconda direzione che investighiamo è la dimensione del problema, dando la possibilità sia al Difensore che all'Attaccante di controllare un numero maggiore di risorse. Dapprima ci concentriamo sul Difensore, studiando come calcolare il numero minimo di risorse in grado di assicurare un certo livello di protezione ad ogni obiettivo. Successivamente, analizziamo come il Difensore debba muoverle, fornendo algoritmi per tre diversi livelli di coordinazione tra le risorse. In seguito, studiamo le opportunità a disposizione dell'Attaccante quando può effettuare molteplici attacchi, simultanei o sequenziali. Sfortunatamente, calcolare le strategie di equilibrio in tale contesto richiede la conoscenza del numero di risorse dell'Attaccante. Dato che è molto raro avere questa informazione a disposizione, forniamo due algoritmi online per calcolare la miglior strategia del Difensore quando quest'ultimo faccia delle ipotesi riguardo il numero di risorse controllate dall’Attaccante e giochi di conseguenza. L'ultima linea di ricerca che esploriamo introduce la nozione di incertezza anche per l'Attaccante. Studiamo il problema di affrontare un avversario ignoto, di cui sappiamo solo che il profilo appartiene ad una lista di possibili candidati. In questo scenario si richiede un nuovo approccio: vogliamo infatti imparare il profilo dell'Attaccante così da poter sfruttare tale informazione per prevenire ulteriori attacchi. Per fare ciò, forniamo due algoritmi e una analisi del regret, mostrando anche sperimentalmente che il nostro approccio è notevolmente superiore agli algoritmi di online learning presenti in letteratura.