Automatic discovery of attack messages and pre- and post-conditions for attack graph generation

Network attack graphs are directed graph-representations of possible attack paths and vulnerabilities in a computer network. Each attack path is a sequence of steps taken by an attacker to achieve one or more goals in the target system. While there are some variations in the representations of the graph proposed by different researchers, typically the edges represent possible actions (or exploits) available to an attacker, and vertices represent the possible states for the system and applications. Attack graphs are often manually created or, less often, automatically generated from a set of attack models and detailed information about the network topology and its applications. There have been several proposals for the automatic identification and representation of attack models, but they all rely on some prerequisite knowledge of the pre- and post-conditions for the different attack steps. A pre-condition may include requirements such as "attacker must have root privileges", while a post-condition defines the state of the system after an action is taken. In this paper we propose algorithms for the automatic identification of likely pre- and post-conditions that can be used for the generation of attack graphs. Our approach extracts such candidate conditions from observational data. By monitoring low-level events on multiple network nodes, in correlation with detected anomalies or attacks, our approach can automatically and unobtrusively identify the attributes of interest for the attack model required for attack graph generation. The paper provides a brief review of the requirements for automatic attack graph generation, and describes our proposed approach in detail. We also present preliminary simulation results for the automatic discovery of attack messages and their pre- and post-conditions, in a simplified fully connected network environment.