Implementing an Attack Graph Generator in CUDA

Attack graphs can be used in security analysis for both computer networks and cyber physical systems to enumerate all possible attack paths. The main challenge in applying attack graphs is the design of scalable generators, which should construct large scale graphs within practical limits for execution time and storage resources. With the availability of high performance computing hardware, parallel computing units can be employed to accelerate the exploration of new states in attack graph generation. While NVIDIA's GPU devices have significantly improved the performance of other graph-oriented algorithms, there is little research using them on the generation of attack graphs. In this paper, we present a parallel attack graph generator based on NVIDIA's extension of C language: CUDA. To accelerate the exploration, the generator uses a large number of warps in the GPU device. Each warp is assigned with multiple initial states, which are then expanded by 32 in-warp threads. The performance experiments are conducted on a virtual machine instance providing a Tesla P4 GPU. The acceleration achieved demonstrates the effectiveness of using a large number of CUDA cores to accelerate the attack graph generator.