（计算机应用技术专业论文）基于文件管理的网站安全动态监控的研究.pdf

摘要 基于文件管理的网站安全动态监控的研究 摘要 随着信息技术的发展，计算机系统和互联网应用日益广泛。各种 形式的网站蕴涵着丰富的信息，但由于网络连接形式的多样性和开放 性等特征，再加上网络技术本身存在着许多不安全因素，导致网站容 易受到黑客、木马程序等恶意攻击，造成网站文件被篡改、删除等诸 多问题，威胁着网络安全。在这种情况下，网站动态监控成了新的研 究热点。网站监控以文件管理为基础，目的为掌握文件的变化信息， 然后根据需要对文件进行增加、删除和修改操作。网站动态监控以最 普遍的信息存储形式文本文件为研究对象，具有很广阔的研究前 旦 一与天0 目前，文本内容比较算法主要应用在文件校对和求解最大匹配率 及最优匹配路径等方面，但在网站动态监控领域，对该方面的研究还 相对较少。针对这个问题，本文以网站文件为对象，结合网站文件的 特点和网站监控的应用需求，将文本内容比较算法应用在网站监控中， 设计并开发了“基于文件管理的网站动态监控系统”。该系统实现了网 站的定时监控，并通过提出的算法对网站文件进行管理。 首先，本文分析了已有的匹配技术和文本内容比较算法，并根据 网站动态监控的特点提出了“基于位置的文本内容比较算法”。该算法 匹配的过程相对简单，易读性强，可以有效的判断出文件是否被篡改。 其次，根据网站动态监控的需求，为实现文件的恢复和更新功能，利 i 北京化工人学硕十学位论文 用数据库分别保存原始信息和变化信息。最后，以提出的算法作为核 心算法，结合数据库，在e c l i p s e 和m ys q l 环境下开发了界面友好的 网站动态监控系统。 关键词：网站动态监控，信息安全，文件管理，文本内容比较算法， 篡改 i l a b s t r a c t r e s e a r c ho fd y n a m i cd e t e c t i o n s y s t e mf o r 、e bb a s e df i l em 哈n a g e m e n t 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 f o r m a t i o nt e c h n o l o g y , c o m p u t e rs y s t e ma n d t h ei n t e m e ti sw i d e l yu s e d v a r i o u sf o r m so fw e bc o n t a i nr i c hi n f o r m a t i o n b e c a u s et h en e t w o r kn o to n l yh a st h ef e a t u r e so fc o n n e c t i o nd i v e r s i t ya n d o p e n n e s sb u ta l s oh a sm a n yf a c t o r so fi n s e c u r i t y , r e s u l t i n gi n s i t e sa r e v u l n e r a b l et oh a c k e r s ，t r o j a n sa n do t h e rm a l i c i o u sa t t a c k s i tb r i n g sm a n y i s s u e ss u c ha st h ef i l e sa r ea l t e r e do rd e l e t e da n ds oo n ，s ot h en e t w o r ki s i n s e c u r e u n d e rs u c hc i r c u m s t a n c e s ，d y n a m i cd e t e c t i o nt e c h n o l o g yf o rw e b h a sb e c o m ean e wh o t s p o t d y n a m i cd e t e c t i o nb a s e do nf i l em a n a g e m e n t ， w h i c hi sd e s i g n e dt om a s t e rf i l ei n f o r m a t i o nw h i c hh a sb e e nc h a n g e d ，a n d a c c o r d i n gt ot h er e q u i r e m e n tt oi n s e r t ，d e l e t ea n dm o d i f y t h es t u d y o b j e c t i v eo fd y n a m i cd e t e c t i o nf o rw e bi s t e x tf i l ew h i c hi st h em o s t c o m m o nf o r mo fi n f o r m a t i o ns t o r a g e ，s ot h er e s e a r c ho fd y n a m i cd e t e c t i o n h a sv e r yb r o a dp r o s p e c t s c u r r e n t l y , t e x tc o m p a r i s o na l g o r i t h m sh a v eb e e nm a i n l yu s e di nt h e f i e l do ff i l ep r o o f r e a d i n ga n dt h ew a yt os o l v et h em a x i m u mm a t c h i n gr a t e a n dt h eo p t i m a lm a t c h i n gp a t h sa n ds oo n h o w e v e r , i nt h ed y n a m i c d e t e c t i o ns y s t e m sf o rw e b ，t h ea p p l i c a t i o no ft e x tc o m p a r i s o na l g o r i t h m si s i l l 北京化工人学硕十学位论文 v e r yl i t t l e t oa d d r e s st h i si s s u e ，a c c o r d i n gt ot h ec h a r a c t e r i s t i co ff i l e su s e d i nw e ba n dt h en e e do fa p p l i c a t i o n ，d y n a m i cd e t e c t i o ns y s t e mf o rw e bi s d e s i g n e da n dd e v e l o p e d ，w h i c hi sb a s e do nf i l em a n a g e m e n ta n du s eat e x t c o m p a r i s o na l g o r i t h m t h i ss y s t e ma c h i e v e st h er e g u l a rd e t e c t i o nf o rw e b ， a n dt h r o u g ht h ep r o p o s e da l g o r i t h mt om a n a g ef i l e so nt h ew e b f i r s t l y , t h em a i nt e c h n o l o g ya n dr e s e a r c hs t a t u so ft e x tc o m p a r i s o ni s a n a l y z e d a n dt h e n ，t e x tc o m p a r i s o na l g o r i t h mb a s e do nt h el o c a l i t yi s p r o p o s e da c c o r d i n gt ot h ec h a r a c t e r i s t i co ft h ed y n a m i cd e t e c t i o nf o rw e b t h em a t c h i n gp r o c e s so ft h i sa l g o r i t h mw h i c hi se a s yt oc o m p r e h e n da n d c a i l e f f e c t i v e l yd e t e r m i n ew h e t h e raf i l eh a sb e e nt a m p e r e dw i t h i s r e l a t i v e l ys i m p l e s e c o n d l y , a c c o r d i n gt ot h en e e d so fd y n a m i cd e t e c t i o n ，i n o r d e rt or e a l i z et h ef u n c t i o no fr e c o v e ra n du p d a t e ，t h eo r i g i n a li n f o r m a t i o n a n dc h a n g ei n f o r m a t i o nw e r es t o r e di nd a t a b a s er e s p e c t i v e l y l a s t l y , a d y n a m i cd e t e c t i o ns y s t e mf o rw e bw i t hf r i e n d l yi n t e r f a c ei sd e v e l o p e d w h i c hb a s e do nf i l em a n a g e m e n t t h es y s t e mi sd e v e l o p e du n d e rt h e c i r c u m s t a n c eo fe c li p s ea n dm ys q l k e yw o r d s ： f i l ed e t e c t i o n ，i n f o r m a t i o ns e c u r i t y , t e x tc o m p a r i s o n a l g o r i t h m ，i n t e r p o l a t i o nf i l ed e t e c t i o n i v 符号说明 符号说明 w i n d o w sa p i ( w i n d o w s a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e ) ：w i n d o w s 应用 程序接口 i r p ( i n p u t o u t p u tr e q u e s tp a c k a g e ) ：i o 请求包 m d ( m e s s a g ed i g e s t ) ：消息摘要 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 作者签名：堑兰i 垫日期： 关于论文使用授权的说明 一 、l 一) 叫d r l o j _ 7 d 学位论文作者完全了解北京化工大学有关保留和使用学位论文 的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属北 京化工大学。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编 学位论文。 保密论文注释：本学位论文属于保密范围，在上年解密后适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授 权书。 作者签名：3 矗壅蔓 日期： 导师签名： y io r 以 日期：塑! ! 二兰堕 第一章绪论 第一章绪论 随着信息技术的不断发展，信息安全被越来越多的用户所关注。网站安全问 题已经成为人们关心和研究的热点问题。本章首先介绍了课题产生的背景和意义， 然后介绍了安全监控技术的现状，最后介绍了论文所讨论的内容、意义以及整篇 论文的结构。 1 1 课题背景 近年来，网络的飞速发展，给人们的生活带来了很多便利，同时也带来了严 重的安全问题。对网站安全的威胁主要来自两个方面：外部入侵和内部攻击。外 部入侵主要指黑客或者木马程序对网站文件系统的增删和篡改；内部攻击主要指 内部人员凭借自己对系统的熟悉，对文件进行更改，此外还包括内部人员由于误 操作造成文件的变劐1 。2 j 。 无论是外部入侵，还是内部攻击都会产生很多安全隐患。而安全问题的威胁 之一就是病毒的攻击，目前比较流行的病毒入侵方式是网页挂马，通过篡改网页 的代码将木马嵌入网页中，当用户打开网页的同时，木马开始运行。网页挂马带 来的危害很大，除了使本地计算机c p u 使用率极高以外，还可能造成存储在计算 机中的资料被篡改或者信息丢失的后果【3 - 6 1 。从网站管理者的角度来讲，必须首先 保证网站的安全性，才能确保网站的持久性。另外，网站作为信息平台，代表着 公众形象，如果被认定网站存在病毒，会使网站的浏览量减少甚至为零，所以保 证其安全性尤为重要。不仅对于管理者，作为普通用户也需要保证文件的安全性。 面对木马篡改等威胁，人们开始希望自己的文件可以得到保护，一旦发生变化， 例如被篡改、被删除等，能够及时地发现。如何对网站安全进行实时的监控逐渐 成为信息安全领域的一个重要研究课题。 现有的数据保密方式有数据加密和访问控制两种【7 - 9 1 。包括一些入侵检测系统， 通过监测用户在系统或者网络上的活动，从而发现企图破坏或非法进入系统的行 为，也主要利用这两种方式以及曰志文件来实现监测【9 】。另外，随着技术人员的不 断研究，过滤驱动技术在不断提高，利用这种技术保护计算机文件系统的模型正 在发展【。 上述数据保密的方式一旦被破坏，文件就有可能被篡改，而过滤驱动技术有 一定的开发难度，大多数以理论研究为主】。为了更好地对网站进行监控，可以 将网站监控与文件管理相结合，本论文就针对该问题进行了探讨。 北京化工大学硕士学位论文 1 2 网站动态监控系统意义 文件是信息的主要载体，在信息安全领域，对文件的保护至关重要，对文件 的新增、修改和删除等操作需要进行准确的记录。 通常，安全监控的对象可分成两类：操作和信息。其中，操作主要是指用户 人为产生的操作行为，而信息则主要是指系统的文件和文本信息【1 2 1 。 由于网站的特殊性，可能经常需要人为操作，而人为操作具有高不确定性和 破坏性等特点。因此网站动态监控也包括两方面，一方面监控网站文件的信息是 否准确和完整；另一方面监控网站文件是否被他人非法操作。从这个角度讲，网 站动态监控系统就是对文件信息的变更，以及人为操作的相关信息进行记录。当 发生人为操作时，可以根据变化的内容进一步处理，从而避免目录结构被破坏及 文件内容被更改。由此可见网站动态监控系统的实现对于保证网站信息的安全性 具有重要意义。 1 3 安全监控技术现状 实现安全监控的技术较多，按照实现机制的不同可以分为5 个层次：基于 w i n d o w sa p i 的技术、基于文件系统过滤器的技术、基于拦截系统调用的技术、 利用防火墙技术及数据加密技术。 1 3 1 基于w i n d o w sa p i 的技术 w i n d o w s 用户可以通过应用程序接i z l ( a p i ) 进行系统编程，原因在于a p i 提供 了外设控制的函数【1 2 】。可以同时提供同步和异步( 同步或异步指的是操作系统提 供的同步或异步机制，从用户程序的角度讲使用操作系统同步机制的代码仍然可 以为异步的) 监测。函数f i n d f i r s t c h a n g e n o t i f i c a t i o n 函数能够监控包括文件名称、 文件大小等文件属性发生变化的最后时间，以及相关的变化信息。该函数返回一 个监控句柄( n o t i f i c a t i o nh a n d l e ) ，可以设置监控的条件，当满足监控条件时， n o t i f c a t i o nh a n d l e 将处于激发状态，这时用户程序就可以知道所监控的文件发生 的变化。通过该句柄获得信息后，可以进行自定义的处理操作，当处理结束后必 须将该句柄设置为去激活状态，准备进行下一次激活。 使用基于a p i 函数的方法提供了文件变更监控处理，执行效率高，但是 f i n d f i r s t c h a n g e n o t i f i c a t i o n 函数使用比较复杂，而且该技术不具备应用到其他功能 的扩展性。 2 第一章绪论 1 3 2 基于文件系统过滤器的技术 内核模式的程序具有最高的操作权限，这一点是使用文件系统过滤器作为安 全监控的核心技术最主要的原因。不论是病毒感染文件的操作，还是已经被感染 的文件把病毒传染给其他的文件的操作，都需要在内存中进行的，而涉及到内存 管理和中断操作的指令只有在内核模式下才能进行有效的监控，在用户模式下根 本无法看到这些指令。f o 管理器收到用户请求时会产生f o 请求包( i r p ) ，所有 针对文件的操作所发出的i r p 首先经过的都是位于文件系统上层的过滤驱动，为 此上层过滤驱动就可以获得操作内容并对内容进行以分析，一旦发现异常操作， 特别是有病毒特征的操作，就发出警告以提示用户进行有选择的处理( 比如删除 等) ，该技术的本质在于产生i r p 和过滤驱动分析所产生的i r p 基本是同步的，这 样就可以保证实时性【1 1 , 1 ) - 1 5 】。该技术实现了在系统级上的监控，随着信息技术的不 断发展，执行效率会不断提高。但由于该技术是通过病毒的特征，判断操作是否 为异常操作，进而发出警告，一方面由于病毒的种类层出不穷，因而可能会造成 遗漏；另一方面也由于某些正常操作与病毒的特征相似，可能造成分析错误。 1 3 3 基于拦截系统调用的技术 i 被称为w i n d o w s 应用程序接口挂接技术的拦截系统调用，它的核心功能是利 用转向挂接代码的方式完成拦截调用。也就是说当一个活动进程空间中的一块代 码( a p i ) 被调用时，转向另一段由编程者所提供的挂接代码，原来应该被调用的功 能就被拦截。该技术一般由d l l 注入和a p i 拦截两部分相结合来实现【1 2 , 1 6 】。将监 控程序写入自己的d l l 程序中并注入相应模块，对函数进行拦截【1 7 1 9 1 。基于拦截 系统调用的技术执行效率较高，但是实现复杂度也较高。 1 3 4 防火墙技术 防火墙是一种访问控制技术，有助于提高计算机的安全性，可以更好地保护 计算机上的数据免遭破坏，并针对那些未经邀请而尝试连接的用户或程序( 包括 病毒和蠕虫) 提供了一条防御线。防火墙技术( 主要是包过滤、应用网关、子网 屏蔽、代理服务等) 可以在机构的网络和外界之间设置障碍，以这种方式一方 面阻止对本机构信息资源的非法访问，另一方面也可以阻止机要信息、专利信息 等涉密信息从该机构的网络上非法输出。从输入和输出两方面起到监控的作用。 从这个角度讲，防火墙就是一道关卡，它实现了输入和输出两个方向的控制。但 是防火墙的安全保障能力仅限于网络边界，如果存在的不安全通信不需要经过 防火墙( 例如内部攻击) ，防火墙则形同虚设【2 0 l 。 北京化工火学硕十学位论文 1 3 5 数据加密技术 目前，随着信息技术的发展，文件的加密方法有很多种，在传输过程中通常 采用“双密钥码进行加密【2 0 - 2 2 j 。与访问控制相比，数据加密是相对比较安全的 方式，相当于设置了密码，因此即便第三方利用一些高端技术获取到文件数据， 但由于其无法正常解密，也就无法使用该数据，准确的说根本无法浏览该数据。 实际上，数据加密的核心就是网络中的每一个加密通信者拥有两个相对应的密钥： 一个是加密密钥，该密钥可以公开；另一个是解密密钥，该密钥必须保密。该技 术在发送和接收前增加了一个加( 解) 密过程，发送方使用接收方的公开密钥发 送报文，接收方使用自己的解密密钥解密。由于加密和解密使用不同的密钥，因 此第三方很难从截获的报文中解出原文，这对于文件具有很好的保护作用。 1 4 论文的内容 现有的安全监控技术多以文件为监控对象，通过拦截异常操作的方式，达到 监控的目的，但是由于黑客、木马程序的复杂化和多样化，监控一旦出现遗漏或 错误都会造成严重后果。因此监控除了需要掌握变化的信息外，是否能够恢复到 指定时间的文件内容以及能否根据需要对文件进行更新同样具有重要的意义。通 常情况下，对于文件内容的更改计算机很难识别其是否是符合需求的，所以监控 系统需要提供对发生的变化进行进一步处理的功能，由用户对发生的变化进行确 认，从而满足更新或者恢复的需求。 本课题研究目标主要是结合文件管理，设计一种适合文本文件监控的算法， 并应用该算法实现网站动态监控系统，及时掌握网站系统文件变化的信息，同时 对发生的变化及时进行处理，当发生了病毒攻击造成文件被篡改时，可以采用恢 复的补救方式，减少恶意攻击的损失。 论文首先描述了目前安全监控的现状，提出了一种监控文本内容变化的文本 内容比较算法并与现有的算法进行比较，分析其优缺点。鉴于该算法适合应用在 对网站系统文件的监控中，本文设计了基于该算法的网站动态监控系统。 论文解决的主要问题如下： ( 1 ) 提出一种监控文本文件内容变化的算法。 ( 2 ) 将所提出的算法与现有算法进行比较。 ( 3 ) 设计网站动态监控系统。 ( 4 ) 将所提出的算法与监控相结合，实现网站动态监控系统。 4 第一章绪论 1 5 论文的意义 随着现代社会对信息资源需求的激增，信息技术突飞猛进，计算机网络也得 到了迅猛地发展。网络安全问题越来越多地被关注。如何有效的管理和监控网站 文件使之更安全成了目前迫切需要解决的问题【2 3 埘】。 由于网站文件多是文本文件，网页篡改多数是通过篡改文本文件，从而实现 对网站的篡改，因此对网站的监控可以在文件的管理基础上实现，通过监控文本 文件的变化，来了解网站系统是否安全。为了判断文本文件的内容是否发生变化， 确定变化的内容，并尽量降低系统开销，论文提出了一种基于位置的文本内容比 较算法。算法利用位置优先原则，简化了比较过程。实验结果表明该算法可以应 用于文件监控，而且易于理解。 将该算法应用于网站动态监控系统，利用m ys q l 数据库存储原始目录的相 关信息，对文件当前的信息与初始信息相比较，从而得出监测结果，对于文件及 目录的变化，实现了恢复功能，有效地解决了文件被篡改的问题；同时提供了发 生变化的时间，可以根据需要选择时间，从而实现了更新文件的功能。除了准确 地判断文件的变化以外，该系统不仅可以有效地防止对文件的恶意篡改，而且对 于用户的误操作也提供了恢复功能，同时操作方便。该系统对网站动态监控具有 十分重要的意义。 1 6 论文的结构 全文共分五章，具体安排如下： 第一章绪论 首先说明了课题背景和现状，然后讨论了本论文研究的内容、意义和整个论 文的框架。 第二章监控文本文件变化的文本内容比较算法 介绍了一种基于位置的文本内容比较算法。通过标志位判断，再利用元素位 置进行取舍，从而得出文件内容比较的结果。并将该算法与已有算法进行对比， 总结算法的优缺点。 第三章网站动态监控系统的设计 从数据库角度设计网站动态监控系统的架构。根据系统要达到的功能设计数 据库的表的结构。 第四章网站动态监控系统的实现 描述系统实现的目标和完成的主要任务，结合网站动态监控系统的功能阐述 北京化工大学硕士学位论文 系统的实现，通过监控实例介绍系统的特点。 第五章结论 总结了本文的研究成果，并指出了需要进一步开展的工作。 6 第二章文本内容比较算法 第二章文本内容比较算法 目前对于文件内容的比较的研究相对较少，按照其目标不同可以将文件内容 比较分为两种：一种是定量的比较，既能判断文件是否被改变，又能定位到不同 之处，往往针对的是文本文件。另一种是定性比较，只能判断文档是否被改变而 不能直观的知道文件的具体差异，这种比较对所有文件都适用，主要利用文件的 特征值、签名文件或者加密算法判吲2 5 1 。而对于二进制文件一般采用指令相似性 【2 6 】、结构化比较【2 7 。2 引、特征提取【2 9 】等来实现。 已有的定量比较的算法主要有两种：一种是简易的文本内容比较算法，另一 种是基于图的文本内容比较算法。对于字数比较少的文本文件可以采用前者，将 源文件( 被监测文件) 和目标文件( 监测时用来与源文件内容进行比较的文件) 的内容从头向后一对一地进行比较，如果发现内容不相同，即为出现了异常，利 用循环来判断异常的位置【3 0 】。后者则使用逆序循环，利用递归模型完成文本内容 比较。而定性比较的算法中被广泛使用的是m d 5 算法【3 。本文主要讨论的是定量 比较，对于上述两种定量比较方法当文件中变化的内容比较多时，前者速度会比 较慢。又因为后者需要缓存计算信息，因此增加了系统开销，并且由于基于图论， 所以过程比较复杂。 为了解决上述问题，本文提出了一种基于位置的文本内容比较算法。通过对 标志位进行判断，再根据元素位置进行取舍，从而得出文件内容比较的结果。 2 1 现有的字段匹配技术 2 1 1 简单的基于字符的字段匹配技术 假设有两个字符串进行比较，首先，将两个个字符串的单词分别进行分词， 按照顺序提取出来；然后，遍历第二个字符串，将从第一个字符串中提取出来的 每一个单词，在第二个字符串的单词中搜索。并且将匹配的单词个数被记录下来。 由于该算法涉及到单词的排序，因此单词的排序决定了算法的复杂性。算法的时 间复杂度为o ( l o g ) ，”表示两个字符串中单词的最大个数。 2 1 2 处理单词缩写的回归字段匹配技术 该算法考虑了缩写因素，按照缩写词与原单词的相对位置不同，分成前缀、 前缀和后缀组合、首字母组合以及前缀串联四种形式。当a 和b 是相同的单词或 7 北京化工人学硕上学位论文 一个是另一个的缩写时，匹配度是l ，否则是0 ，同时考虑最高匹配度问题。每一 个a 的单词和b 的单词串进行匹配，记录下单词匹配度最高的情况【3 2 1 。算法的复 杂度为2 次幂的。给定a 和b ，a 中的每个单词都必须和b 中的每个单词匹配。在 最坏情况下，a 的所有单词都需要和b 的所有单词进行比较。这里的除了可能是单 词匹配外，也可能是单词组成的句子进行匹配【3 2 】。 2 2 已有的文本内容比较算法 2 2 1 简易的文本内容比较算法 通过将源文件的内容和目标文件的内容从头向后一对一地进行比较，当内容 不相同时定义为不匹配，并将不匹配分为删除、修改和插入三种类型。算法的关 键是一旦发生不匹配，就需要将不匹配的类型( 删除、修改和插入) 记录下来， 还可以进行不匹配字数的累加，然后跳过不匹配的部分，从匹配的位置继续进行 比较。 在比较的过程中，当出现不匹配的字符时，需要用一个三层循环来解决，最 外面的循环的作用是控制需要查找的不匹配个数，当循环结束时，它的值应该是 三种不匹配类型的最大个数：中间的一层循环和最内层循环分别代表不匹配位置 的源文件的字符位置和目标文件中的字符位置，作用是控制使这些字符进行相互 比较【2 8 1 。 优点：较准确、智能化地统计出删除、修改和插入的字符。 缺点：当文件中变化的内容比较多时，该方法速度会比较慢。 2 2 2 基于图论的文本内容比较算法 利用文本是流式的特点，该算法将两个文本之间的所有匹配关系转换成一个 很规则的矩阵，将源文件内容写入矩阵的首行，将目标文件的内容写入矩阵的首 列。匹配的过程就转化为如何从第1 行第1 列单元格找到一条路径，该路径匹配 的元素最多。匹配的规则为下一次只能与当前位置向右、向下或者向右下方的元 素进行比较，特别的，如果当前元素已经匹配，则只能与右下方的元素进行下一 步匹配。当到达矩阵的右边界或者下边界时，匹配结束。根据向右、向下和向右 下方三种情况，将下一次匹配的区域划分成三部分，如果设置匹配为l ，不匹配为 o ，那么，求最大匹配点数，就转化为从起点出发，将按照各区域不同路径比较所 获得的最大匹配值。 该方法使用递归的数学原型，结合逆序循环计算目标文件和源文件的最大匹 8 第二章文奉内容比较算法 配数，并在能够得到最大匹配数的所有路径中，选择最短路径作为匹配的最优路 径。也就是说该算法寻找一条匹配数最大、匹配路径最短的路径作为结果，通过 匹配实现比较。 优点：计算出目标文件与源文件的最大匹配数和最优匹配路径。 缺点t 匹配过程比较复杂，特别是对于没有接触过图论的人员比较难理解， 效率相对较低。 2 2 3 基于m d 5 的文本内容比较算法 m d 算法的本质为输入为变长的信息，经过压缩后，输出为一个定长的值。这 一输出可以被看作是原输入的摘要值( m e s s a g ed i g e s t ) ，若输入的信息被改变了， 则输出的定长值( 摘要) 也会改变，m d 算法因此得名。由于是压缩后的摘要值，所 以输入的长度大于输出的长度，进而会出现不同的输入产生相同输出的可能。m d 5 是由r o nr i v c s t 设计的散列函数系列的第5 个。然而对于信息摘录函数而言，给定 一个输出，要求出一个输入以产生相同的输出，这种情况是计算不可行的。m d 5 以一种充分而复杂的方式将各比特弄乱，每个输出比特都受到每一个输入比特的 影响【2 9 】。 基于m d 5 的文本内容比较算法的步骤如下： 第一步，读取用户指定的目录中的所有文件，并计算初始时的m d 5 值。在数 据库中保存诸如文件的完整路径名，上次检查的日期及m d 5 值等信息。 第二步，定时计算文件的m d 5 值并将m d 5 值作为特征信息与数据库中的 m d 5 值相比较，从而监测文件是否被篡改。 第三步，如果计算出的m d 5 值与数据库中存储的初始值相同，则表示该文件 没有变化。相反，如果不同于初始值，则表示自上次监测时间后文件内容发生了 变化【2 3 1 。 优点：快速、准确的判断出文件是否发生变化。 缺点：虽然该算法被广泛应用，但是如果应用在文件比较中只能做定性判断， 无法确定文件变化的具体位置。 2 3 用于监控文本文件变化的文本内容比较算法的特点 用于监控文本文件变化的文本内容比较算法不同于普通的比较算法，其特殊 性表现在：监控最主要的作用是监测文件内容是否发生变化，但是对于所监测出 的变化是否是最小差异要求并不严格。所以算法必须准确监测出源文件与目标文 件的差异，但不需要保证最大匹配，进而可以提高比较速率；当发现文件发生变 9 北京化工大学硕：l ：学位论文 化时，还需要作进一步是否保留该变化的操作，也就是说，不仅判断出是否发生 变化，还需要确定发生变化的具体位置，所以必须使用定量的算法；被监测的文 件可能很大，变化的内容也可能很多，所以要求算法尽量快速，同时系统开销尽 量小。 2 4 基于位置的文本内容比较算法 基于位置的文件比较算法是通过比较文件内容，最后得到发生变化的元素， 所以如果确定一种相似性判断的标准( 例如，发生变化的元素个数等) ，根据该算 法的结果可以从字面上判断论文抄袭等问题，当然该算法并不涉及语义等更为复 杂的分析，不能从字义上判断论文是否为抄袭。 2 4 1 算法简介 所谓基于位置，即位置优先原则，就是按照每个元素在文件中的位置设置了 优先权，在匹配的过程中，位置排在前面的元素优先进行匹配。同时，当两个元 素都可以进行匹配，但是不能同时匹配的时候，也会优先考虑前面的元素。 假设源文件有m 个元素，而目标文件有1 1 个元素。首先，分别为源文件和目 标文件设置一个数组t m 和z ：t n j 用来存放每个元素的标志位。其次，比较源文 件( 假设为第i 个元素) 和目标文件的对应位置的元素是否相同，如果不相同则从 目标文件当前位置向后查找，如果可以找到与源文件元素匹配的元素( 假设为第j 个元素) ，那么设置儿j l - ，j - 1 ，同时 l l j2 ，；如果没有找到可以匹配的元素，则 设置t d l j j _ - 1 ，同时心【l j2 。这样当把源文件的所有元素都与目标文件比较 一次以后，就得到两个已赋值的数组( t s m t t l l t d n ) 。第三步，将数组嬲 聊】中 每一个值分别当作起始元素，然后对其后面的数值进行判断，记录递增元素个数， 最后比较每一个值作为起始元素所得到的d m l 数组中递增元素个数，取个数最多 的一个作为结果，假设该元素的下标为k ( 当然，为了简化过程，可以直接选择数 组硒l 所j 中最小值作为起始元素) 。第四步，d 悼j 前面的值全改为1 ，其后面非递 增值也改为1 。最后，根据数组”i m l 和l d t n l 的值输出结果，结果可以分为两部 分：数组d i m l 中为1 的元素为“删除的元素；数组z ) t n j 中为1 的元素为“插 入”的元素。另外，在整个匹配的过程中，如果已经匹配成功过的元素不能再参 加其它元素的匹配( 即每个元素只能和一个元素成功匹配) 。 1 0 第一二章文本内容比较算法 2 4 2 算法改进 该算法是根据位置优先的原则来进行判断的，如果目标文件中有多个可以与 源文件中元素进行匹配的元素，即目标文件中有相同的元素，根据位置优先的原 则，只有前面的内容有匹配的机会，这样，有可能会造成匹配个数降低。为了解 决这个问题，可以对算法做进一步的改进，在选择匹配元素的时候，尽量从前一 元素匹配的位置后面进行查找。这样就增加了元素匹配后成功被选中的机会。一 方面提高了匹配率，另一方面，由于是从前一元素匹配的位置后面进行查找，也 缩短了查找时间，提高了算法的效率。 例：源文件中的内容为：abcdbc 目标文件中的内容为：caibcbedc 首先，根据源文件和目标文件的元素个数，设置两个数组t s 6 】和t d 9 】。其 次，把源文件的所有元素都与目标文件做比较，为t s 6 】和t d 9 】两个数组赋值。 t s 6 = 0 , 3 ，4 ，7 ，5 ，8 和t d 9 = - 1 ，1 ，一1 ，l ，1 ，一1 ，一l ，l ，1 。 可以看出最终t s 6 】非负元素所对应的源文件内容应该为： abcdc 输出结果为： 删除的内容为( t s i - 一1 ) ： 第1 行第5 列b 增加的内容为( t d j 】= 一1 ) ：第l 行第1 列c 第1 行第3 列i 第1 行第6 列b 第1 行第7 列e 2 4 3 算法优缺点 优点：该算法可以准确地判断出文件内容是否发生变化，以及发生变化的具 体位置( 算法按照空格来分隔元素，并且分别以行号和列号标识元素的位置) 。同 时整个过程比较直观，更容易理解。在匹配的过程中，只用了数组进行存储源文 件和目标文件的各个元素的标志位，然后通过修改标志位来确定文件是如何变化 的。不需要进行复杂的判断，也不需要存储很多相关的信息。 缺点：由于算法是基于位置优先的，也就是说在第k 位和第胁j 位都可以匹 配，同等条件下，如果两者只能保留一个，那么优先考虑第k 位，而舍弃第k + l 位。因此可能会造成匹配元素个数的减少。 北京化工大学硕士学位论文 2 5 实验结果 源文件与目标文件作比较的时候，算法对重复元素的处理方式不同可能造成 结果不同，所以实验中分别比较无重复元素的情况和有重复元素的情况。另外， 考虑到比较的内容有多行时，匹配可能出现错误。综合以上两点考虑，实验结果 如下。 2 5 1 源文件和目标文件中无重复元素的情况 例1 - 源文件中的内容为：ab c d e f 目标文件中的内容为：b c d g h 表2 - 1 无重复元素内容比较结果表l t a b l e2 - 1c o n t r a s t i v er e s u l t lo f c o n t e n tw i t h o u tr e p e t i t i v ee l e m e n t 结果具体内容 第l 行第l 列：a 删除第l 行第5 列：e 第l 行第6 列：厂 第1 行第4 列：g 插入 第1 行第5 列：h 例2 ：源文件中的内容为： f r a m es r c = i n d e x h t m 7 目标文件中的内容为： 结果如表2 1 、2 2 所示，可以看出，对于比较无重复元素的内容，基于位置 的文本内容比较算法可以正确判断更改的内容，由于以空格符号分割字符，所以 可以通过行号和列号表示变化元素的位置。 1 2 第二章文本内容比较算法 表2 2 无重复元素内容比较结果表2 t a b l e2 - 2c o n t r a s t i v er e s u l t 2o f c o n t e n tw i t h o u tr e p e t i t i v ee l e m e n t 结果具体内容 第2 行第3 列：n a m e = t o p f r a m e ” 删除 第3 行第2 列：s r c = k i a h t m 哆 第3 行第2 列：s r c = x i a h t m ” 插入 第1 行第3 列：n a m e = t o p f r a m e 2 5 2 源文件和目标文件中有重复元素的情况 例3 ：源文件中的内容为：i a b i b i c d 目标文件中的内容为：ab f biedegabibi 表2 - 3 有重复元素内容比较结果表l t a b l e2 - 3c o n t r a s t i v er e s u l t lo fc o n t e n tw i t hr e p e t i t i v ee l e m e n t 结果具体内容 第1 行第7 列：c 删除 第1 行第8 列：d 第l 行第l 列：a 第l 行第2 列：b 第l 行第3 列：厂 第l 行第4 列：b 插入 第l 行第6 列：e 第1 行第7 列：d 第1 行第8 列：e 第l 行第9 列：g 例4 ：源文件中的内容为： 目标文件中的内容为： 结果如表2 3 、2 - 4 所示，可以看出，对于比较有重复元素的内容，基于位置 的文本内容比较算法利用位置优先原则判断更改内容。 1 3 北京化t 大学硕上学位论文 表2 - 4 有重复元素内容比较结果表2 t a b l e2 - 4c o n t r a s t i v er e s u l t 2o fc o n t e n tw i t hr e p e t i t i v ee l e m e n t 结果具体内容 第3 行第1n - f r a m e 删除 第3 行第2 列：s r c = x i a h t m 第2 行第1 列： 插入 第5 行第1 列： f r a m e 第5 行第2 列：s i c = x i a h t m 哆 2 6 小结 与简易的文本内容比较算法相比，后者虽然可以判断出文件是否发生变化， 但是考虑到该算法使用多重循环进行整个匹配，。当文件内容过多时，会影响比较 的速度，造出系统开销过大。而基于位置的文本内容比较算法则通过标志位进行 判断，过程相对简单，一定程度上提高了比较的速度。 与基于图论的文本内容比较算法相比，虽然后者可以计算出最大的匹配率， 同时计算出最优的路径。但匹配过程比较复杂，特别是对于没有接触过图论的人 员比较难理解。此外对于文件内容监控来讲，主要的目的是判断文件是否发生变 化，而源文件和目标文件的最大的公共部分以及寻找这个公共部分的最优路径不 是很重要，基于位置的文本内容比较算法将文件的比较转化为对于源文件各个元 素的标记的问题，相对容易理解，而且过程也相对简单，不仅能够判断文件内容 是否发生变化，也可以确定变化的具体内容。 与基于m d 5 的文本内容比较算法相比，后者可以准确的判断出文件是否发生 变化，但是不能确定发生变化的具体位置，给后续的更新和恢复造成很大的困难。 而基于位置的文本比较算法不会出现该问题。 很多情况下，基于位置的文本内容比较算法与已有算法的结果是一样的，可 能在有些情况下，结果是不同的，原因有两种：第一，由于目标文件有相同的元 素，所以在匹配的时候可能会出现选择的不同，对于这种原因所引起的结果不同， 通常情况下源文件和目标文件所匹配的元素是一样的：第二，由于基于位置的文 件比较算法导致有些匹配不能被成功的保留，从而造成结果的差异，但是在文件 内容监控中，更多的是关心文件发生了什么变化，对于是否是最小的差异要求不 是很严格，而且这种方法匹配的过程更加简单，易读性强，容易理解，可以有效 的判断出文件是否被篡改，又由于网站文件多数采用文本文件形式存储，所以基 于位置的文本内容比较算法适于应用在对网站文件内容的实时监控方面。 1 4 第三章网站动态监控系统的设计 第三章网站动态监控系统的设计 本系统只需用户指定监测的间隔时间，由系统定时对指定的文件进行监测， 一方面判断文件是否发生变化，另一方面确定变化的内容及其位置。使用户可以 根据具体的变化进行选择，从而达到了监控文件的目的，同时操作方便。 3 1 系统总体设计 3 1 1 系统的功能 总体上分析，系统的功能分为三个方面：文件监测、文件恢复和文件更新。 l 文件监测 监测分为两种情况，自动监测和手动监测。在监测之前，首先要做的是初始 化( 选择数据库的表) ，因为该系统提供了保存数据库的表的功能，当用户退出系 统，下一次登录时，系统会保留上次的数据库的表内容，也就是说如果对于相同 的目录进行监测，第二次就不需要把文件的相关内容再一次存储到数据库中，这 样可以节省存储时间，对于规模比较大的