Two algorithms for Network Security Gradient marking

Attack graph increasingly becomes a key technique for network security analysis, however, the prevalent Attacker´s Ability Monotonic Assumption (AAMA) constraint for attack graph generation could not make full use of the direction of network attack and the hierarchy of defence. As a result, using AAMA is not efficient enough in the process of attack graph generation, especially for large-scale complicated network. With the aim of improving the efficiency of attack graph generation and reducing attack graph´s complexity, we proposed the concept of Network Security Gradient (NSG) to reflect the hierarchy of network defence, and the Gradient Attack Assumption (GAA) based on NSG to constraint the process of attack graph generation. To make our theory of NSG more sound and reasonable, we proposed two NSG marking algorithms, respectively from static analysis of network topology and dynamic analysis of network access flow, to rank network nodes automatically. Experiment results showed that both of the two algorithms can mark NSG for network correctly and rationally.