Michael Vogel

Sebastian Schmerl

Hartmut König

Efficient Distributed Signature Analysis

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Intrusion detection systems (IDS) have been proven as an important instrument for the protection of computer systems and networks. Nowadays, most IDS use a centralized approach and apply misuse detection (signature analysis). They mainly use single-step signatures to identify harmful behavior in a stream of audit data or network packets, respectively. This will change in next years, since multi-step signatures, in contrast to single step signatures, allow it to model attacks much more precisely, in particular the specific characteristics of the attack traces, existing dependencies, and the chronological order of the attack steps. This will reduce significantly the false alarm rate. Multistep signatures can store state information to track the attack through its different stages. This supports in particular the attack detection in application layer protocols as well as in Web 2.0 applications which are of increasing importance. Many semantic aspects of today's attacks cannot be modeled by single-step signatures at all or only insufficiently. Therefore, we focus our work on multi-step signatures.

A challenge that all intrusion detection systems are facing is the increasing performance of networks and end systems. This leads to a rapid growth of audit data volumes to be analyzed. On the other hand, the growing complexity of IT systems creates novel vulnerabilities and offers new possibilities for running attacks so that the number of signatures to be analyzed increases as well. Already now intrusion detection systems are forced to reject audit data in high load situations or to delay the analysis of security violations significantly. Thus, counter-measures become impossible or lose their impact. As consequence, systems become unprotected, when they are intensively used.

To cope with this situation several approaches have been proposed, e.g. the detection of intrusions based on an analysis of more compact, less detailed audit data [START_REF] Mchugh | Set, Bags and Rock and Roll -Analyzing Large Datasets of Network Data[END_REF][START_REF] Sommer | NetFlow: Information Loss or Win?[END_REF] and network flows [1] as well as various optimizing analysis methods for signature and network based single-step intrusion detection systems. For example, [START_REF] Yang | Improving NFA-based Signature Matching Using Ordered Binary Decision Diagrams[END_REF] describes an approach for the IDS SNORT that transforms signatures into a decision tree to reduce the number of redundant comparisons during analysis. Optimized string matching algorithms are proposed in [START_REF] Anagnostakis | E2xB: A Domain Specific String Matching Algorithm for Intrusion Detection[END_REF]. These approaches aim at optimizing the non-distributed, single threaded signature analyses. A distributed approach like GNORT [START_REF] Vasiliadis | Gnort: High Performance Network Intrusion Detection Using Graphics Processors[END_REF] utilizes the massive parallel computing capabilities of graphic processors (GPUs), but it only doubles the analysis throughput compared to the sequential Snort. So far, network-based IDS only apply primitive means to parallelize analyses by load balancing [START_REF] Colajanni | A Parallel Architecture for Stateful Intrusion Detection in High Trac Networks[END_REF][START_REF] Schaelicke | SPANIDS: A Scalable Network Intrusion Detection Loadbalancer[END_REF]. There are also almost no approaches to parallelize host-based IDS analyses [START_REF] Kruegel | Decentralized Event Correlation for Intrusion Detection[END_REF].

On the other hand, free computing resources are available in any network. CPU technology will provide only slightly more computation power per core in the future. In this paper we present a distributed signature analysis approach to use free resources in networks to overcome this issue. In Section 2 we introduce a generic model for multistep signatures to discuss distribution strategies. Next, in Section 3 we introduce several distribution strategies and outline their benefits and constraints for multi-step IDS. In Section 4 we evaluate the strategies based on measurements of a prototype implementation and discuss their applicability. Some final remarks conclude the paper.

Modeling Multi-Step Signatures

We first introduce a generic model for multi-step signatures which covers all existing multi-step-signature languages and related intrusion detection systems. The model confines to typical characteristics of multi-step signatures and their analysis. The core concept of a multi-step signature language is its ability to store information about attacks, system states, and related changes. Accordingly, a multi-step signature can be defined as a directed, labeled graph MS = {V, E, EvT, SI, f, state, sens, cond, mark, trans} with:  V -set of state nodes, representing the stages of an attack,  E  V  V -set of edges representing valid state transitions,  EvT -finite set of types of security relevant events (audit events), e.g. different types of system calls or network events,  SI -set of state information representing the state and the stage of a certain attack,  state: V  (SI) -a function which labels state nodes with a set si  SI of state information,  f  V -a final node indicating a detected attack as soon as labeled by state(f),  sens: E  EvT -a function which labels each graph edge with an event type, whereby the occurrence of an event of the specified type can trigger a state transition represented by the edge,  cond: E  B -a function labeling each edge (a, b)  E with a Boolean condition B: SI  Ev  {0, 1} which specifies arbitrary expressions (arithmetic, string matching, …) between features of state information si  state(a) of node a and the occurring event ev  Ev, whereby a state transition requires a fulfilled condition,  mark: V  SI  V -a labeling function which adds state information si to node v, whereby mark(v, si) = v', with state(v') = state(v)  si,  trans: E  Ev  V -transition function that evaluates for each occurring event ev of type evType  EvT whether edge e = (a, b)  E is sensitive to this event type (sens(e) = evType) and whether its condition cond(e) is fulfilled. In this case, the transition (a, b) is executed by reading state information si of node a by state(a), modifying si (its features) to si', and moving si' to node b by applying mark(b, si'). The detection of a multi-step attack can be outlined as follows. For each occurring audit event ev and for each edge e = (a, b)  E of the signature, the function trans(e, ev) is executed. This function evaluates by sens(e) whether edge e is sensitive to the type of event ev which may triggers a state transition. In this case, the edge condition cond(e) is evaluated by correlating features of event ev with state information si  state(a) of node a which represents the stage of the attack and contains aggregated information of former state transitions. If the edge condition cond(e) is fulfilled the state transition (a, b) is executed in two steps: (1) State information si  state(a) is read and updated or modified with information from the current event ev. (2) Next, the successor node b is labeled with the modified state information si' by mark(b, si'). This evaluation process is executed for each edge of the signature and all signatures. It must be repeated for each occurring audit event. An attack is detected if the final node f of a signature is reached and labeled with state information.

Now we extend the model for the needs of a distributed analysis by defining functions for statistical data collection to derive optimal distribution decisions.

 C -a cluster representing a virtual analysis unit with limited computation capacities to assign signature fragments (state nodes) to,  cl: V  C -a function which assigns each state node to a cluster, whereby initially each node is assigned to a unique cluster,  compC: E  N -a function labeling each edge e  E with the value of the computation effort (e.g. #cpu cycles), which was consumed in the previous time frame to evaluate the edge condition of e.  commC: E  N -a function labeling each edge (a, b)  E with the value of the communication effort (e.g. #bytes) which was consumed in the previous time frame to transmit state information from a to b.  evC: E  N -a function labeling each edge (a, b)  E with the value of the communication effort which was consumed in the previous time frame to transmit audit events of type sens(a, b) from a sensor to node a.

Distributed Audit Data Analysis Strategies

In signature based intrusion detection systems the analysis of audit data requires considerable computation efforts. Signature bases that cover all currently known vulnerabilities of the protected systems may easily consist of thousands of signatures. In high load situations, when large amounts of audit data are recorded, the resource consumption of the analysis system grows rapidly and exceeds frequently the available resources. For very short time periods (seconds), buffering can be an appropriate measure, but as soon as the buffer capacities are exhausted the analysis system has to drop audit data and becomes useless and blind for attacks.

In order to reliably prevent such overload situations the analysis efforts of a signature based IDS should be kept continuously on a reasonable low level. This can be achieved by distributing and balancing the required analysis efforts among free resources in the protected domain. So it is more appropriate to utilize five analysis units with a load of 20 % each, instead of only two systems with 50 % load each. This allows it to keep sufficient, free resources needed for analysis efforts in high load situations. As known, analysis distribution causes additional communication overhead which burdens the network and may lead to transmission delays. To ensure that the transmission of audit data in high load situations does not delay the analysis, sufficient bandwidth has to be provided. These demands, however, are conflictive and cannot be achieved at the same time. Fig. 1 shows the elements of a distributed audit data analysis. A sensor logs audit events which are forwarded to analysis units, in our example AU 1 to AU 3 . Each analysis unit AU i evaluates a subset of the signatures. The audit events are classified into different event types EvT. To reduce the network utilization a configurable filter discards non-relevant audit events of types which are not needed by the respective analysis unit. For example, only events of type EvT in ∪ a,b  V 1 sens(a, b) are forwarded to AU 1 , where V 1 is the set of state nodes assigned to AU 1 . The analysis units transmit state information si  SI between each other if needed. Analysis results are reported to a central component. Based on this concept we present below five distribution strategies.

A) Distributing Complete Signatures

The first approach simply distributes complete signatures to different analysis units AU i . Hereby, a simple optimization can be performed balancing the number of assigned signatures to each analysis unit. Additionally, a finer-grained optimization can be achieved if statistics on resource consumption are gathered continuously for each signature. So CPU hardware counters can be used [START_REF] Shemitz | Using RDTSC for Pentium Benchmarking[END_REF] to determine the number of clock cycles utilized to evaluate audit events and edge conditions for each signature. For this, the signatures' edges e are labeled with these values by function compC(e) to estimate the resource consumption of each signature. An example for a respective signature distribution is depicted in Fig. 2. Edges are labeled with required computation effort and examined event types as defined by compC(e) and sens(e), respectively. This simple strategy causes, however, two major problems. (1) If an overload situation is mainly caused by a certain signature the performance problem will be solely moved to another analysis unit (another CPU or host) and the strategy to distribute whole signatures fails. (2) A typical signature MS usually correlates different types of audit events. Particularly, MS analyzes all audit events of types in ∪ a,b  V sens(a, b), where V is the set of state nodes of MS. If whole signatures are distributed nearly all audit events captured by a sensor have to be sent to the related analysis units. This multiplies the communication effort by n (number of used analysis units). This is unacceptable for most IT-infrastructures. Fig. 2 depicts these problems exemplarily. First, the three signatures MS 1 to MS 3 are assigned to AU 1 to AU 3 . An optimal distribution would strive for a balanced load on all three systems of 33 % each. But, the analysis of signature MS 3 utilizes 90 % of the available resources of the respective analysis unit, while the analyses of MS 1 and MS 2 require only 5 % each. Secondly, additional communication is caused through event duplication. So the sensor has to triplicate type A events because they are analyzed by all three signatures. Analogously, type B and C events have to be duplicated for two analysis units. Therefore, further distribution options are required to balance the computation load finer-grained and to reduce the communication overhead.

B) Fragmenting Signatures

A more fine-grained signature distribution can be achieved by distributing signature fragments. This allows it to minimize audit event duplication. One or many state nodes (fragments) of a signature can be assigned to various analysis units, as depicted in Fig. 1. Now the distribution strategy can pool nodes having outgoing state transition edges which are sensitive to the same audit event types (label sens(a, b)) onto the same analysis units. So, audit events only have to be duplicated for few analysis units. Fragmentation also supports a better balance of the analysis efforts among the units. Signatures that require the majority of available computation resources of an analysis unit, as discussed above, can be split up now. An optimization strategy though which only aims at pooling signature fragments that analyze the same audit event types on the same analysis unit is not desirable. If two state nodes a, b  V are connected by an edge (a, b) and a and b have been assigned to different analysis units AU 1 and AU 2 (cl(a) ≠ cl(b)), then state information si  SI must be transferred from AU 1 to AU 2 , whenever transition condition cond(a, b) is fulfilled. The transfer of state information has to be minimized as well. To sum up, signature fragmentation allows a better balance of the computation load among analysis units and reduces audit event duplication. Fragmentation though may cause additional communication to transfer state information between analysis units.

C) Additional Reduction of the Communication Costs

Our next optimization does not primarily aim for an optimal balance of the computation efforts among the analysis units. Instead it takes the required communication effort to transmit audit events from the sensor to the analysis units into account as well as the transfer of state information between the distributed units.

To achieve this, the sensor has to gather a statistics that logs how often audit events of different types occur. The average data amount of an audit event is almost the same (evSize = 100 … 1000 bytes). The communication costs to transmit events of different types from the sensor to each analysis unit are labeled to the event types by function evC(evType) = #events * evSize. Additionally, each analysis unit continuously maintains a statistics that logs the number and size of transferred state information separately for each edge of the multi-step signature. The statistical values are labeled at each edge (a, b) of the signature by function commC(a, b). They allow determining the communication effort for audit event duplication and state information transfers for arbitrary signature distributions as an optimization criteria. For a given signature distribution, the event duplication effort can be determined according to equation (1).

       AU i S evT V b V a i i i b a sens S evT evC # 1 ,
) , ( where ), (

 (1)    ) ( ) ( , ) , ( ) , ( b cl a cl E b a b a commC (2)
Here, S i is the set of event types examined by the subset V i of signature fragments (V i  V) that is assigned to AU i . Similarly, the statistics permits to calculate the communication costs for state information transfers among different AUs by eq. ( 2). We apply the cluster component of our signature model (cf. Sect. 2). Each state node a is mapped onto a cluster by function cl(a), virtually representing an analysis unit. Only state information transfers between nodes a and b assigned to different AUs (clusters) cause real communication costs. Transfers between nodes on the same AU use shared memory.

Based on the statistical data, we can determine a communication efficient distribution of signature fragments by using a Greedy clustering algorithm. For this, we initially assign each state node of the signatures to an exclusive cluster. This initial state represents a virtual signature distribution for a maximum number of analysis units. In this case, all communication costs labeled to clusters and the signature edges are relevant because the audit events have to be duplicated for various analysis units and all state information has to be transferred between nodes assigned to different analysis units. Therefore, the initial stage represents the worst case communication scenario. The communication overhead, as defined in equations (1) and ( 2), can now be minimized by an iterative merging of clusters. We merge stepwise two clusters C i and C j that possess the maximum cumulated communication costs ( (a, b)E commC(a, b), with cl(a) = C i , cl(b) = C j ) on edges leading from nodes of C i to nodes of C j or vice versa. This merging process is repeated until the desired number of analysis units (e.g. 3) is reached. Since the clustering algorithm only optimizes the communication costs, it is necessary to limit the number of assigned state nodes and thus the computation effort required to evaluate the transition conditions for each cluster. As a result, our clustering algorithm creates signature distributions with a minimal communication overhead and an acceptable balance of analysis effort.

D) Detection of Repeated Dependencies between Audit Events

A fine-grained signature distribution, as described above, induces new challenges. When fragmentation is applied and the nodes of a signature are assigned to different analysis units, state information may arrive delayed at the successor nodes due to network latencies. An attack, however, can be only detected in the audit event stream if all preceding attack steps, described by the state information, have been recognized before. This is not possible, when the state information arrives too late. There is a simple solution for this problem. Since audit events from the same sensor can be ordered chronologically, state information can be related to the audit events. This can be achieved by enumerating all emitted audit events consecutively with a unique ID in the sensor. Each state information si is labeled with the ID of the related audit event. Thus, the analysis units can easily identify delayed state information by comparing their IDs. Fig. 3 It shows a fragmented signature consisting of four nodes. The nodes v, x and y are assigned to the analysis units AU 1 and AU 2 , respectively. Which is the optimal assignment of node w? The assumed sequence of audit events emitted by the sensor is indicated above the AUs. Since type B events often occur after type A, while type C events rarely occur after B, node w should be assigned together with v to AU 1 to prevent delayed state information arrivals at node w. If delayed state information arrives the related audit event has to be re-evaluated. This requires that the audit events are buffered in the analysis units for a short time. When new state information arrives all audit events that are older than the received one can be removed from the buffer. Therefore, the required buffer memory is assumed to be constant and is not discussed further here.

The repeated evaluation of audit events though may lead to a significant additional computation effort. We demonstrate this with the example above and assume now that node w has been assigned to AU 2 . If a type A event triggers a transition the respective state information has to be placed on node w. We assume that the information is delayed by Δt due to network latencies. The absolute frequency of type B and C events occurring after type A and B events within Δt is listed in Table 1. When events of type B occur after A within a time window of Δt, they have to be buffered in AU 2 for repeated evaluation. An event sequence in the audit data stream containing events of type i and j within Δt is called critical if it may cause repeated evaluations. This is the case, if an applied signature contains edges which are sensitive to i and j, respectively, and a type j event is expected after analyzing a type i event. Now, the sensor and the analysis units can dynamically update the statistics how often such critical sequences occur in the audit event stream. Each analysis unit also continuously logs number and types of repeatedly evaluated audit events. Based on this statistics, the responsible transition edges of a signature can be assigned to the same unit to avoid repeated analyses.

E) Iterative Adaptation of Signature Distributions

The characteristics of the audit data stream can change frequently. Therefore, the statistics on critical event sequences has to be updated continuously and the signature distribution has to be adapted accordingly. All optimization strategies described above determine an entirely new signature distribution. This requires high reorganization efforts because usually many state nodes have to be moved to other analysis units. Therefore, these strategies should only be applied to get an optimal initial signature distribution. They may be repeated perhaps 2-6 times per day. For the normal analysis process, an iterative adaptation strategy should be preferred which adapts the signature distribution with minimal reorganization continuously. If the resource consumption of the distributed analysis systems runs out of balance signature fragments from high loaded analysis units should be reassigned to less occupied ones. The fragments to be moved can be selected accordingly to one of the following procedures. (a) A fragment from the most occupied analysis unit is reassigned to the least occupied unit. (b) Like (a), but the most suitable fragment is selected whose reassignment rebalances the computation load best. This can be achieved by evaluating the computational loads of the analysis units using the analysis statistics based on equation ( 2). (c) That fragment is chosen from the highest loaded unit which mostly requires repeated event analysis due to delayed state information. Again, the analysis statistics have to be evaluated to select the responsible signature fragment. We consider again nodes v and w of the above example. Let node v be the source of the delayed information and (v, w)  E, then node w is reassigned to the same analysis unit as node v. No additional effort for repeated event analysis will be induced by state information transfers between v and w during further analysis.

After finishing a reorganization step the efficiency gain has to be evaluated. If the adapted analysis distribution is not better than the previous one the reorganization step can be easily taken back due to the low reorganization effort required for single fragments. Thereafter an alternative fragment can be chosen for reassignment.

Evaluation

The distribution strategies described in the last section have been implemented and evaluated using the distributed intrusion detection system DSAM (distributed signature analysis module) that utilizes EDL multi-step signatures [START_REF] Meier | A Model for the Semantics of Attack Signatures in Misuse Detection Systems[END_REF]. DSAM sensors are configurable and forward audit events only to analysis units where they are required. The DSAM analysis units are configurable as well. A set of signature fragments (state nodes) is assigned to each of them. The analysis units transfer automatically state information via the network if needed. For the performance measurements, we applied three typical signatures and examined all possible partitions (assignments) of the contained signature fragments to three analysis units. We evaluated each of the 965 possible partitions. These partitions include very efficient distributions as well as completely inefficient ones which cause an unfavorable computation or network load or both. Because of limited space we only give a brief overview about two of the applied signature examples (see Fig. 4).

The first example (Fig. 4 (a)) describes a link shell attack which exploits a vulnerability of a specific shell function and the SUID (set user ID) mechanism of the Solaris OS. If a link refers to a shell script and the scripts file name starts with a hyphen "-" an attacker can get an interactive shell with the access rights of the script owner (e.g. root) by executing the link. The second signature -the SUID script attack (Fig. 4 To evaluate the analysis efficiency of DSAM in a high load situation we used a generic set of audit data. This set was created by capturing system calls of a host, while the described attacks were executed. All logged system calls that did not belong to the attacks were discarded manually. Thus, the audit data set only contains relevant attack traces of the applied signatures. Concerning the required analysis effort, this represents a stress test and a worst scenario. Additionally, the captured attack traces have been duplicated to create a sufficiently large audit data file of 6,000 events (system calls). The experiments were conducted on four machines (Intel Xeon "Prestonia", 2.66 GHz, 512 KB L2 cache, 2 GB RAM) connected by 1 GE links. One machine executed the sensor; the others run an analysis unit. First we applied the generic audit data set and evaluated the strategy A of Section 3 by assigning the three example signatures to different AUs without fragmenting them. Then we applied the strategy B to fragment and to assign fine-grained signature parts to the analysis units. We evaluated all 965 possible distributions of the signature fragments on the three AUs and measured the runtime separately for each unit. The sensor runtime is related to the slowest AU, as the sensor terminates after transmitting the last audit event to the slowest AU. The third column (ID 0) represents the non-distributed case, where only one AU is used that receives all signatures. This is the benchmark for any optimizations of the described strategies. The fourth column (ID 96) represents the simple, non-fragmented distribution for three AUs. The runtime shows a relevant improvement for the distributed case. The other columns represent the least and most efficient distribution. The diagram in Fig. 5 shows for each of the 965 signature distributions the sensor runtime and the required communication effort (bytes) for transmitting state information and audit events. Each point in the diagram represents a signature distribution and is enumerated with a unique ID. The diagram shows many analysis distributions (at the bottom) that require a low computation effort. Furthermore, the step-wise increase of the communication effort for audit event duplication can be seen. The figure indicates that there are many distributions with reasonable computation and communication effort (lower left corner) that should be selected for efficient analyses.

In order to select a suitable analysis distribution for a given network and CPU utilization a metrics based approach can be used. The metrics shall determine a suitability degree for each signature distribution and resource utilization. We defined a metrics that maps features of the audit event characteristics monitored by the sensor as well as the statistics maintained by the analysis units for a specific signature distribution onto a metrics value M. Simplified, M is defined by equation [START_REF] Sommer | NetFlow: Information Loss or Win?[END_REF].

               C c E e b cl a cl E b a AU i S evT c bal e compC b a commC evT evC M i ) ( ) ( ) , ( ) ( ) ( ) ( , ) , ( # 1 
   (3)
The metrics combines and weights four features of a signature distribution by weight factors (, , …): (a) the communication cost for audit event duplication from equation (1), (b) the state information transfers between analysis units from equation ( 2), (c) the computation effort for transition condition evaluation (IDS core functionality), and (d) a load balance function bal(c) which determines for each analysis unit (cluster c) the deviation of the actual load from the average load of all units. Nevertheless, our experimental evaluation shows that the applied worst case scenario (the events contain a large number of attack traces) is misleading, as we were not able to find a reasonable metrics. The problem results from the additional computation effort for repeated event analysis for delayed state information. This effort changes significantly if the distances between critical event sequences change only slightly. Therefore, the computation overhead for repeated event evaluations dominates the overall runtime of unfavorable signature distributions and cannot be predicted by metrics M. Fig. 6 depicts the logged runtime (sec) together with the metrics prognosis (normalized to range [0,1]) for all 965 distributions. We tried different weight factors as well as additional distribution features to find a reasonable metrics, but we could not identify a common relation between metrics prediction and real runtime (see Fig. 6).

Hence, this kind of metrics cannot be used to predict optimal analysis distributions for the worst case, since they do not take all important computation dependencies between the signature fragments into account. Moreover, a further enhancement by additional statistical information is not desirable because CPU and network consumption change continuously and even minor changes would lead to entirely different distributions. Such a metrics can only discover an initial distribution with a satisfying analysis performance that must be adapted periodically. So, we applied next the iterative optimization strategy E for the worst case. When the dynamically updated sensor statistics and the analysis units suddenly indicate significant changes in the audit data characteristics the current distribution has to be iteratively adapted. In typical IT infrastructures this happens inevitable by changing user and system activities (e.g. daily schedules). Our iterative optimization strategy minimizes first the effort for repeated event evaluations by reassigning the responsible signature fragments. For this, fragments are iteratively selected and moved according to selection procedure (c) of strategy E until no computation effort is spent for repeated event evaluations. Then, as a second objective, the load balance of the analysis units is improved iteratively by selecting signature fragments according to procedure (b). For this, a suitable fragment is chosen from the most loaded analysis unit and reassigned to the least loaded unit. If the subsequent performance evaluation turns out that the new distribution performs worse than the previous one the previous distribution is restored. This causes only minor reorganization effort, as only a single signature fragment is reassigned. Fig. 7 depicts the iterative adaptation of the signature distributions by an annotated fragment of Fig. 5.

Starting from the simple non-fragmented distribution (ID 96), where each of the three signatures is assigned to a different analysis unit, the distribution was adapted by consecutively reassigning single signature fragments generating the distributions with the IDs 92, 66, 80, 77, 80, 87, and 63. Distribution 77 was found to perform worse compared to the previous one after some analysis time. Therefore, it was reverted to ID 80 and another suitable fragment was reassigned (ID 87). The iterative adaptation of the signature distribution stops with distribution 63, when no suitable fragment for a further reassignment step can be found. This happens, when a pretty good balanced (and efficient) signature distribution is reached, such that also the "lightest" fragment from the most loaded analysis unit that requires least computation resources will impair the overall load balance, even if it will be reassigned.

To sum up, in worst case situations we always can apply the iterative optimization strategy starting with a sufficiently efficient non-fragmented signature distribution. Minor changes in the distribution can be easily taken back if they turn out to be misleading. The communication overhead can be estimated in advance. Thus, we can prevent high network utilizations. This strategy may only find semi-optimal distributions, but even these perform better than the distributed analysis of complete signatures.

Summary

The increasing performance of IT systems leads to a rapid growth of audit data volumes. This represents a major challenge for signature based intrusion detection systems, which already have to cope with growing signature databases. In this paper we presented various optimization strategies which aim at balancing the analysis load of complex signature based IDS over distributed analysis units. We focused on the analysis of multi-step signatures because complex attacks, i.e. on application level protocols (Web 2.0), will be much more important in the future, while simply structured attacks can be successfully prevented by today's proactive measures (e.g. address space layout randomization, stack protection). A prototype implementation was used to evaluate the achievable performance improvements by the various proposed optimization strategies. Our results indicate that relevant improvements in the efficiency of audit event analyses can be only obtained by a fine-grained assignment of fragmented signatures. But, the results also indicate that poorly chosen distributions require much more computation effort than the non-distributed baseline. Our results also show that a dynamic approach which iteratively adapts the signature distribution to the current analysis situation during runtime should be favored over a statically determined optimal signature distribution. As future work, we plan to integrate our prototype into a multi-agent platform to build up a distributed intrusion detection system responsible for securing an IT infrastructure (e.g. a company network). The system will analyze audit events from many widely distributed sensors and adapt dynamically to changes of the audit stream characteristics, analysis load, available free computation resources, and network bandwidth.

Fig. 1 .

 1 Fig. 1. Elements of a distributed signature analysis

Fig. 2 .

 2 Fig. 2. Example of a simple, non-fragmented signature distribution

Fig. 4 .

 4 Fig. 4. (a) Shell link and (b) SUID script attack

Fig. 6 . 7 .

 67 Fig. 6. Metrics prognosis and real runtime Fig. 7. Iterative optimization of distributions

  illustrates the problem. ID: ...7, 8, 9, 10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25, ...

	sensor	.		t			Event type sequence within Δt	Absolute frequency
								AB	18
	AU 1	network delay: t	AU 2	BC	6
	v	A	si.id = 11	w	B	x	C	y
	host 1		assign w to AU 1 or AU 2 ?	host 2

evT: ..

., A,A,B,A,A,B,B,B,B,B,B,C, A,B,A,D, A,B,A,…

Fig.

3

. Unfavorable sequence of audit events Table

1

. Event type sequences

  (b)) -describes how to gain administrative privileges in Solaris by exploiting a vulnerability of the extended file access rights.

	rename
	link
	rename link link w/o "-" create link w/o "-" initial	delete link delete link	no attack	initial	start script w. critical	execute shell cmd. w/o path start child running script ex. shell script cmd.
	link w. "-" create link with "-"	execute	link attack		path env.	terminate script	w/o path	attack SUID
	rename link	link	(a)			no attack		(b)

Table 2

 2 contains the values for some selected distributions.

	distribution ID	0	96	302	626	912 778	958 945 905 899 879 951 900 901 885 882 880 946 947 860 858 857 844 842 833 831 817 814 813 812 811 795 79 2 807 910 956 944 898 863 815 793 79 1 79 0 789 785 78 2 781 78 0 770 76 8 76 3 76 1 759 757 74 4 742 73 6 73 4 733 731	957 911 816 79 4 741 772 771 73 9
						955 953 952 954 948 906 936 908 909 907 904 903 950 949 902 890 884 883 881 875 861 859 853 841 839 836 834	862
							358 336	360 359 338 324 337 314	315 306	325	357	335
						962 916 895 960 941 931 886 865 864 915 871 856 848 846 820 819 818 809 804 79 8 797 79 6 943 961 925 887 878 876 870 897 854 843 837 832 830 829 937 926 891 827 810 808 803 802 800 78 8 78 7 78 6 78 3 779 777 776 775 773 769 767 76 6 764 762 760 758 756 755 753 928 74 3 73 8 737 73 5 73 2 73 0 72 9 727 72 2 72 0 719 718 715 714 713 712 711 710 70 9 708 70 7 70 6 698 697 696 695 694 693 692 691 690 689 688 687 686 685 684 682 680 679 678 959 942 914 913 896 74 8 740 726 725 683 681 677 673 672 671 670 669 668 667 666 664 663 661 659 657656 655 605 603 602 600 59 8 596 595 59 3 590 58 8 58 7 58 5 583 581 580 579 571 570 56 9 56 8 56 7 56 6 56 5 56 1 54 9 54 8 54 7 54 6 54 5 54 4 54 3 53 9 536 53 5 53 4 53 2 526 52 5 52 4 52 2 517 515 513 511 50 5 50 4 50 3 50 2 50 1 50 0 499 495 494 493 492 491 746 806 78 4 74 9 490 489 488 487 486 484 483 482 481 479 478 477 474 472 471 469 467 465 464463 387 385 384 382 379 376 374 377 363 362 361 717 716 349 341 340 339 327 326 320 316 310 309 307	751
						965 929 930 921 919 868 822 927 938 939 893 892 889 840 935 917 894 888 963 964 940 918 877 874 872 866 855 852 851 849 838 835 826 825 651 650 649 648 647 646 645 641 640 639 638 637 636 635 634 633 632 630 629 628 627 625 624 623 620 618 617 615 613 611 610 609 574 573 572 564 56 3 56 2 56 0 538 552 551 550 54 2 54 1 54 0 53 7 533 53 1 52 7 52 1 52 0 518 510 50 9 394 392 391 389 372 370 369 368	52 3
						356 319 19 6 334 347 328 19 8 350 19 5 19 3 19 1 18 9 18 8	354 332 173 171 16 7 16 6 16 4 16 2 333 18 2 16 0 152 151 150 14 8 14 7 14 6 14 5 14 4 14 3 18 3 18 1 346 18 7 177 159 157 14 2 14 0 13 8 13 7 13 6	311	355 172	321	323 313
						933 869 847 828 805 801 774 76 5 754 745 873 845 79 9 932 752 750 74 7 728 72 4 665 662 660 658 654 653 652 924 59 9 58 9 58 6 58 2 575 823 601 922 72 3 70 5 70 4 70 3 702 701 70 0 699 592 59 1 58 4 578 577 558 557 556 554 53 0 516 514 512 50 7 498 497 676 675 674 52 9 496 485 480 476 475 473 470 468 466 462 461 460 459 458 457 456 455 454 453 449 447 446 445 448 444 443 435 433 432 431 409 407 406 404 402 400 399 398 386 383 381 380 378 375 373 365 353 348 576 604 59 7 594 352 351 342 331 330 329 322 317 312 308 213 212 211 210 209 208 207 205 203 202 201 18 0 179 178 170 16 9 16 8 16 5 16 1 156 155	72 1 442 441 440 438 437 436
						626 619 616	934 867 824 923 850 644 643 642 631 622 621 920 614 612 608 607 606 388 393 390 371 821 519 50 8 553 506 428 427 559 555 528 426 422 424 423 421 420 419 418 416 414 413 412 367 366 364
						343 18 6 18 5 19 2 18 4	19 7	19 4 19 0	345 176 174 16 3 14 9 13 3 13 5 14 1 153 158 13 9 13 4 13 2 13 1 115 113 112 111	12 9 12 8 12 7	318	12 4 12 3	12 6	12 5
						344 206 200 19 9	204	395 119 118 117 154	175 12 1	450 401 408 403 397 396 12 0	452 430429 434 405 451	439
										417 411 410	415	425
										114	13 0	12 2

Table 2 .

 2 Runtimes of selected distributions

					1,E+06
	sensor real [s] 47.95 29.63 110.64 19.72
	AU 1 AU 2	real [s] 47.63 37.72 110.66 19.75 user [s] 46.89 28.67 108.47 17.95 real [s] 29.33 116.34 25.44 user [s] 9.83 33.89 18.08	communication effort (byte)	9,E+05
	AU 3	real [s]	32.39 113.72 23.45
		user [s]	7.84 17.97 17.97
					15	25	35	45	55	65	75	85	95
										real runtime (sec)
				Fig. 5. Runtime and communication costs for
				different signature distributions


Rick Hofstede
email: r.j.hofstede@student.utwente.nl

Idilio Drago
email: i.drago@utwente.nl

Giovane C M Moura

Aiko Pras
email: a.pras@utwente.nl

Carrier Ethernet OAM: An Overview and Comparison to IP OAM

Keywords: Network Management, Carrier Ethernet, Metropolitan Ethernet, Provider Backbone Bridging, Ethernet OAM, IP OAM 1

Introduction

Ethernet has been the number one link-layer technology in local area networks (LANs) for a long time [START_REF] Mcfarland | Ethernet OAM: Key Enabler for Carrier Class Metro Ethernet Services[END_REF]. To make Ethernet suitable to be used in larger networks, such as metropolitan and wide area networks (MANs and WANs respectively), it was extended to provide high availability, quality of service, secure communication, and superior scalability [START_REF] Mcfarland | Ethernet OAM: Key Enabler for Carrier Class Metro Ethernet Services[END_REF]. Carrier Ethernet 1 allows service providers to offer connectivity at the Ethernet level, in contrast to the IP level. Some backbone network operators are already considering a deployment of Ethernet in their Next-Generation Network [START_REF]GigaPort3 and SURFnet7[END_REF].

With the deployment of Carrier Ethernet services it is required to manage Ethernet in an end-to-end manner, besides managing it on the link-layer. To achieve this, IEEE and ITU-T have standardized two Operations, Administration & Maintenance (OAM) protocol suites by means of IEEE 802.1ag [3] and ITU-T T.1731 [START_REF]OAM functions and mechanisms for Ethernet based networks[END_REF], respectively. Ethernet OAM offers end-to-end fault and performance management over Ethernet Virtual Connections (EVCs), which are logical connections between various customer sites [START_REF] Chiruvolu | Issues and Approaches on Extending Ethernet Beyond LANs[END_REF].

From a functional point of view, the Ethernet OAM standards seem to be very similar to IP OAM protocols, such as Ping and Traceroute. Assuming that most Carrier Ethernet devices support IP OAM, one could wonder whether OAM functionality is now duplicated at both the link and network layer. Moreover, if this is the case, could IP OAM functionality be used as a replacement for Ethernet OAM? Since IP OAM has been used already for a long time, operators have more experience with it than with Ethernet OAM. This lead us to the following research questions:

1. What exactly is Carrier Ethernet and which functionality does it provide? 2. How does Ethernet OAM functionality compare to IP OAM, and, more specifically, can IP-based protocols in Carrier Ethernet networks provide the same functionality as comparable Ethernet OAM management techniques?

Since many papers have already been published on the topic of Ethernet OAM, we will first review those that focus on using alternative solutions for Ethernet OAM in Section 2. Section 3 describes the evolution of Ethernet towards a WAN protocol, especially for deployment in service provider environments. The Ethernet OAM standards for managing Carrier Ethernet networks are discussed in Section 4. Although several works state that IP OAM is not (entirely) suited to manage a Carrier Ethernet [START_REF] Mcfarland | Ethernet OAM: Key Enabler for Carrier Class Metro Ethernet Services[END_REF] [5], a clear explanation or motivation is not provided. Section 5 will fill this gap by defining an Ethernet OAM deployment scenario, by means of which an IP-based approach will be analyzed. Finally, we close this paper in Section 6, where we draw our conclusions and future work.

Related Work

Many studies have already been performed on the usage of Ethernet OAM for WANs. McFarland et al. [START_REF] Mcfarland | Ethernet OAM: Key Enabler for Carrier Class Metro Ethernet Services[END_REF] state that enterprise networks typically have straightforward topologies and that IP-based protocols such as SNMP, ICMP, Ping and Traceroute will suffice for management. However, it will not be suitable for managing service provider networks, carrying thousands of services for different customers. Motivations for the unsuitability of IP are not given.

Indukuri goes beyond IP-based protocols for managing Ethernet networks [START_REF] Indukuri | Pseudowire VCCV -BFD vs Ethernet OAM[END_REF], by outlining the use of IP Ping, MPLS LSP Ping, Bidirectional Forwarding Detection (BFD) and especially Ethernet OAM for Virtual Circuit Connectivity Verification (VCCV). It is desirable for metropolitan and especially critical networks to have a fast and accurate fault detection mechanism. Such a sub-50 ms detection and restoration facility is provided by BFD and Ethernet OAM. The author concludes, however, that the choice for a VCCV mechanism should not only depend on technical decisions, but also on the underlying transport infrastructure. In the case that a virtual circuit is constructed on top of an Ethernet network (e.g. an Ethernet Virtual Connection (EVC)) and end-to-end management should be performed, it is wise to use Ethernet OAM in order to avoid the need for translation layers between different network layers. However, this work does not outline why IP-based management techniques do not suffice for the management of Carrier Ethernet networks.

During its evolution from a LAN technology to a MAN and WAN technology, Ethernet was extended to support customer traffic separation, quality of service (QoS) and, most importantly, a greater number of MAC addresses (of customers, among others) in the forwarding tables of switches [START_REF] Allan | Ethernet as Carrier Transport Infrastructure[END_REF]. The frames of the various Ethernet standards are depicted in Figure 1. 'Ethertype' and 'Frame Check Sequence' fields are left out for the sake of space. The evolution of Ethernet has been standardized by the IEEE in several standards, starting with IEEE 802. 1Q [8]. This standard adds a VLAN tag to an Ethernet frame, right after the source and destination MAC addresses, by means of which the forwarding plane can be partitioned into logical segments.

In the same year as IEEE 802.1Q was standardized, an amendment was defined in IEEE 802.1ad [START_REF]Virtual Bridged Local Area Networks -Amendment 4: Provider Bridges[END_REF], also known as Provider Bridging (PB). We assume this standard and all following ones to be Carrier Ethernet standards. The IEEE 802.1Q VLAN tag contains VLAN IDs of 12 bits, supporting up to 4094 VLANs. Although this number of VLANs will be enough for most LANs, it will not suffice for large service provider environments. To overcome this scalability problem [START_REF] Allan | Ethernet as Carrier Transport Infrastructure[END_REF], IEEE 802.1ad defines VLAN tag stacking, allowing service providers to insert an additional VLAN tag of 12 bits in an already tagged frame. This 'S-VID' VLAN tag is only used inside the service provider domain and is inserted in front of the initial VLAN tag, which is now referred to 'Customer VID' (C-VID).

IEEE 802.1ah [10], also known as Provider Backbone Bridging (PBB), allows a strict separation between customer and service provider domains by encapsulating customer traffic. This is achieved by inserting a new Ethernet header in front of the existing one, including a new backbone VLAN tag (B-VID) and a new 'Service Instance ID' (I-SID) field. The latter can be considered an extended VLAN ID, used to identify customer instances inside the operator network. By considering the entire PB frame as payload and inserting a new Ethernet header in front of it, a completely isolated address space is used inside the Ethernet backbone network. The result is a drastically reduced complexity/size of the forwarding tables in backbone nodes, since only backbone node addresses and backbone VIDs are needed for switching. The most recent Carrier Ethernet standard is IEEE 802.1Qay [11]. It uses the same frames as IEEE 801.ah (PBB), but it adds traffic engineering capabilities and related rapid protection against failures [START_REF] Bottorff | Scaling Provider Ethernet[END_REF]. IEEE 802.1Qay is therefore referred to as Provider Backbone Bridging with Traffic Engineering (PBB-TE). It adds support for static, traffic-engineered paths by replacing the use of the spanning tree protocol (STP) by an external method. Besides disabling STP, also broadcasting and MAC address learning are disabled [START_REF] Lee | Autonomous Client Discovery in Backbone Edge Bridges for Multipoint PBB-TE Networks[END_REF]. Broadcast traffic and traffic for unknown destinations are discarded by the edge nodes of the network.

In the next section we present Ethernet OAM, by means of which fault and performance management have been added to Ethernet.

Ethernet OAM

End-to-end OAM has been added to Ethernet by means of IEEE 802.1ag & ITU-T Y.1731. While these standards had different focal areas when work on them started, IEEE 802.1ag is nowadays considered a subset of ITU-T Y.1731. Both standards cover fault management, while performance management is solely covered by ITU-T Y.1731. Fault management can be used for detecting and isolating faults in a network, just as notifying about faults. Performance management allows to measure throughput, delay, etc. This will help to verify and prove service performance against a Service-Level Agreement (SLA) [START_REF] Ryoo | OAM and Its Performance Monitoring Mechanisms for Carrier Ethernet Transport Networks[END_REF], for instance.

Before the Ethernet OAM management techniques can be discussed, some terminology needs to be described. Maintenance End-Points (MEPs) are actively managed components, which are positioned at Maintenance Domain (MD) boundaries. Interconnected MEPs are called a Maintenance Entity (ME). A Maintenance Entity Group (MEG)2 can include several MEs, depending on the topology: for point-to-point Ethernet connections, a MEG contains a single ME. In a multipoint setup, a MEG consists of several MEs. Inside a ME, and thus between MEPs, one or more Maintenance Intermediate-Points (MIPs) can be placed. MIPs only react to OAM flows, while MEPs initiate and terminate them. In order to have management hierarchies, OAM levels can be defined to run OAM mechanisms completely separated. These concepts will be highlighted again in Section 5.1, where a deployment scenario for Ethernet OAM will be discussed.

The remainder of this section will focus on the most commonly known/used Ethernet OAM management techniques.

Continuity Check

Continuity Check (CC) can be used to detect interruptions in connectivity (and thus continuity) between end points (MEPs) in an Ethernet network. This is accomplished by transmitting 'heart-beat' messages between MEPs, which are forwarded by MIPs. By doing so in a periodic manner, connectivity can be verified. MEPs exchange CC messages with the other MEP inside the same ME, and at each administrative OAM level.

Loopback

Loopback (LB) provides a way to transmit request/response messages, in order to verify bi-directional connectivity with another MEP or MIP. Upon reception of a LB message, a response message is returned towards the requester. In contrast to Continuity Check, which sends messages in a periodic fashion, LB messages are typically initiated by operator command, although nodes can be configured to transmit LB messages in a periodic fashion as well.

Link Trace

Link Trace (LT) can be used to isolate faults in Ethernet networks. MEPs send out LT messages on a particular ME, in order to identify the connectivity and relationships with remote MEPs and MIPs. While a LT can only be initiated by a MEP, all MIPs and MEPs downstream the path towards a destination MEP at the same OAM level will respond to it.

Alarm Indication Signal

Alarm Indication Signal (AIS) provides a method for notifying operators about a network anomaly. As soon as a MIP detects a failure at its OAM level, it will send out an AIS message towards the reachable peer MEPs of the same ME. After the MEPs receive the AIS from the MIPs, they will send out a multicast AIS message in the upstream direction of a fault, at the next most superior OAM level and on every service provider VLAN affected by the failure. AIS is not supported by IEEE 802.1ag.

Loss Measurement

Loss Measurement (LM) offers a way for operators to determine the amount of frame loss in an Ethernet network, over an EVC for instance. More precisely, it is the ratio between undelivered OAM frames and the total number of OAM frames transmitted during a specific time interval.

ITU-T Y.1731 defines two types of LM:

1. Single-Ended. LM messages are transmitted to another MEP, which includes transmission and reception frame counts in its response message. In this case, only the LM initiator is able to derive frame loss from the counters (since it does not include its local counters in the initial LM message). 2. Dual-Ended. Continuity Check messages are used to carry frame transmission and reception counters. In contrast to the single-ended approach, this approach allows all MEPs inside a ME to derive frame loss, instead of only the initiating node.

Delay Measurement

Delay Measurement (DM) can be used for measuring delay in a Carrier Ethernet network. The unit of measurement is the round trip delay of a frame, measured from its first transmitted bit, until the reception of its last bit. Since a DM frame needs to be sent back to its originating node, LB messages are used. Two types of DM can be identified:

1. One-way measurement. An initiating MEP includes a transmission timestamp in the Ethernet frame. The destination node will capture the frame reception timestamp, and compare both timestamps. As a consequence, the clocks of the sending and receiving nodes need to be synchronized. 2. Two-way measurement. In contrast to the one-way measurement, this DM type does not require clock synchronization. The initiating node still includes a timestamp in the Ethernet frame. After the destination node performs a loopback on the frame, the initiating node will receive the frame again. On reception, this node will capture the reception timestamp. Finally, the difference between the timestamps can be calculated.

Comparison to an IP-Based Approach

The Ethernet OAM management techniques discussed in the previous section are, from a functional point of view, very similar to IP-based management techniques. A few examples:

-Ethernet OAM Continuity Check resembles a uni-directional IP Ping.

-Ethernet OAM Loopback verifies connectivity with a MEP or MIP, by performing a loopback on a frame. This is similar to IP Ping. -Ethernet OAM Link Trace offers comparable functionality as IP Traceroute.

Both techniques allow to trace a path between nodes through a network. Instead of using a 'time-to-live' (TTL) field in a frame header, MEPs/MIPs pass LT messages downstream the path towards a destination node. -Ethernet OAM Alarm Indication Signal is able to send out notifications to the reachable MEPs of Maintenance Entity (ME). SNMP allows the transmission of traps/notifications to a SNMP manager as well. -Ethernet OAM Loss Measurement & Delay Measurement offer similar features as certain SNMP Management Information Bases (MIBs) do.

As we outlined in the Introduction, we would like to verify whether it is possible at all, or until which extent, to manage Carrier Ethernet networks with IP-based protocols. In order to do so, IP needs to be supported on top of the Ethernet infrastructure. Although this seems to contrast the principle of having a pure Ethernet network, most network devices already have an IP interface for management purposes, in order to support a Web interface, Telnet, SSH, syslog or SNMP, for instance. Since it might not be desirable to have a full IP infrastructure on top of an Ethernet backbone network, we assume that IP will not be used for routing purposes and that all managed devices take part in a management VLAN. This has the following consequences:

1. Only devices inside the same management VLAN and IP domain are reachable. However, it can be advantageous for end-to-end EVC management to have nodes reachable from outside a specific domain, for instance. 2. The IP TTL field value is not lowered on Ethernet network hop transition. 3. Since frames destined to a node (identified by a B-MAC and B-VID) for which no path has been defined will be discarded by ingress Backbone Edge Bridges (BEBs), paths from a management node to all managed devices need to be defined.

In order to verify whether an IP-based approach could be used to manage a Carrier Ethernet network, we defined a typical deployment scenario for a Carrier Ethernet, in which Ethernet OAM could be deployed. It will be used to analyze an IP-based approach for managing a Carrier Ethernet network.

Deployment Scenario

Figure 2 shows our deployment scenario for a Carrier Ethernet network. Four customer sites are shown, belonging to two different customers (A and B). Customers can be end customers, service providers, operators, and access or aggregation networks [START_REF] Luyuan | The Evolution of Carrier Ethernet Services -Requirements and Deployment Case Studies[END_REF]. Both customers acquired an EVC between their two sites. The result is a (virtual) one-hop connection between the customer-facing switch ports of the edge devices. The transport network considered here is based on IEEE 802.1Qay (PBB-TE).

A customer site is connected to a BEB, which consists of two components [START_REF] Luyuan | The Evolution of Carrier Ethernet Services -Requirements and Deployment Case Studies[END_REF]: I-Components are used for bridging in the customer space, based on customer MAC addresses and S-VIDs. B-Components are used for bridging in the provider domain based on B-MAC addresses and B-VIDs [START_REF] Luyuan | The Evolution of Carrier Ethernet Services -Requirements and Deployment Case Studies[END_REF]. The I-Component is often called Customer Premises Equipment (CPE). A CPE is the last hop between a service provider network and a customer's equipment [START_REF] Sofia | A Survey of Advanced Ethernet Forwarding Approaches[END_REF]. The two components of a BEB can be either in one or in two devices. In Figure 2, the components of the left BEB are in separate devices. EVCs are established between two CPEs.

The next hop after the first BEB is one of the Backbone Core Bridges (BCB), depending on the B-VID onto which the frame's I-SID (Instance ID) got mapped. Although a PBB network is considered here, the BCBs consider the frames as normal (VLAN-tagged) Ethernet frames. This is because the first three fields of the Ethernet header are the same for PB, PBB and IEEE 802.1Q, as shown in Figure 1. After the BCBs, the (BEB) egress switch of the backbone network is the next hop. The I-Component and B-Component are now packed into one device and perform the same tasks as the first BEB, but in reverse order.

Section 4 discussed how Carrier Ethernet networks could be managed by using either IEEE 802.1ag or ITU-T Y.1731. These standards require managed nodes to be either a Maintenance End-Point (MEP) or Maintenance Intermediate-Point (MIP). In our deployment scenario, (B-Components of the) BEBs are assigned the role of MEP and BCBs the role of MIP. Three Maintenance Entities (MEs) can be identified, one for each path through the network, so that each MEP is taking part in three MEs. In this work we consider only the operator's OAM mechanisms and a single OAM level.

The remainder of this section discusses the use of IP-based protocols in place of Ethernet OAM management techniques.

Continuity Check & Loopback

To automate Ping message transmission and to make it easier for an operator to handle this, a 'Remote Ping' MIB, which is part of the DISMAN (short for 'Distributed Management') framework, could be used. It lets a 'Local host' command a 'Remote host' to perform a Ping to a 'Target host'. Assuming that all nodes are reachable by the 'Remote host' and have a 'Remote Ping' implementation, a network operator could issue a Ping request from and to each node inside the same VLAN.

Compared to Ethernet OAM, the following advantages can be identified when using IP Ping:

-When using IP Ping, both source and destination nodes can detect a failure.

Request messages can be sent in a periodic fashion, and a destination node must be configured to expect them in that fashion as well. When a reception timeout occurs, a faulty link or device can be assumed. This is not possible with Ethernet OAM CC, which is uni-directional by definition. -All nodes between which a path exists in a PBB-TE network, can exchange IP Ping messages by means of the DISMAN framework. If such a path does not exist, frames will be dropped by the edge switches. The same is done for broadcast traffic [START_REF] Lee | Autonomous Client Discovery in Backbone Edge Bridges for Multipoint PBB-TE Networks[END_REF]. Ethernet OAM CC and LB can only be initiated and terminated by MEPs. Therefore, the set of nodes reachable by IP Ping can be larger than the amount of nodes reachable by Ethernet OAM.

Besides these advantages, also several disadvantages can be identified:

-Without network-layer routing, the set of manageable nodes is restricted to a single IP/management domain. In contrast, Ethernet OAM can be performed in an end-to-end manner over an EVC for monitoring a single service, spanning multiple domains. It is not possible for a service provider to inject (IP) packets into an EVC to verify its functioning in an end-to-end manner. -It is hard to ensure that IP Ping takes the path of a particular EVC, to ensure its connectivity. When customer data arrives at an ingress BEB, it is mapped onto a B-VID, which takes a predefined path through the network.

It is hard to ensure that the management VLAN uses exactly the same path. -A per-customer/EVC granularity requires several translation steps. Since Ethernet OAM allows the verification of an EVC, it is immediately clear which customers are affected by a fault. More knowledge about the network is required with IP-based protocols, in order to derive the same information. Operators will need to know onto which VLAN the customer traffic is mapped. This involves active cooperation with other parties, since operators normally do not know how others mapped customer traffic onto the VLANs.

Customers can also be involved in monitoring an EVC by using IP Ping. They will, however, see the EVC service as a one-hop path. As such, they will be able to detect a problem on the EVC, but without being able to isolate it.

The deployment scenario discussed before can also be made more complex, by considering multiple operator networks between the customer sites. Customers will still see the provider domain as a one-hop connection. As soon as a customer detects a problem without Ethernet OAM, it is up to the service provider 4 to find out which operator network causes the fault. Assuming that the path of the operator's management VLAN is the same as the customer's EVC, fault isolation with IP Ping is possible. With Ethernet OAM however, several (external) nodes could be configured as MIPs, so that a service provider could isolate a fault directly, even if it is located in another administrative domain.

Link Trace

In a similar way as we discussed the replacement of Continuity Check and Loopback by IP Ping, we assume the use of IP Traceroute as a replacement for Link Trace (LT). By adjusting the value in the 'time-to-live' (TTL) field of the IP header, the path through the network can be traced. Since IP is only used inside the management VLAN and not used for routing purposes, intermediate nodes towards a destination will never modify the TTL field value. All traces will then consist of one-hop connections and link tracing by using IP Traceroute will therefore never work in our deployment scenario.

Alarm Indication Signal

Ethernet OAM allows the transmission of fault notifications by means of an Alarm Indication Signal (AIS). In IP-based networks, SNMP traps can be used for the transmission of notifications from agents to managers. Several default traps have been defined, such as 'linkup' and 'linkdown'. When a node inside the network detects a failure, it could send out a trap to an SNMP manager.

SNMP as a replacement for AIS offers several advantages:

-SNMP traps can be sent out to an arbitrary set of SNMP managers inside the management VLAN, while AIS can only be sent out to MEPs. -SNMP offers more flexibility in defining trap structures, by allowing the definition of custom ('enterprise-specific') traps. An arbitrary set of variables can be included in a SNMP trap. Also different traps can be sent for different purposes, while Ethernet OAM AIS has a fixed structure.

Besides these advantages, several disadvantages can be identified. At first, AIS can be multicasted on each S-VLAN affected by the failure automatically. This is also possible with IP-based solutions, but this requires more overhead in deriving the EVCs/customers affected by a failure. Second, SNMP traps can only be sent out inside a single IP/management domain.

Loss Measurement

Ethernet OAM Loss Measurement (LM) calculates the frame loss between two MEPs, by comparing the difference between OAM frame transmission and reception counters at the MEPs of a particular ME. By means of the RMON-MIB [START_REF] Waldbusser | Remote Network Monitoring Management Information Base[END_REF], SNMP manages Ethernet interface counters, such as 'etherStatsPkts'. Although this counter keeps track of the sum of ingoing and outgoing frames, it is possible to define an 'enterprise-specific' MIB which manages these counters individually. Some MIBs exist for this purpose, such as a 'Round Trip Time Monitoring' (RTTMON) MIB and 'Service Assurance Agent' of Cisco.

The use of SNMP for LM offers several advantages:

-Arbitrary values can be retrieved, depending on the used MIB. To do the same with SNMP, an 'enterprise-specific' MIB would be needed to differentiate between frame sources or types for measuring frame loss between two network end points. Besides that, SNMP PDUs can only transmitted inside a single management/IP domain. This has been discussed in Section 5.2.

Delay Measurement

The use of IP Ping for managing Ethernet networks has been discussed before. This protocol provides round trip delay measurements together with its results. Although Ethernet OAM DM offers some sophisticated ways to compensate for processing times at end nodes, round trip delays can be measured by using IP Ping inside the management VLAN as well. This results in the same advantages and disadvantages as described before in Section 5.2. Besides that, several SNMP MIBs have been defined for the purpose of delay measurement, such as Cisco's RTTMON MIB, as discussed in the previous subsection.

Conclusions

This paper presented an overview of the various Carrier Ethernet standards and the related Ethernet OAM mechanisms. By considering a specific deployment scenario for a Carrier Ethernet operator network, an IP-based approach for managing these networks has been analyzed.

In the first section of this paper, two research questions were addressed:

1. What exactly is Carrier Ethernet and which functionality does it provide? Compared to the initial Ethernet standard for LANs, especially scalability improvements have been added to Ethernet. This allowed Ethernet to deal better with a greater number of MAC address in wide area networks. Due to this network scale increase, management of Ethernet became much more important than before. As a result, a set of management techniques was defined, in order to manage Ethernet on the Ethernet layer. When Ethernet is used in large-scale networks and manageable by using Ethernet OAM, it is commonly referred to as 'Carrier Ethernet' or 'Metropolitan Ethernet'. 2. How does Ethernet OAM functionality compare to IP OAM, and, more specifically, can IP-based protocols in Carrier Ethernet networks provide the same functionality as comparable Ethernet OAM management techniques? From a functional point of view, the various Ethernet OAM management techniques appeared to be very similar to IP OAM protocols, such as Ping, Traceroute and SNMP. For a single operator domain, most IP-based protocols discussed in this paper are able to provide similar functionality, as their Ethernet OAM 'counterparts'. IP Traceroute is the only protocol that turned out not to be functional at all. Besides that, the scope of an IPbased approach is limited to a single management/IP domain, since network layer routing was not considered in our deployment scenario. Consequently, IP-based protocols are not deployable in an end-end-end fashion over an Ethernet Virtual Connection, which makes it impossible to verify the endto-end service offered to a customer. IP-based protocols are therefore not a suitable replacement for Ethernet OAM in operator environments.

As future work, a multi-domain Carrier Ethernet deployment could be investigated. Besides that, the use of other OAM techniques for Carrier Ethernet networks, such as MPLS OAM or SDH OAM, could be investigated.

Fig. 1 .

 1 Fig. 1. Evolution of Ethernet frames

1 .Fig. 2 .

 12 Fig. 2. Deployment scenario of a PBB-TE network with Ethernet OAM

  The IF-MIB and RMON-MIB offer a rich set of counters and other interface statistics. Ethernet OAM LM only allows OAM frame counters to be retrieved. -SNMP PDUs can be sent to an arbitrary set of SNMP managers inside the management VLAN. If all nodes have the IF-MIB/RMON-MIB deployed, a SNMP manager can retrieve the counter values from each of these nodes. Ethernet OAM LM only allows MEPs to calculate loss on a path. Ethernet OAM LM measures OAM frame loss between MEPs inside a single ME. As such, frames coming from nodes outside the ME are not considered.

This terminology is based on ITU-T Y.1731. In IEEE 802.1ag, a MEG is called a Maintenance Association (MA).

Whether an I-Component inserts PBB header or not depends on vendor implementation.

We assume the service provider network here to consist of at least two operator networks.

Acknowledgements

This research work has been supported by SURFnet's GigaPort3 project for Next-Generation Networks and the EU FP7-257513 UniverSelf Collaborative Project. Special thanks to Mark Prins from TNO-ICT for his valuable contribution to the research.


Shahriar Bijani
email: s.bijani@ed.ac.uk

David Robertson

Intrusion Detection in Open Peer-to-Peer Multi-agent Systems

Keywords: Security, Confidentiality, Multi-agent Systems, Electronic Institutions, P2P networks, Light Weight Coordination Calculus (LCC)

One way to build large-scale autonomous systems is to develop open peer-to-peer architectures in which peers are not pre-engineered to work together and in which peers themselves determine the social norms that govern collective behaviour. A major practical limitation to such systems is security because the very openness of such systems negates most traditional security solutions. We propose a programme of research that addresses this problem by devising ways of attack detection and damage limitation that take advantage of social norms described by electronic institutions. We have analysed security issues of open peer-to-peer multi-agent systems and focused on probing attacks against confidentiality. We have proposed a framework and adapted an inference system, which shows the possibility of private information disclosure by an adversary. We shall suggest effective countermeasures in such systems and propose attack response techniques to limit possible damages.

Introduction

We have focused on open peer-to-peer (p2p) multi-agent systems (MAS), in which electronic institutions [START_REF] Esteva | Engineering open multi-agent systems as electronic institutions[END_REF] are used to form the interaction environment by defining social norms for group behaviour. An open system is a system that allows new components, which may have been created by different parties or for different objectives, not known at design time, to interact at runtime [START_REF] Poslad | Towards improved trust and security in FIPA agent platforms[END_REF]. An open p2p multiagent system is an open system in which autonomous peers can join and leave freely [START_REF] Esteva | Engineering open multi-agent systems as electronic institutions[END_REF]. Open MAS have growing popularity (e.g. in social networks, e-commerce, social simulation and workflow systems) and are predicted to have many applications in the future [START_REF] Artikis | Specifying norm-governed computational societies[END_REF]. In these open systems, peers may invent the protocols (electronic institutions) themselves and share them with others or use other (unknown) peers' protocols. We address confidentiality of open p2p MAS with dynamic protocols.

Although we focus on the open p2p MAS, we can extend the scope of our secrecy analysis without much difficulty to similar domains such as web services.

Even

Over

Our sugg p2p multi-a only will be that do not framework i 2. The process model of the system is extracted by a process mining tool (ProM 1 ). 3. The extracted process model is converted to LCC interaction models. 4. LCC interaction models are converted to a conceptual representation. (Section 3) 5. The secrecy of the conceptual representation (that represents the interaction model) is analysed using an inference system that shows what an adversary could infer from the interaction model. (Section 3) 6. The interaction model will be fixed if there is any information leak exists. 7. Steps 4 to 6 will be repeated to double check the amended interaction model. 8. The source of the information leak problem and the amended interaction model with some annotations will be sent to the domain expert of the original system.

Probing Attacks and Countermeasures

We analysed possible attacks on open p2p MAS as a part of our work and selected probing attack to address it. We redefine the probing attack [START_REF] Anderson | Tamper resistance: a cautionary note[END_REF] in conventional network security to be applicable in MAS. A probing attack in network security is an attack based on injecting traffic into the victim's network and analysing the results.

In our case, an adversary could infer information not only from the interaction model itself, but also from the local knowledge of other peers. An adversary could control other peers' behaviour in an interaction, by publishing a malicious interaction model. Furthermore, it could access the private local knowledge (e.g. decision rules and policies) of the victim peer by injection of facts to the peer's knowledge-base, asking queries and analysing the queries result.

The first step in our secrecy analysis is converting interaction models to simpler logical representations in order to illustrate only the related parts of the LCC code to the security evaluation. What we need for our conceptual representation is a more minimal interpretation of LCC, which reflects information leaks or helps to find knowledge leakage. We should interpret interaction models for each scenario differently, to be able to discover information leaks and consequently to achieve more accurate secrecy analyses.

After the conceptual representation of interaction models we could analyse them to detect any possibility of a probing attack. We are going to use a security type system to analyse information flow properties in LCC interaction models. Meanwhile we used the Becker's inference system [START_REF] Becker | Information Flow in Credential Systems[END_REF] for detectability 2 to analyse secrecy, because it was compatible with our conceptual representation. Although this inference system has been created for credential-based authorisation policies (such as Datalog), with some modifications, it could also be used to detect probing attack on open MAS. We want to know if an adversary injects expressions into the agent's private knowledge-base and asks a query, what else the adversary will infer from the knowledge-base. To answer this question we used the inference system in [START_REF] Becker | Information Flow in Credential Systems[END_REF]. 1 ProM is an open-source framework for implementing process mining tools in a standard environment (www.processmining.org). We selected it as a working example of process mining systems. 2 Detectability (or non-opacity) is an information flow property that shows the ability to infer a specific predicate from a set of rules.

Two reasons that security problems might lead to probing attacks on choreographic systems are: [START_REF] Anderson | Tamper resistance: a cautionary note[END_REF] no distinguishing notion of private and public data in choreography languages (such as LCC) and ( 2) no mechanism for information leakage control in their interaction models. Hence, two countermeasures to these problems are adding some access control features to the language and secrecy analysis of interaction models. The first solution for LCC is to label information in it and to add attack prevention rules in the LCC interpreter.

The second solution for probing attacks is secrecy analysis of interaction models using techniques such as using the introduced inference system to detect injection attacks before using the interaction models. This analysis could be implemented as a separate interaction model that receives other interaction models and after extracting the corresponding logical representation, check possibility of information leak using the inference system.

Conclusion and Future work

We propose a programme of research that addresses secrecy of open peer-to-peer multi-agent systems by devising ways of probing attack detection and damage limitation. To analyse information leaks in these agent systems, we have suggested a conceptual representations of interaction models and adapted an inference system, which shows the possibility of private information disclosure by an adversary. Finally we have proposed two solutions to prevent and detect probing attacks in open p2p multi-agent systems. We intend to develop a security type system for LCC language to analyse information leakage in agents' interaction models. The evaluation of the suggested techniques has two stages. In the first stage, we will try to find detection and response methods for probing attacks and evaluation would be empirical by simulation of these techniques. In the case that no convincing detection method exists, we will analytically show it and disconfirm the hypotheses, as the second stage.

Fig. 1 .

 1 Fig. 1. A

  though openness in open systems makes them attractive for different new applications, new problems emerge, among which security is a key. Unfortunately

	there remain
	been done i
	using conv
	communicat
	Tradition
	nature of t
	dynamic pr
	minimum gu
	mechanisms
	part of the s
	of security
	of our know
	for open p2p
	An elect
	framework
	formalism w
	actions. The
	LCC [6] (a
	Coordinatio
	electronic in


Pavel Piskac
email: piskac@mail.muni.cz

Jiri Novotny
email: novotny@ics.muni.cz

Using of Time Characteristics in Data Flow for Traffic Classification

Keywords: protocol detection, time characteristics, flow, IPFIX, pattern

This paper describes a protocol detection using statistic information about a flow extended by packet sizes and time characteristics, which consist of packet inter-arrival times. The most common way of network traffic classification is a deep packet inspection (DPI). Our approach deals with the DPI disadvantage in power consumption using aggregated IPFIX data instead of looking into packet content. According to our previous experiments, we have found that applications have their own behavioral pattern, which can be used for the applications detection. With a respect to current state of development, we mainly present the idea, the results which we have achieved so far and of our future work.

Introduction

Information about protocols on a network is very important in many areas. Planning of networks and their topology need to know how the networks will be used in order to their proper configuration. The security point of view needs to recognize protocols in order to find botnets, viruses, spam or intrusions. For example security teams get and analyze data in real-time, protocol detection represents interesting extension of their services and as such will be welcomed.

This work deals with an idea of protocol detection using extended information about a flow. In the first step, we used only inter-packet gaps which seem to be different for each protocol. Then we added information about packet sizes. The most difficult and unsolved problem yet is to find a method which will reduce variability caused by a network mainly jitter.

Related Work

The first attempts to detect protocols were done using well-known port numbers assigned by IANA [6]. Since the applications are able to change their default port numbers, this method is nowadays weak.

Looking for pattern inside packets is called deep packet inspection. Since each packet has to be read and its content compared with pattern database, this method is not suitable for high-speed networks. Another weak point is encrypted communication, because all the specific byte strings are hidden. In spite of these disadvantages, deep packet inspection so far brings the best detection accuracy.

Protocol detection on high-speed networks is based on aggregation which separates the important information and reduces computational power. Such methods use behavioral analysis or flow statistics. Data classification by host behavior looks for connection patterns of end points and deduces what the host is doing [START_REF] Karagiannis | Blinc multilevel traffic classification in the dark[END_REF]. This method is not suitable for precise protocol detection, but it splits connections into groups (WWW, email, etc.) instead.

Extended flow statistics can carry various information about packets, e.g. inter-arrival packet times, packet direction, packet sizes, etc. [START_REF] Erman | Traffic classification using clustering algorithms[END_REF]. Protocol detection based on these techniques is faster than deep packet inspection and it is able to classify the data even if it is encrypted [START_REF] Hjelmvik | Breaking and Improving Protocol Obfuscation[END_REF]. Another approach detects protocols using only the first four packets of a TCP session [START_REF] Bernaille | Early Application Identification[END_REF].

Protocol Detection

Our first attempts were done in order to show the possibility of taking advantage of the extended flow statistics analysis. This approach was new at the time and we had to verify whether the time characteristics can be used for protocol detection or not. Since it was, as mentioned, a test, we did not try to achieve the best results, we wanted to verify the idea of time characteristics.

Early Phase of Research

FlowMon probes deployed at Masaryk University generate raw NetFlow data which is not capable to measure inter-packet gaps. Hence we decided to use Flow Time Statistic (FTS) tool which was developed as a testing tool for Liberouter project [8]. FTS generates IPFIX or text data where an additional information about time characteristics is included. Since FTS is a testing tool, it is not suitable for backbone networks monitoring due to insufficient speed of data processing. FTS was installed on our server where it listened to a network device and stored data in plain text format. This kind of data collecting was sufficient at this experimental phase of research. Data visualization was done as a plugin for NfSen [START_REF]Netflow Sensor (NfSen)[END_REF].

The classification itself was done by vector matching algorithms. FTS computes statistics about flows and these values create a vector. There were obtained pattern vectors from captured data which were then compared with unknown connection vectors. Protocol detection is based on similarity of unknown and pattern vectors. Using this method, we are able to detect dictionary attacks on SSH protocol. There are better tools with higher accuracy but our goal was to show whether the time characteristics can be used for this purpose. As a first step, we used the following properties: number of packets and bytes, identification number of network and transport layer, minimal, maximal, average and standard deviation inter-arrival time of packets in a flow. These values were chosen according to results from previous experiments.

Vector comparison is done by methods which compute average distance between vectors, root-mean-square (RMS) distance, Euclidean distance and angle between vectors [START_REF] Deza | Encyclopedia of Distances[END_REF] in order to test which one is the most suitable for our purpose and which increases the detection accuracy. Experiments were made and we obtained results of around 90 % successful detection and around 7 % false positives. Average distance between vectors, RMS and Euclidean distance were the most accurate. We captured testing data on our network and it presented a real-life communication.

Current Phase of Research

Previous part showed that protocol detection based on time characteristics is possible. The results can be considered as acceptable because we did not use any specialized vector comparison method and the pattern vectors were also chosen manually which was sufficient at this stage. The current phase of development is devoted to making the method capable of detecting the whole protocols instead of one specific situation. The newest version of FTS was extended by computing statistics of packet sizes.

One of the most difficult parts of the detection is minimizing the influences in time characteristics caused by a network. Packet inter-arrival times always change as they go through the network and they are never the same. Thus we have to find techniques of how to compute and reduce the inadvisable variability. Another difficult part represents the number of situations which can occur during the communication, e.g. established connection, dictionary attacks, file transfer or tunneling other protocols, etc. These two points cause the biggest problems and we have to deal with them.

In order to detect more than one protocol, we make experiments with Quality Threshold (QT) clustering algorithm [START_REF] Heyer | Exploring expression data: Identification and analysis of coexpressed genes[END_REF]. QT clustering provides automatic division into groups where the number of groups is not predefined and it gives always equal results for equal input data. The disadvantage is the speed of computation, which is slower than for example K-Means clustering algorithm [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]. No results from application of QT clustering algorithm are presented here, because they are currently being researched.

Conclusion

In this paper, we have shown that statistics about inter-packet gaps in flows can be used for detecting one specific situation of one protocol. Protocol detection is based on vector comparison where predefined pattern vectors are compared to unknown connections vectors. The disadvantage of this approach is that there has to be one pattern vector for each situation, e.g. successful or unsuccessful authentication.

This first part of our work was done in order to verify whether time characteristics are suitable for protocol detection. The result is that time characteristics have to be extended by some other statistics about flow which will increase accuracy and ability to detect various protocols. This work was the starting phase of the future work.

The biggest challenge is to reduce variability caused by network and find out which flow statistics are characteristic for each protocol. As soon as we will figure out how to do that, we can concern on practical implementation.

Future Work

Future work is an iterative process. At first, we have to reduce the variability in time characteristics and find the proper set of attributes which will the vectors consist of. Automatized division into groups and practical experiments will take place afterwards. We expect that these phases will repeat multiple times.

As soon as we will be satisfied with the detection algorithm, we can customize network probes in order to gain this information from the flows and export it in IPFIX format to our data store where the data will be processed and displayed to users. All the steps are leading towards more accurate and fast protocol detection and thus improved security on computer networks.

Acknowledgements. This material is based upon work supported by the Czech Ministry of Defence under Contract No. SMO02008PR980-OVMASUN200801.