Cutting Medusa's Path -- Tackling Kill-Chains with Quantum Computing

Abstract

This paper embarks upon exploration of quantum vulnerability analysis. By introducing vulnerability graphs, related to attack graphs, this paper provides background theory and a subsequent method for solving significant cybersecurity problems with quantum computing. The example given is to prioritize patches by expressing the connectivity of various vulnerabilities on a network with a QUBO and then solving this with quantum annealing. Such a solution is then proved to remove all kill-chains (paths to security compromise) on a network. The results demonstrate that the quantum computer's solve time is almost constant compared to the exponential increase in classical solve time for vulnerability graphs of expected real world density. As such, this paper presents a novel example of advantageous quantum vulnerability analysis.