Automated Post-Exploitation Attack Chain Exploration Based on a Phase-guided Hybrid Planning-Monte Carlo Tree Search Algorithm

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

1

Automated Post-Exploitation Attack Chain Exploration Based on a Phase-guided Hybrid Planning-Monte Carlo Tree Search Algorithm

arXiv:2610.32278v1 [cs.CR] 23 Oct 2026

Jie Ying, Mengce Zheng, Ruoxi Chen, Wenrui Cheng, Tiantian Zhu, Zhongjie Zhu*

Abstract—Advanced attackers in post-exploitation scenarios increasingly craft attack chains that combine benign operations, configuration errors, and vulnerability exploitation to achieve objectives like privilege escalation. While such chains pose significant threats, manually discovering them in complex modern host environments is prohibitively labor-intensive. Automating this discovery is therefore essential for proactive defense, yet existing methods still suffer from inefficiency and lack diversity when exploring these attack chains. To address these limitations, we present APEX, an Automated Post-EXploitation attack chain exploration system. This system transforms attack chain discovery into a planning problem and solves it with a novel phase-guided hybrid Planning-Monte Carlo Tree Search (MCTS) algorithm. By organizing attack actions into semantic phases and integrating symbolic planning with MCTS, APEX enables efficient exploration of the state space while generating multiple diverse chains. Evaluations on a benchmark comprising 5 virtual machines, 30 synthetic problems and 291 cloud instances demonstrate that APEX successfully discovers both known and previously unreported attack chains—including 9 novel privilege escalation vectors—providing actionable intelligence for hardening complex production environments. Index Terms—Attack Chain Exploration, Post-Exploitation Attack, AI Planning, Monte Carlo Tree Search Algorithm.

I. I NTRODUCTION Over the past decades, to prevent potential attackers from exploiting software vulnerabilities to compromise systems, security researchers have proposed numerous techniques for automated software vulnerability detection, such as static analysis [1], [2], dynamic analysis [3], [4], [5], [6], [7], and hybrid analysis [8], [9]. However, not all vulnerabilities can be exploited by attackers to gain control of a system. The Forum of Incident Response and Security Teams (FIRST) [10] proposed the Common Vulnerability Scoring System (CVSS) [11] which evaluates and classifies vulnerabilities. Among these, only vulnerabilities rated as critical (scoring range: 9.0–10.0) This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible. This work is supported in part by the following grants: National Natural Science Foundation of China under Grant 62002324. Zhejiang Provincial Natural Science Foundation of China under Grant No. LQ21F020016. The Fundamental Research Funds for the Provincial Universities of Zhejiang under Grant No. RF-A2023009. Key Program of Zhejiang Province Natural Science Foundation (LZ24F010004), Zhejiang Provincial ”Pioneer, Leader+ X” Science and Technology Program (2026C02A1221), The 14th China Innovation and Entrepreneurship Competition-Innovation Challenge (Ningbo). J. Ying, M. Zheng, R. Chen, and Z. Zhu* are with the College of Information and Intelligent Engineering, Zhejiang Wanli University, Ningbo 315100, China. E-mail: yingjie@zwu.edu.cn, mczheng@zwu.edu.cn, chenruoxi@zwu.edu.cn, zhongjiezhu@hotmail.com*, *corresponding author. T. Zhu and W. Cheng are with the College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China. E-mail: ttzhu@zjut.edu.cn, zjutcwr@zjut.edu.cn.

can be remotely exploited without user interaction and have widespread impact. According to reports [12], only 13.7% of vulnerabilities were marked as critical. In addition, there are many techniques such as Control Flow Integrity (CFI) [13], Address Space Layout Randomization (ASLR) [14], and Shadow Stack [15] to restrict attackers from exploiting vulnerabilities. Consequently, attackers in post-exploitation scenarios—after gaining initial access with limited privileges—increasingly rely on multi-step attack chains that intertwine benign system operations and malicious actions to achieve phased objectives such as privilege escalation and lateral movement. For example, an attacker might chain configuration enumeration, malicious library crafting, environment variable manipulation, and execution of a misconfigured binary to escalate to root privileges. Post-exploitation attack chains exhibit three distinctive characteristics: multi-phase progression, target-specific precision, and high operational efficiency. By executing these carefully orchestrated chains, attackers can rapidly expand their operational capabilities and achieve specific objectives. Conversely, defenders can leverage intelligence about these chains to rectify system misconfigurations and deploy software patches promptly. Undoubtedly, these realities highlight the critical necessity for implementing automated post-exploitation attack chain discovery at the host level. Currently, the identification of post-exploitation attack chains remains a manual process. The inherent complexity of modern operating systems and executable environments makes the task of discovering these attack chains both technically challenging and time-consuming [16], [17], [18]. Researchers have discovered that the permission configurations, library file loading mechanisms, and process capabilities of a host system can be formally modeled, allowing the task of attack chain discovery to be equivalently transformed into a feasible solution search task within the planning domain. Meanwhile, planning algorithms have demonstrated significant effectiveness in the field of network attack simulation and modeling [19], [20], [17], [21], leading researchers to explore their application in solving attack chains discovery [18], [22]. However, integrating host modeling with planning algorithms for post-exploitation attack chain discovery currently faces three significant challenges: (1) Modeling Imprecision: Existing approaches typically model hosts as single nodes with attributes (e.g., OS, vulnerabilities, users) [16], [23], but this coarse-grained representation fails to capture an attacker’s evolving capabilities during post-exploitation phases accurately. (2) Computational Inefficiency: The complexity of host environments results in a huge search space after

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

modeling. Given attackers’ limited dwell time on compromised systems [24], conventional planners often cannot generate viable solutions within operationally relevant time constraints. (3) Solution Inflexibility: Traditional planning solvers employ satisficing strategies that terminate upon finding any feasible solution [25], [26], [27], [28]. Even when configured for optimal planning (minimizing action steps) [29], these systems cannot provide alternative paths when operational constraints (e.g., failed vulnerability exploitation or file access restrictions) render the primary solution unimplementable. To address these issues and achieve rapid, feasible, and flexible attack chain exploration, we propose APEX, an Automated Post-EXploitation attack chain exploration system. In essence, APEX formulates attack chain exploration as an AI planning problem: given the current state of a host (e.g, treestructured file system, user-group relationships, and specific versions of executable binaries) along with a defined goal (e.g., reading a particular file or escalating to a specific user’s privileges), it generates a sequence of actions (i.e., attack chain) to achieve the objective. Specifically, we first heuristically define Objects (e.g., files, users, groups, and permissions), Facts (e.g., file readability, user-group membership), and Actions (e.g., executing binaries, modifying file permissions) involved in post-exploitation. This process, known as domain modeling in AI planning, utilizes a formal language to precisely describe the static structure and dynamic possibilities of the target, serving as a prerequisite and universal procedure. Subsequently, with low privileges (common in post-exploitation phases), APEX automatically retrieves relevant information from the target host and generates a formal host characterization file. Then, based on observed phased characteristics in postexploitation behaviors, we propose a phase-guided hybrid planning-MCTS algorithm. Given the characterization file and a specific objective, APEX leverages this algorithm to solve for multiple feasible action chains within the solution space. Finally, we employ a Large Language Model (LLM) to translate the formally described attack chains into natural language reports, providing targeted remediation suggestions to assist security analysts in identifying potential attack vectors and reinforcing critical system components. For example, if an attacker escalates privileges by executing a misconfigured binary, defenders can proactively adjust its permissions to mitigate potential exploit risks. In this paper, we make the following contributions: • We conduct domain modeling for post-exploitation phases using formal language to describe static structures and dynamic capabilities while maintaining minimalism in the domain model to enhance subsequent planning efficiency. • We propose a phase-guided hybrid Planning-Monte Carlo Tree Search (MCTS) algorithm that leverages the phased nature of post-exploitation behaviors, combining the efficiency of AI planning with the flexibility of MCTS to enable efficient and flexible attack chain exploration. • We implement a prototype of APEX and evaluate it on a benchmark comprising 5 virtual machines with known privilege escalation vulnerabilities and 30 synthetic prob-

2

lems, followed by large-scale real-world assessments on 291 live cloud instances, uncovering 9 unreported attack chains. II. BACKGROUND A. Post-Exploitation in Cyber Attacks Post-exploitation activities occur after initial system compromise, focusing on maintaining access, escalating privileges, moving laterally, and achieving objectives while evading detection. In sophisticated attacks like APTs, this phase involves orchestrating multi-step chains that blend malicious actions with legitimate system interactions (e.g., abusing sudo, cron, or environment variables). These chains exploit complex host environments (permissions, services, configurations), making automated exploration crucial for defense. Our work focuses on automatically generating such attack chains from a constrained initial foothold. For a detailed analysis of the relationship with the MITRE ATT&CK framework and specific attack vectors, see Appendix A. B. AI Planning We model post-exploitation as a classical AI planning problem: finding a sequence of actions that transforms an initial system state (compromised host) into a goal state (e.g., root access). We use the Planning Domain Definition Language (PDDL) to formally describe the domain (system objects, facts, actions) and problem (concrete host state, attacker goal). A planning solver then searches for valid action sequences (plans). However, the state space for real systems is vast, and planning from scratch for every variation is computationally expensive. The formal definition of the planning problem and details of our PDDL domain specification are provided in Appendix B. C. Monte Carlo Tree Search To efficiently navigate the large state space, we leverage Monte Carlo Tree Search (MCTS). MCTS builds a search tree through iterative sampling (selection, expansion, simulation, backpropagation), balancing exploration and exploitation. Its anytime nature suits time-constrained scenarios. Our key insight is to hybridize MCTS with planning: we use phasebased heuristics to guide MCTS’s action selection and employ a planner to dynamically generate feasible actions within each phase, dramatically reducing enumeration overhead (which dominates runtime in naive approaches, approximately 91%). This hybrid approach enables the efficient discovery of diverse and concise attack chains. III. M OTIVATION & T HREAT M ODEL A. Motivation Modern post-exploitation attacks increasingly rely on intricately chaining together seemingly benign system operations with pivotal malicious exploits to form complex attack chains. Successful compromise is rarely the result of a single vulnerability; instead, attackers must strategically combine system misconfigurations, software vulnerabilities,

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

and legitimate operations in specific sequences that create paths to critical security objectives (e.g., root access). One representative example is a chain combining cron misconfigurations, a vulnerable binary, and file manipulation to reach root privileges. A detailed walkthrough of this example is provided in Appendix C. Manually discovering these multi-vector chains requires analysts to mentally traverse a vast state space, connecting disparate system attributes (scheduled tasks, binary versions, permissions, etc.) through non-obvious causal relationships. The challenge is magnified by the scale of modern environments—hundreds of software packages, numerous services, and complex permission hierarchies—creating a state space with millions of possibilities. Existing automated tools are often ill-suited to reason about these complex, stateful chains that blend legitimate and malicious operations. The operational necessity for automated attack chain exploration is clear. Advanced Persistent Threats (APT) increasingly employ techniques that combine legitimate system functionalities (”Living-off-the-Land”) with precise exploitation. Proactive defense therefore demands tools capable of proactively discovering such multi-step vectors before they are weaponized. For practitioners, this capability enables preventative hardening through systematic patching, configuration changes, and permission adjustments. B. Threat Model Our threat model centers on the post-exploitation phase, where an attacker has already gained initial shell access (e.g., as a low-privileged user) on a Unix-based system. The core objective of this work is to automatically explore feasible attack chains that allow the attacker to achieve a specified goal from this initial state, such as privilege escalation, file tampering, data exfiltration, or lateral movement. The attacker can leverage existing system utilities for reconnaissance and is capable of executing actions based on discovered information. While the attacker can introduce external tools if a method is found, they do not initially possess other users’ credentials, ruling out straightforward authenticationbased escalation. We focus exclusively on full-fledged Unix systems with init systems (e.g., systemd). This is because init systems provide a complex landscape of persistent services, scheduled tasks, and environment configurations that are essential for constructing realistic, multi-step attack chains. Consequently, containerized environments are excluded from our scope, as their isolated nature and ephemeral lifecycle present fundamentally different security boundaries and attack surfaces, which limits the applicability and relevance of the intricate chains our system aims to discover. IV. OVERVIEW &P RINCIPLE A. The APEX Architecture APEX adopts a static-dynamic architecture that systematically integrates static domain knowledge with dynamic hostspecific information for automated attack chain discovery in the post-exploitation phase. As illustrated in Figure 1, the

3

architecture comprises two complementary layers: a Static Layer and a Dynamic Layer. The static layer contains the reusable domain model, readonly extraction scripts, and the hybrid Planning-MCTS solver. The dynamic layer applies these components to a target host through three stages: collecting security-relevant host information, parsing the result into a host-specific PDDL problem, and solving for feasible attack chains that are finally translated into analyst-facing reports. This separation keeps domain knowledge reusable while adapting the instantiated problem to each target. This architecture ensures a clear separation of concerns: the static components encapsulate domain knowledge and solving strategies, while the dynamic layer adapts this framework to a specific Unix-like environment, generating human-readable security reports. B. Core Design Principles APEX follows four design principles: (1) Formal Abstraction: Distilling system complexity into a precise PDDL model ensures logical soundness. (2) Phase-Guided Search: Incorporating post-exploitation phases with specific constraints improves search efficiency. (3) Hybrid Solving: Combining symbolic planning with probabilistic MCTS balances feasibility and diversity. (4) Minimal Interference: Strict readonly operations ensure passive, safe assessment. Together, these principles guide the modeling, collection, and solving components of APEX. Extended explanations of the four principles and their implementation implications are provided in Appendix D. V. S YSTEM D ESIGN AND M ODELING APEX follows a model-first design approach: we first define the formal domain model (Section V-A and Section V-B), then create scripts to instantiate it (Section V-C), and finally develop the hybrid solver algorithm (Section VI). This ensures every collected piece of information serves a defined purpose in planning. A. Modeling Philosophy and Scope Our modeling philosophy is centered on sufficiency and minimalism: the model must capture realistic post-exploitation chains while remaining compact enough for tractable planning. We therefore model a minimal sufficient set of attack surfaces: file-system permissions and ownership, process execution and privilege inheritance, automated execution mechanisms, dependency relationships, software vulnerabilities, user/group relationships, and data movement capabilities. A naive model that attempts to capture every system detail would lead to a combinatorial explosion in the state space, rendering automated planning infeasible. Conversely, an overly simplistic model would fail to capture the nuanced interactions that constitute real attack chains. Our modeling approach navigates this tension by adhering to a core principle: model only the entities and relationships that are both necessary and sufficient for achieving objectives through the chaining of benign and malicious actions.

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

Dynamic Layer

4

B. Parsing

C. Solving

Collect Information

Generate Formal File

Solve the Problem

Initial Access

Set Specific Goal

Convert to Report

A. Collecting

Target Host (Low-privilege)

Static Layer

Attacker (or Defender)

Automation Script

Problem File

Domain Model

Goal

Hybrid Algorithm

Solution LLM

Fig. 1: APEX System Architecture.

We identify and model the following core attack surfaces, arguing that they constitute a minimal sufficient set for postexploitation reasoning: (1) File system permissions and ownership; (2) Process execution and privilege inheritance; (3) Automated execution mechanisms; (4) Dependency relationships; (5) Software vulnerabilities; (6) User and group relationships; (7) Data movement capabilities. Together, these attack surfaces provide a minimal but sufficient basis for post-exploitation reasoning. Detailed justifications for the selected attack surfaces and the deliberately omitted system aspects are provided in Appendix E. B. PDDL Domain Definition Building upon the aforementioned philosophy, we formally define the domain model (specified in PDDL) as follows. Types (Objects). 9 object types representing the core entities in post-exploitation scenarios. The type system follows a structured inheritance hierarchy: file is the base type for all files, with specialized subtypes including executable (for runnable binaries/scripts), sharedfile (for automatically loaded files like libraries), and calledexecutable (for scheduled tasks). Other fundamental types include user, group, process, data, and permission. Predicates (State Properties). 30 predicates capture system state, organized into: • Capability Predicates (11 predicates) describe what executables can perform, either through native functionality or known vulnerabilities. • Privilege and Control Predicates (4 predicates) track the attacker’s progress and system privilege structure. • File System Predicates (11 predicates) capture static properties and dynamic state of the file system. • Process Execution Predicate (1 predicate) models the process runtime state. • Derived Capability Predicates (3 predicates) compute effective permissions from base predicates. The predicate design follows our minimalism principle. This design choice avoids storing a quadratic number of permission facts (users × files) in the initial state, significantly reducing state space complexity. Actions (State Transitions). 19 actions model state transitions:

Process Execution Actions (3 actions) establish and leverage execution contexts. • File Manipulation Actions (7 actions) modify file system state. • System Configuration Actions (4 actions) alter access controls and system state. • Derivation and Capability Propagation Actions (5 actions) automatically infer facts when preconditions are met. •

This compact yet expressive action set enables modeling of complex multi-step attacks while maintaining the minimalism necessary for efficient planning. Each action represents a distinct, non-redundant capability observed in real-world postexploitation scenarios, with preconditions and effects carefully crafted to capture security-relevant dependencies. Complete predicate definitions and action specifications are provided in Appendix F. C. Automation Script for Host State Extraction The automation scripts perform passive reconnaissance to instantiate the domain model with concrete host state data, strictly following the Principle of Minimal Interference. These scripts execute only read-only commands to construct a complete snapshot of the system’s security-relevant configuration without altering its state. The extraction is organized into five categories that directly correspond to the attack surfaces defined in our modeling philosophy (Section V-A and Section V-B): Identity and Privilege Context: Enumerates users and groups from system files (/etc/passwd, /etc/group), parses membership relationships, and identifies the attacker’s initial foothold context. • File System State: Discovers files in critical directories, extracts security metadata including permissions, ownership, and special flags (SUID/SGID), and classifies files according to our type hierarchy. • System Dynamics: Identifies automated execution mechanisms (cron jobs, systemd services) and maps dependency chains (shared libraries, shell configurations). • Software Vulnerability Context: Queries executable versions and validates them against a CVE knowledge base to identify exploitable vulnerabilities. •

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

5

Algorithm 1 Phase-Guided Hybrid Planning-MCTS (PG-HPMCTS) - Part 1

Algorithm 2 Phase-Guided Hybrid Planning-MCTS (PG-HPMCTS) - Part 2

Require: Initial state s0 , Goal G, Base domain Dbase , Time limit T Ensure: Set of attack chains Π 1: Π ← ∅ 2: root ← createNode(state = s0 , phase = ϕderiv , depth = 0, action = ∅) 3: I NITIALIZE C APABILITIES(root) ▷ Apply derivation actions 4: root.phase ← ϕpriv ▷ Transition to main search 5: for each iteration within limit T do 6: node ← S ELECT(root) ▷ UCT tree traversal 7: if node.depth < dmax ∧ ¬node.isT erminal then 8: // Phase-Guided Hybrid Expansion 9: ϕ ← node.phase 10: Sϕ ← G ET P HASE ACTION S CHEMAS(ϕ, node.action) 11: Dtemp ← C ONSTRUCT T EMP D OMAIN(Dbase , Sϕ ) 12: Ptemp ← C ONSTRUCT T EMP P ROB(node.state, Sϕ ) 13: A ← M ODIFIED P LANNER Q UERY(Dtemp , Ptemp ) ▷ Returns grounded actions 14: if A = ∅ then 15: Mark node as terminal 16: node′ ← node 17: else 18: a ← S AMPLE ACTION(A) 19: s′ ← A PPLYACTION(node.state, a) 20: ϕ′ ← (ϕ + 1) mod 3 ▷ Phase transition 21: node′ ← createNode(state = s′ , phase = ϕ′ , parent = node, action = a) 22: node.children ← node.children ∪ {a : node′ } 23: end if 24: else 25: node′ ← node 26: end if

1: Continuation from Algorithm 1 2: // Phase-Guided Simulation 3: ∆ ← 0, scurr ← node′ .state, ϕcurr ← node′ .phase 4: for i ← 1 to drollout do 5: Sϕ ← G ET P HASE ACTION S CHEMAS(ϕcurr , ∅) 6: Dtemp ← C ONSTRUCT T EMP D OMAIN(Dbase , Sϕ ) 7: Ptemp ← C ONSTRUCT T EMP P ROBLEM(scurr , Sϕ ) 8: Asim ← M ODIFIED P LANNER Q UERY(Dtemp , Ptemp ) 9: if Asim = ∅ or I S T ERMINAL(scurr ) then 10: break 11: end if 12: asim ← RandomChoice(Asim ) 13: scurr ← A PPLYACTION(scurr , asim ) 14: ϕcurr ← (ϕcurr + 1) mod 3 15: ∆ ← ∆ + S TEP R EWARD(scurr , asim ) 16: end for 17: ∆ ← ∆ + F INAL R EWARD(scurr ) 18: BACKPROPAGATE(node′ , ∆) 19: end for 20: E XTRACT P LANS(root, Π) ▷ Collect terminal node paths 21: return Π 22: function G ET P HASE ACTION S CHEMAS(ϕ, actionList) 23: if ϕ = ϕpriv then 24: return Sϕ ▷ Schema set for privilege manipulation 25: else if ϕ = ϕdep then 26: aprev ← actionList[−1] ▷ Last action in sequence 27: return F IND D EPENDENT S CHEMAS(aprev ) ▷ Schemas

Capability Derivation Primitives: Identifies writable locations to support efficient permission computation, avoiding quadratic storage of permission facts. The scripts’ design is strictly governed by the domain model, guaranteeing that every piece of collected information serves a precise purpose in the subsequent planning phase. This tight mapping allows the extracted host state to be translated directly into planning facts with little intermediate processing. Detailed implementation information and exact predicate mappings are provided in Appendix G.

captures the logical dependencies between different types of operations, enabling structured exploration of the attack space. The CAPABILITY DERIVATION PHASE (ϕderiv ) serves as the initialization stage, encompassing actions that infer implicit system capabilities and establish foundational execution contexts. These operations reveal hidden system properties without directly modifying the state, providing the necessary knowledge for subsequent attack steps. This phase ensures the search begins with a complete understanding of available capabilities. The PRIVILEGE MANIPULATION PHASE (ϕpriv ) involves actions that alter system permissions and security contexts. These operations modify the security landscape to create new attack surfaces or elevate access rights, often serving as prerequisites for more intrusive operations. The actions in this phase focus on changing ownership, permissions, and privilege levels to reshape the system’s security boundaries. The EFFECT DEPENDENT PHASE (ϕdep ) dynamically constructs its action set based on the specific state changes achieved in the preceding phase. For each action apriv executed in ϕpriv , the algorithm identifies all actions whose preconditions intersect with effects(apriv ). Formally:

•

VI. T HE P HASE -G UIDED H YBRID P LANNING -MCTS A LGORITHM To address the dual challenges of computational intractability and solution inflexibility in automated attack chain exploration, we propose a novel Phase-Guided Hybrid PlanningMonte Carlo Tree Search (PG-HP-MCTS) algorithm. It integrates symbolic AI planning with stochastic search while organizing actions into semantically coherent phases.

dependent on aprev ’s effects 28: else if ϕ = ϕgoal then 29: return Sϕ ▷ Schemas that can directly achieve G 30: end if 31: end function

A. Phase Guidance: Modeling Attack Action Semantics The phase guidance mechanism in PG-HP-MCTS organizes attack actions into four semantically distinct categories that reflect their role in the attack progression. This classification emerges from systematic analysis of our domain model and

Adep = {a ∈ A | preconditions(a) ∩ effects(apriv ) ̸= ∅} This design ensures that each phase builds directly upon the effects of the previous one, creating a tight causal coupling in

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

the attack progression. For instance, if a privilege manipulation action establishes file writability, this phase will include file writing actions but exclude operations that don’t leverage this newly established capability. The phase is not defined by prespecified action categories but emerges dynamically from the logical dependencies between actions, embodying the principle that effective attack chains exhibit strong stepwise causality. The GOAL DIRECTED PHASE (ϕgoal ) focuses on actions whose effects contain or directly contribute to the goal predicate. Importantly, these are not necessarily terminal actions but often serve as intermediate steps that advance toward the ultimate objective. A goal-directed action might create conditions enabling further privilege manipulation operations in subsequent cycles. These phases form a logical progression captured by the transition function next(ϕ): ϕderiv → (ϕpriv → ϕdep → ϕgoal )∗ , ∗ ≥ 1 The cyclical nature, implemented by the modulo operation (ϕ + 1) mod 3 in Algorithm 1 (line 20) and Algorithm 2 (line 14), reflects real attack patterns where goaldirected actions often create new conditions for further system manipulation. For example, a typical privilege escalation chain might progress as: inferring executable capabilities (capability derivation), changing file permissions (privilege manipulation), exploiting the new permissions to write a malicious payload (effect-dependent), and executing it to gain elevated access (goal-directed). The elevated access then enables discovery of new attack surfaces, continuing the cycle toward the ultimate objective. This phase system implements semantic pruning through several mechanisms. First, it ensures actions are considered in their logical sequence—effect-dependent operations cannot precede the privilege changes that enable them. Second, it restricts the action space at each node to only those operations relevant to the current phase, significantly reducing the branching factor. Third, it enforces causal dependencies between phases, ensuring coherent attack progression. B. Hybrid Architecture: Synergizing Planning and MCTS The hybrid nature of PG-HP-MCTS addresses complementary weaknesses of pure planning and pure MCTS approaches through carefully designed integration. Our architecture leverages the distinct strengths of each paradigm while mitigating their respective limitations. AI planning excels at sound and complete action enumeration, rigorously checking preconditions and parameter bindings to guarantee semantic validity. Modern planners (i.e., FF [25], Fast Downward [27], and Powerlifted [30]) optimize the computationally expensive process of instantiating action schemas with concrete objects. Conversely, MCTS offers anytime performance crucial for operational time constraints, dynamically balances exploration and exploitation through the UCT formula [31], and naturally discovers multiple diverse solutions within a single search rather than stopping at the first viable path. Our hybrid integration, detailed in Algorithms 1 and 2, operates through a novel division of labor. Instead of solving complete planning problems, we dynamically generate

6

phase-specific subproblems (lines 10-13 in Algorithm 1 ). We maintain a base domain Dbase containing the complete set of objects, predicates, and all possible action schemas. At each search node with phase ϕ, the algorithm invokes G ET P HASE ACTION S CHEMAS(ϕ, ·) (line 22-31 in Algorithm 2) to obtain the phase-specific action schema set Sϕ . This set is then used to construct a temporary domain Dtemp that includes the objects and predicates from Dbase , but restricts the action schemas to Sϕ . This temporary domain is paired with a similarly constructed problem file Ptemp encoding the current state, creating a focused planning subproblem that constrains the planner’s search to phase-appropriate actions. When a node requires expansion (lines 9-22 of Algorithm 1) or simulation (lines 4-16 of Algorithm 2), the algorithm identifies action schemas Sϕ relevant to the node’s phase ϕ, constructs a temporary domain Dtemp only containing actions of Sϕ , builds a temporary problem Ptemp restriced with current phase, and invokes our modified planner in single-step enumeration mode. Besides, we also modify the planner to perform only the first layer of state-space expansion. Traditional planners terminate upon finding a complete plan, but our modified version enumerates all grounded actions with satisfied preconditions and returns this set A without further search (line 13 in Algorithm 1). This provides MCTS with a curated, valid action set at minimal computational cost while maintaining semantic correctness. The MCTS framework then manages the high-level search strategy: selecting which phase progression paths to explore deeper through UCT selection, balancing exploration of different capability derivation strategies, and aggregating rewards from multi-step simulations to evaluate phase sequences. This division creates synergistic efficiency gains through dual pruning mechanisms. Phase guidance provides semantic pruning by restricting actions to phase-appropriate schemas, while the planner provides logical pruning by filtering to only applicable instantiations. Temporary action sets typically comprise only 23% (on average) of the complete domain action sets, with a 70% reduction in branch factor compared to unconstrained planning VII-B). C. Algorithm Execution and Innovation Impact The execution flow of PG-HP-MCTS demonstrates how our innovations interact to address the core challenges of attack chain exploration. Initialization (lines 1-5 of Algorithm 1) begins with capability derivation actions in ϕderiv , automatically enriching the state with inferred facts about system capabilities. This preprocessing addresses the issue of insufficient capabilities during the modeling phase before main search commences. During the expansion phase (lines 9-22 of Algorithm 1), the phase attribute ϕ determines which action schemas Sϕ are considered for exploration. When ϕ = ϕpriv , Sϕ includes privilege manipulation actions. When ϕ = ϕdep , Sϕ is dynamically constructed by identifying actions whose preconditions intersect with the effects of the preceding privilege manipulation action. When ϕ = ϕgoal , Sϕ comprises goal-directed actions. The modified planner then enumerates concrete instantiations,

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

ensuring parameter bindings are valid and all preconditions are satisfied. The simulation phase (lines 4-16 of Algorithm 2) maintains phase guidance even during random rollouts. Each simulation step queries the planner for phase-appropriate actions, ensuring that random exploration respects the semantic constraints of realistic attack progression. The phase transition (ϕcurr + 1) mod 3 enforces the cyclical progression pattern throughout simulation, maintaining the integrity of explored chains while allowing for discovery of novel attack vectors within the phase-constrained space. Finally, we provide a detailed description of the pseudocode for the core function G ET P HASE ACTION S CHEMAS(ϕ, ·) (line 22-31 in Algorithm 2). This design fundamentally transforms the search problem from an unstructured exploration of O(|A|d ) possible sequences—where |A| is the total action Q count and d is d depth—to a structured exploration of O( i=1 |Aϕi |) sequences, where |Aϕi | ≪ |A| is the phase-restricted action set at depth i. With our phase system achieving an average reduction of 74% in action choice per phase, this
represents d a search space reduction of approximately 41 , making deep exploration computationally feasible where brute-force approaches would be intractable. The PG-HP-MCTS algorithm makes three key contributions to automated attack chain exploration. First, it introduces a semantically-grounded phase system that organizes attack actions into capability derivation, privilege manipulation, effectdependent, and goal-directed phases, providing structural guidance that prunes implausible paths and focuses search on realistic progressions. Second, it develops a tight plannerMCTS integration where a modified planner efficiently enumerates valid actions constrained by phase, while MCTS manages strategic exploration—combining the completeness of planning with the flexibility of stochastic search. Third, it implements a dual efficiency mechanism where phase guidance reduces the action space semantically while plannerassisted filtering reduces it logically, achieving multiplicative reductions in search space complexity. This integrated approach directly addresses the second and third challenges identified in Section I: computational inefficiency through dual pruning and hybrid division of labor, solution inflexibility through MCTS’s multi-path exploration and anytime performance. D. Post-Processing and Report Generation We filter derivation actions from discovered chains and use an LLM to generate natural language reports with step-by-step walkthroughs and mitigation recommendations. This bridges formal planning output and analyst-facing security guidance. The LLM prompt template and a generated report example are provided in Appendix H. VII. E VALUATION To assess the efficacy, efficiency, and practicality of APEX, we conduct a comprehensive evaluation across multiple dimensions. Our experiments are designed to answer the following key research questions (RQs):

7

RQ1 (Effectiveness): Can APEX successfully discover known and unknown post-exploitation attack chains with high precision? • RQ2 (Efficiency): Does the proposed Phase-Guided Hybrid Planning-MCTS (PG-HP-MCTS) algorithm outperform baseline planner and pure MCTS in terms of planning time and state-space exploration? • RQ3 (Solution Quality & Diversity): Can APEX generate multiple, concise, and semantically diverse attack chains, addressing the inflexibility of traditional planners? • RQ4 (Practicality): Can APEX identify novel, previously unreported attack chains in large-scale, real-world cloud environments? •

A. Experimental Setup Implementation & System Parameters. We implemented APEX as a Python-based system comprising approximately 8,000 lines of code. The system supports two primary connectivity modes for post-exploitation scenarios: SSH-based collection and reverse-shell listener mode. In both modes, a lightweight agent performs passive reconnaissance through a curated set of read-only commands to extract system state without altering the host. For capability modeling, APEX maps discovered system binaries to formal planning predicates based on the GTFOBins database [32]. When an executable matches a GTFOBins entry (e.g., curl with file-download capability), the system automatically instantiates corresponding predicates such as (download file /usr/bin/curl) in the initial state. This enables the planner to reason about Living-off-the-Land techniques using real-world tool functionality. We implemented the PG-HP-MCTS framework from scratch in Python, with careful optimization of state representation and tree node caching. For the integrated planning component, we selected and modified the Powerlifted planner (commit 41aaddd) and modified its interface to operate in a ”single-step enumeration mode”: given a PDDL domain and problem file, it returns all ground actions applicable in the current state (satisfying all preconditions) but does not proceed with full-plan search. This modification is key to the hybrid architecture. The PG-HP-MCTS parameters were carefully tuned through extensive preliminary experiments on a separate validation set. The MCTS exploration constant was set to C=1.414, with a rollout depth of 15 and a maximum tree depth of 20. The algorithm terminates after reaching either 8,000 iterations or a 30-minute wall-clock time limit. We designed a composite reward function R(s, a) = 1goal (s′ ) · 100 + (1 − len(chain) )· 20 action(chain) 10 + unique · 5, where 1 indicates goal state goal total chains achievement. This function strategically balances three objectives: successful goal attainment (primary reward), plan conciseness (shorter chains are preferred), and action schema diversity (encouraging exploration of different attack vectors). All experiments were conducted on a dedicated server running Ubuntu 22.04 LTS, equipped with an AMD EPYC 7513 32-Core Processor and 256 GB of RAM. Although APEX’s planning core is single-threaded, we parallelized the

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

evaluation of independent target instances across CPU cores to maximize throughput. Each planning task was allocated a maximum of 32 GB of RAM and a 30-minute wall-clock time limit. Benchmark and Dataset.Our evaluation employs a multifaceted benchmark: • CTF VMs (Known-Chain Validation): We selected 5 well-established Capture-The-Flag virtual machines from VulnHub and HackTheBox that are specifically designed for privilege escalation training: Escalate My Privileges [33](C1), Lin.Security [34](C2), FriendZone [35](C3), SolidState [36](C4), and Jack-of-AllTrades [37](C5). These VMs contain documented, multistep privilege escalation chains combining misconfigurations, SUID binaries, and scheduled tasks, providing a ground truth for validation. • Synthetic Problem (Controlled Complexity): To systematically evaluate the scalability of PG-HP-MCTS, we generated 30 synthetic planning problems with controlled complexity levels by incrementally scaling two key parameters: the number of objects (from 500 to 3000 in steps of 500) and the density of predicates (maintaining 3-4 predicates per object to ensure adequate relational structure). Each problem instance was constructed to guarantee at least one solvable privilege escalation path to measure system scalability. • Real-World Cloud Instances (Unreported Attack Chain): To assess practical impact, we deployed and tested APEX on a large-scale dataset of 291 cloud instances: 175 Amazon EC2 instances and 116 Alibaba Cloud ECS instances. We selected a diverse set of official and marketplace Linux images (Ubuntu 18.04/20.04/22.04, CentOS 7/8, Debian 10/11, Amazon Linux 2). All instances were launched with default configurations, and we accessed them via SSH using the default low-privileged user. For fair comparison, we set the goal as obtaining root user privileges. No modifications were made post-creation. Baselines for Comparison. We compare APEX against three critical baselines. (1) Pure Optimal Planner (Powerlifted [30]): Represents the state-of-the-art in optimal classical planning, configured for satisficing planning (i.e., seeking a feasible solution rather than an optimal one). (2) Pure MCTS: A standard Monte Carlo Tree Search implementation that does not incorporate phase guidance or planner integration. It performs a naive random rollout for simulation. (3) ChainReactor [18]: We faithfully reproduced the core planning pipeline of ChainReactor using its reported configuration and ran it on our identical benchmark datasets for a direct, fair comparison. B. Evaluation on Benchmark Environments Known CTF Virtual Machines. APEX successfully discovered valid privilege escalation chains in all 5 CTF VMs, achieving a 100% success rate. However, due to the inherent complexity of state-space search and the probabilistic nature of the PG-HP-MCTS algorithm, the discovered chains were not always identical to the documented ”ground-truth” solutions. Instead, APEX frequently found alternative, functionally equivalent paths that leveraged different combinations of

8

system misconfigurations and capabilities, demonstrating the algorithm’s ability to explore diverse regions of the solution space. The average time to first solution was 870.6s, reflecting the realistic computational cost of navigating large, complex state spaces inherent to real host environments. The results, summarized in Table I, highlight a key strength of APEX in addressing RQ3 (Solution Quality & Diversity). On average, APEX found 2.4 distinct attack chains per VM. Notably, the number of chains discovered exhibited variability across different runs on the same VM, which is characteristic of the stochastic MCTS search process. Critically, all discovered chains were manually validated and confirmed to be operationally feasible, meaning they could be executed stepby-step to achieve the privilege escalation goal. This output of multiple, non-identical chains provides security analysts with a broader perspective on potential attack vectors, moving beyond a single ”ground-truth” path to a more comprehensive risk assessment. Finally, we provide a brief description and analysis of each attack chain in Table I. Analysis for RQ1 & RQ3: These results confirm APEX’s effectiveness in discovering viable attack chains within operationally relevant timeframes (RQ1). More importantly, the consistent generation of multiple distinct and validated chains – rather than converging on a single optimal solution – directly addresses the solution inflexibility challenge. This capability provides defenders with a more complete understanding of the attack surface, enabling them to prioritize mitigations that break entire classes of attacks rather than just the most obvious path. Synthetic Problems: Efficiency and Scalability.Figure 2 and Table II collectively demonstrate the high efficiency and scalability of APEX compared to baseline approaches on synthetic datasets. The average success rates for the pure optimal planner, pure MCTS, and APEX were 57%(17), 7%(2), and 93%(28), respectively. Notably, the pure optimal planner and pure MCTS achieved zero solution success rates at two (2500, 3000) and five (1000, 1500, 2000, 2500, 3000) scales, respectively. In contrast, APEX demonstrates exceptional efficiency and scalability, achieving a 60% planning success rate even on the largest-scale problem (3000 objects)—where competing approaches both failed completely. We additionally focused on analyzing the primary reasons for the poor performance of pure MCTS. As shown in Table II, the average number of node branches and action enumeration time for pure MCTS were significantly higher than those for PGHP-MCTS. This is primarily because pure MCTS lacks both phase guidance and efficient enumeration capabilities. Notably, the action enumeration process in pure MCTS consumed 91% of the total solution time. Finally, we have calculated that the phase-guided PG-HP-MCTS exhibits an average behavioral enumeration count of 219. This represents only 23% of the average enumeration count of 952 observed in the absence of phase guidance. Analysis for RQ2: APEX’s significantly higher success rate and lower planning time, especially on complex problems, provide strong evidence that the PG-HP-MCTS algorithm successfully tackles the computational inefficiency challenge. The drastic reduction in states expanded indicates effective

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

9

TABLE I: Performance on CTF Virtual Machines. CTF VM

Success

# Chains Found

TTFS (s)

Shortest Length

C1

Yes

3

593

6

C2

Yes

2

835

5

C3

Yes

4

816

8

C4

Yes

2

692

7

C5

Yes

1

1417

9

Average

100%

2.4

870.6

7.0

TABLE II: Aggregate Results on Synthetic Problems (n=30). Metric Success Rate Avg. Planning Time (s) Avg. Branches Per Node Avg. Action Enum. Time (s)

Pure Planner 57%

Pure MCTS 7%

649.5

1632.7

799.8

/

27.3

8.1

/

104.5

5.1

PG-HP-MCTS 93%

pruning via phase guidance.

Fig. 2: Efficiency and Scalability Analysis: Success Rate & Planning Time.

C. Large-Scale Real-World Evaluation We deployed APEX on 291 live cloud instances to evaluate its practical effectiveness in real-world scenarios. The evaluation targeted 175 Amazon EC2 instances and 116 Alibaba Cloud ECS instances, representing a diverse set of official and marketplace Linux distributions. The information collection phase demonstrated efficiency, requiring an average of 3.1 minutes per instance with a maximum of 5.5 minutes. In this large-scale deployment, APEX successfully discovered privilege escalation chains in 27 instances, comprising 19 EC2 instances (10.9%) and 8 ECS instances (6.9%). More significantly, the system identified 9 previously unreported attack chains that represent novel security vulnerabilities in production cloud environments. The average total analysis time—including both information collection and solving phases—was approximately 19.4 minutes per instance, representing a reduction of over 47.6% compared to ChainReactor’s

Chain Description and Analysis Chains involved three primitives: SUID binary exploitation, cron job hijacking, and writable systemd service corruption. Two distinct vectors discovered: .bashrc environment variable hijack and direct systemd service file corruption. Multiple chains identified combining LD PRELOAD injection, sudo misconfiguration exploitation, and symbolic link attacks. Alternative paths through different writable script targets: Python service script manipulation and shell script hijacking. Exploit the command injection vulnerability in the scanlosers.sh script to gain access as the pwn user and leverage passwordless sudo privileges to execute msfconsole as root. All 12 total chains were manually verified as feasible.

reported average of 37 minutes [18]. This efficiency gain directly stems from our PG-HP-MCTS algorithm’s optimized search strategy. The discovered attack chains demonstrated meaningful diversity and sophistication. On average, each vulnerable instance yielded 2.1 distinct attack paths, with EC2 instances showing slightly higher diversity (2.3 chains) than ECS instances (1.8 chains). This multi-solution capability proved particularly valuable for defensive analysis, as it revealed alternative attack vectors that might otherwise remain hidden when using single-solution approaches. Case Study 1 (Docker Group to Service File Corruption Chain): On a Debian-11 EC2 instance, APEX discovered a 4-step chain based purely on permission misconfigurations. The chain began with the unprivileged user being a member of the docker group, granting container management capabilities. Further analysis revealed a systemd service (/etc/systemd/system/metrics-collector. service) owned by the docker group with group-write permissions. Using Docker’s ability to mount the host filesystem, the attacker could modify this service file to execute arbitrary commands. Since the service was configured to start at boot with root privileges, the modification resulted in privilege escalation. Case Study 2 (SUID Binary to Cron Script Hijacking): On an Ubuntu-20.04 ECS instance, the system uncovered a chain combining SUID binary misuse with cron script manipulation. The initial foothold involved a custom SUID binary (/usr/local/bin/backup-tool) that executed shell commands without proper sanitization. While this binary alone did not provide direct root access, APEX discovered it could be used to modify a world-writable cron script (/etc/cron.daily/disk-cleanup) that ran as root. By chaining these two misconfigurations—first using the SUID binary to inject malicious commands into the cron script, then relying on the cron execution—the system achieved privilege escalation. Case Study 3 (Environment Variable Injection via Writable Profile Scripts): On a Centos-7 EC2 instance, APEX identified a subtle chain involving environment variable manipulation. The system detected that the user’s home directory contained a .profile script that was writable by other users in the same group. Concurrently, a system administration script

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

TABLE III: Direct Comparison with ChainReactor. Metric Instances with ≥1 Chain Total Chains Discovered Avg. Chains per Instance Avg. Solver Time per Instance

ChainReactor 2 2 1.0 25.1min

APEX 6 14 2.3 14.4min

(/usr/local/bin/system-check) executed with root privileges and sourced environment variables without proper validation. By modifying the .profile script to inject malicious environment variables, and triggering the systemcheck script (which could be done through various means discovered by the solver), the attacker could execute arbitrary commands as root. Analysis for RQ1 & RQ4: The discovery of 9 unreported attack chains in production cloud environments provides compelling evidence of APEX’s practical effectiveness (RQ1). More importantly, the consistent generation of multiple attack chains per vulnerable instance—combined with significantly reduced analysis times—demonstrates that our approach not only identifies novel vulnerabilities but does so with efficiency that enables large-scale security assessments (RQ4). The 47.6% reduction in analysis time compared to ChainReactor directly addresses operational constraints in real-world security workflows, while the multi-chain output provides defenders with a more comprehensive understanding of their attack surface. Notably, all discovered chains involved either pure configuration errors or hybrid chains combining vulnerabilities with misconfigurations, validating our domain modeling approach focused on system interactions rather than individual bug exploitation. Direct Comparison with ChainReactor. To ensure a fair comparison, we ran the reproduced ChainReactor pipeline on a randomly selected subset of 50 instances from our dataset. It is important to note that ChainReactor directly invokes pure solver (Powerlifted) for its solving component. As shown in Table III, the results highlight the differences between ChainReactor (a pure satisfying solver) and our method. First, APEX identified potential attack chains on 6 instances, while ChainReactor found only 2 (which were covered), indicating that APEX possesses stronger attack chain detection sensitivity. Second, APEX discovered a total of 14 attack chains—seven times more than ChainReactor—with an average of 2.3 attack chains per instance, which is 2.3 times higher than ChainReactor’s average. Finally, APEX achieved an average solution time of 14.4 minutes, representing a 42.6% reduction in time overhead compared to ChainReactor. This direct comparison validates that our PG-HP-MCTS algorithm is not only faster but crucially generates a richer set of offensive options. Where ChainReactor stops at the first found path, APEX continues exploring, which is vital for comprehensive defensive analysis (RQ3). The speed advantage stems from the targeted, phase-guided search (RQ2). VIII. D ISCUSSION & L IMITATION A. Discussion Our experimental results demonstrate that APEX effectively addresses core challenges in automated attack chain

10

exploration. The phase-guided hybrid algorithm successfully balances computational efficiency with solution diversity, enabling discovery of multiple feasible chains within operationally relevant timeframes. This capability represents a significant advancement over traditional satisficing planners, which terminate upon finding a single solution. The generation of diverse attack chains has particular defensive value. Rather than identifying only the shortest path, APEX reveals different vulnerability classes and their interactions within a system. This comprehensive view enables defenders to prioritize mitigations that break entire attack surfaces—for instance, fixing a single writable service file that appears in multiple chains—rather than addressing isolated vulnerabilities. Our approach thus shifts the defensive paradigm from reactive patching to proactive attack surface reduction. The methodology is fundamentally extensible. While instantiated for Unix post-exploitation, the core framework—formal domain modeling combined with phase-guided hybrid search—can be adapted to other security domains requiring multi-step reasoning, such as cloud misconfiguration analysis or software supply chain attack exploration. The primary adaptation would involve creating a new domain model and designing phase-guided hybrid MCTS algorithms; the solver architecture remains largely domain-agnostic. B. Limitations and Future Work Despite its contributions, APEX has several limitations that warrant discussion. First, while our domain model captures prevalent attack vectors, it remains an abstraction. Certain advanced techniques—particularly kernel-level exploits, race conditions, or hardware-based attacks—fall outside its current scope. Future work will develop a modular extension framework to incorporate new attack patterns as they emerge, potentially through automated extraction from security advisories and exploit write-ups. Second, our current vulnerability capability modeling requires manual curation. We manually extracted specific capabilities (e.g., arbitrary file write, command injection) from known CVEs and mapped them to executable predicates. This process is labor-intensive and cannot scale to the continuous stream of new vulnerabilities. Future work should investigate automated vulnerability capability extraction using large language models (LLMs). By analyzing CVE descriptions, exploit proofs-of-concept, and advisory texts, LLMs could automatically infer the security-relevant effects of vulnerabilities and translate them into formal planning predicates and action schemas. This would significantly enhance the model’s comprehensiveness and timeliness. Third, our current model optimizes for logical feasibility rather than operational stealth. Generated chains may contain actions likely to trigger security alerts in monitored environments. Integrating detection-awareness into the reward function—by modeling common EDR signatures or logging patterns—would enable the discovery of more covert attack paths, better simulating advanced adversaries. Fourth, APEX generates attack chains but does not automatically execute them to validate operational feasibility or collect

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

11

runtime data. Future work should implement safe, controlled execution of discovered chains in isolated environments, coupled with comprehensive logging of system events. This would enable the creation of high-quality, actionable datasets for data-driven network/host security. Such datasets, capturing the complex multi-step nature of real attacks, could significantly improve supervised machine learning approaches for intrusion detection that currently struggle with sophisticated, multivector threats. Finally, APEX assumes static host configurations during analysis and does not model interactive defender responses. Extending the framework to support adaptive planning in dynamic environments, possibly through integration with lightweight runtime monitors, represents a valuable direction for transforming attack chain exploration into fully automated penetration testing.

planning has shown particular promise for modeling multi-step attacks, with applications in network penetration testing [60], [61], [62], [63] and smart grid security [64]. While planning has also been applied to host-level privilege escalation [18], [16], existing approaches face significant challenges when modeling complex host environments. Most critically, they typically employ satisficing strategies that terminate upon finding any feasible solution, providing limited insight into alternative attack paths. This limitation is particularly problematic in post-exploitation scenarios where defenders need to understand all potential attack vectors, not just the most obvious one. Our work addresses this by integrating planning with Monte Carlo Tree Search (MCTS), enabling discovery of multiple diverse attack chains while maintaining the formal correctness guarantees of classical planning.

IX. R ELATED W ORK

C. Search Algorithms and System-Specific Security Analysis

A. Automated Penetration Testing and Post-Exploitation Analysis

Exploring the vast solution space of possible attack chains requires efficient search algorithms capable of handling complex state spaces. Classical planning systems employ either grounded [65], [66], [67] or lifted [68], [69] approaches, with lifted planners offering better scalability for domains with many objects—a critical requirement for host modeling. Monte Carlo Tree Search provides complementary strengths through its ability to balance exploration and exploitation via randomized simulations [31], offering anytime performance and multi-solution discovery. However, pure MCTS lacks the formal reasoning needed for complex security operations. Our phase-guided hybrid Planning-MCTS algorithm synthesizes these approaches, addressing limitations in both paradigms. Unlike penetration testing tools that explore abstract network spaces [70], [23], our algorithm is specifically designed for the concrete, highly constrained environments of post-exploitation host analysis. This domain requires reasoning about specific system components and their complex interactions, rather than abstract network states. The problem of privilege escalation has been extensively studied across various environments, including UNIX/Linux systems [71], [72], mobile platforms [73], [74], browser environments [75], trusted execution environments [76], cloud infrastructures [77], [78], and firmware [79]. While these investigations comprehensively catalog individual escalation mechanisms, they provide limited methodology for automatically discovering how these mechanisms can be chained together—the precise gap our work addresses.

The automation of security assessment has evolved along two primary dimensions: pre-exploitation vulnerability discovery and post-exploitation attack chain analysis. In the preexploitation domain, systems like PenTestGPT and PentestAgent [38], [39] leverage large language models to interpret scan results and generate exploitation scripts, while some approaches [40], [41], [42] employ reinforcement learning to explore networks and establish footholds. These approaches focus on the early stages of the attack lifecycle—reconnaissance, vulnerability scanning, and initial compromise. Complementary to these efforts are traditional vulnerability discovery techniques including fuzzing [43], [44], symbolic execution [45], hybrid analysis [46], [47], [48], bounded model checking [49], static analysis [50], and formal verification [51]. While effective for identifying individual vulnerabilities, these methods lack the capability to reason about how multiple weaknesses can be strategically combined into operational attack chains. In contrast, our work focuses exclusively on the postexploitation phase, where an attacker has already obtained shell access and must navigate complex host environments. This requires fundamentally different modeling that captures system state transitions, permission relationships, file dependencies, and capability propagation—elements that are largely irrelevant to initial access tools but essential for discovering multi-step attack chains that blend benign and malicious operations. Our approach bridges this gap by providing systematic methodology for discovering how defenders can proactively identify chains combining multiple independent weaknesses. B. Formal Modeling and Planning for Attack Simulation Formal methods have been widely applied to model security operations and enable systematic reasoning. Early simulation approaches modeled attacks as cause-effect transitions [52], while graph-based representations like attack graphs have been used to analyze network intrusion paths [53], [54], [55]. Other formalisms include Petri nets [56], [57], logical frameworks [58], and game-theoretic models [59]. More recently, AI

D. Positioning of Our Work C HAIN R EACTOR [18] represents the closest related work, applying lifted planning to privilege escalation chain discovery. Our approach differs fundamentally in several aspects. First, we introduce semantic phase guidance that organizes attack actions based on their operational purpose, enabling more efficient search. Second, we integrate MCTS with planning rather than relying solely on classical planners, addressing solution inflexibility and enabling discovery of multiple diverse chains. Third, our modeling captures finer-grained host

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

state transitions and attacker capability evolution during postexploitation. Finally, our evaluation demonstrates discovery of previously unreported attack chains in production cloud environments. X. C ONCLUSION In this work, we presented APEX, an automated system for discovering post-exploitation attack chains in complex host environments. APEX addresses the realistic threat scenario where adversaries combine benign operations, configuration errors, and targeted exploits to form multi-step attack chains. By formulating this problem as an AI planning task and solving it with our novel phase-guided hybrid Planning-MCTS algorithm, we enable efficient and diverse exploration of attack chains that would be infeasible to discover manually. Our experimental evaluation demonstrates the practical effectiveness of this approach. APEX successfully rediscovers known attack chains in controlled benchmarks while identifying 9 previously unreported privilege escalation vectors in realworld cloud environments. The system’s ability to generate multiple distinct attack paths provides defenders with comprehensive threat intelligence, enabling proactive hardening of complex production systems against sophisticated postexploitation attacks. R EFERENCES [1] Brian Chess and Gary McGraw. Static analysis for security. IEEE security & privacy, 2(6):76–79, 2004. [2] Roberto Baldoni, Emilio Coppa, Daniele Cono D’elia, Camil Demetrescu, and Irene Finocchi. A survey of symbolic execution techniques. ACM Computing Surveys (CSUR), 51(3):1–39, 2018. [3] Hongliang Liang, Xiaoxiao Pei, Xiaodong Jia, Wuwei Shen, and Jian Zhang. Fuzzing: State of the art. IEEE Transactions on Reliability, 67(3):1199–1218, 2018. [4] Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse. {AFL++}: Combining incremental steps of fuzzing research. In 14th USENIX workshop on offensive technologies (WOOT 20), 2020. [5] James Clause, Wanchun Li, and Alessandro Orso. Dytan: a generic dynamic taint analysis framework. In Proceedings of the 2007 international symposium on Software testing and analysis, pages 196–206, 2007. [6] James Newsome and Dawn Xiaodong Song. Dynamic taint analysis for automatic detection, analysis, and signaturegeneration of exploits on commodity software. In NDSS, volume 5, pages 3–4. Citeseer, 2005. [7] William Wright, David Schroh, Pascale Proulx, Alex Skaburskis, and Brian Cort. The sandbox for analysis: concepts and methods. In Proceedings of the SIGCHI conference on Human Factors in computing systems, pages 801–810, 2006. [8] Silvius Rus, Lawrence Rauchwerger, and Jay Hoeflinger. Hybrid analysis: static & dynamic memory reference analysis. In Proceedings of the 16th international conference on Supercomputing, pages 274–284, 2002. [9] Kevin A Roundy and Barton P Miller. Hybrid analysis and control of malware. In Recent Advances in Intrusion Detection: 13th International Symposium, RAID 2010, Ottawa, Ontario, Canada, September 15-17, 2010. Proceedings 13, pages 317–338. Springer, 2010. [10] FIRST. Forum of incident response and security teams. https://www. first.org/, 2025. [11] FIRST.Org. Common vulnerability scoring system v3.1: Specification document. https://www.first.org/cvss/v3-1/specification-document, 2025. [12] 2024 cves in review - vulnerability blog. https://vulnerability.blog/2025/ 01/14/2024-cves-in-review/, 2024. [13] Nathan Burow, Scott A Carr, Joseph Nash, Per Larsen, Michael Franz, Stefan Brunthaler, and Mathias Payer. Control-flow integrity: Precision, security, and performance. ACM Computing Surveys (CSUR), 50(1):1– 33, 2017.

12

[14] Hovav Shacham, Matthew Page, Ben Pfaff, Eu-Jin Goh, Nagendra Modadugu, and Dan Boneh. On the effectiveness of address-space randomization. In Proceedings of the 11th ACM conference on Computer and communications security, pages 298–307, 2004. [15] Thurston HY Dang, Petros Maniatis, and David Wagner. The performance cost of shadow stacks and stack canaries. In Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, pages 555–566, 2015. [16] Ryusei Maeda and Mamoru Mimura. Automating post-exploitation with deep reinforcement learning. Computers & Security, 100:102108, 2021. [17] Doug Miller, Ron Alford, Andy Applebaum, Henry Foster, Caleb Little, and Blake Strom. Automated adversary emulation: A case for planning and acting with unknowns. MITRE CORP MCLEAN VA MCLEAN, 2018. [18] Giulio De Pasquale, Ilya Grishchenko, Riccardo Iesari, Gabriel Pizarro, Lorenzo Cavallaro, Christopher Kruegel, and Giovanni Vigna. {ChainReactor}: Automated privilege escalation chain discovery via {AI} planning. In 33rd USENIX Security Symposium (USENIX Security 24), pages 5913–5929, 2024. [19] Adam Amos-Binks, Joshua Clark, Kirk Weston, Michael Winters, and Khaled Harfoush. Efficient attack plan recognition using automated planning. In 2017 IEEE symposium on computers and communications (ISCC), pages 1001–1006. IEEE, 2017. [20] Jörg Hoffmann. Simulated penetration testing: From” dijkstra” to” turing test++”. In Proceedings of the international conference on automated planning and scheduling, volume 25, pages 364–372, 2015. [21] Patrick Speicher, Marcel Steinmetz, Jörg Hoffmann, Michael Backes, and Robert Künnemann. Towards automated network mitigation analysis. In Proceedings of the 34th ACM/SIGAPP symposium on applied computing, pages 1971–1978, 2019. [22] Taejun Choi, Ryan KL Ko, Tapan Saha, Joshua Scarsbrook, Abigail MY Koay, Shunyao Wang, Wenlu Zhang, and Connor St Clair. Plan2defend: Ai planning for cybersecurity in smart grids. 2021 IEEE PES Innovative Smart Grid Technologies-Asia (ISGT Asia), pages 1–5, 2021. [23] Mingda Li, Tiantian Zhu, Haoqi Yan, Tieming Chen, and Mingqi Lv. Her-pt: An intelligent penetration testing framework with hindsight experience replay. Computers & Security, 152:104357, 2025. [24] CrowdStrike. Lateral movement explained. https://www.crowdstrike. com/en-us/cybersecurity-101/cyberattacks/lateral-movement/, 2025. [25] Jörg Hoffmann. Ff: The fast-forward planning system. AI magazine, 22(3):57–57, 2001. [26] David E Smith and Daniel S Weld. Conformant graphplan. In AAAI/IAAI, pages 889–896, 1998. [27] Malte Helmert. The fast downward planning system. Journal of Artificial Intelligence Research, 26:191–246, 2006. [28] Blai Bonet and Héctor Geffner. Planning as heuristic search. Artificial Intelligence, 129(1-2):5–33, 2001. [29] Maxim Likhachev, Geoffrey J Gordon, and Sebastian Thrun. Ara*: Anytime a* with provable bounds on sub-optimality. Advances in neural information processing systems, 16, 2003. [30] Powerlifted planner. https://github.com/abcorrea/powerlifted, 2024. [31] Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pages 282– 293. Springer, 2006. [32] Emilio Pinna and Andrea Cardaci. Gtfobins. https://gtfobins.github.io/, 2025. [33] Escalate my privileges. https://www.vulnhub.com/entry/escalate-myprivileges-1,448/, 2025. [34] Lin.security. https://www.vulnhub.com/entry/linsecurity-1,244/, 2025. [35] Friendzone. https://www.hackthebox.com/machines/friendzone, 2025. [36] Solidstate. https://www.hackthebox.com/machines/solidstate, 2025. [37] Jack-of-all-trades. https://thewireshark.com/2025/05/jack-of-all-trades/, 2025. [38] Gelei Deng, Yi Liu, Vı́ctor Mayoral-Vilches, Peng Liu, Yuekang Li, Yuan Xu, Tianwei Zhang, Yang Liu, Martin Pinzger, and Stefan Rass. {PentestGPT}: Evaluating and harnessing large language models for automated penetration testing. In 33rd USENIX Security Symposium (USENIX Security 24), pages 847–864, 2024. [39] Xiangmin Shen, Lingzhi Wang, Zhenyuan Li, Yan Chen, Wencheng Zhao, Dawei Sun, Jiashui Wang, and Wei Ruan. Pentestagent: Incorporating llm agents to automated penetration testing. In Proceedings of the 20th ACM Asia Conference on Computer and Communications Security, pages 375–391, 2025. [40] Shicheng Zhou, Jingju Liu, Yuliang Lu, Jiahai Yang, Yue Zhang, and Jie Chen. Mind the gap: towards generalizable autonomous penetration testing via domain randomization and meta-reinforcement

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

learning. Frontiers of Information Technology & Electronic Engineering, 26(12):2511–2528, 2025. [41] Jonathon Schwartz and Hanna Kurniawati. Autonomous penetration testing using reinforcement learning. arXiv preprint arXiv:1905.05965, 2019. [42] Zhenguo Hu, Razvan Beuran, and Yasuo Tan. Automated penetration testing using deep reinforcement learning. In 2020 IEEE European Symposium on Security and Privacy Workshops (EuroS&PW), pages 2– 10. IEEE, 2020. [43] Andrea Fioraldi, Dominik Maier, Heiko Eißfeldt, and Marc Heuse. {AFL++}: Combining incremental steps of fuzzing research. In 14th USENIX workshop on offensive technologies (WOOT 20), 2020. [44] Hongliang Liang, Xiaoxiao Pei, Xiaodong Jia, Wuwei Shen, and Jian Zhang. Fuzzing: State of the art. IEEE Transactions on Reliability, 67(3):1199–1218, 2018. [45] Roberto Baldoni, Emilio Coppa, Daniele Cono D’elia, Camil Demetrescu, and Irene Finocchi. A survey of symbolic execution techniques. ACM Computing Surveys (CSUR), 51(3):1–39, 2018. [46] Ju Chen, Wookhyun Han, Mingjun Yin, Haochen Zeng, Chengyu Song, Byoungyoung Lee, Heng Yin, and Insik Shin. {SYMSAN}: Time and space efficient concolic execution via dynamic data-flow analysis. In 31st USENIX Security Symposium (USENIX Security 22), pages 2531– 2548, 2022. [47] Sebastian Poeplau and Aurélien Francillon. Symbolic execution with {SymCC}: Don’t interpret, compile! In 29th USENIX Security Symposium (USENIX Security 20), pages 181–198, 2020. [48] Nick Stephens, John Grosen, Christopher Salls, Andrew Dutcher, Ruoyu Wang, Jacopo Corbetta, Yan Shoshitaishvili, Christopher Kruegel, and Giovanni Vigna. Driller: Augmenting fuzzing through selective symbolic execution. In NDSS, volume 16, pages 1–16, 2016. [49] Armin Biere. Bounded model checking. In Handbook of satisfiability, pages 739–764. IOS press, 2021. [50] Brian Chess and Gary McGraw. Static analysis for security. IEEE security & privacy, 2(6):76–79, 2004. [51] Osman Hasan and Sofiene Tahar. Formal verification methods. In Encyclopedia of Information Science and Technology, Third Edition, pages 7162–7170. IGI Global Scientific Publishing, 2015. [52] Fred Cohen. Simulating cyber attacks, defences, and consequences. Computers & Security, 18(6):479–518, 1999. [53] Hannes Holm, Khurram Shahzad, Markus Buschle, and Mathias Ekstedt. P2 CySeMoL: Predictive, probabilistic cyber security modeling language. IEEE Transactions on Dependable and Secure Computing, 12(6):626– 639, 2014. [54] Pontus Johnson, Robert Lagerström, and Mathias Ekstedt. A meta language for threat modeling and attack simulations. In Proceedings of the 13th international conference on availability, reliability and security, pages 1–8, 2018. [55] Xinming Ou, Sudhakar Govindavajhala, Andrew W Appel, et al. Mulval: A logic-based network security analyzer. In USENIX security symposium, volume 8, pages 113–128. Baltimore, MD, 2005. [56] Srdjan Pudar, Govindarasu Manimaran, and Chen-Ching Liu. Penet: A practical method and tool for integrated modeling of security attacks and countermeasures. Computers & Security, 28(8):754–771, 2009. [57] Gaofeng Zhang, Paolo Falcarin, Elena Gómez-Martı́nez, Shareeful Islam, Christophe Tartary, Bjorn De Sutter, and Jerome d’Annoville. Attack simulation based software protection assessment method. In 2016 International Conference On Cyber Security And Protection Of Digital Services (Cyber Security), pages 1–8. Ieee, 2016. [58] Igor Kotenko. Active vulnerability assessment of computer networks by simulation of complex remote attacks. In 2003 International Conference on Computer Networks and Mobile Computing, 2003. ICCNMC 2003., pages 40–47. IEEE, 2003. [59] Robert K Abercrombie, Bob G Schlicher, and Frederick T Sheldon. Security analysis of selected ami failure scenarios using agent based game theoretic simulation. In 2014 47th Hawaii international conference on system sciences, pages 2015–2024. IEEE, 2014. [60] Adam Amos-Binks, Joshua Clark, Kirk Weston, Michael Winters, and Khaled Harfoush. Efficient attack plan recognition using automated planning. In 2017 IEEE symposium on computers and communications (ISCC), pages 1001–1006. IEEE, 2017. [61] Jörg Hoffmann. Simulated penetration testing: from” dijkstra” to” turing test++”. In Proceedings of the international conference on automated planning and scheduling, volume 25, pages 364–372, 2015. [62] Doug Miller, Ron Alford, Andy Applebaum, Henry Foster, Caleb Little, and Blake Strom. Automated adversary emulation: A case for planning and acting with unknowns. 2018.

13

[63] Patrick Speicher, Marcel Steinmetz, Jörg Hoffmann, Michael Backes, and Robert Künnemann. Towards automated network mitigation analysis. In Proceedings of the 34th ACM/SIGAPP symposium on applied computing, pages 1971–1978, 2019. [64] Taejun Choi, Ryan KL Ko, Tapan Saha, Joshua Scarsbrook, Abigail MY Koay, Shunyao Wang, Wenlu Zhang, and Connor St Clair. Plan2defend: Ai planning for cybersecurity in smart grids. 2021 IEEE PES Innovative Smart Grid Technologies-Asia (ISGT Asia), pages 1–5, 2021. [65] Augusto B Corrêa, Markus Hecher, Malte Helmert, Davide Mario Longo, Florian Pommerening, and Stefan Woltran. Grounding planning tasks using tree decompositions and iterated solving. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 33, pages 100–108, 2023. [66] Daniel Gnad, Alvaro Torralba, Martı́n Domı́nguez, Carlos Areces, and Facundo Bustos. Learning how to ground a plan–partial grounding in classical planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 7602–7609, 2019. [67] Malte Helmert. Concise finite-domain representations for pddl planning tasks. Artificial Intelligence, 173(5-6):503–535, 2009. [68] Augusto B Corrêa, Florian Pommerening, Malte Helmert, and Guillem Frances. Lifted successor generation using query optimization techniques. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, pages 80–89, 2020. [69] Bernardus Ridder. Lifted heuristics: towards more scalable planning systems. PhD thesis, King’s College London (University of London), 2014. [70] He Kong, Die Hu, Jingguo Ge, Liangxiong Li, Tong Li, and Bingzhen Wu. Vulnbot: Autonomous penetration testing for a multi-agent collaborative framework. arXiv preprint arXiv:2501.13411, 2025. [71] Bhushan Jain, Chia-Che Tsai, Jitin John, and Donald E Porter. Practical techniques to obviate setuid-to-root binaries. In Proceedings of the Ninth European Conference on Computer Systems, pages 1–14, 2014. [72] Yuseok Jeon, Junghwan Rhee, Chung Hwan Kim, Zhichun Li, Mathias Payer, Byoungyoung Lee, and Zhenyu Wu. Polper: Process-aware restriction of over-privileged setuid calls in legacy applications. In Proceedings of the Ninth ACM Conference on Data and Application Security and Privacy, pages 209–220, 2019. [73] Abdulla Aldoseri, David Oswald, and Robert Chiper. A tale of four gates: Privilege escalation and permission bypasses on android through app components. In European Symposium on Research in Computer Security, pages 233–251. Springer, 2022. [74] Lucas Davi, Alexandra Dmitrienko, Ahmad-Reza Sadeghi, and Marcel Winandy. Privilege escalation attacks on android. In international conference on Information security, pages 346–360. Springer, 2010. [75] Young Min Kim and Byoungyoung Lee. Extending a hand to attackers: browser privilege escalation attacks via extensions. In 32nd usenix security symposium (usenix security 23), pages 7055–7071, 2023. [76] Darius Suciu, Stephen McLaughlin, Laurent Simon, and Radu Sion. Horizontal privilege escalation in trusted applications. In 29th USENIX Security Symposium (USENIX Security 20), 2020. [77] Ibrahim Bu Haimed, Marwan Albahar, and Ali Alzubaidi. Exploiting misconfiguration vulnerabilities in microsoft’s azure active directory for privilege escalation attacks. Future Internet, 15(7):226, 2023. [78] Nicholas Pecka, Lotfi Ben Othmane, and Altaz Valani. Privilege escalation attack scenarios on the devops pipeline within a kubernetes environment. In Proceedings of the International Conference on Software and System Processes and International Conference on Global Software Engineering, pages 45–49, 2022. [79] Jiawei Yin, Menghao Li, Wei Wu, Dandan Sun, Jianhua Zhou, Wei Huo, and Jingling Xue. Finding smm privilege-escalation vulnerabilities in uefi firmware with protocol-centric static analysis. In 2022 IEEE Symposium on Security and Privacy (SP), pages 1623–1637. IEEE, 2022. [80] MITRE. ATT&CK matrix for enterprise. https://attack.mitre.org/, 2025. [81] Constructions Aeronautiques, Adele Howe, Craig Knoblock, ISI Drew McDermott, Ashwin Ram, Manuela Veloso, Daniel Weld, David Wilkins Sri, Anthony Barrett, Dave Christianson, et al. Pddl—the planning domain definition language. Technical Report, Tech. Rep., 1998.

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

A PPENDIX A E XTENDED D ISCUSSION ON P OST-E XPLOITATION AND MITRE ATT&CK Within the MITRE ATT&CK Matrix [80], 11 of the 14 tactics fall under the post-exploitation phase (excluding reconnaissance, resource development, and initial access). In contemporary attack scenarios, particularly Advanced Persistent Threats (APTs), post-exploitation has evolved into a sophisticated process combining both malicious exploits and benign system interactions. Attackers typically operate under constrained privileges initially and must carefully orchestrate multi-step attack chains to reach their goals. These chains often leverage system misconfigurations, insecure permissions, vulnerable software versions, and legitimate system utilities in creative combinations. For instance, attackers might abuse sudo misconfigurations, hijack shared library loading mechanisms, exploit cron job vulnerabilities, or manipulate environment variables to escalate privileges. The complexity of modern operating systems creates numerous potential attack vectors during post-exploitation. File system permissions, user-group relationships, process capabilities, scheduled tasks, and service configurations all present opportunities for privilege escalation and persistence. What makes post-exploitation particularly challenging for defenders is that these attack chains often blend malicious actions with legitimate system operations, making detection through conventional security mechanisms difficult. Understanding these complex interactions requires a systematic analysis of the host environment and the potential pathways an attacker could leverage to advance their position. A PPENDIX B F ORMAL P LANNING D EFINITIONS AND PDDL S PECIFICATION A. Formal Planning Problem A classical planning problem is typically defined by the tuple < S, A, γ, so , SG >, where S represents the set of all possible states, A is the set of available actions, γ : S ×A → S is the state transition function, so ∈ S is the initial state, and SG ∈ S is the set of goal states. A solution to such a problem is a sequence of actions < a1 , a2 , ..., an > that, when applied in sequence starting from so , results in a state sn ∈ SG . B. PDDL Domain and Problem Specification The Planning Domain Definition Language (PDDL) [81] provides a standardized formalism for describing planning problems through domain and problem files. The domain file defines the static structure using objects (e.g., users, groups, different types of files, and file system permissions), predicates representing system facts (e.g., file capabilities, content relationships), and actions modeling state transitions. Each action specifies parameters, preconditions (conditions required for execution), and effects (fact changes after execution). In our work, the domain file (domain.pddl) is heuristically defined based on our analysis of post-exploitation behaviors, formally capturing the objects, facts, and actions relevant to host-level attacks.

14

Predicates describe the facts that hold in a given state. In PDDL syntax, a predicate takes the form (predicate_name ?arg1 - type1 ?arg2 type2 ...) where ?arg denotes a variable (parameter) of the specified type. For instance, (user_write_access ?u - user ?g - group ?f - file) indicates that user ?u in group ?g has write access to file ?f. When all variables are instantiated with concrete objects (e.g., (user_has_access_write alice developers config.txt)), the predicate becomes a grounded fact that is either true or false in a particular state. Actions model state transitions with the following components: (1) Parameters (?var - type): Variables that must be instantiated with concrete objects; (2) Precondition: A logical formula that must hold true in the current state for the action to be applicable. (3)Effect: Changes to the state when the action is executed, adding (and (predicate ...)) or removing (and (not (predicate ...))) facts. The problem file instantiates the domain with concrete objects (specific files, users, etc.), defines the initial state through grounded predicates describing the current system configuration, and specifies the goal condition representing the attacker’s objective. APEX automatically generates this problem file by retrieving the state of the target host, including the file system, the relationships between user groups, and the executable properties, during the post-exploitation phase with limited privileges. A PPENDIX C E XTENDED M OTIVATION E XAMPLE This appendix provides the detailed example referenced in the Motivation & Threat Model section of the main manuscript to illustrate the complexity of modern post-exploitation attack chains. Consider a privilege escalation scenario on a Linux system, where an attacker operates solely with the initial privileges of a low-privileged user (user_a): 1) Benign Enumeration: The attacker begins by understanding the automated processes on the system. They list the cron jobs and discover that user user_b has a scheduled task that periodically executes a backup script located at /home/user_b/scripts/backup.sh. Crucially, this script is configured to run with root privileges via sudo without a password. 2) Vulnerability Discovery: The attacker inventories the system for vulnerable software. A critical finding emerges: the system’s gzip binary (/bin/gzip) is version 1.11. This version is known to be affected by CVE2022-1271, an arbitrary file write vulnerability that allows attackers to write arbitrary content to any file location accessible by the user running gzip. 3) Malicious Orchestration: Leveraging this vulnerability, the attacker crafts an exploit. They use the gzip -N command with specially crafted input to directly append malicious shell commands to the privileged script backup.sh. The exploit carefully constructs the payload to ensure the appended content constitutes valid shell commands that will execute during the script’s next run.

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

4) Benign Trigger: The attacker waits for the scheduled cron job to execute. The cron daemon runs /home/user_b/scripts/backup.sh with root privileges. The script now executes both its legitimate backup operations and the malicious payload appended by the attacker. 5) Privilege Escalation: The malicious payload executes in the context of the root-privileged process, immediately granting the attacker a root shell on the system. This attack chain exemplifies the core challenge in modern post-exploitation: successful attacks are rarely about a single vulnerability. Instead, they are sophisticated sequences that strategically chain together system misconfigurations, versionspecific software vulnerabilities, and benign and malicious actions. It is the intricate interplay and specific combination of these distinct elements—each potentially harmless on its own—that creates a viable path to a critical security objective. A PPENDIX D D ESIGN P RINCIPLES D ETAILED E XPLANATION A. Formal Abstraction Principle We identify the minimal yet sufficient set of PDDL constructs to capture post-exploitation mechanics, ensuring all reasoning is logically sound, reproducible, and free from ambiguities of natural language or ad-hoc scripting. B. Phase-Guided Search Principle By observing that post-exploitation actions naturally progress through semantically meaningful phases, we incorporate this structure into the search strategy. Phase-specific constraints and heuristics prune irrelevant branches early, dramatically improving computational efficiency and focusing exploration on promising avenues. C. Hybrid Solving Principle Our approach synergistically combines symbolic AI planning with probabilistic search. We leverage planners for welldefined sub-problems within phases while using MCTS for high-level strategy management, achieving both rigor in constraint satisfaction and exploratory power in large state spaces. D. Minimal Interference Principle During information collection, APEX operates under strict read-only mandates: no file creation/modification/deletion, no service/process manipulation, and no configuration alterations. This ensures passive, forensically quiet assessment safe for production environments. A PPENDIX E M ODELING P HILOSOPHY D ETAILS A. Attack Surface Details For each of the seven attack surfaces: • File system permissions and ownership: The foundational layer of Unix security. Without modeling permissions, we cannot reason about whether an attacker can read, write,

15

or execute files—the basic building blocks of any attack chain. • Process execution and privilege inheritance: Processes are the vehicles through which attackers execute code. Modeling process creation, ownership, and SUID/SGID behavior is essential for capturing privilege escalation. • Automated execution mechanisms: Cron jobs, systemd services, and other scheduled tasks represent critical pivots—they execute with specific privileges at predictable times, making them prime targets for persistence and privilege escalation. • Dependency relationships: Shared libraries, configuration files, and script inclusions create implicit trust relationships. An attacker controlling a loaded file can influence the loader’s behavior—a common exploitation pattern. • Software vulnerabilities: Known CVEs provide capabilities that bypass normal permission checks. Integrating CVE knowledge allows the model to capture real-world exploit chains combining misconfigurations with vulnerabilities. • User and group relationships: Unix privilege models are fundamentally based on user and group memberships. Modeling these relationships is necessary for understanding permission inheritance and group-based privilege escalation. • Data movement capabilities: File upload and download represent basic attacker capabilities for payload delivery and data exfiltration. B. Omitted Aspects This model deliberately omits: vulnerability exploitation process, network stack states, specific memory layouts, kernel internals, and fine-grained process scheduling. These are not required for reasoning about the logical dependency chains of file permissions, user contexts, and automated executions that define host-level post-exploitation. A PPENDIX F PDDL D OMAIN D ETAILS Predicates (State Properties). Predicates describe the facts that hold in a given state. In PDDL syntax, a predicate takes the form (predicate_name ?arg1 type1 ?arg2 - type2 ...) where ?arg denotes a variable (parameter) of the specified type. For instance, (user_write_access ?u - user ?g - group ?f - file) indicates that user ?u in group ?g has write access to file ?f. When all variables are instantiated with concrete objects (e.g., (user_has_access_write alice developers config.txt)), the predicate becomes a grounded fact that is either true or false in a particular state. We define a comprehensive set of 30 predicates and categorize them into five functional groups: (1) Capability Predicates (11 predicates) describe what executables can perform, either through native functionality or known vulnerabilities. This includes basic operations like file manipulation (can_read/write/upload/download_file,

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

can_change_file_onwer, can_change_file_permission), system interaction capabilities (can_exec_cmd, can_shell), and vulnerability-based predicates (has_cve_cmd_inject, has_cve_any_write/read) that model CVE exploits bypassing normal permission checks. These predicates abstract implementation details, focusing on the effects executables can achieve. (2) Privilege and Control Predicates (4 predicates) track the attacker’s progress and system privilege structure. Key predicates include attacker_control (indicating which users are under attacker control), user_is_admin (administrative privilege status), user_in_group (membership relationships), and group_is_admin (group-level administrative privileges). (3) File System Predicates (11 predicates) capture static properties and dynamic state of the file system. These include permission matrices (user/group_has_file_perm), ownership (file_belongs_to), content storage (file_contains), and special file properties enabling specific attack vectors: has_suid_flag (SUID binaries), scheduled_exec_by_user (cron/scheduled tasks), exec_auto_loads_file (auto-loaded dependencies), and is_daemon_file (service management files). State tracking predicates (file_was_read, file_was_uploaded, file_was_downloaded) record file access for exfiltration analysis. (4) Process Execution Predicate (1 predicate) process_running models runtime state by serving as an execution token: it represents that process ?p is running with user ?u executing binary ?e. This design enforces realistic sequencing—actions requiring active process contexts consume this token, while process creation actions generate it. (5) Derived Capability Predicates (3 predicates) compute effective permissions from base predicates (user_has_read/write/exec_access). These are not directly asserted but derived through axiom actions that consolidate all permission sources: direct user permissions, group permissions, ownership, and administrative overrides. Actions (State Transitions). The domain includes 19 actions modeling state transitions available to the attacker, categorized by their primary purpose: (1) Process Execution Actions (3 actions) establish and leverage execution contexts. launch_process creates basic process tokens, while launch_suid_process enables SUID-based privilege escalation—if an attacker-controlled user can execute a SUID binary, they obtain a process running as the binary’s owner. launch_shell_grant_control directly grants user control when a shell-capable process is executed. (2) File Manipulation Actions (7 actions) modify file system state. write_file allows writing data to writable files using appropriate executables, while cve_write_any_file bypasses permission checks via arbitrary-write vulnerabilities. read_file and cve_read_any_filecaptures file reading for information gathering, and propagate_loaded_content models

16

dependency chain exploitation—if an executable always loads a file, controlling that file’s contents effectively controls the loader (e.g., .bashrc hijacking). download_file creates attacker-owned files locally, while upload_file marks files as exfiltrated to remote systems. (3) System Configuration Actions (4 actions) alter access controls and system state. set_suid_flag allows setting SUID bits (post-escalation backdoor creation), change_file_owner modifies ownership, and add_default_perm adds default permissions to owned files. hijack_scheduled_exec exploits scheduled tasks: writing a malicious payload to an executable systematically called by another user grants control of that user when the task executes. (4) Derivation and Capability Propagation Actions (5 actions) automatically infer facts when preconditions are met. These include permission derivation axioms (derive_read/write/exec_access) that compute effective access rights from multiple permission sources. Capability propagation actions model logical relationships: derive_cmd_implies_caps establishes that arbitrary command execution implies multiple other capabilities, while derive_launch_shell transforms payloads into a shell-spawning capability. A PPENDIX G S CRIPT I MPLEMENTATION D ETAILS The information extraction is organized into five core categories, each fulfilling specific requirements of the modeling philosophy and domain definition: (1) Identity and Privilege Context – This corresponds to the user and group relationships attack surface identified in the modeling philosophy. The scripts enumerate all system users and groups from /etc/passwd and /etc/group, establishing the concrete user and group objects for the domain. We further parse membership relationships to instantiate the user_in_group predicate and identify the current execution context to initialize the attacker_control predicate for the foothold user. (2) File System State – This addresses the file system permissions, ownership, and process execution and privilege inheritance attack surfaces. The collection phase discovers all files in critical directories (/bin, /usr/bin, /home, etc.), classifies them into the domain’s type hierarchy (executable, sharedfile, regular file), and extracts their security metadata. This includes octal permissions (grounding the user_has_file_perm and group_has_file_perm predicates), ownership information (for file_belongs_to), and special permission flags like SUID/SGID (for has_suid_flag). (3) System Dynamics – This operationalizes the automated execution mechanisms and dependency relationships components of the modeling philosophy. The scripts identify all scheduled execution mechanisms: cron jobs (from /etc/crontab) and systemd services (from /etc/systemd/), creating calledexecutable objects and asserting the scheduled_exec_by_user predicate. We

APEX: AUTOMATED POST-EXPLOITATION ATTACK CHAIN EXPLORATION

also map dependency chains by analyzing shared library loads and shell configuration files (e.g., .bashrc, .profile), establishing facts for the exec_auto_loads_file predicate that enables modeling of library hijacking and shell initialization attacks. (4) Software Vulnerability Context – This implements the software vulnerabilities dimension of the attack surface model. The scripts query version information for discovered executables and validate them against a knowledge base of known CVEs. When an executable matches a vulnerable version pattern and satisfies all dependency conditions, the corresponding CVE capability predicate (e.g., has_cve_any_write, has_cve_cmd_inject) is asserted in the problem state, enabling the planner to reason about exploit chains. (5) Capability Derivation Primitives – Supporting the data movement capabilities and the efficient permission derivation strategy outlined in the domain model, the scripts identify writable files and directories not owned by the current user. This information, while not directly mapping to a single predicate, provides the raw data from which the derived capability predicates (user_has_access_read/write/exec) can be computed by the planner’s axiom actions, avoiding the storage of a quadratic number of permission facts. A PPENDIX H R EPORT G ENERATION D ETAILS LLM Prompt Template and Example. Our LLM prompt transforms filtered formal PDDL attack chains into actionable natural language reports. A. Input: PDDL Attack Chain Example (Docker Group Escalation) 1: (launch_process ec2-user_u docker_g usr_bin_docker process1) 2: (write_file process1 usr_bin_docker etc_systemd_system_cloud-logger_timer shell_payload local ec2-user_u docker_g) 3: (spawn_shell_grant_control etc_systemd_system_cloud-logger_timer root_u process2)

PDDL Object Explanations: • ec2-user_u: The default EC2 user account. • docker_g: Docker group. • etc_systemd_system_cloud-logger_timer: Systemd timer file scheduled for execution by ec2-user. • usr_bin_docker: Docker binary at /usr/bin/docker. • root_u: Root user account. B. LLM Prompt Template Analyze this PDDL attack chain and generate a security report: PDDL ATTACK CHAIN: [insert PDDL sequence here]

17

REPORT REQUIREMENTS: 1. ATTACK WALKTHROUGH: Translate each PDDL action into natural language, explaining what the attacker does at each step. 2. MITIGATION RECOMMENDATIONS: Provide specific, actionable defensive measures. Include concrete commands or configuration changes. Include metadata: number of steps, attacker skill level required, and overall risk assessment.

C. Output: Generated Natural Language Report Attack Walkthrough: 1) Step 1: The attacker spawns a Docker process leveraging their group membership. 2) Step 2: Using Docker’s host filesystem mounting capability, the attacker modifies the systemd timer file to include a malicious payload while maintaining the file’s root execution context. 3) Step 3: When the systemd timer triggers, it executes the modified script with root privileges, granting the attacker a root shell. Mitigation Recommendations: • File Permissions: Secure systemd timer file: sudo chown root:root /etc/systemd/system/ cloud-logger.timer sudo chmod 644 /etc/systemd/system/ cloud-logger.timer • •

Group Policy: Restrict docker group to trusted users only Monitoring: Implement auditing for systemd file modifications: sudo auditctl -w /etc/systemd/system/ -p wa -k systemd_files

•

Docker Hardening: Implement Docker daemon security options: # In /etc/docker/daemon.json { "authorization-plugins": ["cayley"], "userns-remap": "default", "no-new-privileges": true }

Chain Metadata: • Steps: 3 • Attacker skill: Intermediate (requires Docker knowledge) • Risk level: Critical (direct path from default user to root) • CVSS Estimate: 8.8 • Impact: Complete system compromise

Related documents

• Towards Behavior Tree-Guided Vulnerability Detection with Lightweight LLMs#632795
• Automated Post-Exploitation Attack Chain Exploration Based on a Phase-guided Hybrid Planning-Monte Carlo Tree Search Algorithm#1447645
• StarOR: Synergizing Tree Search and Test-Time Reinforcement Learning for Optimization Modeling#1116335
• Object-to-Source Mapping under Optimization: What a Control-Flow Trace Can Show, and Where Source-Level Coverage Breaks#1077584
• THE-Planner: Topological and Hierarchical Exploration Path Planner for Fast 3D Mapping of Outdoor Structures with UAVs#472150