Acdzero Achieves Sample-Efficient Cyber Defense with Graph-Embedding Tree Search

Automated cyber defence aims to safeguard computer systems with limited human involvement, responding to attacks through actions like host isolation and access control updates. Current methods, including reinforcement learning, struggle with the vast decision spaces inherent in complex networks, demanding substantial computational resources. Yu Li, Sizhe Tang, and Rongqian Chen, from the Department of ECE at George Washington University, alongside Fei Xu Yu, Guangyu Jiang, and Mahdi Imani et al., address this challenge by reframing cyber defence as a context-based decision problem. Their research introduces ACDZero, a novel planning-centric defence policy utilising Monte Carlo Tree Search and innovative graph neural networks. By embedding network observations into attributed graphs, ACDZero facilitates more effective reasoning and significantly improves both the reward and robustness of automated defence strategies when tested against diverse adversarial behaviours.

Learned Models Enable General Game-Playing AI

This research details a reinforcement learning algorithm that learns a model of the game environment and uses this model to plan ahead, achieving superhuman performance in Atari, Go, Chess, and Shogi. This approach differs from previous methods that relied heavily on either handcrafted features or extensive training data. The core idea centres on a general algorithm capable of adapting to different games with minimal modifications. The agent learns a model predicting the next state and reward given the current state and action, trained using supervised learning from self-play. The agent achieved superhuman performance in Go, Chess, and Shogi, and demonstrated strong performance on a range of Atari games, often exceeding human-level play. This was accomplished with significantly less training data than previous methods, highlighting the power of combining a learned model with MCTS for effective planning and informed decision-making in complex situations. The research demonstrates a significant advancement in reinforcement learning, showcasing the potential for broader applications in artificial intelligence.

Graph Neural Networks Guide Cyber Defence Planning

A novel approach to automated cyber defence has been engineered, framing the challenge as a context-based partially observable Markov decision problem. The study pioneers the use of graph neural networks (GNNs) to embed observations as attributed graphs, enabling permutation-invariant reasoning over hosts and their relationships. To address computational demands, the search process is guided with learned graph embeddings and priors over graph-edit actions, combining model-free generalization and policy distillation with look-ahead planning.

The experimental setup uses a Decentralized Partially Observable Markov Decision Process, defining agents, states, actions, observations, transition functions, rewards, and a discount factor. A specialized Environment Interface translates simulation data into graph-based representations for the policy architecture. This interface transforms local observations into attributed graphs representing hosts, subnets, ports, and files, each encoded with attributes like OS metadata and process information. Inter-agent communication is integrated by parsing messages and encoding them as features of subnet nodes, facilitating coordination.

Actions are abstracted into graph operations, allowing the system to adapt to varying network topologies. The resulting agent, termed ACDZERO, utilizes a MuZero-like framework, employing MCTS as a policy improvement operator for a GNN-based PPO agent. ACDZERO models network state evolution as transitions within a latent search tree, initialized with a GNN-based representation network processing observation history. A two-stage hierarchical aggregation process creates representations invariant to node permutations and network size. The dynamics function predicts subsequent latent states based on current states and actions, utilizing a GRU to capture temporal dependencies. The research addresses sample efficiency in complex cybersecurity environments, framing the problem as a context-based partially observable Markov decision process within the CAGE-4 (CC4) challenge. Explicitly modelling the exploration-exploitation tradeoff, coupled with statistical sampling, substantially guides exploration and decision-making. The team measured performance on CC4 scenarios with diverse network structures and adversarial behaviours, demonstrating a marked improvement in defense reward and robustness compared to state-of-the-art reinforcement learning baselines.

The work introduces a novel use of graph neural networks to embed observations from attributed graphs, enabling permutation-invariant reasoning over hosts and their relationships, a critical step in handling dynamic network topologies. This allows the system to function effectively with varying numbers of hosts and active services. The system constructs semantically rich attributed graphs from local observations, representing network entities as typed nodes , Hosts, Subnets, Ports, and Files , each with attributes like OS metadata and process information. Categorical attributes are one-hot encoded, and inter-agent communication is integrated by parsing messages into features of Subnet nodes, facilitating implicit coordination.

Simulator actions are abstracted into graph operations, allowing defensive measures to target Host nodes and network traffic control to modify edges between subnet nodes. This decoupling enables seamless adaptation to variable network topologies. The breakthrough delivers a framework, termed ACDZERO, which employs MCTS as a policy improvement operator, enhancing a GNN-based PPO agent and generating improved policy and value estimates distilled into decentralized actor-critic networks. This approach addresses challenges in dynamic network environments, specifically topology generalization and multi-step reasoning, by integrating the representational flexibility of graph networks with the deliberative capabilities of tree search. This combination achieves robust performance across diverse network configurations while maintaining computational efficiency for real-time deployment. Evaluations on the CAGE Challenge 4 demonstrate a significant performance improvement of 29.2% over the existing state-of-the-art GCN baseline, with faster convergence , a 25% reduction in training time , and reduced variance, measured at 5.8% lower than the baseline.

The authors acknowledge limitations in relying on fully observable graphs and highlight potential extensions to the method. Another promising avenue involves learning a graph-based dynamics model from offline trajectories generated by existing defence systems, potentially reducing the need for costly online interaction while preserving the system’s adaptive planning abilities.