（计算机应用技术专业论文）基于支持向量机的中文网页自动分类系统.pdf

摘要 随着i n t e m e t 的发展，网络上的信息正在以前所未有的速度膨胀着，人类已经进 入了一个信息极其丰富的时代。人们通过网络了解世界、查找资料，但包容万象的 网络信息内容过于庞杂，如何查找到所需的某类资源成为人们日渐关注的问题。将 网络信息内容进行分类就是解决这个问题的一种很好的方法。若采用传统的人丁分 类的方法，不仅费时、费力，而且远远不能满足人们当前的需求。因此采用计算机 实现的文本自动分类就成为了必然的选择。 本文主要实现了个基于支持向量机的中文网页内容的自动分类系统。本文首 先介绍并实现了局域网内通过网卡截获网络数据报并对数据报进行重组，牛成了 h t m l 页面，再结合h t m l 页面内容提取技术得到了纯文本文件，这些保证了系统 的实时性。 本文对几种常用的中文自动分词算法进行了说明，并指出了不足之处，在此基 础上提出并实现了一种新的基于b i g r a m 的无词典分词利特征词抽取算法，这是本文 的一个创新之处。此算法不仅能够提高特征词抽取的准确性、很大程度上降低了特 征词的维数，提高了系统的分类性能，并且可以根据不同的训练集牛成不同的特征 词分词词典，具有很好的扩展性和灵活性。 本文在介绍和比较了几种常用的文本自动分类算法的性能和适用环境的基础 上，采用了支持向量机算法的序列最小最优化训练算法实现了中文网页的自动分类， 提高了系统的效率和准确性。系统可以在出现较大的分类误差时，通过对分类器重 新训练进行修正，不需要人工添加特征词等工作，具有很好的a 学习功能，为更广 泛的应用打下了基础。 最后的实验结果表明，此系统可满足一般文本分类系统的要求，并具有实时性、 灵活性、可扩展性、易用性及广泛的应用性等特性。 关键词文本分类；中文自动分词；b i g r a m ；支持向量机；序列最小最优化法 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e t i n f o r m a t i o ni ni n t e r n e th a sb e e ne n l a r g e da t i n c r e d i t a b l es p e e d an e wi n f o r m a t i o ne r ah a sc o m et ol i v e so fm e m b e r so fs o c i e t y u n d e r s t a n d i n gt h i sw o r l da n ds e a r c h i n gf o rt h ei n f o r m a t i o nf r o mi n t e r n e ta r eb e c o m i n g v e r yp o p u l a r h o w e v e r , t h e r ei ss om u c hi n f o r m a t i o no nt h ei n t e m e ta n di ti sb e c o m i n ga f o c u s e di s s u eo nh o wt og e tt h ek n o w l e d g en e e d e d t h ec l a s s i f i e di n f o r m a t i o ns h o u l db e ag o o ds o l u t i o n n e v e r t h e l e s s ，c l a s s i f i c a t i o nm a n u a l l yi sc o s t l ya n dt i m e c o n s u m i n g ，i t c a nn o ts a t i s f yt h em e m b e r so fs o c i e t y a sar e s u l t t h ea u t o m a t i cc l a s s i f i c a t i o nw i t h c o m p u t e r si sa ni n e v i t a b l ec h o i c e i nt h i sp a p e r , ac h i n e s ew e bp a g e sa u t o m a t i cc l a s s i f i c a t i o nb a s e do ns u p p o r tv e c t o r m a c h i n e ( s v m ) w a si m p l e m e n t e d f i r s t l y , t h ep r i n c i p l eo fh o w t oc a p t u r et h ei pp a c k e t s a n dg e n e r a t eh t m lf i l e sj nl a nw a sd i s c u s s e d s e c o n d l y , w i t ht h ec o n t e n t s e x t r a c t i o n t h eh t m lt e x tc o n t e n t sw e r eg e n e r a t e d i nt h ee n d ，t h r o u g ht h ec a p t u r eo ft h ei pp a c k e t s a n dt h ec o n t e n t se x t r a c t i o nf r o mh t m l ar e a l - t i m ea u t o m a t i cc l a s s i f i c a t i o ns y s t e r nw a s i m p l e m e n t e d s o m ec o m m o nc h i n e s es e g m e n tm e t h o d sw e r ed e s c r i b e da n dc o m p a r e da n dt h e i r d e f i c i e n c yw e r ea l s od i s c u s s e d b a s e do nt h e s e ，an e wd i c t i o n a r y f r e ec h i n e s es e g m e n t b a s e do nb i g r a mw a sp r o p o s e da n di m p l e m e n t e d t h i sm e t h o dd o e sn o to n l yi m p r o v et h e p r e c i s i o no ft h es e g m e n ta n dt h ec l a s s i f i c a t i o np e r f o r m a n c e ，b u ta l s o l e s s e nt h e d i m e n s i o n so ft h ec h a r a c t e r i s t i cs h a r p l y i na d d i t i o n v a r i o u sc h a r a c t e r i s t i cd i c t i o n a r i e s c a r lb eg e n e r a t e dw i t hd i f f e r e n tt r a i n i n gs e t sw h i c hi n t r o d u c et h ef l e x i b i l i t ya n dt h e e x p a n s i b i l i t y t h r o u g ht h ec o m p a r i s o no fs o m ec o m m o nu s e da u t o m a t i cc l a s s i f i c a t i o nm e t h o d s ，t h e s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ( s m o ) w a sa d o p t e da n di m p l e m e n t e dt oc l a s s i f yt h e c h i n e s et e x t s t h es y s t e mc a nb ea m e n d e dw i t ht h er e t r a i n i n go ft h ec l a s s i f i c a t i o n m a c h i n ei fab i g d i v e r g e n c ew a sf o u n d 。t h e r ei sn om a n u a lw o r kt ob eu n d e r t a k e nw h i c h b r o a d e nt h ea p p l i c a t i o no f t h es y s t e m ， t h ea n a l y s i so ft h er e s u l t sp r o v e st h a tt h i ss y s t e mc a ns u p p o r tt h eg e n e r a ln e e do f c l a s s i f i c a t i o nw i t hr e a l - t i m ea b i l i t y , f l e x i b i l i t y , e x p a n s i b i l i t y , u s a b i l i t ya n dh i g hu s a b i l i t y k e y w o r d s t e x tc l a s s i f i c a t i o n ，a u t o m a t i cc h i n e s es e g m e n t ，s u p p o r tv e c t o rm a c h i n e ( s v m ) ， b i g r a m ，s e q u e n t i a lm i n i m a lo p t i m i z a t i o n ( s m o ) i i ， 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 签名：至墓量日期：丕! 竺! ! ：鲨 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保 留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名： 五芰爨 导师签名日期：坦兰! ! ：蔓 第1 章绪论 1 1 文本自动分类研究的背景和意义 随着信息技术的不断发展，特别是i n t e r n e t 应用的广泛普及，人们可以从 i n t e r n e t 获取到极其丰富的信息。这些信息的内容包罗万象，t u ，人们往往只是对某 几类的信息内容感兴趣。若想快速准确的获得人们想要的某些特定信息，就要通过 对网页信息的内容进行分类来实现。对网页信息内容的分类可以通过人工分类和自 动分类两种方式完成，采用传统上的人工分类，可以做到组织结构清晰、分类精度 高、服务质量高，但这需要大量的人力资源，极其费时、费力且难以及时更新。随 着网页数量及信息内容的迅猛增长，人工分类已远远不能满足各种领域获取信息的 需要，显然再采用人工分类的方式进行网页信息内容的分类是不切实际的，那么就 需要采用另一种分类方式以计算机处理为核心的文本自动分类控术来完成。网 络信息的激增一方面增加了文本自动分类的迫切需求，另方面又为摹于机器学习 的文本自动分类方法准备了充分的资源和素材。 网络作为一种媒体，已成为人类日常生活中不可或缺的一部分。人们通过网络 了解世界、查找资料、更好的进行学习和生活。而男一方面，“垃圾”信息也在不断 的干扰着网络用户正常的学习和生活。比如有关暴力、色情、政治上反动等内容的 信息就严重的影响了广大网络用户的身心健康，并严重的危害着社会的安定团结。 因此，非常有必要对网络上传播的信息内容加以检测，判别及分类；并能自动识别 有害信息，对其加以监控和屏蔽，维护网络的信息安全。通过使用文本自动分类技 术就可以将各种网页信息分门别类，可以帮助人们更加快速准确的查找资料，也可 以及时的识别“垃圾”信息。 1 2 文本自动分类的问题描述 文本自动分类是自然语言理解的一个重要应用领域，是一个非常重要的信息组 织和管理的手段。文本自动分类是指将文本按一定的策略归于一个或多个类别中。 可以把文本自动分类描述成这样一个过程：对于每个新发现的文本，由文本自动分 类技术自动判断它与系统预先规定的各个文本类别之间的相关性，从而给每个新文 本指派一个类别。 从数学角度看，文本自动分类其实是一个映射过程，它将未标明类别的文本映 射到分类体系下已有的类别中。该映射可以是一一映射，也可以是一对多的映射， 因为某些文本不但可以与一个类别关联，也可以与多个类别相关联。该映射用数学 公式表示如下： 其中：a - ( d 。，d 2 ，”，d 。) b = ( c 。，c 。，c 。) 即：a 为所有待分类的文本集合，b 为给定分类体系下所有类别的集合。a 可以 为无限集合，但b 必须为有限集合。文本分类的映射规则f 是文本自动分类的关键。 它是系统根据已经掌握的每类若干样本的数据信息，总结出分类的规律性而建立的 。，。，彗当蛰2 茎至三耋堡垒：一。 ! 一 判别公式和判别规则。在已经确定的映射规则的摹础上，系统在遇到新文本时，根 据计算和判别规则来确定文本相关的类别。 文本自动分类涉及向量空间模型、特征提取、机器学习、文本相关性等方面的 学科领域。近年来，文本分类技术已经逐渐与搜索引擎、信息推送、信息过滤等信 息处理技术相结台，有效地提高了信息服务的速度和质量。 1 3 文本自动分类研究的技术动态 1 3 1 文本自动分类在国内外的研究现状 国外文本自动分类研究始于1 9 5 0 年末，h p l u h n 在这一领域进行了开创性的研 究。他首先将词频统计的思想用于文本分类中。1 9 6 0 年m a r o n 在j o u r n a lo fa s m 上发表了有关文本自动分类的第一篇论文”o nr e l e v a n c e ，p r o b a b i l i s t i c i n d e x i n ga n di n f o r m a t i o nr e t r i e v a ”。1 9 6 2 年h b o r k o 等人提出了利用因子分 析法进行文本的自动分类。其后许多学者在这一领域进行了很多卓有成效的研究工 作。总体说来，他们主要从文本的词频统计分析、句法分析、语义分析三个层次进 行研究。 国外的文本自动分类研究大体上可以分为二个阶段：第一阶段是1 9 5 8 年到1 9 6 4 年，主要进行文本自动分类的可行性研究；第二阶段是1 9 6 5 年到1 9 7 4 年，主要进 行了文本自动分类的实验研究；第二阶段从1 9 7 5 年开始，丰要进行文本自动分类的 实用化研究。 自2 0 世纪9 0 年代以来，随着世界范围内出现了新一轮的数字图书馆研究热潮 国外计算机界和图书情报界陆续展开了对因特网信息资源自动分类的研究，相关的 研究项目有： 1 北欧w m s 万维网自动分类项目。 2 诺伊斯等人的概念分析试验。 3 用于分类体系自动交叉参照的基于知识的系统k b s c r o s s 。 国外当前流行的文本分类方法有r o c c h i o 法及其变异方法，k 最近邻居法( k n n ) ， 决策树，朴素贝叶斯，贝叶斯网络，支持向量机( s v m ) 等方法。这些方法在英文以及 欧洲语种的文本分类上有广泛的研究，而且很多的研究表明k n n 和s v m 是英文文本 分类最好的方法。 国内文本自动分类研究起步较晚，2 0 世纪8 0 年代才开始进行。1 9 8 l 午候汉清 对计算机在文献分类工作中的应用作了探讨，并介绍了国外在计算机管理分类表、 计算机分类检索、计算机自动分类、计算机编制分类表等方法的概况。吴军、吴立 德和黄萱箐等人进行了中文语料自动分类的研究，他们以字或者词作为特征项构成 特征向量，以频率作为字或词的权重，利用一些分类算法构造分类器，取得了一定 的效果。 现有的中文文本分类系统从实现技术上可以分为：基于词典的自动分类系统和 基于专家的自动分类系统。 基于词典的分类系统主要有： l _ 莫少强的计算机辅助图书分类系统( 1 9 8 4 ) 。 2 朱兰娟的中文科技文献( 计算机类) 实验性自动分类系统( 1 9 8 6 ) 。 3 叶新明的中文文献自动分类系统( 1 9 9 5 ) 。 4 吴军的自动分类系统( 1 9 9 5 ) 。 5 刘开瑛等人的金融档案自动分类系统( 1 9 9 7 ) 。 基于专家系统的分类系统主要有： j ，同济大学计算机系的辅助分类专家系统( 】9 9 2 ) 。 2 东北大学图书馆的图书分类专家系统( 1 9 9 4 ) 。 3 长春地质学院图书馆的图节自动分类专家系统( 1 9 9 7 ) 。 4 基于神经网络优化算法的中文自动分类系统( 1 9 9 9 ) 。 我国文本自动分类的研究大体上正在经历从可行性探讨到辅助分类、自动分类 系统的发展阶段。关于中文文本分类的研究相对较少，国内外摹本上是在英文文本 分类研究的基础上采取相应的策略，结合中文文本的特定知识，然后应用于中文之 上，继而形成中文文本自动分类研究体系。 1 3 1 2 中文文本自动分类存在的问题 虽然国内的文本自动分类研究已经取得了一些成果，但是总的来说，仍然存在 以下问题： 1 缺少统一的中文语料库 由于没有标准的用于文本分类的中文语料库，各个学者分头收集自己的 训练文本集，并在此基础上开展研究，因此，系统的性能可比性不强。同时 由于财力人力有限，中文语料库的规模普遍不大。 2 向量空间模型的研究还不十分成熟 国内的学者，例如，吴立德和黄甍箐提出了如何选择特征项的问题，他 们提出可以使用字、词、概念作为特征项构成向量空间模型，并对以此为基 础的文本分类系统进行了初步的性能比较。但是在这方面的研究还没有深入 的开展，尤其是对概念的定义不清晰，没有全面的比较和测试。另外，在特 征项抽取算法方面也缺少系统而深入的研究。 3 测试标准不统一 由于缺少标准和用于分类的中文语料库，所以文本分类系统的性能测试 可比性较差，测试方法比较简单，通常只给出整个系统的准确率，很少分析 训练文档数量和质量对文本分类系统性能的影响。 4 没有深入开展未标记文本对文本分类系统性能的影响 5 文本分类技术与其它信息技术尚没有很好地结合。 国内的文本分类系统主要应用于图节馆等专业的信息处理机构，在信息 服务领域，除了与搜索引擎有所结合外，文本分类技术与其它信息技术还没 有很好地结合，没有得到充分的利用。 1 4 本文的主要研究内容 本文对中文文本自动分类中所涉及的各项主要技术都进行了全面的论述，并通 过试验测试方法对基于网页内容的中文文本自动分类研究中的三个关键技术局 ，一，。 i ：窑i 兰誊= 留生篁留盗一。， 域网内数据报截获和网页内容提取、中文文本自动分词利特征提取以及基于支持向 量机的中文文本分类算法进行了深入的研究： 1 实现了局域网内数据报的截获和h t m l 页面的生成； 2 提出了基于b i g r a m 方法的无词典中文文本自动分词算法和特征抽取技术： 3 通过试验分析了采用b i g r a m 中文文本自动分词算法和特征提取技术以及支 持向量机分类算法所实现的中文文本自动分类系统的分类性能。 论文工作主要分为四个部分。第一部分是网络数据报的截获及重组，是本文的 第二章；第二部分是h t m l 网页内容提取技术以及系统设计，是本文的第二章；第三 部分是基于b i g r a m 的无词典文本分词算法和特征提取的原理和设计，是本文的第四 章；第四部分是基于s v m 算法的中文文本分类算法的设计和实现，是本文的第五章。 其中，文章的第三、四部分是本论文的重点。由于时间和条件所限，本文只做以下 的工作： 1 只截获8 0 8 0 8 0 端口的数据报并进行重组； 2 。只对基于国标码的h t m l 网页进行内容提取； 3 只对某一特定信息内容进行文本自动分类，即二元分类。 1 5 论文组织 第一章绪论 第二章介绍了i p 数据报的截获及重组技术及实现 第三章基于国标码的网页内容自动提取技术及设计实现 第四章详细介绍并实现了b i g r a m 中文文本自动分词算法和特征提取技术 第五章详细介绍并实现了支持向量机中文文本训练和分类算法 第六章基于支持向量机算法的中文文本分类系统总体设计和实验结果及分析 最后是全文工作的结论和展望。 第2 章局域网内数据报截获原理和实现 若要对网页的信息内容进行自动分类，则获取网页是第一步。而获取网页首先 就要截获构成网页的i p 数据报，再对其进行分析和重组，牛成h t m l 文件。因此， 本章就首先介绍一下在局域网内实现数据报截获的原理和实现技术。 2 1t c p i p 协议簇介绍 t cp lp 是一个四层的协议簇系统，每一层负责不同的功能。具体的层次如图 2 一l 所示 心辩 缓 运簸联 燃臻裂 蝴聪 1 e l r t e t 、i ：- 1 1 p 穰e - m a i l 筹 l p 、l c m p 和晒m p 设镪鞭翘聪半艟接【jk 图2 1t c p i p 协议簇的四层 f i g u r e2 - 1t c p i pp r o t o c o l s 1 链路层：包括操作系统中的设备驱动程序和计算机中对应的网络接口 ，它 们一起处理与电缆( 或其他任何传输媒介) 的物理接口细节。 2 网络层：处理分组在网络中的活动，如分组的路由选择等。在tcp ，ip 协 议簇中，网络层协议包括ip 协议( 网际协议) ，i c mp 协议( in ter i le t 百- 联网控制报文协议) ，以及i g m p 协议( in ter ne t 组管理协议) 。 3 运输层：为两台主机上的应用程序提供端到端的通信服务。在tcp lp 协 议族中，有两个互不相同的传输协议：t cp ( 传输控制协议) 和udp ( 用 户数据报协议) 。tcp 为两台主机提供高可靠性的数据通信。它所做的工作 包括把应用程序交给它的数据分成合适的分组交给下面的网络层，确认接收 到的分组，设置发送最后确认分组的超时时钟等。由于运输层提供了高可靠 性的端到端的通信，因此应用层可以忽略所有这些细节。而另一方面，ud p 则为应用层提供一种非常简单的服务。它只是把称作数据报的分组从一台 主机发送到另一台丰机，但并不保证该数据报能到达另一端。任何必需的可 靠性必须由应用层来提供。 4 应用层：负责处理特定的应用程序细节。几乎各种不同的t cp jp 实现都 会提供下面这些通用的应用程序： t e l n e t 远程登录。 f t p 文件传输绑议。 s m t p 简单邮件传送协议。 h t t p 超文本传输协议。 ，些彗兰茎= 篁：j 鎏耋銮 ，一，一 。一 2 2 数据封装 当应用程序用tcp 传送数据时，数据被送入协议栈中，然后逐个通过每一层， 直到被当作一串比特流送入网络。其中每一层对收到的数据都要增加一些首部信息 ( 有时还要增加尾部信息) ，该过程如图2 - 2 所示。tcp 传给jp 的数据单元称作t cp 报文段或简称为tcp 段( t c ps e g m e n t ) 。ip 传给网络接口层的数据单元称作 1p 数据报o pd a m g r a m ) 。通过以太网传输的比特流称作帧( f r a m e ) 。 图2 - 2 数据封装 f i g u r e2 - 2e n c a p s u l a t i o n 汰太叫 图2 - 2 中帧头和帧尾下面所标注的数字是典型以太网帧首部的字节长度。准确 地说，图2 2 中ip 和网络接口层之间传送的数据单元应该是分组( p a c k e t ) 。分组 既可以是一个ip 数据报。也可以是ip 数据报的一个片段( f r a g m e n t ) 。 2 3 数据分用 当目的丰机收到一个以太网数据帧时，数据就开始从协议栈中由底向上传送， 同时去掉各层协议加上的报文首部。每层协议都要去检查报文首部中的协议标识， 以确定接收数据的上层协议。这个过程称作分用( d c m u l t i p l e x i n g ) ，图2 3 显示了 该过程是如何发生的。 第2 章局域网内数据报截获原理和实现 选人随柱 图2 - 3 数据分用 f i g u r e2 - 3d e m u l t i p l e x i n g i 峨l d p f | ：咎遵 ；e | f 目辨 分蹦 2 4 端口号 t cp 和u dp 采用1 6b i t 的端口号来识别应用程序。服务器端采用所谓的知名 端口号。例如，对于每个t c p 1 p 实现来说，f t p 服务器的t c p 端口号都足2 1 ， t e lne t 服务器的t cp 端口号都是2 3 ，h t t p 服务器的端口号是8 0 或者8 0 8 0 。 客户端通常对它所使用的端口号并不关心，只需保证该端口号在本机上是唯一 的就可以了。客户端口号又称作临时端口号( 即存在时间很短暂) 。这是因为它通常 只是在用户运行该客户程序时才存在。 2 5 ip 数据报格式 lp 是t c p ip 协议簇中最为核心的协议。所有的t cp 、u dp 、i c mp 及l g mp 数据都以ip 数据报格式传输。i p 数据报的格式如图2 - 4 所示： 北京l 业大学工学硕士学位论文 口1 51 63 l 4 俯 4 矗苗掷8 能聪并蹙掣 1 6 能想托鹰字宵彀) i 5 i 啦 疑缝r r 0 固 3 托 i3 能h + 镌j = 嚣 1 6 经轹1 5 酥忠 8 能啦存埘知 1 6 位泞黼黢瓣r2 。 f r r l l 8 髓鼢泌 3 2 f 灏l 嘲| = 3 2 位f 】的肾她鹱 选项f 如港有。，一 数锚 ， 图2 4i p 数据报格式 f i g u r e2 - 4i pd a t a g r a m 4 个字节的3 2 比特值以下面的次序传输： 首先是o 7 比特，其次8 1 5 比特，然后l6 2 3 比特，最后是2 4 3 1 比特。 这种传输次序称作b i ge n d i a n 字节序。由于t c p i p 首部中所有的二进制整数在网络 中传输时都要求以这种次序，因此它又称作网络字节序。 4 位首部长度指的是包括任何选项的首部以3 2 比特为单位的长度。由于它是一 个4 比特字段，因此首部最长为6 0 个字节( 1 5 * 3 2 8 = 6 0 ) 。普通i p 数据报( 没有任 何选项) 字段的值是5 ，也就是2 0 个字节。 总长度字段是指以字节为单位的整个l p 数据报的长度。利用首部长度字段和总 长度字段，就可以知道l p 数据报中数据内容的起始位置和长度。由于该字段长1 6 比特，所以i p 数据报最长可达6 5 5 3 5 字节。当数据报被分片时，该字段的值也随着 变化。尽管可以传送一个长达6 5 5 3 5 字节的l p 数据报，但是大多数的链路层都会对 它进行分片。而且，丰机也要求不能接收超过5 7 6 字节的数据报。由于t c p 把用户 数据分成若干片，因此般来说这个限制不会影响t c p 。 标识字段唯一地标识主机发送的每一份数据报。通常每发送一份报文它的值就 会加】。 t t l ( t i m e - t o - l i v e ) 牛存时间字段设置了数据报可以经过的最多路由器数。它 指定了数据报的生存时间。t t l 的初始值由发送主机设置( 通常为3 2 或6 4 ) 一旦 经过一个处理它的路由器，它的值就减去1 。当该字段的值为0 时，数据报就被丢 弃，并发送i c m p 报文通知发送主机。 8 位协议表明上层采取的是何种协议，比如t c p , u d p ，i c m p 等等a 首部检验和字段是根据1 p 首部计算的检验和码。它不对首部后面的数据进行计 算。i c m p 、i g m p 、u d p 和t c p 在它们各自的首部中均含有同时覆盖首部和数据 检验和码。当收到一份i p 数据报后，同样对首部中每个1 6 比特进行二进制反码的 求和。由于接收方在计算过程中包含了发送方存在首部中的检验和，因此，如果首 部在传输过程中发生了差错，那么接收方计算的结果不是全1 ，则i p 就丢弃收到的 数据报。但是不生成差错报文，由上层去发现丢失的数据报并进行重传。 2 6t o p 数据报格式 t c p 数据报的格式如图2 - 5 所示： 卜一噍瓣缀叫 卜一1 p 攮定瑷叫 l p 筠1 都 t c p 嚣都r ( 1 p 数姑 2 群雾簟2 僻雾爷 i 醇a 滁端阿蟹 1 6 辍| ；l 躺0 1 喜； 3 2 缭j2 爹蛰 3 2 稼确试垮垮 4 辩菇辫 u 雏 tsf k 瞧 绦黧( 6 德 翼尊yl 1 6 德留l 式小 g，nn i 每撼嫒赣翻 1 6 攮鬟惫崧铤 遴磷 。 i ?皴搿 一 i i 图2 - 5t c p 数据报格式 f i g u r e2 - 5 t c pd a t a g r a m 每个tcp 段都包含发送端和目的端的端i s l 号，用于寻找发送端和目的端应用 进程。这两个值加上ip 首部中的发送端ip 地址和目的端ip 地址可以唯一确定一 个t c p 连接。 一个ip 地址和一个端1 2 1 号也称为一个套接字( s o c k e t ) 。套接字对( s o c k e t p a i r ) f 包含客户ip 地址、客户端口号、服务器ip 地址和服务器端口号的四元组) 可惟一 确定互联网络中每个tcp 连接的双方。 ；，|；l上 ，。一，一，一，：坚鲨些；：；：彗i 2 生| 氅呈三；一，一一：。， 序号用来标识从tcp 发送端向tcp 目的端发送的数据字节流，它表示在这个 报文段中的的第一个数据字节。如果将字节流看作在两个应用程序问的单向流动， 则tcp 用序号对每个字节进行计数。序号是3 2 比特位的无符号数，序号到达2 3 2 1 后又从0 开始。 当建立一个新的连接时，syn 标志变i 。序号字段包含由这个丰机选择的该 连接的初始序号isn ( i n i t i a ls e q u e n c en u m b e r ) 。该丰机要发送数据的第一个字节 序号为这个is n 加l ，因为s y n 标志消耗了一个序号。 既然每个传输的字节都被计数，确认序号包含发送确认的一端所期望收到的下 一个序号。因此，确认序号应当是上次已成功收到数据字节序号加1 。只有ack 标志( 下面介绍) 为i 时确认序号字段才有效。发送a c k 无需任何代价，因为3 2 比特的确认序号字段和a c k 标志一样，总是t cp 首部的一部分。因此，一旦一 个连接建立起来，这个字段总是被设置为1 ，ack 标志也总是被设置为l 。 首部长度给出首部以3 2 比特为单位的长度。这个字段占4 比特，因此t cp 最 多有60 字节的首部。然而，在没有任选字段时的长度是20 字节。在t cp 首部中 有6 个标志位。它们中的多个可同时被设置为l 。 这六个标志位分别为： u r g 紧急指针有效。 a c k 确认序号有效。 psh 接收方应该尽快将这个报文段交给应用层。 rs t 重建连接。 syn 同步序号用来发起一个连接。 fi n 发端完成发送任务。 2 7 局域网内实现数据报截获的基本原理 在因特网上有很多使用以太网协议的局域网，许多丰机通过电缆、集线器连在 一起。当同一网络中的两台主机通信的时候，发送丰机将写有目的的主机地址的数 据报直接发向目的主机。但这种数据报不能在1 p 层直接发送，必须从t c p i p 协议 的i p 层交给网络接口，也就是数据链路层，而网络接口是不识别j p 地址的，因此 在网络接口数据报又增加了一部分以太网帧头的信息。在以太网帧头中有两个域， 分别为只有网络接口才能识别的发送主机的物理地址和目的主机的物理地址，物理 地址是与l p 地址相对应的4 8 位的地址。 传输数据时，包含物理地址的以太网帧从网络接口( 网譬) 发送到物理线路上， 如果局域网是由一条粗缆或细缆连接而成，则数字信号在电缆上传输，并能够到达 线路上的每一台手机。当使用集线器时，由集线器再发向连接在集线器上的每一条 线路，数字信号也能到达连接在集线器上的每一台丰机。当数字信号到达一台丰机 的网络接口时，正常情况下，网络接口读入数据帧。进行检查，如果数据帧中携带 的物理地址是自己的或者是广播地址，则将数据帧交给上层协议软件，也就是1 p 层 软件，否则就将这个帧丢弃。对于每个到达网络接口的数据帧，都要进行这个过 程。 然而，当乇机工作在监听模式下时，网络接口卡上收到的所有的数据帧都将被 ， 。一互：薹璺鎏罂丝墼堡堡塞誊坚矍型：些：，! ， 交给上层协议软件处理。而且，当连接在同一条电缆或集线器上的丰机被逻辑地分 为几个子网时，如果一台主机处于监听模式下，它还能接收到发向与自己不在同一 f 网( 使用了不同的掩码、i p 地址和嗣关) 的丰机的数据报。即在倒一条物婵信道 上传输的所有信息都可以被接收到。 现在举一个例子来明确的说明这个问题；假定现在有a ，b 两台牛机，通过集线 器相连在一个以太网内。现在a 机上的一个用户想要访问b 机提供的w w w 服务， 那么当a 机上的用户在浏览器中键入b 的l p 地址，得到b 机提供的w w w 服务时， 会发生以下的过程： 1 首先，当a 机上的用户在浏览器中键入b 机的地址发出浏览请求后，a 机的应用层得到请求，要求访问l p 地址为b 的主机； 2 应用层将请求发送到传输层进行连接； 3 传输层将数据报交到网络层，由网络层来选路； 4 由于a ，b 两机在一个共享网络中，i p 路由选择很简单：i p 数据报直接由 发送主机发送到目的主机； 5 由于a ，b 两机在一个共享网络中，所以a 机必须将3 2 比特的l p 地址转 换为4 8 比特的以太网地址，这一工作是由a r p 协议完成的； 6 链路层的a r p 通过工作在物理层的集线器向以太网上的每个卞机发送一份 包含目的i p 地址的以太网数据帧，在这份请求报文中中明：谁是b 机l p 地址的拥有者，请将你的硬件地址告诉我： 7 ，在同一个以太网中的每台机器都会”接收”( 请注意这一点! ) 到这个报文， 但正常状态下除了b 机外其他主机都会忽略这个报文，而b 机网p 驱动程 序识别出是在寻找自己的i p 地址，于是回送一个a r p 应答，告知自己的 i p 地址和以太网m a c 地址： 8 a 机的网卡驱动程序接收到了b 机的数据帧，知道了b 机的以太网地址， 于是以后的数据利用这个已知的以太网地址作为目的地址进行发送。 需要特别指出的一点是：由于以太网的工作原理，尽符b 机告知了自己是该i p 地址的所有者，但这并不意味着在一个网络内的其他丰机听不到a 和b 之间的通讯， 只是在正常状况下其他主机会忽略这些通讯报文而已。如果这些丰机不愿意忽略这 些报文的话，那么，对于在这个网段上的每台主机的网络接口而言，任何在网络上 传输的信息都是可以被听到的。如果将网络接口设置为混杂模式( p r o m i s c u o u s ) ， 一台丰机可以默不作声地监听到以太网内传输的所有信息。 2 8 局域网内数据报截获模块的设计和实现 上几节介绍了t c p i p 协议和的局域网内数据报截获的原理，下面介绍在l i n u x 系统上通过应用l i b n e t 和l i b n i d s 提供的函数库实现的局域网内数据报截获模块，程 序代码用c 编写。 2 & 1 基于l i b n e t 和l b n i d s 库的通用数据报截获 l j b n e t 是在l i b p c a p ( 即数据报捕获函数库) 基础上开发的数据报截获a p i 函 数接口，它提供的接口函数丰要实现和封装了与数据报截获有关的过程。l i b n i d s 一一，! ，! 些刍：型i 竖! ! ：一。， 的英文意思是n e t w o r k n t r u s i o nd e t e c ts y s t e m 1i b r a r y ，即网络入侵监测系统 函数库。它是在c 函数接口库1 i b n e t 的基础上开发的，它封装了开发n i d s 所需的 许多通用型函数。l i b n i d s 提供的接口函数可监视流经本地的所有网络通信及检查 数据报。除此之外，它还具有重组t c p 数据段、处理i p 分片包和监测i c p 端口扫描 的功能。 由于l i b n i d s 函数库已经提供了对i p 数据报重组、t c p 数据重组的功能，可以 直接将i p 数据报组合成为t c p 数据流，因此，本文直接使用其提供的函数写成了对 h t t p 协议的解码工作，生成了h t t p 页面。 丰要的数据结构有： s t r u c t t u p l e 4 t c p 连接参数，其 t u p l e 4 袁示i p v 4 ( u n s i g n e ds h o r ts o u r e 2 d e s t ；客户端和服务器端的端u 号 u n s i g n e dl o n gs a d d r , d a d d r ；客户端和服务器端的i p 地址 ； s t r u c th a l fs t r e a m t c p 连接一端的数据结构 c h a rs t a t e ； 套接字状态( 如t c pe s t a b l i s h e d ) c h a rc o l l e c t ；如果大干0 ，则保存其数据到缓冲区。h 西则忽略 c h a rc o l l e c tu r g ；如果人于0 ，则保存紧急数据，否则忽略 c h a r d a t a ； 正常数据的缓冲区 u n s i g n e dc h a ru r g d a t a ；紧急数据缓冲区 i n tc o u n t ；自从连接建立以来保存到”d a t a 缓冲区的数据宁节 数总和 i n to f f s e t ；保存到”d a t a ”缓冲区的首字节数据偏移量 i n tc o u n tn e w ；最近一次接收到的数据字节数；如果为0 ，则无数据 ，到达 c h a rc o u n tn e wu r g ；如果非0 ，表示有新的紧急数据到达 u _ i r as e q ；序列号 ui n ta c k 确认序列号seq； ui n tf i r s td a t as e q ；第个数据的序列号 j ； s t r u c tn i d s d a r m n i d s 参数 i n t nt c ps t r e a m s ；存放t c p _ s t r e a m 结构的h a s h 表大小。缺省值：1 0 2 4 i n tnh o s t s ；存放l p 分片信息的h a s h 表大小。缺省值：2 5 6 c h a r d e v i c e ； l i b n i d s 监听的接口设备名 缺省值一n u l l ，即由p e a p函数确定_iookupdev i n ts kb u f fs i z e ； ( l i n u x 内核) s kb u f f 结构人小。缺省值：1 6 8 i n td e va d d o n ； s kb u f f 为网络接l 保留的宁节数 如果d e va d d o n - - - 1 ，则由a i d si n i t 函数确定。缺省值：1 v o i d ( * s y s l o g ) o ；日志函数指针 i n ts y s l o g _ l e v e l ；如果n i d s j a a r a m s s y s l o n i d s _ s y s l o g ，则此宁段值 ，将确定日志等级i o g l e v e l 缺省值：l o ga l e r t i n ts c a nh u mh o s t s ；同时扫描的机器数目，存放端口扫描信息的h a s h 表人小。 1 2 。，。! ! ，：釜：薹2 警卫旦兰i 坚兰薹矍垩竺兰些，一，一， 如果为0 ，则关闭端u 扫描监测功能。 ，缺省值：2 5 6 ，即可以同时扫描2 5 6 个小同i p 地址对的连接 i n ts c a n _ n u m j a o r t s ；来自同一i p 地址所扫描的t c p 端l 】数上限。缺省值：1 0 i n ts c a nd e l a y ； 在两次端u 扫描f 的间隔时间上限( 毫秒) 。缺省值：3 0 0 0 v o i d ( + n o内存不足时被凋用，此时应终止当前进程_mem)0；n i n t ( + i p f i l t e r x s l r u c t i p +