On the Expressiveness and Complexity of Randomization in Finite State Monitors

Chadha, Rohit; Sistla, A. Parsad; Viswanathan, Mahesh

Permalink

https://hdl.handle.net/2142/10838 Copy

Description

Title

On the Expressiveness and Complexity of Randomization in Finite State Monitors

Author(s)

• Chadha, Rohit
• Sistla, A. Parsad
• Viswanathan, Mahesh

Issue Date

2009-02

Keyword(s)

• Computer Science
• Engineering

Abstract

"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 paper we study 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. Finally, we give the exact complexity characterization of the problems of determining whether the monitor permits any sequence (emptiness) and whether the monitor permits all sequences (universality). These decision problems help determine if the monitor is ""non-trivial""."

Type of Resource

text

Permalink

http://hdl.handle.net/2142/10838

Owning Collections