Analysis of Stepping Stone Attacks in Dynamic Vulnerability Graphs

Gamarra, M., Shetty, S., Gonzalez, O., Nicol, D.M., Kamhoua, C., and Njilla, L.

To appear, IEEE ICC 2018 Communication and Information Systems Security Symposium. Kansas City, MO. May 20-24, 2018. 


Vulnerability graphs have been employed as an effective tool for analyzing exploitability and the impact of chains of exploits in networked environments. The attack graphs are created by a chain of “stepping stones” from the attacker origin to the desired target. The stepping stones not only provide the intermediate steps to reach the target, but also make it difficult to identify the attacker’s true location. In this paper, we model and analyze stepping stones in dynamic vulnerability graphs. Most analysis based on attack graphs assume that the graph edges and weights remain constant during the attacker’s attempt to propagate through the network. We propose a biased minconsensus technique for dynamic graphs with switching topology as a distribute the technique to determine the attack paths with more probable stepping stones in dynamic vulnerability graphs. We use min-plus algebra to determine the necessary and sufficient convergence conditions. A Necessary condition for convergence to the shortest path in the switching topology case is provided.

Publication Status:
To Appear
Publication Type:
Publication Date:
Copyright Notice:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

  1. The following copyright notice applies to all of the above items that appear in IEEE publications: "Personal use of this material is permitted. However, permission to reprint/publish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from IEEE."

  2. The following copyright notice applies to all of the above items that appear in ACM publications: "© ACM, effective the year of publication shown in the bibliographic information. This file is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the journal or proceedings indicated in the bibliographic data for each item."

  3. The following copyright notice applies to all of the above items that appear in IFAC publications: "Document is being reproduced under permission of the Copyright Holder. Use or reproduction of the Document is for informational or personal use only."