Decoy allocation games on graphs with temporal logic objectives

DOI10.1007/978-3-030-64793-3_9zbMATH Open1483.68044arXiv2010.01208OpenAlexW3126961494MaRDI QIDQ2056945FDOQ2056945

Authors: Abhishek N. Kulkarni, Jie Fu, Huan Luo, Charles A. Kamhoua, Nandi O. Leslie 

Publication date: 8 December 2021

Abstract: We study a class of games, in which the adversary (attacker) is to satisfy a complex mission specified in linear temporal logic, and the defender is to prevent the adversary from achieving its goal. A deceptive defender can allocate decoys, in addition to defense actions, to create disinformation for the attacker. Thus, we focus on the problem of jointly synthesizing a decoy placement strategy and a deceptive defense strategy that maximally exploits the incomplete information the attacker about the decoy locations. We introduce a model of hypergames on graphs with temporal logic objectives to capture such adversarial interactions with asymmetric information. Using the hypergame model, we analyze the effectiveness of a given decoy placement, quantified by the set of deceptive winning states where the defender can prevent the attacker from satisfying the attack objective given its incomplete information about decoy locations. Then, we investigate how to place decoys to maximize the defender's deceptive winning region. Considering the large search space for all possible decoy allocation strategies, we incorporate the idea of compositional synthesis from formal methods and show that the objective function in the class of decoy allocation problem is monotone and non-decreasing. We derive the sufficient conditions under which the objective function for the decoy allocation problem is submodular, or supermodular, respectively. We show a sub-optimal allocation can be efficiently computed by iteratively composing the solutions of hypergames with a subset of decoys and the solution of a hypergame given a single decoy. We use a running example to illustrate the proposed method.

Full work available at URL: https://arxiv.org/abs/2010.01208

Recommendations

• Harnessing the power of deception in attack graph-based security games
• Game theory on attack graph for cyber deception
• Optimal placement of honeypots for network defense
• Deception tactics for network interdiction: a multiobjective approach
• Modeling secrecy and deception in a multiple-period attacker-defender signaling game

zbMATH Keywords

games on graphstemporal logicdeceptionhypergames

Mathematics Subject Classification ID

Applications of game theory (91A80) Games involving graphs (91A43) Temporal logic (03B44) Computer security (68M25)

Cites Work

• Infinite Games
• Title not available (Why is that?)
• A survey of stochastic \(\omega \)-regular games
• Title not available (Why is that?)
• Solution concepts in hypergames
• Concurrent reachability games
• Infinite games played on finite graphs
• Antichains and compositional algorithms for LTL synthesis
• Computing optimal randomized resource allocations for massive security games
• Graph Games and Reactive Synthesis
• Game theoretic model of strategic honeypot selection in computer networks
• Approximate solutions for attack graph games with imperfect information
• Honeypot Allocation Games over Attack Graphs for Cyber Deception

Cited In (1)

• Game theory on attack graph for cyber deception

This page was built for publication: Decoy allocation games on graphs with temporal logic objectives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2056945)