University of Pennsylvania - PRECISE

The continuous run-time monitoring of the behavior of a system is a technique that is used both as a complementary approach to formal verification and testing to ensure reliability, as well as a means to discover emergent properties in a distributed system, like intrusion and event correlation. The monitors in all these scenarios can be abstractly viewed as automata that process a (unbounded) stream of events to and from the component being observed, and raise an "alarm" when an error or intrusion is discovered. These monitors indicate the absence of error or intrusion in a behavior implicitly by the absence of an alarm.

In this talk, we will investigate the power of randomization in run-time monitoring. Specifically, we examine finite memory monitoring algorithms that toss coins to make decisions on the behavior they are observing. We give a number of results that characterize, topologically as well as with respect to their computational power, the sets of sequences the monitors permit. We will present the complexity of various decision problems and discuss the connections to a theory of omega-languages recognized by probabilistic automata.

This joint work with Rohit Chadha, and A. Prasad Sistla.

Mahesh Viswanathan obtained his bachelor's degree in computer science from the Indian Institute of Technology at Kanpur in 1995, and his doctorate from the University of Pennsylvania in 2000. He was a post-doctoral fellow at DIMACS with a joint appointment at Telcordia Technologies in 2000-01. Since 2001, he has been on the faculty at the University of Illinois at Urbana-Champaign. His research interests are in the core areas of logic, automata theory, and algorithm design, with applications to the algorithmic verification of systems.