Chronicle Recognition Improvement Using Temporal Focusing and Hierarchization

1 Introduction

Symbolic scenario recognition arises in monitoring of dynamic systems in many areas such as telecommunications networks supervision, gas turbine control, healthcare monitoring or automatic video interpretation (for an overview, refer to [Cordier and Dousson, 2000]).

Such scenarios could be obtained among other things by experts, by automatic learning [Fessant et al., 2004; Vautier et al., 2005] or by deriving a behavioral model of the system [Guerraz and Dousson, 2004]. Due to the symbolic nature of those scenarios, the engine performing the recognition is rarely directly connected to sensors. There is often (at least) one dedicated calculus module which transforms the "raw" data sent by the system into symbolic events. Typically this module can compute a numerical quantity and sends symbolic events when the computed value reaches given thresholds. In cognitive vision, this module is usually a videoprocessing which transforms images into symbolic data.

Often those scenarios are a combination of logical and temporal constraints. In those cases, symbolic scenario recognition can process the scenarios uniformly as a set of constraints

(like the Event Manager of ILOG/JRules based on a modified RETE algorithm for processing time constraints [Berstel, 2002]) or separate the processing of temporal data from the others like in [Dousson, 2002]. This article mainly deals with this second approach where temporal constraints are managed by a constraint graph between relevant time points of the scenarios. There are two approaches for dealing with temporal constraints: STRS recognizes scenarios by an analysis of the past [Rota and Thonnat, 2000] and SPRS which performs an analysis of scenarios that can be recognized in the future [Ghallab, 1996]. Two main problems in the SPRS approach are the fact that scenarios have to be bounded in time in order to avoid never expected ending scenario (in practice, when working on real-time systems, it is difficult to exhibit scenario which cannot be bounded in time); and, second, that SPRS engine has to maintain all partially scenarios which possibly leads to use a large amount of memory space. To partially avoid those drawbacks, the implementation of SPRS algorithms in [Dousson, 2002] introduces a clock and deadlines which are used to garbage collect the pending scenarios. On the other hand, the main problem with STRS algorithms is to maintain all previously recognized scenarios. To our knowledge, no work has been published on how long such scenarios should be maintained. In addition, STRS does not provide any kind of "prediction" as SPRS does.

A first attempt to take the benefits of both approaches was made in [Vu et al., 2003]. It consists of a hierarchization of the constraint graph of the scenario. It deals only with graphs where all information about time constraints can be retrieved from a path where temporal instants can be totally ordered. The hierarchy constructs an imbricated sequence of scenarios containing only two events at a time. The principle of the recognition is, at any instant, to instantiate elementary scenarios and when an event is integrated in a high-level scenario, looking for previously recognized elementary scenarios. The purpose of this article is to generalize this method; the starting point will be an SPRS approach and the generalization mixes reasoning on past and future. As a byproduct, STRS and SPRS methods appear as two extreme kinds of the propose focused hierarchical recognition.

The next section presents the used SPRS approach and details some aspects which are relevant to this paper. The section 3 is dedicated to the temporal focusing which enables the system to focus on uncommon events prior to others. Events could be not only basic events coming directly from the supervised system but aggregated indicators. So the temporal focusing could be used in order to control the computation of such indicators on particular temporal windows and to avoid useless computation. As such indicators could be themselves scenarios, section 4 presents how the hierarchical recognition deals with common subscenarios. Finally, we show that both concepts could be merged and experimentally lead to good improvement of performances. This will be the object of the section 5.

We conclude in section 6 by experimentation on detecting naive servers in a Reflected Distributed Denial of Service (RDDoS) attack.

2 Chronicle Recognition System

Our approach is based on the chronicle recognition as proposed in [Dousson, 2002] which falls in the field of SPRS methods. A chronicle is given by a time constraint graph labeled by predicates.

An instance of event is a pair (e, t) where t is the date of the event and e is its type. When no ambiguity results, we sometimes do not distinguish between an event and its type. Figure 1 shows a chronicle which contains four events: the event e (if instantiated) must occur between 1 and 3 units of time after an instantiation of f, the event g must occur between 0 and 3 units of time after e and between -1 and 4 units of time after e′ .

Note that the complete formalism is based on a reified logic (a chronicle is a conjunctive formula) and introduces also predicates on persistency or event absence. In this article we choose to present in details the focusing from the time constraint graph point of view, other predicates are also taken into account but not discussed here.

2.1 Recognition Algorithms

Let CRS (Chronicle Recognition System) denote the algorithm of recognition. Basically the mechanism of CRS is, at each incoming event, to try to integrate it in all the pending (and partial) instances of the chronicle model and/or created a new instance and calculating (using constraint propagation [Dechter et al., 1991]) new forthcoming windows for all the forthcoming events of each instance. An instance of a chronicle model is then a partial instantiation of this model and forthcoming windows fc(e) of a non-instantiated event e is the (extended 1 ) interval where the occurrence of an event could lead to a recognition 2 .

1 An extended interval is a disjoint union of intervals.

2 This does not imply that, for all non instantiated events e, if (e, t) occurs with t ∈ fc(e) then the instance is recognized. This a difference between SPRS mechanism where integration of events is

Figure 2 shows the mechanism of the recognition algorithm on a small example: when CRS receives f at 1, it creates the new instance I1 and updates the forthcoming window of the node e. When a new f occurs at 3, instance I2 is created (the forthcoming windows of I1 is updated "using" a clock tick set at 3). When e occurs, I3 is created (from I2) and I1 is destroyed as no more event e could from now be integrated into (instance I2 is not destroyed, waiting for another potential e between 5 and 6). As all events of I3 are instantiated the chronicle I3 is recognized.

2.2 FromClock to "AssertNoMore" Event.

In first implementations of chronicle recognition, a clock was introduced in order to discard "impossible" instances when the clock goes past one of their forthcoming windows (see behavior of I1 in figure 2).

In order to take into account some jitter in data transmission a possible delay δ can be taken into account. This delay bounds the maximum difference observed at reception between two events sending at the same time by the (possibly distributed) system. Basically, the event integration algorithm could be written as following:

The main drawback is that it implies that events arrive roughly in a FIFO manner (the allowed jitter is bounded by δ): so, when the FIFO hypothesis should be relaxed (and it is often the case when the monitored system is distributed), δ should be increased and the garbage efficiency decreases 3 .

In order to avoid this, instead of a clock, we define a new input message: "AssertNoMore(e, I)", where e is an event type and I an extended interval. It specifies to CRS that, from now on, it will not receive more events of type e with an occurence date in I. This mechanism is implemented in CRS by managing one forthcoming window for each event type which is updated when receiving an "AssertNoMore" message.

We do not describe here how CRS deals with this assertion as it is very close to the previous CRS. Intuitively, all the forthcoming windows of e are reduced (fc(e) \ I), these windows are propagated according to the constraint graph of the chronicle and, if a forthcoming window becomes empty, the instance is discarded. The previous garbage collect of CRS could be emulated by the following:

incremental and some STRS mechanism where integration is made by block in a backward manner.

3 In case of focusing, an other side effect of using clock is the creation of "false" instances. This will be explained in section 6.

integrate((e, t)); ∀ event type e′ , AssertNoMore(e′ , ] -∞, t - δ])

It illustrates that the previous clock management forces all the event types to be synchronized: in other words, if one kind of event could be widely jittered, then all event types are supposed to be the same. Notice that, as we allow the use of extended intervals, more complex garbage management could be easily implemented: it could be different from ] -∞, clock] and non chronological: we could process, for instance, "AssertNoMore(e, [10, 20] ∪ [30, 40])" and, then, "AssertNoMore(e, [0, 10])".

This point of view changes slightly the manner the engine works: the progress of time is no more driven by the observations coming from the supervised system but by an "internal" control, this control could be given by the knowledge of the temporal behavior of the system. We will see in the next section how this new feature is essential for an efficient temporal focusing.

3 The Temporal Focusing

3.1 General Description

In some cases, not all events have the same status: in example on figure 2, event f could be very frequent and event e extremely uncommon. Due to this difference of frequency, the recognition of the chronicle could be intractable in practice, indeed each event f potentially creates a new instance of the chronicle waiting for other events: if a thousand f arrive between 0 and 1, a thousand instances will be created. As event e is extremely uncommon most of those instances would be finally destroyed. In CRS, the number of creation of instances has a great impact on performance of the recognition. In order to reduce this number, we focus on event e in the following manner: when events f arrive, we store them in a collector and we created new instances only when events e occur, then we will search in the collector which f could be integrated in the instances. Potentially the number of created instances will be the number of e and not the number of f. In order to be not limited to uncommon events, we order the recognition process by introducing a level for each event type. The principle of the temporal focusing is then the following:

Temporal focusing: Begin the integration of events of level n + 1 only when there exists an instance such that all events of level between 1 and n had been integrated.

So, if level(e) ≤ level(f), the engine will integrate e at t = 5 then it will search in the collector all events f between t = 2 and t = 4. The collector finds (f, 3) and sends it to the engine, this leads to the creation of the instance I3. Technically we made the choice of sending f not only to instances waiting for events of same level but to all the pending instances. As the number of f sending from the collector to the engine is small, only a small number instances are created. This also ensures that the collector sends an event one and only one time. So, in our example, (f, 3) leads to the creation of instance I2 with fc(e) = [5, 6].

In addition to the recognition engine, we developed some modules (see figure 3): an Event Router which routes the events coming from the supervised system to either the engine or the collector; a module named Finished Level Detector which detects when a particular instance of chronicle has finished to integrate all events of level lesser than n, then looks at the forthcoming windows of events of level n+1 and sends them (through a "Focus" message) to the collector as a request for events. At last, a module called No Need Window Calculator, which computes for all current instances the windows where they do not need events of greater level and sends this information to the collector via a "Discard" message. In order to make the buffer management easier, the collector itself is split into Buffered Streams: one for each event type.

At this stage, we have defined two messages for a feedback control on the production of event of high level: CRS is able to focus on specified time windows (by sending a "Focus" message) but also could discard events in irrelevant time windows (by sending a "Discard" message).

3.2 The Buffered Streams

The collector is composed of many buffered streams, each of them is dedicated to one event type. This section presents how it works: each buffered stream manages three particular temporal windows (see figure 4) :

1. the assert no more window (nm) which contains all the occurrence dates for that no more event will be received from now,

• ii) the filtered window (fil) which contains all the occurrence event dates for which the pending instances don't care, and
• iii) the focus window (foc) which contains all the occurrence dates for which incoming events are required and should be integrated immediately by CRS without be stored.

The figure 5 illustrates the different cases of processing an event according to its position against the temporal windows of the buffered stream.

Reception of control messages ("AssertNoMore", "Discard" or "Focus") updates also the buffered stream:

• "AssertNoMore(f,w)" : it updates the windows (see fig. 6) nm ← nm∪w, fil ← fil\w and foc ← foc\w and sends to CRS "AssertNoMore(f, w ∩ foc)".
• "Discard(f,w)" : it destroys all events in w, then updates the windows : fil ← fil ∪ (w\nm), foc ← foc\w and sends back to CRS "AssertNoMore(f, w)" 4 .
• "Focus(f,w)" : it sends all events in w, then updates the focused window: foc ← foc ∪ (w\(nm ∪ fil) and sends back to CRS "AssertNoMore(f, w ∩ (nm ∪ fil))".

So, during the recognition process, the following properties are always true : i) The windows nm, fil and foc are mutually exclusive. ii) There is no buffered event in the filtered and the focused windows. Whatever the levels in a chronicle, this mechanism performs exactly same recognitions as CRS with no focusing; only the performances are affected.

3.3 Partial order and relative event frequencies

In figure 2, if e is much more frequent than f , there is no need to define level, as, if no f was arrived, no e initiates new instances, thus the number of partial instances equals number of f. So relatively to an other event e, event f (very frequent) should be leveled only if e ̸≤ f (in the partial order induced by the constraints), in particular when e and f are not ordered, for example if e [-1,2] -→ f. We can decompose instances into two categories: the instances where f is before e for which the focusing will be particular efficient and the other part where f is after e, in this case f should be directly sent to the recognition engine which is done by the use of the maintained focus window. An other case where focusing is useful is when f [a,b] -→ e, with a, b ≥ 0, with e FIFO but f having a jitter delay greater than b. To sum up, setting a level to an event is based on an a priori knowledge of its incoming frequency and on its position in the constraint graph.

4 This message is a kind of acknowledgment used to synchronize the event buffer state and the CRS state.

The focusing must be combined with hierarchization in the case where one can identify uncommon sub-patterns or when more than one occurrence of a frequent event is required for the recognition (see section 5 and 6 for an example).

4 Hierarchical Chronicles

A hierarchical chronicle is a pair (C, {h1, . . . , hn}) where C is the base chronicle and hi are the sub-chronicles; we assume that events involved in C can take value in the set of sub-chronicle labels {h1, . . . , hn}. We treat only deterministic hierarchical chronicles 5 , i.e. we do not allow two sub-chronicles having the same label, so, in the following, we make no distinction between the chronicle and its label. Moreover we suppose that each hi has a distinguished event bi. The hierarchical chronicle C will be recognized if it is

5 There is no technical difficulty to consider non-deterministic hierarchical chronicles. The main difference is that expansion (see below) leads to more than one chronicle. This is a possible way to introduce disjunction in chronicle formalism.

(classically) recognized with integrated events labeled by a sub-chronicle hi have the date of an integrated event bi in a recognized instance of hi. In other words, when a subchronicle hi is recognized, it "sends" to all chronicles the event (hi, date of bi).

In figure 7, the hierarchical chronicle H = (C, {h, k}) possesses two sub-chronicles h and k, the chronicle k is composed of two types of events: a basic one, f (which comes from the supervised system) and one from the sub-chronicle h. The distinguished events are respectively e and h.

Let C be a chronicle with constraint graph G and with an event h, where h is a subchronicle with distinguished element b and with constraint graph V . Expanding the chronicle C (or its graph) is replacing the node h ∈ G by the graph V , specifying that the constraints between b and G\V are the constraints of h ∈ G. Let the relation hi → hj be defined if hj contains the event type hi. The hierarchical chronicle is structurally consistent if ∀i, ∄hi →∗ hi. In this case the expansion of a hierarchical chronicle is well defined (the graph of the figure 8 is the expansion of (C, {h, k})). A hierarchical chronicle C is consistent if there exists a set of events s.t. C is recognized. It is straightforward that a (structurally consistent) hierarchical chronicle is consistent iff when expanding sub-chronicles the obtained constraint graph is consistent.

Hierarchical chronicles can come from two ways: the first one is that the chronicle is initially specified in a hierarchical manner, for example if the architecture of the system is itself hierarchical; the second one is, starting from a flat chronicle, we identify identical patterns inside this chronicle. The next proposition is a necessary and sufficient condition to the hierarchization of a (temporal) pattern and shows we have to take care in pattern factorization: two subgraphs could be identical (with same constraints) but one of them can satisfy the condition and the other not.

Proposition 4.1 Let G be a minimal constraint graph and U ⊆ G a subgraph. Let b ∈ U be a (distinguished) node and H the hierarchical chronicle defined by G′ = (G\U) ∪ {h} and h = U, where h ∈ G′ has the same constraints as node b. Then H and G recognize the same events iff

where Dxy is the time constraint between nodes x and y in the graph G.

5 Focused Hierarchical Recognition

In this section, we present how focusing and the hierarchization could be mixed. We need to add a module which transforms the windows of high level events representing subchronicles into those of the different buffered streams representing the events in the sub-chronicles.

We only present the formula for updating the filtered window: when the collector receives a "Discard" message for f, it transforms it into a "Discard" message for all events of the sub-chronicle f, but needs also to take into account other high-level events. In order to do that, we also introduce a filtered window for all high level events representing a subchronicle.

So, the window of the "Discard" message receives by the buffered stream of event type e (included in f) is given by: ⋂e∈fi fil(fi)/De,bi where De,bi is the time constraint from e to the distinguished node bi of fi and where:

with natural extension to the set of extended intervals.

Remark: An example of gain of focusing vs. techniques presented in [Vu et al., 2003] is that for subgraphs with [0, 0] constraints (co-occurrence), we don't have to explore combination of partial instantiation but only store events and wait for an event in the future in order to extract from the collector events with the "good" parameters; thus all the combinatorial explosion of elementary scenarios is avoided.

6 Experimentation

This experiment was done on real data coming from the real case application which motivates this work: the detection of RDDoS (Reflected Distributed Denial of Service) attacks in IP networks.

In such attack, machines with the spoofed IP address of the victim send SYN messages to naives servers. Then, those servers will reply by sending to the victim SYN/ACK messages generating a massive flooding. Characteristic of the attack is that SYN traffic to naive server is low, persistent and, taken alone, do not trigger an alarm. We want to identify the naive servers. In our experiment, information on the global traffic are sent way up by dozens of core routers. Preprocessing is done by a particular numerical algorithm which computes throughput between pairs of IP addresses and sends alarms when this throughput is greater than two thresholds: a low one (L events) and a high one (H events).

So CRS receives two kinds of events: H[ip dest] and L[ip scr, ip dest] where variables are IP addresses of the source and of the destination. To identify the IP addresses of the naive servers, the focused hierarchical chronicle to recognize is :

where event H is of level 1 and SynLow of level 2. We do not discuss here the choice of threshold nor the relevance of the chronicle, our aim is to present performance of focusing face to huge amount of data. The log contains ≃240,000 events (L and H), its period is equal to ≃6min, frequencies are ≃660 L/sec and ≃3 H/sec. Due to a lack of synchronization of routers the jitter delay is set to 60s. We compare processing time 6 for 4 different cases: on one hand, using previous CRS with clock management (clk) [Dousson, 2002] or using CRS with "AssertNoMore" extension (anm), and on the other hand by using a hierarchical chronicle with focusing (fh) or the corresponding flat chronicle.

Considering only the anm extension, the processing time decreases a little since the garbage collect is more efficient: partial instances have a shorter lifetime in memory. The amount of created instances is considerably reduced when using focusing. The difference between number of instances when using clock (3550) and when using anm (1840) is explained on this example: for the leveled chronicle of figure 2, when f arrives at t = 1, we store it and the clock is set to 1; but when (e, 3) arrives, the clock can not be set to 3 otherwise all current instances would be discarded; so, even if in the FIFO hypothesis, it is necessary to set the delay to 3 (the upper bound of the constraint between f and e). By this artifact, a (possible large) number of "false" instances are uselessly created. The introduction of this delay has also an incidence on the collector's size.

7 Conclusion

This paper presents two improvements of chronicle recognition. The first one is the focusing on particular events which allows the system to reason on the past and on the future in a homogeneous manner. The second concerns the hierarchical recognition based on subpatterns. We also showed that mixing both improvements increases the efficiency and also fills the gap between SPRS and STRS approaches which are completely covered. In practice, our approach is sufficiently adaptive in order to fine-tune the recognition system. For instance, the order of event integration could be different from their arrival order. Moreover, focused events could postpone some expensive numerical computations to generate events and avoid useless ones.

6 Performed on a PPC G4 biprocessor 2×1GHz with 1Gb SDRAM. Java implementation was run on JVM 1.4 / Mac OS X.

Future works will take two directions: the first one is to define a more flexible way to factorize common patterns - condition 1 (proposition 4.1) is too restrictive for many practical cases. As dealing with the event frequency substantially increases the efficiency of CRS, the second direction will be focused on online analysis of event frequency in order to adapt dynamically the hierarchical temporal focusing.