The rule definition

Let ^{_{F1, F2,...Fk}} be sets whose elements are known as features. The integer n, k >1, represents the number of features that characterize the data to be processed. Indeed, all rule discovery algorithms process sequences or stream of instances, where each instance ^{_{n = (f1, f2, fk)}} is a vector belonging to the universe ^{_{U = F1 x}} F₂ x ... x F_k, where f_i ∈ ^_Fi for every 1 ≤ i ≤ k.

Let π₁, π₂, ..., π_k be functions such that π: U → ^_Fi so that given an instance ^{_{n = (f1, f2,}} ...,f_k) ∈ U to π (n) = ^_fi, for each 1 ≤ i ≤ k. These functions in the literature are known as projection functions.

A condition in the universe U is a m: U → ^_Fi {0, 1}, defined from three elements π ⊕ and f_i where π is a projection function, ⊕ is a comparison operator valid for ƒ _i elements (if ƒ _i is a numerical set ⊕ ∈ {<, ≤, >, ≥, = ...}), and ^{_{fi ∈ Fi.}} An instance n satisfies the condition m when the comparison between π (n) and ^_fi performed by ⊕ returns true, in that case m (n) = 1, otherwise m (n) = 0.

A formula in the universe U is also a function that takes values {0, 1} which is defined recursively based on the following principles:

- If m is a condition in U then ρ = m is a formula.

- If g is a formula in U then ρ = (g) is another formula, so that ρ (n) = g (n) for all n ∈ U.

- Given two formulas ^{_{U, g1}} , g₂, we have:

• ^{_{ρ = g1}} and g₂, is a formula, where ρ (n) ^{_{= g1}} (n) ∧ g₂ (n) for all n ∈ U.

• ρ = g₁ ∨ g₂ is a formula where ρ (n) = g₁ (n) ∨ g₂ (n) for all n ∈ U.

A rule in the universe U x C, is represented by , where C = {c1, c2,...c1} is a set of classes with l being an integer l ≥ 2, a formula in U and is an equality condition defined on the corresponding component classes (C). For simplicity, a rule is usually represented as (r,cS, where c¡. The intuitive meaning of a rule is that the fulfillment of the premise in an instance implies that such instance belongs to the class c _i .

For example, let it assume that we have a rule r in the form: if ( ^_f1 ≥ 0.2 andf < 5.0) andf₃ = "http" then"attack"; wherer f ≥ 0.2 and f₁ ≤ 5.0) and ^{_{f3 "http",}} as well as c ₁ = "attack". Considering and c₁, an instance n = (0.3, "http", "UDP") is labeled as "attack", since is fulfilled in n.

Related work

The ARG techniques ⁵ are useful for dealing with various challenges in many application contexts, especially for intrusion detection or fraud detection. These techniques provide a better understanding to analysts, since the outputs are defined as expressions in an understandable language ⁵, unlike other ones considered as black boxes. The ARG methods discussed in this paper can be clustered into four categories: greedy algorithms, conceptual clustering, technique to obtain fuzzy rules and decision trees.

The greedy algorithms (AQ21 ⁷, X2R ⁸, RIPPER ⁹, PART ⁶, AntMiner ¹⁰) ⁵ perform an iterative process over the training collection. The first step consists in selecting a set of instances from the training collection to generate rules. After the rules are created, a filtering process is executed, and the filtered rules are added to a rule set. Subsequently, the selected instances above are removed from the training collection and the iterative process repeats until there are no more training instances. Finally, a filtering rule set is obtained.

In general, the rules, obtained from ARG techniques, generally define unambiguous boundaries for the features of the data to be analyzed. The unambiguous boundaries can often be fraudulent activities laying, but not exceeding, the threshold. The FURIA algorithm ¹¹ presents an interesting proposal for dealing with this situation. This approach performs an adaptation of the RIPPER algorithm, allowing the computation of a first rule set. The obtained rules are transformed into fuzzy rules, by processing the conditions associated to numerical attributes.

There are several algorithms based on creating rules coming from decision trees, for example C4.5 ¹², C5.0 ¹³ and CART ¹⁴. A rule is generated for each leaf, following the path from the root to leaf. The first step of these algorithms is to generate a decision tree. The criteria used to construct the decision tree can vary depending on the proposal ⁵. A pruning process is applied to the generated a decision tree, and a collection of trees is obtained. According to the used method in the previous step, the collection may comprise one or more trees. Afterwards, an optimization procedure is performed in order to select the optimal tree from the collection. Finally, a rule set from the selected tree is obtained.

The method presented in ¹⁵ combines conceptual clustering and natural induction to discover rules. In this method, the data associated to taxes are clustered by a conceptual algorithm. Then, the fraudulent instances of each cluster are used as training collection to learn new rules. The output contains simple rules describing regular and fraudulent instances.

A framework based on frequent subgraph mining. Recently, a framework for intrusion detection based on frequent subgraph mining was reported in literature ¹⁸. During the training stage, this framework processes the training collection through two modules to get frequent subgraphs (see Figure 1).

Figure 1 Training stage diagram used from the framework ¹⁸. 

The preprocessing module is the first to be executed. This step is performed to reduce the dimensionality of the training collection and relabel the values of each selected feature. The relabeling algorithm assigns a unique numerical label for each non numerical feature value. Furthermore, it creates a range of numerical values which are represented by a unique numerical label. These labels are assigned to each numerical feature value. Then, the redundant instances are removed. This module allows obtaining a smaller and quality data collection to improve the effectiveness in the patterns extraction process.

The reduced collection is then processed by the graph mining module. In this module, each instance is represented as a star graph ¹⁸. In a graphical representation (see Figure 2), a star graph has a central vertex representing the instance itself and a vertex for each corresponding feature ^_fi connected to the center. The edge label is the feature index i, and the vertex label is the value of the corresponding feature. Finally, frequent subgraphs (patterns) are obtained which will represent the pattern set P.

Figure 2 Star graph example. 

In this paper, we use the first two modules of the training stage in this framework as a basis to obtain a pattern set P for rule generation.

RF algorithm

The obtained rule set R is processed by the RF algorithm (see Figure 5). This algorithm requires the entire training collection ^_Dt from where the pattern set P was obtained. Furthermore, it takes a precision threshold L₂ defined by an analyst, which can take values within range [0, 1]. We use the entire training collection, because the used framework to generate the patterns set P, reduces the training collection. Therefore, the fact of using the entire training collection provides more information to compute the precision value r precision of the rule r.

Figure 5 Rule Filtering algorithm. 

This algorithm starts with an iterative process (see Figure 5, lines 1-6). For each instance d, where ^{_{d ∈ Dt,}} each rule r is evaluated, where r ∈ R (see Figure 5, lines 2-5). In the Calculate-Precision function (see Figure 5, line 3), if r covers d, then r.precision value

is calculated as .

The variable r.precision represents the number of instances correctly covered by r, and the variable r.total represents the total number of covered instances by r. After calculate r.procision value, the rule r with its new precision value and the new number of instances correctly covered is updated in the rule set R.

Once all the instances in Dt are processed, another iterative process starts in order to select the most representative rules (see Figure 5, lines 8-21). For each rule r, its precision value r.precision is compared against the precision threshold L2. If r.precision exceeds L2, then the function Exist (see Figure 5, line 10) search in the filtered rule set Rf, a rule r1 (where r1 ∈ Rf) that its premise is the same as that of . If there is not a rule r ₁, then r is added to R₁. But, if there exist a rule r₁, then a comparison is performed between precision values. In case of r.procision value is greater than ^{_{r1.procision,}} then r₁ is removed from ^_Rf, and r is added to ^_Rf.

When the iterative process concludes, the next step is to generalize rules in ^_Rf using the function Generalize-Rules (see Figure 5, line 22). This function searches for rules that share at least one same conditions and define the same class. When it finds two rules with these characteristics a merger takes place.

Such merger is performed by keeping the identical conditions and logically adding those different. For example, assume we have two rules: the generated rule r from the presented pattern in Figure 4, and a rule r₁: ^{_{if f3}} ≥ 0.7 ^{_{and f3}} ≤ 1.0) and f₆ = "smtp" them "DoS"; the result of the merger between r and r₁ is: if (f₃ ≥ 0.7 ^{_{and f3}} ≤ 1.0) and ( ^_f4 = ^{_{"tcp" or f6}} = "smtp") then "DoS". This procedure not only allows us to obtain more general rules, but also reduce the final set of rules, providing more effectiveness in the rules evaluation process.

Using the Sort function (see Figure 5, line 23), the obtained rule set is sorted according to the precision of the rules. Thus, the rules with highest precision value will be the first in order. If there are two rules with the same precision value, then the one with greater number of instances correctly covered during the filtering process will go first in order. Finally, a filtered rule set ^_Rf with the most representative rules is returned.

Rule evaluation

Like others rule-based techniques ¹⁹, our method is supplemented with a rule evaluation (RE) strategy. The goal of this strategy is to assign a label to a new instance. The RE algorithm starts with an iterative process (see Figure 6, lines 3-10). Each rule r, where r ∈ R_f, is evaluated over a new instance d, using Evaluate-Rule function (see Figure 6, line 4).

Figure 6 Rule Evaluation algorithm. 

This function returns true if r covers d. When the variable cover take the value true, then the iterative process stops and the labe l l takes the value of the decision part of the rule . If no rule in R covers d, then the algorithm does not assign a specific class, and l takes the value "abstain". Finally, the label l that defines the new instance d is returned.

KDD Cup '99 dataset

In our experiment we use the KDD '99 Dataset ¹⁶, which provides connection records (instances) generated by a simulation of a military network. This dataset contains two labeled collections: training with 4, 898, 431 instances and testing with 311,029 instances. Each instance contains 41 features, which can be continuous or discrete, and is labeled as either normal or an attack, with exactly one specific type of attack.

The simulated attacks are clustered into the following four categories: surveillance and other probing (Probe), denial of service (DoS), unauthorized access to local root privileges (U2R) and unauthorized access from a remote machine (R2L). Therefore, unlike other datasets which have only one specific attack type (e.g. CAIDA "DDoS Attack 2007" dataset ¹⁷), the KDD '99 dataset contains instances of four different attacks types.

Experimental results

Experiments were performed on a machine with a Quad Core processor at 2.5 GHz and 4 GB of RAM. The algorithms are implemented using Python and ANSI-C programming languages. To run the RG algorithm is required a pattern set P and a defined occurrence threshold L ₁. The pattern set P is obtained by the framework based on frequent subgraph mining above. In order to obtain a substantial number of rules to represent all existing classes, we seek a small value for occurrence threshold (in our case L ₁ = 0.3). Once the input parameters are ready, we proceed to generate the rule set R. The total number of rules generated was |R| = 3081.

The obtained rule set R is processed by the RF algorithm. This step is based on preserving the rules that best describe the existing classes; to do this, a value close to 1 must be defined for the precision threshold (in our case L₂ = 0.7). To perform the RF algorithm, the same training collection ^_Dt used by the framework to extract patterns most be provided. Then, the rule set R is significantly reduced to a filtered rule set ^_Rf, where |R_f| = 41.

With the filtered rule set, we proceed to evaluate the rules on the testing collection using RE algorithm. In order to compare our results, we process the testing collection with different classifiers using the reduced training collection (see Figure 1) to build the classification models. Some of the methods discussed in Related Work Section could not be included in the comparison because they are not publicly available.

In our experiments, we evaluate the performance of classifiers such as C5.0 and others from Weka platform ²⁰, which are: decision table/naive bayes hybrid classifier (DTNB), Id3, JRip (RIPPER), nearest-neighbor-like algorithm using non-nested generalized exemplars (NNge), PART, PRISM, Ripple-Down Rule learner (RIDOR) AND SimpleCart (CART). The achieved results

over the same KDD '99 test collection are shown in the Table 1 (our approach is represented as RE). Moreover, the reported results in ¹⁸ using J48graft, classification via Regression and SMO classifiers are included in the Table 1. The accuracy achieved for an attack category is computed as is shown in equation (1).

Table 1 Accuracy achieved using different classifiers. 

The variable ^_categoryi indicates the i-th attack category to be calculated it accuracy, true_positive represent the number of instances from ^_categoryi correctly classified during the test, and total_category_instances is the total number of instances labeled as ^_categoryi in the test collection. The accuracy for "normal" category is computed using equation (2).

The variable true_negatine represent the number of instances from "normal" category correctly classified during the test, and total_normal_instances is the total number of instances labeled as "normal" in the test collection.

From the obtained results, it can be said, that none of the filtered rules ^_Rf are representative of U2R and R2L attack categories. This is because, the precision value of such attacks representative rules is below the precision threshold L ₂. Moreover, our approach outperforms other classifiers in terms of accuracy in DoS attack category.

Since our approach is able to abstain, misclassifications tend to decrease (see Table 2). In Table 3, can be seen that the misclassification rate in our proposal is considerably lower than those reported by other classifiers. Another important aspect to note is the overall accuracy, given by equation (3).

(3)

Table 2 Summary of the achieved results using our approach. 

In such equation, the variable total_tp represents the number of attack instances correctly classified during the test, and total_test_instances indicates the number of instances in the test collection. The achieved results shown in the Table 3, prove that our proposal with 86.76 % of overall accuracy and 1.37 % of misclassification rate in general terms outperforms other analyzed classifiers. Inclusive, if abstentions are considered as misclassification, even so, the misclassification rate with 13.24% would be lower than those reported by the analyzed classifiers.

Table 3 Overall accuracy and misclassification rate achieved using different classifiers. 

The results achieved by our approach show that it can be applied in scenarios that require minimal misclassifications. Since it is a rule-based approach ¹⁹, it can be incorporated as a module of a security system to identify online criminal activities in data streams. Also, the instances labeled as "abstain", can be used to generate patterns. Then, from these patterns new rules can be generated that define new classes, or existing classes that have changed their concept.