【作者】 阮幼林；

【导师】 李庆华；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2004， 博士

【摘要】 随着网络和其它信息技术的广泛应用,网络系统的安全变得至关重要。入侵检测系统是保护网络系统安全的关键技术和重要手段,但现行的入侵检测不仅对新的攻击或特征未知的入侵无能为力,而且检测的准确性与实时性均达不到实际应用的需求。频繁模式挖掘是数据挖掘研究中一个重要的研究内容,可以从海量数据中发现正常和异常的行为模式, 将其用于入侵检测不仅可以有效地检测已知入侵, 而且还具有检测未知攻击模式的能力,具有更高的准确性和适应性。因此,针对入侵检测中的数据特点,研究频繁模式的高效挖掘算法及其并行化方法对于提高入侵检测的准确性和时效性具有非常重要的理论意义和实用价值。针对现有挖掘算法存在的多趟扫描数据、动态维护复杂、更新效率低等问题,提出了一种基于前缀树的频繁模式挖掘算法 PT-Mine 和更新算法 UPT-Mine。PT-Mine 算法利用前缀树压缩存放数据,通过调整前缀树中相关节点信息和节点链直接在前缀树上采用深度优先的策略挖掘频繁模式,不需要任何附加的数据结构, 而且每次挖掘只需前缀树的一棵子树即可。因此,本算法既有效地节省了存储空间,又提高了挖掘的效率和可扩展性。更新算法 UPT-Mine 利用事务树及通过事务树的转换实现前缀树的更新,只需对新增数据扫描一次而无须扫描原始数据,从而大大提高了频繁模式的更新效率。由于最大频繁模式隐含了所有频繁模式, 因此可以用来描述系统的正常行为模型和攻击行为模型。随着网络环境的变化和新的攻击模式的不断出现,入侵检测模型需要不断更新和完善。因此,研究最大频繁模式的高效挖掘和更新算法对于提高入侵检测的准确性和可扩展性是非常重要的。为此,在挖掘算法 PT-Mine 的基础上,提出了一种基于前缀树的最大频繁模式快速挖掘算法 DMFP。本算法不需要产生大量候选集和创建条件模式树,挖掘效率明显优于其它算法。针对现有算法更新难、代价大等问题,提出了增量式更新算法 IUMFP 和阈值更新算法 UMFP。这两种更新算法充分利用 I<WP=5>已有的挖掘结果, 高效地发现最新事务数据库中所有的最大频繁模式。 对于网络入侵数据的高维数和大尺寸以及分布性,高性能的并行挖掘算法是提高检测效率的有效途径。针对传统的并行算法存在的诸如大量候选集的生成、通信代价高、多次同步等问题,提出了一种基于分布数据的并行频繁模式挖掘算法 PMFP。本算法通过分析局部频繁模式和全局频繁模式的关系,尽可能地让每个处理器独立地挖掘, 并通过相关性质尽量减少候选全局频繁模式的规模,从而减少网络的通信量和同步次数以提高挖掘效率。由于候选全局频繁模式的挖掘只需搜索事务树中对应该模式的路径即可,无须对各站点的原始数据进行扫描,从而大大提高全局频繁模式的挖掘效率。考虑各站点的数据量比较悬殊、负载不平衡的情况,提出了一种基于复制的平衡调度算法 TDBS。TDBS 算法充分考虑各站点的负载和利用处理机的空闲时间段,把任务尽量分配到已用的处理机上以均衡负载、提高利用率, 进而提高并行挖掘算法PMFP 的加速比和总体效率。 由于现行的入侵检测系统建立的正常模式和异常模式不够准确、完善, 容易造成误警或漏警, 往往会给网络系统造成巨大损失。据此,提出了一种基于频繁模式挖掘的入侵检测方法。本方法首先通过挖掘训练数据集中的最大频繁模式建立系统和用户的正常行为模型和攻击模型,并通过滑动窗口对实际数据进行并行挖掘和标记,能够更加精确、快速地区分用户的正常行为和异常行为;并及时更新、不断优化入侵检测模型,从而提高入侵检测的准确性和可靠性。实验结果表明,通过不断更新和选择合适的相关参数,本方法可以提高检测的精度和时效性。更多还原

【Abstract】 With the development of network and other information technology, security is themost critical problem to network system. Thus, Intrusion Detection System(IDS) becomeskey way and technology of protecting network system. Current IDS neither detects new orunknown attacks, nor accuracy and response can reach requirement ofapplication. Miningfrequent pattern is a fundamental and important problem in data mining, which not onlydetects normal behavior but also abnormal behavior. So, applying frequent pattern to IDScan detect both known and unknown intrusion, which has more accuracy and compatibilitythan manual. Thus, this paper focuses on the research of efficient frequent patterns miningalgorithm and parallel algorithms and detection methods based on frequent patterns mining,which has more important theory meaning and utility value for improving accuracy andefficiency of IDS. For solving scans of data, adjusting and updating difficulty, this paper presents a novelmining algorithm PT-Mine and updating algorithm UPT-Mine. PT-Mine designs Prefix Treeto store data in a highly compact form, which mines frequent patterns in depth-first orderand directly in Prefix Tree by adjusting node information and node links without using anyadditional data structures. Thus, it not only save space but also improve performance andscalability of IDS greatly. UPT-Mine designs Trans-Tree that updates and changes easily,which needs one scan of the new data only without scanning the existing data. Maximum frequent patterns can describe normal and abnormal model because ofcomprising all of frequent patterns. With the change of circumstances of network andemergence of new attacks, intrusion detection model should be updated and improvedcontinually. Thus, mining and updating maximum frequent patterns is very important toimprove accuracy and scalability of IDS. In this paper, a fast mining algorithm DMFP basedon Prefix Tree is proposed, which mines frequent patterns without creating candidate andconditional pattern tree. Thus, it improves performance greatly. Then, incremental updatingalgorithm IUMFP and updating algorithm UMFP are proposed. Both of them make use ofthe previous mining results to cut down the cost of finding new maximal frequent patterns inan updated database. In order to deal with the high dimension, huge volume and distributed environment ofintrusion data, parallel mining is a practical way to improve efficiency of IDS. In this paper, III<WP=7>parallel mining algorithm PMFP in distributed database is proposed. PMFP attempts tomake each processor to do independently and decrease the number of candidate of globalfrequent patterns according to the relation between local frequent pattern and globalfrequent pattern. Therefore, PMFP uses far less communication overhead and fewersynchronization steps, and improves efficiency of mining. Moreover, mining candidate ofglobal frequent patterns only search corresponding paths in Trans-tree without traversing olddata. Under unbalance workload, this paper presents a Task Duplication based BalanceScheduling(TDBS) algorithm. By considering workloads and some idle time slots of usedprocessors, TDBS tries to assign tasks to scheduled processors and maximize theirutilization. Therefore, TDBS algorithm is a viable option for improving performance ofPMFP. Because user behavior features extracted by current IDS cannot reflect realcircumstances, normal and abnormal model are not accurate. Thus, there are some misuseand leakage warning that may be happened easily and much losses in network system. Thepaper presents an intrusion detection method based on frequent pattern mining. At first, themethod constructs user normal model and abnormal model by mining training data sets.Then, mine and mark the real data in a slide window. The methods can distinct normal andabnormal behavior rapidly, which timely update and improve model of IDS. So, theaccuracy and relia更多还原