University of Illinois Urbana-Champaign

On the Expressiveness and Complexity of Randomization in Finite State Monitors

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

Content Files
On the Expressiveness and Complexity of Randomization in Finite State Monitors.pdf

Permalink

https://hdl.handle.net/2142/11522

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
Date of Ingest
2009-04-23T15:51:37Z
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
Genre of Resource
Technical Report
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

Research and Tech Reports - Computer Science PRIMARY