文献翻译费下载.doc

重 庆 理 工 大 学文 献 翻 译二级学院 计算机科学与工程 班 级 09371 学生姓名 周旸 学 号 10903070134 利用粗糙集分类的干扰检测简介干扰检测是用于分类正常与异常的活动，在机器学习方面可以发挥重要的作用。最近，基于机器学习的干扰检测方法（Allen等，2000）受到了广泛的研究，因为他们可以检测出的误用和异常。学习的干扰检测方法包括两个关键步骤：功能前牵引和检测模型生成。Wenke（1999）利用改进的Apriori算法在干扰检测特征提取的研究，获得网络连接级别的功能。此方法是非常有效的。后来，SRINIVAS和Sung（2002）提出了利用支持向量机（SVM）排列这些提取出的特征，但这种方法需要多次迭代，是非常耗时的。在检测模型生成的研究，这是可取的，检测模型可以被解释的，并具有高的检出率，但现有方法无法实现这两个目标。例如，神经网络（James，1998年）可以达到较高的检测率，但生成的检测规则是不能解释的；决策树（Wenke，1999年）可能会产生解释的规则，但检出率较低。在本文中，我们目前使用干扰检测系统（IDS）功能的排名和干扰检测规则生成的粗糙集分类（RSC）（帕夫拉克，1982）。干扰检测RSC可以得到解释的检测规则和高检出率的一些攻击和IDS是简单而快速的使用RSC功能的排名。RSC是粗糙集理论（王陶，2003）的重要内容之一。粗糙集学习理论的主要贡献是约简的概念。具有相同属性的对象分类能力的一整套属性约简是一个很小的子集。在本文中，我们提出了一个快速混合遗传算法的粗糙集的约简计算。事实上，简粗糙集计算的对应功能的IDS在RSC排名。与经典的基于支持向量机的功能排名的方法（SRINIVAS，SUNG，2002年）相比，此功能的排序方法是简单和快速。RSC约简为模板创建的干扰规则（决定）。简代后，随后的检测规则自动计算。生成的规则有直观的“IF-THEN”的形式，提高探测器的设计是可以解释的，非常有价值的。实验的目的是测试的规则检测性能。我们使用的实验数据源于麻省理工学院的林肯实验室。它是为KDD（1999年）由DARPA竞争，被认为是干扰检测评估标准的基准。由于SVM进行经典的干扰检测的算法（SRINIVAS，SUNG，2002年）中，我们还可以使用支持向量机的干扰检测对同一数据进行比较。试验结果表明，RSC算法与SVM算法检测探头和DARPA数据集上的DoS攻击（99以上）的兼容电平的检测性能。不过，RSC规则的解释具有明显的优势。进一步比较的RSC基于IDS和基于支持向量机的干扰检测系统中提供了详细论述。本文的组织如下。在第二部分中，系统模型一般基于机器学习的干扰检测方法。在第三部分中，初步解释粗糙集和粗糙集分类算法本文提出的混合遗传算法进行了详细解释。在第四节实验设计比较RSC的IDS和基于支持向量机IDS表示RSC算法的优点。最后，我们总结了本文的最后一节。系统模型Wenke（1999）的研究工作是设计基于学习算法的干扰检测系统，我们可以在后续步骤中了解到：（1） 使用的工具如tcpdump，dsniff等捕获网络数据;（2） 将这些数据转换成合适的输入格式;（3） 从原始数据提取功能标准化净工作流程和攻击行为或正常的使用模式。（4） 设计和使用学习的算法来得到检测规则;（5） 整合为实时IDS检测干扰检测规则。上一节所说的这五个步骤中，特征提取和检测规则生成是两个关键步骤。进行特征提取，它取决于数据源，并以被检测到的攻击类别。为了专注于我们的学习算法的研究，我们选择了1999年的KDD干扰检测的比赛数据集设计我们的系统。1999 KDD干扰检测测试使用了1998年DARPA干扰检测数据集，构建连接记录和提取对象功能（Wenke，1999）。1998年DARPA干扰检测数据集是从9个星期的原始TCP转储数据的局域网（LAN）仿真相关的典型美国空军局域网收购，并夹杂着探头，U2R，R2L的攻击：拒绝服务攻击，四大类。连接记录是TCP包序列的起点和终点在某些清楚界定的时候，它们之间的数据流从一个源IP地址和目标IP地址下一些定义良好的协议。每个连接都被标记为或正常，作为一种攻击，恰好与一个特定的攻击类型。对于每个TCP / IP连接，41各种定量和定性的特征提取。可以使用以下三个主要的功能集，分类每一个连接。（1）固有的特点，即与连接相关的信息。它们包括工期类型，协议，标志等的连接;（2）流量的功能，即过去的连接，类似于当前的一个，例如，具有相同的目标主机的连接或连接在一个给定的时间窗口内或预定数量的过去连接到相同的服务有关的数量有关的统计信息;（3）内容的功能，即提供的信息数据内容的数据包（“有效载荷”），这可能是有关发现的干扰，例如，报告的错误操作系统，根的访问尝试等。粗糙集分类算法。检测规则自动生成，完成这个任务，我们目前使用的粗糙集分类。它包括三个阶段：1）预处理：原始数据首先被划分为三组：DoS攻击检测数据集，探针攻击检测数据集，U2R和R2L攻击检测数据。对于每个数据集，构造决策系统。每一个决策系统，后来分裂成两部分：训练数据集和测试数据集。2）培训：粗糙集分类的训练，每次训练数据集的三种不同类型的攻击（DOS，探头，U2R和R2L）。每一个训练数据集使用相应的输入功能，可分为两大类：（+1）和攻击（ -1 ）。3）测试：测量测试数据上的表现。在下面的章节中，我们将详细描述我们的粗糙集分类算法。A部分：粗糙集理论初步粗糙集理论是由Zdzislaw Pawlak在20世纪80年代初（Pawlak，1982年）。它是一种数学近似推理决策支持工具，是特别适合于对象分类。粗糙集也可用于特征选择，特征提取等（Wang，2001）。定义1一种信息系统中被定义为一个四元组如下，S= , 其中U =X1，X2，.，Xn是一个有限的对象集（n是对象的数目）;Q是有限的属性集，Q= Q1，Q2，.，QN; V = UQqVq的和Vq是一个域的属性q ）; F：UVV是一个总的功能，例如，函数f（xV q为每个qQ，XU，Q）。如果属性可分为条件属性集C和决策属性集D，即在S。Q = CD和CD =，S称为决策系统或决策表信息系统。定义2设IND（P），IND（Q）是不可分辨，由属性确定的关系设置P，Q的P正区域的Q，表示为（IND）（PPOS（IND Q）被定义为如下：定义3设P，Q，R是一个属性集，我们说R是约简到Q的P当且仅当满足下列条件：（1）（2）B部分：粗糙集分类算法我们的总体方案中提出的粗糙集分类算法图1。（1） 原始输入数据集被转换成一个决策系统，它随后被分成两部分：训练数据集和测试数据集。一个分类器从训练数据集将被诱导，并施加到测试数据集以获得一个性能估计。对于训练数据集，我们做了以下的步骤（2），（3）;（2） 如果决策系统具有真正的价值属性，离散化战略，应建立分类规则，以获得更高的质量。有很多discretizaion方法，如嘘声推理算法，半幼稚的算法等。如何选择合适的discretizaion方法仍然是一个难以回答的问题，一些测试是必要的。在我们下面的实验中，使用平等间隔宽度discretizaion的方法。等间隔宽度离散化方法划分成k个大小相等的时间间隔，其中k 0为用户提供的参数范围内的观测值属性。如果一个属性被观察到有此方法计算的时间间隔宽度宽度（K）=（AMAX-AMIN）/ k和结构的阈值AMIN+ I *宽度（K）的一个分钟和一个maxthen的范围内的值，其中i= 1，.，的k - 1。独立的方法被施加到每个连续属性。由于这无监督的方法不使用在设置分区边界的判定值，则很可能由像素合并的结果相结合的值强烈关联到相同的时间间隔的不同的类的分类信息将丢失。但在我们的例子中，这样可以使有效的分类。（3）干扰（决定）创建的规则约简的属性约简算法计算模板。有很多的属性约简算法，如动态约简（巴桑等人，1994年）和RA-订单算法（王陶，2003）等，但到现在为止最有效的算法，大的决策系统重新duction计算实践是遗传算法（Wroblewski，1995），它是由最粗糙集工具如粗糙足够的（安德斯，1997年）和Rosetta（亚历山大，1999年）。在本文中，我们找到最小约简属性重要性的启发式规则的基础上，提出了一种混合遗传算法。这种混合遗传算法降低了训练时间，使生成的分类更有效的调整，以适应干扰检测环境。这种混合遗传算法的关键是在我们的RSC算法的子算法。为了讲清楚，我们首先介绍了一般遗传算法（气）及其扩展在C部分，我们将介绍详细的键子算法测试数据集D部分，下面的步骤就完成了。（4）第一次使用相同削减计算从训练数据discretizaion的方法离散化的新对象的数据集。然后生成的规则是用来匹配测试对象，计算的力量所选择的规则设置的任何决策类。新的对象将被分配到与选定的规则集的最大强度的决定类。C部分：寻找最小约简基于混合遗传算法的基础上SGF（1）框架的混合遗传算法作为上述的“第一个”，发现粗糙集最小约简被视为最小碰集问题。对于离散化的决策支持系统L =（U，AD，V，F），multiset的根据上述定义5，A部分。随后，这multiset的碰集的计算基于混合遗传算法。在我们的算法中，命名位适应构建一个新的运营商。这种新的运营商对整个人口，并能保证每个染色体收敛到一个碰集。（2）代表（生成的初始群）人口一个简单的选择，对于极小碰集问题，是一组P的元素从2A，编码为bitvectors，其中每个比特表示的集合中的特定元素的存在。例如，假设我们有10个条件属性A1，A2，.，A10A1，A4，A6，A9，我们有一个简候选人。简候选人应表示为：1001010010。（3）选择和重组的方法选择和重组运营商都配有两个步骤：第1步：计算每个染色体在当前t代健身。然后，根据每个染色体的适应度，我们采用随机抽样的方法选择。第2步：设minsingle（后代）是新的种群中的最差个体（后代），minfit相应的健身：让我们maxsingle（母公司）是最好的老年人口，个人maxfit（母公司）相应的健身。 ，如果minfit（后代）maxfit（母公司），我们将minsingel（后代）maxsingle（母公司）。实验为了比较RSC算法与传统的学习算法的干扰检测，我们构建干扰检测系统，利用粗糙集分类（RSC）和支持向量机（SVM）和1999年的KDD干扰检测比赛数据集上测试其性能。两个实验（RSC的IDS和基于支持向量机的干扰检测系统）在同一个人电脑（戴尔OptiPlex GX400系统），1.70 GHz奔腾IV CPU，运行Windows 2000系统和128 M RAM。编译器是Microsoft Visual C + 6.0的程序语言是C和C +。结论高检测率和解释的规则，这是非常有价值的，因为这可以提高我们的知识的性质的干扰。在本文中，我们使用粗糙集分类（RSC）的干扰检测系统（IDS）功能的排名和干扰检测规则生成。干扰检测RSC可以同时得到解释的一些攻击检测规则和较高的检测率。并设有排名使用RSC的IDS是简单和快速。此外，我们提出了一种混合遗传算法的人的属性重要性的基础上计算的粗糙集属性约简和加快收敛速度，并减少RSC的训练时间。但是，对于实时的IDS，RSC的训练时间还长的，需要进一步改善。 原文Intrusion detection using rough set classification*INTRODUCTIONIntrusion detection is used to classify normal and intrusive activities, in which machine learning can play an important role. Recently the machine learning-based intrusion detection approaches (Allen et al., 2000) have been subjected to extensive researches because they can detect both misuse and anomaly. The learning-based intrusion detection approaches include two key steps: feature ex-traction and detection model generation. In the research of feature extraction in intrusion detection, Wenke (1999) used improved Apriori algorithm to acquire features of network connection level. This method is very effective. Later, Srinivas and Sung (2002) presented the use of support vector machine (SVM) to rank these extracted features, but this method needs many iterations and is very time-consuming. In the research of detection model generation, it is desirable that the detection model be explainable and have high detection rate, but the existing methods cannot achieve these two goals. For example, neural networks (James, 1998) could achieve high detection rate but the detection rules generated are not explainable; decision trees (Wenke, 1999) could yield explainable rules but the detection rate is low.In this paper we present the use of rough set classification (RSC) (Pawlak, 1982) for intrusion detection system (IDS) feature ranking and intrusion detection rules generation. Intrusion detection using RSC can yield both explainable detection rules and high detection rate for some attacks, and feature ranking using RSC for IDS is simple and fast.RSC is one of the importa nt contents of rough set theory (Wang and Tao, 2003). The main contribution of rough set to learning theory is the concept of reducts. A reduct is a minimal subset of attributes with the same capability of objects classification as the whole set of attributes. In this paper,we propose a fast hybrid genetic algorithm for the reduct computation of rough set. In fact, the reduct computation of rough set corresponds to feature ranking for IDS in RSC. Compared with the classic SVM based feature ranking approach (Srinivas and Sung, 2002), this feature ranking method is simpler and faster. RSC creates the intrusion (decision) rules using the reducts as templates. After reduct generation, the detection rules are automatically computed subsequently. The rules generated have the intuitive “IF-THEN” format, which is explainable and very valuable for improving detector design. Experiments were designed to test the rules detection performance. The experiment data we used originated from MITs Lincoln Labs. It was developed for KDD (1999) competition by DARPA and is considered a standard benchmark for intrusion detection evaluations. Since SVM performed well among the classical intrusion detection algorithms (Srinivas and Sung, 2002), we also use SVM to detect intrusions on the same dataset for comparison. The test results indicated that RSC algorithm has compatible level detection performance with SVM algorithm for detection of Probe and DoS attacks (all above 99%) on DARPA dataset. But RSC has obvious advantage in rules explanations. Further comparisons between RSC based IDS and SVM based IDS are provided in detail in the paper. The paper is organized as follows. In the second section, the system model for general machine learning-based intrusion detection approach is introduced. In the third section, rough set is preliminarily interpreted and rough set classification algorithm used in this paper and the hybrid genetic algorithms proposed are explained in detail. Experiment design for comparison of RSC based IDS and SVM based IDS is given in the fourth section to indicate the advantages of RSC algorithm. Finally we conclude the paper in the last section. SYSTEM MODELBased on the research work of Wenke (1999), designing an intrusion detection system based on learning algorithm can be described in the follow-ing steps: (1). Capture network data by using tools such as Tcpdump, Dsniff, etc.; (2). Process these data into suitable input format; (3). Normalize the net-work flow and extract features of attack behavior or normal usage pattern from raw data; (4). Design and use learning algorithm to get detection rules; (5). Integrate the detection rules into the real time IDS for detecting intrusion. In these five steps, as the above section said, feature extraction and detection rules generation are two key steps. For feature extraction, it depends on data source and the category of attack to be detected. In order to focus on our learning algo-rithm study, we choose the 1999 KDD intrusion detection contest dataset to design our system. The 1999 KDD intrusion detection contest used 1998 DARPA intrusion detection dataset to construct the connection records and extract the object features (Wenke, 1999). 1998 DARPA intrusion detection dataset was acquired from nine weeks of raw TCP dump data for a local-area network (LAN) simu-lating a typical U.S. AirForce LAN and peppered with four main categories of attacks: DoS, Probe, U2R, R2L. A connection record is a sequence of TCP packets starting and ending at some well de-fined times, between which data flows to and from a source IP address to a target IP address under some well defined protocol. Each connection is labeled as either normal, or as an attack, with exactly one specific attack type. For each TCP/IP connection, 41 various quantitative and qualitative features were extracted. The following three mainfeature sets can be used to classify each connection.1) Intrinsic features, i.e., general information related to the connection. They include the duration type, protocol, flag, etc. of the connection; 2) Traffic feature, i.e., statistics related to past connections similar to the current one, e.g., number of connections with the same destination host orconnections related to the same service in a given time window or within a pr edefined number of past connections; 3) Content features, i.e., features containing information about the data content of packets (“payload”) that could be relevant to discover an intrusion, e.g., errors reported by the operating system, root access attempts, etc.For detection rules auto-generation, we present the use of rough set classification for this task. It includes three phases: 1) Preprocessing: The raw data is first partitioned into three groups: DoS attack detection dataset, Probe attack detection dataset, U2R&R2L attack detection dataset. For each dataset, a decision system is constructed. Each decision system is subsequently split into two parts: the training dataset and the testing dataset. 2) Training: rough set classifier is trained on each training dataset of three different types of attacks (DoS, Probe, U2R&R2L). Each training dataset uses the corresponding input features and fall into two classes: normal (+1) and attack ( 1). 3) Testing: measure the performance on testing data. We will describe our rough set classification algorithm in detail in the following section. ROUGH SET CLASSIFICATION ALGORITHMPart A: Rough set theory preliminary Rough sets theory was developed by Zdzislaw Pawlak in the early 1980s (Pawlak, 1982). It is a mathematical tool for approximate reasoning for decision support and is particularly well suited for classification of objects. Rough sets can also be used for feature selection, feature extraction etc. (Wang, 2001). Definition 1 An information system is defined as a four-tuple as follows, S= , where U= x1, x2, , xn is a finite set of objects ( n is the number of objects); Q is a finite set of attributes, Q= q1, q2, , qn; V=UqQVq and Vq is a domain of attribute q ; f : U V V is a total function such that f ( x , q ) V qfor each q Q , x U . If the attributes in S can be divided into condition attribute set C and decision attribute set D, i.e . Q=C D and C D= , the information system S is called a de-cision system or decision table.Definition 2 Let IND ( P ), IND ( Q ) be indiscernible relations determined by attribute sets P , Q , the P positive region of Q , denoted ()() IND PPOS IND Q is defined as follows: Definition 3 Let P , Q , R be an attribute set, we say R is a reduct of P relative to Q if and only if the following conditions are satisfied: (1) (2) Part B: Rough set classification algorithmOur general scheme of rough set classification algorithm is presented in Fig.1. The raw input data set is transformed into a decision system which is subsequently split into two parts: the training dataset and the testing dataset. A classifier will be induced from the training dataset and applied to the testing dataset to obtain a performance estimate. For the training dataset, we do the following steps (2), (3); (2) If the decision system has real values at-tributes, the discretization strategies should be built to obtain a higher quality of classification rules. There are many discretizaion methods such as boo reasoning algorithm, semi-nave algorithm etc. How to choose the suitable discretizaion methods is still a difficult question and some tests are needed. In our following experiment, Equal Interval Width discretizaion method is used. The Equal Interval Width discretization method divides the range of observed values for an attribute into k equal sized intervals, where k0 is a user-supplied parameter. If an attribute a is observed to have values bounded by a min and a maxthen this method computes the interval width width( k ) = ( amax amin)/ k and con-structs thresholds at amin+i*width ( k ) where i= 1, ., k 1. The method is applied to each continuous attribute independently. Since this unsupervised method does not utilize decision values in setting partition boundaries, it is likely that classification information will be lost by binning as a result of combining values that are strongly associated with different classes into the same interval. But in our case this could make effective classification. (3) The intrusion (decision) rules are created using the reducts computed by the attribute reduction algorithm as templates. There are many attribute reduction algorithms such as dynamic reduct (Bazan et al. , 1994) and RA-Order algorithm (Wang and Tao, 2003), etc. But, until now, the most effective algorithm for large decision system re duction computation in practice is genetic algorithm (Wroblewski, 1995), which is used by most of the rough set tools such as Rough Enough (Anders, 1997) and Rosetta (Aleksander, 1999). In this paper, we proposed a hybrid genetic algorithm based on the attribute significance heuristic rule to find minimal reducts. This hybrid genetic algorithm decreases the training time and makes the generated classifier more effective and it is adjusted to fit the intrusion detection environment. This hybrid ge-netic algorithm is the key sub-algorithm in our RSC Algorithm. In order to make it clear, we first introduce the general Genetic Algorithms (GAs) and their extension in Part C, then we describe the key sub-algorithm in detail in Part D. For the testing dataset, the following step is done. (4) The same cuts computed from training dataset discretizaion method are first used to discretize the new object dataset. Then the rules generated are used to match testing objects to compute the strength of the selected rule sets for any decision class. The new object will be assigned to the decision class with maximal strength of the selected rule set. Part C: Finding minimal reduct using hybrid genetic algorithm based on SGF(1) Frame of hybrid Genetic Algorithm As the above “Part A” said, finding the rough set minimal reduct is viewed as minimal hitting set problem. For the discretized decision system L =( U , A d , V, f ), a multiset is constructed according to the above Definition 5, Part A. Subsequently, the hitting set of this multiset is computed using hybrid genetic algorithm.In our algorithm, a new operator named Bit-adapt is constructed. This new operator operates on the whole population and can guarantee each chromosome converges into one of the hitting sets.(2) Representation (Generation of the Initial Population) For the minimal hitting set problem, a straightforward choice of population is a set P of elements from 2A, encoded as bitvectors, where each bit indicates the presence of a particular element in the set. For example, assume that we have 10 condition attributes a1, a2, , a10 and we have a reduct candidate as a1, a4, a6, a9. Then the reduct candidate should be represented as: 1001010010.(3) Selection and recombination method The selection and recombination operator are imple