Posted on

Complex Event Processing #2

So let’s continue the introduction of the complex-event processing work of our IoT challenge project.

In a former post you could read about the computer vision, which will provide the information for the complex-event processing engine. However, answering the question of what and how to process relies only on the complex-event processing. Now, we give some details about our extensions of the VIATRA-CEP framework. Note that it has not yet been merged: we plan to integrate them in the future!

Just a reminder about the workflow of the imagined CEP compiler:

Formalisms

The general idea of the extensions proposed in this project relies on our former work with VIATRA-CEP.

Regular languages were chosen according to their semantics, traditional automata transformation were planned to be used for supporting the work of the execution.

Now let’s see what have been implemented, and how it was done. We have developed the metamodel of the automata representation in EMF. In addition, several executor-related classes had to be developed in Xtend.

EMF model of the Automaton

As the intermediate language is intended to be used as a semantic integration layer, Xtext is used to implement a Regular Expression language.

Various transformations are used to generate the monitoring from the high level requirements description. As the regular formalisms are introduced into the system, we gain two main advantages:

  1. The semantics of the languages are familiar for the developers as regular languages are widely used in various areas of software engineering.
  2. Existing transformation algorithms could be utilized.

From the Regular Expressions, without timing and parameters, a transformation to automata is well-known in the literature so my task was quite simple. I found a well-specified algorithm and I implemented and integrated the compiler to the system. Also note that this algorithm generates a deterministic automaton which can be executed with a single active state, also known as token. This point is really important!

When using monitoring in resource constrained environments, it is useful to be able to give limits for the resource usage. This can be provided by deterministic automata.The timed part of the work was much more difficult!

One of our main goals was to keep the transformed automata deterministic – but as we found out it is mathematically impossible.

Summary

Our extensions will increase the usability of the VIATRA-CEP engine and hopefully enable us to limit the resource consumption of the engine. An additional advantage is that we plan to support the analysis of the CEP specification: this automata theoretic approach can help identifying design problems in the rules with the application of rigorous formal techniques.

Posted on

Complex Event Processing #1

I am Laszlo, and I am currently working on a Complex Event Processing Engine, which could be later integrated to the VIATRA-CEP project. This post will present the theoretical aspects, and the some other things excluding the implementation.

The motivation behind all of my work is simple: In our Scientific Students’ Conference Report we developed a system with multiple levels of runtime verification, and the system level verification was implemented with Complex Event Processing. For that, we have used the Open Source VIATRA-CEP framework which is part of the well-known VIATRA Eclipse project.

The reason for choosing this incredibly novel framework, is simple: It can be easily integrated on the top of live models. To do so the user can define graph patterns with EMF-IncQuery on these EMF models and use the appearance/disappearance of such graph patterns as atomic events in defining complex event patterns.

VIATRA-CEP uses an expressive event pattern language for the complex event pattern definitions. This language is called Viatra Event Pattern Language (or VEPL for short). This language is great for clear CEP proposes, but it lacks a truly clear and analyzable semantics and execution. Without explaining the grammar of this language I just show you a simple illustrative example of usage.

VEPL example

Of course instead of using atomicEvents it would be wise to use query events but that would just make this example longer. To show you, what I am working on right now let’s take a closer look to the architecture of the VIATRA-CEP

Architecture of the VIATRA-CEP

To extend this system towards the world of runtime verification, our idea was to create a similar language to VEPL but with the semantics of regular expressions. Also our plans are to map the VEPL to our Regular Expression language for debug and analysis purposes.

Architecture with the intermediate language

To create this intermediate language layer so we first developed a Parametric Timed Regular Expression formalism, which extends the well-known regular expressions with timing and parameters. For accepting languages generated by parametric timed regular expressions, we introduced the concept of the parametric timed event automata.

Formalisms