K Maximum Probability Attack Paths Dynamic Generation Algorithm

Kun Bi1, Dezhi Han1 and Jun Wang1

  1. College of Information Engineering, Shanghai Maritime University
    Shanghai 201306, China
    kunbi@shmtu.edu.cn, dezhihan88@sina.com, jwang@eecs.ucf.edu


An attack graph depicts multiple-step attack and provides a description of system security vulnerabilities. It illustrates critical information necessary to identify potential weaknesses and areas for enhanced defense. Attack graphs include multiple attack paths, which are a focus for further detailed analysis and risk mitigation. Considering that different vulnerabilities have different probabilities of being exploited, this paper proposes an algorithm to dynamically generate the top K attack paths with maximum probabilities for every node of a system. The proposed algorithm does not require generation of the full attack graph to calculate the K attack paths. Instead, it directly processes and analyzes the system input data and dynamically identifies the K attack paths. The computational time, based upon the complexity of the attack paths, can be constrained by the parameter K. Experimental results show that the algorithm is scalable and efficient.

Key words

attack path, attack graph, K shortest paths, system security, network security

Digital Object Identifier (DOI)


Publication information

Volume 13, Issue 2 (June 2016)
Year of Publication: 2016
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Bi, K., Han, D., Wang, J.: K Maximum Probability Attack Paths Dynamic Generation Algorithm. Computer Science and Information Systems, Vol. 13, No. 2, 677–689. (2016)