Workshop on Recent Advances on Intrusion-Tolerant Systems


March 23, 2007


Keynote speech


Automatic Recovery from Failures and Attacks Using
Bounded Partially Observable Markov Decision Processes

William H. Sanders

Donald Biggar Willett Professor of Engineering 
Director, Information Trust Institute 
University of Illinois at Urbana-Champaign


Providing high availability with acceptable cost is becoming increasingly critical in a wide variety of application domains. Automatic system monitoring, followed by diagnosis and recovery, has the potential to provide the required low-cost solution, high-availability solution that is needed in those domains. However, automating recovery is difficult in practical settings because of low coverage, poor localization abilities, false positives, and/or false negatives exhibited by many commonly used monitoring techniques. Furthermore, multiple recovery actions are often applicable even when the fault or attack can be correctly diagnosed, and the correct choice is not always obvious.  We present a holistic model-based approach that overcomes these challenges and enables automatic recovery in distributed systems. To do so, it uses theoretically sound techniques to provide controllers that choose good, if not optimal, recovery actions according to a user defined optimization criteria. The automatic recovery problem is framed as an undiscounted accumulated reward maximization problem on a structurally restricted class of partially observable Markov decision processes (POMDPs) that we call R-POMDPs. The resulting recovery controller can be proven to always terminate in a finite amount of time, to probabilistically not terminate before recovery is finished, and to generate recovery actions that are on the average no more expensive than promised. Simulation-based experimental results on a realistic e-commerce system demonstrate that the proposed bounds can be rapidly improved iteratively, and the resulting controller convincingly outperforms a controller that uses heuristics instead of bounds.