Minimizing Expected Intrusion Detection Time in Adversarial
Patrolling

D 2022

Minimizing Expected Intrusion Detection Time in Adversarial Patrolling

KLAŠKA, David, Antonín KUČERA, Vít MUSIL a Vojtěch ŘEHÁK

Základní údaje

Originální název

Minimizing Expected Intrusion Detection Time in Adversarial Patrolling

Autoři

KLAŠKA, David (203 Česká republika, domácí), Antonín KUČERA (203 Česká republika, garant, domácí), Vít MUSIL (203 Česká republika, domácí) a Vojtěch ŘEHÁK (203 Česká republika, domácí)

Vydání

Neuveden, 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022. od s. 1660-1662, 3 s. 2022

Nakladatel

International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

Paper URL

Kód RIV

RIV/00216224:14330/22:00126563

Organizační jednotka

Fakulta informatiky

ISBN

978-1-4503-9213-6

ISSN

DOI

http://dx.doi.org/10.5555/3535850.3536068

Klíčová slova anglicky

Security Games; Adversarial Patrolling

Štítky

formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 28. 3. 2023 11:53, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

In adversarial patrolling games, a mobile Defender strives to discover intrusions at vulnerable targets initiated by an Attacker. The Attacker’s utility is traditionally defined as the probability of completing an attack, possibly weighted by target costs. However, in many real-world scenarios, the actual damage caused by the Attacker depends on the time elapsed since the attack’s initiation to its detection. We introduce a formal model for such scenarios, and we show that the Defender always has an optimal strategy achieving maximal protection. We also prove that finite-memory Defender’s strategies are sufficient for achieving protection arbitrarily close to the optimum. Then, we design an efficient strategy synthesis algorithm based on differentiable programming and gradient descent.We evaluate the efficiency of our method experimentally.

Návaznosti

CZ.02.2.69/0.0/0.0/18_053/0016952, interní kód MU
(Kód CEP: EF18_053/0016952)

Název: Postdoc2MUNI

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Postdoc2MUNI, PO 2 Rozvoj vysokých škol a lidských zdrojů pro výzkum a vývoj

EF18_053/0016952, projekt VaV

Název: Postdoc2MUNI

MUNI/A/1145/2021, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI. (Akronym: SV-FI MAV XI.)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace XI.

0011629866, interní kód MU

Název: Models, Algorithms, and Tools for Solving Adversarial Security Problems

Investor: Ostatní - zahraniční, Models, Algorithms, and Tools for Solving Adversarial Security Problems

Citovat

KLAŠKA, David, Antonín KUČERA, Vít MUSIL a Vojtěch ŘEHÁK. Minimizing Expected Intrusion Detection Time in Adversarial Patrolling. Online. In Piotr Faliszewski, Viviana Mascardi, Catherine Pelachaud, Matthew E. Taylor. 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022. Neuveden: International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022, s. 1660-1662. ISBN 978-1-4503-9213-6. Dostupné z: https://dx.doi.org/10.5555/3535850.3536068.

@inproceedings{2214539,
   author = {Klaška, David and Kučera, Antonín and Musil, Vít and Řehák, Vojtěch},
   address = {Neuveden},
   booktitle = {21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022.},
   doi = {http://dx.doi.org/10.5555/3535850.3536068},
   editor = {Piotr Faliszewski, Viviana Mascardi, Catherine Pelachaud, Matthew E. Taylor},
   keywords = {Security Games; Adversarial Patrolling},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Neuveden},
   isbn = {978-1-4503-9213-6},
   pages = {1660-1662},
   publisher = {International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)},
   title = {Minimizing Expected Intrusion Detection Time in Adversarial Patrolling},
   url = {https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p1660.pdf},
   year = {2022}
}

TY  - JOUR
ID  - 2214539
AU  - Klaška, David - Kučera, Antonín - Musil, Vít - Řehák, Vojtěch
PY  - 2022
TI  - Minimizing Expected Intrusion Detection Time in Adversarial Patrolling
PB  - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
CY  - Neuveden
SN  - 9781450392136
KW  - Security Games
KW  - Adversarial Patrolling
UR  - https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p1660.pdf
N2  - In adversarial patrolling games, a mobile Defender strives to discover intrusions at vulnerable targets initiated by an Attacker. The Attacker’s utility is traditionally defined as the probability of completing an attack, possibly weighted by target costs. However, in many real-world scenarios, the actual damage caused by the Attacker depends on the time elapsed since the attack’s initiation to its detection. We introduce a formal model for such scenarios, and we show that the Defender always has an optimal strategy achieving maximal protection. We also prove that finite-memory Defender’s strategies are sufficient for achieving protection arbitrarily close to the optimum. Then, we design an efficient strategy synthesis algorithm based on differentiable programming and gradient descent.We evaluate the efficiency of our method experimentally.
ER  -

KLAŠKA, David, Antonín KUČERA, Vít MUSIL a Vojtěch ŘEHÁK. Minimizing Expected Intrusion Detection Time in Adversarial Patrolling. Online. In Piotr Faliszewski, Viviana Mascardi, Catherine Pelachaud, Matthew E. Taylor. \textit{21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022.}. Neuveden: International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2022, s.~1660-1662. ISBN~978-1-4503-9213-6. Dostupné z: https://dx.doi.org/10.5555/3535850.3536068.

Podrobný výpis o publikaci