任 穎 、李華偉 ，2、趙 媛 ，呂海燕

（1.海軍航空工程學院 山東 煙臺 264000；2.山東商務職業(yè)學院 山東 煙臺 264000）

網(wǎng)絡安全監(jiān)控數(shù)據(jù)流的查詢優(yōu)化方法

任 穎1、李華偉1，2、趙 媛1，呂海燕1

（1.海軍航空工程學院 山東 煙臺 264000；2.山東商務職業(yè)學院 山東 煙臺 264000）

本文針對網(wǎng)絡安全監(jiān)控數(shù)據(jù)流中的查詢機制進行了研究，采用了一種以流數(shù)據(jù)方作為物化共享中間結(jié)果的方法，研究流數(shù)據(jù)方在內(nèi)存中的壓縮存儲。實驗通過兩種流數(shù)據(jù)方存儲結(jié)構(gòu)StreamQCTree-D和QC-Tree，驗證了采用動態(tài)物化方案的StreamQCTree相對QC-Tree在降低部分查詢性能獲得較高的數(shù)據(jù)壓縮率，進一步驗證了數(shù)據(jù)壓縮對多查詢優(yōu)化的有效性。

數(shù)據(jù)流;網(wǎng)絡安全;數(shù)據(jù)壓縮;查詢優(yōu)化

近年來，信息處理技術(shù)的應用領(lǐng)域得到了廣泛拓展，各種網(wǎng)絡安全威脅也越來越多，對網(wǎng)絡進行以安全為目的的監(jiān)控并對監(jiān)控數(shù)據(jù)進行分析，具有重要的現(xiàn)實意義。網(wǎng)絡安全監(jiān)控產(chǎn)生了海量、持續(xù)、快速的數(shù)據(jù)。采用數(shù)據(jù)流處理技術(shù)可以持續(xù)、快速地分析實時數(shù)據(jù)，因而數(shù)據(jù)流處理技術(shù)成為數(shù)據(jù)庫研究領(lǐng)域的又一熱點[1]。

大規(guī)模網(wǎng)絡安全監(jiān)控流數(shù)據(jù)處理系統(tǒng)在管理和分析安全監(jiān)控時，多個系統(tǒng)將同時登陸系統(tǒng)，并產(chǎn)生大量查詢，而每個查詢分別處理，這種查詢方式是低效的[2]。多個查詢可能共享相同的子任務，通過多查詢優(yōu)化可提高用戶查詢效率、降低系統(tǒng)計算開銷。多查詢優(yōu)化一般采用兩類方法：優(yōu)化查詢計劃和物化共享中間結(jié)果。本文針對數(shù)據(jù)流中的查詢處理機制進行了深入的研究，提出了一種以流數(shù)據(jù)方作為物化共享中間結(jié)果的方法，研究流數(shù)據(jù)方在內(nèi)存中的壓縮存儲，優(yōu)化系統(tǒng)存儲效率以便保存更多的中間結(jié)果。

1 數(shù)據(jù)流多查詢優(yōu)化

給定查詢集Q=｛Q1, …,Qq｝由復雜 SQL查詢 Q1…,Qq組成，并包含關(guān)系集R1…,Rr，每個查詢Qi為該關(guān)系屬性集合的子集。用表示關(guān)系Ri中元組數(shù)。數(shù)據(jù)流查詢處理引擎只允許順序、單遍掃描數(shù)據(jù)流表R1…,Rr，并且不能再次讀取。采用物化共享中間結(jié)果的多查詢優(yōu)化技術(shù)，將多個查詢共享的子表達式計算機結(jié)果緩存于內(nèi)存中以便于多個查詢的多次讀取，適合于數(shù)據(jù)流單遍掃描數(shù)據(jù)的特征，同時提高查詢效率。物化共享中間結(jié)果的多查詢優(yōu)化技術(shù)系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 數(shù)據(jù)流多查詢優(yōu)化Fig.1 Multiple query optimization in data stream

壓縮物化中間結(jié)果存儲于內(nèi)存中重復使用，隨著查詢時間窗口不斷增大，存儲占用空間隨之提高。有限的內(nèi)存空間無法滿足不斷增大的存儲需求，壓縮物化共享中間結(jié)果的方法可以較好的解決這一問題。

將多查詢集中所有查詢限定為聚集查詢時，物化中間結(jié)果可以映射為部分流數(shù)據(jù)方。較好的流數(shù)據(jù)方壓縮方法應盡量滿足 個條件：

1）壓縮時去除數(shù)據(jù)方冗余;

3）有針對性的預計算數(shù)據(jù)流上的查詢。

2 流數(shù)據(jù)方壓縮結(jié)構(gòu)

選擇適當?shù)牧鲾?shù)據(jù)方壓縮結(jié)構(gòu)可以在相同容量的內(nèi)存保存更多的信息。目前有多種壓縮結(jié)構(gòu)如QC-tree[4]、Dwarf[5]等，這些壓縮結(jié)構(gòu)都是針對靜態(tài)數(shù)據(jù)的完全物化數(shù)據(jù)方。而動態(tài)數(shù)據(jù)的流數(shù)據(jù)方存儲于內(nèi)存中，動態(tài)數(shù)據(jù)是持續(xù)產(chǎn)生、無限的，在有限的內(nèi)存空間中無法容納整個完全物化的數(shù)據(jù)方壓縮結(jié)構(gòu)，只能存儲一定時間內(nèi)的流數(shù)據(jù)方切片；為了在內(nèi)存中保存更多的流數(shù)據(jù)方切片，需進一步減小單個切片的容量。

本文針對實時數(shù)據(jù)流分析需求提出數(shù)據(jù)流系統(tǒng)生成流數(shù)據(jù)方的實現(xiàn)框架，并實現(xiàn)壓縮流數(shù)據(jù)方結(jié)構(gòu)StreamQCTree[6]，以及其更新和查詢算法

定義 1StreamQCTree StreamQCTree類似于 QC-Tree，除以下性質(zhì)：

1）StreamQCTree中根結(jié)點root直接用邊連接每個時間維time結(jié)點。每個時間維結(jié)點包括一個QC-Tree子樹，該子樹對應數(shù)據(jù)方時間切片SCti。

2）StreamQCTree中包含所有基本上界類，并選擇添加部分附加上屆類。

3）在StreamQCTree中每個結(jié)點包含一個附加值cost，表示檢索結(jié)點的成本。對于物化結(jié)點，成本為1；非物化結(jié)點，表示為在聚集查詢時，訪問其后續(xù)結(jié)點的時間。

4）所有的非物化結(jié)點不存儲其度量值。

“我在這里聞一種氣味，它們發(fā)生在泥土里面。整整一早晨我都在干這件事。要不是這些霧……玉蘭花的每一個瓣兒里……還有那些胖胖的地蠶。……”

3 物化結(jié)點的選擇

定義2物化結(jié)點選擇問題[7]給定一個數(shù)據(jù)庫模式R、約束條件T、查詢集合Q和成本評估函數(shù)C，物化結(jié)點的選擇問題就是在R之上選擇一個物化結(jié)點集合V，使得V中的物化結(jié)點滿足條件T情況下代價C(R,V,Q)最小化。

3.1 成本計算

設(shè)指針存儲占P，維標記存儲占La，度量值存儲占Me，其后續(xù)結(jié)點數(shù)為cost。如果增加一個附加上界類，將增加存儲空間為

3.2 收益計算

對于任意附加上界UBi，若在查詢集中訪問UBi在樹中結(jié)點概率 Pubi，已物化 UBi的訪問次數(shù)為Cm(UBi)，未物化 UBi的訪問次數(shù)為Cum(UBi)。物化上界UBi的收益率為Bubi：

Bubi是個對比值，可以評價UBi相對于其他上界的物化收益，以評價并選擇最佳的附加上界類物化，達到最低的平均查詢響應時間。

4 壓縮流數(shù)據(jù)方的更新與查詢

4.1 StreamQCTree更新算法

StreamQCTree使用時間片數(shù)據(jù)方模型。更新算法中，數(shù)據(jù)流不斷到達，因為每個時間間隔△t將生成一個該數(shù)據(jù)方時間切片的QC-Tree子樹。更新只需要將該Ti時間的子樹添加到StreamQCTree中的Root結(jié)點。

刪除只有一種情況，當時刻Ti數(shù)據(jù)方時間切片在內(nèi)存中過期，將該子樹從內(nèi)存中刪除。只要將該QC-Tree子樹內(nèi)存釋放并去掉Root指向子樹的指針。

4.2 StreamQCTree查詢算法

查詢算法類似于QC-Tree的查詢算法，因為部分結(jié)點未物化，所以在查詢涉及到未物化結(jié)點時會產(chǎn)生查詢異常。在定位查詢異常之后，根據(jù)異常所處樹的層次i來確定第i-1層需要訪問的樹中基本上界類結(jié)點，即函數(shù) traverBUB()。

5 實驗

實驗中算法采用VC++6.0實現(xiàn)，運行環(huán)境是安裝Windows XP Professional的PC，硬件配置為160G硬盤，2G內(nèi)存。假定數(shù)據(jù)流上的元組在時間維上是均勻分布的。數(shù)據(jù)共有6個維度，每個維度的基數(shù)均為100，數(shù)據(jù)方時間窗口W=10，Zipf(factor=1.2),每個時刻有100k個新元組到達，總共分配200M內(nèi)存空間，每個時間片分配內(nèi)存10M。實驗采用了兩種流數(shù)據(jù)方存儲結(jié)構(gòu)StreamQCTree-D和 QC-Tree，StreamQCTree-D采用動態(tài)選擇方案StreamQCTree。

實驗結(jié)果驗證了StreamQCTree的壓縮方法的有效性，如圖2所示，StreamQCTree相對QC-Tree進一步壓縮了內(nèi)存占有空間。StreamQCTree-D采用了動態(tài)選擇方案選擇部分物化樹結(jié)點，該方案物化查詢頻率最高的樹中結(jié)點，盡量裁剪查詢頻率低或未查詢到得樹結(jié)點，相對QC-Tree的查詢響應時間差距較小，降低較小查詢性能，如圖3所示。

圖2 內(nèi)存空間占用對比Fig.2 The memory space occupied by contrast

圖3 查詢響應時間對比Fig.3 The query response time by contrast

6 結(jié)論

本文采用了一種以流數(shù)據(jù)方作為物化共享中間結(jié)果的方法，實驗通過兩種流數(shù)據(jù)方存儲結(jié)構(gòu)StreamQCTree-D和QC-Tree，通過實驗結(jié)果驗證了采用動態(tài)物化方案的StreamQCTree相對QC-Tree在降低部分查詢性能獲得較高的數(shù)據(jù)壓縮率，進一步驗證了數(shù)據(jù)壓縮對多查詢優(yōu)化的有效性。

[1]Chien J T,Wu C C.Discriminant waveletfaces and nearest feature classifiers for face recognition [J].IEEE Trans.on PAMI,2002,24(12):1644-1649.

[2]ZHENG Wen-ming,ZOU Cai-rong,ZHAO Li.Face Recognition using two novelnearestneighborclassifiers[C]//Proceedings of ICASSP,2004:725-728.

[3]Roy P,Seshadri S,Sudarshan S,et al.Efficient and Extensible algorithms for multi query optimization[C].//Proceedings of the 19th ACM SIGMOD InternationalConference on Management of Data,2000:249-260.

[4]Lakshmanan LVS,PEI Jian,ZHAN Yan.QC-trees:An efficient summary structure for semantic OLAP[C].//Proc of the 2003 ACM SIGMOD International Conference on Management of Data,2003:64-75.

[5]Sismanis Y,Deligiannakis A,Roussopoulos N,et al.Dwarf shrinking the petacube[C].//Proc of the 2002 ACM-SIGMOD international conference management of data,2002:464-475.

[6]甘亮，劉東紅，賈焰，等.StreamQCTree:一種流數(shù)據(jù)方壓縮結(jié)構(gòu)[J].計算機工程與應用，2011:62-65.

GAN Liang,LIU Dong-hong,JIA Yan,et al.StreamQCTree:A stream data compression structure[J].Computer engineering and Applications,2011:62-65.

[7]Harinarayan V,Rajaraman A,Ullman J D.Implementing data cubes efficiently [C]//Proc of the 1996 ACM SIGMOD International Conference on Management of Data,1996:205-216.

Query optimum scheduling strategy on network security monitoring data streams

REN Ying1,LI Hua-wei1,2,ZHAO Yuan1,LV Hai-yan1
（1.Naval Aeronautical and Astronautical University,Yantai 264000,China;2.Shandong Businss Institute，Yantai 264000,China）

This thesis studies on the query mechanism of network security monitoring datastreams,and researchs storage flow data in memory adopting a method of using flow data as materialized sharing intermediate results of compression.Through the experiments of two kinds of flow data storage structure of StreamQCTree-D and QC-Tree,confirmed the dynamic scheme of StreamQCTree relative to QC-Tree in the lower part of the query performance to get higher data compression rate,further validation of the data compression of multiple query optimization is effective.

data strean;network security;data compression;query optimum

TP311.13

A

1674-6236（2014）13-0028-03

2013-06-26 稿件編號：201306169

任 穎（1979—），女，山東鄆城人，碩士研究生，講師。研究方向飛：計算機應用。