基于抽樣流長與完全抽樣閾值的異常流自適應(yīng)抽樣算法

伊 鵬 錢 坤 黃萬偉 王 晶 張 震

（國家數(shù)字程控交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002）

基于抽樣流長與完全抽樣閾值的異常流自適應(yīng)抽樣算法

伊 鵬 錢 坤*黃萬偉 王 晶 張 震

（國家數(shù)字程控交換系統(tǒng)工程技術(shù)研究中心 鄭州 450002）

高速IP網(wǎng)絡(luò)的流量測量與異常檢測是網(wǎng)絡(luò)測量領(lǐng)域研究的熱點。針對目前網(wǎng)絡(luò)流量測量算法對小流估計精度偏低，對異常流量篩選能力較差的缺陷，該文提出一種基于業(yè)務(wù)流已抽樣長度與完全抽樣閾值 S的自適應(yīng)流抽樣算法（AFPT）。AFPT算法根據(jù)完全抽樣閾值S篩選對異常流量敏感相關(guān)的小流，同時根據(jù)業(yè)務(wù)流已抽樣長度自適應(yīng)調(diào)整抽樣概率。仿真和實驗結(jié)果表明，AFPT算法的估計誤差與理論上界相符，具有較強(qiáng)的異常流量篩選能力，能夠有效提高異常檢測算法的準(zhǔn)確率。

網(wǎng)絡(luò)測量；自適應(yīng)流抽樣；異常檢測

1 引言

網(wǎng)絡(luò)基礎(chǔ)通信設(shè)施的大規(guī)模部署和網(wǎng)絡(luò)接入方式的開放性，使得互聯(lián)網(wǎng)成為一種高度異構(gòu)與開放的復(fù)雜系統(tǒng)［1］。通過網(wǎng)絡(luò)流量測量技術(shù)，可以幫助人們理解掌握網(wǎng)絡(luò)運行狀況，進(jìn)而優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)應(yīng)用。網(wǎng)絡(luò)上的數(shù)據(jù)報文流經(jīng)測量節(jié)點后，根據(jù)系統(tǒng)測量算法必須進(jìn)行數(shù)據(jù)壓縮［2］或者抽樣［3］以減少流量日志，并將測量流量按照一定的數(shù)據(jù)結(jié)構(gòu)格式存儲。測量過程完成后，得到的流量數(shù)據(jù)可以進(jìn)一步用于流量分布特征估計、流量計費以及異常檢測［4，5］等應(yīng)用分析。

流量測量時由于大流較小流更容易被抽樣檢測，因此大流的測量難點主要在于優(yōu)化數(shù)據(jù)存儲結(jié)構(gòu)或抽樣模型，小流由于數(shù)量的龐大性和較低的抽樣率，與大流的測量估計往往不能兼得［6］。網(wǎng)絡(luò)研究和管理者僅使用部分原始流量對網(wǎng)絡(luò)流量的異常檢測進(jìn)行分析，但由于原始流量信息的不完整性使得異常檢測算法的分析結(jié)果在準(zhǔn)確率上不可避免地存在一定偏差［7，8］。針對上述問題，一種理想的流量測量算法首先應(yīng)當(dāng)能夠為流量分布特征提供較高估計精度信息，同時對異常流量具有準(zhǔn)確的篩選抽樣能力，或者是具有能夠在測量中保留大量與異常流量敏感相關(guān)的小流數(shù)據(jù)的能力。

草圖指導(dǎo)的抽樣（Sketch Guided Sampling，SGS）算法［9］基本能夠解決上述問題，該算法抽樣保留每流（per-flow）信息，設(shè)置包抽樣率為該數(shù)據(jù)包所屬業(yè)務(wù)流當(dāng)前流量的單調(diào)遞減函數(shù)。隨機(jī)共享計數(shù)器（Randomized Counter Sharing，RCS）算法［10］是一種較好地滿足以上要求的算法，其核心思想是：從流量數(shù)據(jù)的存儲優(yōu)化出發(fā)，使用m組計數(shù)器壓縮存儲所有數(shù)據(jù)信息，將不同業(yè)務(wù)流的數(shù)據(jù)信息隨機(jī)存儲在 l（ 0 ＜ l ＜ m）組計數(shù)器內(nèi)。文獻(xiàn)［11］提出了一種基于網(wǎng)絡(luò)流長分布的自適應(yīng)抽樣（Flow Size Adaptive Sampling，F(xiàn)SAS）算法，F(xiàn)SAS通過估計異常流量的分布特征，得到異常流量的流長閾值，根據(jù)閾值對流量進(jìn)行分段抽樣，其自適應(yīng)抽樣的實質(zhì)是分段的靜態(tài)流抽樣算法。文獻(xiàn)［12］提出了一種特征感知的自適應(yīng)流抽樣（Adaptive Flow Sampling，AFS）方法，根據(jù)流量五元組特征定義了2個特征矩-特征計數(shù)和特征熵，在采樣前計算特征矩，在抽樣時一旦某一特征值出現(xiàn)頻度過高立即降低該業(yè)務(wù)流的抽樣率。

本文針對當(dāng)前流量測量算法對網(wǎng)絡(luò)流統(tǒng)計特征估計誤差偏高、對異常流量抽樣能力偏弱的問題，提出一種基于業(yè)務(wù)流抽樣流長與完全抽樣閾值S的自適應(yīng)流抽樣算法（Adaptive Flow sampling algorithm based on sampled Packets and force sampling Threshold S，AFPT）。第2節(jié)對AFPT算法的抽樣模型給出了詳細(xì)描述，并從理論上對AFPT算法的流長度無偏估計、標(biāo)準(zhǔn)差以及存儲開銷進(jìn)行了分析證明。第3節(jié)采用真實鏈路數(shù)據(jù)和模擬攻擊流量對AFPT算法進(jìn)行仿真測試，實驗結(jié)果與第2節(jié)的理論分析吻合。第4節(jié)總結(jié)全文。

2 自適應(yīng)流抽樣算法

2.1 抽樣模型

定義1 抽樣概率函數(shù) P（ s） =1/（p（ s+ 1）- p（ s）），其中抽樣函數(shù) （）p s滿足條件：

（2）p（ s）滿足 p（ 0）= 0且 p（ 1）= β，β ＞ 0，β可用于調(diào)整完全抽樣閾值S；

（3）p（ s + 1）＜ α p（ s）+ β，α＞ 1，β ＞0。

2.2 理論分析

定理1 使用AFPT算法抽樣時，原始業(yè)務(wù)流長度n的無偏估計是

證明 對于流長度真實值為n的業(yè)務(wù)流，若計數(shù)器計數(shù)值s i= ，有：

令 L（n）表示業(yè)務(wù)流長度的真實值為n時，無偏估計n（s）的期望值，則

由式（1）可得

根據(jù)定義1可得 p（ i + 1）- p（ i） = 1/P（ i ），則有

故

（2）完全抽樣閾值 S|β= S0＞ 1時，根據(jù)上述推導(dǎo)，得

若n ＞ S0，則

綜合上述推導(dǎo)定理1得證。 證畢

證明 對流長度 n ≤ S0的業(yè)務(wù)流，估計誤差始終為0。

對流長度 n ＞ S0的業(yè)務(wù)流，由 E［ p2（ s） ］=和定義1可得：

進(jìn)一步可得：

AFPT算法的標(biāo)準(zhǔn)差上界為

證畢

表1是SGS，RCS和AFPT算法的抽樣概率函數(shù)與理論標(biāo)準(zhǔn)差。圖1（a）～圖1（c）分別是3種算法的標(biāo)準(zhǔn)差對比。SGS算法和RCS算法的理論誤差相近，誤差均隨流長度的增加而減小，AFPT算法的理論誤差隨流長度的增加略有增大，但誤差最大值仍然小于0.071。

表1 理論誤差

2.3 存儲開銷

抽樣算法的主要存儲開銷集中在流長度計數(shù)器的使用上。為盡可能保留原始流量信息，抽樣算法通常采用每流抽樣模型，為每個業(yè)務(wù)流創(chuàng)建流長度計數(shù)器；在計數(shù)器的設(shè)計上，由于業(yè)務(wù)流長度的差異跨度非常大，抽樣算法為保證所有業(yè)務(wù)流的統(tǒng)計需求，必須根據(jù)最大業(yè)務(wù)流長度值確定計數(shù)器位寬。

定理3 對真實大小為n的業(yè)務(wù)流，AFPT算法計數(shù)器位寬的數(shù)學(xué)期望上界是p-1（n），其中p-1（n）是p（c）的反函數(shù)。

圖1 3種算法的理論誤差

證畢

圖2對比了SGS算法與AFPT算法所需計數(shù)器位寬，對于流長度在100以內(nèi)的小流，SGS算法和AFPT算法的計數(shù)器位寬差距較小。隨著業(yè)務(wù)流長度的增加，SGS算法的計數(shù)器位寬成對數(shù)比例增加，AFPT算法的計數(shù)器位寬趨近于10且此時已能夠滿足流長度在 107以內(nèi)的所有業(yè)務(wù)流。即使在提高完全抽樣閾值時，AFPT算法的計數(shù)器位寬仍然保持趨近于10，存儲開銷未出現(xiàn)大幅增加。與RCS算法相比，在小流與中大流計數(shù)器位寬的使用上，AFPT算法優(yōu)于RCS算法，隨著流長度的增加，AFPT算法所需的計數(shù)器位寬趨近于10略大于RCS算法。

3 仿真與結(jié)果分析

3.1 真實網(wǎng)絡(luò)流量下的仿真實驗

本文使用CAIDA［13］在2012年3月10日采集的互聯(lián)網(wǎng)實際網(wǎng)絡(luò)40 Gbps鏈路的流量數(shù)據(jù)。仿真過程中，SGS算法參數(shù)設(shè)置為 0.1ε= ，計數(shù)器位寬為14；AFPT算法抽樣概率β=1 ；RCS算法的計數(shù)器組數(shù)隨機(jī)映射計數(shù)器數(shù)目 100l= ，計數(shù)器位寬 8b= 。

AFPT算法抽樣仿真結(jié)果與標(biāo)準(zhǔn)差如圖3所示。對圖 3（b）中的標(biāo)準(zhǔn)差數(shù)據(jù)點進(jìn)行統(tǒng)計，結(jié)果如表 2所示，AFPT的標(biāo)準(zhǔn)差穩(wěn)定在0.071以內(nèi)，97.67%的數(shù)據(jù)點誤差范圍在 0.071以內(nèi)，個別小流的標(biāo)準(zhǔn)差稍大于0.07但原始流量的整體誤差仍然小于0.5。隨著業(yè)務(wù)流長度的增加，標(biāo)準(zhǔn)差完全落在區(qū)間［0，0.071］以內(nèi)，這與定理2的標(biāo)準(zhǔn)差理論上界保持一致。

表2 3種算法標(biāo)準(zhǔn)差的區(qū)間比例

圖4是SGS算法的流長度估計值與標(biāo)準(zhǔn)差，估計誤差顯著高于AFPT算法。盡管大流的估計誤差較低，但小流的估計誤差是AFPT的數(shù)十倍以上。由于SGS使用哈希引入了誤判誤差，SGS的標(biāo)準(zhǔn)差在0.1以上的比例超過了17.36%，且小流的估計精度差于AFPT，標(biāo)準(zhǔn)差上界較AFPT高出約30%。

RCS算法的流長度估計值與標(biāo)準(zhǔn)差如圖 5所示。與SGS相比，RCS對小流的標(biāo)準(zhǔn)差較大，當(dāng)業(yè)務(wù)流長度達(dá)到100左右時標(biāo)準(zhǔn)差基本穩(wěn)定在1以內(nèi)，且快速降低趨近于0。RCS約81.28%的標(biāo)準(zhǔn)差在0.3以內(nèi)，稍差于SGS。而AFPT仿真結(jié)果的標(biāo)準(zhǔn)差僅在0.01以內(nèi)的比例就高達(dá)99.85%，且AFPT算法的標(biāo)準(zhǔn)差基本落在0.071以內(nèi)，誤差上界較RCS降低約76.3%。

圖2 報文抽樣與AFPT算法需要的計數(shù)器位數(shù)

圖3 AFPT算法仿真結(jié)果

圖4 SGS算法仿真結(jié)果

3.2 異常流量下的仿真實驗

在DoS、端口掃描或者蠕蟲攻擊等網(wǎng)絡(luò)攻擊下會使網(wǎng)絡(luò)鏈路產(chǎn)生大量的小流，抽樣測量時如果能夠?qū)@些小流盡可能地抽樣就可以獲得更多的異常流量數(shù)據(jù)，為異常檢測算法的準(zhǔn)確率提供更加可靠的保證。由于不同類型攻擊流的流長并沒有相關(guān)的明確定義，綜合考慮存儲資源的消耗，本文選擇設(shè)置完全抽樣閾值 50S= 以滿足大多數(shù)攻擊流都可被抽樣，實際閾值的設(shè)置視需求而定。

AFPT的抽樣概率函數(shù)P（s）值取決于α與β，對于不同的取值組合 （）P s可能出現(xiàn)大于1的情況。對P（s）取值大于1的概率點，均以概率1進(jìn)行完全抽樣。若取β∈［0，1］間任意值，可調(diào)整完全抽樣閾值S，將需要深入研究的業(yè)務(wù)流全部保留，僅對流長度超過閾值S的業(yè)務(wù)流進(jìn)行抽樣測量。圖 6是 α= 1.01時，完全抽樣閾值隨β的變化曲線。

圖7（a）是SGS，RCS和AFPT這3種算法對合成流量的測量仿真結(jié)果，SGS和RCS算法的參數(shù)設(shè)置與3.1節(jié)的仿真實驗一致，AFPT算法取完全抽樣閾值。異常流量的合成采用文獻(xiàn)［14］提出的構(gòu)造方法，基于實驗中使用的正常情況下網(wǎng)絡(luò)數(shù)據(jù)流量和DARPA入侵檢測流量［15］，模擬異常流量的攻擊強(qiáng)度為每秒30000包，其中異常流量比例約20.8%，攻擊流量在100 s，200 s，300 s時逐漸達(dá)到60%。

SGS的異常流量抽樣比例接近于 0.7，最差約0.4。由于 RCS對所有數(shù)據(jù)報文采用了數(shù)據(jù)壓縮方式存儲，對異常流量的抽樣原則僅與壓縮率有關(guān)，比例值穩(wěn)定在 0.8左右，即使在過渡壓縮數(shù)據(jù)信息時的抽樣比例降低至約 0.6，仍優(yōu)于 SGS。AFPT通過設(shè)置完全抽樣閾值，抽樣比例顯著優(yōu)于SGS和RCS，比例值穩(wěn)定在1.00左右，在攻擊流量較為集中時也能夠保證抽樣比例不小于 0.75，基本實現(xiàn)對異常流量的逐包抽樣統(tǒng)計。

AFPT與AFS，F(xiàn)SAS算法的比較結(jié)果如圖7（b）所示，其中，F(xiàn)SAS的參數(shù)設(shè)置為：大中小流閾值分別是1000，500，50，抽樣概率分別是0.01，0.10，0.20。由于 FSAS需要在抽樣的同時估計業(yè)務(wù)流長度，極其耗費計算資源，因此在攻擊強(qiáng)度增大時，對小流的估計偏差也相應(yīng)增大，導(dǎo)致其抽樣性能下降非常明顯。AFS的抽樣效果略差于AFPT，這是由于 AFS的特征矩是根據(jù)流五元組特征信息定義的，而抽樣攻擊流量中的Probe與U2R等攻擊流僅僅依靠這些特征信息是不夠的。

4 結(jié)束語

圖5 RCS算法仿真結(jié)果

圖6 完全抽樣閾值S的變化曲線

圖7 異常流量抽樣比例

高速 IP網(wǎng)絡(luò)的流量測量在抽樣與異常檢測之間，一直存在由于抽樣導(dǎo)致的異常檢測偏差。本文提出一種可設(shè)置完全抽樣閾值的抽樣算法，在對網(wǎng)絡(luò)業(yè)務(wù)流抽樣估計原始流量分布特征的同時，將與異常流量敏感相關(guān)的小流完全抽樣，使得異常檢測處理的流量數(shù)據(jù)中包含了至少 75%以上的異常流量，有助于提高檢測算法的準(zhǔn)確率。該算法將抽樣流量的估計誤差上界降低了30%以上，在存儲開銷上降低了對計數(shù)器位寬的需求，與其他每流測量算法相比所需的存儲開銷基本持平并未明顯增加。通過實驗仿真的進(jìn)一步驗證，該算法完全能夠適用于40 Gbps速率的骨干鏈路，對大型骨干網(wǎng)絡(luò)的管理規(guī)劃具有重要意義。

［1］ Zhou Ai-ping，Cheng Guang，and Guo Xiao-jun. High-speed network traffic measurement method［J］. Journal of Software，2014，25（1）：135-153.

［2］ Peter Lieven and Bj?rnScheuermann. High-speed per-flow traffic measurement with probabilistic multiplicity counting［C］. Proceedings of the INFOCOM 2010，San Diego，CA，USA，2010：1-9.

［3］ Cheng Guang and Tang Yong-ning. Estimation algorithms of the flow number from sampled packets on approximate approaches［J］. Journal of Software，2013，24（2）：255-265.

［4］ Lee Y J，Yeh Y R，and Wang Y C F. Anomaly detection via online oversampling principal component analysis［J］. IEEE Transactions on Knowledge and Data Engineering，2013，25（7）：1460-1470.

［5］ Pham D S，Venkatesh S，Lazarescu M，et al.. Anomaly detection in large-scale data stream networks［J］. Data Mining and Knowledge Discovery，2014，28（1）：145-189.

［6］ Cai Yuan-jun，Wu Bin，Zhang Xin-wei，et al.. Flow identification and characteristics mining from internet traffic with hadoop［C］. Proceedings of the Computer Information and Telecommunication Systems （CITS），Jeju Island，Korea，2014：1-5.

［7］ Brauckhoff D，Tellenbach B，Wagner A，et al.. Impact of packet sampling on anomaly detection metrics［C］. Proceedings. of the 6th ACM Sigcomm conference on Internet measurement，Rio de Janeiro，Brazil，2006：159-164.

［8］ Mai Jian-ning，Chuah C N，Sridharan A，et al.. Is sampled data sufficient for anomaly detection？［C］. Proceedings of the 6th ACM Sigcomm Conference on Internet Measurement，Rio de Janeiro，Brazil，2006：165-176.

［9］ Kumar A and Xu J. Sketch guided sampling using on-line estimates of flow size for adaptive data collection［C］. Proceedings of IEEE INFOCOM 2006，Barcelona，Spain，2006：1-11.

［10］ Li Tao and Chen Shi-gang. Per-flow traffic measurement through randomized counter sharing［J］. IEEE ACM Transactions on Networking，2012，13（5）：325-336.

［11］ 王蘇南. 高速復(fù)雜網(wǎng)絡(luò)環(huán)境下異常流量檢測技術(shù)研究［D］. ［博士論文］，信息工程大學(xué)，2012：38-49.

Wang Su-nan. Research on anomaly detection technology in high-speed complex network environment［D］. ［Ph.D. dissertation］，The PLA Information Engineering University，2012：38-49.

［12］ 郭通. 基于自適應(yīng)流抽樣測量的網(wǎng)絡(luò)異常檢測技術(shù)研究［D］.［博士論文］，信息工程大學(xué)，2013：38-49.

Guo Tong. Research on network anomaly detection technology based on adaptive flow sampling measurement［D］.［Ph.D. dissertation］，The PLA Information Engineering University，2013：38-49.

［13］ CAIDA. Cooperative as-sociation for internet data analysis［OL］. http：//www.caida.org/data，2012.

［14］ Lakhina A，Crovella M，and Diot C. Mining anomalies using traffic feature distributions［C］. Proceedings of the 5th ACM Sigcomm Conference on Internet Measurement，Philadelphia，PA，USA，2005：217-228.

［15］ MIT Lincoln Laboratory. DARPA Intrusion Detection Evaluation［OL］. http：//www.ll.mit.edu/mission/communications/ist/corpora/ideval/data/index.html，1999.

伊 鵬： 男，1977年生，副教授，博士，研究方向為寬帶信息網(wǎng)絡(luò).

錢 坤： 男，1990年生，碩士生，研究方向為寬帶信息網(wǎng)絡(luò)、網(wǎng)絡(luò)測量、異常流檢測.

黃萬偉： 男，1979年生，講師，博士，研究方向為寬帶信息網(wǎng)絡(luò).

王 晶： 女，1980年生，講師，博士生，研究方向為可重構(gòu)網(wǎng)絡(luò)與網(wǎng)絡(luò)測量技術(shù).

張 震： 男，1985年生，講師，博士，研究方向為網(wǎng)絡(luò)測量技術(shù).

Adaptive Flow Sampling Algorithm Based on Sampled Packets and Force Sampling Threshold S Towards Anomaly Detection

Yi Peng Qian Kun Huang Wan-wei Wang Jing Zhang Zhen

（National Digital Switching System Engineering Technological R&D Center， Zhengzhou 450002， China）

The network traffic measurement and anomaly detection for high-speed IP network become the hotspot research of network measurement field. Because the current measurement algorithms have large estimation error for the mice flows and poor performance for the sampling anomaly traffic，an Adaptive Flow sampling algorithm based on the sampled Packets and force sampling Threshold S （AFPT） is proposed. According to the force sampling threshold S，the AFPT is able to sample the mice flows which is sensitive to the anomaly traffic，while adaptive adjustment the probability of sampling based on the sampled packets. The simulation and experimental results show that the estimation error of AFPT is consistent with the theoretical upper bound，and provide better performance for the anomaly traffic sampled. The proposed algorithm can effectively improve the accuracy of anomaly detection algorithm.

Network measurement；Adaptive flow sampling；Anomaly detection

TP393

A

1009-5896（2015）07-1606-06

10.11999/JEIT141379

2014-10-29收到，2015-01-13改回，2015-05-11網(wǎng)絡(luò)優(yōu)先出版

國家973計劃項目（2012CB315901，2013CB329104）資助課題

*通信作者：錢坤 qiank126@126.com