AI Planning in Cybersecurity
We introduce the notion of Attack-Connectivity Graph (ACG) that allows us to perform simultaneous modeling of attack paths and network connectivity. In this formalization, we obviate the need for traditional monotonicity assumptions of attack graphs. We show how ACG can be captured us- ing AI planning models. We provide complexity results for this process.
Attack graphs have been widely used to help the cyber defender understand how a networked system can be attacked and how defenses can be deployed. However, previous works have relied on access to some complete and correctly specified cost model for potential hardening/interdiction actions. Unfortunately, for very large-scale cyber systems, collecting a complete specification is infeasible. Thus, it is important to have an interactive system that allows the user to provide input and generate the best possible security hardening solutions. This requires the system be able to correctly interpret human instructions, and propose efficient courses of action. We propose two strategies to address this problem. First, we identify a set of diverse security hardening strategies that can be presented to the administrator. Second, we provide the administrators the ability to ask for explanations as to why a proposed strategy best meets their goals. The two strategies together allow the administrator to explore the solution space in a systematic fashion and help illustrate the impact of each proposed strategy. Our approach, called iEXAM, automatically converts network configurations and vulnerability descriptions into planning models expressed in Planning Domain Definition Language. This allows us to leverage highly scalable AI planners for various analyses, empowering iEXAM to scale to large networks.