SoK: Harmonizing Attack Graphs and Intrusion Detection Systems

This paper presents the first systematic analysis of Attack Graph and Intrusion Detection System integration, proposing a novel unifying lifecycle framework that establishes a continuous feedback loop to enhance threat detection and incident response.

The Gist

Imagine you are the security chief of a massive, bustling city. Your job is to keep the city safe from thieves, vandals, and saboteurs. To do this, you rely on two very different tools, but unfortunately, they don't talk to each other very well.

This paper is about finally getting these two tools to hold hands, dance together, and work as a single, super-smart security team.

The Two Tools: The Alarm System and The Blueprint

1. The Alarm System (The IDS)
Think of the Intrusion Detection System (IDS) as the city's thousands of motion sensors and cameras.

• How it works: It screams "ALERT!" every time it sees something weird, like a shadow moving in an alley or a window breaking.
• The Problem: It screams too much. It gets confused by a cat walking by, a strong wind, or a stray dog. It produces a mountain of "False Alarms." The security team is so overwhelmed by noise that they miss the real burglars hiding in the crowd.

2. The Blueprint (The Attack Graph)
Think of the Attack Graph (AG) as a giant, complex blueprint of the city. It doesn't just show buildings; it shows how a thief could get from the park, through the sewer, into the bank vault. It maps out every possible path a criminal could take.

• How it works: It helps you plan defenses. "If we lock the sewer grate, the thief can't get to the bank."
• The Problem: The blueprint is static. It shows every possible path, even ones that are impossible in real life (like a thief flying). It's too big and too slow to update in real-time. If a new hole appears in the wall, the blueprint doesn't know about it until someone manually redraws it.

The Current Situation: They Ignore Each Other

Right now, most security teams use these tools separately.

• The Alarm System screams at everything, and the team gets tired.
• The Blueprint sits on a shelf, showing all the theoretical ways to break in, but it doesn't know what's actually happening right now.

Some researchers have tried to make them talk. Sometimes they use the Blueprint to tell the Alarm System, "Ignore that shadow, it's just a cat." Other times, they use the Alarm System to say, "Hey, update the Blueprint, someone actually tried to break in through the sewer!"

But the paper argues that these attempts are like two people talking through a wall. They are "fragmented." They fix one small problem but don't create a true partnership.

The Big Idea: A "Living" Security Cycle

The authors propose a new way to think about this: The AG-IDS Lifecycle.

Imagine instead of a static blueprint and a noisy alarm, you have a living, breathing security organism.

1. The Feedback Loop:

   • The Alarm System spots a weird noise.
   • Instead of just screaming, it whispers to the Blueprint: "Hey, check the sewer path. I think someone is there."
   • The Blueprint instantly updates, realizing, "Oh! The sewer grate is open. That path is now real."
   • The Blueprint then tells the Alarm System: "Okay, now I know the sewer is a real threat. From now on, if you hear a noise in the sewer, treat it as a 100% emergency, not a cat."

2. The Cycle of Improvement:

   • The Blueprint gets smarter because it learns from real alarms.
   • The Alarm System gets quieter and more accurate because it learns from the Blueprint's logic.
   • They repeat this forever. Every time a new threat appears, they learn from it, update each other, and get better at catching the next one.

The Experiment: Proving It Works

The authors didn't just talk about this; they built a "proof of concept" (a prototype). They simulated a network attack using real data.

• Without the partnership: The security system was slow, missed things, or got confused by too many false alarms.
• With the partnership: The system became a "smart filter." It ignored the noise (false alarms) and focused only on the paths that actually made sense based on the Blueprint.
• The Result: They found that by letting the two tools talk to each other continuously, they could detect attacks faster, make fewer mistakes, and even figure out the risks of specific parts of the network more accurately.

Why This Matters

Think of it like a GPS and a Driver.

• Right now, the Driver (IDS) is driving fast but getting lost in traffic, and the GPS (AG) is showing a map of roads that might not even exist anymore.
• This paper suggests a new car where the Driver and GPS talk constantly. The Driver says, "There's a roadblock!" and the GPS instantly recalculates the route and tells the Driver, "Okay, take the next left, and watch out for the pothole on that new road."

The Takeaway

This paper is a call to action. It says: "Stop treating your security alarms and your security plans as separate things. Build a system where they constantly learn from each other."

By creating this continuous loop, we can move from a security system that is reactive (screaming after the fact) to one that is adaptive and intelligent, capable of predicting and stopping cyber-attacks before they even succeed. It's the difference between a security guard with a clipboard and a security guard with a supercomputer brain.

Technical Summary

Here is a detailed technical summary of the paper "SOK: Harmonizing Attack Graphs and Intrusion Detection Systems."

1. Problem Statement

The paper addresses the critical challenge of detecting and responding to complex, multi-stage cyber attacks in high-volume network environments. While Intrusion Detection Systems (IDSs) are effective at identifying individual anomalous behaviors, they often struggle with:

• False Positives: High volumes of traffic lead to alert fatigue.
• Lack of Correlation: Inability to link isolated alerts across different nodes to reconstruct a full attack campaign.
• Contextual Blindness: Difficulty in understanding the strategic intent of an attacker.

Conversely, Attack Graphs (AGs) provide a comprehensive threat model that maps vulnerability exploits and potential attack paths, aiding in response planning and risk assessment. However, AGs suffer from:

• Scalability Issues: The combinatorial explosion of possible attack paths makes real-time generation difficult.
• Static Nature: Traditional AGs often fail to adapt to dynamic, real-time network changes.

The Core Gap: Despite early recognition of the synergy between IDSs and AGs, current research is fragmented. Existing integrations are typically unidirectional (e.g., using IDS alerts to prune AGs, or using AGs to filter IDS alerts) and static (one-time configuration). There is a lack of a unifying, continuous framework that treats IDS and AG as a cohesive, adaptive system capable of iterative refinement.

2. Methodology

The authors conducted a Systematization of Knowledge (SoK) involving a rigorous review of 73 primary research papers selected from a pool of 102 initial articles.

• Search Strategy: Queries were executed across major bibliographic databases (ACM, IEEE, Springer, etc.) using keywords related to "intrusion detection," "attack graphs," "anomaly detection," and "alert correlation."
• Selection Criteria: Papers were included only if they explicitly described the integration of AGs and IDSs, detailing specific detection engines, AG models, and integration objectives.
• Taxonomy Development: Based on the research questions (RQ1: How are they coupled? and RQ2: To what end?), the authors developed a novel taxonomy categorizing approaches into four distinct types:
  1. AG|IDS (IDS-based AG Generation): Using IDS outputs (alerts) to construct or update Attack Graphs.
  2. IDS[AG] (AG-integrated IDS): Embedding AG knowledge directly into the IDS detection pipeline to optimize rules or runtime detection.
  3. IDS → AG (AG-based IDS Refinement): Using pre-existing AGs to validate, filter, or refine IDS alerts (e.g., reducing false positives).
  4. Hybrid Approaches: Combining two or more of the above categories.

3. Key Contributions

A. Comprehensive Taxonomy and Analysis

The paper provides the first systematic categorization of AG-IDS integration. Key findings from the analysis of 73 papers include:

• Dominance of Unidirectional Flows: Most research focuses on isolated problems (e.g., just reducing false positives or just generating graphs) rather than holistic integration.
• Technology Bias: There is a heavy reliance on Network-based IDS (NIDS) and Signature-based IDS (SIDS) because their deterministic outputs map easily to AG nodes. Anomaly-based IDS (AIDS) and Host-based IDS (HIDS) are underutilized due to semantic gaps.
• Data Limitations: The field suffers from a lack of realistic datasets. Many studies rely on outdated datasets (e.g., DARPA2000) or synthetic simulations, limiting real-world applicability.
• ML Underutilization: While Machine Learning (ML) is used, it is often limited to simple models (Bayesian Networks, Markov Chains). Advanced Graph Neural Networks (GNNs) and Neuro-Symbolic approaches are largely unexplored despite their suitability for graph-structured data.

B. The Proposed AG-IDS Lifecycle

To address the fragmentation and static nature of current solutions, the authors propose a continuous AG-IDS Lifecycle. This framework establishes a bidirectional feedback loop:

1. IDS Refines AG: IDS alerts are used to dynamically generate or prune AGs, focusing only on relevant, active attack paths (improving scalability).
2. AG Refines IDS: Updated AG models are fed back into the IDS to adjust detection rules, validate alerts, and reduce false positives (improving accuracy).
3. Iterative Adaptation: The system continuously updates both the vulnerability database and the detection models, allowing for prompt responses to emerging threats (e.g., zero-days).

C. Proof-of-Concept Implementation

The authors implemented a proof-of-concept (PoC) using the CIC-IDS2017 dataset to validate the lifecycle.

• Setup: A Decision Tree (DT) classifier served as the IDS, integrated with an AG generated from "Emerging Threats" rules.
• Experiments: They tested three phases:
  1. AG|IDS: Generating AGs based on IDS alerts.
  2. IDS[AG]: Injecting AG path existence as a feature into the IDS.
  3. IDS → AG: Using AGs to post-process and flip false positive predictions.

4. Results

The experimental results demonstrated significant performance improvements across the lifecycle iterations:

• Scalability (AG|IDS):

  • Classical AG generation produced 11,842 attack paths (computation time: 32.23s).
  • IDS-based AG generation produced only 360 paths (computation time: 0.37s), focusing only on exploited vulnerabilities.
  • Finding: IDS-driven generation is significantly more efficient and context-aware.

• Detection Accuracy (IDS[AG]):

  • Integrating AG path information into the IDS improved Accuracy and F1-score by ~1.4% and reduced False Positive Rate (FPR) by ~1.26%.
  • Gains were most pronounced when training data was limited or features were unreliable, proving the AG acts as a strong structural prior.

• Refinement (IDS → AG):

  • Using AGs to validate IDS predictions reduced FPR by ~1.27%.
  • The refinement was most effective when the underlying IDS had a reasonable baseline performance, confirming that AGs act as a "sanity check" for structural feasibility.

• Robustness: The lifecycle maintained performance gains even with degraded AG quality (randomly added paths), though optimal results were achieved with tailored, high-quality AGs.

5. Significance and Future Directions

This paper is significant because it moves the field from fragmented, static integrations to a dynamic, holistic lifecycle.

• Theoretical Impact: It establishes a unified taxonomy and identifies the "missing link" in current research: the lack of continuous, bidirectional adaptation.
• Practical Impact: The PoC proves that integrating AGs and IDSs is not just theoretically sound but practically viable, offering tangible improvements in scalability (faster graph generation) and accuracy (lower false positives).
• Future Opportunities: The authors outline several critical research directions:
  • Neuro-Symbolic AI: Combining symbolic AG reasoning with neural learning for interpretable, adaptive detection.
  • Dataset Standardization: Creating comprehensive datasets that include both network traffic and vulnerability inventories.
  • Multi-Source Integration: Moving beyond single IDS/AG sources to handle complex, multi-layered enterprise environments (e.g., Cloud, IoT, SCADA).
  • Automation: Leveraging tools like LangChain for agentic systems to automate TTP (Tactics, Techniques, and Procedures) mapping.

In conclusion, the paper argues that the future of network security lies in harmonizing detection (IDS) and modeling (AG) into a self-improving loop, rather than treating them as separate, static tools.