（计算机软件与理论专业论文）基于遗传算法的模糊测试数据生成的研究.pdf

il】，1 jj a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h es o f t w a r et e c h n o l o g y , s o f t w a r es e c u r i t y t e s t i n gh a s d e v e l o p e d g e n e t i ce f f i c i e n tt e s td a t af o rt e s t i n gh a sa ni m p o r t a n ts c i e n t i f i ca n da c a d e m i cv a l u e m o r e o v e r ，i ti ss i g n i f i c a n c et oo u rs e c u r i t yt e s t i n g h o w e v e r , s o f t w a r es e c u r i t yt e s t i n gh a ss t i l lo nt h e s t a g eo fr e s e a r c ha n dd e v e l o p m e n ts of a r m a n yt e c h n i c a lp r o b l e m ss u c ha sh o wt oe n h a n c ee f f i c i e n c y a n da c c u r a c yh a v en o tb e e ns o l v e dc o m p l e t e l y t h i sp a p e rd e v o t e st ot h er e s e a r c ho ft h eg e n e r a t i o no f t h et e s td a t af o rs o f t w a r es e c u r i t ya n dt h eo p t i m i z a t i o no ft h et e s td a t a f i r s t l y ，t h i sp a p e ri n t r o d u c e st h es o f t w a r es e c u r i t yt e s t i n gt e c h n o l o g y i ti sm a i n l ya b o u tt h e r e s e a r c hs t a t u sa n dt h eb a s i cc o n c e p t sa n dm e t h o d so ft h es o f t w a r es e c u r i t yt e s t i n g i ng e n e r a l ， i n t r o d u c et h ee x i s t i n gm e t h o do fs e c u r i t yt e s t i n gm e t h o d sa n dt h eu s i n go ff a u l ti n j e c t i o na n df u z z i n g s e c o n d l y ，t h i sp a p e rp r o p o s e st h ea p p l i c a t i o nm e t h o do ff a u l ti n j e c t i o n ( f 1 ) u s e di ns e c u r i t y t e s t i n gd a t ag e n e r a t i o n i n t r o d u c ei t sg e n e r a t i o n ，b a s i cc o n c e p t i o na n df e a t u r e e x p a t i a t et h eg e n e r a l p r o c e s so ff a u l ti n j e c t i o na n da n a l y z et h em e t h o do ff a u l ti n j e c t i o na r et h em a i nt e c h n o l o g i e s a n d p r o p o s et h em e t h o do fu s i n gf u z z i n gt og e n e t i ct h et e s td a t a w ea n a l y z et h ea c a d e m i cs u p p o r to ft e s t d a t ag e n e r a t i o nu s i n gf a u l ti n j e c t i o nb a s e do nf u z z i n ga n dt h ep r o b l e m sw h i c hw en e e di st os o l v e l a s t l y , t h i sp a p e ri n v e s t i g a t e sa na p p r o a c ht oe f f e c t i v ea u t o m a t i cs e c u r i t yt e s td a t ag e n e r a t i o n u s i n gf u z z i n g i n t r o d u c i n gt h eg e n e r a lp r o c e s sf o rs e c u r i t yt e s td a t ao p t i m i z e db a s e do ng e n e t i c a l g o r i t h m ( g a ) ，d i s c u s s i n gt h ed e s i g nm e t h o do ff i t n e s sf u n c t i o na l em a i nq u e s t i o n sa l s o t h e i m p r o v e m e n t si no p t i m i z i n gt h et e s td a t au s i n gg ai n c l u d et h ec o d i n go fc h r o m o s o m e s ，s p e c i f i c a l l y d e s i g n e dg e n e t i co p e r a t o r sa n dt h ed e s i g no ff i t n e s sf u n c t i o n t h ec o n v e r s i o nt i m et o t h et a r g e t s e c u r i t yr e q u i r e m e n ti sr e d u c e db yt h em e t h o do fc o n t r o l l i n gv a r i a n c ep o s i t i o n t h ee f f i c i e n c yo f s e a r c h i n gs e c u r i t yt e s td a t ai se n h a n c e db yi m p r o v i n ga d a p t i v eg a at o o lm o d e li sd e s i g n e dt o a u t o m a t i c a l l yo p t i m i z es e c u r i t yt e s td a t aa c c o r d i n gt ot h es e c u r i t yr e q u i r e m e n t s t h ef e a s i b i l i t ya n d e f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h mi sd e m o n s t r a t e dw i t ht h es e c u r i t yt e s t i n go nw e ba p p l i c a t i o n k e yw o r d s ：s o f t w a r es e c u r i t yt e s t i n g ；f a u l ti n j e c t i o n ；f u z z i n g ；g e n e t i ca l g o r i t h m s ； t e s tc a s e 目录 第一章绪论1 1 1 引言1 1 2 国内外研究动态2 1 2 1 软件安全性测试2 1 2 2 错误注入技术4 1 2 3 模糊测试5 1 2 4 遗传算法7 1 3 论文的主要工作和创新点8 1 4 论文的结构与章节安排8 第二章软件安全性测试概述1 0 2 1 软件安全性测试方法1 0 2 2 基于错误注入的安全性测试方法1l 2 2 1 动态环境错误注入概念1 2 2 2 2 错误注入的关键问题1 3 2 2 3 错误注入测试充分性标准1 3 2 3 模糊测试概述1 4 2 3 1 模糊测试方法分类1 5 2 3 2 模糊测试局限性1 6 2 4 本章小结1 7 第三章模糊测试数据生成研究1 8 3 1 环境错误注入点和对应注入错误1 8 3 2 基于环境错误注入的模糊测试设计2 0 3 2 1 模糊测试步骤2 l 3 2 2 模糊测试中的异常检测2 2 3 3 模糊测试用例生成算法设计。2 3 3 3 1 基于输入的测试用例划分2 3 3 3 2 基于r c c 的模糊测试用例生成算法2 4 3 4 本章小结2 7 第四章基于遗传算法的模糊测试数据( g a f ) 优化2 9 1 j 越f 钟j 。l j 小流利2 9 4 2 遗传算法编码设计3 0 4 2 1 编码规则3 0 4 2 1 参数编码及动态编码设计3 1 4 3 遗传操作设计3 2 4 3 1 改进的自适应遗传算法3 2 4 3 2 适应度函数的设计3 3 4 3 3 跨代基因选择3 3 4 3 4 染色体交叉和变异3 4 4 4 本章小结3 5 第五章w e b 应用程序的测试及效果评估3 6 5 1w e b 浏览器模糊测试设计3 6 5 1 1 模糊器的设计3 7 5 1 2 模糊数据优化3 7 5 2 测试实例3 8 5 3 实验数据分析4 1 5 3 1 跨代选择策略比较4 1 5 3 2 交叉率比较4 2 5 3 3 变异率比较4 3 5 3 4g a f 与f u z z i n g 比较4 3 5 4 本章小结4 - t 第六章总结与展望4 5 6 1 本课题总结4 5 6 2 本课题展望4 5 参考文献4 7 攻读学位期间的研究成果一，5 0 致谢5 1 学位论文独创性声明5 2 学位论文知识产权权属声明5 2 第一章绪论 1 1 引言 第一章绪论 随着互联网的迅速发展和软件功能的不断强大，我们生活的各个关键领域都离 不开计算机系统，核电站、航空、航天、工业控制、交通、军事、金融等，都依赖 于软件。这类软件都是规模庞大，结构复杂并且对可靠性和安全性要求极高的安全 软件( s e c u r i t ys o i t w a r e ) 。但是，软件系统并不安全，它存在着各种各样的不安全 性、脆弱性和危险性因素。如果这些软件被破坏而瘫痪，将会给人们的生命财产造 成极大的损失，因此软件的安全性测试在保证软件的可靠性和安全性上就显得极为 重要。 计算机安全面临的现状并不乐观，由于软件的规模和复杂度以非线性的速度增 大，软件中的安全缺陷和漏洞也在不断增多，同时由于网络技术在各个领域中的应 用，软件缺陷和漏洞对软件的安全性危害也日益增大，使得大多数软件都不能成功 的抵御恶意攻击。软件安全性是软件在受到恶意攻击时仍能提供所需功能的能力。 通过实际的经验教训，人们逐渐认识到软件可靠性和软件安全性对软件成功运行在 当今网络环境下的重要性，而现在软件测试方面又大都集中在软件的功能测试上。 在这样的测试前提下，软件在运行时很容易由于自身的缺陷和漏洞而对攻击没有抵 抗能力，造成损失。 软件的安全性测试主要就是针对软件的安全缺陷和漏洞进行测试的，目的是确 定软件的安全特性实现是否与预期的设计思路一致。软件安全性测试是保证软件安 全性、降低软件安全风险的重要手段。模糊测试是一种发现安全漏洞的有效的测试 方法，在安全性测试中越来越受到重视。模糊测试是将随机的坏数据插入程序，观 察程序是否能容忍杂乱输入的测试方法。模糊测试是不合逻辑的，只是产生杂乱数 据攻击程序。采用模糊测试攻击应用程序可发现其它采用逻辑思维测试很难发现的 安全缺陷。模糊测试是一种通过提供非预期的输入并监视异常结果来发现软件故障 的方法。模糊测试典型地是一个自动的或半自动的过程，这个过程包括反复操纵目 标软件并为其提供处理数据。测试用例的设计和使用几乎贯穿了软件测试的整个过 程，因此，测试用例的选择将直接影响软件安全性测试的质量，同时测试用例的合 理选取也会直接影响到测试项目的工期和成本。由此可见，测试用例的选择方法是 软件安全性测试中的一个首要的关键性问题，会直接影响到测试的成败。生成模糊 测试的数据是测试用例非常重要和关键的问题，利用高覆盖率、完备、精简的测试 数据生成测试套，可以提高整个测试系统的工作效率。目| j ，所有的模糊器都可被 分为两大类：基于变异的模糊器和基于牛成的模糊器。这两种力+ 法各有优缺点。对 青岛人学硕i ：学位论文 于安全性测试来说，最佳的测试数据应满足下列条件：( 1 ) 在满足安全性测试要求 的条件下，测试数据最精确。( 2 ) 对应不同的输入测试数据，程序表现出的异常不 同。由于对于大型复杂软件系统的穷举测试是不可能做到的，而基于遗传算法的测 试数据能够选择最符合软件安全性要求的测试数据，因此得到比较广泛的研究。 综上所述，本文提出的利用遗传算法的安全性测试数据生成方法去测试安全性 软件质量具有新意，由于遗传算法通过对数据的优化能够生成更加精确的测试数 据，能达到有效检测系统安全性质量的目的。 1 2 国内外研究动态 1 2 1 软件安全性测试 2 0 0 1 年软件安全性方面的第一部专业著作发表，标志着计算机软件系统安全 性开始受到了系统的研究。软件的安全性漏洞伴随着软件规模和复杂度的迅速提 高，2 0 0 3 年c e r tc o o r d i n a t i o nc e n t e r 发布了4 0 0 0 多个软件漏洞，比2 0 0 2 年多了 7 0 ，几乎是2 0 0 1 年的4 倍乜引。面对日益增多的软件安全性问题，软件安全性测试 也受到了研究者的重视，国内外己经有了许多研究成果。首先是基于软件设计阶段 的安全性需求分析方面，2 0 0 5 年p a u l i h l 针对安全信息系统提出了一种基于风险驱动 的架构设计。w i l a n d e r 和g u s t a v s s o n 畸1 提出忽视安全性需求是因为选择需求条件时， 细节设计上以及安全领域没有标准需求设计这几个方面的原因。针对这几方面的原 因他们提出了一种针对安全性方面的需求度量方法。 随后g a r ym c g r a w 发表了一系列的关于软件安全性及软件安全性测试方面的 论文，在他2 0 0 4 年的论文( ( s o f t w a r es e c u r i t y 匝1 中提出软件安全性贯穿于软件开 发与测试的整个生命周期h 1 ，并阐述了软件安全性在软件开发中的重要作用。在随 后的论文( ( s o f t w a r es e c u r i t y t e s t i n g ) ) | ：7 1 中说明了软件安全性测试与软件功能性测试 的区别，并且提出了基于风险模型的软件安全性测试方法。2 0 0 5 年他又发表了关于 软件安全性测试方法的论文，重点阐述了关于故障注入测试方法的基本原理，提出 了一种更好的故障注入测试方法，指出了故障注入测试方法的有效性3 。2 0 0 3 年， j o h nw a c k ，m i l e st r a c y 和m u r u g i a hs o u p p a y a 【9 1 详细的介绍了软件安全性测试在整个 系统生命周期中的重要性，介绍了主要的安全性测试技术，指出了安全性测试的发 展策略旧1 。2 0 0 7 年m a u r aa m a u r a ，v l i n d e n n 0 1 对软件安全性测试的和软件的漏洞知 识做了详细描述，并详细的介绍了多种安全性测试方法，包括渗透测试、s o l 注入 测试和f u z zt e s t i n g 等。2 0 0 6 年a s s o d i y a n 对软件的安全性测试的相关内容作了 详细研究，阐述了软件安全性测试的相关问题和建立安全性软件的难点，提出了安 伞。陀软件开发模型( s e c u r es o f t w a r ed e v e l o p m e n tm o d e l ( s s d m ) ) ，指出在开发软 件的过程中，如果能够按照该模型进行开发，就能有效的保证软件的安全性。并通 2 第一章绪论 过个案研究说明了模型的正确性。施寅生n 2 1 等将软件安全性测试分为软件安全功能 测试和软件安全漏洞测试，并对现有的安全性测试方法做了分析和研究，现有的软 件安全性测试方法主要有形式化安全方法，基于模型的安全功能测试方法，语法测 试，基于故障注入的安全性测试，模糊测试和基于属性的测试。其中模糊测试作为 一种发现安全漏洞的有效的测试方法，在安全性测试中越来越受到重视。 在分析和加强软件系统的安全性方面，很多学者提出了多种提高软件安全性的 方法。一种方法是h a l l 和r o d n 如在2 0 0 4 年通过p r a x i sc r i t i c a ls y s t e m sl i m i t e d 提出的 c o r r e c t n e s s b y - c o n s t r u c t i o n 方法，通过引入形式化语言对该方法进行了描述并对其模 型通过讨论和分析论证了该方法的正确性。此模型能使每一千行代码的漏洞率保持 在0 0 4 至u o 7 5 之间。另一种实现软件安全性系统的方法是“n g e r 和s t a c y 1 4 】提出的 c l e a n r o o m 。这种方法提出了开发过程中增加基于功能的详细说明和设计，正确性证 明和数据测试。基于这种方法他们将代码的漏洞率缩小到每千行代码只有o 1 到0 4 。 软件能力成熟度模型c a p a b i l i t ym a t u r i t ym o d e l s ( c m m s ) 口5 3 模型把系统工程过程中的 开发、管理、优化及执行能力作为系统工程能力的主要评价要素。1 9 9 7 年h e f n e r 提 出了系统安全工程能力成熟度模型s y s t e m ss e c u r i t yc a p a b i l i t ym a t u r i t ym o d e l ( s s e c m m ) 。2 0 0 3 年g o l d e r s o n 干i g i b s o n u 卅提出基于c m m s 的设计能够在总体上降低 软件在设计和执行时的漏洞。 与c m m 相似的是风险模型。风险模型用来分析计算机系统潜在的风险来防止 软件受到攻击。2 0 0 5 年m o g i l e v s k y , l e e 和y u r c i k ；m y a g m a r , l e e 和y u r c i k n7 1 在相关 的工作中证明了风险模型的在软件安全性分析方面的有效性。攻击树和攻击图在决 定软件安全性量度方面也有重要的作用。a h n ，j a n g 和c h u n n 哪在攻击树或攻击图方 面进行了大量的研究。攻击树模型的集合来源于有限状态机的状态集中的一部分， 在建立攻击树之前先进行潜在风险集合的建立，但是通过实验证明，攻击树和攻击 图这两种模型在安全性测试应用中不易于实现。 另一种丌发安全性软件的方法是由d a v i s 和m u l l a n e y 在2 0 0 3 年提出的软件团 队软件过程( t e a ms o f t w a r ep r o c e s s ( t s p ) ) n 引。团队软件过程的出现提供了一个实 用的、可靠的软件过程参考模型，这个模型加强管理和降低软件漏洞，将软件的漏 洞检测贯穿到整个软件的生命周期中，并采用预测的方法减少漏洞，从而提高了软 件的安全性。并将平均每千行代码的漏洞率控制在0 0 6 。 从相关文献可以看出，软件系统仍然存在安全性漏洞，攻击者只要能发现其中 的一个安全性漏洞就可以对整个系统造成损害，因此能够通过各种测试方法使软件 尽可能达到零b u g 率是非常重要的，因为一旦软件被攻击者损害就可能造成严重的 后果。 在具体的各种安全性测试方法上，国内外也有很多学者进行了大量的研究工作。 青岛人学硕士学位论文 1 2 2 错误注入技术 首次提出故障注入技术是在七十年代初期，作为计算机系统可靠性和容错机制 的试验评价方法开始是八十年代中期，直到九十年代后，该技术才越来越多的受到 研究人员和工程设计者的重视。w e n l i a n gd u 幢训在论文( ( v u l n e r a b i l i t yt e s t i n go f s o f t w a r es y s t e mu s i n gf a u l ti n j e c t i o n ) ) 分析了渗透性分析以及常规软件安全测试方法 在软件安全性测试方面的不足，提出软件安全性受运行环境的各种约束，建立了基 于故障注入测试方法的软件与环境交互模型( e n v i r o n m e n t a p p l i c a t i o ni n t e r a c t i o n f a u l tm o d e l ) e a i 澳i 试模型( 1 9 9 8 ) ，并指出了下一步的工作重点是将故障注入模型 应用于通用软件上。相关项目有o u s p g ( u n i v e r s i t yo fo u l u ，s e c u r ep r o g r a m m i n g g r o u p ) 的项目p r o t o ss e c u r i t yt e s t i n go f p r o t o c o li m p l e m e n t a t i o n s 。该项目的目标是 测试协议实现上的安全性。主要思路是通过构造植入故障的各类协议数据包来测试 目标软件是否能正确处理，如修改某些协议字段的值等，以发现被测软件是否存在 安全漏洞，支持的协议有h t t p 、s i 、w 、s n m 等。故障注入可以有效地模拟各 种各样的异常程序行为，通过故障注人函数能够强制性地使程序进入到某些特定的 状态，而这些状态在采用常规的标准测试技术的情况下一般是无法到达的。 y a o w e n h u a n g 2 1 1 在at e s t i n g f r a m e w o r kf o rw 曲a p p l i c a t i o ns e c u r i t y a s s e s s e m e n t ) ) 一文中指出w e b 应用程序的快速发展和开发周期的缩短使得w e b 应用 程序很难控制它的漏洞数量，研究了诸如软件故障注入测试和运行时监控测试的方 法应用在w e b 程序测试上，提出了一种对w e b 应用程序漏洞扫描的模型，建立了 一种基于黑盒测试的w e b 应用程序安全评估的自动化模型，通过实验说明了模型的 有效性。 静态测试和动态测试2 0 0 7 年c d dg r o s s o 昭列等人在文章( ( d e t e c t i n gb u f f e r o v e r f l o wv i aa u t o m a t i ct e s ti n p u td a t ag e n e r a t i o n ) ) 中说明了缓冲区漏洞对软件安全性 的重要影响，并对以往的静态测试和动态测试进行了分析，提出了基于遗传算法的 自动化测试方法，设计了一种完全自动化的进化算法来生成测试数据对软件的缓冲 区漏洞进行测试。 2 0 0 3 年p a u lm i d i a n 在论文( ( h o wt oe n s u r ea ne f f e c t i v ep e n e t r a t i o nt e s t ) ) 中讨论 了渗透性测试，漏洞扫描和软件安全性测试的相关知识心引。分析了漏洞扫描和渗透 性测试技术的不同之处，介绍了测试工具v m w a r e 。通过对来自于w e b 应用程序， s q l 数据库，h t m l 脚本语言和网关接口的攻击进行分析说明了渗透性测试方法在 软件安全性测试方面发挥的作用。 张继业在基于攻击图的渗透测试模型的设计中借鉴了攻击图这种成熟的攻 击模型，设计了基于攻击图的渗透测试模型( p e n e t r a t i o n t e s t i n gg r a p hm o d e l ) 但制， 将渗透测试仓过程映射到p t g m 模型中。江南计算机技术研究所的余静等人在对基 4 第一章绪论 于s q l 注入的渗透性测试技术也做了相关的研究，提出了渗透性测试的原型系统， 给出了主要的功能，通过对动网论坛的渗透性测试分析比较了原型系统的效能，并 能过实验表明了该原型系统能较好的发现系统s q l 注入的脆弱点，可以帮助管理 员提升系统的安全性。清华大学在软件安全性测试用例的动态生成方面也进行了大 量的研究，利用故障树的原理和方法，设计了故障树最小割集的生成算法，提出了 基于最小割集的安全性测试用例的动态生成算法。 1 2 3 模糊测试 对模糊测试最早的引用可以追溯到1 9 8 9 年。b a r t o nm i l l e r 乜钉教授( 被很多人认 为是模糊测试之“父 ) 和他的高级操作系统课开发和使用了一个原始的模糊器， 用来测试u n i x 应用程序的健壮性。测试的关注点并不是评价系统的安全性，而是 验证全部代码的质量和可靠性。尽管在该项研究的过程中提及了安全性考虑的问 题，但是在对s e t u i d 应用程序的测试中并没有专门强调这一点。1 9 9 5 年的研究发现 模糊测试让s e t u i d 应用程序的可靠性得到了改进，但是该应用程序仍然被认为“具 有较高的失效概率”。 m i l l e r 的小组所用的模糊测试方法是非常粗糙的。如果应用程序崩溃或者扶起， 那么就认为测试失败，否则就认为测试通过。所用的方法是简单地向目标应用程序 抛出随机字符串，这是一种纯黑盒的方法。尽管这种方法看上去可能过于简单，但 是在那个时候甚至还没有人听说过模糊测试的概念。 大约在1 9 9 9 年，o u l u 大学开始进行p r o t o s 测试集的开发工作。通过首先分 析协议规约然后产生违背规约或者很有可能让协议实现无法j 下确处理的报文，各种 各样的测试集先后开发出来。一开始时，产生这样的测试集需要耗费相当大的努力， 但是一旦产生之后，这些测试集就可以用来测试多个供戍商的产品，这个例子属于 白盒和黑盒混合混合的测试方法，由于后来证明大量的故障是用这样的方法发现 的，标志着模糊测试发展历程中的一个重要罩程碑啦6 。 2 0 0 2 年m i c r o s o f t 为p r o t o s 提供了资金支持，2 0 0 3 年p r o t o s 组的成员开 发了c o d e n o m i c o n 乜 ，这是一个专门致力于设计和产生商业用模糊测试集的公司。 该公司今天的产品仍然基于最初的o u l u 测试集，不过又包括了一些图形用户界面、 用户支持以及通过健康特征枪测而实现的故障检测能力，此外还增加了其他一些特 征。 随着p r o t o s 在2 0 0 2 年逐渐成熟，d a v ea i t e l 发前i 了一个丌放源代码的模糊器， 名为s p i k e 啪1 ，采用了g u n 许可( g p l ) 。a i t e l 的模糊器实现了一种基于块的方法， 目的是为了测试基于网络的应用程序。s p i k e 采用了一种比m i l l e r 的模糊器更高级 的方法，最显著的特征是包括了描述可变长数据块的能力。此外，s p i k e 不仅能够 生成随机数据，而且包括一组预定义的函数，这些函数能够产生常见的协议和数掘 气 青岛大学硕十学位论文 格式，其中包括s u nr p c 和m i c r o s o f tr p c 。它们是两个常见的通信协议，过去发 现的许多安全漏洞都起源于它们。作为第一个允许用户创建自定制模糊器的公开框 架，s p i k e 的发布标志着一个重要的里程碑。 大致在s p i k e 发布的同一时间，a i t e l 还发布了一个名为s h a r e f u z z 汹1 的本地u n i x 模糊器。与m i l l e r 的模糊器不同，s h a r e f u z z 以环境变量为目标而不是以命令行参数 为模糊测试目标。s h a r e f u z z 还采用了一个有用的技术来促进模糊测试过程。它使用 共享数据库来挂起函数调用，这些函数返回的环境变量值是一些长字符串，为的是 发现缓冲区溢出漏洞。 在s p i k e 发布之后的大多数模糊测试技术是以不同类型的具体模糊测试工具出 现的。m i c h a lz a l e w s k i ( 又名l a c a m t u f ) 于2 0 0 4 年发布的m a n g l e m e 关注w 曲浏览 器的模糊测试，m a n g l e m e 是一个公共网关接1 ：3 ( c g i ) 脚本，可用来持续产生畸形 的、在一个目标w e b 浏览器中被反复刷新的h t m l 文件。随后很快又出现了几个以 w e b 浏览器为测试目标的模糊器。h d m o o r e 和a v i vr a f t 开发了h a m a c h i ，用来对 动态h t m l 脚本进行模糊测试以查找其实现缺陷，他们两个后来与m a t tm u r p h y 和t h i e r r yz o l l e r 合作又推出了c s s d i e ，这是一个对重叠样式表进行解析的模糊器 3 0 】 o 文件模糊测试。的兴起始于2 0 0 4 年。那一年m i c r o s o f t 发布了m s 0 4 2 8 安全公 告，详细描述了负责j p e g 文件的引擎中的一个缓冲区溢出漏洞。尽管这并不是第 一个被发现的文件格式方面的安全漏洞，但是它还是吸引了人们的注意力，因为许 多流行的m i c r o s o f t 应用程序都共享这段有漏洞的代码。文件格式安全漏洞对网络 的保护者也提出了挑战。尽管相当数量的类似漏洞在随后几年相继出现，但是如果 我们仅仅阻止有可能存在漏洞的文件格式进入公司的网络，也是不切实际的。图像 和媒体文件构成了i n t e m e t 流量中相当大的一部分。此外，这些漏洞中的大多数在 不久后就会对m i c r o s o f t 的o f f i c e 文档文件产生威胁。文件格式安全漏洞最后成为 基于变异模糊测试要发现的主要候选漏洞，因为漏洞的样品容易获得，并且文件格 式可以在监视目标应用程序故障的同时快速地连续变异。我们在b l a c kh a tu s a b r i e f i n g si n2 0 0 5 上做了陈述并发布了一系列同时基于变异和生成的工具，用于对文 件格式进行模糊测试，包括f i l e f u z z 、s p i k e 6 l e 和n o t s p i k e n l e 。 2 0 0 5 年，一个名为m us e c u r i t y 的公司开始开发一种硬件模糊器装置口2 1 ，其目 的是让网络中传输的协议数据发生变异。这个商业产品供应商的出现，恰好吻合了 当前人们关注模糊测试的潮流。我们丌始看到日益增加的可用的商业模糊测试解决 方案，同时伴随着模糊测试技术的自由软件解决方案的出现。另外，大量的开发者 和安全领域的研究人员开始对模糊测试感兴趣，一个明显的证据是他们创建了模糊 测试邮件列表，该邮件列表由g a d ie v r o n 维护。办有时间才能说明未来将会有什么 样的创新在等待着我们。 6 第一章绪论 a c t i v e x 模糊测试在2 0 0 6 年开始流行，当年d a v i dz i m m e r 发布了c o m r a i d e r ， h d m o o r e 发布了a x m a n 1 。这两个工具关注那些在访问m i c r o s o f ti n t e m e te x p l o e r 浏览器时能够被w e b 应用程序实例化的a c t i v e x 控件。此类应用程序中的可被人远 程利用的漏洞是一种高风险，因为此类应用程序的用户群体十分庞大。就像人们最 后发现的那样，a c t i v e x 控件是一种优秀的模糊测试目标，由于其中包括了接口、 函数原型和实际的控制逻辑，从而允许对其实施自动化的智能测试。 1 2 4 遗传算法 遗传算法1 最早是由b a g l e yj d 博士在1 9 6 7 年提出的，1 9 7 5 年，随着m i c h i g a n 大学的j o h nh o l l a n d 教授的第一本系统论述遗传算法和人工自适应系统的专著 ( ( a d a p t a t i o ni nn a t u r a la n da r t i f i c a ls y s t e m s ) ) 的发表，遗传算法的理论和应用研究 正式兴起，遗传算法是一种全新的随机搜索与优化算法，其基本思想是基于达尔文 的进化论和孟德尔的遗传学说。遗传算法的基本思想简单，便于实现和并行搜索的 优点得到了多种领域的广泛应用。随着遗传算法应用的不断深入，它的收敛速度慢 和陷入局部最优的问题在优化的参数较多时，凸显了遗传算法的不足。目前，在改 进遗传算法的研究中，尤以遗传算法与其他算法相结合方面最受关注，现在比较常 见的混合遗传算法嘲1 有模拟退火遗传算法，免疫遗传算法，小生境遗传算法，模糊 遗传算法，混沌遗传算法和量子遗传算法汹3 等。 在当今系统的开发中，安全性测试占了非常重要的比例，遗传算法也得到了广 泛的应用。面向路径覆盖测试啪3 属于动态测试的一种，它要求在程序安全性测试过 程中，尽可能覆盖程序能够到达的所有与安全性相关的路径。在2 0 0 6 年的美国安 全会议b l a c k h a t 上发表了佛罗里达中央大学( u c f ) 的一个团队近期所研究应用遗 传算法以提高模糊测试的性能的相关研究成果。u c f 团队发布了一个能够自动生成 输入使程序强制按照一个设计好的路径执行的名为s i d e w i n d e r 的概念验证工具。在 这种情形下，应用定义的一个适应度函数作为模糊测试的方法。模糊器将生成提供 给目标进程的输入，在数据优化时选择适应度最高的个体。然后继续执行整个过程 直到成功到达一个潜在漏洞的目标节点。 基于路径覆盖的用于改进模糊测试性能的遗传算法设计是一种白盒测试的方 法。白盒测试要求在掌握程序源代码的基础上对程序进行控制流程图的设计，路径 的选择进行测试。但随着现在组件技术的发展，不可能掌握所有待测程序的源代码， 在这种情况下，路径覆盖的测试方法就展示出了很大的局限性。虽然有反汇编技术 做支持，但仍需要耗费大量的人力和物力资源，在这种条件下基于黑盒的安全性测 试方法受到了广泛关注。 7 青岛人学硕士学位论文 1 3 论文的主要工作和创新点 根据以上的背景情况及国内外的研究现状，在课题的研究过程当中，主要做了 如下工作： 1 广泛的阅读文献，分析研究目前国内外已有的安全性测试方法。学习了现有 的安全性测试技术和安全测试用例生成技术。对软件安全性测试方法进行对比分 析，比较各种方法的优缺点，重点讨论了基于错误注入的测试方法和模糊测试数据 的生成问题。 2 对软件的故障注入测试方法进行了详细的分析，讨论了基于模糊测试方法 生成安全性测试数据的问题，对随机生成测试数据的不确定性导致的测试数据爆炸 问题进行研究，提出将遗传算法应用到模糊测试数据的优化过程中，将软件的安全 规则设计成适应度函数，当适应度值取得预期最大值时，输入的测试数据为符合要 求的测试数据。 3 研究基于遗传算法的安全性规则覆盖测试用例的自动生成，对遗传算法的一 些操作进行了改进，并对实验结果进行了对比分析。 论文的创新点如下： 1 针对基于路径覆盖的模糊测试数据生成方法的不足，借鉴动态环境错误注 入的测试方法，针对应用程序的环境错误注入点利用模糊测试方法生成模糊测试数 据对程序进行错误注入，达到安全性测试的目的。并利用相关完全覆盖策略，设计 出基于错误注入的模糊测试数据生成算法。 2 针对模糊测试方法的安全性测试数据生成的不确定性导致的测试数据爆炸问 题进行研究，提出利用遗传算法对模糊测试数据进行优化的方法，从而能利用发展 较为成熟的遗传算法设计能够针对软件安全性漏洞更为精确的测试数据。 3 通过一个安全性要求高的系统阐述基于遗传算法的模糊测试方法在实际安全 性测试中的应用，并通过与遗传自适应算法得到的测试结果的对比和分析来讨论基 于遗传算法的安全性测试用例设计方法的优点及其不足之处。 本文主要用基于遗传算法的模糊测试数据生成方法对软件的安全性u j 题进行研 究，提出改进方法，使其由原先的随机生成测试数据模糊器扩展到通过利用与遗传 算法相结合的模糊器来生成测试数据，并对测试数据的自动生成方法提出解决方 案，使得由该方法产生的测试用例更有利于测试的实际执行。 1 4 论文的结构与章节安排 论文的结构与章节安排如下： 第一章简要介绍困内外灭于软件安伞性测试方法、故障注入测试方法和模糊测 试的研究现状以及论文的研究内容和解决的主要问题。 8 第一章绪论 第二章主要介绍软件安全性测试的基本知识，对错误注入测试方法进行了详细 的分析，说明模糊测试作为错误注入测试的一种方法在软件安全性测试方面有着极 其重要的作用、并对遗传算法进行了简要描述。 第三章着重阐述基于模糊测试故障注入测试问题，包括模糊测试的概念，测试 阶段，模糊测试方法和模糊器的分类，以及引入基于遗传算法的模糊测试方法。 第四章提出了基于遗传算法的模糊测试数据自动生成的方法，进行了完整的策 略设计，对遗传算法进行了详细的设计和分析，设计了基于遗传算法的模糊器模型。 第五章通过以w e b 浏览器的安全性测试为实例，描述了基于遗传算法的模糊测 试数据生成的整体设计和实现，并进行了分析。 第六章结论与展望。分析了论文的创新之处和测试数据自动生成的发展前景以 及有待于进一步解决的问题。 最后致谢和参考文献。 9 青岛人学硕士学位论文 l o 第二章软件安全性测试概述 第二章软件安全性测试概述 软件安全性刀是软件在受到恶意攻击时仍能提供所需功能的能力。软件安全性 测试是确定软件的安全特性是否与预期设计一致的过程( 施寅生，邓世伟，谷天阳， 2 0 0 8 ) 。软件漏洞引起的安全性问题越来越多，这些漏洞被称为是软件的安全性错 误的缺陷。软件的安全性影响着开发者和用户使用软件的可靠性。软件安全性测试 的工作就是希望通过测试检测出软件的安全性漏洞使得软件在使用过程中能够很 好的抵制恶意攻击。目前在提到软件安全性时考虑的更多的是功能安全性方面的需 求，安全性需求也包括非功能性的或者不包括在需求和设计模型当中的需求。功能 性的需求是很容易被描述，设计，执行和测试的。但是对于安全性需求，在需求分 析时，并没有告知设计人员，软件要能抵制哪方面的攻击威胁，所以对于攻击威胁 方面的安全性要求是无法预言和很难规范的。 软件安全性在软件工程的不同阶段有着不同的表现，如需求分析的安全性、概 要设计的安全性、详细