网络安全监控数据流的查询优化方法

任 颖 、李华伟 ，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—），女，山东郓城人，硕士研究生，讲师。研究方向飞：计算机应用。