Graph similarity metrics for assessing temporal changes in attack surface of dynamic networks

Assessment of attack surface is a formidable challenge for the present-day dynamic networks. Essentially, attack surface (of a computer network) is a subset of network configuration and vulnerabilities that an adversary can use to compromise the target network in an incremental fashion. There are a large number of metrics available for network security risk assessment. However, they fail to measure temporal variation in the network attack surface. To overcome this problem, we propose graph distance metrics based on the Maximum Common Subgraph (MCS) and Graph Edit Distance (GED). In particular, we make use of classical graph distance metrics to quantify the distance between a pair of successive attack graphs generated for a dynamic network. Since the attack graph is capable of successfully capturing the attack surface of an underlying network, the distance between a pair of consecutive attack graphs (generated over the observed sampling interval) indicates the change in the network attack surface. To validate the efficacy and usability of graph distance metrics proposed in this study, we have tested 11 different metrics on a set of 3 different network models, viz., Flat, External-Internal, and DMZ. Experimental results show that MCS and GED based graph distance metrics successfully capture the temporal variation in the attack surface and also generate an alert about the security events which are responsible for the change. Using such graph distance metrics, we can pinpoint the events that cause a significant change in the network attack surface, locate most dangerous hosts in the network and the effect of increasing vulnerabilities further on these hosts. The advantage of using these metrics is that they scale polynomially with the graphs size and are independent of the graphs topology. It is also evident from the test results that the performance of MCS and GED based metrics is almost similar and hence the computation of one metric is enough to detect temporal variation in the network attack surface. The MCS and GED based graph distance metrics are oblivious to the AND semantic between the initial conditions in the attack graphs. Thus, there is a scope for improving their performance (sensitivity) by considering the AND semantic.