On the Expressiveness and Complexity of Randomization in Finite State Monitors

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

Permalink

https://hdl.handle.net/2142/11522 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

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/11522

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections