Abstract:

The attack graph model which uses the causal relationship between the attack steps to infer the attack progress from the initial state to the target state is a key method for network risk assessment. And the whole analysis process is based on the graph data expressed in formal style, but few uncertainty factors such as the uncertainty degree of the network link, network congestion, and intrusion alarm, are considered. Based on the concept of uncertain graphs, we expand the attack graph content to a possible attack graph, describe the construction method for the possible attack graph, and propose a maximum probability algorithm and an algorithm to find maximum possible attack paths based on reachability. Experimental results show that we can generate the possible attack graph within acceptable time, effectively speculate the attack intentions, and provide decision-making foundation for a network administrator.

Key words: uncertain graph, attack graph, possible worlds model, possible attack model, attack intent inferring