当前位置：文档之家 › 基于模型检测的数据流异常测试技术研究

基于模型检测的数据流异常测试技术研究

  • 格式：pdf
  • 大小：338.46 KB
  • 文档页数：4

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　

＠博士论坛＠　

基于模型检测的数据流异常测试技术研究　

陈涛　，许金超　，钮俊　

ＣＨＥＮ　Ｔａｏ　’　～，ＸＵ　Ｊｉｎｃｈａｏ　一，ＮＩＵ　Ｊｕｎ　’　

１同济大学计算机科学与技术系，上海２０１８０４　

２周家高性能计算机工程技术中心同济分中心，上海２０１８０４　３．安徽财经大学计算机科学与技术系，安徽蚌埠２３３０３０　

１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｔｏｎ￣ｉ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ　２０１８０４，Ｃｈｉｎａ　２．Ｔｏｎｇｊｉ　Ｂｒａｎｃｈ。Ｎａｔｉｏｎａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ＆Ｔｅｃｈｎｏｌｏｇｙ　Ｃｅｎｔｅｒ　ｏｆ　Ｈｉｇｈ　Ｐｅｒｆｏｒｍａｎｃｅ　Ｃｏｍｐｕｔｅｒ，Ｓｈａｎｇｈａｉ　２０１８０４，Ｃｈｉｎａ　３．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ａｎｈｕｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｆｉｎａｎｃｅ＆Ｅｃｏｎｏｍｉｃｓ，Ｂｅｎｇｂｕ，Ａｎｈｕｉ　２３３０３０，Ｃｈｉｎａ　

ＣＨＥＮ　Ｔａｏ，ＸＵ　Ｊｉｎｃｈａｏ，ＮＩＵ　Ｊｕｎ．Ｄａｔａ　ｆｌｏｗ　ａｎｏｍａｌｙ　ａｎａｌｙｓｉｓ　ｂａｓｅｄ　ｏｎ　ｍｏｄｅｌ　ｃｈｅｃｋｉｎｇ．Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐ－　

ｐｌｉｃａｆｉｏｎｓ，２０１１，４７（２５）：１－４．　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｅｘｅｃｕｔｉｏｎ　ｏｆ　ｐｒｏｇｒａｍ　ｅｍｂｏｄｉｅｓ　ｆｌｏｗｓ　ｏｆ　ｄａｔａ　ｉｎ　ｖａｉｌａｂｌｅ．Ａ　ｎｏｖｅｌ　ｍｅｔｈｏｄ　ｉＳ　ｐｒｏｐｏｓｅｄ　ｔｏ　ｄｅｔｅｃｔ　ｄａｔａ　ｆｌｏｗ　

ａｎｏｍａｌｙ　ｉｎｃｌｕｄｉｎｇ　ｖａｒｉａｂｌｅ　ｕｎｄｅｆｉｎｅｄ　ｏｒ　ｄｅｆｉｎｅｄ　ｂｕｔ　ｎｏｔ　ｒｅｆｅｒｅｎｃｅｄ　ｏｒ　ｍｕｌｔｉ—ｕｓｅｄ．Ｔｈｅ　ｔｒｕｓｔ　ｐａＲｅｍ　ｏｆ　ｐｒｏｇｒａｍ　ｉｓ　ｄｅｆｉｎｅｄ　

ａｎｄ　ｐｒｏｇｒａｍ　ｉｓ　ｔｒａｎｓｌａｔｅｄ　ｉｎｔｏ　ｆｉｎｉｔｅ　ｓｔａｔｅ　ｍａｃｈｉｎｅ．Ｂａｓｅｄ　ｏｎ　ＡＬＣＣＴＬ　ｔｅｍｐｏｒａｌ　ｌｏｇｉｃ　ａｎｄ　ｍｏｄｅｌ　ｃｈｅｃｋｉｎｇ．ｖｅｒｉｆｉｃａｔｉｏｎ　ｍｏｄｅｌ　

ｓａｔｉｓｆｉｅｓ　ｔｈｅ　ｔｒｕｓｔ　ｐａＲｅｒｎ　ｄｅｆｉｎｅｄ．Ｅｘｐｅｒｉｍｅｎｔ　ｓｈｏｗｓ　ｔｈａｔ　ｔｈｉｓ　ｍｅｔｈｏｄ　ｉｓ　ｅｆｆｅｃｔｉｖｅ　ａｎｄ　ｈａｓ　ｂｅｅｎ　ｉｍｐｌｅｍｅｎｔｅｄ　ｉｎ　ａ　ｄｅｆｅｃｔ－ｏｒｉｅｎｔ—　

ｅｄ　ｔｅｓｔｉｎｇ　ｓｙｓｔｅｍ．　Ｋｅｙ　ｗｏｒｄｓ：ｖａｒｉａｂｌｅ　ｒｅｆｅｒｅｎｃｅｄ；ｓｏｆｔｗａｒｅ　ｔｅｓｔｉｎｇ；ｄａｔａ　ｆｌｏｗ　ａｎｏｍａｌｙ；ｍｏｄｅｌ　ｃｈｅｃｋｉｎｇ　

摘要：程序的执行体现为数据在变量中的流动。对Ｃ／Ｃ＋＋源代码中变量定义使用情况进行分析，针对变量未赋值就使用、变量　重复赋值和变量定义后未使用三种数据流异常情况，使用程序阅读自动机，把程序转换为变量状态机，使用ＡＬＣＣＴＬ时序逻辑和　

模型检验工具，验证程序是否满足定义的可信模式。提出了新的静态查找变量使用故障的方法。该方法已应用于面向故障的软　

件测试系统中。　

关键词：变量使用；软件测试；数据流异常；模型检测　

ＤＯＩ：１０．３７７８￣．ｉｓｓｎ．１００２．８３３１．２０１１．２５．００１　文章编号：１００２．８３３１（２０１１）２５．０００１．０４　文献标识码：Ａ　中图分类号：ＴＰ３１１．５　

１引言　

伴随着云计算和物联网时代的到来，计算机给人类发展　

带来了更多的惊喜，人们越来越依赖于计算机。同时，由于软　件错误，计算机也让人类付出巨大甚至惨重的代价，如导致飞　

机失事、空间飞行器任务失败等各种灾难。为了让软件能正　

确运行，在过去的十几年里科学家们进行了不懈的努力和研　

究，比如采用软件测试技术暴露软件的错误，采用软件调试技　术对故障进行定位并改正，遗憾的是这些方法只能表明故障　

存在，而不能证明故障不存在。因此人们发展了形式化方法，　

如定理证明和模型检验　】，试图从理论上来证明一个程序是无　

误的。但由于状态爆炸等原因，形式化方法主要应用在嵌入　

式等一些小型软件上，离实用程度还很远。　找出程序的所有错误是不可判定的　。在大型软件开发　中，采用软件测试技术来保证软件的开发质量得以首要应用，　

成为当前保证软件质量的主力军。软件测试以发现和消除软　

件内部隐藏的故障为中心，以提高软件质量为目的。软件测　试的方法很多，根据测试时程序是否运行，可分为静态测试和　

动态测试。动态测试，是需要输入相应的测试数据，运行程　

序，检查实际输出结果和预期结果是否相符。动态测试在测　

试时需要执行程序，不能在早期阶段实施。静态测试是指不　

实际运行被测软件，通过对需求文件、设计文件及源程序的阅　

读和分析找出其中的错误或可疑之处。实践表明，大约３０％～　

７０％的逻辑设计错误和编码错误可以通过静态测试分析得　

出。静态测试通过分析或检查源程序的方法、结构、过程、接　

口等来检查程序的正确性，可以在软件开发生命周期的早期　进行，把错误消除在“萌芽”阶段，可以节省大量的开发时间和　

基金项目：国家自然科学基金（ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｍａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．９０７１８０１５）；国家高技术研究发展计划（８６３）　（Ｎｏ．２００７ＡＡ０１Ｚ４２５，Ｎｏ．２００９ＡＡ０１２２０１）；国家重点基础研究发展规￣Ｊ（９７３）（Ｎｏ．２００７ＣＢ３１６５０２）；ＮＳＦＣ一微软亚洲研究院联合资助项　目（Ｎｏ．６０９７０１５５）；教育部博士点基金项目（Ｎｏ．２００９００７２１１００３５）；上海市优秀学科带头人计划项目（Ｎｏ．１０ＸＤ１４０４４００）；高效能服务器　和存储技术国家重点实验室开放基金项目（Ｎｏ．２００９ＨＳＳＡ０６）；安徽省自然科学基金（Ｎｏ．１１０４０６０６Ｍ１５１）。　作者简介：陈涛（１９７２一），男，博士研究生，副教授，ＣＣＦ学生会员，主要研究方向为并行计算和模型检测；许金超（１９８４一），男，博士研究生；钮俊　

（１９７６一），男，博士研究生。Ｅ－ｍａｉｌ：９ｅｈｅｎ＠ｔｏｎｇｊｉ．ｅｄｕ．ｅｎ　

收稿Ｂ期：２０１１－０１—２６；修回日期：２０１１－０５－３１

　２　ｃ０，印础　西７ｇｊ　ｒｆ增口　，ｆｃ日，ｆ０　计算机工程与应用　

成本。静态测试包括代码检查、静态分析两种途径。它可以　

由人工进行，充分发挥人的逻辑思维优势，也可以借助软件工　

具自动进行。代码检查包括桌面检查、代码审查、代码走查和　技术评审等。主要检查代码的设计是否一致性、代码是否遵　

循标准性和可读性、代码的逻辑表达是否正确性、以及代码结　

构是否合理性等。静态分析则是一种计算机辅助的静态分析　

方法。主要对程序进行控制流分析、数据流分析　、接口分析　

和表达式分析等。　程序的执行体现为数据的流动。目前，一个很有意思且　

很有前景的辅助性方法是通过数据流分析技术静态地定位错　

误　。数据流分析可以在所有可能的执行路径上找到错误，而　

且不用等到软件全部完成就可以进行测试。数据流测试目前　

主要集中在检测内存泄漏　、基于变量使用　如变量定义未使　

用　、变量未初始化赋值ｉｓ］等方面的研究，主要采用以语法树和　

控制流图的对变量的赋值和使用情况进行跟踪来查找数据流　的使用异常。本文结合软件测试和模型检验技术，另辟蹊径，　

把变量的使用抽象成程序的信任模式，使用模型检测技术进　

行验证，如果不满足，找出其反例，从而达到找到数据流的异　

常情况的目的。　

２数据流分析及其信任模式　

２．１问题描述　

从数据流观点来看，程序的执行可以看成变量从声明、定　

义（赋值）到最后使用的一个循环过程。　定义１（变量声明）在程序中给出变量的类型，并指出该　

变量所占的内存空间。例如，ｉｎｔ　，ｆｌｏａｔ　都是声明一个变　量。在Ｃ／Ｃ＋＋语言中，全局变量和静态变量的初始数据值自动　

设置为零，而局部非静态变量的初始值则是不确定的。　

定义２（变量定义）在程序中给出变量的初始值，因此，比　

较通俗的说法是变量赋值或变量初始化。可以在变量声明的　

同时对变量进行初始化，也可以在变量声明后通过赋值语句　获得，如ｉｎｔ　ｘ＝５，ｙ＝８．０等。变量的定义有一个特征，变量在赋　

值号的左侧。　定义３（变量的使用）在程序中使用变量进行运算的过　

程，３￣Ｕｘ＝ｘ＋５等。　

其中，变量声明错误很容易在程序的编译过程检测出来，　

而变量的定义和使用有时是检查不出来的，而且有时可能是　

程序员的误写，但变量的定义和使用也会造成程序的一些不　可预料的后果或者程序的崩溃。限于篇幅，在本文中对于数　

据流的分析主要限于对变量使用的分析上，着重解决以下三　

个问题：　（１）变量未初始化。对于未初始化就使用的变量，一般的　编译器都能够进行识别，容易出现未初始化变量故障的情况　

是在程序执行的某个路径上初始化了该变量，但是另一个路　

径上，该变量又没有被初始化，从而导致了未初始化变量的故　障。此外，变量未初始化可能是由于程序员的误用，比如在程　

序中使用赋值语句　—　一，，这里，以前没有定义。这里，有　

两种情况，第一可能真的是在初始化前使用，这会变得非常危　

险，因为当变量被使用时，其当前值是未知的，可能会导致灾　

难性后果；第二种可能是笔误，比如其实可能是数字１而不是　

字母，。　’　

（２）变量定义（赋值）后没有使用。比如函数调用　，Ｙ），　之后再也没有使用　，这类异常会造成程序冗余，使程序的可　

读性比较差；还有一种可能是这个赋值语句用错了，比如应该　

是　，ｙ），而不是ｘ＝ｆ（ｘ，Ｙ）。　（３）变量在两次定义（赋值）之间未被使用。比如下面程序：　

＝厂　）］　｝中间变量ｘ没有使用　

＝厂（ｗ　

这里有可能出现　）赋值冗余或者在这两个赋值语句之间　

遗漏了对Ｘ的某些使用语句。　总之，变量使用异常问题通常不容易被编译器所识别，因　

为编译器只识别语法，对变量的语义使用无法察觉。因此，这　

种测试特别对于使用弱类型检查的语言（例如ｃ／Ｃ＋＋），通过对　变量的检查，可以对程序执行语义进行合理、有穷和近似的计　

算，它对系统静态表示进行分析以发现问题，文档和代码分析　

工具对其会有一定帮助。　２．２程序语言中的信任模式　

在本文中，把满足以下规则的变量正确使用称为是满足　

可信模式的使用。　定义４（可信模式）所谓可信模式是指判断研究对象是否　

可信的标准或依据。　例如，可以根据程序中变量使用的先后顺序也判断程序　

是否有故障，这里的变量使用的先后顺序就是判断程序是否　

可信的一个可信模式。　定义５（程序信任模式）所谓程序信任模式是指对于程序　中变量的使用进行结构和内容规范性的描述，其作用根据变　

量的使用来判断程序的故障。　根据上面叙述，对程序中变量的使用情况进行了归纳和　

总结，提取了程序中变量使用的如下可信模式：　

规范１变量在使用之前一定要先定义。　

规范２两次变量定义之间一定要使用。　

规范３变量最终一定要被使用。　这些规范主要从变量的使用上来对程序进行测试，这些　

合集下载

IoT数据流实时监测与预警技术

IoT数据流实时监测与预警技术

IoT数据流实时监测与预警技术

随着物联网（IoT）技术的快速发展，大量设备和传感器连接到互联网，产生海量的数据流。为了能够及时了解和响应这些数据流中的异常情况，监测和预警技术变得至关重要。本文将介绍IoT数据流实时监测与预警技术的原理、应用和挑战。

一、IoT数据流实时监测技术的原理

IoT数据流实时监测技术主要通过对数据流进行实时分析和处理，以识别异常情况并提供预警。其原理包括以下几个方面：

1. 数据采集：通过传感器等设备，实时采集物理环境、设备状态等各类数据，并将其传输到监测系统。

2. 数据处理：监测系统对传输过来的数据进行过滤、清洗和加工，提取关键特征并构建数据模型。

3. 异常检测：基于构建的数据模型，利用各种机器学习和数据挖掘算法，对数据流进行实时分析，识别异常情况。

4. 预警通知：一旦发现异常情况，监测系统将及时发送预警通知给相关人员，以便及时采取措施。

二、IoT数据流实时监测技术的应用

IoT数据流实时监测技术广泛应用于各个领域，例如：

1. 工业生产：通过监测设备和工艺参数数据，实时监控生产过程中的异常情况，提高生产效率和质量。 2. 城市管理：通过监测城市交通流量、环境污染等数据，实时监控和预测城市交通状况和环境质量，为城市管理决策提供支持。

3. 智能家居：通过监测家庭设备的使用情况和环境参数，实时监控家庭安全和能源消耗，提供智能化的家居管理。

4. 电力系统：通过监测电力设备的状态和用电量数据，实时监控电力系统的运行状况，提供及时的故障诊断和预警。

三、IoT数据流实时监测技术面临的挑战

虽然IoT数据流实时监测技术带来了巨大的潜力，但也面临一些挑战：

1. 数据质量：由于大量设备和传感器参与数据采集，数据的质量和准确性存在一定的问题，如数据噪声、丢失和错误。

2. 数据处理：海量的实时数据需要进行高效的处理和分析，包括数据过滤、特征提取、模型训练等，对计算能力和算法效率提出了要求。

基于数据流分析的工作流模型局部性研究

基于数据流分析的工作流模型局部性研究

第２８卷第ｌ０期　

２０１１年１０月　计算机应用与软件　

Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　ａｎｄ　Ｓｏｆｔｗａｒｅ　Ｖｏ１．２８　Ｎｏ．１Ｏ　

Ｏｃｔ．２０１ｌ　

基于数据流分析的工作流模型局部性研究　

郭春丽李海波　

（华侨大学计算机科学与技术学院福建厦门３６１０２１）　

摘要　由于模型化简的方法存在着通用性的限制，工作流模型中控制流和数据流相结合的冲突检测通常要在整个模型范围内　

进行，模型维护的复杂性高。首先通过分析工作流模型中存在的时序依赖和数据依赖关系，以及二者应该满足的一致性，揭示出工　

作流模型的拓扑结构中存在着局部性。基于工作流模型的局部性原理提出活动的稳定子图，以及工作流模型重构后的局部区域求　

解方法，并对方法给予证明。最后的对比分析表明，工作流模型的拓扑结构发生变化时，控制流和数据流的一致性完全可以在局部　

范围内验证和维护，进而提高了模型维护的效率。　

关键词　工作流模型　

中图分类号ＴＰ３０１．６　局部性稳定子图　

文献标识码Ａ　

ＤＡＴＡＦＬｏＷ　ＡＮＡＬＹＳＩＳ　ＢＡＳＥＤ　ＷｏＲＫＦＬｏＷ　ＭｏＤＥＬ　ＬｏＣＡＬＩＴＹ　ＲＥＳＥＡＲＣＨ　

Ｇｕｏ　Ｃｈｕｎｌｉ　Ｌｉ　Ｈａｉｂｏ　

（Ｃｏｌｌｅｇｅ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈｕａｑｉａｏ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｍｅｎ　３６１０２１，Ｆｕｊｉａｎ，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ　Ｓｉｎｃｅ　ｔｈｅｒｅ　ｉｓ　ｃｏｎｓｔｒａｉｎｔ　ｆｏｒ　ｇｅｎｅｒａｌｉｔｙ　ｗｉｔｈ　ｔｈｅ　ｍｏｄｅｌ　ｒｅｄｕｃｔｉｏｎ　ｍｅｔｈｏｄ．ｉｎ　ａ　ｗｏｒｋｆｌｏｗ　ｍｏｄｅｌ　ｔｈｅ　ｃｏｌｌｉｓｉｏｎ　ｄｅｔｅｃｔｉｏｎ　ｃｏｍｂｉｎｉｎｇ　

ｂｏｔｈ　ｔｈｅ　ｃｏｎｔｒｏｌ　ｆｌｏｗ　ａｎｄ　ｔｈｅ　ｄａｔａ　ｆｌｏｗ　ｉｓ　ｕｓｕａｌｌｙ　ｃａｒｒｉｅｄ　ｏｕｔ　ｗｉｔｈｉｎ　ｔｈｅ　ｅｎｔｉｒｅ　ｍｏｄｅ１．Ｓｏ　ｉｔ　ｉｓ　ｃｏｍｐｌｅｘ　ｔｏ　ｍａｉｎｔａｉｎ　ａ　ｍｏｄｅ１．Ｆｉｒｓｔｌｙ　ｔｈｒｏｕｇｈ　

分形技术与矢量量化相结合的网络流量异常检测研究

分形技术与矢量量化相结合的网络流量异常检测研究

3第19卷第3期邯郸学院学报2009年9月Vol.19No.3JournalofHandanCollegeSept.2009分形技术与矢量量化相结合的网络流量异常检测研究何月梅1，2，杜海艳1，王保民1（1．邯郸学院信息工程学院，河北邯郸056005；2．河北工程大学信息与电气工程学院，河北邯郸056038）————————————————————————————————————————————摘要：本文在分析国内外网络流量异常检测现状的基础上，针对多数异常检测模型实时性较差、检测率较低、误报率较高等问题，提出了一种新的基于分形技术和矢量量化的网络流量异常检测方法.理论分析表明，该方法具有较高的精度和较低的时间、空间复杂度，可以准确高效地检测出异常网络流量，并定位网络异常原因.关键词：分形；矢量量化；网络流量；异常检测中图分类号：TP393文献标识码：A文章编号：1673-2030(2009)03-0073-04基金项目：河北省教育厅项目（项目编号：Z2009408）收稿日期：2009-06-09作者简介：何月梅（1975—），女，河北武安人，邯郸学院信息工程学院讲师，硕士研究生在读；王保民（1971—），男，河北魏县人，邯郸学院信息工程学院副教授，硕士；杜海艳（1974—），女，河北文安人，邯郸学院信息工程学院讲师，硕士.————————————————————————————————————————————1引言随着IP技术的飞速发展和信息化进程的不断加快，基于网络的应用服务变得越来越广泛.但是Internet以及网络技术的发展也使得网络入侵攻击变得更为普遍，数量和破坏程度也随之增加，因此检测网络异常流量，并提高网络健壮性十分必要.从Denning提出异常检测模型到今天，作为入侵检测分支的异常检测已经有十几年的历史.包括机器学习、数据挖掘、聚类分析、支持向量机、时间序列和小波分析等在内的大量计算机学科领域的算法和模型都已经被用在异常检测方面.但随着网络速度的增加，网络业务量数据处理规模急剧增加，其中仍然存在很多问题:（1）传统的机器学习和数据挖掘算法虽然广泛的应用到异常检测领域，但目前的方法和模型大多仅仅是简单应用，并没有满足检测算法实时性的要求[1]1569-1584，大多数的算法实时性较差，对于检测大流量高带宽的恶意数据流更是如此.（2）多数异常检测模型的检测率较低、误报率和漏报率较高，检测率和误报率很难平衡，也就是检测率较高的情况下不能降低误报率.基于分形技术的异常检测和矢量量化的异常检测方法是近年来针对网络异常检测的两个研究热点.2005年，Bulut提出了一种高效的突变检测算法[2]44-55，该算法通过维护分层的最小限制矩形来索引多个滑动窗口上的聚集计算结果.但该突变检测算法[3]336-345只能检测随滑动窗口长度单调变化的聚集函数值的突变，不能检测非单调的聚集函数值的突变.文献[4，5]中也提出了用于网络流量突变行为的检测方法.虽然它们使用的方法不同，但它们都有一个共同点，即只能同时检测单一窗口的变化.事实上，实际应用需要检测的滑动窗口长度往往难以确定.因此，为了能够检测到所有要求的突变，简单的办法就是分别运行多种算法.显然，这会导致大量的空间和时间开销，使得系统性能降低7.MiMj时间XXP'iP'i+1PiPjP'j图数据流X上分段分形模型的收缩映射文献[6]提出了基于分形技术的数据流突变检测算法，与已有研究成果相比，算法具有较高的精度和较低的时间/空间复杂度，更加适用于进行数据流的突变检测.文献[7]在基于矢量量化码书结构的基础上，提出了一种基于矢量量化的网络异常检测方法用于恶意数据流的检测，将数据压缩和矢量量化的思想用于网络业务量用户行为模式分析，理论分析和实验结果证明了该方法的有效性.2基于分形技术的网络流量检测一般把在自然界存在的自相似的现象称为分形，分形模型适用于描述自然界中复杂的形状[8]37-47.已有大量研究工作证明：自相似性是自然界中普遍存在的现象.例如：网络上的通信行为、股票交易数据、人类的生理现象、气象数据等都是自相似的.式（1）所示的幂律伸缩性关系作为分形模型的重要性质，是对自相似性进行数学描述的有力工具.s为特征线度，如时间、长度；q为s上的度量，如聚集计算；p为比例常数；d为伸缩性指数，对式（1）两端同时取对数可得式（2）.dspq=（1）sdpqlogloglog+=（2）准确分形的数据是指在任意长度s上的度量q的值都遵守式（1）的数据，幂律伸缩性关系是判断准确分形的充要条件.因此，对于准确分形的数据，所有的点（logs，logq）都在式（2）代表的直线上，d为直线的斜率.而对于近似分形的数据，式（2）两端的值只具有相同的分布，d则是所有点（logs，logq）的线性回归线的斜率.分段分形更适合于描述实际应用中具有近似分形特性的数据，已被成功地运用于给定数据集的建模以及压缩.分段分形模型（piecewisefractalmodel）由有限多的收缩映射{Mi：i=1，k}组成.每一个收缩映射Mi对应一组分段Pi和Pi′，形如式（3）.它的数学基础是循环迭代函数系统（recurrentiteratedfunctionsystem）.mibbyxaaaayxMiiiiiii,212122211211，，=+=（3）在Mi的系数中，ia22称作收缩因子，且122

基于Filter-ary-Sketch数据结构的骨干网异常检测研究

基于Filter-ary-Sketch数据结构的骨干网异常检测研究

第３２卷第１２期　２０１１年１２月　通信学报　Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｖ０１３２　ＮＯ．１２　Ｄｅｃｅｍｂｅｒ　２０１　１　

基于Ｆｉｌｔｅｒ－ａｒｙ．Ｓｋｅｔｃｈ数据结构的骨干网异常检测研究　

郑黎明　，邹鹏　，韩伟红　，李爱平　，贾焰　

（１．国防科学技术大学计算机学院，湖南长沙４１００７３；２．装备指挥技术学院，北京１０００２９）　

摘要：针对骨干网上异常检测的特殊要求，提出了一种基于Ｆｉｌｔｅｒ－ａｒｙ—Ｓｋｅｔｃｈ数据结构的异常检测方法。该方法　

通过Ｆｉｌｔｅｒ－ａｒｙ．Ｓｋｅｔｃｈ实时记录网络流量信息，然后每隔一定周期进行基于多维熵值的异常检测。如果出现异常则　

根据Ｆｉｌｔｅｒ－ａｒｙ—Ｓｋｅｔｃｈ记录的流量信息进行异常点定位，最后利用Ｂｌｏｏｍ　Ｆｉｌｔｅｒ中记录的源ＩＰ信息进行恶意流量阻　

断。该方法能够检测多种类型的网络攻击，且能有效地进行恶意流量阻断。利用实际骨干网流量数据，分别从效　

率和精度２个方法进行对比实验，取得了较好的效果。　

关键词：网络安全；异常检测；概要数据结构；熵　

中图分类号：ＴＰ３９３．０８　文献标识码：Ａ　文章编号：１００　４３６Ｘ（２０１１）１２—０１５１—１０　

Ａｎｏｍａｌｙ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｂａｃｋｂｏｎｅ　ｎｅｔｗｏｒｋｓ　ｕｓｉｎｇ　Ｆｉｌｔｅｒ－・ａｒｙ－－Ｓｋｅｔｃｈ　

ＺＨＥＮＧ　Ｌｉ—ｍｉｎｇ　，ＺＯＵ　Ｐｅｎｇ　，ＨＡＮ　Ｗｅｉ—ｈｏｎｇ　，ＬＩ　Ａｉ．ｐｉｎｇ　，ＪＩＡ　Ｙａｎ　

（１．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒ，ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙ　ｏｆＤｅｆｅｎｓｅＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ；　

２．Ａｃａｄｅｍｙ　ｏｆ　Ｅｑｕｉｐｍｅｎｔ　Ｃｏｍｍａｎｄ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ　１０００２９，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｆｏｒ　ｔｈｅ　ｓｐｅｃｉａｌ　ｒｅｑｕｉｒｅｍｅｎｔｓ　ｏｆ　ａｎｏｍａｌｙ　ｄｅｔｅｃｔｉｏｎ　ｉｎ　ｂａｃｋｂｏｎｅ　ｎｅｔｗｏｒｋｓ，ａｎ　ａｎｏｍａｌｙ　ｄｅｔｅｃｔｉｏｎ　ｍｅｔｈｏｄ　ｗａｓ