TY - GEN
T1 - Scalable attack graph for risk assessment
AU - Lee, Jehyun
AU - Leet, Heejo
AU - In, Hoh Peter
PY - 2009
Y1 - 2009
N2 - 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-k depended on their division rounds. By this workload reduction, risk assessment processes which work with large size attack graphs become more scalable and resource practical.
AB - 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-k depended on their division rounds. By this workload reduction, risk assessment processes which work with large size attack graphs become more scalable and resource practical.
UR - http://www.scopus.com/inward/record.url?scp=77951428960&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77951428960&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:77951428960
SN - 9788996076131
T3 - 2009 International Conference on Information Networking, ICOIN 2009
BT - 2009 International Conference on Information Networking, ICOIN 2009
T2 - 2009 International Conference on Information Networking, ICOIN 2009
Y2 - 21 January 2009 through 24 January 2009
ER -