Decoy allocation games on graphs with temporal logic objectives

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

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

Publication date 8 December 2021

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

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)

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.

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

Cites work

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

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)