A game-theoretic approach for selecting optimal time-dependent thresholds for anomaly detection

Amin Ghafouri, Aron Laszka, Waseem Abbas, Yevgeniy Vorobeychik, Xenofon Koutsoukos

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Adversaries may cause significant damage to smart infrastructure using malicious attacks. To detect and mitigate these attacks before they can cause physical damage, operators can deploy anomaly detection systems (ADS), which can alarm operators to suspicious activities. However, detection thresholds of ADS need to be configured properly, as an oversensitive detector raises a prohibitively large number of false alarms, while an undersensitive detector may miss actual attacks. This is an especially challenging problem in dynamical environments, where the impact of attacks may significantly vary over time. Using a game-theoretic approach, we formulate the problem of computing optimal detection thresholds which minimize both the number of false alarms and the probability of missing actual attacks as a two-player Stackelberg security game. We provide an efficient dynamic programming-based algorithm for solving the game, thereby finding optimal detection thresholds. We analyze the performance of the proposed algorithm and show that its running time scales polynomially as the length of the time horizon of interest increases. In addition, we study the problem of finding optimal thresholds in the presence of both random faults and attacks. Finally, we evaluate our result using a case study of contamination attacks in water networks, and show that our optimal thresholds significantly outperform fixed thresholds that do not consider that the environment is dynamical.

Original languageEnglish (US)
Pages (from-to)430-456
Number of pages27
JournalAutonomous Agents and Multi-Agent Systems
Volume33
Issue number4
DOIs
StatePublished - Jul 1 2019

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'A game-theoretic approach for selecting optimal time-dependent thresholds for anomaly detection'. Together they form a unique fingerprint.

Cite this