Game-Theoretic Threat Screening and Deceptive Techniques for Cyber Defense

Aaron SchlenkerAAAI 2018 · DOI

Abstract

Modern cybersecurity operations are characterized by an overwhelming volume of alerts generated by automated detection systems, leading to a critical bottleneck in human analyst resources. This paper explores the application of game theory to optimize threat screening processes. By extending traditional Threat Screening Games (TSGs) to incorporate general-sum payoffs, varying investigation times, and deceptive tactics, this research provides a robust framework for strategic resource allocation. We introduce the GATE algorithm for solving complex general-sum games and the Cyber-alert Allocation Game (CAG) model to account for temporal constraints, ultimately demonstrating how defenders can leverage asymmetric information to mislead adversaries.

1. Introduction

The proliferation of Intrusion Detection and Prevention Systems (IDPS) and Security Information and Event Management (SIEM) tools has created a "deluge of alerts" that often exceeds the capacity of human security teams. This phenomenon, known as alert fatigue, was a primary factor in the 2013 Target breach, where critical warnings were ignored amidst a sea of false positives. To address this, researchers have turned to Threat Screening Games (TSGs), mathematical models designed to optimize the allocation of limited screening resources against potential threats.

However, traditional TSG models suffer from three significant limitations: they often assume zero-sum interactions, they fail to account for the varying time required to investigate different alert types, and they assume attackers possess perfect information while ignoring the defender's potential for deception. This research addresses these gaps by proposing more realistic and computationally efficient game-theoretic models for cyber defense.

2. Methodology and Algorithmic Frameworks

2.1 Stackelberg Game Framework

The research utilizes a Stackelberg game model where the defender (the leader) commits to a randomized screening strategy. The adversary (the follower) observes this strategy over time and reacts by choosing the target or attack vector that maximizes their utility. This framework allows defenders to proactively set a policy that accounts for rational adversarial responses.

2.2 Marginal Strategies and the Bihierarchy Constraint

To overcome the "curse of dimensionality"—the exponential growth of possible screening combinations—the author employs marginal strategies. Instead of calculating every possible permutation of resource assignments, the model focuses on the expected number of objects screened by a specific resource. To ensure these mathematical marginals can be translated into valid real-world schedules, the research leverages a "bihierarchy" condition, guaranteeing the implementability of the calculated strategies.

2.3 The GATE Algorithm

For scenarios where the defender's loss does not perfectly mirror the attacker's gain (general-sum games), the author developed the GATE algorithm. GATE utilizes a hierarchical tree structure to decompose large-scale games into smaller, manageable sub-games. By employing a branch-and-bound search, the algorithm identifies optimal strategies in environments that were previously considered computationally prohibitive (NP-hard).

2.4 Cyber-alert Allocation Games (CAGs)

Recognizing that not all alerts are equal, the CAG model introduces a temporal component. It accounts for the fact that different alert types require different investigation times and that specific attacks manifest as certain alert types with varying probabilities. This allows for a more granular and realistic allocation of an analyst's limited shift time.

3. Strategic Deception

Beyond resource allocation, this research explores the use of asymmetric information as a defensive tool. By manipulating an attacker’s "belief state" during the reconnaissance phase, defenders can feed false information regarding network configurations. This deceptive modeling aims to trick adversaries into targeting low-value assets or decoys, thereby reducing the defender's overall expected loss.

4. Key Results and Insights

  • Scalability: The GATE algorithm demonstrates the ability to solve general-sum TSGs at scales relevant to modern enterprise networks, outperforming traditional column generation techniques.
  • Resource Efficiency: The CAG model provides a more effective allocation of analyst time than standard TSGs by incorporating fixed investigation times ($T^r_a$), ensuring that the most critical and time-sensitive threats are prioritized.
  • Deceptive Efficacy: Preliminary results indicate that altering an adversary's perception of asset values can successfully divert attacks, proving that proactive deception is a viable complement to traditional screening.

5. Limitations and Future Work

While the current models offer significant improvements, several challenges remain. The assumption of "perfect knowledge"—where the attacker perfectly understands the defender's strategy—is often unrealistic; future work should model attackers with only partial visibility. Additionally, the current models assume fixed investigation times, whereas real-world analysis is stochastic. Future iterations of the CAG framework will need to incorporate time distributions and address parameter uncertainty regarding the volume of incoming alerts. Finally, the full integration of deception tactics into the CAG framework remains a primary objective for concluding this research.

Summary updated

BibTeX
@inproceedings{schlenker2018game,
  author = {Aaron Schlenker},
  title = {{Game-Theoretic Threat Screening and Deceptive Techniques for Cyber Defense}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11363},
}
Figure