郭方方 潮洛蒙 朱建文

摘 要：大規(guī)模網(wǎng)絡(luò)環(huán)境和大數(shù)據(jù)相關(guān)技術(shù)的發(fā)展對(duì)傳統(tǒng)數(shù)據(jù)融合分析技術(shù)提出了新的挑戰(zhàn)。針對(duì)目前多源數(shù)據(jù)融合分析過程靈活性差、處理效率低的問題，提出了一種基于相似連接的多源數(shù)據(jù)并行預(yù)處理方法，該方法采用了分治和并行的思想。首先，通過對(duì)多源數(shù)據(jù)中的相似語義進(jìn)行統(tǒng)一、對(duì)個(gè)性語義進(jìn)行保留的預(yù)處理方法提高了靈活性;其次，提出了一種改進(jìn)的并行MapReduce框架，提高了相似連接的效率。實(shí)驗(yàn)結(jié)果表明，所提方法在保證數(shù)據(jù)完整性的基礎(chǔ)上，使總的數(shù)據(jù)量減小了32%。與傳統(tǒng)的MapReduce框架相比，改進(jìn)后的框架在耗費(fèi)時(shí)間方面減小了43.91%，因此該方法可以有效提高多源數(shù)據(jù)融合分析的效率。

關(guān)鍵詞：網(wǎng)絡(luò)安全;多源數(shù)據(jù);數(shù)據(jù)預(yù)處理;相似連接;MapReduce

中圖分類號(hào)： TP274

文獻(xiàn)標(biāo)志碼：A

Abstract： With the development of large-scale network environments and big data-related technologies， traditional data fusion analysis technology faces new challenges. Focusing on poor flexibility and low processing efficiency in current multi-source data fusion analysis process， a multi-source data parallel preprocessing method based on similar connection was proposed， in which the idea of dividing and conquering and paralleling was adopted. Firstly， the preprocessing method was improved to increase the flexibility by unifying similar semantics in multi-source data and retaining personality semantics. Secondly， an improved parallel MapReduce framework was proposed to improve the efficiency of similar connections. The experimental results show that the proposed method reduces total data volume by 32% while ensuring data integrity. Compared with traditional MapReduce framework， the improved framework decreases 43.91% of time consumed; therefore， the proposed method can effectively improve the efficiency of multi-source data fusion analysis.

Key words： network security; multi-source data; data preprocessing; similar connection; MapReduce

0 引言

多源數(shù)據(jù)的預(yù)處理過程是網(wǎng)絡(luò)環(huán)境進(jìn)行安全分析的重要環(huán)節(jié)，根據(jù)實(shí)際的應(yīng)用采取相應(yīng)的具體措施[1]。一般性地，包括數(shù)據(jù)清理、數(shù)據(jù)格式轉(zhuǎn)換、數(shù)據(jù)簡(jiǎn)約等過程。其中數(shù)據(jù)清洗作為一個(gè)重要的環(huán)節(jié)，通過按照一定規(guī)則篩選數(shù)據(jù)，去除數(shù)據(jù)中的冗余部分。好的數(shù)據(jù)清洗方法不僅能夠降低系統(tǒng)處理數(shù)據(jù)所需的時(shí)間，并且能夠提高數(shù)據(jù)分析結(jié)果的準(zhǔn)確度。

為了對(duì)數(shù)據(jù)源進(jìn)行靈活的數(shù)據(jù)清洗，盡量保留數(shù)據(jù)源的個(gè)性屬性，本文采用基于相似連接的數(shù)據(jù)清洗方法。相似連接在相似對(duì)象匹配問題中得到廣泛應(yīng)用，如互聯(lián)網(wǎng)、數(shù)據(jù)分析、數(shù)據(jù)庫(kù)等，匹配對(duì)象也日益多樣，如串、圖、字符串和集合等。為了適應(yīng)各種各樣的場(chǎng)景和對(duì)象，相似連接相關(guān)算法也得到了優(yōu)化和改進(jìn)。無論是基于單行串行數(shù)據(jù)還是集合數(shù)據(jù)，或是基于樹結(jié)構(gòu)還是圖結(jié)構(gòu)，優(yōu)化和改進(jìn)的方案主要以提高效率和靈活性或伸縮性為主。為了解決單行串行的相似連接候選集過多的問題，Li等[2]提出了一種基于劃分的傳遞性的相似連接，該相似連接的過程進(jìn)行的劃分，該方法在此句不通順，請(qǐng)修改相似匹配過程中利用傳遞性沒有使用全部子串，從而減少了匹配的候選集數(shù)目，提升了匹配的效率。為了提升算法的靈活性與伸縮性，Wang等[3]提出了一種快速相似連接算法，該算法既考慮到了相似的準(zhǔn)確度，又考慮到了相似連接屬性的模糊度，可以進(jìn)行靈活的篩選;然而隨著大數(shù)據(jù)與云計(jì)算等的出現(xiàn)，由于數(shù)據(jù)量的龐大導(dǎo)致算法效率低，這也是相似連接算法面臨的難題之一。

MapReduce作為一種并行框架，由于其擴(kuò)展性好、易實(shí)現(xiàn)等特點(diǎn)，被廣泛使用在數(shù)據(jù)并行處理中。陳一帆等[4]提出一種基于MapReduce的圖相似連接的處理方法，使用“過濾驗(yàn)證”框架下的MGSJion與Bloom Filter相結(jié)合，并使用MapReduce框架提升了算法整體的效率。陳子軍等[5]提出基于MapReduce框架的相似連接算法，該算法應(yīng)用對(duì)象是空間文本，在MapReduce框架實(shí)現(xiàn)了相應(yīng)的劃分和裁剪工作，提升了算法效率;然而MapReduce框架在被普遍應(yīng)用的同時(shí)，MapReduce框架本身的缺點(diǎn)也顯現(xiàn)出來，如：迭代計(jì)算比較乏力，計(jì)算中產(chǎn)生的Mapper數(shù)量過多，裝載和卸載較頻繁等問題。據(jù)此，Bu等[6]提出一種HaLoop可擴(kuò)展框架，通過添加循環(huán)控制模塊來解決迭代乏力的問題。為了進(jìn)一步提升效率，Zhang等[7]提出一種基于內(nèi)存的iMapReduce框架，通過Map和Reduce階段長(zhǎng)期駐留內(nèi)存和適時(shí)的中斷迭代次數(shù)來提升框架的計(jì)算效率;然而現(xiàn)有的基于內(nèi)存的框架處理方式比較粗糙，浪費(fèi)內(nèi)存空間比較嚴(yán)重。

據(jù)此，為了提高數(shù)據(jù)清洗的效率，本文提出了一種基于相似連接的數(shù)據(jù)預(yù)處理方法，并且采用改進(jìn)的MapReduce框架實(shí)現(xiàn)該算法。該框架基于內(nèi)存的思想來提升框架的并行效率，能夠高效地完成相似連接操作。

1 基于相似連接的數(shù)據(jù)預(yù)處理模型

為保障分析的全面性，傳統(tǒng)的安全分析方法盡可能多地獲取數(shù)據(jù)特征，構(gòu)建分析模型;然而大數(shù)據(jù)環(huán)境中數(shù)據(jù)源的特點(diǎn)致使數(shù)據(jù)量太大，并且會(huì)包含大量無用的、冗余的數(shù)據(jù)。若將這些多源數(shù)據(jù)直接導(dǎo)入作為源數(shù)據(jù)進(jìn)行分析，則會(huì)出現(xiàn)數(shù)據(jù)不完整、數(shù)據(jù)冗余等問題，從而影響系統(tǒng)效率和準(zhǔn)確率，因此，在進(jìn)行數(shù)據(jù)分析前，需要增設(shè)一個(gè)數(shù)據(jù)預(yù)處理過程，從中提取有用的數(shù)據(jù)，進(jìn)而提高數(shù)據(jù)挖掘結(jié)果的準(zhǔn)確性。數(shù)據(jù)預(yù)處理是很有必要的環(huán)節(jié)。

多源數(shù)據(jù)的清洗工作需要充分利用數(shù)據(jù)源之間的互補(bǔ)性，融合多方面的數(shù)據(jù)源信息。為了保留數(shù)據(jù)源的個(gè)性信息，并且最大化壓縮數(shù)據(jù)量，本文提出了多源數(shù)據(jù)預(yù)處理模型。主要環(huán)節(jié)包括以下幾個(gè)方面：首先，通過選取各自屬性特征模式對(duì)數(shù)據(jù)源進(jìn)行獨(dú)立篩選;其次，對(duì)于不同數(shù)據(jù)源的屬性中的相似語義進(jìn)行統(tǒng)一，對(duì)個(gè)性語義予以保留;最后將各個(gè)數(shù)據(jù)源的處理結(jié)果進(jìn)行連接合并。如圖1所示，本文提出的方法可以對(duì)不同的數(shù)據(jù)源進(jìn)行個(gè)性、靈活的處理，最后形成一個(gè)多維度的數(shù)據(jù)源。其中在連接合并環(huán)節(jié)本文采用了基于相似連接的數(shù)據(jù)預(yù)處理方法[8]，本文采用Jaccard系數(shù)來度量數(shù)據(jù)之間的相似性，Jaccard系數(shù)定義如（1）所示：

其中X和Y分別代表兩個(gè)集合。

對(duì)于安全分析數(shù)據(jù)而言，上述預(yù)處理模型可以通過動(dòng)態(tài)調(diào)整閾值將信息不完整、缺失嚴(yán)重、無分析價(jià)值的日志條目清洗掉，從而保證數(shù)據(jù)源的可分析性和可靠性，但由于大數(shù)據(jù)環(huán)境數(shù)據(jù)量的龐大導(dǎo)致對(duì)每一條數(shù)據(jù)據(jù)計(jì)算其Jaccard系數(shù)將耗費(fèi)大量的時(shí)間，因此在本文的第2章將重點(diǎn)介紹如何通過MapReduce框架實(shí)現(xiàn)上述預(yù)處理模型，從而提高其效率。關(guān)于相似連接算法也將在第3章設(shè)計(jì)Map函數(shù)和Reduce函數(shù)時(shí)進(jìn)行詳細(xì)介紹。

2 基于改進(jìn)的IAE-MapReduce數(shù)據(jù)聚合方法

MapReduce框架作為一個(gè)并行計(jì)算框架，能夠大幅度提高預(yù)處理算法的效率，但對(duì)網(wǎng)絡(luò)數(shù)據(jù)源的互補(bǔ)性分析而言，MapReduce框架計(jì)算過程中會(huì)產(chǎn)生大量相似的鍵值對(duì)。為了解決Map端計(jì)算結(jié)果中的鍵值對(duì)過多的問題，目前有兩種方法：一種方法是引入Combine[9]組件，將中間結(jié)果聚合，相當(dāng)于做了一小的Reduce，但這樣做將會(huì)進(jìn)行兩次I/O，系統(tǒng)開銷較大;另一種方法將Map端計(jì)算結(jié)果中的鍵值對(duì)在內(nèi)存中聚合，一次計(jì)算，一次I/O，這種方法的優(yōu)點(diǎn)是速度快，但由于Map端聚合的不足容易導(dǎo)致最終的計(jì)算結(jié)果可能和外聚合的結(jié)果不同。

針對(duì)上述問題，本文提出了一種改進(jìn)的IAE（Internal And External）-MapReduce數(shù)據(jù)聚合方法，將聚合分為兩個(gè)階段，第一個(gè)階段為測(cè)試階段;第二個(gè)階段為聚合階段。兩個(gè)階段的具體步驟如下。

2.1 測(cè)試階段

測(cè)試階段的任務(wù)是測(cè)試Map端計(jì)算后的數(shù)據(jù)是否能夠進(jìn)行內(nèi)聚合，具體做法是將要進(jìn)行計(jì)算的部分?jǐn)?shù)據(jù)通過內(nèi)聚合方法和外聚合方法計(jì)算后，比較得到的結(jié)果是否相同。因?yàn)槭褂玫臄?shù)據(jù)少，所以時(shí)間測(cè)試階段使用的時(shí)間將很短，相對(duì)于整個(gè)MapReduce的計(jì)算總時(shí)間，可以忽略不計(jì)。如圖2所示，具體步驟如下：

1）分別通過外聚合和內(nèi)聚合計(jì)算出相應(yīng)的結(jié)果。

2）比較兩個(gè)結(jié)果是否相同。

3）若相同則進(jìn)行內(nèi)聚合，若不相同則進(jìn)行外聚合。

2.2 聚合階段

1）內(nèi)聚合方法。內(nèi)聚合方法的作用是將聚合操作放置到內(nèi)存中進(jìn)行。具體步驟如下：

a）建立〈Key，Value〉倒排索引。根據(jù)讀入的〈Key，Value〉中Key值建立倒排索引，在索引中記錄〈Key，Address〉，Address為〈Key，Value〉在內(nèi)存中的地址值。

b）對(duì)Address建立指向Count的索引。為了在內(nèi)存不足時(shí)，能夠及時(shí)地將匹配次數(shù)少的〈Key，Value〉調(diào)出內(nèi)存，對(duì)Address建立匹配次數(shù)Count的索引，并對(duì)其進(jìn)行匹配，將匹配成功的〈Key，Value〉進(jìn)行合并。

c）在進(jìn)行下次匹配之前，查看內(nèi)存是否足夠，如果內(nèi)存不足夠，將內(nèi)存中Count值小的部分〈Key，Value〉寫回磁盤。如果內(nèi)存足夠，查看是否還有未計(jì)算的〈Key，Value〉：如果有未計(jì)算的〈Key，Value〉，將未計(jì)算的〈Key，Value〉調(diào)入內(nèi)存進(jìn)行計(jì)算并返回a）繼續(xù)執(zhí)行;如果沒有未計(jì)算的〈Key，Value〉則結(jié)束。

2）外聚合方法。〈Key，Value〉外聚合模塊的作用是將聚合操作放在Map端的Map函數(shù)計(jì)算完成后統(tǒng)一進(jìn)行。具體步驟如下：

a）將〈Key，Value〉調(diào)入內(nèi)存進(jìn)行計(jì)算，將計(jì)算結(jié)果寫入磁盤，記為S〈Key，Value〉。

b）將磁盤中的S〈Key，Value〉重新調(diào)回內(nèi)存，執(zhí)行內(nèi)聚合的操作。

本文提出的方法通過對(duì)Map端數(shù)據(jù)在內(nèi)存中建立索引，根據(jù)數(shù)據(jù)特點(diǎn)選擇不同的Map端數(shù)據(jù)聚合方法，減少I/O次數(shù)，同時(shí)減少了生成Mapper的數(shù)量，減少了傳輸?shù)耐ㄐ帕亢蚆apper裝載和卸載所消耗的時(shí)間。在下一部分，本文將介紹如何通過本文提出的IAE-MapReduce框架實(shí)現(xiàn)基于相似連接的預(yù)處理方法。

3 算法實(shí)現(xiàn)與性能分析

3.1 基于IAE-MapReduce的相似連接預(yù)處理算法實(shí)現(xiàn)

IAE-MapReduce框架的聚合過程中需要三個(gè)階段：測(cè)試階段、內(nèi)聚合階段、外聚合階段。其中內(nèi)聚合算法的核心部分如算法1所示。為了提升算法的效率，在進(jìn)行相似連接算法的實(shí)現(xiàn)時(shí)，使用多重集合的相似連接算法，該算法需迭代三次得出結(jié)果：第一階段得出集合中各個(gè)元素的出現(xiàn)次數(shù);第二階段分別將兩個(gè)集合聯(lián)合得出所含元素的次數(shù);最后階段根據(jù)Jaccard相似度計(jì)算公式，分別計(jì)算集合之間的相似度。其中相似連接算法的第二階段的核心部分如算法2所示。

多重集合相似連接第二階段主要完成的是對(duì)兩個(gè)集合共有特征數(shù)量的統(tǒng)計(jì)，〈〈M1，M2，c1，c2〉，〈count1，count2〉〉表示集合M1和集合M2分別有c1、c2個(gè)屬性值，而它們共有的某個(gè)屬性的個(gè)數(shù)分別為count1、count2。

3.2 實(shí)驗(yàn)結(jié)果與算法性能分析

為了驗(yàn)證本文所提出的基于IAE-MapReduce框架的相似連接預(yù)處理算法的性能，實(shí)驗(yàn)首先將預(yù)處理前后的數(shù)據(jù)集大小進(jìn)行比較，其次針對(duì)算法的效率，將本文方法與傳統(tǒng)的MapReduce方法進(jìn)行比較。

圖3顯示的是對(duì)防火墻（iptables）日志、域名系統(tǒng)（Domain Name System， DNS）日志和Snort日志進(jìn)行預(yù)處理后數(shù)據(jù)量的變化。本實(shí)驗(yàn)共采用3GB數(shù)據(jù)進(jìn)行預(yù)處理，其中約800MB為防火墻日志，約1150MB為DNS日志，約1050MB為Snort日志。使用相似連接算法對(duì)數(shù)據(jù)源進(jìn)行處理時(shí)，根據(jù)相似度的不同約簡(jiǎn)出的結(jié)果略有不同，但總體上是相似的。實(shí)驗(yàn)結(jié)果表明本文所提出的基于相似連接的預(yù)處理方法使總的數(shù)據(jù)量減小了30%左右。

4 結(jié)語

多源數(shù)據(jù)融合分析是網(wǎng)絡(luò)安全領(lǐng)域用戶行為分析預(yù)測(cè)的基礎(chǔ)，而數(shù)據(jù)清洗是其重要環(huán)節(jié)。大數(shù)據(jù)網(wǎng)絡(luò)安全分析環(huán)境下，由于數(shù)據(jù)量的龐大，導(dǎo)致傳統(tǒng)的數(shù)據(jù)清洗技術(shù)效率低，難以滿足態(tài)勢(shì)分析實(shí)時(shí)性的需求，據(jù)此本文提出了一種基于相似連接的多源數(shù)據(jù)預(yù)處理方法，并且采用改進(jìn)的IAE-MapReduce并行處理框架去實(shí)現(xiàn)該方法。最后通過實(shí)驗(yàn)驗(yàn)證本文提出的預(yù)處理方法使總的數(shù)據(jù)量減小了30%，并且相比傳統(tǒng)的MapReduce框架，效率提高了43.91%。

參考文獻(xiàn) （References）

[1] MAJIDI M， OSKUOEE M. Improving pattern recognition accuracy of partial discharges by new data preprocessing methods [J]. Electric Power Systems Research， 2015， 119： 100-110.

[2] LI G， DENG D， WANG J， et al. Pass-join： a partition-based method for similarity joins[J]. Proceedings of the VLDB Endowment， 2011， 5（3）： 253-264.

[3] WANG J， LI G， FE J. Fast-join： an efficient method for fuzzy token matching based string similarity join[C]// Proceedings of the 2011 International Conference on Data Engineering. Piscataway， NJ： IEEE， 2011： 458-469. 本文文獻(xiàn)列表存在重復(fù)現(xiàn)象，如文獻(xiàn)3與文獻(xiàn)14是同一個(gè)文獻(xiàn)，請(qǐng)作相應(yīng)調(diào)整，因?yàn)樵谡闹械囊梦墨I(xiàn)的順序是依次進(jìn)行的，所以建議將文獻(xiàn)3（或14）改為另外一條文獻(xiàn)，注意彼此間不要再重復(fù)了。

[4] 陳一帆，趙翔，何培俊，等.BMGSJoin：一種基于MapReduce的圖相似度連接算法[J].模式識(shí)別與人工智能，2015，28（5）：472-480.（CHEN Y F， ZHAO X， HE P J， et al. BMGSJoin： a MapReduce based graph similarity join algorithm [J]. Pattern Recognition & Artificial Intelligence， 2015， 28（5）： 472-480.）

[5] 陳子軍，張娟娜，劉文遠(yuǎn).MapReduce框架下基于范圍的空間文本相似連接[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36（10）：2245-2251.（CHEN Z J， ZHANG J N， LIU W Y. Range-based spatial text similarity connection under MapReduce framework[J]. Journal of Chinese Computer Systems， 2015， 36（10）： 2245-2251.）

[6] BU Y， HOWE B， BALAZINSKA M， et al. HaLoop： efficient iterative data processing on large clusters[J]. Proceedings of the VLDB Endowment， 2010， 3（1/2）： 285-296.

[7] ZHANG Y， GAO Q， GAO L， et al. iMapReduce： a distributed computing framework for iterative computation [J]. Journal of Grid Computing， 2012， 10（1）： 47-68.

[8] 榮垂田，徐天任，杜小勇.基于劃分的集合相似連接[J].計(jì)算機(jī)研究與發(fā)展，2012，49（10）：2066-2076.（RONG C T， XU T R， DU X Y. Partition-based set similarity join [J]. Journal of Computer Research and Development， 2012， 49（10）： 2066-2076.）

[9] STUART J A， OWENS J D. Multi-GPU MapReduce on GPU clusters[C]// Proceedings of the 2011 International Conference on Parallel & Distributed Processing Symposium. Piscataway， NJ： IEEE， 2011： 1068-1079.

[10] LIN F， SONG C， XU X， et al. Sensing from the bottom： smart insole enabled patient handling activity recognition through manifold learning[C]// Proceedings of the 2016 International Conference on Connected Health： Applications， Systems and Engineering Technologies. Piscataway， NJ： IEEE， 2016： 254-263.

[11] LU J， WANG G， DENG W， et al. Multi-manifold deep metric learning for image set classification[C]// Proceedings of the 2015 International Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2015： 1137-1145.

[12-7] ZHANG Y， GAO Q， GAO L， et al. iMapReduce： a distributed computing framework for iterative computation [J]. Journal of Grid Computing， 2012， 10（1）： 47-68.

[13-4] 陳一帆，趙翔，何培俊，等.BMGSJoin：一種基于MapReduce的圖相似度連接算法[J].模式識(shí)別與人工智能，2015，28（5）：472-480.（Chen Y， Zhao X， He P， et al. BMGSJoin： a MapReduce based graph similarity join algorithm [J]. Pattern Recognition & Artificial Intelligence， 2015， 28（5）： 472-480.）

[14-3] WANG J， LI G， FE J. Fast-join： an efficient method for fuzzy token matching based string similarity join[C]// Proceedings of the 2011 International Conference on Data Engineering. Piscataway， NJ： IEEE， 2011： 458-469.

[12] 劉雪莉，王宏志，李建中，等.基于實(shí)體的相似性連接算法[J].軟件學(xué)報(bào)，2015，26（6）：1421-1437.（LIU X L， WANG H Z， LI J Z， et al. Entity-based similarity join algorithm[J]. Journal of Software， 2015， 26（6）： 1421-1437.）