Complex Event Processing (CEP) provides a mechanism to eficiently correlate and infer conclusions about systems by means of analyzing the events they process. In areas such as the Internet of Things (IoT), Cyber Physical Systems (CPS), system monitoring or data streaming analytics, CEP is able to read events from a data stream and to generate complex events that represent situations of interest to the system owner by means of event patterns. Every time a sequence of events matches a pattern, a complex event is created and added to the data stream. The dependencies among the rules and the possibility of non-confluent behavior of CEP rulebased systems may lead to unexpected outputs when executing CEP programs. In this work, we show how to statically check and correct two particular properties of CEP systems: rule acyclicity and rule race conditions. We use Esper EPL as a CEP language, and present a tool we have developed to perform these analyses.
Domains such as Internet of Things (IoT), Cyber-Physical Systems (CPS), social networks, or system monitoring, generate gigabytes of data every second. In order to take advantage of that situation, approaches for data analytics have arisen and are used to extract useful information and knowledge from it.
Complex Event Processing (CEP) [
CEP systems are developed using Event Pattern Languages (EPL), which are normally rule-based languages that define rules for each pattern. Patterns are triggered when their matching conditions are met (e.g., the relevant source event occurs) and are in charge of generating the resulting complex events.
As with any other rule-based language, CEP programs are easy to develop and very eficient when they are composed of a small set of rules. However, as the number of patterns (rules) grow, the complexity of CEP programs becomes unmanageable, their behavior can be unpredictable, and checking their correctness becomes a very dificult task.
In this work, we present a tool for the static analysis of CEP programs, which addresses the issues of detecting and fixing acyclicity and rule race conditions. This static analyses help improve and maintain the code quality and give developers immediate feedback in the early development phases of the CEP software system.
The rest of the paper is structured as follows. First, Section 2 presents the background of our work. Then, we present our main contribution in Section 3, and our tool in Section 4. Section 5 discusses a validation exercise we have used to evaluate our approach, using a real CEP application. Finally, Section 6 compares our approach with other related works, and Section 7 concludes and outlines our future lines of work. 2
Complex Event Processing ofers a form of data processing [
There are two types of events in a CEP system: simple events,
which contain the information received by the sensors; and complex
events, which are generated by the CEP system and inserted into
the data stream [
Although several CEP systems and languages exist, they all share
the same basic concepts, mechanisms and structure. In this paper
we write the rules in one particular EPL, called Esper EPL [
In order to explain CEP and to illustrate our proposal, we will use
the Smart House case study we introduced in [
For the particular case of ensuring security in situations of fire, we know that when a fire starts, the temperature increases at a rate higher than a given value; and carbon monoxide (CO), which weights less than air, increases and accumulates in the ceiling. For this reason, temperature and carbon monoxide (CO) sensors have been installed in the ceiling. They record the absolute value of the temperature and CO in their respective position every second and send signals to the central system.
In case of fire, another key aspect is to determine whether or not someone is at home. For this purpose, our system uses the mobile phones of its occupants as motion detectors that inform of their geographical coordinates at all times.
Using the measurements produced by these sensors, and using Esper EPL, we have defined the set of CEP rules that we show in Listing 1. Lines 1–3 show the types of the simple events, in the form of templates that specify their name and attributes. In this example,
Listing 1: Esper EPL patterns for the Smart House 1 create schema Home ( id i n t , ts i n t , x i n t , y i n t , sqre i n t , 2 temp i n t , co i n t , dopen boolean ) ; 3 create schema Person ( pid i n t , ts i n t , x i n t , y i n t ) ; 4 5 @Name( " TempIncrease " ) 6 i n s e r t into TempIncrease 7 s e l e c t h2 . ts as ts , h1 . id as id , h2 . temp as temp , 8 h2 . temp−h1 . temp as incr 9 from pattern [ ( every ( h1 = Home ( ) −> 10 h2=Home ( h2 . temp−h1 . temp >=2 and h2 . id=h1 . id ) ) ) 11 where timer : within ( 1 minutes ) ] ; 12 13 @Name( " TempWarning " ) 14 i n s e r t into TempWarning 15 s e l e c t t4 . ts as ts t1 . id as id , t4 . temp 16 from pattern [ ( every ( t1 = TempIncrease ( t1 . temp >= 3 3 ) ) 17 −> ( t2 = TempIncrease ( t2 . temp > t1 . temp and t2 . id = t1 . id ) ) 18 −> ( t3 = TempIncrease ( t3 . temp > t2 . temp and t3 . id = t1 . id ) ) 19 −> ( t4 = TempIncrease ( t4 . temp > t3 . temp and t4 . id = t1 . id ) ) ) 20 where timer : within ( 5 minutes ) ] ; 21 22 @Name( " COHigh " ) 23 i n s e r t into COHigh 24 s e l e c t h1 . ts as ts , h1 . id as id 25 from pattern [ ( every ( h1 = Home ( h1 . co >= 5 0 0 0 ) ) ) ] ; 26 27 @Name( " FireWarning " ) 28 i n s e r t into FireWarning 29 s e l e c t tw . id as id , coh . ts as ts 30 from pattern [ ( every ( coh = COHigh ( ) ) −> 31 every ( tw = TempWarning ( tw . id = coh . id ) ) ) 32 where timer : within ( 5 seconds ) ] ; 33 34 @Name( " NobodyHome " ) 35 i n s e r t into NobodyHome 36 s e l e c t p . ts as ts , h . x as x , h . y as y , h . id as id 37 from pattern [ ( every h =Home ( not dopen ) −> every ( p=Person ( 38 ( p . x <= ( h . x − Math . sqrt ( h . sqre ) / 4 ) ) or 39 ( p . x >= ( h . x + Math . sqrt ( h . sqre ) / 4 ) ) or 40 ( p . y <= ( h . y − Math . sqrt ( h . sqre ) / 4 ) ) or 41 ( p . y >= ( h . y + Math . sqrt ( h . sqre ) / 4 ) ) ) ) ) 42 where timer : within ( 3 seconds ) ] ; 43 44 @Name( " CallFireDepartment " ) 45 i n s e r t into CallFireDepartment 46 s e l e c t fw . id as id , fw . ts as ts 47 from pattern [ ( every ( nh = NobodyHome ( ) ) −> 48 fw = FireWarning ( fw . id = nh . id ) ) ) 49 where timer : within ( 5 seconds ) ] ; there are two types of simple events that serve as inputs to the CEP program: Home and Person. Each Home event keeps information of the house identifier, the event timestamp, the house location given its geographical coordinates x and y, its size measured in square meters, the temperature degrees and CO accumulated in the environment and whether the main door is open or not. Regarding the simple events of type Person, they are represented by a tuple with information about the person identifier, her corresponding geographical location given by its x and y coordinates, and the timestamp in which the event is produced.
Our example contains six event patterns. The pattern called TempIncrease matches Home events in a time window of one minute and checks whether the temperature of the house has increased in 2 or more degrees. If so, it generates a complex event with the same name. Similarly, the pattern COHigh creates a complex event each time the sensors detect CO levels above 5000 ppm.
Pattern TempWarning detects if four events of type TempIncrease occur in a five-minute window where the first one starts from a temperature equal to or greater than 33 degrees, and the rest of them detect a temperature increase of two or more degrees.
A FireWarning event is created every time an event of type COHigh is detected, followed by another of type TempWarning, everything within less than 5 seconds.
A NobodyHome event is created from the primitive events Home and Person when the main door of the house is closed and there is nobody whose geographic coordinates are within the perimeter of the house.
Finally, pattern CallFireDepartment creates an event of the same name when there is nobody at home and a fire warning has been detected. In these cases, the central system must react and call the fire department.
In Esper EPL, as can be inferred from previous patterns, each complex event created has a type and set of attributes indicated in the select clause of the pattern.
Due to the nature of rule-based declarative languages such as Esper EPL, their patterns (rules) could be executed in any order. Pattern execution of course depends on the arrival of the events and thus the event arrival would constrain the order in which patterns will execute. However, CEP systems can generate complex events that are added to the event stream, and there are rules that depend on these complex events to produce further complex events. The order in which these rules are triggered may have a significant efect on the final output of the program. This makes the execution of CEP programs non-deterministic and hard to maintain, test and debug.
The two main source of problems we detect in this work are rule acyclicity conditions and rule race conditions. Rule acyclicity takes place, for instance, when a pattern A generates events of type a, which are consumed by another pattern B, which at the same time generates events of type b that are consumed by A.
Rule race conditions occur when there are input-output dependencies between rules in uncontrollable or non-deterministic situations. In the case of CEP, rule race conditions happen when a pattern consumes complex events that have not been produced by the time it is being executed, but afterwards. Hence, the pattern misses them and its match and execution never take place although they should. For example, pattern A produces complex event a; pattern B produces complex event b; and pattern C requires the occurrence of the events a and b to produce the event c. What happens if pattern C is checked before patterns A or B are triggered?
In order to address the problems presented in Section 2.2, we represent CEP programs as directed graphs where the patterns are nodes and the dependencies between patterns are the graph edges. Note that two patterns can generate the same complex event. In the case that that complex event is consumed by a third pattern, this third pattern has dependencies with the two former patterns. Person
Home NobodyHome
TempIncrease Home
Person TempIncrease
NobodyHome TempWarning
COHigh COHigh
TempWarning
FireWarning CallFireDepartment
Rule acyclicity is not a problem in itself but it can cause problems, such as infinite loops that flood the system with useless events. Thus, we decided to detect those cycles and inform the engineer about them.
First of all, we build the graph corresponding to the Esper EPL
code. As mentioned before, a node is created for each pattern. Edges
are created as follows. For each pattern R, we analyze its from
pattern to detect the events involved in its matching phase, track
the patterns in which these events are produced, and create an edge
in the graph associating the pattern R with each one with which it
has dependencies. In a second step, once the dependency graph is
built, we apply the Kosaraju-Sharir algorithm [
Imagine that due to copy-paste, the code of our example contains errors. Imagine that the rule TempIncrease stated in its from pattern that depends on FireWarning events, and the COHigh rule consumed its own events. The generated graph following our approach would be the one presented in Figure 1. Note how cycles are depicted in red to catch the engineer’s attention. 3.2
In Esper EPL, priorities can be assigned to patterns by using the label @Priority(n) where n is a non-negative integer. By default, if the priority is not specified, the CEP engine assumes that the pattern has the highest priority, which is 0. Users may assign priorities to rules in order to avoid the rule race conditions described in Sect. 2.2.
The lack of priority assignation, or errors in their assignments, can lead to race conditions between patterns—specially those that consume complex events. In order to detect these conditions, we also rely on the graph representation of the Esper EPL programs.
Firstly, the acyclicity analysis has to be performed. If it detects cycles, we cannot make any conclusion about the correctness of the priorities. On the contrary, if the graph does not contain cycles, we are able to generate the priority of each node given their dependencies. In order to do so, we make use of the graph topological order of their nodes. The priority of each node is the maximum of the priorities of its predecessors plus one.
FireWarning
CallFireDepartment
Once we calculate the priority that each pattern should have, we compare them with the priorities assigned by the user. With the result of the analysis we generate two files. One with the program dependency graph that, when interpreted and visualized, shows in red every node for which the priorities do not coincide, and one with the Esper EPL code containing the same code as the original ifle in which the priorities have been fixed.
As an example, Figure 2 shows the graph generated from the code in Listing 1. We can see how, due to the lack of priorities (which the Esper engine assumes as priority 0), patterns TempWarning, FireWarning and CallFireDepartment are suggested for review. Listing 2 shows the excepts of the new generated Esper file in which the right priorities are explicitly defined. In this context, right means that the rule priorities ensure the correct order of triggering, in order to avoid rule race conditions. 4
We have created an Eclipse plug-in called CEPA1, 2 to give support to our approach. We have used Xtext,3which allows the definition of Domain-Specific Languages (DSL) and ofers a parser, typechecker and compiler for free; and GEF, 4 which permits the integration of the Graphviz5 tool for graph visualization within Eclipse.
Using Xtext, we have defined a simplified grammar that parses any valid Esper EPL program, and builds an Abstract Syntax Tree (AST) that focuses only on the parts of interest needed to extract the pattern dependencies. In this way, the AST only contains information about the select and from pattern parts of the CEP programs, ignoring the rest of the language syntax.
Given the AST provided by Xtext, we have built a Java program that creates a graph containing the primitive events and pattern dependencies and perform the analyses mentioned in Section 3.
If the acyclicity analysis detects cycles, we use the Xtend6 code generator to automatically generate the textual code that represent 1https://github.com/Garlo13/CEPStaticAnalysis 2CEPA stands for CEP Analysis. Cepa is also the Spanish word for strain. 3https://www.eclipse.org/Xtext/ 4https://www.eclipse.org/gef/ 5http://www.graphviz.org/ 6http://www.eclipse.org/xtend/
Esper EPL Program Graphviz Graph Graphviz Graph
Parse Program and create AST
(Xtext) Graphviz
Graph Generate Graphviz No Race Code Cond? (Xtend) Generate Graphviz Code (Xtend)
Yes AND
AST
Create Graph
(Java) Generate Yes Graphviz Code (Xtend)
Cycles?
No
Perform Race Condition Analysis
(Java) Generate Esper EPL Program w/
Priorities (Xtend)
Graph Perform Acyclicity
Analysis (Java) Esper EPL Program the pattern dependency graph showing the cycles with red arrows. This graph is interpreted by Graphviz and shown to the user.
In case the acyclicity analysis does not report the presence of cycles, the race condition analysis is carried out. If rule race conditions are detected, Xtend is used to generate two files: one containing the Graphviz graph with the result of the analysis, and another one with the Esper code with the right priority for each pattern. If no rule race condition is detected, only one file is generated with the Graphviz graph.
For clarity, Figure 3 depicts the CEPA workflow diagram, with the main steps of its internal behavior. For illustration purposes, Figure 4 presents a screenshot of our tool, showing its graphical interface to the user. 5
In order to validate our approach, we used a real CEP application
that currently runs across the Andalusian region in southern Spain,
and controls the quality of the air in real time, using the index
proposed by the U.S. Environmental Protection Agency (EPA) [
The definition of this CEP program 7, which is written in Esper
EPL [
Interestingly, we discovered that, although there are no cycles in this program, these 43 patterns sufered from rule race conditions due to dependencies between the patterns. These dependencies may cause that some patterns are triggered before the patterns on which they depend, hence leading to erroneous results and conclusions about the quality of the air in the region.
Our tool was able to detect this error and to propose the correct assignment of priorities to the application CEP patterns that permitted solving the rule-race condition problem. 6
Rabinovich et al. [
In the context of Active DBMSs [
Race detection in event-driven systems have been previously
studied [
There are other works modeling CEP systems using Petri Nets.
An an example, Ahmad et al. [
Finally, some of the issues discussed here were identified in our
previous work [
In this contribution, we present our approach to statically analyze Esper EPL programs, and to automatically check two properties: rule acyclicity and rule race conditions. Furthermore, when rule race conditions are detected, we suggest how to repair the Esper code to avoid non-confluence problems. We have built an Eclipse tool, called CEPA, that ofers support for conducting such tests.
In the future we plan to increase the list of analyses supported
by our tool, such as for example dead-end detection. Furthermore,
we would like to extend our current scope, by integrating into our
tool the dynamic analyses we explored in [
Acknowledgements. We would like to thank the reviewers of this paper for their helpful suggestions and comments. This work has been funded by Spanish Research Project TIN2014-52034-R.