On the expressiveness and complexity of randomization in finite state monitors

Rohit Chadha, A. Prasad Sistla, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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. We also present results on the complexity of deciding non-emptiness of the set of sequences permitted by a monitor.

Original languageEnglish (US)
Title of host publicationProceedings - 23rd Annual IEEE Symposium on Logic in Computer Science, LICS 2008
Pages18-29
Number of pages12
DOIs
StatePublished - Sep 17 2008
Event23rd Annual IEEE Symposium on Logic in Computer Science, LICS 2008 - Pittsburgh, PA, United States
Duration: Jun 24 2008Jun 27 2008

Publication series

NameProceedings - Symposium on Logic in Computer Science
ISSN (Print)1043-6871

Other

Other23rd Annual IEEE Symposium on Logic in Computer Science, LICS 2008
CountryUnited States
CityPittsburgh, PA
Period6/24/086/27/08

    Fingerprint

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Chadha, R., Sistla, A. P., & Viswanathan, M. (2008). On the expressiveness and complexity of randomization in finite state monitors. In Proceedings - 23rd Annual IEEE Symposium on Logic in Computer Science, LICS 2008 (pp. 18-29). [4557897] (Proceedings - Symposium on Logic in Computer Science). https://doi.org/10.1109/LICS.2008.42