数字水印算法在多媒体图像上的应用研究.docx
《数字水印算法在多媒体图像上的应用研究.docx》由会员分享，可在线阅读，更多相关《数字水印算法在多媒体图像上的应用研究.docx（36页珍藏版）》请在冰点文库上搜索。
数字水印算法在多媒体图像上的应用研究
摘要
软件测试是保证软件质量和可靠性重要手段，在这方面发挥着其它方法不可替代的作用。
然而，软件测试是一，需要耗费巨大的人力、物力和时间，约占整个软件开发成本的40%～50%。
因此，提高软件测试工具的自动化程度对于确保软件开发质量、降低软件开发成本非常重要。
而提高测试用例生成的自动化程度又是提高测试工具乃至整个测试过的关键所在，本文主要针对这一问题进行了研究和设计。
本文在分析软件测试和算法基本概念的基础上，提出软件测试用例的设计是软件测试的难点之一。
论文提出的测试用例生成的内含是应用算法来求解一组优化的测试用例，其框架包括了测试环境构造、算法及测试运行环境三部分，论文给出了基于算法的测试用例生成的进行测试用例生成可行。
关键词：
软件测试测试用例算法
ABSTRACT
Softwaretestistheimportantmeansthatguaranteesoftwarequalityandreliability，andinthisrespect，itplaystherolethatothermethodcannotreplace.Howeversoftwaretestisacomplexprocess,itneedstoconsumehugemanpower，materialresourcesandtime，whichtakesthe40%~50%ofentiresoftwaredevelopmentcostapproximately.Therefore，raisingtheautomationlevelofsoftwaretesttoolisveryimportantforensuresoftwaredevelopmentqualityandreductionsoftwaredevelopmentcost.Andthen，themostimportantisraisingtheautomationlevelofthetestcasegenerationforraisingtheautomationleveloftesttoolandevenentiretestprocess，sothispaperstudyanddesignmainlyaccordingtothisproblem.
Basedontheanalysisofbasicconceptsofsoftwaretestingandgeneticalgorithm,thisarticleproposesthatsoftwaretestcasedesignisoneofthedifficultiesofsoftwaretesting.Paperpresentstheinherentinsoftwaretestcasedesigningbasedongeneticalgorithmisusinggeneticalgorithmtosolveasetofoptimizationtestcases,andtheframeworkincludesthreepartswhicharetestenvironmentconstruction,geneticalgorithmandtheenvironmentfortest.Paperpresentsthemodelofsoftwaretestcasegenerationbasedongeneticalgorithm.Finally,wetakethetrianglecategorizerasanexample,simulatesoftwaretestcasegenerationbasedongeneticalgorithm.Theresultsdisplaythatsoftwaretestcasegenerationbasingongeneticalgorithmispossible.
KEYWORDS:
softwaretest,testcase,geneticalgorithm
目录
摘要2
ABSTRACT3
目录4
第一章绪论6
1.1问题的提出6
1.2国内外研究现状7
1.3论文研究内容9
第二章软件测试及算法基本概念10
2.1软件测试基本概念10
2.1.1软件测试的目的10
2.1.2软件测试的原则10
2.2软件测试的难点11
2.3算法12
2.3.1算法的思想及流程12
2.3.2算法的特点14
2.4本章小结15
第三章基于算法的测试用例生成16
3.1基于算法的测试用例生成基本内涵16
3.1.1软件测试用例的基本内涵16
3.1.2基于算法的测试用例生成的基本内涵17
3.2基于算法的测试用例生成框架17
3.3基于算法的测试用例生成算法实现19
3.3.1编码策略19
3.3.2适应度函数及程序插桩20
3.3.3策略21
3.3.4参数控制23
3.4本章小结23
第四章实验及结果分析24
4.1待测程序分析24
4.1.1待测程序引入24
4.1.2程序流程分析24
4.1.3路径分析25
4.2程序插桩25
4.3参数设定及程序实现26
4.3.1参数设定26
4.3.2部分程序实现26
4.4结果分析29
4.5本章小结31
第五章总结与展望32
致谢语33
参考文献34
第一章绪论
1.1问题的提出
在信息化普及的今天，计算机在人们的生活和工作中占据着重要地位，使人们的工作效率提高，也使生活更丰富多彩。
而作为计算机的重要组成部分，软件的重要性不言而喻。
随着计算机技术的日益发展，计算机软件的规模越来越庞大，复杂性越来越高，这就为软件质量的保证带来了困难。
因为软件的开发过程大部分是由人的智力活动构成，不可能完美无缺。
而软件缺陷如果不能及时发现，带来的损失可能是巨大的，有的甚至会危及人的生命。
在历史上臭名昭著的软件缺陷案例有[1]：
1999年12月3日，美国航天局的火星基地登陆飞船在试图登陆火星表面时失踪，原因仅仅是一个数据位的意外更改；美国爱国者导弹防御系统曾在几次对抗导弹战役中失利，其中一次竟然误使28名美国士兵丧生，原因是一个很小的系统时钟错误导致系统累计拖延了100多个小时使跟踪系统失去准确度；还有就是大名鼎鼎的“千年虫”问题，起因是在20世纪70年代，为了节省硬盘空间，美国某位程序员在编写工资系统时将4位数日期（如1975）改成了2位数日期（如75），该缺陷一直拖到1995年都没有修复，最终给全球带来了高达数亿美元的损失等等。
作为提高软件质量的重要手段，软件测试越来越受到重视。
在美国的微软公司，测试人员和开发人员的比例达到了2：
1[2]。
软件测试伴随着整个开发过程，是一个非常复杂的过程，其消耗的人力和资金一般占整个项目的一半左右。
而在某些特别重要的软件开发过程中，为保证软件的质量，测试的费用甚至是其它各阶段之和的3到5倍[3]。
测试过程中，测试人员通常需要分析、设计和执行大量的测试用例，从而耗费了大量资源，因此找出合理的测试用例生成方法可以有效缩短测试时间，减少损耗，一般可以有效降低整个项目的4%费用[4]。
然而，目前生成测试用例的方法主要是向前核查法和逆向回溯法，测试人员根据自己的项目经验手工为指定的程序路径生成测试数据[5]。
向前核查法是指沿预期的路径向前检查，确定到每一个判断点时变量所能提供的最宽数值区间，然后继续前行，从而将多个变量的可能取值范围逐渐缩小，到达程序出口后，就能找到覆盖这条路径所需的输入数据。
逆向回溯法正好相反，是指从期望执行的程序位置出发，逆向回溯，在每个判断点处逐渐调整各变量取值，直到退到程序入口，即获得所需的输入数据。
向前核查法和逆向回溯法的局限性是，对某些条件要求苛刻的路径使用时非常困难，同时由于大多数程序中包含的路径数非常多，如果按每条路径手工测试，显然带来的工作量是非常巨大的。
由于测试的工作量大、测试过程的重复性高等特点，自动化测试正逐渐得到广泛的应用。
很多测试工具的使用大大提高了测试人员的工作效率，有效减少了项目开支。
然而这些工具主要为测试的执行、管理和度量工具，在测试用例自动生成方面还不完善。
而在软件测试过程中，动态测试作为测试的重要环节占了很大比例，动态测试的关键正是测试用例的生成问题。
因此，寻找一种有效的测试用例生成方法是提高测试自动化的重中之重。
1.2国内外研究现状
自上世纪60年代起，国内外的学者专家对测试用例的自动生成提出了很多方法，应用较为广泛的有随机法、静态法、动态法以及试探法[5][6][7][8][9][10][11][12]。
D.Bird[13]等提出了采用随机法生成测试用例，其思想是不受限制地随机产生大量的测试用例。
该方法产生测试用例的成本很低，在某些抽样测试中效果较好，但是该方法的针对性较弱，在输入空间为无穷大时产生的测试用例集非常庞大，测试效率低，现在的很多工具都是采用的该方法。
静态法的典型代表是符号执行法，由P.D.Coward[14]和C.Ramanmoorthy[15][16]等人提出。
该方法的主要思想是把符号值作为程序输入，静态“执行”指定路径的语句，从而得到变量的值。
这里所谓的执行，是指按照程序执行的顺序将相应的变量用符号表达式代换。
该方法的缺点为需要进行复杂的代数运算，难以处理依赖于输入变量的循环条件、数组元素下标和模块调用的情况，特别对于动态的面向对象程序不适合使用。
与静态法相对应的是动态法，该方法的基本思想是从输入空间中任取一个假设解作为初始输入，通过实际运行程序不断调整输入，使得程序实际执行路径向指定路径不断逼近，直到与指定路径完全一致。
Korel[17]法是动态法的典型代表：
其采用的是步进的方式执行程序，即一次只前进一个分支谓词；Korel还提出了“谓词函数”的概念，用来度量分支谓词的接近满足程度。
然而，由于Korel法一次只考虑一个分支谓词，使用回溯技术，所以要进行大量的迭代，浪费了大量的资源。
而且由于对于非线性路径约束，该方法只能找到局部极小值，当谓词函数有多个局部极小值时显然将难以找到目标路径的解。
除此之外，动态法还包括程序插装的方法和迭代松弛法，M.Gallagher和NeelamGuptal[18]分别对这两种方法进行了全面的阐述。
第四种算法是试探法，该方法的基本思想是从输入数据空间中选择输入数据，运行程序，将运行结果结合概率论的思想产生新的数据继续进行试探。
其受搜索空间限制条件的约束小，且不需要其它辅助性信息，对于很多高复杂度问题（如大空间、多峰、非线性、全局优化等）具有独特的优势和高效性。
试探法主要包括算法、模拟退火算法、禁忌搜索算法、混合策略的算法等。
自20世纪90年代起，算法因其独特的优点而开始被广泛的用于测试用例的生成领域，并取得了良好的研究成果。
算法模拟生物学中的变异原理，采用编码技术将待求数据映射到基因空间，并通过选择、交叉、变异等操作和优胜劣汰的自然选择确定搜索方向，从而找到最优解。
实验证明，该算法具有隐性并行性和全局寻优能力，可以自动获取搜索过程中的有关信息并用于指导优化。
Jones等人[19]的实验表明，为使三角形分类等程序达到分支覆盖，算法生成的测试数据比随机法小一到两个数量级。
Jin-CherngLin等人[20]等人对适应度函数进行了研究，提出了使用广义海明距离来构建适应度函数。
荚伟[21]分析了算法在测试用例产生这一问题上的可行性，提出了要有效解决该问题，必须从以下几个角度进行研究：
参数的编码方法、适应度函数的构造、算子的设计以及算法参数的选择等。
Berndt等人[22]将输入空间划分成多个区间，根据待选输入的多种特性创建了一个最小化函数,使用简单算法进行求解,并使用了求解过程中的化石记录来指导求解过程。
景志远[23]则从数学的角度分析了将MGA和K均值等改进的算法应用于测试用例的自动生成。
蔡立志等人[24]提出了一种基于算法的成对测试生成方法,该方法用于选择当前局部优化覆盖的测试用例，以此构建满足成对测试基准的测试用例套，有效降低了相同覆盖率下的测试用例数量。
陈雨等人[25]将自适应算子和禁忌搜索思想融入到算法中，充分发挥算法的全局搜索和禁忌搜索算法局部搜索优势,提高了测试数据的生成能力。
全君林等人[26]提出了一种应用于软件回归测试过程中的基于算法的最小化测试用例集算法模型，该算法较一般的优化算法具有更高算法性能与效率。
1.3论文研究内容
本文主要做了以下方面的研究：
（1）广泛阅读了国内外相关文献资料，对软件测试和算法的应用现状进行了概述，认为使用算法进行测试用例生成可行。
（2）分析了使用算法进行测试用例生成的基本内涵，提出了算法框架及对算法进行实现的具体策略。
（3）以三角形分类程序为例进行试验，分析了试验结果，证实了算法的优越性。
第二章软件测试及算法基本概念
2.1软件测试基本概念
2.1.1软件测试的目的
1983年IEEE在“软件工程标准术语”中将软件测试定义为：
“使用人工或自动手段来运行或测定某个软件系统的过程，其目的在于检验该被测软件是否满足规定的需求或是衡量预期结果和实际结果之间的差别。
”
定义中指出软件测试的目的是“检验该被测软件是否满足规定的需求或是衡量预期结果和实际结果之间的差别”
Grenford.J.Myers在其著作《TheArtOfSoftwareTesting》中提出了与软件测试相关的三个重要观点，指明了软件测试的目的为：
软件测试是程序的执行过程，目的在于发现错误；
一个好的测试用例是指很可能找到迄今为止尚未发现的错误的用例;
一个成功的测试是指发现了迄今为止尚未发现的错误的测试。
由此可见，软件测试的目的可以概括为：
首先，软件测试要以最少的人力、物力，尽快找出软件中潜在的各种缺陷，通过修正这些缺陷，提高软件产品质量，尽量减少软件产品发布后由潜在的软件缺陷带来的可能的商业风险。
其次，通过分析软件缺陷产生的原因，可以帮助发现当前开发开发过程中的软件过程缺陷，以便进行软件过程的改进。
同时，通过对测试结果的分析整理，还可以修正软件开发规则，并为软件可靠性分析提供依据。
2.1.2软件测试的原则
软件测试作为一门独立的计算机软件技术，在执行过程中必须遵守一定的原则，以保证测试效果。
软件测试的专家们经过长期的实践，总结出了软件测试的原则应如下：
应把“尽早和不断地进行软件测试”作为软件开发者的座右铭。
实践证明单元测试能够尽早发现问题,减少后期测试的错误量。
单元测试过程中可以使用相应白盒测试工具（如Junit，Jtest等）进行辅助测试，以提高测试效率。
测试用例应由测试输入数据、测试执行步骤和与之对应的预期输出结果三部分组成。
应当避免由程序员检查自己的程序。
特别在后期的性能测试及系统测试中，应避免程序员测试自己的程序。
这其中除了某些心理因素外，该原则还可避免由于程序员个人的惯性思维而导致的某些理解错误。
测试用例的设计要确保能覆盖所有可能路径。
在设计测试用例时，应当包括合理的输入条件和不合理的输入条件。
不合理的输入条件是指异常的、临界的、可能引起问题的输入条件。
充分注意测试中的群集现象。
经验表明，测试后程序残存的错误数目与该程序中已发现的错误数目或检错率成正比。
应该对错误群集的程序段进行重点测试。
严格执行测试计划，排除测试的随意性。
软件测试是有组织、有计划、有步骤的活动。
测试计划应包括：
所测软件的功能，输入和输出，测试内容，各项测试的进度安排，资源要求，测试资料，测试工具，测试用例的选择，测试的控制方法和过程，系统的配置方式，跟踪规则，调试规则，以及回归测试的规定等等以及评价标准。
应当对每一个测试结果做全面的检查。
妥善保存测试计划，测试用例，出错统计和最终分析报告，为维护提供方便。
2.2软件测试的难点
（1）测试用例设计
测试用例及测试例程是其设计者对被测对象实现原理和外部需求的理解，能否正确反映对被测对象的质量要求，很大程度上取决于其设计者的分析、理解和设计能力。
这是一种缺乏指导性方法的、不易制订标准或规范的、需要“技巧”的设计活动。
（2）测试管理
目前缺乏测试管理方面的资料，几乎没有可供参考的、已实现的、完整的测试管理与测试实施模式。
（3）测试的组织
软件测试的有效实施需要开发组织与测试组织充分配合。
虽然测试活动看似是对开发人员劳动成果的不断“挑剔”，但测试工作的出发点是：
确保开发人员的劳动成果成为可被接收的、更高品质的软件产品。
因此，测试人员应向开发人员谦虚求教，在测试工作中真正发挥作用，为保证软件产品的高质量起尽可能大的作用。
测试的组织者应在促进上级组织协调各组织工作方面发挥作用。
（4）测试的估计
有效的测试工作需要投入足够的人力和物力，需要对工作的难度和消耗有充分的估计。
测试的组织者也应在促进上级组织对资源的统一调度方面发挥作用。
2.3算法
2.3.1算法的思想及流程
算法（geneticalgorithm）是模拟达尔文的选择和自然淘汰的生物进化过程的计算模型。
该算法最先于1975年由美国的J.Holland教授提出。
其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
算法作为一种不依赖具体问题的直接搜索方法受到广泛关注，它是现代有关智能计算的关键技术之一。
算法的思想源于生物学和适者生存的自然选择规律，因此是具有“生存+检测”的迭代过程的搜索算法。
它以一个群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。
算法将问题的解空间映射为空间，对解空间进行编码，即将每个可能的解用一串二进制或十进制数字串表示，称为一个染色体，解的每个分量称为一个基因。
算法开始时先随机给出一群染色体，即候选解，由预先设定的某个评价指标计算每个染色体的适应值，将适应度低的染色体淘汰掉，而保留适应度高的优良染色体，然后对这些染色体进行选择复制、交叉和变异等操作，从而产生新的一代染色体群体。
这样一代一代的“进化”，直至找到算法的最优解，即适应值满足条件的解。
由于算法产生的“后代”是由优秀的“父代”和“母代”产生的，因此继承了上代的优良性态而优于上代，从而使算法向着最优解的方向进行，直到满足预先设定的条件。
算法过程包括了编码、产生初始群体、计算适应值、选择、交叉、变异等操作。
其一般流程图如图2-1所示：
图2-1算法流程图
2.3.2算法的特点
算法是一类可用于复杂系统优化计算的搜索算法，与其他一些优化算法相比，它的主要特点有如下几点[27]：
（1）算法以决策变量的编码作为运算对象，而传统优化算法往往直接利用变量的实际值来进行优化计算。
这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念以及和进化机理。
特别是对—些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独待的优越性。
（2）算法直接以目标函数值作为搜索信息，而不需要目标函数的导数值等其他辅助信息。
这个特性对很多目标函数难以求导的优化问题，以及组合优化问题等，应用算法时就显得比较方便。
而且，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。
（3）算法同时使用多个搜索点的搜索信息，而传统的优化算法往往是从解空间中的一个初始点开始最优解的迭代搜索过程。
单个搜索点的搜索效率不高，甚至可能使搜索过程陷于局部最优解而停滞不前。
算法通过对个体组成的群体进行操作运算，产生新的群体，其中包含的群体信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是算法所特有的一种隐性并行性。
（4）算法使用概率搜索技术，而很多传统的优化算法往往使用的是确定性的搜索方法。
确定性的方法由于固定了点与点之间的转移方法和转移关系，往往可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。
而算法属于一种自适应的概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了算法搜索过程的灵活性和搜索效率。
2.4本章小结
本章首先介绍了软件测试的一些基本概念，对软件测试的知识做了系统的介绍，包括软件测试的目的、原则、过程，介绍了了软件测试的主要技术难点，其中包括了测试用例的设计。
本章后半部分介绍了算法的基本概念，包括算法的思想、流程及特点。
第三章基于算法的测试用例生成
3.1基于算法的测试用例生成基本内涵
3.1.1软件测试用例的基本内涵
测试用例是为某个特殊目标而编制的一组测试输入、执行条件以及预期结果，以便测试某个程序路径或核实是否满足某个特定需求，包含输入和输出两部分。
构造测试用例的目的是为了检查被测软件的操作结果是否与预期的需求相吻合，确定应用程序的某些特性是否正常的工作等。
测试用例的质量可以用以下四个标准来描述:
（1）有效性:
是否能够发现缺陷，或者至少可能发现缺陷；
（2）仿效性:
可仿效的测试用例能够测试多项内容，从而减少测试用例的数量；
（3）经济性:
测试用例的执行、分析和调试是否经济；
（4）修改性:
软件修改后测试用例的维护成本。
实践中，设计测试用例需遵守一定的原则，这些原则主要有：
（1）全面性
包括：
应尽可能覆盖程序的各种路径；应考虑存在跨年、跨月的数据；大量数据并发测试的准备等。
（2）正确性
输入界面后的数据应与测试文档所记录的数据一致且预期结果应与测试数据发生的业务吻合。
（3）符合正常业务惯例
测试数据应符合用户实际工作业务流程且兼顾各种业务变化的可能。
（4）仿真性
人名、地名、电话号码等应具有模拟功能，符合一般的命名惯例；不允许出现与知名人士、小说中人物名等雷同情况。
（5）可操作性
测试用例中应写清测试的操作步骤，不同的操作步骤相对应的操作结果。
3.1.2基于算法的测试用例生成的基本内涵
使用算法实现测试用例的自动生成可描述为[12]：
应用算法来求解一组优化的测试用例。
在每一步进化计算过程中，测试用例自动生成器使用当前群体（测试用例）驱动被测试程序的执行，每一个测试用例的执行路径被跟踪和记录，以最大化程序执行路径的覆盖为适应性目标函数进行计算，产生出下一代群体。
在多代进化之后，得到最优种群或超过特定的循环限制条件而结束。
因为测试用例的自动生成是在一个数据域中寻找满足给定的测试标准的一组测试输入数据的过程，所以近年来出现了把测试用例的生成问题转化成路径搜索问题的思想。
由于一般情况下，测试数据的产生是一个不可判定性问题，再加上被测程序的规模和复杂性，一般的搜索算法受到了极大的限制。
算法在处理不确定搜索问题时有着非常明显的优势。
算法能针对程序路径生成大量有效测试用例，因此符合测试用例设计的全面性、正确性等原则。
生成的测试用例符合上节中的测试用例设计标准，特别是有效性和经济性等，由此可见算法应用
升级会员 