基于数据挖掘技术的入侵检测模型中的Apriori算法研究.docx

信息技术与工程学院课程 入侵检测与防火墙技术 专业班级 网络工程1401 学号 1411132143 姓名 张浩 指导教师 赵丽 成绩 基于数据挖掘技术的入侵检测模型中的Apriori算法实现本节首先对现有的异常检测技术进行了系统的分析研究，然后着重对数据挖掘技术从其概念本身和它在异常检测中的应用两个方面进行了分析和探讨。继而综合关联规则算法、击键韵律以及其他检测技术，提出了一个检测模型。本模型的一个出发点就是，认为用户的击键韵律是一种生物特征，用户与用户之间的这种特征是有差别的，可以作为入侵检测中的行为模式。模型具体是利用一系列数据挖掘算法建立用户的键盘行为模式库和鼠标行为模式库，然后用分类算法和漏桶算法相结合进行实时检测。 1概述目前入侵检测产品大多采用误用检测,这种入侵检测技术的主要局限在于：1.它只能根据已知的入侵序列和系统缺陷的模式来检测系统中的可疑行为，而面对新的入侵攻击行为以及那些利用系统中未知或潜在缺陷的越权行为则无能为力。2.检测系统知识库中的入侵攻击知识与系统的运行环境有关。3.对于系统内部攻击者的越权行为，由于他们没有利用系统的缺陷，因而很难检测出来。异常检测技术是一种在不需要操作系统及其安全性缺陷专门知识的情况下检测入侵的方法，同时它也是检测冒充合法用户入侵的有效方法。(如数据挖掘技术，免疫技术、遗传算法GA。) 数据挖掘技术本身发展迅速，它在入侵检测中也得到了广泛的应用，取得了不少成果。其中比较常用的有关联规则、序列规则、联结分析和分类算法等方法，对于发现新的攻击和更好的描述用户正常行为取得了很好的效果。同时也出现了几个比较成熟的应用数据挖掘的入侵检测系统。击键韵律最先是由Rick Joyce和Gopal Gupta作为认证手段提出的，并取得了一定的成果。实验数据表明，不同用户之间击键韵律存在可以进行鉴别的差别，同理，不同用户对鼠标的使用也有各自的特征。本文着眼于用户键盘和鼠标的行为特征，将其作为分析对象，应用数据挖掘技术进行异常检测。 2 数据挖掘技术及其在入侵检测中的应用。.基本概念.数据挖掘 (Data Mining) ,也称数据库中的知识发现 (KDD:Knowledge Discovery in Database)，KDD一词首次出现在1989年8月举行的第11届国际联合人工智能学术会议上。数据挖掘: 是指从大型数据库或数据仓库中提取人们感兴趣的知识,这些知识是隐含的、事先未知的潜在有用信息,提取的知识一般可表示为概念 (Concepts)、规则(Rules)、规律 (Regularities)、模式 (Patterns)等形式。其过程如下图所示：.数据挖掘主要技术 .数据挖掘的方法繁多，从应用到入侵检测领域的角度来讲，以下几种方法非常常用： (下面几个方面要细化)(1)关联分析(2)序列模式分析(3)分类分析(4)聚类分析.数据挖掘与入侵检测的结合 .数据挖掘技术在入侵检测中主要是两个方向，一是发现入侵的规则、模式，与模式匹配检测方法相结合。二是用于异常检测，找出用户正常行为，创建用户的正常行为库。提出这个技术的目的之一是为了弥补模式匹配技术对未知攻击无能为力的弱点。 目前将数据挖掘技术应用于入侵检测领域具有代表性的成果就是美国哥伦比亚大学的wenke lee研究小组所创建的入侵检测系统。所用的主要技术是分类、关联规则和序列规则分析。 这些系统中大多应用关联规则、序列规则、分类算法等。下面，以wenkee lee小组的研究为例，分析一下这几项技术如何用于检测。(1). 关联规则：(细化)(2). 序列规则: (细化)(3). 分类算法: (细化).一个基于数据挖掘的异常检测模型 .下面介绍的仍然是美国哥伦比亚大学的wenke lee研究小组所做的异常检测模型。概括一下，此模型分三个步骤完成:步骤一、前四周作为数据收集阶段； 步骤二、第五周为训练阶段； 步骤三、从第六周开始进入正常检测阶段。 . 存在的问题和发展方向. 数据挖掘在入侵检测领域有着很好的发展前景，然而，这项技术还有一些困难需要解决。数据挖掘需要大量的数据，系统庞大而复杂。前期所需要的训练数据来之不易，比较昂贵。挖掘大量的数据需要花费计算力，时间和内存，如何保证检测的实时性,有效性就成为了一个重大问题. 4.Apriori是关联规则模型中的经典算法,是由R.Agrawal和R.Srikant于1994年提出的为布尔关联规则挖掘频繁项集的原创性算法。Apriori使用一种称作逐层搜索的迭代方法，k项集用于搜索k+1项集。该算法主要用于在交易数据、关联数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联性或因果结构。重要概念N项集 表示由N个元素组成的元素集合（N为大于0的整数）N项集的支持度 表示在所有样本中，能够匹配特定N项集要求的样本数量，它也可以表示成百分比的形式。频繁N项集（Ln） 表示满足指定的最小支持度的所有N项集候选N项集（Cn） 它由频繁N-1项集Ln-1生成，是计算频繁N项集的基础。Cn必须保证包括所有的频繁N项集。重要性质频繁项集的所有非空子集也必须是频繁的。即如果项集A不满足最小支持度阈值MinSupport，则A不是频繁的，如果将项集B添加到项集A中，也就是A B也不可能是频繁的。该性质是一种反单调性的性质，也就是说如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试。基本实现原理首先寻找L1（即频繁1项集）；在Lk的基础上生成候选频繁k+1项集Ck+1；用事务数据库D中的事务对所有Ck+1进行支持度测试以寻找频繁项集Lk+1，计算每个候选频繁项集的支持度，如果大于最小支持度，则加入到Lk+1；如果Lk+1为空集，则结束，L1 L2 即为结果；否则转2继续。算法示例:操作数据:Apriori在Java中的实现:package com.sram.tends;import java.io.BufferedReader; import java.io.File; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; import java.util.List; /* * Apriori算法实现 最大模式挖掘，涉及到支持度，但没有置信度计算 * author push_pop * */ public class AprioriMyself private static final double MIN_SUPPROT = 0.2;/最小支持度 private static boolean endTag = false;/循环状态 static ListList record = new ArrayListList();/数据集 public static void main(String args) /*读取数据集* record = getRecord(); /控制台输出记录 System.out.println(以矩阵形式读取数据集record); for(int i=0;irecord.size();i+) List list= new ArrayList(record.get(i); for(int j=0;jlist.size();j+) System.out.print(list.get(j)+ ); System.out.println(); /*获取候选1项集* ListList CandidateItemset = findFirstCandidate(); /控制台输出1项候选集 System.out.println(第一次扫描后的1级 备选集CandidateItemset); for(int i=0;iCandidateItemset.size();i+) List list = new ArrayList(CandidateItemset.get(i); for(int j=0;jlist.size();j+) System.out.print(list.get(j)+ ); System.out.println(); /*获取频繁1项集* ListList FrequentItemset = getSupprotedItemset(CandidateItemset); /控制台输出1项频繁集 System.out.println(第一次扫描后的1级 频繁集FrequentItemset); for(int i=0;iFrequentItemset.size();i+) List list = new ArrayList(FrequentItemset.get(i); for(int j=0;jlist.size();j+) System.out.print(list.get(j)+ ); System.out.println(); /*迭代过程* while(endTag!=true) /*连接操作*由k-1项频繁集 获取 候选k项集* ListList nextCandidateItemset = getNextCandidate(FrequentItemset); System.out.println(扫描后备选集); for(int i=0;inextCandidateItemset.size();i+) List list = new ArrayList(nextCandidateItemset.get(i); for(int j=0;jlist.size();j+) System.out.print(list.get(j)+ ); System.out.println(); /*减枝操作*由候选k项集 获取 频繁k项集* ListList nextFrequentItemset = getSupprotedItemset(nextCandidateItemset); System.out.println(扫描后频繁集); for(int i=0;inextFrequentItemset.size();i+) List list = new ArrayList(nextFrequentItemset.get(i); for(int j=0;j频繁集); for(int i=0;iFrequentItemset.size();i+) List list = new ArrayList(FrequentItemset.get(i); for(int j=0;jlist.size();j+) System.out.print(list.get(j)+ ); System.out.println(); /*下一次循环初值* CandidateItemset = nextCandidateItemset; FrequentItemset = nextFrequentItemset; /* * 读取txt数据 * return */ public static ListList getRecord() ListList record = new ArrayListList(); try String encoding = GBK; / 字符编码(可解决中文乱码问题 ) File file = new File(C:UsersDELL-01Desktopsimple.txt); if (file.isFile() & file.exists() InputStreamReader read = new InputStreamReader( new FileInputStream(file), encoding); BufferedReader bufferedReader = new BufferedReader(read); String lineTXT = null; while (lineTXT = bufferedReader.readLine() != null) /读一行文件 String lineString = lineTXT.split( ); List lineList = new ArrayList(); for (int i = 0; i lineString.length; i+) /处理矩阵中的T、F、YES、NO if (lineStringi.endsWith(T)| lineStringi.endsWith(YES) lineList.add(record.get(0).get(i); else if (lineStringi.endsWith(F)| lineStringi.endsWith(NO) ;/ F，NO记录不保存 else lineList.add(lineStringi); record.add(lineList); read.close(); else System.out.println(找不到指定的文件！); catch (Exception e) System.out.println(读取文件内容操作出错); e.printStackTrace(); return record; /* * 有当前频繁项集自连接求下一次候选集 * param FrequentItemset * return */ private static ListList getNextCandidate(ListList FrequentItemset) ListList nextCandidateItemset = new ArrayListList(); for (int i=0; iFrequentItemset.size(); i+) HashSet hsSet = new HashSet(); HashSet hsSettemp = new HashSet(); for (int k=0; k FrequentItemset.get(i).size(); k+)/获得频繁集第i行 hsSet.add(FrequentItemset.get(i).get(k); int hsLength_before = hsSet.size();/添加前长度 hsSettemp=(HashSet) hsSet.clone(); for(int h=i+1; hi)连接 每次添加且添加一个元素组成 新的频繁项集的某一行， hsSet=(HashSet) hsSettemp.clone();/！做连接的hasSet保持不变 for(int j=0; j FrequentItemset.get(h).size();j+) hsSet.add(FrequentItemset.get(h).get(j); int hsLength_after = hsSet.size(); if(hsLength_before+1 = hsLength_after & isSubsetOf(hsSet,record)=1 & isnotHave(hsSet,nextCandidateItemset) /如果不相等，表示添加了1个新的元素，再判断其是否为record某一行的子集 若是则其为 候选集中的一项 Iterator itr = hsSet.iterator(); List tempList = new ArrayList(); while(itr.hasNext() String Item = (String) itr.next(); tempList.add(Item); nextCandidateItemset.add(tempList); return nextCandidateItemset; /* * 判断新添加元素形成的候选集是否在 新的候选集中 * param hsSet * param nextCandidateItemset * return */ private static boolean isnotHave(HashSet hsSet, ListList nextCandidateItemset) / TODO Auto-generated method stub List tempList = new ArrayList(); Iterator itr = hsSet.iterator(); while(itr.hasNext() String Item = (String) itr.next(); tempList.add(Item); for(int i=0; inextCandidateItemset.size();i+) if(tempList.equals(nextCandidateItemset.get(i) return false; return true; /* * 判断hsSet是不是record2中的某一记录子集 * param hsSet * param record2 * return */ private static int isSubsetOf(HashSet hsSet, ListList record2) /hsSet转换成List List tempList = new ArrayList(); Iterator itr = hsSet.iterator(); while(itr.hasNext() String Item = (String) itr.next(); tempList.add(Item); for(int i=1;irecord.size();i+) List tempListRecord = new ArrayList(); for(int j=1;jrecord.get(i).size();j+) tempListRecord.add(record.get(i).get(j); if(tempListRecord.containsAll(tempList) return 1; return 0; /* * 由k项候选集剪枝得到k项频繁集 * param CandidateItemset * return */ private static ListList getSupprotedItemset(ListList CandidateItemset) / TODO Auto-generated method stub boolean end = true; ListList supportedItemset = new ArrayListList(); int k = 0; for (int i = 0; i = MIN_SUPPROT * (record.size()-1) supportedItemset.add(CandidateItemset.get(i); end = false; endTag = end;/存在频繁项集则不会结束 if(endTag=true) System.out.println(无满足支持度项集,结束连接); return supportedItemset; /* * 统计record中出现list集合的个数 * param list * return */ private static int countFrequent(List list) / TODO Auto-generated method stub int count = 0; for