Information Technology Reference
In-Depth Information
It can be observed that rule-based programming seems like an attractive ap-
proach to monitoring, as exemplified by the Ruler system [5]. Rules are of the
form
lhs
rhs
, where the left-hand side are conditions on a memory of
facts
,
and the right-hand side is an action that can add or remove facts, or execute
other code, including yielding error messages. This model seems very well suited
for processing data rich events, and is simple to understand due to its opera-
tional flavor. Within the field of Artificial Intelligence (AI) rule-based production
systems have been well studied, for example in the context of expert systems
and business rule systems. The Rete algorithm [6] is a well-established ecient
pattern-matching algorithm for implementing such production rule systems. It
maintains a network of nodes through which facts filter to the leaves where ac-
tions (rule right-hand sides) are executed. It avoids re-evaluating conditions in
a rule's left hand side each time the fact memory changes. This algorithm has
acquired a reputation for “extreme diculty”. Our primary goal with this work
has been to understand how well this algorithm serves to solve the runtime ver-
ification task, and hence attempt to bridge two communities: formal methods
and artificial intelligence. An initial discussion of this work was first presented
in [8]. We have specifically implemented a rule-based system, named LogFire,
basedontheRete algorithm in the Scala programming language as an internal
DSL, essentially extending Scala with rule-based programming. We have made
some modifications to the algorithm to make it suitable for the RV problem,
including fitting it for
event
processing (as opposed to
fact
processing) and opti-
mizing it with fast indexing to handle commonly occurring RV scenarios. Early
results show that the algorithm performs reasonably, although not as optimal as
specialized RV algorithms, such as Mop [11].
There are several well-known implementations of the Rete algorithm, in-
cluding Drools [1]. These systems offer external DSLs for writing rules. The
Drools project has an effort ongoing, defining functional programming exten-
sions to Drools. In contrast, by embedding a rule system in an object-oriented
and functional language such as Scala,asdoneinLogFire,wecanlever-
age the already existing host language features. Drools supports a notion of
events, which are facts with a limited life time. These events, however, are not as
short-lived as required by runtime verification. The event concept in Drools is
inspired by the concept of
Complex Event Processing
[10]. Two rule-based inter-
nal DSLs for Scala exist: Hammurabi [7] and Rooscaloo [2]. Hammurabi
is not Rete-based, and instead evaluates rules in parallel. Rooscaloo [2] is
Rete based, but is not documented in any form other than experimental code.
A Rete-based system for aspect-oriented programming with history pointcuts is
described in [9]. The system offers a small past time logic, which is implemented
with a modification of the Rete algorithm. This is in contrast to our approach
where we maintain the core of the Rete algorithm, and instead write or generate
rules reflecting specifications. In previous work we designed the internal Scala
DSL TraceContract for automaton and temporal logic monitoring [4]. An
internal Scala DSL for 'design by contract' is presented in [12].
⇒
