How much training data is enough?. A case study for HTTP anomaly-based intrusion detection

SPECIAL SECTION ON EMERGING APPROACHES TO CYBER SECURITY Received January 31, 2020, accepted February 23, 2020, date of publication March 2, 2020, date of current version March 13, 2020. Digital Object Identifier 10.1109/ACCESS.2020.2977591 How Much Training Data Is Enough? A Case Study for HTTP Anomaly-Based Intrusion Detection RAFAEL ESTEPA 1, JESÚS E. DÍAZ-VERDEJO 2, ANTONIO ESTEPA 1, AND GERMAN MADINABEITIA 1 1Department of Telematics Engineering, University of Seville, 41092 Seville, Spain 2Department of Signal Theory, Telematics and Communications, CITIC, University of Granada, 18071 Granada, Spain Corresponding author: Antonio Estepa ([email protected]) This work was supported in part by the Corporación Tecnológica de Andalucía and the University of Seville through the Projects under Grant CTA 1669/22/2017, Grant PI-1786/22/2018, and Grant PI-1736/22/2017. ABSTRACT Most anomaly-based intrusion detectors rely on models that learn from training datasets whose quality is crucial in their performance. Albeit the properties of suitable datasets have been formulated, the influence of the dataset size on the performance of the anomaly-based detector has received scarce attention so far. In this work, we investigate the optimal size of a training dataset. This size should be large enough so that training data is representative of normal behavior, but after that point, collecting more data may result in unnecessary waste of time and computational resources, not to mention an increased risk of overtraining. In this spirit, we provide a method to find out when the amount of data collected at the production environment is representative of normal behavior in the context of a detector of HTTP URI attacks based on 1-grammar. Our approach is founded on a set of indicators related to the statistical properties of the data. These indicators are periodically calculated during data collection, producing time series that stabilize when more training data is not expected to translate to better system performance, which indicates that data collection can be stopped. We present a case study with real-life datasets collected at the University of Seville (Spain) and a public dataset from the University of Saskatchewan. The application of our method to these datasets showed that more than 42% of one trace, and almost 20% of another were unnecessarily collected, thereby showing that our proposed method can be an efficient approach for collecting training data at the production environment. INDEX TERMS Anomaly-based intrusion detection, dataset assessment, training. I. INTRODUCTION Anomaly-based Intrusion Detection Systems (AIDS) enable the identification of suspicious behavior that significantly differs from normal activities in a computer system or network [1]. To this end, AIDS model the normal activity of a system adopting diverse approaches (e.g., statistical, knowledge-based, or machine learning techniques) [2]. A prerequisite of AIDS is to train their model with a dataset (training dataset) that represents the normal operation of the protected system. Once trained, normal activity profiles are formed and the system performance can be evaluated by rating the events included in a testing dataset. Public benchmark datasets are commonly used to compare different research results [3]. However, in real-life The associate editor coordinating the review of this manuscript and approving it for publication was Ana Lucila Sandoval Orozco. deployments, AIDS need to be trained and validated with datasets that faithfully represent the traffic seen in production. Indeed, inadequate or outdated datasets may lead to false alarms because new behaviors, or changes in the protected system, can be interpreted as anomalies, which is a general issue with AIDS [4]. Therefore, besides their particular models and techniques, the success of anomaly-based detectors strongly depends on the availability of suitable training datasets [5]. The creation of training datasets with real-life properties is not trivial. AIDS in production require to be (re)trained with datasets that at least: (a) are free of attacks (or else these are properly labeled), and (b) represent normal traffic (e.g., up-to- date traffic similar to production). Other desirable properties of a dataset described by Viegas et al. [6] include: easily updatable, variant, correct, reproducible (so researchers can compare), and shareable (i.e., with no confidential data). 44410 This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see http://creativecommons.org/licenses/by/4.0/ VOLUME 8, 2020 R. Estepa et al.: How Much Training Data Is Enough? Case Study for HTTP Anomaly-Based Intrusion Detection Additionally, Sharafaldin et al. [7] also pointed to the inclusion of variant protocols and appropriate documentation as two desirable properties of datasets. From the previous requirements, one can infer that extracting suitable datasets from real-life traces is not straightforward and may require a process of sanitization [8], [9] to, at least, identify attacks embedded in the trace (an example of sanitization of HTTP traces can be found in [10]). However, the workload associated with this process grows linearly with the size of the trace. And, although unsupervised sanitization approaches have been suggested (e.g., analysis of entropy [11], or filtering known-attacks with signature-based IDS [12]), manual supervision may be unavoidable in order to discover attacks (e.g., 0-day) unnoticed by fully automated methods [13], [14]. The size of a dataset is a factor that has not received much attention in the scientific literature. One possible reason is that it is commonly assumed to be a given in the experimental outline. A generally accepted idea is that a large volume of data is more representative of normal activity, and as such, it translates to better AIDS performance, which also seems intuitive. Indeed, a tiny dataset may lead to insufficient training and, consequently, poor performance. However, a large dataset may exhibit some drawbacks. First, the data collection may take weeks or even months, which besides increasing the time-to-train the AIDS (and thus, delay the start of operation), can also be associated with higher resource consumption in terms of storage or computational power during data preprocessing or training [15]. This fact might limit applicability in devices with limited processing ability or storage capacity such as those commonly found in industrial control systems, or in the field of IoT (especially with computationally-intensive algorithms [16]). Secondly, the workload associated with the sanitization of a large trace can be prohibitive if done manually, or else, if the sanitization process is fully automated or skipped, the risk of having unnoticed attacks in the resulting dataset increases with the dataset size. Last but not least, large datasets occasionally may lead to the over-training problem in which models are over-adapted to the training set and, as such, AIDS performance deteriorates [17]. In this paper, we investigate the impact of the size of a training dataset on the performance of an anomaly-based intrusion detector. The underlying hypothesis is that there is an optimum size from a cost-benefit perspective, which depends on the detection techniques and model used by the AIDS, as well as the characteristics of the captured traffic [18]. With this in mind, we propose a novel method to find the optimal size of a dataset suited for training AIDS based on 1-grammar models. We use indicators that characterize the learning value of data collected over time. When these indicators stabilize, the amount of data collected is considered optimum for training (i.e., more data would not produce better AIDS performance). A case study applies this methodology to three real-life service traces from our university, and one public dataset from the University of Saskatchewan [19]. The novelty and originality of this work are: •We study the effect of the dataset size on the performance of detectors of HTTP URI attacks based on 1-grammar models. •We provide a method to estimate the representativeness of a training dataset with respect to normal behavior, which is applied in a real-life case study. •We suggest indicators applicable to 1-grammar models that enable the comparison of two evolutionary versions of the same dataset in terms of the training data sufficiency. The main contribution of this paper is a method to determine when the data collected is representative of normal behavior. This can be useful for reducing the size of existing datasets (e.g., to reduce the risk of overtraining), to reduce the time spent collecting data at the production environment (e.g., to reduce the time needed to put the AIDS in production), or to estimate when (re)training is necessary. Although this work is restricted to AIDS based on 1-grammar, the principles and ideas revealed could be partially reused by the research community to investigate extensions to different models. The remainder of this paper is as follows. Section II presents related works. Section III introduces the reference AIDS model, definitions and terminology used. Section IV describes the datasets and the resulting dictionaries used in our study. The temporal evolution of these dictionaries is studied in Section V. Our method for on-line data collection is described in Section VI, and Section VII describes the limitations of this work. Finally, Section VIII concludes the paper and outlines future work. II. RELATED WORKS As stated earlier, the quality of the datasets used by anomaly-based intrusion detectors has a decisive influence on their performance. In the scientific literature, the performance of different models and techniques is commonly compared using public benchmark datasets whose quality have been subject of criticism by some authors such as Sommer and Paxson [4] or Sharafaldin et al. [7]. It is also possible to find some works [18], [20] aimed at defining how to carry out a correct comparison of different AIDS according to the characteristics of the datasets. However, as mentioned earlier, public benchmark datasets, albeit necessary for comparing research results, are not suitable for training models in practice due to the lack of real-life properties similar to those seen in production. The problem of capturing representative data suitable for training or validating models has been addressed in the past in the research field of machine learning [21], as well as in the anomaly-based intrusion detection research field [22]. The generation of realistic datasets from captured traffic may be a resource-intensive task that some authors have tried to alleviate. In [23], the authors propose techniques for instrumenting network warfare competitions to collect scientifically valid labeled datasets, which otherwise would be resource-intensive. Similarly, Velarde-Alvarado et al. [11] VOLUME 8, 2020 44411 R. Estepa et al.: How Much Training Data Is Enough? Case Study for HTTP Anomaly-Based Intrusion Detection remark the scarcity of suitable datasets for AIDS development and propose a semi-automated process for the sanitization of the traffic captured based on the entropy of embedded traffic flows. This enables the collection of large volumes of data without excessive resource consumption in terms of manual supervision or computational resources. However, as stated earlier, fully automated sanitization methods can never guarantee that the resulting datasets are free of attacks. Few authors have studied the influence of the training dataset on the performance of the AIDS. In [24], the authors studied the effect of partitioning a dataset to obtain separate pieces for training and evaluation. They found that different data blocks produced different results in AIDS performance, which suggests that the entire dataset exhibited heterogeneous characteristics over time. Maxion and Tan [25], [26] have studied the structure and regularity of captured data and its influence in the performance of an HTTP-attack AIDS based on n-grams. The authors generated artificial datasets of the same size but with increased complexity (according to the relative conditional entropy) obtaining a rate of false positives that increased exponentially with the inverse of the complexity of the data. The authors concluded that training should be adapted to the characteristics of the dataset, including its variability over time, which leads to the consideration of a temporal window in the training dataset. A similar conclusion was drawn by Lee et al. in [27], where the authors analyzed the problems associated with the use of multiple configurations and datasets for evaluating AIDS performance. The size of the training dataset has received scarce attention in the research literature. Kishimoto et al. [17] studied the appropriate size of a learning dataset for anomaly-based intrusion detection based on machine learning. In their work, the authors collected Internet traces from a honeypot and analyzed the effect of trace size on the performance of their classifiers. They found that when the learning dataset was too small (e.g., one day), the rate of false positives was high due to insufficient training. On the other hand, when the size of learning dataset was extremely large (e.g., ten days), overfitting caused the deterioration of performance. Therefore, they experimentally concluded that the appropriate size was five days of capture when using Kyoto2006+ public dataset for validation. This supports our initial hypothesis that there is an optimum size for the training dataset, which depends on the techniques and models used, and the properties of the captured traffic. A similar claim is supported in [28], where the influence of the size of the training data in two classifiers was studied. One of the classifiers compared (Naive Bayes Classifier) was also successfully tested in another work related to anomaly-based intrusion detection [29]. Finally, some works have pointed to the need for re-training the models [4], [5] as a sound solution to the problem of data shift [30]. However, few works actually address the issue of model adaptation to dynamic changes. In [31] the authors propose a batch-based approach that involves manual work to determine the level of performance degradation, which indicates when re-training is necessary. In a more generic context, the authors in [32] have proposed the use of EWMA and Kolmogorov-Smirnoff tests to determine the occurrence of data shift in non-stationary environments. Our contribution can also be applied to find if the dataset used for training is still representative of normal behavior, and therefore, to find whether re-training is necessary or not. III. REFERENCE AIDS AND TERMINOLOGY A dataset has to be suited for the specific model and parameters used by the anomaly detector. In this regard, the findings of this work are limited to detectors of anomalous HTTP requests based on probabilistic models (e.g., n-gram [33], or Markov-based models [34]). In particular, the AIDS used in this work is based on 1-grammar since the authors are largely experienced in this technique (see [35]), which is simple enough as to let the reader stay focused on the contribution. In our reference AIDS, the goal of the training phase is to form a dictionary that will be used afterward to classify Universal Resource Identifiers (URIs) received in HTTP requests as normal or anomalous. As such, the datasets used in this work are a collection of URIs extracted from HTTP trace files. A. DICTIONARY FORMATION Let U= {ui|i∈N}be the set of URIs contained in a training dataset. RFC 3986 [36] defines the structure of a URI, which is basically a text string composed of an optional protocol, an optional host, a sequence of one or more path segments, namely absolute path and, optionally, a query composed of a sequence of attributes, each of them with an optional value. This is generally expressed as: "http://"host[":"port][abs_path["?"query]] A URI can be parsed using a set of standard delimiters (:/?#[]@!$&’()*+,;=),1obtaining a set of sub-strings or words that are central to our AIDS. For the purpose of anomaly-detection, only those words extracted from the path, attribute or value fields are considered of interest in this work (i.e., we assume that host and port are invariant throughout the trace). Let us define the vocabulary learned from a training dataset (U), as the set of words observed after segmenting all the URIs contained in U: W(U)= {wi|1≤i≤M}(1) where Mis the cardinality of the vocabulary. Let O(U)= {oi|1≤i≤M}be the number of occurrences (i.e., absolute frequency) of the words observed in the training dataset U. 1We consider both gen-delims and sub-delims, as defined in the standard, to be able to parse the queries. 44412 VOLUME 8, 2020 R. Estepa et al.: How Much Training Data Is Enough? Case Study for HTTP Anomaly-Based Intrusion Detection Let us define a dictionary, or equivalently, a 1-grammar2 as the set of different words (and their absolute frequency) observed after segmenting the URIs contained in a dataset U as: D(U)= {(wi,oi)|wi∈W(U),oi∈O(U))}(2) Given a dictionary, the relative frequency (or empirical probability) of word wican be readily obtained as: pi=oi O(3) where Ois the overall number of observations: O= M X i=1 oi(4) Finally, let P(U) be the set of relative frequencies of the words observed: P(U)= {pi|1≤i≤M}(5) As an example, consider the following URI: http://traj.us.es/set/index.php?set=200&theme=blue It is possible to segment this URI in 8 strings (http, traj.us.es, set, index.php, set, 200, theme, blue) using standard delimiters. Then, using only strings from the attribute, path and value fields, the extracted dictionary would be: D= {(set,2),(index.php,1),(theme,1), (200,1),(blue,1)}(6) The overall number of observations would be O=6, and the relative frequency of the words would be 1/6 for all but the first one which would be p1=2/6. B. AIDS PERFORMANCE Figure 1illustrates a generic scheme for the assessment of the performance of AIDS. This scheme relies on three disjoint datasets: •Training dataset: it contains URIs that represent normal behavior, and as such, it should be free of attacks. This dataset is used to train the model and is the subject of our study (i.e., U). •Evaluation dataset (clean): this dataset is also composed of (different) instances from the normal behavior and it should be free of attacks. In this work, the evaluationclean dataset is similar to the training dataset (indeed, it comes from halving the collected traces). •Evaluation dataset (attacks): this dataset contains malicious URIs used to evaluate the performance of the detector. In our work, it is composed of 2 200 malicious URIs from a public repository [37] (category 2An analysis on a per-field basis is also possible by arranging words into field-based dictionaries as in the original SSM technique proposed in [35]. Nevertheless, for the sake of simplicity and clarity, we consider a single state, merging all words in a single dictionary. Experiments carried out using three states did not show differences in the behavior of the proposed method. FIGURE 1. AIDS performance evaluation. ML-driven-Web-Application-Firewall) that can be downloaded from [38]. After processing the training dataset (training mode in Figure 1), the dictionary is formed and AIDS performance can be evaluated. The AIDS (in evaluation mode) uses the dictionary when assigning an anomaly score to each URI found in the evaluation datasets. Given a URI uicomposed of a set of words Wui= {wi|i=1,· · · ,L}, its anomaly score is calculated as follows: AS(ui)= − 1 L L X i=1 log(xi) (7) where xi=(pi,if wi∈W(U) poov,if wi/∈W(U)(8) being poov a default value assigned to the words not included in the dictionary (i.e., out of vocabulary words). In this work, after some tuning, we selected poov =p3 min, where pmin is the lowest probability in P(U). This is an effective solution to deal with the problem of insufficient training [35]. Finally, if the anomaly score exceeds a threshold θ (i.e., AS(ui)> θ), the URI uiis classified as anomalous. Otherwise, it is considered normal. In the evaluation process illustrated in Figure 1, the AIDS classifies registers from the clean datasets as either normal (i.e., True Negative –TN–) or anomalous (i.e., False Positive –FP–), whereas registers from the attack dataset can be classified as either normal (i.e., False Negative –FN–) or anomalous (i.e., True Positive –TP–). These four basic indicators allow one to evaluate AIDS performance through various metrics such as Detection Rate (DR) and False Positive Rate (FPR): DR =TP TP +FN ,FPR =FP FP +TP (9) Other metrics are possible (e.g., accuracy or sensibility) [3], but good performance is always a synonym of very high DR and very low FPR. However since we are going to compare performance in different scenarios, and the classes VOLUME 8, 2020 44413 R. Estepa et al.: How Much Training Data Is Enough? Case Study for HTTP Anomaly-Based Intrusion Detection normal and anomalous are clearly unbalanced (the attack dataset is several times smaller than the others), we will use the metric geometric mean [39] as performance indicator. This metric combines recall and specificity, and hence, it is sensitive to both detection capacity and false positives. Thus, for the remainder of this paper, the AIDS performance metric will be given by: η=pDR ·(1 −FPR) (10) IV. CHARACTERIZING THE TRAINING DATASETS AND DICTIONARIES OF THIS STUDY Without loss of generality, for the remainder of this work, we can assume that dictionaries are arrays arranged so words are sorted by their frequency (i.e., words more frequent are first). That is: D(U)= {(wi,oi)|1≤i≤M,or≥ok∀r≤k}(11) A. STATISTICAL PROPERTIES OF A DICTIONARY A dictionary D(U) is statistically characterized by the empirical probability of its words P(U) (i.e., probability mass function). Since we are assuming that words are sorted by their frequency, a plot of P(U) should show a monotonically decreasing function such as the one illustrated in Figure 2, where the horizontal axis represents the index of the elements in P(U) (i.e., word index). Observe that the maximum and minimum empirical probabilities are pmax =p1and pmin =pMrespectively. FIGURE 2. Generic probability mass function of a typical dictionary. According to our experience, the probability mass function of URI-based dictionaries is likely to exhibit a tail formed by words rarely observed. If so, the plot of this function can be split into two contiguous regions: core, with the more frequent words, and tail with the less frequent words, by simply defining a lower threshold for the empirical probability of words that belong to the core (see pth in Figure 2). Then, a tail sub-dictionary T(U)⊆D(U) can be defined as: T(U)= {(wi,oi)|(wi,oi)∈D(U),pi<pth}(12) Similarly, a core sub-dictionary C(U)⊆D(U) can be defined as: C(U)= {(wi,oi)|(wi,oi)∈D(U),pi≥pth}(13) In Figure 2, the number of words that belong to the core is represented by nc= |C(U)|. Regarding the value of the threshold pth, it should be lower than the average word frequency, and also should account for the dynamic range of the probability mass function. After some experimentation, we found that the following value provided good results: pth =1−(pmax −pmin) M=1+pM−p1 M(14) Besides P(U), a dictionary can be further characterized by the following statistics: •Average relative frequency of words. R=M O(15) •Entropy of the dictionary. S= − M X i=1 pi·log2pi(16) •Entropy of the core sub-dictionary. Score = − nc X i=1 pi·log2pi,pi≥pth (17) •Cumulative empirical probability of core-words: Pcore = nc X i=1 pi,pi≥pth (18) Note that Ptail =1−Pcore. Next, we introduce the experimental datasets used in this work and characterize the dictionaries formed after training our reference AIDS with them. B. TRAINING DATASETS AND BASELINE DICTIONARIES FORMED In order to perform a comprehensive study, we have used four HTTP traces collected at different experimental testbeds, which has produced datasets with heterogeneous characteristics. The experimental datasets used in this work are: •Biblio: this dataset is formed by the daily traces collected by the web server of the Library of the University of Seville (http://bib.us.es). It includes 1 002 000 HTTP requests received from 1/1/2017 to 17/07/2017. •Teulada: this dataset is formed by the traces of a web application server devoted to interwork with a research-oriented IoT sensor network deployed in the city of Seville. •UofS: this is a public dataset from the University of Saskatchewan [19] that includes 2.3 million HTTP requests (method +URI). 44414 VOLUME 8, 2020 R. Estepa et al.: How Much Training Data Is Enough? Case Study for HTTP Anomaly-Based Intrusion Detection TABLE 1. Most relevant statistics for the considered datasets (training partitions). FIGURE 3. Probability mass function for the dictionaries formed from: a) Teulada, b) Inves, c) Biblio, d) UofS. •Inves: this dataset is created from the traces of a document-search web service of the University of Seville geared toward research (http://fama.us. es). It includes about 4.6 million requests received during May 2018. The previous traces have been sanitized to remove existing attacks. Then, the datasets have been halved to create the training and validation (clean) partitions. For the remainder of this paper (but when addressing performance evaluation), we will only refer to the training partition. Table 1provides information about the training datasets created on each experimental environment, and some statistics of the dictionary formed with each dataset. These properties show diversity in size, number of words observed, etc. For example, Teulada exhibits a reduced vocabulary (e.g., 1 101 different words) while Inves exhibits a large one (153 653 different words). This difference is attributable to the service provided in each case (e.g., Teulada is more similar to a static website whereas Inves provides a search service). This information is complemented with a plot of the mass probability function of the dictionaries formed shown in Figure 3. Note that axes are represented in log scale for clarity, which, albeit improves the visualization of the core, distorts the actual shape. Results from Table 1and Figure 3show that the core sub-dictionary is always composed of a reduced number of words (less than 1% of each vocabulary) that accounts for the bulk of the empirical probability in each vocabulary. As shown in Table 1, core words account for a cumulative probability ranging from 83% (Teulada) to 95% (Biblio). This suggests that the choice of pth, according to Eq. (39), is reasonable, as tails are commonly expected to represent less than 20% of the distribution. Note also that the entropy of the core is a significant fraction of the entropy of the dataset. On the other hand, the transition between the core and the tail is more abrupt in Teulada and Inves than in Biblio and UofS, which might show that the latter two datasets are more sensitive to the choice of the threshold. V. TEMPORAL EVOLUTION OF DICTIONARIES In this section, we study the evolution of the probability mass function of a dictionary with the number of URIs processed. VOLUME 8, 2020 44415 R. Estepa et al.: How Much Training Data Is Enough? Case Study for HTTP Anomaly-Based Intrusion Detection FIGURE 4. Temporal Evolution of the core and the tail in our datasets. In the datasets, URIs are assumed to be in chronological order. As such, we can regard this study as a temporal evolution. We expect three different behaviors in this temporal evolution that let us classify the dictionaries accordingly as: 1) Stable dictionary: its probability mass function remains mostly steady after a certain number of URIs. This would be the case of websites with a closed set of potential words in their URIs (e.g., static website) when the behavior of users (i.e., requests) is regular over time. 2) Core-stable dictionary: the probability mass function of the core-subdictionary remains mostly steady after processing a certain number of URIs, but it does not stabilize in the tail-subdictionary. It would be the case of websites that include variable parts in their URIs such as timestamps, auto-incremental values, hashes, etc. Although some words are frequently observed (core words), some others (tail words) are scarcely seen (maybe one or two times), having little influence in the anomaly score of a URI. 3) Non-stable dictionary: new URIs might produce significant changes in the probability mass function of the dictionary. As such, neither core nor tail sub-dictionaries stabilize with the number of URIs processed. This is probably the case of dynamic websites with highly changing resources. Figure 4shows the temporal evolution of the dictionaries formed with our datasets. For each dataset, we have plotted the mass probability function obtained after processing different percentages of the dataset size. For a clearer view, the tail and core have been represented using two separate scales. The temporal evolution of the tail and the core shown in Figure 4 confirms the types of dictionaries suggested earlier. Teulada remains stable after processing a minimum portion of the dataset (i.e., stable dictionary), Biblio exhibits significant changes in his tail but, after a certain number of URIs, its core remains steady (i.e., core-stable dictionary), and UofS and Inves show unsteadiness in both core and tail sub-dictionaries (i.e., non-stable dictionaries). Regarding the lower threshold probability pth (transition zone in Figure 4), its variations with the number of URIs processed are minimal. Indeed, as demonstrated in Appendix, there is a point after which its variations are negligible. For the remainder of this section, we investigate how some datasets may hold registers that barely impact the statistical properties of a dictionary. We work under the assumption that in some cases, there should be a minimum-sized dataset that exhibits the same statistical properties as that of a bigger one and, consequently, processing more registers does not pay off from the perspective of AIDS performance. This idea will be used in the next section to stop data collection. A. STABILITY CONDITIONS OF A DICTIONARY In this section, we study the conditions that can help us decide when the statistical properties of a dictionary of a certain type become invariant to more data from the same dataset. 44416 VOLUME 8, 2020 R. Estepa et al.: How Much Training Data Is Enough? Case Study for HTTP Anomaly-Based Intrusion Detection 1) STABLE DICTIONARY (TYPE 1) Let U= {ui|1≤i≤U}be the set of URIs contained in a dataset in chronological order. Then, we say that a dictionary is stable if there is a value Usthat meets: W(U0)=W(Us),∀U0>Us(19) P(U0)=P(Us),∀U0>Us(20) where U0is the subset composed of the first U0URIs from U, and Usis the subset composed of the first UsURIs from U0. The first condition –Eq. (19)– can be put in a more tractable form by simply using the cardinality of the vocabularies (i.e., |W(U0)| = Us∀U0>Us) since Us⊂U0and URIs are processed in chronological order. The second condition –Eq. (20)–, however, is impossible to meet in a strict sense in practice, as every new URI processed impacts the frequency distribution. Thus, this condition has to be relaxed from equality of distributions to similarity of distributions. We use the Chi-squared test (χ2test) to compare the similarity of two distributions. This test indicates whether there is a significant difference between the expected frequencies and the observed frequencies in one or more categories. In our case, the set of categories is the set of words W(U0) whose cardinality is M0. Let’s assume that D0=D(U0) has an unknown probability distribution P0=P(U0) and an overall number of observations O0, and that D=D(U) has a known distribution P=P(U). Then, we would like to validate the following hypothesis: H0:P=P0,(21) H1:P6= P0(22) The χ2statistic can be calculated according to the following equation: χ2(D,D0)= M0 X k=1 (o0 k−pk·O0)2 pk·O0(23) If χ2(D,D0) is 0, the distribution of the observations in Dand D0is identical. If not, we can consider that both distributions are similar (i.e., accept the null hypothesis) with a certain statistical significance αif its pvalue (indicator to support or reject the null hypothesis) is greater than α (i.e., pvalue(D,D0)=Prob(χ2 (M0−1) > χ2(D,D0)) > α)).3 Finally, notice that in order to have a reliable application of the Chi-squared test, the following has to be met: (a) the overall number of observations has to be large, (b) the frequency of each word should be greater than a lower threshold (typically 2). In our case, the first condition is met in all datasets, and the second condition has been applied by excluding words whose frequency is less than that lower threshold from both Dand D0. Therefore, the requirement for a dictionary to be considered stable with a statistical significance of α, is that there is 3Typical accepted values for αare: 0.05,0.01 and 0.001. a value Usthat meets the following conditions: |W(U0)| = |W(Us)|,∀U0>Us(24) pvalue(D,D0)> α, ∀U0>Us(25) 2) CORE-STABLE DICTIONARY (TYPE 2) In this case, both the mass probability function and the number of words in the core-subdictionary stabilize after some point, but the number of new words (in the tail) is continuously growing. Therefore, this type of dictionaries can be characterized by: |W(U0)| ≥ |W(Us)|,∀U0>Us(26) C(U0)=C(Us),∀U0>Us(27) In this case, stability conditions can be set based on the stability of the core-subdictionary C(U): |C(U0)| = |C(Us)|,∀U0>Us(28) pvalue(C(U0),C(Us)) > α, ∀U0>Us(29) As shown in Appendix, in type 2 dictionaries, pth tends to stabilize after a certain point, and so does the number of core-words and their cumulative probability. Nevertheless, pvalue(C(U0),C(Us)) is particularly sensitive to fluctuations in the core-tail delimitation, which depends on pth. Therefore, it would be desirable to replace Eq. (29) with an alternative condition that let us compare the similarity of the distributions and has better tractability. We believe that entropy, although is a softer condition, can be used to this end. Lemma 1: Given a core-stable dataset U, of size U, there is a minimal subset, of size Us<U, whose entropy would be equal to the entropy of the full dataset if U was large enough. Proof: see Appendix. Then, for the remainder of this work, we consider that a dictionary is core-stable if there is a value Usthat meets Eq. (28) and: S(U0)=S(Us)±σ, ∀U0>Us(30) where σis a constant that accounts for minimal differences which tends to 0 with the dataset size. Obviously, those dictionaries that can not be classified as type-1 or type-2, will be considered non-stable (type 3)4for which no stability conditions can be set. B. APPLICATION OF THE STABILITY CONDITIONS TO FIND DISPENSABLE DATA IN OUR DATASETS In this section, we seek the previous stability conditions in our experimental datasets in order to find the minimum value of U0, namely Us, so that the statistical properties of the resulting dictionary were similar to that of the dictionary formed with the full dataset. In this process, we first divide the original datasets in data chunks of 1UURIs. Then, we look 4A given training dataset can be classified as type 3 even if its associated source could correspond to type 1 or type 2 due to insufficiency of the acquired training dataset. In any case, the conclusion is that additional observations are needed. VOLUME 8, 2020 44417 R. Estepa et al.: How Much Training Data Is Enough? Case Study for HTTP Anomaly-Based Intrusion Detection FIGURE 5. Evolution of the number of words (M) for different dataset sizes. FIGURE 6. Evolution of the Entropy (S) and word in the Core (nc) for different dataset sizes. for the minimum number of pieces that meets the stability conditions. The first condition for type 1 dictionaries is related to the number of words contained in the dataset–Eq. (24)–. Figure 5 shows the evolution of this indicator (M) with the number of chunks processed for each dataset under study. The size of the chunk on each case is a divisor of the dataset size. The results in Figure 5show that only Teulada meets this condition. The other requirement for a dataset to be considered type 1 was similarity of distribution –Eq. (25)–. Therefore, we want to find the minimum value of U0, namely Usso both dictionaries D(U) and D(Us) are similar with a statistical significance of α. Figure 6shows the evolution of the entropy and the number of core-words (nc) in the datasets. It can be noticed that, besides Teulada, only Biblio exhibits a stable behavior. Thus, according to Lemma 1 and Eqs. (25), (28) and (29), Teulada is definitively a dataset that produces a stable (type-1) dictionary, whereas Biblio can be classified as core-stable (type-2). Algorithm 1 UsSearch Algorithm for Stable (Type=1) and Core-Stable (Type=2) Dictionaries Input:U,U,α,1U,σ,Type Output:Us 1: function: D(n) 2: d={ui∈U|i≤n} 3: return d 4: end function 5: D←D(U) 6: U0=U−1U 7: D0←D(U0) 8: if Type =1then 9: while ((α≤pvalue(D,D0)) & (|W(U)| = |W(U0)|)&(U0> 1U)) do 10: U0←U0−1U 11: D0←D(U0) 12: end while 13: if α > pvalue(D,D0)then 14: Us←U0+1U 15: else 16: Us←U0 17: end if 18: else 19: while ((σ≤ |S(D)−S(D0)|) & (|W(C(U))| = |W(C(U0))|)&(U0> 1U)) do 20: U0←U0−1U 21: D0←D(U0) 22: end while 23: if σ > |S(D)−S(D0))|then 24: Us←U0+1U 25: else 26: Us←U0 27: end if 28: end if 29: return Us As such, we want to find the minimal subset Usso the difference of the entropy in both dictionaries D(U) and D(Us) is lower than σ. Algorithm 1shows a pseudocode that finds the value of Us in datasets that produce stable or core-stable dictionaries. It takes as input the initial dataset considered, U, its size, U, and type, the αvalue considered for similarity’s statistical significance, the σvalue considered in Eq. 30, and the dataset size reduction step 1. It first builds the dictionary D=D(U) using the full dataset. Then, it builds a second dictionary D0=D(U0) that excludes the last 1UURIs. The similarity condition (pvalue or Entropy difference) is then examined and, if met, the size is reduced by another 1UURIs, and D0is rebuilt. Then, the similarity condition is examined again. This process continues until both are not similar, or the dataset size cannot be further reduced. The algorithm returns Us. Note that Us, will be lower than Uonly when it is applied to the correct dataset type. Thus, if applied to Inves and UofS, 44418 VOLUME 8, 2020 R. Estepa et al.: How Much Training Data Is Enough? Case Study for HTTP Anomaly-Based Intrusion Detection ANTONIO ESTEPA received the M.S. and Ph.D. degrees in telecommunication engineering from the University of Seville, in 1998 and 2004, respectively. From 1998 to 2000, he was a software and network engineer with a software development company. In 2004, he was also a Visitor with the Department of Electrical Engineering and Computer Science, University of Minnesota, USA. He is currently an Associate Professor with the Department of Telematics Engineering, University of Seville. He has authored or coauthored in several conferences or journal articles. His research interests include the areas of telecommunication networks, with a particular emphasis on networking protocols, wireless networks, and cybersecurity. GERMAN MADINABEITIA received the M.S. and Ph.D. degrees in telecommunication engineering from the Universidad Politecnica de Madrid, in 1986 and 2004, respectively. In the past, he was working for ten years as a product engineer in the industry. He is currently an Assistant Professor with the Department of Telematics Engineering, University of Seville. His research interests include the areas of networking, the Internet of Things, cybersecurity, and traffic engineering. VOLUME 8, 2020 44425