An approach to incorporating uncertainty in network security analysis

Hoang Hai Nguyen, Kartik Palani, David M. Nicol

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Attack graphs used in network security analysis are analyzed to determine sequences of exploits that lead to successful acquisition of privileges or data at critical assets. An attack graph edge corresponds to a vulnerability, tacitly assuming a connection exists and tacitly assuming the vulnerability is known to exist. In this paper we explore use of uncertain graphs to extend the paradigm to include lack of certainty in connection and/or existence of a vulnerability. We extend the standard notion of uncertain graph (where the existence of each edge is probabilistically independent) how- ever, as significant correlations on edge existence probabilities exist in practice, owing to common underlying causes for dis-connectivity and/or presence of vulnerabilities. Our extension describes each edge probability as a Boolean expression of independent indicator random variables. This paper (i) shows that this formalism is maximally descriptive in the sense that it can describe any joint probability distribution function of edge existence, (ii) shows that when these Boolean expressions are monotone then we can easily perform uncertainty analysis of edge probabilities, and (iii) uses these results to model a partial attack graph of the Stuxnet worm and a small enterprise network and to answer important security-related questions in a probabilistic manner.

Original languageEnglish (US)
Title of host publicationHoTSoS 2017 - Symposium and Bootcamp
Subtitle of host publicationHot Topics in the Science of Security
PublisherAssociation for Computing Machinery
Number of pages11
ISBN (Electronic)9781450352741
StatePublished - Apr 4 2017
Event4th Annual Symposium and Bootcamp on Hot Topics in the Science of Security, HoTSoS 2017 - Hanover, United States
Duration: Apr 4 2017Apr 5 2017

Publication series

NameACM International Conference Proceeding Series
VolumePart F127186


Other4th Annual Symposium and Bootcamp on Hot Topics in the Science of Security, HoTSoS 2017
Country/TerritoryUnited States


  • Attack graphs
  • Network security
  • Uncertainty analysis

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'An approach to incorporating uncertainty in network security analysis'. Together they form a unique fingerprint.

Cite this