Limited Query Graph Connectivity Test
Authors: Mingyu Guo, Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We empirically demonstrate that our algorithm is scalable for a wide range of much larger practical graphs (i.e., graphs representing Windows domain networks with tens of thousands of edges). We also propose three heuristics. Our best-performing heuristic is via limiting the planning horizon of the exact algorithm. The other two are via reinforcement learning (RL) and Monte Carlo tree search (MCTS). We also derive an algorithm for computing the performance lower bound. Experimentally, we show that all our heuristics are near optimal. |
| Researcher Affiliation | Academia | Mingyu Guo, Jialiang Li, Aneta Neumann, Frank Neumann, Hung Nguyen School of Computer and Mathematical Sciences, University of Adelaide, Australia {mingyu.guo, j.li, aneta.neumann, frank.neumann, hung.nguyen}@adelaide.edu.au |
| Pseudocode | No | The paper describes algorithms conceptually and provides formal definitions (e.g., for the integer program) but does not include structured pseudocode blocks or figures labeled as such. |
| Open Source Code | No | The paper mentions external open-source tools like BLOODHOUND and IMPROHOUND in the introduction but does not state that the authors are providing open-source code for their own described methodology or implementation. |
| Open Datasets | Yes | We experiment on a wide range of practical graphs, including road and power networks (Davis and Hu 2011; Kunegis 2022; Rossi and Ahmed 2015; Watts and Strogatz 1998; Dembart and Lewis 1981), Python package dependency graphs (pydeps 2022), Microsoft Active Directory attack graphs (DBCreator 2022; Carolo 2022; Guo et al. 2022; Goel et al. 2022; Guo et al. 2023; Goel et al. 2023) and more (Allard et al. 2019). |
| Dataset Splits | No | The paper mentions various datasets but does not explicitly provide details about training, validation, and test splits (e.g., percentages, sample counts, or specific pre-defined split configurations) for their experiments. It only states, "For all experiments, we set p = 0.5. Sources and destinations are selected randomly." |
| Hardware Specification | No | The paper does not specify any hardware details (e.g., CPU, GPU models, memory, or cloud instances) used for running its experiments. |
| Software Dependencies | No | The paper mentions using Proximal Policy Optimization (PPO) and Soft Actor-Critic for Discrete Action, but it does not specify version numbers for these or any other software, libraries, or programming languages used in the experiments. |
| Experiment Setup | Yes | For all experiments, we set p = 0.5. Sources and destinations are selected randomly. For Microsoft Active Directory attack graphs, the destination is set to be the admin node representing the highest privilege. Our best-performing heuristic is via limiting the planning horizon of the exact algorithm. The other two heuristics are based on reinforcement learning (RL) and Monte Carlo tree search (MCTS), where the action space is reduced with the help of query limit. Specifically, we generate H1 s policy tree assuming a query limit of B . All edges referenced form the action space. The action space size is at most 2B 1. It is also not scalable to take the whole graph as observation. Fortunately, the query limit comes to assist. Our observation contains B 1 segments as there are at most B 1 past queries. Each segment contains 3 + (2B 1) bits. 3 bits are one hot encoding of query result (not queried yet, ON, OFF). 2B 1 bits encode the action. Since the action space always contains H1 s default action, in experiments, when we apply Proximal Policy Optimization (PPO) (Schulman et al. 2017), the agent ended up cloning H1 and we cannot derive better/new heuristics. We instead apply Soft Actor-Critic for Discrete Action (Christodoulou 2019), as it involves entropy maximisation, which encourages the agent to deviate from H1. We managed to obtain better policy than H1 on many occasions. Monte Carlo tree search: We use the same heuristic to limit the action space (same as RL). We apply standard epsilon-greedy Monte Carlo tree search. |