ERE Monitoring Algorithm
Regular expressions can be easily understood by ordinary software engineers and programmers, as shown by the immense interest in and the success of scripting languages like Perl, based essentially on regular expression pattern matching. We believe that regular expressions provide an elegant and powerful specification language also for monitoring requirements, because an execution trace of a program is in fact a string of states. Extended regular expressions (EREs) add complementation to regular expressions, which brings additional benefits by allowing one to specify patterns that must not occur during an execution. Complementation gives one the power to express patterns on strings non-elementarily more compactly. Generating optimal ERE monitors is highly non-trivial and the interested reader should refer to the below papers. One important observation about the use of ERE in the context of runtime verification is that ERE patterns are often used to describe buggy patterns instead of desired properties.
More information can be found in the following paper:
- Towards Monitoring-Oriented Programming: A Paradigm Combining Specification and Implementation
- Feng Chen and Grigore Rosu
RV'03, ENTCS 89, issue 2, pp 108 - 127. 2003.
PDF, ENTCS, RV'03, DBLP, BIB