網絡安全監控數據流的查詢優化方法

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

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

網絡安全監控數據流的查詢優化方法

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

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

本文針對網絡安全監控數據流中的查詢機制進行了研究，采用了一種以流數據方作為物化共享中間結果的方法，研究流數據方在內存中的壓縮存儲。實驗通過兩種流數據方存儲結構StreamQCTree-D和QC-Tree，驗證了采用動態物化方案的StreamQCTree相對QC-Tree在降低部分查詢性能獲得較高的數據壓縮率，進一步驗證了數據壓縮對多查詢優化的有效性。

數據流;網絡安全;數據壓縮;查詢優化

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

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

1 數據流多查詢優化

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

圖1 數據流多查詢優化Fig.1 Multiple query optimization in data stream

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

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

1）壓縮時去除數據方冗余;

3）有針對性的預計算數據流上的查詢。

2 流數據方壓縮結構

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

本文針對實時數據流分析需求提出數據流系統生成流數據方的實現框架，并實現壓縮流數據方結構StreamQCTree[6]，以及其更新和查詢算法

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

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

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

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

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

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

3 物化結點的選擇

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

3.1 成本計算

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

3.2 收益計算

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

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

4 壓縮流數據方的更新與查詢

4.1 StreamQCTree更新算法

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

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

4.2 StreamQCTree查詢算法

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

5 實驗

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

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

圖2 內存空間占用對比Fig.2 The memory space occupied by contrast

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

6 結論

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

[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:一種流數據方壓縮結構[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—），女，山東鄆城人，碩士研究生，講師。研究方向飛：計算機應用。