Reasoning Under Uncertainty in Cyber-Physical Systems: Toward Efficient and Secure Operation

Abstract

The increased sensing, processing, communication, and control capabilities introduced by cyber-physical systems bring many potential improvements to the operation of society's systems, but also introduce questions as to how one can ensure their efficient and secure operation. This dissertation investigates three questions related to decision-making under uncertainty in cyber-physical systems settings.

First, in the context of power systems and electricity markets, how can one design algorithms that guide self-interested agents to a socially optimal and physically feasible outcome, subject to the fact that agents only possess localized information of the system and can only react to local signals? The proposed algorithms, investigated in the context of two distinct models, are iterative in nature and involve the exchange of messages between agents. The first model consists of a network of interconnected power systems controlled by a collection of system operators. Each system operator possesses knowledge of its own localized region and aims to prescribe the cost minimizing set of net injections for its buses. By using relative voltage angles as messages, system operators iteratively communicate to reach a social-cost minimizing and physically feasible set of injections for the whole network. The second model consists of a market operator and market participants (distribution, generation, and transmission companies). Using locational marginal pricing, the market operator is able to guide the market participants to a competitive equilibrium, which, under an assumption on the positivity of prices, is shown to be a globally optimal solution to the non-convex social-welfare maximization problem. Common to both algorithms is the use of a quadratic power flow approximation that preserves important non-linearities (power losses) while maintaining desirable mathematical properties that permit convergence under natural conditions.

Second, when a system is under attack from a malicious agent, what models are appropriate for performing real-time and scalable threat assessment and response selection when we only have partial information about the attacker's intent and capabilities? The proposed model, termed the dynamic security model, is based on a type of attack graph, termed a condition dependency graph, and describes how an attacker can infiltrate a cyber network. By embedding a state space on the graph, the model is able to quantify the attacker's progression. Consideration of multiple attacker types, corresponding to attack strategies, allows one to model the defender's uncertainty of the attacker's true strategy/intent. Using noisy security alerts, the defender maintains a belief over both the capabilities/progression of the attacker (via a security state) and its strategy (attacker type). An online, tree-based search method, termed the online defense algorithm, is developed that takes advantage of the model's structure, permitting scalable computation of defense policies.

Finally, in partially observable sequential decision-making environments, specifically partially observable Markov decision processes (POMDPs), under what conditions do optimal policies possess desirable structure? Motivated by the dynamic security model, we investigate settings where the underlying state space is partially ordered (i.e. settings where one cannot always say whether one state is better or worse than another state). The contribution lies in the derivation of natural conditions on the problem's parameters such that optimal policies are monotone in the belief for a class of two-action POMDPs. The extension to the partially ordered setting requires defining a new stochastic order, termed the generalized monotone likelihood ratio, and a corresponding class of order-preserving matrices, termed generalized totally positive of order 2.