毕业论文-基于程序切片的网页过滤方法研究

1、南京邮电大学 毕 业 设 计（论 文）题 目基于程序切片的网页过滤方法研究专 业信息安全学生姓名班级学号指导教师指导单位计算机学院、软件学院 日期： 2014 年 3月10 日至 2014 年 6 月13 日毕业设计（论文）原创性声明本人郑重声明：所提交的毕业设计（论文），是本人在导师指导下，独立进行研究工作所取得的成果。除文中已注明引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。 论文作者签名： 日期： 年 月 日摘 要互联网的高速发展已经使其成为世界上覆盖面最广、范围最大、内容最为

2、丰富的资源库。网络已成为人们获取信息的主要途径。但是随着信息的爆炸，人们在充分享受信息共享所带来的便利的同时，却也饱受着大量垃圾信息的困扰。因此网页过滤技术就发挥了足够的作用。本文研究了基于程序切片的网页过滤方法。本文的网页过滤技术主要是通过输入关键字来找出相关的内容，用切片方法来提取或过滤出相关程序。DOM是Document Object Model(文档对象型)的缩写，它将网页中的各个元素都看作一个对象，从而使网页的元素也可以被计算机语言获取或者编辑。使用DOM的API，可以探索一个网页的节点，查询其属性。本文的过滤技术是构造一个包含Web页面按照文件顺序分层的树状的数据结构，这个数据结构

3、是一个真正的可以查询树的对象。在用户界面，用户输入关键字，工具根据过滤的公差找出相关的节点以及它的父母节点和子节点来进行过滤。本文的研究是在Firefox浏览器上进行的，最后的成果以扩展工具的形式展现。关键词：网页过滤；DOM树；程序切片；Firefox扩展工具全套设计加扣3012250582ABSTRACTThe rapid development of the Internet makes the Internet have become the worlds resource base which is the most extensive in coverage, largest in

4、 scope, and richest in content. Internet has become the main way that people access the information. But with the explosion of information, on the one hand, people are in the full enjoyment of the convenience brought by the information share, on the other hand they suffer a large number of “spam” pr

5、oblem. Therefore, web filtering technology has played a sufficient role.The thesis studies the program slicing based method to web filter web. Web filtering technique in this thesis is mainly through keywords to find or filter relevant content, and use slicing technique to extract the relevant proce

6、dures. DOM (Document Object Model) pages of the various elements as an object, so that the elements of the page can also be accessed or edited by computer language. With the API of DOM we can explore the nodes of a wed page and query their properties. Our filtering algorithm first constructs a tree-

7、like data structure which contains all the information of the Web page hierarchically organized in document order. This data structure is really an object with provides methods to query the tree. In the user interface, when users specify a keyword, the slice tool identifies a node and its associated

8、 parent nodes or child nodes according to the degree of filtering. The thesis was conducted in the Firefox Brower, the final outcome is an extension tool.Key words: Web Filter; DOM tree; Program Slicing; Firefox extension tool 目 录第一章 绪论11.1研究背景及意义11.2网页过滤的发展现状21.3本文的研究内容及论文结构3第二章 程序切片技术的阐述52.1程序切片的定

9、义52.2程序切片技术发展过程52.3程序切片分类62.4程序切片准则82.5程序切片算法92.5.1静态切片算法92.5.2动态切片算法112.5.3面向对象切片算法112.6本章小结12第三章 基于程序切片的网页过滤技术133.1网页过滤技术133.1.1 URL过滤133.1.2内容过滤143.2体系结构概述143.3详细体系结构设计153.3.1对网页HTML建立DOM树153.3.2切片相关信息及其算法173.3.3可视化切片193.4本章小结20第四章 网页过滤的实现214.1实现的平台214.1.1 XUL214.1.2扩展所涉及的技术214.1.3扩展的基本结构224.2方法实

10、现展示224.2.1整体描述224.2.2实现结果234.2.3结果分析254.3本章小结26结束语27致 谢28参考文献29南京邮电大学2014届本科生毕业设计（论文）第一章 绪论1.1研究背景及意义随着互联网的高速发展，互联网的应用越来越普遍，己经渗透于经济、文化、政治、科技、军事等各个领域，对人们的生产、生活、工作、学习、交往、娱乐等各个方面产生了重大影响，离开了互联网，整个社会将寸步难行。互联网作为当下最流行的信息发布媒介已经被越来越多的人们接受，从而使人们获取信息变得更加方便。人们在充分享受信息共享所带来的便利的同时，却也饱受着大量“垃圾信息”的困扰。Internet的开放性、平等性

11、、无界性等特征又导致了网络的无限制滥用，大量的垃圾及敏感信息充斥于网络，如何滤除这些垃圾及敏感信息，消除网络带来的消极及负面影响已成为Internet信息服务须解决的关键问题之一。特别是对于广大青少年学生，一些“有害信息”正在威胁着他们的身心健康。另外，企业员工的上网行为亟待规范。网络的复杂性和开放性带来的安全问题有以下几点：1. 网上的不良信息 现在有各种成人网站、论坛，不健康站点充斥着整个互联网，甚至一些大型的门户网站为了广告收入，也设置部分的成人图片、成人网站广告显示。这些内容极大的危害着互联网访问用户中占很大比例的青少年。2. 网上的反动信息 由于互联网传播信息的便捷性和对用户身份的隐

12、蔽性，反动分子已将反动信息传播的主体转移至互联网上。他们一般将网站架设在国外的服务器上，使用数据加密,论坛会员制，电子邮件等方式传播反动信息。互联网上的反动信息极大危害着国家安全。3. 网络病毒 计算机病毒的破坏性众所周知，目前病毒的传播途径大多数都是通过网络，包括靠电子邮件、网页、文件传输等方式。4. 网上收费陷阱 许多网站发放各种虚假广告信息诱骗用户通过手机或者银行进行服务定购，收取高额的信息费和服务费。5. 垃圾邮件 目前，垃圾邮件的泛滥己经使整个因特网不堪重负。垃圾邮件主要危害包括占用网络带宽、收集用户隐私信息、传播病毒木马、不良信息和虚假广告等。6. 其他 还有很多其他的安全问题，例

13、如广告软件、间谍软件、网络诈骗等等。并且，随着互联网上信息呈几何级的增长，人们想要准确获取一条自己想要的信息已变得非常困难。人们对高效率的信息获取技术的需求越来越迫切。在这种情况下，出现了搜索引擎，它可以通过给定的关键词来对相应的页面作大纲式索引，从而为人们获取信息提供便利。搜索引擎的出现虽然暂时缓解了信息检索的问题，但缺陷依然明显：它不能解决页面级别的信息内部索引问题；虽然给出了相关信息页面的链接，但用户在夹杂大量噪声数据的网页中获取有效信息依然困难；搜索结果不准确，截词操作符功能不稳定；只能把有限数量的网页编入索引，造成数据不全；索引的结果跟不上页面更新频率。这时就需要网页过滤了。网页过滤

14、就是在网络的不同地点部署访问策略，通过一定的技术手段，根据对网页内容合法性的判断来禁止用户访问不良内容。家长不想让孩子沉溺在网络游戏当中；老板不希望员工在上班时间浏览娱乐新闻；政府不允许任何人传播浏览反动和色情信息，这些需求都在网页过滤的范畴之内。网页过滤不仅能美化网络环境，还能够加快人们查询信息的速度，剔除掉一些不相关的信息。本文所开发的基于程序切片的网页过滤技术是一个让用户输入想要查找的关键字而提取或过滤关键字相关的内容的一种工具。相对于开发商自动填写过滤词的过滤工具，这个扩展工具增强了它的自由性和与用户的互动性。1.2网页过滤的发展现状网页过滤技术的研究早己是网络安全领域的一个重要热点，

15、国内外的许多厂商和机构都做了大量的研究工作。网络信息过滤是根据一定的标准和利用一定的工具从动态的网络信息流中选取相关的信息或剔除不相关信息的一系列过程。现在网页过滤技术主要是分成两个方面： 一种是基于内容的网页过滤。这种技术根据内容的形式可以分成基于文本的过虑技术和基于图像的过滤技术。一般来说，基于文本的内容过滤步骤主要包括建立模板、提取文本内容特征、过滤过程和信息反馈这几个过程。基于文本内容的过滤技术有关键词过滤,模式过滤，智能文本内容分析过滤等。智能内容分析网页过滤是主流方向，其核心是算法，常用的算法有决策树算法、SVM算法、KNN算法和贝叶斯算法等。基于文本内容的网页过滤技术，过滤面广，

16、可以对基于文本内容的网页进行及时过滤，但是需要权衡过滤的准确率和过滤效率，而且每一次过滤都需要分析网页内容，计算量大，不适合集中过滤。基于图像的过滤技术主要分析网页中图片的内容，判断其合法性。但是普遍存在过滤精度不够、滤效率低、耗时大等问题。 另一种是基于URL分类的网页过滤技术。早在20世纪90年代，通过建立、编辑和更新黑白名单的方式建立URL网页过滤系统。在进行网页过滤时，通过与黑白名单中的URL进行匹配，是黑名单则过滤掉，白名单则放行，未命中URL则根据系统的自定义的方式操作。这种基于URL黑白名单的过滤，实际上把URL分成两类:合法与非法。基于URL黑白名单方案很难实现客观、细粒度的U

17、RL分类，很难成为有效的URL过滤方案。随着文本分类技术的发展，URL的分类逐渐丰富。URL分类数据库一般采用自动的机器学习结合人工分类的技术来获得。通过人工分类的准确数据,不断地训练机器学习系统,提高系统自动分类的准确性。基于URL分类的网页过滤技术在过滤时不需要大量的计算操作，显著地提高了过滤的效率，但是URL分类数据的时效性与覆盖率是需要考虑的问题。在整个 URL 过滤市场中美国的 Web Sense 厂商独占鳌头，占据了 50左右的市场份额，其次是 Surf Control、Secure Computing、Cyber Guard、8e6 等厂商。现在市场上已经有不少网页过滤功能的软件

18、，根据用户数据的规模，主要分成个人应用级和企业级两类。1. 个人应用级的网页过滤软件即在个人的终端上安装软件，或者嵌套于用户的浏览器中。但是在个人的实际使用中，更多的用户使用此类软件过滤掉某类特定危害的网站，如钓鱼网站和恶意网站，对于主动访问不良网站的行为，这类软件无能为力。而且随着移动互联网的高速发展，上网的终端越来越多样化，很难在所有的移动终端上都安装此类客户端。广大的互联网用户，也没有主动安装此类过滤软件的意识。因此，个人应用级的网络过滤系统作用极为有限。2. 企业级的网页过滤系统可以实现强制性的过滤，一般部署于企业的网关。但是此类过滤系统一般都是和硬件绑定在一起，当企业网内用户数量增加

19、，此类系统无法进行有效的扩展。而且过滤的用户只限于企业的内部用户，对网络环境的净化作用也比较有限。就网页过滤来讲，我国的市场与发达国家相比，还处于发展的初级阶段。在美国，从事内容过滤软件研制的几个专业公司都是上市公司，整个市场每年的营业额达数十亿美元。而我国目前的市场规模只是美国的一个零头，这与我国目前的互联网发展规模并不相称。一个好的软件研发体系应该具有极强的专业性和稳定的技术队伍才能不断地进行技术创新和组织持续的技术服务，在这一方面，大公司的软件项目组并不一定比一家专业性中小型公司的全力投入更有优势，这就是现在没有大厂商进入内容过滤产品市场的原因。目前内容过滤软件的使用集中在网吧等互联网经

20、营场所，而网吧仅仅是互联网的一个组成部分，更大量的使用者是来自于学校、单位和个人 ，这一部分的过滤软件市场尚处于初级阶段。另外，内容过滤软件不仅是内容过滤一个功能这样简单，更重要的是进行互联网访问控制管理， 提高单位网络的使用效率，这一点还未被广大的企业管理者所普遍认识，而这一部分市场所占份额是最大的。我们要通过认清国内外网页过滤技术的差距，寻找一条最适合中国环境发展的网页内容过滤技术的发展之路。 1.3本文的研究内容及论文结构论文研究的主要内容是实现基于程序切片的网页过滤，结合网页脚本语言的程序相关技术，研究并实现一种网页过滤方法。本文将通过一个四元组来构建切片准则，而这四元组就包括了过滤网

21、页的标准。本文共分为四章，第一章是绪论，介绍了课题的研究背景和网页过滤的发展现状。第二章介绍了程序切片的一些基础知识。第三章是论文的核心，介绍了网页过滤技术，以及实现基于程序切片的网页过滤的框架以及详细过程。第四章介绍了具体实现时需要的相关技术以及实现的成果展示及分析。最后对本文工作进行了总结。第二章 程序切片技术的阐述2.1程序切片的定义顾名思义，程序切片就是指将一个程序中用户所感兴趣的代码都抽取出来组成一个新的程序，这个新的程序就是源程序的切片，根据切片规则的不同，生成的切片也各不相同。程序切片可以用 S(V, N) 的形式表示，其中 V 表示程序中的某一个变量或是变量的集合，N 表示在程

22、序中的某一个位置 ( 变量 V 所在的语句) 。S(V, N) 的含义是“一个程序切片是由程序中的一些语句所组成的集合，这些语句可能会影响到在程序的某个位置 N 处所定义或引用的变量或变量的集合 V 的状态”。S(V, N)是程序切片最基本的形态，任何形式的程序切片都可以通过对这个标准进行扩展而得到。2.2程序切片技术发展过程程序切片技术是一种分析和理解程序的技术，通过对源程序中各个兴趣点计算程序切片以便分析和理解程序。程序切片概念由 Mark Weiser 于 1979 年在他的博士论文中首次提出，随后又在 1981 年的国际软件工程大会（ICSE81）上以及 1984 年的 IEEE Tr

23、ansactions on Software Engineering 杂志上发表文章做了进一步的阐述。程序切片总的发展情况可以分为以下四个阶段： 1. 基于数据流方程的程序切片阶段这一阶段主要是指由M.Weiser提出的程序切片概念，以及运用基于CFG的数据流方程来计算程序切片的算法。2. 基于依赖图的程序切片阶段这一阶段主要包括：K.J.Ottenstein等人分别于1984年和1987年引入了基于程序依赖图的图可达性算法，它能够计算当时流行的过程内后向切片；S.Horwitz等人分别于1988年、1990年和1992年引入了前向切片的概念及算法，过程间切片概念以及基于系统依赖图的两步遍历图

24、可达性算法；B.Korel和J.Laski于1988年，H.Agrawal和J.R.Horgan于1990年分别引入了动态切片的概念和算法。3. 面向对象程序切片阶段随着面向对象程序设计语言和设计方法的兴起，人们自1996年开始了面向对象的程序切片技术的研究。其中，M.J.Horrald等人利用类依赖图来扩充传统的系统依赖图使其能够表示对象的C+程序，然后利用改进的两步遍历图可达性算法来计算C+程序的程序切片；C.Steindl通过对各种各样的控制流和数据流的计算，并结合他们所使用的一个项目来讨论面向对象程序的切片计算问题；另外，J.Zhao教授，D.Liang博士和Z.Chen博士等人分别在

25、面向对象动态程序切片、使用对象依赖图切片面向对象程序，以及面向对象Java程序切片等方面各自提出了自己的观点。4. 程序切片发展“百花齐放”阶段这一阶段的主要标志就是出现了各种各样的程序切片变体，如削片、砍片，还有数据切片、层次切片和无定型切片等。同时，程序切片技术的应用也在此阶段得到了极大的丰富和发展。除了传统的基于切片的软件调试、软件测试和程序理解以外，程序切片还被广泛运用于程序重组、逆向工程、软件维护、程序验证以及软件可靠性分析和建模等方面。而本文的网页过滤就是基于程序切片技术的。2.3程序切片分类1. 静态切片与动态切片Weiser 最初提出的程序切片概念和所得到的切片就属于静态切片（

26、Static S1icing）范畴。静态切片是在编译时间，即程序尚未运行时进行切片：该技术对程序的输入不作任何假设，所作的分析完全以程序的静态信息为依据。因为要分析程序所有可能的执行轨迹，静态切片技术一般用于程序理解与软件维护方面。 实际应用中，人们往往更关注某一具体输入下，程序实际执行时影响兴趣点处某一变量值的那些语句。因此，Korel 等人提出了动态切片（Dynamic Slicing）的概念切片准则是一个三元组（n，v，x），n，v 的定义不变，x 是一个输入序列，在该输入下与源程序计算出的该变量的值是相同的动态程序切片计算过程使用用户的实际输入 x 产生的精确数据流信息进行分析。动态切

27、片技术多用于程序调试、测试方面动态切片还可以用在理解大型程序方面。 2. 后向切片与前向切片如果切片s由程序p中可能受到 n 处变量v的值的影响的所有语句组成，这称为前向切片（Forward Slicing），与此相反，后向切片（Backward Slicing）s 是程序 p 中影响到兴趣点 n 处变量 v 的值的所有语句和谓词组成的集合。3. 面向对象切片随着面向对象程序设计方法逐步成为主要的程序设计和实现方法，对于基于面向过程程序的切片方法来说，但这些方法已不适用于面向对象程序。因为面向对象编程语言提出了一些新的概念与特性，例如：类、对象、动态绑定、封装、继承、消息传递等以及多态，所以面

28、向对象程序切片不仅要考察语句和数据之间的依赖关系，还要考察各个类之间的关系为了获得更准确、更有效的程序切片。 传统的系统依赖图是在控制依赖图、数据依赖图、过程依赖图和程序依赖图的基础上建立起来的一种语法分析树表示。在面向对象程序中存在着继承、多态、动态联编等特性是传统系统依赖图无法描述的。现在一般采取两种策略：第一，引入适合表示面向对象程序的表示方法，如类层次图用来表示类之间的继承关系、虚函数调用图反映虚函数的调用。第二，构造适合于面向对象程序的系统依赖图，再利用图的可达性算法计算切片。 D.Liang 和 M.T.Harrod 提出了对象切片（Object Slicing）技术这一概念，主要

29、是通过扩展系统依赖图实现的。目前对它的研究更多是侧重于静态切片这一部分，而且基本都是基于依赖图的。李必信等人提出了一种逐步求精的基于面向对象程序的分层切片方法。4. 其他类型程序切片（1）准静态切片（Quasi Static Slicing）。准静态切片的产生是对于一些特殊程序 P，某些输入值可以确定而另外一些输入不停变化、在此情况下对程序 P 进行分析时，混合使用静态切片和动态切片方法在计算切片时，固定一部分输入值，使得程序 P 中的某些特定子路径得以执行，从而删除一些分支这样得到的切片比纯粹的静态切片要精简得多，部分静态切片用于程序理解和转换。 （2）同步动态切片（Synchronous

30、Dynamic Slicing）。Hall扩展了动态切片，他将一个测试集而不是单个测试用例用于程序动态切片中一个测试集可以看成是对某个需求的完全测试用例集。Hall 提出的同步动态切片并不是简单地对每个测试用例的动态切片进行的并集，而是采用了迭代算法，从初始切片开始在迭代过程中逐步增长为大型的动态切片同步动态切片适用于定位程序 P 的某个需求有关的代码部分。 （3）分解切片（Decomposition Slicing）。它是一种以把程序分解为不同模块为目的的切片技术。分解切片是由一组关注某一变量的程序切片构成的集合，可以捕获程序中对某一变量的所有计算分解切片不依赖于语句在程序中的位置，构成分解

31、切片的程序切片按照一定的规则排列成网格，利用这个网格实现对程序的分解，可以直观的判断出一个模块中哪些语句和变量可以被安全地修改，即这种修改不会影响其他模块，以及哪些语句和变量不能随意被修改，通过使用这种网格来实现对程序的分解分解切片技术适用于回归测试方面。 （4）条件切片（Conditional Slicing）。Confora 等人提出的条件切片技术是通过增加一个条件扩展了传统的静态切片准则，条件切片技术是介于静态切片技术和动态切片技术之间的一种切片技术，它既不是仅仅局限于只对程序的静态信息进行分析，也不是仅仅局限于只依赖外部的输入来获得程序的信息。在构造条件切片时，只有那些满足切片条件的语

32、句才会被提取出来，因此某条件对应着程序的某个或某些初始状态在进行切片算法时，只有满足该切片条件的那些输入才会被分析提取出来，条件切片技术主要用于程序理解和软件重用方面。 （5）无定型切片（Amorphous Slicing）。无定型切片在简化源程序的过程中保留原程序语义，该技术施加更广泛的切片准则，充分利用传统切片技术保留源程序语义映射的简化功能。无定型切片的特点使其更适合程序理解领域，这样就能够在一个较小的范围内更加高效地分析程序，而传统的切片技术则更多地应用在调试领域。2.4程序切片准则程序切片必须依据一定的切片准则进行计算。对同一程序而言，切片准则不同，对应的程序切片也随之不同。同时，不

33、同的切片算法也是依据不同的切片准则。以下就是对于程序切片准则的介绍：1静态切片准则：静态切片与程序的输入无关,即对于感兴趣的变量，静态切片准则是一个二元组 C=，其中 V 是程序 P 中变量集合的一个子集，n 是程序 P 中的某个兴趣点（对应于 P 中的一条语句）。给定静态切片准则 C，静态切片是有可能影响 n 处 V 中变量的所有语句和谓词组成。程序P 的切片 Slice 可以是任何一个对 n 处 V 中变量具有与程序 P 相同影响的程序。由静态切片计算出来的值和原来程序在任意输入下执行时所计算出的值是完全一致的。2动态切片准则：动态切片与程序的输入密切相关，对应不同输入，按照切片准则所构造

34、的程序切片也不相同。由于动态切片只关心某种特定的输入情况，因此往往可以构造出比静态切片更小的程序切片。动态切片准则是一个三元组 C=，其中 x 是一个程序输入，n 是程序 P 中的某个兴趣点（对应于程序 P 中的一条语句或一个语句块），V是程序 P 中变量的一个子集。给定标准 C，动态切片由在输入为 x 时，所有程序中直接影响或间接影响兴趣点：V处中变量的语句和谓词组成。当输入为x 时，在兴趣点 s 处的关于 V中变量的动态切片 Slice 保留 P 的与 s 点的变量集合 V 有关的投影含义。3迭代切片准则：迭代切片准则也是一个三元组 C=，这里 V 是变量的集合，s 是程序 P 中一个兴趣

35、点，n 是自然数。程序 P 的第 n 次（静态）迭代切片 Slice 是由第 n 次执行到达时那些保持程序 P 的投影含义不变的语句组成。当 n 扩充到 N（自然数集）时就变成广义迭代切片准则。 4条件切片准则：条件切片准则是一个四元组 C=，这里 I 是变量名的集合，这些变量的值是从输入序列中获得的，S 是程序 P 中的一个兴趣点：是一个谓词，它的自由变量是 I 的一个子集，V 是一个变量名的集合。构造一个程序 P 的条件切片 Slice，当在一个满足 p 的初始状态执行时，条件切片 Slice 必须保持程序 P（与 V 有关）的投影含义。 5传统的前向切片准则：传统的前向切片准则是一个二元

36、组 C=，这里 V 是变量的集合，n 是程序 P 中的一个兴趣点。程序切片 Slice 是一个由语句和谓词组成的集合，这些语句和谓词受到 P中 V 的变量在 n 处的值的影响。 6分解切片准则：程序 P 的关于一个变量 v 的分解切片 Slice 是由关于切片准则 C=（v,end）的静态后向切片和（v,n1）， ，（v，nm）的并集组成，其中 n1，nm是行的集合（v 在 P中是输出，End 是程序的结尾语句）。 7多点切片准则：该切片准则是一个二元组 C=，其中 N 是程序 P 中节点的集合，V 是变量的集合。当在 N 中任何一点执行一条语句时，对于 V 中的所有变量而言，切片 Slice

37、 和程序 P 具有同样的效果。目前，易彤等研究人员提出了一种基于覆盖测试的动态切片的计算方法，该方法在计算程序切片时没有事先指定切片准则，而是通过首先选取程序中的部分路径作为测试路径，然后通过分析节点间的依赖关系建立基于覆盖测试的动态依赖图，在此基础上设计了一种动态切片方法。其中使用动态依赖图和标记边法相结合而得到的基于覆盖测试的动态依赖图的动态切片方法不仅利用动态执行信息，而且还利用静态信息来获得程序动态执行时的依赖关系。一旦基于覆盖测试的动态依赖图建立好，那么任何针对该程序的动态切片都可以在此基础上进行，而不必重新建立动态依赖图。对于这种方法在多个过程和面向对象领域的有效性还需要进一步验证

38、。2.5程序切片算法程序切片自提出以来，在广大研究工作者的共同努力下，不同类型的程序切片被不断提出来，相应的切片算法也被提出，为程序切片的实际应用提供了可靠的理论基础，其中主要的切片算法有：Weiser的基于数据流方程的算法，无定型切片算法，Bergeretti 的基于信息流关系的算法，Ottenstein 和L.M.Ottenstein 以及 Horwitz 的基于程序依赖图的图形可达性算法，杨洪的基于波动图的算法。另外，还有参数化程序切片算法，行切片算法以及面向对象的分层切片算法等。这里将从静态切片，动态切片和面向对象切片三个方面介绍主要的算法。2.5.1静态切片算法1Weiser 提出的

39、基于数据流方程的切片计算方法Weiser 是通过解数据流和控制流方程来计算程序切片的。首先，建立待切片程序的控制流图（CFG），从其 CFG 中产生相应的数据流和控制流方程。他使用一种迭代过程计算 CFG 中每个结点相关的变量的集合。Weiser 在这里描述了一种用来计算最少语句切片近似值的迭代算法。这种算法使用两种不同的迭代层次，即： （1）跟踪可传递的数据依赖层。这要求迭代过程是在循环存在情况下发生的； （2）跟踪控制依赖层。该层把跟踪到的新的控制谓词控制的语句包含到某个控制谓词的切片中。对每个这样的谓词，重复步骤（1），直到把该谓词依赖的所有语句都包含进来为止。这类算法确定相关变量（Re

40、levant Variable）的连贯（Consecutive）集合，由此可得到相关语句的集合。2. 基于信息流关系的算法这主要是由 Bergeretti 和 Carre 做出的贡献。他们计算切片的方法是：首先定义了一些信息流关系（Information-Flow Relations），然后利用这些信息流关系来计算切片。例如，对一条语句（或语句序列）s，一个变量 v，以及一个在 s 中出现的表达式 e（它可以是一个控制谓词或一条赋值语句的右边），可以定义信息流关系 s、s、s。这些关系具有下列特性：（1）（v，e）s：当且仅当在s的入口处v的值潜在地影响e计算的值； （2）（e，v）s：当且仅

41、当为e计算的值潜在地影响在s的出口处 v 的值； （3）（v，v）s：当且仅当在s的入口处v的值潜在地影响在s的出口处 v的值。 信息流关系是按照语法制导的自底向上的方式来计算的。3基于依赖图（DG，Dependence Graph）的图形可达性算法K.J.Ottenstein 和 L.M.Ottenstein 于 1984 年提出切片准则（V，S），其中 s 为程序 P 中的一个兴趣点，v 是在 s 处定义或使用的变量，依据此切片准则，在程序依赖图（PDG：Program Dependence Graph）上使用图形可达性（Reachability）算法来计算切片。 根据他们对切片含义的理解

42、，切片是由程序中所有可能影响 v 在 s 点的值的语句和谓词构成。1990年，Horwitz，Reps 和 Binkley 等人使用依赖图来计算切片，他们开发了一种过程间的程序表示系统依赖图（SDG，System Dependence Graph），并实现了一个基于系统依赖图的两阶段图形可达性切片算法。由于使用调用位置的可传递的依赖流信息中包含被调用过程的上下文环境，所以该算法的计算精度比以前的算法更高。4无定型切片算法（Amorphous Slicing）无定型切片概念是 M.Harman 和 S.Danicic 在 1997 年提出的，主要是针对程序理解领域，有些约束可以被适当放宽而提出的

43、。在程序调试领域应用切片技术，为了使得到的程序切片包含那些可能引起错误的语句，在去除语句时必须施加一定的约束。显而易见，这些约束是必要的，因为它们剔除了那些其执行不影响s处所切变量 v 的值的语句，从而使调试者能够在一个较小的范围内有效地发现并且修改错误。但是，M.Harman 和 S.Danicic发现在程序理解领域，这些约束过于苛刻，实际上是可以适当放宽的。因此，他们于 1997 年提出了无定型切片的概念。这种切片技术继承了传统切片技术在简化原程序的过程中保留原程序语义的功能，唯一不同之处在于这种切片充分利用了任何能保留语义映射的简化技术，尽可能地简化原程序。这种特点使得这种切片更适用于程

44、序理解领域。5. 有条件切片算法（Conditional Program Slicing）G.Canfora，A.Cimitile 和 D.Lucia 于 1998 年提出了基于程序依赖图的有条件切片计算算法。具体来说，要计算有条件切片，首先要根据输入条件的限制对程序进行简化，然后根据简化的程序计算切片，这种简化的程序条件化的程序。一个有条件切片的计算可以先通过计算静态切片，再通过符号执行对静态切片进行简化来实现。 依赖图能够从条件化的程序中计算有条件切片。首先，在某个初始路径条件下，标记依赖图种对应符号执行的所有语句和谓词节点；然后，后向遍历标记节点之间的控制依赖边和数据依赖边，由此包含的所

45、有语句和谓词构成的集合就构成了切片。2.5.2动态切片算法1Agrawal 和 Horgan 等人提出的基于动态依赖图（DDG，Dynamic Dependence Graph）的切片计算方法计算静态程序切片时，可以采用建立程序依赖图，在程序依赖图上使用图形可达性获得程序切片。对于动态程序切片而言，我们则可以通过执行原程序并记录其执行历史（EH，Execution History），构建源程序的动态依赖图，可以计算出精确的动态切片。但是，构建动态依赖图时，语句的不同出现可能会受不同语句的影响，因此在动态依赖图中，语句的不同出现要用不同的节点来表示，这样其空间开销较大（尤其是规模较大，有循环的程

46、序），这在一定程度上限制了该方法的使用。2Korel 和 Al-Yami A M 提出的基于可移动块的切片前向计算方法这种算法的基本思想是：程序可以看成由若干个基本块构成，当程序执行到一个基本块的出口时，算法确定是否应将该基本块包括进相应的动态切片中。这种算法无需存储动态依赖图，空间开销较小，但是对包含循环的程序来说，该算法可能会产生不确切的结果。3Gyimothy 提出的基于程序 D/U 表达式（D/U Representation）计算动态切片的方法利用程序 D/U 表达式，计算某条语句执行时，影响其变量定义的所有语句，进而求其动态切片。一个程序 D/U 表达式记录了一条语句中变量的定义与

47、引用情况。使用 D/U 表达式，可将程序的控制依赖和数据依赖同等看待，从而不需使用动态依赖图，就可计算出与使用动态依赖图同样的动态切片来，其空间开销较小。2.5.3面向对象切片算法在对面向对象的程序进行切片计算时，需要考虑面向对象程序设计语言的特点，如：类、对象、继承和多态等。在此方面研究的思想主要是扩展传统的系统依赖图并结合类依赖子图、类层次子图等，来构造面向对象的系统依赖图，从而计算面向对象切片；但是，传统的切片方法都是基于依赖图的，而构造面向对象程序的依赖图是一件非常复杂的工作，在文献根据程序逻辑分层的角度提出一种面向对象程序的层次模型，然后在层次模型的基础上采用逐步求精算法来分层计算面

48、向对象程序的切片。 在分层切片算法中针对面向对象的程序设计语言的特点，将程序分成多个层次进行分析，其步骤分为： 1. 面向对象程序层。在计算与切片准则有关的程序切片时，首先确定所有与包含 v和 n 的类有关（由继承、消息传递、数据依赖或控制依赖等形成的直接或间接关系)的类、方法、main函数中的语句等，删除那些与包含 v 和 n 的类无任何关系的类、自由标准过程、main 函数中的语句以及控制谓词等。通过这种方法得到关于切片准则的程序切片的一个粗略切片 S（P）。 2. 类层次和单个类层次。对 S（P）中的类层次进行逐步求精，进一步计算该类层次中影响切片准则的类，并把不影响切片准则或不受切片准

49、则影响的类从类层次结构中删除，从而得到面向对象程序切片 S（P），从而进一步计算单个类中影响切片准则或受切片准则影响的变量、语句和方法，得到 S（P）。 3. 方法层。在前面三步的基础上进一步计算过程或方法中与切片准则有关的变量和语句，删除那些与切片准则无关的变量等信息，最后得到 S（P）。在此过程中，得到的一系列切片的关系可表示为：S（P）S（P） S（P）S（P）。可知，该面向对象的分层切片是一个逐步求精的过程，从而得到的整个程序的切片。 分层切片的提出突破了传统的基于依赖图的切片计算方法，适应了程序设计语言的发展趋势。拓展了切片方法应用范围。2.6本章小结本章中详细介绍了程序切片的定义、

50、发展、分类和切片算法。程序切片作为一种分析和理解程序的技术，广泛地应用于逆向工程，回归测试，程序调试，程序验证和维护过程中，可以说切片技术已经应用到了几乎软件工程的每个角落。本文对程序切片的分类和切片准则也进行了详细介绍，并介绍了主要的静态切片算法、动态切片算法和面向对象切片算法。29第三章 基于程序切片的网页过滤技术3.1网页过滤技术网络信息过滤是根据一定的标准和利用一定的工具从动态的网络信息流中选取相关的信息或剔除不相关信息的一系列过程。信息过滤对网络用户来说并不陌生,如订阅电子杂志、垃圾邮件过滤以及色情网站过滤等都用到了信息过滤方法，过滤网页中的不良信息是信息过滤的主要应用之一。过滤不良

51、信息的方法很多，从过滤系统的作用来看，可以分为推荐系统、阻挡系统和一般过滤三种；从过滤的依据来看，可以分为URL二过滤、内容过滤、以及混合过滤三种；从是否对过滤的信息进行预处理来看，可以分为主动过滤和被动过滤两种：主动过滤是预先处理网络信息，如预先对网页或网站进行分级、建立允许或禁止访问的地址列表等，当用户访问时根据分级标记或地址列表决定能否访问；被动过滤则是对网络信息不作预处理,当用户访问时才对地址、文本或图像等信息进行分析以决定是否过滤。3.1.1 URL过滤URL过滤（URL Filtering）为目前最普遍的网页过滤方式，它首先将URL地址从客户端所发出的请求中取出，然后与预先定义好的

52、样式集合或URL数据库进行比对，依照其结果来判断该URL的合法性，最后决定该请求是否被允许。URL给资源的位置提供一种抽象的识别方法，并用这种方法给资源定位。URL的一般形式如下(即由以冒号隔开的两大部分组成,并且在URL中的字符对大写或小写没有要求)：:/:/由于URL的唯一性，因此可以用URL来过滤因特网上的信息。URL过滤通过比较请求的网页的URL与已经存在的URL列表来限制或允许访问。通常情况下，需要维护两种类型的列表，一个称为“黑名单”，包括禁止访问的目标网站的URL；另外一个称为“白名单”，包括允许访问的网站的URL列表。大多数网页内容过滤系统使用“黑名单”来禁止用户的访问。URL

53、名单一般以数据库或格式化文本的形式存在，由管理者或第三方根据一定的标准来收集和编制，如家长可以根据自己孩子的情况编制白名单或者黑名单；公司、学校、图书馆等机构也可以根据各自的管理对象编制URL名单；许多过滤软件开发商还编制了各种URL名单库。URL过滤具有以下一些优点，例如实现比较简单，准确性比较高以及速度快。但它同时也有很多不足，如URL名单的覆盖面很难达到满意的要求，更新问题比较难,特别是随着网页的动态增加，URL名单的更新是个比较难以解决的问题以及ISP或过滤软件开发商往往以商业秘密为由拒绝透露名单中的网址。由于速度快和准确率高等特点，大部分的过滤系统都采用了URL过滤。对于名单覆盖面的

54、问题，开发人员往往采用智能分析网页内容,然后动态更新名单的方法，其准确性则完全依赖于内容分析的准确性了。3.1.2内容过滤内容过滤(Content Filtering)是对输入的网页内容做关键词(Keyword)或图片过滤,将包含关键词或图片的网页拦截,并以警告信息代替。这种技术根据内容的形式可以分成基于文本的过虑技术和基于图像的过滤技术。一般来说,基于文本的内容过滤步骤主要包括建立模板、提取文本内容特征、过滤过程和信息反馈这几个过程。基于文本内容的过滤技术有关键词过滤、模式过滤、智能文本内容分析过滤等。智能内容分析网页过滤是主流方向，其核心是算法，常用的算法有决策树算法、SVM算法、KNN算

55、法、贝叶斯算法等。基于文本内容的网页过滤技术，过滤面广，可以对基于文本内容的网页进行及时过滤，但是需要权衡过滤的准确率和过滤效率，而且每一次过滤都需要分析网页内容，计算量大，不适合集中过滤。基于图像的过滤技术主要分析网页中图片的内容，判断其合法性。现阶段内容过滤主要是针对文字做关键词检查以决定内容是否恰当，对于图像、声音、视频等尚无较快速且有效的方法来判别其内容的合法性。身处飞速发展的多媒体时代，网络上图文并茂的内容越来越多，目前该技术所能发挥的过滤功能实在有限。文字内容过滤根据主题词典，以文字辨别的方式对网页上出现的关键词进行比对、语义分析，通过判断是否含有特定的关键词来决定是否拦截。在文字

56、解析的过程中，取字的位置错误也经常会造成误判而引起争议。因此通常必须辅以人工判断以增加其准确性,但相应地增加了管理上的开销。另外，该方法对嵌入到图片中的文字无法辨识。3.2体系结构概述本文的网页过滤技术主要是通过输入关键字来找出相关的内容，是用切片方法来提取或过滤出相关程序。使用DOM的API，探索一个网页的节点，查询其属性。我们的过滤技术就是首先构造一个包含Web页面按照文件顺序分层的树状的数据结构，这个数据结构是一个真正的可以查询树的对象。用户输入关键字后，就很容易找出相关的节点以及它的父节点和子节点，最后根据过滤的程度进行切片。我们建立一个多元祖（w，t，k，i）来表示一个查询组。其中w是表示想要抽取或者删除的关键字；t是一个自然数，代表与关键字的距离；k是一个布尔值，表示是否要保持过滤之后网页的结构；i也是一个布尔值，表示抽取或者删除。我们根据算法给出切片的流程图，如下图（图3.1）。图3.1网页过滤算法流程图3.3详细体系结构设计3.3.1对网页HTML建立DOM树DOM(Document Object Model)是W3C建立的一个标准API，通过这个API，Web应用程序可任意访问和更改HTML和XML文档中的数据。W3C早在1998年10月就提出了DOM的正式建议(Recommendation)，但直到本世纪初，这个建议才逐渐为一些