Scalable attack graph for risk assessment
Je-Hyun Lee, Heejo Lee, Hoh Peter In · International Conference on Information Networking · 2009
The growth in the size of networks and the number of vulnerabilities is increasingly challenging to manage network security. Especially, difficult to manage are multi-step attacks which are attacks using one or more vulnerabilities as stepping stones. Attack graphs are widely used for analyzing multi-step attacks. However, since these graphs had large sizes, it was too expensive to work with. In this paper, we propose a mechanism to manage attack graphs using a divide and conquer approach. To enhance efficiency of risk analyzer working with attack graphs, we converted a large graph to multiple sub-graphs named risk units and provide the light-weighted graphs to the analyzers. As a result, when k order of time complexity algorithms work with an attack graph with n vertices, a division having c of overhead vertices reduces the workloads from nk to r(n + c)k. And the coefficient r becomes smaller geometrically from 2−kdepended on their division rounds. By this workload reduction, risk assessment processes which work with large size attack graphs become more scalable and resource practical.