laszlobalogh – MoDeS3

2016-02-27

Complex Event Processing #3

Let’s discuss the Internet ot Things in particular. What is the internet? A(n array)list of cute stuff. Cute stuff like bunnies. Everybody likes bunnies, right?

Far Bunny (Or not?)

Okay, it looks kinda weird, but aren’t we all? Let’s step closer and look again, as you know, looks can be deceiving

Closer Bunny

Well there is something definitely not right, therefore this examination process must continue!

CloseBunny

Well… This is definitely not cute (or just not for my taste) What could this be then? After a little inspection you can realize that this is a graph… Between railRegions, and their connections… It’s 2 AM right now here, so after all this trying-to-be-funny let’s continue in a way more serious manner.

The bunny looking stuff is the instance model of our RailRoad system. Of course it is implemented in EMF and we only visualized it for debug purposes. We used yEd which is a graph visualizer with multiple layout algorithms and the organic layout algorithm generated this bunny-looking stuff.

So here is the EMF metamodel for further inspection:

EMF metamodel for the RailRoad System

Definitely not flawless, especially on the clockwise-counterclockwise part, as some part of the railroad (like the parts responsible for the reversion) are hard to model this way.

Most of the faulty behavior can be detected in this graph with some graph patterns… Of course, this calls for an Eclipse solution for this problem: The world best Incremental graph query engine. The IncQuery!

As the these patterns are declarative: understanding them takes way more time than simple imperative code (Java for example). Our codebase contains over a hundred lines of these graph patterns so it would take quite a long time to explain all of them. We are not going to do so, but this post wouldn’t be complete without at least inspecting some of them.

Simple IncQuery Pattern

For example, this one is simple one: To detect if some train is near in a neighbor section, the direction of the train must be observed. If there is a train on the next section according to the direction of the given trains, the pattern matches. The direction matters, because if one train is tailgating an other then only the rear train had to be stopped.

After all this, it is time to take a look at my first post about VEPL because here comes the same example:

VEPL example

VEPL support the extension of the monitoring system with temporal statements for anything more complex than a simple collision detection.

The Warning pattern compiles to this regex

regex Automaton

The automaton generated from the regex shown in the image above.

The general workflow of information processing transforms the image of a camera into information for the safety logic.

As you can see, these are the ingredients to do complex event processing on models. We have a model which is updated according to the information coming from the computer vision. The updated model contains all the necessary information which is used by the IncQuery patterns. Complex event sequences are then defined with the help of the VEPL language which is then compiled into an executable monitor automaton.

2016-02-26

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:

The semantics of the languages are familiar for the developers as regular languages are widely used in various areas of software engineering.
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.

2016-02-25

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