Visible to the public Uncertainty in Security Analysis - April 2019Conflict Detection Enabled

PI: David M. Nicol

Researcher: Hoang Hai Ngyuen

This refers to Hard Problems, released November 2012.

This research intersects the predictive security metric problem since we are attempting to predict uncertainty associated with a system model. It also intersects with resilience as a system's resilience will be established by analysis of some model and decisions (e.g., how significant breach may be, whether to interdict and where, where to focus recovery activity) will be made as a result. Those decisions will be better informed when some notion of uncertainty is built into the model predictions, or accompanies those model predictions.

Papers written as a result of your research from the current quarter only.

Hoang Hai Nguyen, Kartik Palani, and David M. Nicol, "Extensions of Network Reliability Analysis", 49th IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2019), Portland, OR, June 24-27, 2019, to appear.

Abstract: Network reliability studies properties of networks subjected to random failures of their components. It has been widely adopted to modeling and analyzing real-world problems across different domains, such as circuit design, genomics, databases, information propagation, network security, and many others. Two practical situations that usually arise from such problems are (i) the correlation between component failures and (ii) the uncertainty in failure probabilities. Previous work captured correlations by modeling component reliability using general Boolean expression of Bernoulli random variables. This paper extends such a model to address the second problem, where we investigate the use of Beta distributions to capture the variance of uncertainty. We call this new formalism the Beta uncertain graph. We study the reliability polynomials of Beta uncertain graphs as multivariate polynomials of Beta random variables and demonstrate the use of the model on two realistic examples. We also observe that the reliability distribution of a monotone Beta uncertain graph can be approximated by a Beta distribution, usually with high accuracy. Numerical results from Monte Carlo simulation of an approximation scheme and from two case studies strongly support this observation.

Each effort should submit one or two specific highlights. Each item should include a paragraph or two along with a citation if available. Write as if for the general reader of IEEE S&P.
The purpose of the highlights is to give our immediate sponsors a body of evidence that the funding they are providing (in the framework of the SoS lablet model) is delivering results that "more than justify" the investment they are making.

Our research focuses on understanding the network security risk and the uncertainty associated with the estimate when security properties of the network components are not exactly known. In previous study, we used Bernoulli random variables to model the existence of a link between two immediate hosts in the network, which indicates the possibility of a lateral movement [1]. Our current investigation generalized this model by modeling the uncertainty in the link existence using Beta distribution, a more versatile class of distributions that takes one of many different shapes depending on its two parameters.

Computing the existence of a pathway between two specifically chosen hosts (i.e. reachability analysis) in the generalized model reduces to identifying the reachability distribution, in the form of a multivariate reliability polynomial of Betas. This is a hard problem. However, our initial results highly suggest that in many cases, the reliability distribution can be well-approximated by another beta distribution. This observation aligns with several results from previous studies [2] [3] regarding approximating Betas. Our finding however applies to a much more general setup. The implication of this result is that under conditions in which the approximation is sufficiently good, the computational cost of reachability analysis can be significantly reduced.

[1] HH Nguyen, K Palani, DM Nicol, "An Approach to Incorporating Uncertainty in Network Security Analysis", Hot Topics in Science of Security: Symposium and Bootcamp (2017).

[2] Da-Yin Fan, "The Distribution of the Product of Independent Beta Variables", Communications in Statistics - Theory and Methods (1991).

[3] Saralees Nadarajah and Samuel Kotz, "Exact and Approximate Distributions for the Product of Dirichlet Components, Kybernetika 40.6 (2004).


No community engagements this quarter.


No educational advances this quarter.