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

SPECIAL SECTION ON EMERGING APPROACHES TO CYBER SECURITY Recei ed Janua y 31, 2020, accep ed Feb ua y 23, 2020, da e o publica ion Ma ch 2, 2020, da e o cu en e sion Ma ch 13, 2020. Digi al Objec Iden i ie 10.1109/ACCESS.2020.2977591 How Much T aining Da a Is Enough? A Case S udy o HTTP Anomaly-Based In usion De ec ion RAFAEL ESTEPA 1, JESÚS E. DÍAZ-VERDEJO 2, ANTONIO ESTEPA 1, AND GERMAN MADINABEITIA 1 1Depa men o Telema ics Enginee ing, Uni e si y o Se ille, 41092 Se ille, Spain 2Depa men o Signal Theo y, Telema ics and Communica ions, CITIC, Uni e si y o G anada, 18071 G anada, Spain Co esponding au ho : An onio Es epa ([email p o ec ed]) This wo k was suppo ed in pa by he Co po ación Tecnológica de Andalucía and he Uni e si y o Se ille h ough he P ojec s unde G an CTA 1669/22/2017, G an PI-1786/22/2018, and G an PI-1736/22/2017. ABSTRACT Mos anomaly-based in usion de ec o s ely on models ha lea n om aining da ase s whose quali y is c ucial in hei pe o mance. Albei he p ope ies o sui able da ase s ha e been o mula ed, he in luence o he da ase size on he pe o mance o he anomaly-based de ec o has ecei ed sca ce a en ion so a . In his wo k, we in es iga e he op imal size o a aining da ase . This size should be la ge enough so ha aining da a is ep esen a i e o no mal beha io , bu a e ha poin , collec ing mo e da a may esul in unnecessa y was e o ime and compu a ional esou ces, no o men ion an inc eased isk o o e aining. In his spi i , we p o ide a me hod o ind ou when he amoun o da a collec ed a he p oduc ion en i onmen is ep esen a i e o no mal beha io in he con ex o a de ec o o HTTP URI a acks based on 1-g amma . Ou app oach is ounded on a se o indica o s ela ed o he s a is ical p ope ies o he da a. These indica o s a e pe iodically calcula ed du ing da a collec ion, p oducing ime se ies ha s abilize when mo e aining da a is no expec ed o ansla e o be e sys em pe o mance, which indica es ha da a collec ion can be s opped. We p esen a case s udy wi h eal-li e da ase s collec ed a he Uni e si y o Se ille (Spain) and a public da ase om he Uni e si y o Saska chewan. The applica ion o ou me hod o hese da ase s showed ha mo e han 42% o one ace, and almos 20% o ano he we e unnecessa ily collec ed, he eby showing ha ou p oposed me hod can be an e icien app oach o collec ing aining da a a he p oduc ion en i onmen . INDEX TERMS Anomaly-based in usion de ec ion, da ase assessmen , aining. I. INTRODUCTION Anomaly-based In usion De ec ion Sys ems (AIDS) enable he iden i ica ion o suspicious beha io ha signi ican ly di e s om no mal ac i i ies in a compu e sys em o ne wo k [1]. To his end, AIDS model he no mal ac i - i y o a sys em adop ing di e se app oaches (e.g., s a is i- cal, knowledge-based, o machine lea ning echniques) [2]. A p e equisi e o AIDS is o ain hei model wi h a da ase ( aining da ase ) ha ep esen s he no mal ope a ion o he p o ec ed sys em. Once ained, no mal ac i i y p o iles a e o med and he sys em pe o mance can be e alua ed by a ing he e en s included in a es ing da ase . Public benchma k da ase s a e commonly used o com- pa e di e en esea ch esul s [3]. Howe e , in eal-li e The associa e edi o coo dina ing he e iew o his manusc ip and app o ing i o publica ion was Ana Lucila Sando al O ozco. deploymen s, AIDS need o be ained and alida ed wi h da ase s ha ai h ully ep esen he a ic seen in p oduc ion. Indeed, inadequa e o ou da ed da ase s may lead o alse ala ms because new beha io s, o changes in he p o ec ed sys em, can be in e p e ed as anomalies, which is a gen- e al issue wi h AIDS [4]. The e o e, besides hei pa icula models and echniques, he success o anomaly-based de ec- o s s ongly depends on he a ailabili y o sui able aining da ase s [5]. The c ea ion o aining da ase s wi h eal-li e p ope ies is no i ial. AIDS in p oduc ion equi e o be ( e) ained wi h da ase s ha a leas : (a) a e ee o a acks (o else hese a e p ope ly labeled), and (b) ep esen no mal a ic (e.g., up- o- da e a ic simila o p oduc ion). O he desi able p ope ies o a da ase desc ibed by Viegas e al. [6] include: easily upda able, a ian , co ec , ep oducible (so esea che s can compa e), and sha eable (i.e., wi h no con iden ial da a). 44410 This wo k is licensed unde a C ea i e Commons A ibu ion 4.0 License. Fo mo e in o ma ion, see h p://c ea i ecommons.o g/licenses/by/4.0/ VOLUME 8, 2020 R. Es epa e al.: How Much T aining Da a Is Enough? Case S udy o HTTP Anomaly-Based In usion De ec ion Addi ionally, Sha a aldin e al. [7] also poin ed o he inclu- sion o a ian p o ocols and app op ia e documen a ion as wo desi able p ope ies o da ase s. F om he p e ious equi emen s, one can in e ha ex ac ing sui able da ase s om eal-li e aces is no s aigh o wa d and may equi e a p ocess o sani iza ion [8], [9] o, a leas , iden i y a acks embedded in he ace (an example o sani iza ion o HTTP aces can be ound in [10]). Howe e , he wo kload asso- cia ed wi h his p ocess g ows linea ly wi h he size o he ace. And, al hough unsupe ised sani iza ion app oaches ha e been sugges ed (e.g., analysis o en opy [11], o il- e ing known-a acks wi h signa u e-based IDS [12]), manual supe ision may be una oidable in o de o disco e a acks (e.g., 0-day) unno iced by ully au oma ed me hods [13], [14]. The size o a da ase is a ac o ha has no ecei ed much a en ion in he scien i ic li e a u e. One possible ea- son is ha i is commonly assumed o be a gi en in he expe imen al ou line. A gene ally accep ed idea is ha a la ge olume o da a is mo e ep esen a i e o no mal ac i - i y, and as such, i ansla es o be e AIDS pe o mance, which also seems in ui i e. Indeed, a iny da ase may lead o insu icien aining and, consequen ly, poo pe o mance. Howe e , a la ge da ase may exhibi some d awbacks. Fi s , he da a collec ion may ake weeks o e en mon hs, which besides inc easing he ime- o- ain he AIDS (and hus, delay he s a o ope a ion), can also be associa ed wi h highe esou ce consump ion in e ms o s o age o compu a ional powe du ing da a p ep ocessing o aining [15]. This ac migh limi applicabili y in de ices wi h limi ed p ocessing abili y o s o age capaci y such as hose commonly ound in indus ial con ol sys ems, o in he ield o IoT (especially wi h compu a ionally-in ensi e algo i hms [16]). Secondly, he wo kload associa ed wi h he sani iza ion o a la ge ace can be p ohibi i e i done manually, o else, i he sani iza ion p ocess is ully au oma ed o skipped, he isk o ha ing unno iced a acks in he esul ing da ase inc eases wi h he da ase size. Las bu no leas , la ge da ase s occasionally may lead o he o e - aining p oblem in which models a e o e -adap ed o he aining se and, as such, AIDS pe o - mance de e io a es [17]. In his pape , we in es iga e he impac o he size o a aining da ase on he pe o mance o an anomaly-based in usion de ec o . The unde lying hypo hesis is ha he e is an op imum size om a cos -bene i pe spec i e, which depends on he de ec ion echniques and model used by he AIDS, as well as he cha ac e is ics o he cap u ed a - ic [18]. Wi h his in mind, we p opose a no el me hod o ind he op imal size o a da ase sui ed o aining AIDS based on 1-g amma models. We use indica o s ha cha ac- e ize he lea ning alue o da a collec ed o e ime. When hese indica o s s abilize, he amoun o da a collec ed is conside ed op imum o aining (i.e., mo e da a would no p oduce be e AIDS pe o mance). A case s udy applies his me hodology o h ee eal-li e se ice aces om ou uni e si y, and one public da ase om he Uni e si y o Saska chewan [19]. The no el y and o iginali y o his wo k a e: •We s udy he e ec o he da ase size on he pe - o mance o de ec o s o HTTP URI a acks based on 1-g amma models. •We p o ide a me hod o es ima e he ep esen a i eness o a aining da ase wi h espec o no mal beha io , which is applied in a eal-li e case s udy. •We sugges indica o s applicable o 1-g amma models ha enable he compa ison o wo e olu iona y e - sions o he same da ase in e ms o he aining da a su iciency. The main con ibu ion o his pape is a me hod o de e - mine when he da a collec ed is ep esen a i e o no mal beha io . This can be use ul o educing he size o exis ing da ase s (e.g., o educe he isk o o e aining), o educe he ime spen collec ing da a a he p oduc ion en i onmen (e.g., o educe he ime needed o pu he AIDS in p oduc ion), o o es ima e when ( e) aining is necessa y. Al hough his wo k is es ic ed o AIDS based on 1-g amma , he p inciples and ideas e ealed could be pa ially eused by he esea ch communi y o in es iga e ex ensions o di e en models. The emainde o his pape is as ollows. Sec ion II p esen s ela ed wo ks. Sec ion III in oduces he e e ence AIDS model, de ini ions and e minology used. Sec ion IV desc ibes he da ase s and he esul ing dic iona ies used in ou s udy. The empo al e olu ion o hese dic iona ies is s udied in Sec ion V. Ou me hod o on-line da a collec ion is desc ibed in Sec ion VI, and Sec ion VII desc ibes he limi a ions o his wo k. Finally, Sec ion VIII concludes he pape and ou lines u u e wo k. II. RELATED WORKS As s a ed ea lie , he quali y o he da ase s used by anomaly-based in usion de ec o s has a decisi e in luence on hei pe o mance. In he scien i ic li e a u e, he pe o mance o di e en models and echniques is commonly compa ed using public benchma k da ase s whose quali y ha e been subjec o c i icism by some au ho s such as Somme and Paxson [4] o Sha a aldin e al. [7]. I is also possible o ind some wo ks [18], [20] aimed a de ining how o ca y ou a co ec compa ison o di e en AIDS acco ding o he cha ac e is ics o he da ase s. Howe e , as men ioned ea lie , public benchma k da ase s, albei necessa y o compa ing esea ch esul s, a e no sui able o aining models in p ac- ice due o he lack o eal-li e p ope ies simila o hose seen in p oduc ion. The p oblem o cap u ing ep esen a i e da a sui able o aining o alida ing models has been add essed in he pas in he esea ch ield o machine lea ning [21], as well as in he anomaly-based in usion de ec ion esea ch ield [22]. The gene a ion o ealis ic da ase s om cap u ed a ic may be a esou ce-in ensi e ask ha some au ho s ha e ied o alle ia e. In [23], he au ho s p opose echniques o ins umen ing ne wo k wa a e compe i ions o collec scien i ically alid labeled da ase s, which o he wise would be esou ce-in ensi e. Simila ly, Vela de-Al a ado e al. [11] VOLUME 8, 2020 44411 R. Es epa e al.: How Much T aining Da a Is Enough? Case S udy o HTTP Anomaly-Based In usion De ec ion ema k he sca ci y o sui able da ase s o AIDS de elop- men and p opose a semi-au oma ed p ocess o he sani iza- ion o he a ic cap u ed based on he en opy o embedded a ic lows. This enables he collec ion o la ge olumes o da a wi hou excessi e esou ce consump ion in e ms o manual supe ision o compu a ional esou ces. Howe e , as s a ed ea lie , ully au oma ed sani iza ion me hods can ne e gua an ee ha he esul ing da ase s a e ee o a acks. Few au ho s ha e s udied he in luence o he aining da ase on he pe o mance o he AIDS. In [24], he au ho s s udied he e ec o pa i ioning a da ase o ob ain sepa a e pieces o aining and e alua ion. They ound ha di e en da a blocks p oduced di e en esul s in AIDS pe o mance, which sugges s ha he en i e da ase exhibi ed he e oge- neous cha ac e is ics o e ime. Maxion and Tan [25], [26] ha e s udied he s uc u e and egula i y o cap u ed da a and i s in luence in he pe o mance o an HTTP-a ack AIDS based on n-g ams. The au ho s gene a ed a i icial da ase s o he same size bu wi h inc eased complexi y (acco ding o he ela i e condi ional en opy) ob aining a a e o alse posi i es ha inc eased exponen ially wi h he in e se o he complexi y o he da a. The au ho s concluded ha aining should be adap ed o he cha ac e is ics o he da ase , including i s a iabili y o e ime, which leads o he conside a ion o a empo al window in he aining da ase . A simila conclusion was d awn by Lee e al. in [27], whe e he au ho s analyzed he p oblems associa ed wi h he use o mul iple con igu a ions and da ase s o e alua ing AIDS pe o mance. The size o he aining da ase has ecei ed sca ce a en- ion in he esea ch li e a u e. Kishimo o e al. [17] s udied he app op ia e size o a lea ning da ase o anomaly-based in usion de ec ion based on machine lea ning. In hei wo k, he au ho s collec ed In e ne aces om a honeypo and analyzed he e ec o ace size on he pe o mance o hei classi ie s. They ound ha when he lea ning da ase was oo small (e.g., one day), he a e o alse posi i es was high due o insu icien aining. On he o he hand, when he size o lea ning da ase was ex emely la ge (e.g., en days), o e i ing caused he de e io a ion o pe o mance. The e o e, hey expe imen ally concluded ha he app op i- a e size was i e days o cap u e when using Kyo o2006+ public da ase o alida ion. This suppo s ou ini ial hypo h- esis ha he e is an op imum size o he aining da ase , which depends on he echniques and models used, and he p ope ies o he cap u ed a ic. A simila claim is sup- po ed in [28], whe e he in luence o he size o he aining da a in wo classi ie s was s udied. One o he classi ie s compa ed (Nai e Bayes Classi ie ) was also success ully es ed in ano he wo k ela ed o anomaly-based in usion de ec ion [29]. Finally, some wo ks ha e poin ed o he need o e- aining he models [4], [5] as a sound solu ion o he p ob- lem o da a shi [30]. Howe e , ew wo ks ac ually add ess he issue o model adap a ion o dynamic changes. In [31] he au ho s p opose a ba ch-based app oach ha in ol es manual wo k o de e mine he le el o pe o mance deg a- da ion, which indica es when e- aining is necessa y. In a mo e gene ic con ex , he au ho s in [32] ha e p oposed he use o EWMA and Kolmogo o -Smi no es s o de e mine he occu ence o da a shi in non-s a iona y en i onmen s. Ou con ibu ion can also be applied o ind i he da ase used o aining is s ill ep esen a i e o no mal beha - io , and he e o e, o ind whe he e- aining is necessa y o no . III. REFERENCE AIDS AND TERMINOLOGY A da ase has o be sui ed o he speci ic model and pa ame- e s used by he anomaly de ec o . In his ega d, he indings o his wo k a e limi ed o de ec o s o anomalous HTTP eques s based on p obabilis ic models (e.g., n-g am [33], o Ma ko -based models [34]). In pa icula , he AIDS used in his wo k is based on 1-g amma since he au ho s a e la gely expe ienced in his echnique (see [35]), which is simple enough as o le he eade s ay ocused on he con ibu ion. In ou e e ence AIDS, he goal o he aining phase is o o m a dic iona y ha will be used a e wa d o classi y Uni- e sal Resou ce Iden i ie s (URIs) ecei ed in HTTP eques s as no mal o anomalous. As such, he da ase s used in his wo k a e a collec ion o URIs ex ac ed om HTTP ace iles. A. DICTIONARY FORMATION Le U= {ui|i∈N}be he se o URIs con ained in a aining da ase . RFC 3986 [36] de ines he s uc u e o a URI, which is basically a ex s ing composed o an op ional p o ocol, an op ional hos , a sequence o one o mo e pa h segmen s, namely absolu e pa h and, op ionally, a que y composed o a sequence o a ibu es, each o hem wi h an op ional alue. This is gene ally exp essed as: "h p://"hos [":"po ][abs_pa h["?"que y]] A URI can be pa sed using a se o s anda d delimi e s (:/?#[]@!$&’()*+,;=),1ob aining a se o sub-s ings o wo ds ha a e cen al o ou AIDS. Fo he pu pose o anomaly-de ec ion, only hose wo ds ex ac ed om he pa h, a ibu e o alue ields a e conside ed o in e es in his wo k (i.e., we assume ha hos and po a e in a ian h oughou he ace). Le us de ine he ocabula y lea ned om a aining da ase (U), as he se o wo ds obse ed a e segmen ing all he URIs con ained in U: W(U)= {wi|1≤i≤M}(1) whe e Mis he ca dinali y o he ocabula y. Le O(U)= {oi|1≤i≤M}be he numbe o occu ences (i.e., absolu e equency) o he wo ds obse ed in he aining da ase U. 1We conside bo h gen-delims and sub-delims, as de ined in he s anda d, o be able o pa se he que ies. 44412 VOLUME 8, 2020 R. Es epa e al.: How Much T aining Da a Is Enough? Case S udy o HTTP Anomaly-Based In usion De ec ion Le us de ine a dic iona y, o equi alen ly, a 1-g amma 2 as he se o di e en wo ds (and hei absolu e equency) obse ed a e segmen ing he URIs con ained in a da ase U as: D(U)= {(wi,oi)|wi∈W(U),oi∈O(U))}(2) Gi en a dic iona y, he ela i e equency (o empi ical p obabili y) o wo d wican be eadily ob ained as: pi=oi O(3) whe e Ois he o e all numbe o obse a ions: O= M X i=1 oi(4) Finally, le P(U) be he se o ela i e equencies o he wo ds obse ed: P(U)= {pi|1≤i≤M}(5) As an example, conside he ollowing URI: h p:// aj.us.es/se /index.php?se =200& heme=blue I is possible o segmen his URI in 8 s ings (h p, aj.us.es, se , index.php, se , 200, heme, blue) using s anda d delimi e s. Then, using only s ings om he a ibu e, pa h and alue ields, he ex ac ed dic iona y would be: D= {(se ,2),(index.php,1),( heme,1), (200,1),(blue,1)}(6) The o e all numbe o obse a ions would be O=6, and he ela i e equency o he wo ds would be 1/6 o all bu he i s one which would be p1=2/6. B. AIDS PERFORMANCE Figu e 1illus a es a gene ic scheme o he assessmen o he pe o mance o AIDS. This scheme elies on h ee disjoin da ase s: •T aining da ase : i con ains URIs ha ep esen no mal beha io , and as such, i should be ee o a acks. This da ase is used o ain he model and is he subjec o ou s udy (i.e., U). •E alua ion da ase (clean): his da ase is also composed o (di e en ) ins ances om he no mal beha io and i should be ee o a acks. In his wo k, he e alua ion- clean da ase is simila o he aining da ase (indeed, i comes om hal ing he collec ed aces). •E alua ion da ase (a acks): his da ase con ains mali- cious URIs used o e alua e he pe o mance o he de ec o . In ou wo k, i is composed o 2 200 mali- cious URIs om a public eposi o y [37] (ca ego y 2An analysis on a pe - ield basis is also possible by a anging wo ds in o ield-based dic iona ies as in he o iginal SSM echnique p oposed in [35]. Ne e heless, o he sake o simplici y and cla i y, we conside a single s a e, me ging all wo ds in a single dic iona y. Expe imen s ca ied ou using h ee s a es did no show di e ences in he beha io o he p oposed me hod. FIGURE 1. AIDS pe o mance e alua ion. ML-d i en-Web-Applica ion-Fi ewall) ha can be downloaded om [38]. A e p ocessing he aining da ase ( aining mode in Figu e 1), he dic iona y is o med and AIDS pe o mance can be e alua ed. The AIDS (in e alua ion mode) uses he dic iona y when assigning an anomaly sco e o each URI ound in he e alua ion da ase s. Gi en a URI uicomposed o a se o wo ds Wui= {wi|i=1,· · · ,L}, i s anomaly sco e is calcula ed as ollows: AS(ui)= − 1 L L X i=1 log(xi) (7) whe e xi=(pi,i wi∈W(U) poo ,i wi/∈W(U)(8) being poo a de aul alue assigned o he wo ds no included in he dic iona y (i.e., ou o ocabula y wo ds). In his wo k, a e some uning, we selec ed poo =p3 min, whe e pmin is he lowes p obabili y in P(U). This is an e ec i e solu ion o deal wi h he p oblem o insu icien aining [35]. Finally, i he anomaly sco e exceeds a h eshold θ (i.e., AS(ui)> θ), he URI uiis classi ied as anomalous. O he wise, i is conside ed no mal. In he e alua ion p ocess illus a ed in Figu e 1, he AIDS classi ies egis e s om he clean da ase s as ei he no mal (i.e., T ue Nega i e –TN–) o anomalous (i.e., False Pos- i i e –FP–), whe eas egis e s om he a ack da ase can be classi ied as ei he no mal (i.e., False Nega i e –FN–) o anomalous (i.e., T ue Posi i e –TP–). These ou basic indi- ca o s allow one o e alua e AIDS pe o mance h ough a - ious me ics such as De ec ion Ra e (DR) and False Posi i e Ra e (FPR): DR =TP TP +FN ,FPR =FP FP +TP (9) O he me ics a e possible (e.g., accu acy o sensibil- i y) [3], bu good pe o mance is always a synonym o e y high DR and e y low FPR. Howe e since we a e going o compa e pe o mance in di e en scena ios, and he classes VOLUME 8, 2020 44413 R. Es epa e al.: How Much T aining Da a Is Enough? Case S udy o HTTP Anomaly-Based In usion De ec ion no mal and anomalous a e clea ly unbalanced ( he a ack da ase is se e al imes smalle han he o he s), we will use he me ic geome ic mean [39] as pe o mance indica o . This me ic combines ecall and speci ici y, and hence, i is sensi i e o bo h de ec ion capaci y and alse posi i es. Thus, o he emainde o his pape , he AIDS pe o mance me ic will be gi en by: η=pDR ·(1 −FPR) (10) IV. CHARACTERIZING THE TRAINING DATASETS AND DICTIONARIES OF THIS STUDY Wi hou loss o gene ali y, o he emainde o his wo k, we can assume ha dic iona ies a e a ays a anged so wo ds a e so ed by hei equency (i.e., wo ds mo e equen a e i s ). Tha is: D(U)= {(wi,oi)|1≤i≤M,o ≥ok∀ ≤k}(11) A. STATISTICAL PROPERTIES OF A DICTIONARY A dic iona y D(U) is s a is ically cha ac e ized by he empi - ical p obabili y o i s wo ds P(U) (i.e., p obabili y mass unc ion). Since we a e assuming ha wo ds a e so ed by hei equency, a plo o P(U) should show a mono onically dec easing unc ion such as he one illus a ed in Figu e 2, whe e he ho izon al axis ep esen s he index o he ele- men s in P(U) (i.e., wo d index). Obse e ha he maximum and minimum empi ical p obabili ies a e pmax =p1and pmin =pM espec i ely. FIGURE 2. Gene ic p obabili y mass unc ion o a ypical dic iona y. Acco ding o ou expe ience, he p obabili y mass unc ion o URI-based dic iona ies is likely o exhibi a ail o med by wo ds a ely obse ed. I so, he plo o his unc ion can be spli in o wo con iguous egions: co e, wi h he mo e e- quen wo ds, and ail wi h he less equen wo ds, by simply de ining a lowe h eshold o he empi ical p obabili y o wo ds ha belong o he co e (see p h in Figu e 2). Then, a ail sub-dic iona y T(U)⊆D(U) can be de ined as: T(U)= {(wi,oi)|(wi,oi)∈D(U),pi<p h}(12) Simila ly, a co e sub-dic iona y C(U)⊆D(U) can be de ined as: C(U)= {(wi,oi)|(wi,oi)∈D(U),pi≥p h}(13) In Figu e 2, he numbe o wo ds ha belong o he co e is ep esen ed by nc= |C(U)|. Rega ding he alue o he h eshold p h, i should be lowe han he a e age wo d equency, and also should accoun o he dynamic ange o he p obabili y mass unc ion. A e some expe imen a ion, we ound ha he ollowing alue p o ided good esul s: p h =1−(pmax −pmin) M=1+pM−p1 M(14) Besides P(U), a dic iona y can be u he cha ac e ized by he ollowing s a is ics: •A e age ela i e equency o wo ds. R=M O(15) •En opy o he dic iona y. S= − M X i=1 pi·log2pi(16) •En opy o he co e sub-dic iona y. Sco e = − nc X i=1 pi·log2pi,pi≥p h (17) •Cumula i e empi ical p obabili y o co e-wo ds: Pco e = nc X i=1 pi,pi≥p h (18) No e ha P ail =1−Pco e. Nex , we in oduce he expe imen al da ase s used in his wo k and cha ac e ize he dic iona ies o med a e aining ou e e ence AIDS wi h hem. B. TRAINING DATASETS AND BASELINE DICTIONARIES FORMED In o de o pe o m a comp ehensi e s udy, we ha e used ou HTTP aces collec ed a di e en expe imen al es beds, which has p oduced da ase s wi h he e ogeneous cha ac e is- ics. The expe imen al da ase s used in his wo k a e: •Biblio: his da ase is o med by he daily aces col- lec ed by he web se e o he Lib a y o he Uni- e si y o Se ille (h p://bib.us.es). I includes 1 002 000 HTTP eques s ecei ed om 1/1/2017 o 17/07/2017. •Teulada: his da ase is o med by he aces o a web applica ion se e de o ed o in e wo k wi h a esea ch-o ien ed IoT senso ne wo k deployed in he ci y o Se ille. •Uo S: his is a public da ase om he Uni e si y o Saska chewan [19] ha includes 2.3 million HTTP eques s (me hod +URI). 44414 VOLUME 8, 2020 R. Es epa e al.: How Much T aining Da a Is Enough? Case S udy o HTTP Anomaly-Based In usion De ec ion TABLE 1. Mos ele an s a is ics o he conside ed da ase s ( aining pa i ions). FIGURE 3. P obabili y mass unc ion o he dic iona ies o med om: a) Teulada, b) In es, c) Biblio, d) Uo S. •In es: his da ase is c ea ed om he aces o a documen -sea ch web se ice o he Uni e si y o Se ille gea ed owa d esea ch (h p:// ama.us. es). I includes abou 4.6 million eques s ecei ed du - ing May 2018. The p e ious aces ha e been sani ized o emo e exis ing a acks. Then, he da ase s ha e been hal ed o c ea e he aining and alida ion (clean) pa i ions. Fo he emainde o his pape (bu when add essing pe o mance e alua ion), we will only e e o he aining pa i ion. Table 1p o ides in o ma ion abou he aining da ase s c ea ed on each expe imen al en i onmen , and some s a is- ics o he dic iona y o med wi h each da ase . These p op- e ies show di e si y in size, numbe o wo ds obse ed, e c. Fo example, Teulada exhibi s a educed ocabula y (e.g., 1 101 di e en wo ds) while In es exhibi s a la ge one (153 653 di e en wo ds). This di e ence is a ibu able o he se ice p o ided in each case (e.g., Teulada is mo e simila o a s a ic websi e whe eas In es p o ides a sea ch se ice). This in o ma ion is complemen ed wi h a plo o he mass p obabili y unc ion o he dic iona ies o med shown in Figu e 3. No e ha axes a e ep esen ed in log scale o cla i y, which, albei imp o es he isualiza ion o he co e, dis o s he ac ual shape. Resul s om Table 1and Figu e 3show ha he co e sub-dic iona y is always composed o a educed numbe o wo ds (less han 1% o each ocabula y) ha accoun s o he bulk o he empi ical p obabili y in each ocabula y. As shown in Table 1, co e wo ds accoun o a cumula i e p obabili y anging om 83% (Teulada) o 95% (Biblio). This sugges s ha he choice o p h, acco ding o Eq. (39), is easonable, as ails a e commonly expec ed o ep esen less han 20% o he dis ibu ion. No e also ha he en opy o he co e is a signi ican ac ion o he en opy o he da ase . On he o he hand, he ansi ion be ween he co e and he ail is mo e ab up in Teulada and In es han in Biblio and Uo S, which migh show ha he la e wo da ase s a e mo e sensi i e o he choice o he h eshold. V. TEMPORAL EVOLUTION OF DICTIONARIES In his sec ion, we s udy he e olu ion o he p obabili y mass unc ion o a dic iona y wi h he numbe o URIs p ocessed. VOLUME 8, 2020 44415 R. Es epa e al.: How Much T aining Da a Is Enough? Case S udy o HTTP Anomaly-Based In usion De ec ion FIGURE 4. Tempo al E olu ion o he co e and he ail in ou da ase s. In he da ase s, URIs a e assumed o be in ch onological o de . As such, we can ega d his s udy as a empo al e o- lu ion. We expec h ee di e en beha io s in his empo al e olu ion ha le us classi y he dic iona ies acco dingly as: 1) S able dic iona y: i s p obabili y mass unc ion emains mos ly s eady a e a ce ain numbe o URIs. This would be he case o websi es wi h a closed se o po en ial wo ds in hei URIs (e.g., s a ic websi e) when he beha io o use s (i.e., eques s) is egula o e ime. 2) Co e-s able dic iona y: he p obabili y mass unc ion o he co e-subdic iona y emains mos ly s eady a e p ocessing a ce ain numbe o URIs, bu i does no s abilize in he ail-subdic iona y. I would be he case o websi es ha include a iable pa s in hei URIs such as imes amps, au o-inc emen al alues, hashes, e c. Al hough some wo ds a e equen ly obse ed (co e wo ds), some o he s ( ail wo ds) a e sca cely seen (maybe one o wo imes), ha ing li le in luence in he anomaly sco e o a URI. 3) Non-s able dic iona y: new URIs migh p oduce sig- ni ican changes in he p obabili y mass unc ion o he dic iona y. As such, nei he co e no ail sub-dic iona ies s abilize wi h he numbe o URIs p o- cessed. This is p obably he case o dynamic websi es wi h highly changing esou ces. Figu e 4shows he empo al e olu ion o he dic iona ies o med wi h ou da ase s. Fo each da ase , we ha e plo ed he mass p obabili y unc ion ob ained a e p ocessing di e - en pe cen ages o he da ase size. Fo a clea e iew, he ail and co e ha e been ep esen ed using wo sepa a e scales. The empo al e olu ion o he ail and he co e shown in Figu e 4 con i ms he ypes o dic iona ies sugges ed ea lie . Teulada emains s able a e p ocessing a minimum po ion o he da ase (i.e., s able dic iona y), Biblio exhibi s signi ican changes in his ail bu , a e a ce ain numbe o URIs, i s co e emains s eady (i.e., co e-s able dic iona y), and Uo S and In es show uns eadiness in bo h co e and ail sub-dic iona ies (i.e., non-s able dic iona ies). Rega ding he lowe h eshold p obabili y p h ( ansi ion zone in Figu e 4), i s a ia ions wi h he numbe o URIs p ocessed a e minimal. Indeed, as demons a ed in Appendix, he e is a poin a e which i s a ia ions a e negligible. Fo he emainde o his sec ion, we in es iga e how some da ase s may hold egis e s ha ba ely impac he s a is ical p ope ies o a dic iona y. We wo k unde he assump ion ha in some cases, he e should be a minimum-sized da ase ha exhibi s he same s a is ical p ope ies as ha o a bigge one and, consequen ly, p ocessing mo e egis e s does no pay o om he pe spec i e o AIDS pe o mance. This idea will be used in he nex sec ion o s op da a collec ion. A. STABILITY CONDITIONS OF A DICTIONARY In his sec ion, we s udy he condi ions ha can help us decide when he s a is ical p ope ies o a dic iona y o a ce ain ype become in a ian o mo e da a om he same da ase . 44416 VOLUME 8, 2020 R. Es epa e al.: How Much T aining Da a Is Enough? Case S udy o HTTP Anomaly-Based In usion De ec ion 1) STABLE DICTIONARY (TYPE 1) Le U= {ui|1≤i≤U}be he se o URIs con ained in a da ase in ch onological o de . Then, we say ha a dic iona y is s able i he e is a alue Us ha mee s: W(U0)=W(Us),∀U0>Us(19) P(U0)=P(Us),∀U0>Us(20) whe e U0is he subse composed o he i s U0URIs om U, and Usis he subse composed o he i s UsURIs om U0. The i s condi ion –Eq. (19)– can be pu in a mo e ac able o m by simply using he ca dinali y o he ocabula ies (i.e., |W(U0)| = Us∀U0>Us) since Us⊂U0and URIs a e p ocessed in ch onological o de . The second condi ion –Eq. (20)–, howe e , is impossible o mee in a s ic sense in p ac ice, as e e y new URI p ocessed impac s he equency dis ibu ion. Thus, his condi ion has o be elaxed om equali y o dis ibu ions o simila i y o dis ibu ions. We use he Chi-squa ed es (χ2 es ) o compa e he sim- ila i y o wo dis ibu ions. This es indica es whe he he e is a signi ican di e ence be ween he expec ed equencies and he obse ed equencies in one o mo e ca ego ies. In ou case, he se o ca ego ies is he se o wo ds W(U0) whose ca dinali y is M0. Le ’s assume ha D0=D(U0) has an unknown p obabili y dis ibu ion P0=P(U0) and an o e all numbe o obse a ions O0, and ha D=D(U) has a known dis ibu ion P=P(U). Then, we would like o alida e he ollowing hypo hesis: H0:P=P0,(21) H1:P6= P0(22) The χ2s a is ic can be calcula ed acco ding o he ollow- ing equa ion: χ2(D,D0)= M0 X k=1 (o0 k−pk·O0)2 pk·O0(23) I χ2(D,D0) is 0, he dis ibu ion o he obse a ions in Dand D0is iden ical. I no , we can conside ha bo h dis ibu ions a e simila (i.e., accep he null hypo hesis) wi h a ce ain s a is ical signi icance αi i s p alue (indica o o suppo o ejec he null hypo hesis) is g ea e han α (i.e., p alue(D,D0)=P ob(χ2 (M0−1) > χ2(D,D0)) > α)).3 Finally, no ice ha in o de o ha e a eliable applica ion o he Chi-squa ed es , he ollowing has o be me : (a) he o e all numbe o obse a ions has o be la ge, (b) he e- quency o each wo d should be g ea e han a lowe h esh- old ( ypically 2). In ou case, he i s condi ion is me in all da ase s, and he second condi ion has been applied by excluding wo ds whose equency is less han ha lowe h eshold om bo h Dand D0. The e o e, he equi emen o a dic iona y o be consid- e ed s able wi h a s a is ical signi icance o α, is ha he e is 3Typical accep ed alues o αa e: 0.05,0.01 and 0.001. a alue Us ha mee s he ollowing condi ions: |W(U0)| = |W(Us)|,∀U0>Us(24) p alue(D,D0)> α, ∀U0>Us(25) 2) CORE-STABLE DICTIONARY (TYPE 2) In his case, bo h he mass p obabili y unc ion and he num- be o wo ds in he co e-subdic iona y s abilize a e some poin , bu he numbe o new wo ds (in he ail) is con in- uously g owing. The e o e, his ype o dic iona ies can be cha ac e ized by: |W(U0)| ≥ |W(Us)|,∀U0>Us(26) C(U0)=C(Us),∀U0>Us(27) In his case, s abili y condi ions can be se based on he s abili y o he co e-subdic iona y C(U): |C(U0)| = |C(Us)|,∀U0>Us(28) p alue(C(U0),C(Us)) > α, ∀U0>Us(29) As shown in Appendix, in ype 2 dic iona ies, p h ends o s abilize a e a ce ain poin , and so does he numbe o co e-wo ds and hei cumula i e p obabili y. Ne e heless, p alue(C(U0),C(Us)) is pa icula ly sensi i e o luc ua ions in he co e- ail delimi a ion, which depends on p h. The e o e, i would be desi able o eplace Eq. (29) wi h an al e na i e condi ion ha le us compa e he simila i y o he dis ibu ions and has be e ac abili y. We belie e ha en opy, al hough is a so e condi ion, can be used o his end. Lemma 1: Gi en a co e-s able da ase U, o size U, he e is a minimal subse , o size Us<U, whose en opy would be equal o he en opy o he ull da ase i U was la ge enough. P oo : see Appendix. Then, o he emainde o his wo k, we conside ha a dic iona y is co e-s able i he e is a alue Us ha mee s Eq. (28) and: S(U0)=S(Us)±σ, ∀U0>Us(30) whe e σis a cons an ha accoun s o minimal di e ences which ends o 0 wi h he da ase size. Ob iously, hose dic iona ies ha can no be classi ied as ype-1 o ype-2, will be conside ed non-s able ( ype 3)4 o which no s abili y condi ions can be se . B. APPLICATION OF THE STABILITY CONDITIONS TO FIND DISPENSABLE DATA IN OUR DATASETS In his sec ion, we seek he p e ious s abili y condi ions in ou expe imen al da ase s in o de o ind he minimum alue o U0, namely Us, so ha he s a is ical p ope ies o he esul ing dic iona y we e simila o ha o he dic iona y o med wi h he ull da ase . In his p ocess, we i s di ide he o iginal da ase s in da a chunks o 1UURIs. Then, we look 4A gi en aining da ase can be classi ied as ype 3 e en i i s associa ed sou ce could co espond o ype 1 o ype 2 due o insu iciency o he acqui ed aining da ase . In any case, he conclusion is ha addi ional obse a ions a e needed. VOLUME 8, 2020 44417 R. Es epa e al.: How Much T aining Da a Is Enough? Case S udy o HTTP Anomaly-Based In usion De ec ion FIGURE 5. E olu ion o he numbe o wo ds (M) o di e en da ase sizes. FIGURE 6. E olu ion o he En opy (S) and wo d in he Co e (nc) o di e en da ase sizes. o he minimum numbe o pieces ha mee s he s abili y condi ions. The i s condi ion o ype 1 dic iona ies is ela ed o he numbe o wo ds con ained in he da ase –Eq. (24)–. Figu e 5 shows he e olu ion o his indica o (M) wi h he numbe o chunks p ocessed o each da ase unde s udy. The size o he chunk on each case is a di iso o he da ase size. The esul s in Figu e 5show ha only Teulada mee s his condi ion. The o he equi emen o a da ase o be conside ed ype 1 was simila i y o dis ibu ion –Eq. (25)–. The e o e, we wan o ind he minimum alue o U0, namely Usso bo h dic iona ies D(U) and D(Us) a e simila wi h a s a is ical signi icance o α. Figu e 6shows he e olu ion o he en opy and he numbe o co e-wo ds (nc) in he da ase s. I can be no iced ha , besides Teulada, only Biblio exhibi s a s able beha io . Thus, acco ding o Lemma 1 and Eqs. (25), (28) and (29), Teulada is de ini i ely a da ase ha p oduces a s able ( ype-1) dic io- na y, whe eas Biblio can be classi ied as co e-s able ( ype-2). Algo i hm 1 UsSea ch Algo i hm o S able (Type=1) and Co e-S able (Type=2) Dic iona ies Inpu :U,U,α,1U,σ,Type Ou pu :Us 1: unc ion: D(n) 2: d={ui∈U|i≤n} 3: e u n d 4: end unc ion 5: D←D(U) 6: U0=U−1U 7: D0←D(U0) 8: i Type =1 hen 9: while ((α≤p alue(D,D0)) & (|W(U)| = |W(U0)|)&(U0> 1U)) do 10: U0←U0−1U 11: D0←D(U0) 12: end while 13: i α > p alue(D,D0) hen 14: Us←U0+1U 15: else 16: Us←U0 17: end i 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: i σ > |S(D)−S(D0))| hen 24: Us←U0+1U 25: else 26: Us←U0 27: end i 28: end i 29: e u n Us As such, we wan o ind he minimal subse Usso he di e ence o he en opy in bo h dic iona ies D(U) and D(Us) is lowe han σ. Algo i hm 1shows a pseudocode ha inds he alue o Us in da ase s ha p oduce s able o co e-s able dic iona ies. I akes as inpu he ini ial da ase conside ed, U, i s size, U, and ype, he α alue conside ed o simila i y’s s a is ical signi icance, he σ alue conside ed in Eq. 30, and he da ase size educ ion s ep 1. I i s builds he dic iona y D=D(U) using he ull da ase . Then, i builds a second dic iona y D0=D(U0) ha excludes he las 1UURIs. The simila i y condi ion (p alue o En opy di e ence) is hen examined and, i me , he size is educed by ano he 1UURIs, and D0is ebuil . Then, he simila i y condi ion is examined again. This p ocess con inues un il bo h a e no simila , o he da ase size canno be u he educed. The algo i hm e u ns Us. No e ha Us, will be lowe han Uonly when i is applied o he co ec da ase ype. Thus, i applied o In es and Uo S, 44418 VOLUME 8, 2020 R. Es epa e al.: How Much T aining Da a Is Enough? Case S udy o HTTP Anomaly-Based In usion De ec ion ANTONIO ESTEPA ecei ed he M.S. and Ph.D. deg ees in elecommunica ion enginee ing om he Uni e si y o Se ille, in 1998 and 2004, espec- i ely. F om 1998 o 2000, he was a so wa e and ne wo k enginee wi h a so wa e de elop- men company. In 2004, he was also a Visi o wi h he Depa men o Elec ical Enginee ing and Compu e Science, Uni e si y o Minneso a, USA. He is cu en ly an Associa e P o esso wi h he Depa men o Telema ics Enginee ing, Uni- e si y o Se ille. He has au ho ed o coau ho ed in se e al con e ences o jou nal a icles. His esea ch in e es s include he a eas o elecommunica ion ne wo ks, wi h a pa icula emphasis on ne wo king p o ocols, wi eless ne wo ks, and cybe secu i y. GERMAN MADINABEITIA ecei ed he M.S. and Ph.D. deg ees in elecommunica ion enginee - ing om he Uni e sidad Poli ecnica de Mad id, in 1986 and 2004, espec i ely. In he pas , he was wo king o en yea s as a p oduc enginee in he indus y. He is cu en ly an Assis an P o es- so wi h he Depa men o Telema ics Enginee - ing, Uni e si y o Se ille. His esea ch in e es s include he a eas o ne wo king, he In e ne o Things, cybe secu i y, and a ic enginee ing. VOLUME 8, 2020 44425