A Weighted Model Counting Approach for Critical Infrastructure Reliability

Reliability assessment of engineered systems such as telecommunication networks, power grids, and railroads is an important step towars supporting resilient communities. However, calculating the reliability of a network is computationally intensive. Thus, simulation methods are often preferred over exact methods in practice. Unfortunately, highly reliable and large scale systems can challenge common assumptions in simulation techniques, rendering reliability estimates—as well as reported error and confidence—unreliable themselves. A new generation of techniques, termed probably approximately correct (PAC) methods, delivers provable network reliability calculations with user-specified error and confidence. In this paper we focus on RelNet, a model counting-based method for network reliability estimation endowed with rigorous PAC guarantees. Despite previous success in power transmission network applications, small edge failure probabilities and dependent failures can challenge the current methodology. We put forward Weighted RelNet, a general importance sampling-based extension that treats the systems joint probability distribution as a black box. Empirical evaluations suggest the new approach is competitive across challenging rare-event benchmarks.The authors gratefully acknowledge the support by the U.S. Department of Defense (Grant W911NF-13-1-0340) and the U.S. National Science Foundation (Grants CMMI-1436845 and CMMI-1541033)