COMPILE-TIME AND RUNTIME ANALYSIS OF ACTIVE BEHAVIORS

Active rules may interact in complex and sometimes unpredictable ways, thus possibly yielding infinite rule executions by triggering each ot her indefinitely. This paper presents analysis techniques focused on d etecting termination of rule execution. We describe an approach which combines static analysis of a rule set at compile-time and detection o f endless loops during rule processing at runtime. The compile-time an alysis technique is based on the distinction between mutual triggering and mutual activation of rules. This distinction motivates the introd uction of two graphs defining rule interaction, called Triggering and Activation Graphs, respectively. This analysis technique allows us to identify reactive behaviors which are guaranteed to terminate and reac tive behaviors which may lead to infinite rule processing. When termin ation cannot be guaranteed at compile-time, it is crucial to detect in finite rule executions at runtime. We propose a technique for identify ing loops which is based on recognizing that a given situation has alr eady occurred in the past and, therefore, will occur an infinite numbe r of times in the future. This technique is potentially Very expensive , therefore, we explain how it can be implemented in practice with lim ited computational effort. A particular use of this technique allows u s to develop cycle monitors, which check that critical rule sequences, detected at compile time, do not repeat forever. We bridge compile-ti me analysis to runtime monitoring by showing techniques, based on the result of rule analysis, for the identification of rule sets that can be independently monitored and for the optimal selection of cycle moni tors.