PaperlayerView exact revision on arXiv

Source-linked AI summary

Automating Attack Graph Construction for Agentic Pentesting. Towards Neuro-Symbolic Vulnerability Hunting

Oliver Stevanovic, Jasmin Wachter

arXiv:2609.15523v1cs.CRcs.AI

TL;DR

LLM-agent decisions are often grounded in unstructured prompts or transcripts, while integrating MulVAL with contemporary scanners requires translating findings into predicates and creating domain-specific rules. A semi-automated pipeline translates scanner evidence into MulVAL facts, uses LLM assistance to construct domain-specific rules, and runs MulVAL/XSB inference to generate attack paths. Every task produced a goal-reaching graph, and the mean noise path percentage was 83.9%.

  • Problem

    LLM-agent decisions are often grounded in unstructured prompts or transcripts, while integrating MulVAL with contemporary scanners requires translating findings into predicates and creating domain-specific rules.

    Source: §1 · pp. 1–2

  • Method

    A semi-automated pipeline translates scanner evidence into MulVAL facts, uses LLM assistance to construct domain-specific rules, and runs MulVAL/XSB inference to generate attack paths.

    Source: §1 · p. 2, §3 · p. 4

  • Results

    Every task produced a goal-reaching graph, and the mean noise path percentage was 83.9%.

    Source: §6 · p. 8

  • Takeaways & Limitations

    The results establish graph-construction feasibility, but the current graphs are not yet reliable enough for unqualified downstream agentic guidance.

    Source: §6 · p. 8

    The study evaluates graph-construction infrastructure, not whether graph guidance improves agent performance, and aggregate results do not identify errors in individual rules or components.

    Source: §1.1 · p. 3, §7 · p. 10

Abstract

from arXiv · show

Logic attack graphs grounded in scanner output provide explicit and auditable attack path reasoning LLM-based agents lack. Integrating symbolic frameworks such as MulVAL to contemporary security workflows or agentic pipelines, however, requires translating scanner evidence to initial facts, and creating domain-specific rules. We present a semi-automated pipeline that addresses this interoperability problem and depict its feasibility in a web-security case study. Our pipeline parses findings from Trivy, Semgrep, and Nmap into MulVAL predicates and uses an LLM-assisted process to construct domain-specific Datalog rules linking scanner-detectable evidence to attack techniques. MulVAL/XSB then performs symbolic inference to generate structured attack paths. We evaluate the attack-graph construction infrastructure on 54 web Capture-the-Flag tasks from CyBench within an agentic pipeline (Hybrid Reasoner); we do not evaluate the performance of the downstream agent. Every task produced at least one goal-reaching graph, and we achieve mean ground-truth vulnerability coverage of 53.7%, with 51.9% achieving full coverage; mean noise-path rate was 83.9%. With median end-to-end time of 24.9 s (MulVAL reasoning: 2.7 s) the pipeline is feasible and runtime-practical for agentic workflows, but predicate coverage, rule coverage, and path precision remain limiting factors. Next steps include semantic rule validation and agent-level comparison for graph-guided pentesting.

1 Introduction

The paper addresses the gap between unstructured, difficult-to-audit LLM-agent reasoning and symbolic attack graphs that can represent attack paths explicitly. It presents a semi-automated scanner-to-MulVAL pipeline and evaluates graph construction on web-security tasks, not downstream agent performance.

1 Introduction

  • Scanner findings do not directly instantiate MulVAL predicates, and generic rules may miss domain-specific attack patterns, making integration manual and difficult to maintain.The authors identify this interoperability problem as an obstacle to testing symbolic attack graphs in agentic environments.Source: §1 · p. 2
  • The pipeline translates scanner findings into MulVAL facts, uses LLM assistance to construct domain-specific Datalog rules, and invokes MulVAL/XSB to derive structured attack paths.A two-layer predicate architecture links scanner-detectable evidence to higher-level attack techniques.Source: §1 · p. 2, §1.1 · p. 3

1.1 Research Question and Contribution

  • The case study grounds its web-security customization in OWASP Top 10 vulnerabilities and the MITRE ATT&CK framework.The paper presents this as a proof-of-concept vulnerability-hunting pipeline.Source: §1.1 · p. 2
  • On 54 CyBench web tasks, every task produced a goal-reaching graph, but mean vulnerability coverage was 53.7% and mean noise-path rate was 83.9%.The evaluation measures reachability, vulnerability fidelity, path noise, and generation time.Source: §1.1 · p. 2
  • The study evaluates graph construction infrastructure only; it does not establish that graph guidance improves agent performance, exploitation success, efficiency, safety, or reasoning quality.A controlled comparison of unguided, scanner-guided, and graph-guided agents is left for future work.Source: §1.1 · p. 3

2 Related Work and Concepts

The paper situates its work within logic attack graphs, LLM-to-logic translation, and agentic penetration testing. Its focus is the customization layer that connects heterogeneous scanner evidence to MulVAL, rather than a new graph formalism or an evaluation of agent performance.

2 Related Work and Concepts

  • MulVAL builds attack graphs by combining a Datalog fact base with exploit rules and using XSB symbolic deduction to derive attack paths.Facts encode configurations, vulnerabilities, and hosts; rules encode attacker behavior and privilege escalation.Source: §2 · p. 3
  • Adapting MulVAL to contemporary scanners remains substantial engineering work because findings vary in abstraction and require stable predicates and connecting rules.The paper translates Trivy, Semgrep, and Nmap findings while retaining MulVAL/XSB rather than introducing a new formalism or reasoning algorithm.Source: §2 · p. 3
  • Prior language-model-to-logic studies examine Datalog or ASP translation, while this paper evaluates security-specific attack graphs against task vulnerability annotations.The accuracy of generated security rules is deferred to future work.Source: §2 · p. 3
  • Incalmo separates high-level planning from execution, but leaves open the benefit of symbolic attack reasoning and graph construction from heterogeneous vulnerability evidence.The cited analysis reports problems including irrelevant actions, execution errors, lost asset tracking, and context bloat in long-horizon settings.Source: §2 · pp. 3–4
  • Related attack-modeling systems use CTI-derived planning structures or knowledge-graph entailment, whereas this work connects scanner evidence to MITRE ATT&CK techniques through MulVAL.The pipeline evaluates graph-construction feasibility, not whether graph guidance improves agent performance; manual rule inspection and predicate deduplication were performed.Source: §2 · p. 4

3 Framework Architecture

The framework separates offline construction of a hierarchical MulVAL knowledge base from runtime attack-graph generation. It combines ATT&CK-level rules, scanner-grounded rules, and correlated scanner evidence, while formal rule validation remains out of scope.

3 Framework Architecture

  • The architecture separates offline rule and fact generation from runtime graph generation and agent integration.The pipeline is intended to connect scanner sources to MulVAL and provide structured attack-path guidance to an agent.Source: §3 · p. 4
  • Formal validation of generated rules is out of scope, although attack-graph quality depends on their syntactic and semantic correctness.The architecture also notes that agentic performance evaluation is pending.Source: §3 · p. 4

3.1 MulVAL Rule Generation and Customization Pipeline

  • MITRE ATT&CK techniques provide an abstract strategic layer, while a customizable second layer grounds transitions in scanner-detectable evidence.Connector predicates link findings such as endpoint exposure, weakness class, and attacker reachability to higher-level rules.Source: §3.1 · pp. 5–6

3.2 Top-Level Rule Generation Pipeline (MITRE ATT&CK)

  • The top-level rule pipeline reviews an ATT&CK-derived predicate vocabulary, generates one rule per technique with an LLM pipeline, then merges rules and registries into a knowledge base.The vocabulary is human-reviewed; predicate additions are restricted, and memoization directives help prevent pathological derivation chains in cyclic graphs.Source: §3.2 · p. 6
  • The second rule layer bridges concrete scanner findings to higher-level ATT&CK transitions through application-specific predicates and connector rules.This layer is designed to make the rules customizable and interoperable with network and vulnerability scanner outputs.Source: §3.2 · p. 6

3.3 Populating the Initial Facts — A Unified Pipeline

  • The UnifiedPipeline collects scanner evidence, correlates network and vulnerability findings, then synthesizes normalized evidence into MulVAL predicates for the initial fact base.In the web case study, Trivy and Semgrep findings are normalized into predicates covering topology, exposed services, vulnerability evidence, and web context.Source: §3.3 · p. 6

4 Attack Graph Generation and Agentic Integration

The runtime component uses MulVAL/XSB to derive attack graphs from the unified predicates and rules, then parses derivations into structured paths. The graphs are intended as context for a customized CAI Red Team agent, but the paper evaluates the graph-generation infrastructure rather than the agent.

4 Attack Graph Generation and Agentic Integration

  • MulVAL goal generation supplements generic compromise goals with service-specific goals when discovered, focusing reasoning on relevant paths.This is intended to avoid exhaustive reachability graphs.Source: §4 · p. 6
  • MulVAL/XSB evaluates the unified predicates and interaction rules, and the resulting derivation trace is parsed into structured attack paths.Each path contains ordered base facts and rule applications that provide logical justification for its edges.Source: §4 · pp. 6–7
  • The structured output includes path totals, attack goals, target host, and individual paths with ordered, justified steps.The rule-generation pipeline employed Claude Opus 4.5 and GPT-4o, while its methodology is described as LLM-agnostic.Source: §4 · pp. 6–7
  • The Hybrid Reasoner is a customized CAI Red Team agent instructed to use attack-graph information, but only graph-generation infrastructure is empirically evaluated.A full analysis of the Hybrid Reasoner is out of scope.Source: §4 · p. 7

5 Proof-of-Concept — Evaluation Methodology

The evaluation runs the symbolic pipeline on 54 web-oriented CyBench tasks with manually assigned ground-truth vulnerability classes. It measures goal reachability, vulnerability fidelity and path noise, and runtime cost across sequential scanner, inference, and trace-parsing stages.

5 Proof-of-Concept — Evaluation Methodology

  • The evaluation corpus contains 54 web tasks from CyBench, spanning static and live deployments, with manually inspected ground-truth vulnerability annotations.Tasks come from the hkcert-ctf and project-sekai-ctf collections.Source: §5 · p. 7
  • Each benchmark run times scanner and predicate generation, MulVAL reasoning, and trace parsing as sequential stages.The resulting paths are evaluated for goal reachability, vulnerability fidelity, path noise, and wall-clock generation time.Source: §5 · p. 7
  • The evaluation measures whether inference reaches a goal, how faithfully paths represent required vulnerability classes, how many paths are unrelated, and execution time.Table 2 is identified as the benchmark evaluation metrics table.Source: §5 · p. 7, Table 2 · p. 7

6 Results and Discussion

Across 54 web CTF tasks, the pipeline generated goal-reaching graphs in every task, but ground-truth coverage and path precision remained limited. Runtime was modest, and the authors conclude the graphs are not yet reliable for unqualified downstream agent guidance.

Results

  • Every task in the corpus produced at least one goal-reaching graph, indicating that each had an executable goal derivation.Goal reachability establishes graph creation, not that a graph contains the vulnerabilities needed to solve the task.Source: §6 · p. 8
  • Median end-to-end pipeline time was 24.9 s, compared with 2.7 s for MulVAL reasoning.Input predicate generation dominated wall-clock time; scanner information retrieval, particularly Nmap's port and software-version checks, was the bottleneck.Source: §6 · p. 8
  • 28 of 54 tasks (51.9 %) achieved full vulnerability coverage, while 24 (44.4 %) had zero coverage; mean noise path percentage was 83.9%.Coverage is measured against ground-truth vulnerability annotations; noise paths are relative to those annotated classes.Source: Table 3 · p. 8, §6 · p. 8
  • Only one of the four multi-vulnerability tasks achieved full coverage, including CTF-2023/15-wishlist, which requires XSS and SSRF.The chunky task's request_smuggling and cache_poisoning classes were not modeled with sufficient rule specificity; two other tasks achieved partial coverage.Source: Table 4 · p. 8, §6 · p. 8

Discussion

  • The authors conclude that lower vulnerability coverage and high path noise make the graphs insufficient for unqualified downstream agent guidance, despite consistent derivations and modest runtime.They identify semantic rule validation and agent-level comparison as future work.Source: §6 · p. 8
  • Potential applications include structured attack hypotheses for planning in safety-constrained OT settings and support for traditional network hardening.The paper presents these as potential uses, not evaluated outcomes.Source: §6 · pp. 9–10

7 Conclusion

Every task reached a compromise goal, but vulnerability coverage and path relevance remained limited. The authors identify rule and input quality, component attribution, and agent-level evaluation as areas for further work.

7 Conclusion

  • Every task reached a compromise goal, but lower vulnerability coverage and high path noise show that reachability alone is insufficient.Errors may arise from missed scanner evidence, parser mapping problems, incomplete rules, or irrelevant executable paths.Source: §7 · p. 10
  • The pipeline’s effectiveness depends on rule and input-predicate quality, and component-level activation and provenance analysis is needed before graphs can be treated as reliable guidance.The aggregate evaluation does not yet attribute errors to individual rules or components.Source: §7 · p. 10
  • The authors propose comparing agents given no graph, raw scanner output, or structured attack graphs to assess effects beyond vulnerability hints.Suggested measures include pass@3, token efficiency, tool calls, dead-end actions, and adherence to exploitable paths.Source: §7 · p. 10
  • Future work targets noisy, incomplete scanner output and limited rule coverage through better predicates and broader attack-pattern coverage.The authors also propose failure attribution, evaluating small language models for rule generation and validation, and standardized tool integration.Source: §7 · p. 10

Use of AI

The authors report LLM and coding-agent use, list author contributions, and declare no relevant competing interests.

Use of AI

  • LLMs generated domain-specific MulVAL rules from natural-language attack descriptions, with all outputs manually reviewed by the authors.Coding agents assisted software development, and LLMs supported manuscript preparation.Source: Use of AI · p. 11

CRediT Author Contributions

  • Stevanovic contributed investigation, validation, methodology, software, and writing; Wachter contributed conceptualization, methodology, supervision, software, and writing.Both authors are credited with original drafting, review, and editing.Source: CRediT Author Contributions · p. 11

Competing Interests

Loading 2609.15523v1…