基于路径覆盖的测试用例生成算法研究

基于路径覆盖的测试用例生成算法研究

姓名：李煜申请学位级别：硕士专业：计算机软件与理论指导教师：陈金水

20080601

河海大学硕上论文摘要摘要随着计算机技术的不断发展，计算机软件占据着重要的地位。软件危机的出现，让更多计算机Ｔ作者意识到保证软件质量的重要性。软件测试是保证软件质量的唯一有效的方法，而测试用例的生成又是软件测试的关键。测试用例设计的好坏直接影响软件测试的有效性。本文探讨一种白盒测试中测试用例自动生成的搜索算法，旨在为软件测试提供完整的测试．｝ｆｊ例。路径覆盖是白盒测试中覆盖率最高的一种覆盖方法，结构化测试数据一般都是通过路径覆盖的方式来生成。根据不同的路径，可以生成覆盖不同路径的测试数据，所有路径的测试数据就组成了程序完整的测试用例。在研究测试数据生成的搜索算法时，本文在原有搜索算法只针对一维谓词的基础上，增加了对复合谓词处理的方法，提出了针对复合谓词的分组搜索算法。在测试数据搜索过程中，本文还引入了程序切片技术，这是一种分析和理解程序的技术，可抽取有用的程序片段，具有简化程序代码的特点。本文详细介绍了切片技术的发展、切片的分类、切片准则、切片算法思想，重点介绍了基于前向分析的动态切片算法。最后，本文提出了一种测试用例生成的系统框架，详细说明了该系统的流程，以及各个模块预期实现的功能，并给ｆｎ了具体的算法思想。最后通过实例，验证了系统框架的可行性。关键词：软件测试、测试数据、测试用例、路径覆盖、切片技术、复合谓词、分支函数。河海人学硕十论文摘要ＡｂｓｔｒａｃｔＷｉｔｈｔｈｅｄｅＶｅｌｏｐｍｅｎｔｏｆｃｏｍｐｕｔｅｒｔｅｃｈｎｏｌｏｇｙ，ｃｏｍｐｕｔｅｒｓｏ仟ｗａｒｅｐｌａｙｓｍａｋｅｓｍｏｒｅｃｏｍｐｕｔｅｒｗＯｒｋｅｒｓｒｅａｌｉｚｅａｎｉｍｐＯｎａｎｔｒｏＩｅ．Ｔｈｅｅｍｅ唱ｅｎｃｅ０ｆｓＯＲｗａｒｅｃｒｉｓｉｓｔｈｅｉｍｐｏｒｔａｎｃｅｏｆＳｏｆｈ＾，ａｒｅｑｕａｌｉｔｙ雏ｓｕｒａｎｃｅ．ＳｏＲｗａｒｅｔｅｓｔｉｎｇｉｓｔｈｅｏｎｌｙｅｆ『ｅｃｔｉＶｅｗａｙｔｏＴｅｓｔｃａＳｅｅｎｓｕｒｅｓｏｍＶａｒｅｑｕａｌｉｔｙ．ｏｎｇｅｎｅｒａｔｉｏｎｉｓｔｈｅｋｅｙｏｆｓｏｆｈＶａｒｅｔｅｓｔｉｎｇ．ＴｅｓｔｏｆｓｏＲＷａｒｅｔｅｓｔｉｎｇ．ＴｈｉｓｐａｐｅｒｃａＳｅｄｅｓｉｇｎｉｎｇｈａｓａｄｉｒｅｃｔｉｍｐａｃｔｔｈｅｄａｔａｅｆｒｅｃｔｉＶｅｎｅｓｓｄｉｓｃｕｓｓｅｓＯｎｅｓｅａｒｃｈｉｎｇａｌｇｏｒｉｔｈｍＯｆｔｅｓｔｇｅｎｅｒａｔｉｏｎｉｎｔｈｅｗｈｉｔｅｂｏｘｔｅｓｔｉｎｇ．ＴｈｉｓｍｅｔｈｏｄｗｉＩｌｉｍｐｒｏＶｅｔｈｅｅ衢ｃｉｅｎｃｙｏｆＰａｔｈｃｏＶｅｒａｇｅｉｓｏｎｅｓｏ胁ａｒｅｔｅＳｔｉｎｇ．ｏｆｔｈｅｈｉｇｈｅｓｔｃｏＶｅｒａｇｅｍｅｔｈｏｄｓｉｎｔｈｅｗｈｉｔｅｂｏｘｔｅｓｔｉｎｇ，ａｎｄｇｅｎｅｒａｌｌｙ，ｔｈｅｓｔｒｕｃｔｕｒｅｄｔｅｓｔｄａｔａｉｓｇｅｎｅｒａｔｅｄｂｙｔｈｅｗａｙｏｆｐａｔｈｃｏＶｅｒａｇｅ．Ｔｈｒｏｕｇｈｄ诩’ｅｒｅｎｔｐａｔｈ，ｉｔｇｅｎｅｒａｔｅｄｉａ’ｅｒｅｎｔ铲ｏｕｐｓｏｆｔｅＳｔｄａｔａｗｈｉｃｈｃｏｎｓｔｉｔｕｔｅｔｈｅｐｒｏ伊ａｍ’ｓｉｎｔｅｇｒａｔｅｄｔｅｓｔｃａＳｅ．ｃａｎｃ锄ｃｏＶｅｒａｇｅｄｉｆｒｅｒｅｎｔｐａｔｈ，ａｌｌｔｈｅ伊ｏｕｐｓｏｆｔｅｓｔｄａｔａＷｈ订ｅｒｅａｃｈｉｎｇｔｈｅｓｅａｒｃｈｉｎｇａｌｇｏｒｉｔｈｍｏｆｔｅＳｔｄａｔａｇｅｎｅｒａｔｉｏｎ，ｂａｓｅｄｏｎｔｈｅｏｒｉｇｉｎａｌｓｅａｒｃｈｉｎｇａｌｇｏｒｉｔｈｍｉｓｏｎｌｙｆｏｒｔｈｅｏｎｅ－ｄｉｍｅｎｓｉＯｎａｌｐｒｅｄｉｃａｔｅ，ｔｈｉｓｔｈｅｃｏｍｐｏｕｎｄｐｒｅｄｉｃａｔｅ，ａｎｄｐｕｔｓｆｏｎＶａｒｄａｐ印ｅｒａｄｄｓａｍｅｔｈｏｄｔｏｓｏｌＶｅｇｒｏｕｐｅｄｓｅａｒｃｈｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｔｈｅｐｒｏｇｍｍｗｈｉｃｈａｉｎｃｌｕｄｅｓｃｏｍｐｏｕｎｄｐｒｅｄｉｃａｔｅ．Ｄｕｒｉｎｇｔｈｅｐｒｏｃｅｓｓｏｆｓｅａｒｃｈｉｎｇｔｅｓｔｄａｔａ，ｔｈｉｓａｒｔｉｃｌｅｉｎｔｒｏｄｕｃｅｓｐｒｏ黟ａｍｓｌｉｃｉｎｇｔｅｃｈｎｏｌｏｇｙ．ＴｈｉｓｔｅｃｈｎＯｌｏｇｙａｌｓｏｃａｎｃａｎｈｅｌｐｕｓａｎａｌｙｚｅａｎｄｕｎｄｅｒｓｔａｎｄｐｒｏｇｒａｍ，ａｎｄｃｏｄｅ．Ｔｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｓｔｈｅａｂｓｔｒａｃｔｕｓｅ如ｌｐｒｏｃｅｄｕｒｅ，ｓｏｉｔｃａｎｓｉｍｐｌｉｆｙｐｒｏ黟ａｍｄｅＶｅｌｏｐｍｅｎｔｏｆｔｈｅｓｌｉｃｉｎｇｔｅｃｈｎｏｌｏｇｙ，ｔｈｅｃｌａＳｓｉｆｉｃａｔｉｏｎｏｆｓｌｉｃｉｎｇ，ｔｈｅｓｌｉｃｉｎｇｇｕ｛ｄｅｌｉｎｅｓ，ｓｌｉｃｉｎｇａｌｇｏｒｉｔｈｍ，ａｎｄｐｕｔｓｔｈｅｉｍｐｏｎａｎｃｅｏｎｔｈｅｄｙｎａｍｉｃｓｌｉｃｉｎｇａｌｇｏｒｉｔｈｍｂａＬｓｅｄａｏｎｆｏｒｎｌｅｒａｎａｌｙｓｉｓ．Ａｔｌａｓｔ，ｔｈｉｓａｎｉｃｌｅｐｕｔｓｆｏｎＶａｒｄＳｙｓｔｅｍｆｈｍｅｗｏｒｋ，ｄｅｓｃｒｉｂｅｓｔｈｉｓｓｙｓｔｅｍ’ｓｐｒｏｃｅｓｓｅｓａｎｄａｅａｃｈｍｏｄｕｌｅ’ｓｅｘｐｅｃｔｅｄｆｕｎｃｔｉｏｎｉｎｄｅｔａｉｌ，ａｎｄｇｉＶｅｓＶｅｒｉｆｉｅｄｔｈｅｆｅａｓｉｂｉｌｉｔｙｏｆｔｈｉｓｓｙＳｔｅｍｆｒａｍｅｗｏｒｋ．ｓｐｅｃｉｆｉｃａｌｇｏｒｉｔｈｍ．Ｔｈｒｏｕ曲ａｎｅｘａｍｐｌｅ，ｉｔＫｅｙｗｏｒｄｓ：ｓｏｍＶａｒｅｐｒｅｄｉｃｔ，ｂｒａｎｃｈｆｕｎｃｔｉＯｎ．ｔｅｓｔｉｎｇ，ｔｅｓｔｄａ氓ｔｅｓｔｃａＬｓｅ，ｐａｔｈｃｏｖｅｒａｇｅ，ｓｌｉｃｉｎｇｔｅｃｈｎｏｌｏｇｙ，ｃｏｍｐｏｕｎｄ１１学位论文独创性声明：本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。如不实，本人负全部责任。论文作者（签名）：（注：手写亲笔签名）釜丝量沙矿年／月ｆ名日学位论文使用授权说明河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊（光盘版）电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部分内容的公布（包括刊登）授权河海大学研究生院办理。论文作者（签名）：（注：手写亲笔签名）ｐ８年乡月ｒＺ日河海大学硕十论文第一章绪论第一章绪论人类在不断创新，社会在不断进步，科技在不断发展，２１世纪的人们越来越离不丌计算机，计算机技术已经深入到人类生活的方方面面。随着计算机技术的发展，作为计算机灵魂的软件发挥着举足轻重的作用。软件危机的出现，让更多的计算机工作者意识到软件质量保证的重要性。软件测试是保障软件质量的重要手段，也是软件工程的重要组成部分。对软件测试技术的研究与应用已成为人们日益关注的课题…－【引。软件测试的真正确立是在２０世纪７０年代，１９７２年首届软件测试正式会议上，Ｍｙｅｒｓ给出了测试的定义——“为发现程序错误而执行程序的过程＂…。８０年代，一些软件开发人员和测试人员一起制定了测试的各种标准，但由于这些标准过于庞大，在实际应用中无法全部实现，但它们确实为一些测试提供了非常宝贵的参考。直到９０年代，软件测试以及各种测试工具逐渐盛行起来。在这段时间内，测试理论以及测试用例的选择一直是研究的热点。现在，测试理论逐渐趋于完善，但是软件测试用例生成仍是软件测试领域一个较为复杂的问题，方法和手段尚未成熟。１．１课题研究的背景和意义随着软件规模的不断扩大，软件设计的复杂程度不断提高，软件开发中出现错误或缺陷的概率越来越大。同时，由于人们对于软件质量的重视程度越来越高，就导致了测试在软件开发中的地位越来越重要。软件测试是目ｆ；｛『用来验证软件是否能够完成所期望的功能的唯一有效的方法。白盒测试和黑盒测试是软件测试中的两大方法１５Ｊ，无论哪种方法都离不开测试用例的生成。测试用例设计的好坏直接影响到软件测试的成功与否，也影响了软件质量的保证。本文所讨论的测试用例生成方法是基于白盒测试的。白盒测试是针对程序内部逻辑的测试，要求对程序的结构特性做到一定的覆盖，是基于代码覆盖的一种测试。路径覆盖是白盒测试中覆盖率最高的一种覆盖方法，所以结构化测试数据一般都是通过路径覆盖的方式来生成。根据不同的路径，可以生成覆盖不同路径的测试数据，所有路径的测试数据就组成了程序完整的测试用例。２０世纪７０年代以来，有关结构测试用例自动生成的搜索寻优算法这一领域的研究就己展开。人们分别采用随机化、爬山法、遗传算法等方法实现测试数据生成【６１。爬山法，也就是函数最小化方法，是一种传统的搜索算法，善于找到局部最优解。它使用迭代改进法，每次迭代从现时点的邻域选择一个新的点进行搜索。但由于在方向探测时，每次只针对一个变量，因此仅能解决一维谓词的情况。在路径谓词多样性的情况下，很难达到较高的搜索成功率。河海火学硕：Ｅ论文第～章绪论遗传算法作为一种基于自然选择原理和自然遗传机制的通用搜索算法，模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化【７】。与其它算法的不同之处在于整个搜索空间随机采样，按一定的评估策略对每一样本评价，并采用特定的算子进行样本优化，直至产生最优解。从理论上来看，遗传算法在解决大空间、多峰、非线性、全局优化等高复杂度问题时可以显示独特的优势和高效性，但其面临一系列的实现问题，使得人们对遗传算法的实际应用效果并不乐观。本文将改进爬山算法只针对一维谓词的情况，分析了复合谓词这一情况，提出一种难度适中、效率较高的分组搜索算法１６Ｊ。对于复合谓词中出现的多个变量，分析其内在联系，并将其分组搜索，这样可以减少搜索的次数，提高搜索效率。本文在运用分组搜索算法的同时，引入了程序切片技术。程序切片技术是一种软件调试、测试、理解和维护的技术，通过寻找程序内部的相关性来分解程序，从而达到快速错误定位的目的１８Ｊ。在软件测试中，测试数据生成是至关重要的一步。将程序切片技术应用到软件测试数据生成中，重点关注程序中与指定路径上兴趣点相关的那部分语句，可以有效地提高基于路径的测试数据生成效率。１．２国内外的研究现状及发展动态本文讨论的测试用例生成是基于白盒测试而言，白盒测试是针对程序内部逻辑的测试。在多种逻辑覆盖方法中，本文选择覆盖率最高的路径覆盖方法，一方面是由于路径覆盖方法具有较好的覆盖性，在动态生成测试用例时，可以保证获得程序完整的执行路径；另一方面，本文是根据程序路径生成对应的测试用例，所以首先需要获得程序的执行路径，使用路径覆盖方法可以获得程序所有的有效执行路径。本文基于路径覆盖方法，并结合测试用例生成的搜索算法，研究了基于路径覆盖的测试用例生成的搜索算法。１．２．１测试用例生成方法黑盒测试和白盒测试是两类广泛使用的软件测试方法，任何一种方法都离不开测试用例的生成。所谓测试用例（ＴｅｓｔＣａｓｅ），是指在测试中，为某个特殊目标而编写的一组测试数据、执行步骤以及预期结果，以便测试某个程序路径或核实是否满足某个特定需求。本文中提到的测试用例并不是完整的测试用例，其实只是测试数据部分。白盒测试中测试数据的生成主要是基于路径的，主要有以下几种方法１９Ｊ：１．随机法：基本思想是对输入数据空间进行随机取样。这种方法实现起来容易，但是要生成基于给定路径的测试数据，就需要按照产生大量的测试数据运行被测程序，测试数据的效率非常低下。２．静态方法：基本思想是将路径上的所有语句采用符号执行方法转化成约束河海人学硕十论文第一章绪论系统，然后求解。基于符号执行方法来生成测试数据，克服了浮动测试中难以选取恰当的测试数据这一难点，但是，一旦程序中存在循环、过程调用、动态数组和指针处理时，符号执行实现起来就比较困难ｌ１０１‘【１２１。３．动态方法：动态测试数据生成是目前应用最为广泛的一种测试数据生成方法。所谓动态，是指从输入空问随机选取一组数据作为初始输入，基于程序实际运行，不断调整输入，使得程序实际执行路径沿着指定路径不断逼近，直到与指定路径完全一致。在这种方法中，一般采用分析待测程序中的谓词，将其转化成分支函数，应用分支函数极小化的方法进行处理。其中最具代表的Ｋｏｒｅｌ【１３】－【１４】提出的方法，他采用的是任选一组输入数据，按步迸的方式运行程序，即一次前进一个分支谓词。若当前分支谓词的值不符合要求，就建立一个分支函数ｆ。然后用函数极小化方法调整输入变量值。根据分支函数的定义，ｆ值为负数（或０）就意味着当前分支谓词被满足。然后重复执行，逐步前进直到通过整条路径。由于采用步进方式，所以这种方法可以尽早发现不可行路径。不过这种方法一次只考虑一个分支函数和一个输入变量，因此需要进行大量的迭代，在时间上的代价会很大。程序插装是另一种主要的动态法，该方法通过插装程序强制程序以任意一组数据为输入来执行指定的路径，并用插装语句向测试数据生成器返回各变量和分支谓词的状态。对程序中的每个判断语句进行插装，使插装语句恰好插在判断语句之前。这种方法能生成整型、实型、离散类型的测试数据，并支持子程序和异常处理，能够用于黑盒测试。但是为了尽早发现不可行路径，该方法一次也只考虑一个分支谓词和一个输入变量，并且使用回溯技术，所以会造成大量的资源浪费。另外，当初始程序输入距离问题解太远时，即使对于线性路径约束，该方法也有可能无法找到解。４．试探方法：主要包括遗传算法和模拟退火算法【１５１－【１７】。试探法的基本思想是从数据空间中选择输入数据，运行程序，根据运行结果，结合概率论的思想产生新的数据继续试探。其优点是不受搜索空问性条件的约束，对于一些传统方法难以处理的大空间、多峰、非线性、全局优化等复杂度较高的问题，该方法具有独特的优势和高效性。但是，这种方法对于线性路径约束是不完备的，不能保证总能找到解。本文所述的搜索算法就是在动态方法基础上，增加了对复合谓词的处理情况，并引入了路径覆盖和程序切片技术进行改进的一种测试数据生成方法。下面介绍一下路径覆盖方法和程序切片技术。１．２．２路径覆盖方法本文提出的是基于路径覆盖的测试用例生成的搜索算法，路径覆盖是白盒测河海人学硕－｝：论文第一章绪论试中普遍应用的覆盖方法。除此之外，国内外很多学者提出了其它的覆盖方法，比如函数覆盖、指令块覆盖、ＤＤＲ覆盖、ＭＣ／ＤＣ覆盖、ＬＣＳＡＪ覆盖、ＰＰＰ覆盖等。比较各种覆盖方法的可自动化性、可维护性和完整性，如表卜ｌ所示，可以看出，在所有的覆盖方法中，路径覆盖的完整性足最好的。表卜１各种覆盖方法的比较【１８】覆盖方法语句覆盖判定覆盖条件覆盖判定条件覆盖路径覆盖ＩＢ覆盖ＤＤＲ覆盖ＭＣ／ＤＣ覆盖ＥＳＴＣＡ覆盖ＬＣＳＡＪ覆盖接口覆盖ＰＰＰ覆盖Ｚ路径覆盖自动化性好好较好较好差好好较好较差较好差较好较差维护性好好好好较差好好好较好较差好较好较差完整性差较差一般较好好差较差较好一般较好一般较差较好路径覆盖的方法就是指设计足够的测试用例，使得运行这些测试用例时，被测程序的每一条语句至少执行一次，这是最强的覆盖准则。但是当程序比较复杂，路径数目很大时，要手动地找到所有路径是非常困难的。为此，可以通过一定的算法寻找出所有的路径。如果程序中出现多个判定和多个循环，路径数目将会急剧增长，为了解决这个问题，有学者引入了Ｚ路径覆盖【ｌ９。。Ｚ路径覆盖舍掉了路径覆盖的一些次要因素，对循环机制进行简化，极大地减少了路径的数量。循环的简化是指循环的次数，无论循环的形式及实际执行循环体次数多少，只考虑一次和零次两种情况【ｌ引。通过路径覆盖方法得到程序的所有路径后，可以选定其中一条路径，运用搜索算法寻找符合该路径的测试数据。在搜索过程中，为了简化程序代码，提高执行速度，又引入了程序切片技术。１．２．３程序切片技术的起源与发展现状程序切片技术是本文引入的一种重要的技术，它是一种分析和理解程序的技术，通过对源程序中各个兴趣点计算其程序切片以便分析和理解程序。程序切片实际上是对程序进行分割和简化，依据程序切片准则，从被测程序中抽取出与兴趣点相关的那部分语句，忽略那些与兴趣点无关的语句。４河海大学硕卜论文第一章绪论程序切片的基本思想是由ＭａｒｋＷｅｉｓｅｒｌ２０Ｊ于１９７９年在他的博士论文中首先提出的，１９８１年他又在国际软件工程大会上报告了这一新发现，立即引起了当时计算机界不小的震动。当时ｗｅｉｓｅｒ等人正在进行自动程序抽象的理论和实践研究，他们通过对源程序代码的分析以及对控制流图（ＣＦＧ）的研究发现：程序的某一个输出只与源程序中部分语句和控制谓词有关，删除其他的语句和谓词并不影响该输出的结果。１９８４年，Ｗｅｉｓｅｒ博士进一步形式地阐述了程序切片技术的基本思想，以及如何基于数据流方程计算程序切片的方法。此后，在他的基础上又有许多人提出了不同的程序切片的定义和用于切片的算法。１９８４年到１９８７年之间，Ｏｔｔｅｎｓｔｅｉｎｓ【２１Ｊ等人引入了基于程序依赖图（ＰＤＧ）的图形可达性算法，利用这种算法可以计算程序过程内后向切片。随后，Ｈｏｒｗｉｔｚ，Ｔ．Ｒｅｐｓ和Ｄ．Ｂｉｎｋｌｅｙ等人分别引入了基于系统依赖图（ＳＤＧ）的前向切片概念及算法，以及过程问切片的概念和两阶段图形可达性算法。Ｋｏｒｅｌ【１５】【１６】【２２Ｊ和Ｌａｓｋｉ等人还引入了动态切片的概念和算法。从１９９４年开始，随着面向对象编程语言及设计方法的推广，针对面向对象的程序切片技术的研究也随之兴起。Ｃａｎｆｏｒａ，Ｃｉｍｉｔｉｌｅ和Ｌｕｃｉａ在１９９８年提出在程序理解上采用条件切片技术，这种技术是通过增加一个条件扩展了传统的静态切片准则，实际上是一种附加了一定条件的动态切片。如今，程序切片技术经历了２０多年的漫长发展，在理论和应用两个方面都取得了丰硕的成果，这些研究成果在计算机学科的很多方面发挥了重要的作用。总的来说，程序切片技术的发展经历了从静态到动态，从前向到后向，从单一过程到多个过程，从面向过程的程序到面向对象的程序，从非分布式到分布式的程序的发展过程１２３Ｊ【２４１。本文运用的动态切片技术是由Ｋｏｒｅｌ等人提出，主要思想是依据动态的数据流和控制流信息计算切片，每一次的计算工作量较小，这种技术更多地提供了程序的动态信息，多用于程序调试、测试方面。１．３本文的主要工作本文在测试用例生成的方法上，主要研究基于路径覆盖的测试用例生成的算法，后面章节中将分别介绍以下四个方面的内容：（１）分析源程序，根据程序流程图生成测试路径。（２）改进以往算法只针对一维谓词的情况，研究了基于复合谓词的分组搜索算法，并采用动态调整步长的计算方法。（３）在数据调整过程中，引入程序切片技术，在切片生成算法中引入控制依赖关系。（４）设计了由程序预处理模块、路径生成器、谓词分析器、数据调整模块组河海大学硕上论文第一章绪论成的测试用例生成框架。１．４本文的组织结构本文的组织结构如下：第一章绪论主要介绍了本课题的研究背景及发展现状；第二章测试用例生成的搜索算法研究首先介绍了测试路径生成的过程和算法，然后介绍了基于复合谓词的软件测试用例生成的分组搜索算法，并用几个实例讲解了搜索算法的实现步骤。第三章程序切片技术与动态切片算法介绍了程序切片技术，包括程序切片技术的发展、程序切片的分类、程序切片的准则，以及计算程序切片的算法。第四章设计与实现给出了整个系统实现的框架，包括对各个模块实现的具体步骤和算法，并对具体的实例运用该系统的思想进行测试用例的生成。第五章总结与展望对本文进行总结，说明了本文存在的不足以及今后继续改进的方法。１．５本章小结软件测试是保证软件质量的有效途径，测试用例的生成是软件测试的核心和关键。本章简单介绍了本课题的研究背景和国内外的发展现状，比较了测试数据生成的几种方法，有随机法、静态法、动态法和试探法，本文在动态方法的基础上提出了基于路径覆盖的分组搜索算法。为了提高测试用例生成的效率，本文还引入了动态切片的思想。６河海人学顾｝论文第二章测试用例生成的搜索算法研究第二章测试用例生成的搜索算法研究白盒测试是一种常用的测试方法，基于代码进行测试，但并不是简单测试程序代码。一般需要根据不同的测试要求，结合不同的测试对象，使用适合的方法进行测试。测试用例的生成是软件测试的第一步，必须根据测试用例执行软件测试。第一章中已经介绍过有关测试用例生成的方法，本章主要研究测试用例生成的搜索算法。所谓搜索算法，就是在寻找测试用例的过程中，给定测试变量的初始值，按照一定的路径和分支函数的要求调整测试数据，直到搜索到合适的测试数据为止。搜索过程是基于给定执行路径的基础上，所有测试路径的生成又是测试用例生成的第一步。本章首先介绍测试路径的生成，然后介绍根据测试路径实现测试用例生成的搜索算法。２．１测试路径的生成测试路径的生成是测试用例生成的前提，对于同一个程序而言，根据不同的逻辑覆盖方法可以获得不同的程序路径。通过覆盖方法的介绍，可以知道路径覆盖是覆盖性最强的覆盖方法。在执行程序时，当程序有多条执行路径时，程序总会按照不同的输入数据，选择不同的执行路径。程序之所以会选择不同的路径，是因为在执行过程中，经常会遇到控制语句，根据控制语句中的分支谓词，可以确定在某个特定输入下程序的执行路径。所以，可以通过分析程序的结构，按照控制语句中的分支谓词来确定程序的不同执行路径。２．１．１路径覆盖方法白盒测试中常用的六种逻辑覆盖方法主要有语句覆盖、判定覆盖、条件覆盖、判定条件覆盖、条件组合覆盖、路径覆盖。语句覆盖是最弱的覆盖测试，一般不能满足测试要求。下面通过实例，介绍一下根据不同的覆盖方法设计出不同的测试用例。为了下文的举例描述方便，以一段简单程序为例：ｉｎｔｘ，ｙ，Ｔ：０ＡＢｉｆ（ｘ＞＝８０＆＆ｙ＞＝８０）Ｔ＝ｌ：Ｅｌｓｅｉｆ（ｘ＋ｙ＞＝１４０＆＆（ｘ＞＝９０ｌＩｙ＞＝９０））Ｔ＝２：Ｃ河海大学硕上论文第二章测试用例生成的搜索算法研究首先给出以上程序的流程图。可以将该程序看作是评定奖学金的算法，即两门课程均为８０分以上，可以获得一等奖学金；如果两门课程总分１４０分以上，其中一门９０分以上，可以获得二等奖学金；否则都以三等奖学会计算。图２—１程序流程图１．语句覆盖语句覆盖是最简单的结构覆盖要求，语句覆盖要求设计足够多的测试用例，使得程序中每条语句至少被执行一次。测试用例设计：Ｘｌ２３９０５０９０Ｙ９０５０７０路径ＯＡＥ０ＢＤＥＯＢＣＥ２．判定覆盖判定覆盖要求设计足够多的测试用例，使得程序中每个判定至少有一次为真值，有一次假值，即程序中的每个分支至少执行一次。８河海大学硕士论文第，二章测试用例生成的搜索算法研究测试用例设计：Ｘｌ２３９０５０９０Ｙ９０５０７０路径０ＡＥＯＢＤＥＯＢＣＥ３．条件覆盖条件覆盖要求判定中的每个条件获得各种可能的结果，即每个条件至少有一次真值，有一次假值。测试用例设计：Ｘｌ２９０４０Ｙ９０５０路径ＯＡＥＯＢＤＥ４．判定／条件覆盖该方法使得判定中每个条件的所有结果至少出现一次，每个判定本身所有可能结果也至少出现一次。测试用例设计如下：Ｘ１２３４９０５０９０７０Ｙ９０５０７０９０路径０ＡＥ０ＢＤＥ０ＢＣＥ０ＢＣＥ判定／条件覆盖满足判定条件覆盖准则和条件覆盖准则，弥补了二者的不足。５．组合覆盖组合覆盖要求设计足够多的测试用例，使得每个判定中条件结果的所有可能组合至少出现一次。测试用例设计：Ｘｌ２３４５６７９０９０９０７０３０７０５０Ｙ９０７０３０９０９０７０５０路径０ＡＥＯＢＣＥＯＢＤＥＯＢＣＥＯＢＤＥＯＢＤＥ０ＢＤＥ９河海人学硕十论文第二章测试用例生成的搜索算法研究组合覆盖准则满足判定覆盖、条件覆盖和判定／条件覆盖准则，但另一方面也增加了测试用例的数量。６．路径覆盖路径覆盖是指没计足够的测试用例，覆盖程序中所有可能的路径。测试用例设计：Ｘ１２３４９０５０９０７０Ｙ９０５０７０９０路径ＯＡＥ０ＢＤＥ０ＢＣＥ０ＢＣＥ在这个例子中，路径覆盖方法设计的测试用例和判定／条件覆盖方法设计的测试用例相同，但是判定／条件覆盖方法和路径覆盖方法未考虑条件的组合情况，测试用例可能不够全面，而组合覆盖虽然考虑了足够多的测试用例，但对测试用例的寻找比较复杂。事实上，并不存在一种十全十美的测试方法能够发现所有的软件故障，但相对来说，路径覆盖可以对程序进行比较全面的测试，无论从覆盖性上来说，还是从测试用例生成的简易程度上来说，路径覆盖都是一个比较合理的选择。所以，本文选择路径覆盖的方法生成测试用例。２．１．２测试路径生成的方法对于通过路径覆盖来生成测试用例的方法而言，测试路径的生成是本文探讨的第一个内容。首先对程序代码进行分析，生成对应的执行路径。然后根据不同的路径，生成覆盖不同路径的测试数据，所有路径的测试数据就组成了程序完整的测试用例。白盒测试一般从最基本的单元测试开始，所以本文探讨的问题也是基于最简单最基本的单元模块进行的测试。在传统的结构化编程语言中，要进行测试的单元一般是函数或子过程，而在类似Ｃ＋＋这样的面向对象的语言中，要进行测试的基本单元是类或是类的方法。本文暂且不考虑类与类之间的继承和调用关系，只考虑简单的程序结构，一般可以分为顺序结构、循环结构和分支结构。其中，顺序结构是最简单的一种结构，无需任何处理；分支结构也很好处理，只要将不同的分支视为不同的路径即可。最复杂的当属循环结构，如果程序中出现上百次的循环次数，那么程序的复杂性不可估量。为此，本文采用一种Ｚ路径覆盖的方法１２５Ｊ【２６１，实际是指对循环机制进行简化，了循环的次数。无论循环的形式和实际执行循环体的次数，只考虑循环体执行一次和零次两种情况。循ｌＯ河海大学硕士论文第二章测试用例生成的搜索算法研究环体不执行的情况实际上就是不满足循环条件，这样可以将循环结构转化为分支结构。通过对循环结构的化简，程序中只存在顺序和分支两种结构。由图２—２所示。图２．２程序结构图图中将程序语句分为基本语句块、分支语句块和控制语句。通过控制语句，可以按照不同的分支生成不同的路径，ｎ个分支对应于ｎ条路径。如果分支语句块中含有控制语句，需要将分支语句块逐级展开。如果程序中含有多条控制语句，那么程序的所有路径就是各级控制语句下分支语句块的笛卡尔积。例如图４—１河海大学硕十论文第二章测试用例生成的搜索算法研究中，分支语句块的笛卡尔乘积表示为（分支语句块１ｌ，分支语句块１２）×（分支语句块２１，分支语句块２２），由此可以得到四条程序路径：路径１：基本语句块１，控制语句１，分支语句块１ｌ，基本语句块２，控制语句２，分支语句块２１，基本语句块３；路径２：基本语句块ｌ，控制语句ｌ，分支语句块１１，基本语句块２，控制语句２，分支语句块２２，基本语句块３；路径３：基本语句块１，控制语句１，分支语句块１２，基本语句块２，控制语句２，分支语句块２１，基本语句块３；路径４：基本语句块ｌ，控制语句ｌ，分支语句块１２，基本语句块２，控制语句２，分支语句块２２，基本语句块３；如果分支语句块中嵌套控制语句，那么就需要对分支语句块进行路径展丌，进行递归处理。如图２—２中分支语句块２１中含有控制语句，因此要对上述含有分支语句块２１的路径进行拓展。由于分支语句块２ｌ中含有控制语句３和分支语句块３１及分支语句块３２，所以可以用（控制语句３，分支语句块３１）和（控制语句３，分支语句块３２）替代分支语句块２１。即上述路径１和路径３分别扩展为：路径卜ｌ：基本语句块ｌ，控制语句ｌ，分支语句块１１，基本语句块２，控制语句２，控制语句３，分支语句块３１，基本语句块３；路径卜２：基本语句块ｌ，控制语句１，分支语句块１１，基本语句块２，控制语句２，控制语句３，分支语句块３２，基本语句块３；路径３—１：基本语句块１，控制语句１，分支语句块１２，基本语句块２，控制语句２，控制语句３，分支语句块３１，基本语句块３；路径３—２：基本语句块１，控制语句１，分支语句块１２，基本语句块２，控制语句２，控制语句３，分支语句块３２，基本语句块３；加上原有的路径２和路径４，由原来的四条路径扩展为六条路径。按照这样的思路，可以获得程序的所有路径。２．１．３测试路径生成的算法根据上一节内容的介绍，可以设计一种测试路径生成的算法，从而自动获得程序的所有路径。在实际生成测试路径的时候，需要对程序语句标号，这样程序路径就可以用一组语句标号来表示。这项工作应该放在程序预处理器中实现，将在第五章中有所介绍。测试路径生成的算法思想【９】如下：将程序语句分为基本语句块、分支语句块和控制语句，根据程序结构图获得程序的基本路径。如果分支语句块中含有控制语句，需要将分支语句块逐级展开。通过控制语句，可以按照不同的分支生成不１２河海大学硕士论文第二章测试用例生成的搜索算法研究同的路径，即ｎ个分支对应于ｎ条路径。如果程序中含有多条控制语句，那么程序的所有路径就是各级控制语句下分支语句块的笛卡尔积。算法描述如下：ｐａｔｈＡｎａｌｙｓｅ（ＢａｓｅＰａｔｈ［］，ＰＢ［］）｛Ｆｏｒ（ＥａｃｈＢａｓｅＰａｔｈ）｛Ｆｌａｇ＝０：Ｆｏｒ／／对每条路径进行分解／／设置每条路径中控制语句的数量ＰＢｉｉｎ（ＥａｃｈＢａｓｅＰａｔｈ）／／对每条路径中每个分支语句块进行分析｛Ｉｆ（ＰＢｉｉｎｃｌｕｄｅｓｃｏｎｔｒｏｌｓｅｎｔｅｎｓｅ）／／判断分支语句块中是否含控制语句，／／如果含有控制语句，需进一步分解｛№ｗＰＢ口＝ｇｅｔＮｅｗＰＢｉ：Ｆｌａｇ＋＋：／／获取新的分支语句块））Ｉｆ（Ｆｌａｇ＞＝１）／／当路径上的分支语句块中含有一个以上的控制语句时，／／说明路径可进一步分解，通过笛卡尔积计算出所有路径｛ＢｒａｎｃｈＢｌｏｃｋ［］［］＝ｇｅｔＡｌｌＢｒａｎｃｈＢｌｏｃｋ（ＮｅｗＰＢ［］）：／／获取所有的分支语句块Ｄｉｃａｒ［］＝ｇｅｔＤｉｃａｒ（ＢｒａｎｃｈＢｌｏｃｋ［］［］）：／／求出分支语句块的笛卡尔积ＢａｓｅＰａｔｈ［］＝ｇｅｔＮｅｗＰａｔｈ（Ｄｉｃａｒ［］）：／／根据笛卡尔积求出新的所有基本路径ＣＢ［］＝ｇｅｔＥｖｅｒｙｐａｔｈＢｒａｎｃｈＢｌｏｃｋ（）：／／获取每条新路径对应的分支语句块ＢａｓｅＰａｔｈ［］＝ｐａｔｈＡｎａｌｙｓｅ（ＢａｓｅＰａｔｈ［］，ＰＢ［］）：／／采用递归方式对新路径扩展）ＲｅｔｕｒｎＢａｓｅＰａｔｈ口：／／返同程序的基本路径１３河海大学硕士论文第二章测试用例生成的搜索算法研究｝ｇｅｔＡｌｌＰａｔｈ（ｐｒｏｇｒａｍ）｛Ｌｏａｄｆｉｌｅ（ｐｒｏｇｒａｍ）：ＢａｓｅＰａｔｈ＝ＣｒｅａｔＢａｓｅＰａｔｈ（ｐｒｏｇｒａｍ）：／／根据程序结构生成一条原始的基本路径ＰＢ＝ｇｅｔＣｏｎｔｒｏｌＢｌｏｃｋ（ｐｒｏｇｒａｍ）：／／获得程序的分支语句块／／装载需要分析的程序ＢａｓｅＰａｔｈ［］＝ｐａｔｈＡｎａｌｙｓｅ（ＢａｓｅＰａｔｈ，ＰＢ）：２．２基于复合谓词的分组搜索算法２０世纪７０年代以来，有关结构测试用例自动生成的搜索寻优算法这一领域的研究就已展开。人们分别采用随机法、爬山法、遗传算法等方法实现测试数据生成。本文讨论的通过路径覆盖实现测试用例生成的搜索算法的思想是：根据路径覆盖的原则生成所有的测试路径，然后根据每条测试路径分别生成对应的测试数据，测试数据生成的过程是一个逐步搜索的过程。原有的爬山法利用函数最小化的方法，每次只针对一个变量进行搜索，善于找到局部最优解，但是搜索效率比较低。随着程序复杂性的不断提高，简单的一维谓词很难满足程序的需要，路径谓词越来越复杂多样，所以相应的搜索算法也需要不断改进。如果仍采用以前算法的思想，即对多个变量逐一搜索，这样将不能很好地处理复合谓词的情况，搜索效率也会大大降低。对于一个普通的程序，假设有Ｎ个输入变量，搜索方向分为正向和负向，如果采用逐一搜索的方法，最糟糕的情况下就需要进行２Ｎ次方向搜索。这样的方法最终当然也可以找到所需的数据，但是搜索效率非常低。那么如何提高搜索效率，能否对多个变量同时搜索就成了本文所需要探讨的问题之一。本节将原来基于简单谓词的分支函数定义扩展到基于复合谓词的分支函数定义，通过扩展的分支函数极小化方法实现测试数据的搜索算法。２．２．１分支函数的定义及扩展定义所谓简单谓词是指谓词中仅含单个关系运算符（＜，≤，＞，≥，＝，≠之一）的谓词，而复合谓词是指两个或两个以上的简单谓词由布尔连接词（ＡＮＤ或ＯＲ）连接而成的谓词。分支函数的定义１２７Ｊ：假设谓词ｐｒ是简单关系表达式：Ｅ，ｏｐＥ：，其中Ｅ。，１４河海大学硕十论文第二章测试用例生成的搜索算法研究Ｅ：为算术表达式，关系运算符ｏｐ∈｛＜，≤，＞，≥，＝，≠）。表达式Ｅ．ｏｐ可等价表示为Ｆ（１）（２）ｒｅｌＥ：０，其中运算符ｒｅｌ∈｛＜，≤，＝），并且满足：当谓词ｐｒ为假时，Ｆ为正（或为零，若ｒｅｌ为＜）；当谓词ｐｒ为真时，Ｆ为负（或为零，若ｒｅｌ为＝，≤）；则Ｆ是输入变量的一个实值函数，称为分支函数。分支函数Ｆ，谓词ｐｒ和运算符ｒｅｌ的对应关系如下表所示：表２—１分支函数Ｆ，谓词ｐｒ和运算符ｒｅｌ的对应关系谓词ｐｒＥｌ＞Ｅ２分支函数ＦＥ２一Ｅ１Ｅ２一ＥｌＥＩ—Ｅ２Ｅｌ—Ｅ２运算符ｒｅｌ＜Ｅｌ≥Ｅ２Ｅｌ＜Ｅ２≤＜Ｅ１≤Ｅ２ＥＩ＝Ｅ２Ｅｌ≠Ｅ２≤ａｂｓ（Ｅ，一Ｅ：）一ａｂｓ（Ｅ。一Ｅ２）＜分支函数的扩展定义：假设谓词ｐｒ是复合谓词，即ｐｒ中含有布尔连接词ＡＮＤ或（矛口）ＯＲ，复合谓词ｐｒ表示成：ｐｒ。ｂｏｐｐｒ：ｂｏｐｐｒ。…ｐｒ。，其中ｐｒ。、ｐｒ。、ｐｒ３…ｐｒ。为简单谓词，ｂｏｐ为布尔连接词，ｂｏｐ∈｛ＡＮＤ，ＯＲ｝。ｐｒ。、ｐｒ。、ｐｒ。…ｐｒ。可以根据上述的分支函数的定义来得到对应的分支函数ｆ。、ｆ２、ｆ。…ｆ。。那么，谓词ｐｒ中如果存在ＡＮＤ或ＯＲ连接词的问题就可以转化成如下的几种情况了：（１）如果只存在ＡＮＤ连接词，那么复合谓词ｐｒ对应的分支函数Ｆ＝ｍａｘ（ｆ。，ｆ２，ｆ。…ｆ。）；（ｍａｘ表示求最大值的函数）（２）如果只存在ＯＲ连接词，那么复合谓词ｐｒ对应的分支函数Ｆ＝ｍｉｎ（ｆ。，ｆ。，ｆ。…ｆ。）；（ｍｉｎ表示求最小值的函数）（３）如果ＡＮＤ和０Ｒ都存在，那么复合谓词ｐｒ就需要转换成相应的由ｍａｘ和ｍｉｎ函数组成的分支函数。例如复合谓词ｐｒ由各分支函数表示为（（ｆ，ＡＮＤ（ｆ。ｆ：）ＯＲｆ。），那么对应的分支函数Ｆ＝ｍｉｎ（ｍａｘｆ：），ｆ。）。注：为了更好的区分复合谓词对应的分支函数和复合谓词中包含的分支函数，暂且称复合谓词中包含的各个简单谓词对应的分支函数为子分支函数。如上述的ｆＩ，ｆ２，ｆ３…ｆ。。２．２．２扩展分支函数极小化方法分支函数是谓词的函数表现形式，可以通过分支函数的值来确定谓词的布尔河海人学硕上论文第二章测试用例生成的搜索算法研究性质。由上节中分支函数的定义可知，当谓词为假时，分支函数的值为正；当谓词为真时，分支函数的值为负。在执行某条选定的路径时，一旦出现与选定路径不一致的兴趣点，就应该判定该兴趣点处谓词的布尔性质。如果需要满足该处谓词，则使用分支函数极小化方法，通过使分支函数的值逐步减小直到为负数的方法来满足谓词为真的条件。从而根据分支函数值减小的方向调整函数中变量的值。反之，则向分支函数值增大的方向调整变量的值。所谓扩展的分支函数极小化方法就足针对复合谓词而言，通过扩展的分支函数定义来得到分支函数，并确定分支函数的值，同样如果要满足复合谓词为真的条件时，要使分支函数的值逐步减小直到为负数。当然复合谓词中含有多个子分支函数，这比简单谓词复杂很多。下一节，将介绍基于复合谓词的分组搜索算法，重点介绍如何根据复合谓词对应的分支函数调整测试数据的方法。２．２．３分组搜索算法对于每个复合谓词而言，通常会含有多个变量，假设有Ｎ个变量，那么如果逐一搜索变量，最糟糕的情况就需要进行２Ｎ次方向探索。如果同时对多个变量进行探测性搜索，那么在一定程度上势必会提高搜索效率。例如有这样一个问题：需要在坐标系的第一象限内寻找一个点，使得该点到原点的距离等于５。根据上述要求，可以列出对应的不等式条件：（ｘ＞Ｏ）＆＆（ｙ＞Ｏ）＆＆（ｘ２＋ｙ２＝２５）。根据分支函数的定义，可以得到以下几个分支函数：Ｆ。＝Ｏ—ｘ，Ｆ：＝０一ｙ，Ｆ。＝ａｂｓ（ｘ２＋ｙ２—２５）。从直观上可以看出，Ｆ。函数和Ｆ。函数其实是一样的，只是变量不同而已，如果选定同样的初始值的话，ｘ、ｙ这两个变量的探索方向应该是一致的。这样的话，不需要对每个变量都进行一次正向探索和一次负向探索，只需要同时进行一次正向探索和一次负向探索。从上例中可以看到，如果可以把多个变量划分成若干个组群，那样可以大大地减少方向探索的次数。前面提到的遗传算法考虑了待测程序的所有输入变量，这样既增加了耗费，又使得有些搜索操作可能是无效的。事实证明，只有一部分输入变量对某个特定谓词的分支函数值有影响，文中暂且将这样的变量称为影响变量。通过分析，选取有价值的变量作为输入变量，这样不但可以减少搜索的复杂度，而且可以提高搜索的正确率。例如有这样一段简单的代码：ｉｎｔａ，ｂ，ｃ，ｍａｘ：ｓｃａｎｆ（“％ｄ％ｄ％ｄ’’，＆ａ，＆ｂ，Ｉｆ＆ｃ）：（ａ＞＝ｂ）ｍａＸ＝ａ：Ｆ１ｓｅ１６河海人学硕士论文第二章测试用例生成的搜索算法研究ｍａｘ＝ｂ：Ｉｆ（ｍａｘ＜＝ｃ）ｍａＸ＝Ｃ：ｐｒｉｎｔｆ（“三个数最大值为％ｄ”，ｍａｘ）；对于这段代码，有三个输入变量ａ、ｂ、ｃ，但是对于第一个谓词（ａ＞＝ｂ）而言，真正有影响的变量只有ａ和ｂ两个；而对于第二个谓词（ｍａｘ＜＝ｃ）而言，真正有影响的变量是ｃ。所以对于特定谓词的分支函数而言，只需要考虑对其有影响的输入变量即可。以上两个例子只是简单地阐述了论文所描述的问题，事实上，在实际运行的程序中并非如此简单，可能会碰到一些更复杂的复合谓词。所以需要给出一定的规则和方法来确定变量组合的划分以及确定影响变量。对于一个测试用例的搜索算法来说，首先需要一个初始测试数据，只有根据这个初始测试数据才能做出是否需要调整以及进行正向或负向搜索的判断。以往的爬山算法和遗传算法都是在定义域内随机选择测试用例，这样显然十分盲目。本文认为，可以通过分解谓词得到的子分支函数来得到部分变量的临界值，通过这个临界值搜索测试数据就显得容易许多。但也不是所有的变量都能通过分支函数计算出初始数值的，在这种条件下，可以采取随机选择的方式。其次，需要解决变量组合的划分以及确定影响变量的问题。由前面分析可以知道，不同的谓词对应的影响变量也不同，所以文中所说的变量组合也是针对一个谓词中出现的不同变量进行组合，而并不是程序中出现的所有变量。根据简单谓词的分支函数定义，对于复合谓词中出现的简单谓词，可以用表达式Ｅ，ｏｐＥ：来表示，ｏｐ∈｛＜，≤，＞，≥），那么对应的分支函数可以表示为Ｆ＝Ｅ：一Ｅ。或Ｆ＝Ｅ。一Ｅ：，如果该分支函数中仅含一个输入变量，可以用Ｆ＝ａｘ＋ｍ表示，（其中ａ为变量ｘ前的系数，ｍ为常数，ａ、ｍ为实数，ａ≠Ｏ），根据ａ为正数或负数，可以将变量分为两个组。如果该分支函数中含有多个输入变量，可以用Ｆ＝ａｘ＋ｂｙ＋…＋ｍ表示，（其中ａ、ｂ为变量ｘ、ｙ前的系数，ｍ为常数，可以含有多个变量，用…表示省略，ａ、ｂ、ｍ为实数，ａ≠Ｏ，ｂ≠Ｏ），如果该分支函数中出现的变量没有单独出现过，也可以根据ａ、ｂ的正负性来为变量分组，否则的话，根据仅含一个输入变量的情况分组，同时考虑变量前系数的正负性是否与前者一致，如果不一致应该单独考虑，如果一致可以根据前面的搜索方向进行进一步搜索。如果各分支函数中出现非线性函数，那么其中的变量可以单独考虑。例如有这样一个复合谓词（ｘ＞２）＆＆（ｙ＞５）＆＆（ｚ＜３）＆＆（ｘ—ｚ＞５），根据分支函数的定义，可以得到以下几个子分支函数：Ｆ。＝２一ｘ，Ｆ：＝５一ｙ，Ｆ。＝ｚ一３，Ｆ。＝５一ｘ＋ｚ，经过变形可以得到如下形式：Ｆ。＝一ｘ＋２，Ｆ：＝一ｙ＋５，Ｆ。＝ｚ一３，Ｆ４＝一ｘ１７河海人学硕上论文第’二章测试用例生成的搜索算法研究＋ｚ＋５。根据上面的规则，变量ｘ、ｙ前面的系数都为负数，而变量ｚ前面的系数为正，所以可以将ｘ、ｙ分为一组，ｚ为另一组。对于分支函数Ｒ中出现的变量ｘ、ｚ，由于前面已经出现过，且Ｊ下负性与前者一致，所以根据前者来分组。如果复合谓词为（ｘ＞２）＆＆（ｙ＞５）＆＆（ｚ＜３）＆＆（ｘ＋ｚ＞５），分支函数经过变形表示为Ｆ，＝一ｘ＋２，Ｆ：＝一ｙ＋５，Ｆ。＝ｚ一３，Ｆ。＝一ｘ—ｚ＋５。其中Ｒ中变量ｚ前的系数与Ｆ。中变量ｚ前的系数不一致，此时应该对ｚ单独考虑。否则的话，在搜索过程中，如果对ｘ、ｚ取相同的步长进行探索，｛ｘ＝２，ｚ＝３｝，｛ｘ＝３，ｚ＝２｝，｛ｘ＝４，ｚ＝１），…那么永远也找不到合适的值。但我们也可以看到Ｆ４中变量ｘ前的系数与Ｆ；中变量ｘ前的系数一致，所以可以对ｘ进行原方向探索，对ｚ单独考虑。假设根据Ｆ。对ｙ取值为６，根据Ｆ。，对ｚ取值为２，那么根据复合谓词对应的分支函数定义，第一轮｛ｘ＝３，ｙ＝６，ｚ＝２｝计算得到Ｆ＝ｍａｘ（一１，一ｌ，一１，０）＝Ｏ，第二轮只对ｘ进行探索，设计测试数据为｛ｘ＝４，ｙ＝６，ｚ＝２｝，计算得到Ｆ＝ｍａｘ（一１，一ｌ，一１，一１）＝一１符合分支函数定义的对测试数据的要求，这样才能找到合适的测试数据。２．３搜索算法中值得考虑的细节原函数最小化方法在测试数据搜索阶段以固定步长进行搜索，在针对不同程序测试时，不容易掌握步长的大小，针对这一问题，本文将采用一种动态确定步长的方法。在测试用例生成的改进算法中依据冲突谓词的当次运行所得的分支函数值来动念确定步长，有效地减少了搜索代数，缩短搜索时间，提高了搜索效率。动态步长确定可以用如下公式表示№Ｊ：Ｓｔｅｐ＝ｋ０＋ｋ术ＶａｌｕｅＶａｌｕｅ为当前谓词的分支函数值；参数ｋ由谓词表达式的系数及阶数等综合确定，本文中取变量前系数的倒数；ｋＯ为一微小修正量，当分支函数值为０，路径仍不匹配时，此修正量进行微小调整。例如有一分支函数Ｆ＝３ｘ＋５；假设变量ｘ的初始输入为６，则分支函数值Ｆ＝２３，取ｋ＝１／３，则Ｓｔｅｐ＝ｋ０＋（１／３）术２３＝ｋ０＋２３／３；在输入为整数时，将ｋＯ设为１／３，使得Ｓｔｅｐ＝８；由于分支函数值为正，而函数极小化方法的要求是向函数值减小的方向搜索，所以应该进行负向搜索，设置新一轮变量的值为６—８＝一２，由验证可知，此时Ｆ＝３水（一２）＋５＝一ｌ；符合分支函数定义，即谓词为真时，分支函数为负值。如果按照常规的设置步长的方法，将步长设为ｌ的话，需要经过多次搜索才能找到一２这个值。采用动态设置步长的方法可以在一定程度上提高搜索算法的效率，选择适当的步长可以减少搜索的次数，但每次重新确定新的变量值时，都要重新执行一遍１８河海人学硕士论文第一二章测试用例生成的搜索算法研究程序代码。如果能将程序代码简化，那么搜索的速度将更快。为此，本文还将引入程序切片技术，将对变量有影响的语句抽取出来，去掉无关的语句，减少代码量，以此简化代码，提高执行速度。２．４引入程序切片技术的必要性将程序切片技术运用到软件测试用例生成方法中，主要是为了提高测试用例生成的效率【２８１。在生成一组测试数据的过程中，选定某条执行路径，首先以初始值执行程序，以实际执行路径上某个不符合指定路径要求的分支点作为兴趣点，计算对应的动态程序切片。这样，当调整输入数据时，不再需要执行源程序，只需执行相应的程序切片即可。事实上，这个程序切片是源程序的一个子集，这样就减少了反复执行程序花费的时间，提高了测试数据生成的效率。程序切片有静态和动态之分，下一章内容将会详细介绍。本文选择动态切片，主要是因为动态切片更符合实际路径的代码需求，而静态切片不能很好的反应在某个输入变量下程序所选择的路径。动态切片包含了在某个特定输入下，所有可能影响兴趣点处某个兴趣变量的所有语句。它只考虑程序中的一条特定执行路径，这与路径覆盖方法能很好的结合起来。另一方面，动态程序切片保持了程序执行的动态行为，根据这些动态行为，确定相应分支函数的当前值，指导测试数据的调整方向。这样可以避免调整的盲目性，减少调整次数，也就提高了测试数据生成的效率。２．５本章小结本文讨论的测试用例生成的搜索算法的思想是：根据路径覆盖的原则生成所有的测试路径，然后根据每条测试路径分别生成对应的测试数据，测试数据生成的过程是一个逐步搜索的过程。随着程序复杂性的提高，原有搜索算法只针对一维谓词的情况已经无法满足程序需要。本章首先介绍了测试用例生成的前提，测试路径的生成，然后介绍了基于复合谓词的分组搜索算法。并通过具体的实例说明搜索算法执行的过程。１９河海人学硕士论文第三章程序切片技术与动态切片算法第三章程序切片技术与动态切片算法程序切片技术是一种分析和理解程序的技术，通过对源程序中各个兴趣点计算其程序切片以便分析和理解程序。对程序切片技术的研究有着极其重要的理论和实际意义，极大地丰富了程序分析、程序理解、程序维护的理论知识，为软件工程的各个阶段提供理论和技术支持，保证软件开发过程正确进行下去。尤其在编码和测试阶段，程序切片技术的应用更加广泛，它在程序分析、理解、测试、调试、度量以及维护过程中都有着极其广泛的用途。本文为了提高搜索算法的效率，重点引入了程序切片技术。为了很好的描述程序切片技术在搜索算法中的应用，本章将详细地介绍程序切片的定义与分类、程序切片技术的发展、静态程序切片和动态程序切片的切片准则和相关算法等内容。３．１程序切片的定义及分类３．１．１程序切片的定义程序切片是按照一定的准则从源程序中移去零条或多条语句后构成的，这部分语句可能会直接或间接地影响程序中某一兴趣点处变量的值。程序切片的基本思想是由Ｍａｒｋｗｅｉｓｅｒ于１９７９年在他的博士论文中首先提出的，他给出的程序切片的定义是：程序Ｐ的切片ｓｌｉｃｅ是Ｐ的一个可执行部分，对于某个兴趣点ｓ处的变量ｖ而言，这个可执行部分相对于程序Ｐ，在功能上是等效的。这是一种静态可执行切片【２０】。Ｓ．Ｈｏｒｗｉｔｚ等人对程序切片定义做了进一步的推广，“一个程序切片是由程序中的一些语句和判定表达式组成的集合。这些语句和判定表达式可能会影响在程序中的某个位置ｓ上所定义点或所使用的变量ｖ的值”１２４Ｊ。这种程序切片可以是一个可执行的程序，但它也属于静态切片。Ｋｏｒｅｌ和Ｌａｓｋｉ等人提出了动态切片的概念，认为动态切片是由在某个程序输入ｘ下，程序Ｐ中直接影响或间接影响某个兴趣点ｓ处的变量ｖ的那部分语句构成。３．１．２程序切片的分类程序切片可以按照不同的范畴进行分类，可以分为静态切片和动态切片、前向切片和后向切片、过程内切片和过程间切片【２７】。（１）静态切片和动态切片２０河海大学硕士论文第三章程序切片技术与动态切片算法静态切片包含了所有可能影响兴趣变量的语句。主要利用静态分析程序源代码的方法，计算在所有可能输入值情况下，对某个兴趣点有影响的那部分语句。也就是说，静态切片考虑了程序所有可能的执行路径。动态切片包含了在某个特定输入下，所有可能影响兴趣点处某个兴趣变量的所有语句。它只考虑了程序中的一条特定执行路径。（２）前向切片和后向切片对于程序中第ｉ条语句处的变量ｖ而言，前向切片包含了所有可能受ｖ影响的语句，而后向切片包含了所有可能影响ｖ的语句。要计算前向切片实际上就是构造集合Ｓｆｏｒｗａｒｄ（Ｖ／ｎ），该集合由程序Ｐ中所有受到变量Ｖ在ｎ点值影响的语句和控制谓词构成。而计算后向切片的集合Ｓｂａｃｋｗａｒｄ（Ｖ／ｎ），该集合由所有影响Ｖ在ｎ点值的语句和控制谓词构成。（３）过程内切片和过程问切片过程内切片只考虑了一个过程内部的语句，当程序中存在过程调用，则不能衍生出有效信息，而过程间切片主要针对程序由多个过程组成的情况。在使用过程问切片时需要注意的问题是当一个过程在不同的地方被调用时，必须要考虑调用的上下文，以便在编译时能够正确模型化运行时的执行情况。３．２程序切片技术的应用程序切片技术在软件分析、理解、调试、测试、度量、软件质量保证、逆向工程等许多方面有着广泛的应用，本节简单介绍切片技术在程序调试、软件维护、回归测试、软件度量等方面的应用瞵Ｊ。（１）程序调试在软件调试过程中，定位程序中存在的错误是一项困难的工作，程序切片可以帮助程序员很容易地进行错误定位。若检测到程序点Ｓ上的某个变量Ｖ存在错误，我们可以把＜Ｓ，Ｖ＞作为切片准则来计算后向切片，即所有对变量Ｖ在Ｓ点的值有影响的语句集，这样引起错误的代码就限定在这个切片中，通常情况下，这会大大降低要分析的代码量。（２）软件维护软件维护是软件生命周期的重要组成部分，要求在对现有系统理解的基础上确保修改系统不会引发新的错误。分解切片捕获与程序中某个变量在所有计算位置的值相关的程序信息，将对程序的修改引起的影响控制在一定的范围内，而不会带来无法预料的后果。这种方法需要计算程序中某个变量在所有位置的切片，也需要计算所有变量的分解切片。变量ｖ的分解切片是与变量ｖ有关的关键节点切片的并集，其中，关键点是指输出变量ｖ的节点和程序的出口节点。一个分解切片可以把程序分解为三个部分：部分、相关部分和补集部分。部分包含所有只被ｖ的分解切片包含的语句。私有部分的语句可被删除河海大学硕士论文第三章程序切片技术‘ｊ动态切片算法而不会影响其他部分。若对变量ｖ的所有赋值都集中在私有部分，则变量ｖ为可修改变量。可以在切片的任何位置中添加对可改变变量的赋值语句。相关部分包含所有既在ｖ的分解切片中又在其它变量的分解切片中的语句。若至少有一个对变量ｖ的赋值在公共部分，则变量ｖ为不可修改变量。修改这种变量会引起其他部分的改变。补集部分包含所有不包含在ｖ的分解切片中的语句。修改切片中的语句时，补充部分应该保持不变。（３）回归测试当软件系统修改后，为了保证系统的正确性以及修改后不会带来副作用，需要对其进行重新测试，这就是所谓的回归测试。回归测试不同于软件开发过程中的测试，因为已经存在部分测试用例，对于这些测试用例，我们可以全部重新测试一遍或者选择一部分进行测试。完全重新测试可能会消耗大量的资源，并且大部分情况下只有一小部分代码会受到修改的影响。因此，只需要对那些受影响的代码进行重新测试。对通过分解切片获得的补充部分就不需要进行重新测试。程序切片技术可以帮助我们获得那些受影响的代码，从而有助于选择测试用例，进一步分析需要测试的代码，简化测试过程，提高测试效率。（４）软件度量软件度量的两个重要指标就是内聚和耦合。其中内聚度指模块内部各成分之问的关联程序。模块的内聚度越高，越容易理解、修改和维护。为了度量模块的内聚度，Ｌ．Ｍ．Ｏｔｔ和Ｊ．Ｊ．Ｔｈｕｓｓ提出了数据切片的概念，计算关于数据标记而不是语句的切片，其中数据标记是指变量和常量的定义和使用。关于数据标记ｖ的数据切片包含：ｖ的切片集合中的语句所包含的数据标记序列。若一个数据标记存在于多个数据切片中，则称这个标记为胶水标记。通过胶水标记可以及将不同的数据切片连接起来。若一个数据标记存在于所有数据切片中，则称这个标记为强力胶水标记。标记的粘性用来度量与一个标记连接的切片数目。强功能内聚度定于为“强力胶水标记的个数与切片中数据标记的总数的比值”；弱功能内聚度定义为“胶水标记的个数与切片中数据标记的总数的比值”。根据这些定义，可以比较直观的分析模块的内聚度【８Ｊ。３．３程序切片准则程序切片必须依据一定的切片准则进行计算。对同一程序而占，切片准则不同，对应的程序切片也随之不同。静态切片准则和动态切片准则是程序切片最常用的两种切片准则１２７。。静态切片准则：静态切片准则可以用一个二元组Ｃ＝（Ｖ，ｓ）来表示，其中Ｖ是程序Ｐ中变量集合的一个子集，ｓ是程序Ｐ中的某个兴趣点，所谓兴趣点就是我们在程序Ｐ中关注的某条语句。给定这样一个静态切片准则Ｃ，我们就可以计算静态切片，得到的静态切片由可能影响ｓ处Ｖ中变量的所有语句和谓词组成。河海大学硕上论文第三章程序切片技术与动态切片算法对于ｓ处Ｖ中的变量来说，得到的切片应该与源程序具有相同的影响。动态切片准则：动态切片准则可以用一个三元组Ｃ＝（ｘ，ｓ，Ｖ）来表示，其中ｘ是程序Ｐ的一个输入，ｓ是程序Ｐ中的某个兴趣点，Ｖ是程序Ｐ中变量的一个子集。给定动态切片准则Ｃ，动态切片由在输入为ｘ时，程序中所有直接或间接影响兴趣点ｓ处Ｖ中变量的语句和谓词组成。除此之外，还有迭代切片准则、条件切片准则、前向切片准则、分解切片准则、多点切片准则和广义切片准则等等。３．４计算程序切片的算法根据程序切片的不同分类，切片算法也有静态和动态之分。本节首先介绍与程序切片技术相关的图论知识，以便更好的理解后面介绍的切片算法。随后简单介绍几种常用的静态切片算法以及动态切片算法ｆ２７１１２９１。３．４．１控制流图、程序依赖图和系统依赖图１．控锘０流图（Ｃｏｎｔｒ０１Ｆ１０ｗＧｒａｐｈ，ＣＦＧ）计算机程序设计语言一般都提供一些基本的控制结构用以表达程序中的控制流。比如顺序结构、分支结构和循环结构就是典型的程序结构。控制流图是程序分析领域中一个非常重要的概念，它将源程序用图的形式表示出来，在控制流图上可以方便的分析语句间的前趋关系和后继关系、支配节点以及程序执行路径等问题。有了这些概念就可以进一步分析语句问的控制依赖和数据依赖关系。定义３．１控制流图：一个控制流图Ｇ是一个有向图，该有向图的节点是一个具有唯一入口和唯一出口的基本模块。如果控制可以直接从基本模块Ａ流向基本模块Ｂ，则从节点Ａ到节点Ｂ有一条有向边。一个程序Ｐ的控制流图可以用四元组Ｇ＝（Ｎ，Ｅ，Ｅｎｔｒｙ，Ｅｘｉｔ）表示。其中，Ｎ是节点的集合，表示程序中的基本模块；Ｅ是边的集合，每条边是一个有序节点对＜ｎ；，ｎ。＞，它表示从ｎ；到ｎ，可能存在的控制转移；Ｅｎｔｒｙ和Ｅｘｉｔ分别表示程序Ｐ的入口和出口节点。如下所示为一个程序Ｐ和Ｐ的ＣＦＧ：河海大学硕ｌ：论文第三章程序切片技术与动态切片算法图３一ｌ程序片断Ｐ图３—２程序Ｐ的ＣＦＧ２．程序依赖图（Ｐｒｏｇｒ锄ＤｅｐｅｎｄｅｎｃｅＧｒａｐｈ，程序依赖图是由一个控制流图（Ｃｏｎｔｒ０１赖图（ＣｏｎｔｒｏｌＧｒａｐｈ，ＤｅｐｅｎｄｅｎｃｅＦｌｏｗＰＤＧ）Ｇｒａｐｈ，ＣＦＧ）、一个控制依ＤｅｐｅｎｄｅｎｃｅＧｒａｐｈ，ＣＤＧ）和一个数据依赖图（ＤａｔａＤＤＧ）组成。其中，控制流图描述了一个程序中的控制流；控制依赖图包含了程序中的控制依赖关系；数据依赖图是一个程序中语句之间所有数据依赖的集合。定义３．２控制依赖图：控制依赖图是一个有向图（Ｎ，Ｃ），其中节点集Ｎ是程序中所有语句对应的节点集合；如果有语句ｓｌ直接控制依赖于ｓ２，也就是有ＣＤ（ｓ１，ｓ２），则把边ｓ１一＞ｓ２加入到边集Ｃ中。定义３．３数据依赖图：数据依赖图也是一个有向图（Ｎ，Ｄ），其中节点集Ｎ是程序中所有语句对应的节点集合；如果有语句ｓ１数据依赖于ｓ２，即有ＤＤ（ｓ１，ｓ２），则把边ｓｌ一＞ｓ２加入到边集Ｄ中【３０Ｊ。３．系统依赖图在结构化程序中，程序依赖图一般包含过程依赖图（ＰｒｏｃｅｄｕｒｅＧｒａｐｈ，ＰｒＤＧ）和系统依赖图（ＳｙｓｔｅｍＤｅｐｅｎｄｅｎｃｅＤｅｐｅｎｄｅｎｃｅＧｒａｐｈ，ＳＤＧ）。系统依赖图是过程依赖图的一种扩充。系统依赖图所描述的程序具有以下特征：它由主过程和一些辅助过程构成；过程由ｒｅｔｕｒｎ结束而不是由ｅｎｄ结束，ｒｅｔｕｒｎ语句不包含一个变量列表；参数传递是ｖａｌｕｅ—ｒｅｓｕｌｔ方式的，也就是说形参的变化会导致实参的改变。系统依赖图包括了系统中各个过程的过程依赖图，另外还包括一些附加的边。这些附加的边包括表示从调用点到被调用过程的直接依赖边和表示调用引起的可达依赖的边。２４河海人学硕士论文第三章程序切片技术与动态切片算法３．４．２静态切片的算法ｗｅｉｓｅｒ首先提出了程序切片的概念，他所定义的程序切片实际上是一种静态切片，之后，人们对静态程序切片的方法进行了大量的研究，常用的静态切片算法主要有以下几种：（１）Ｗｅｉｓｅｒ提出的基于数据流方程的切片计算方法ｗｅｉｓｅｒ是通过解数据流和控制流方程来计算程序切片的。首先，建立待测程序的控制流图（ＣＦＧ），从其ＣＦＧ中产生相应的数据流和控制流方程。他使用一种迭代过程计算ＣＦＧ中每个结点相关的变量的集合。Ｗｅｉｓｅｒ描述了一种用来计算最少语句切片近似值的迭代算法。这种算法使用两种不同的迭代层次：跟踪可传递的数据依赖层和跟踪控制依赖层。后者把跟踪到的新的控制谓词控制的语句包含到某个控制谓词的切片中。对这样的新谓词，重复跟踪可传递的数据依赖层，直到把该谓词依赖的所有语句都包含进来为止。（２）基于信息流关系的算法这主要是由Ｂｅｒｇｅｒｅｔｔｉ和Ｃａｒｒｅ提出，他们计算切片的方法是：首先定义一些信息流关系，然后利用这些信息流关系来计算切片。（３）基于依赖图的图形可达性算法Ｋ．Ｊ．Ｏｔｔｅｎｓｔｅｉｎ和Ｌ．Ｍ．Ｏｔｔｅｎｓｔｅｉｎ于１９８４年提出切片准则（ｖ，ｓ），其中ｓ为程序Ｐ中的一个兴趣点，ｖ是在ｓ处定义或使用的变量，依据此切片准则，在程序依赖图（ＰＤＧ）上使用图形可达性算法来计算切片【２¨。这种方法的具体计算步骤是：先查找节点ｓ处变量ｖ的所有可到达定义节点，然后以这些节点为起点遍历程序依赖图，遍历过程中所有访问到的节点就构成了所需的静态程序切片。１９９０年，Ｈｏｒｗｉｔｚ，Ｒｅｐｓ和Ｂｉｎｋｌｅｙ等人使用依赖图来计算切片，他们丌发了一种过程问的程序表示——系统依赖图（ＳＤＧ），并实现了一个基于系统依赖图的两阶段图形可达性切片算法。在这类基于图形可达性的算法中，一般是指程序依赖图和系统依赖图可达。３．４．３动态切片的算法相对于静态程序切片技术而言，动态程序切片技术起步较晚，研究的时间比较短，但由于其动态性、灵活性受到了广泛的应用。一般来说，动态程序切片算法可以分为两类：基于后向分析的算法和基于前向分析的算法。基于后向分析的切片算法基本思想足：首先在某一输入下执行源程序并记录其执行轨迹，再回溯该执行轨迹，分析该执行轨迹上变量的动态依赖关系，最后河海大学硕士论文第三章程序切片技术ｊｊ动态切片算法通过这些动态依赖关系，计算出关于兴趣点处兴趣变量的动态切片。这种算法需要存储程序的执行轨迹以及其中的动态依赖关系，占用的空间比较大。Ｋｏｒｅｌ和Ｙａｌａｍａｎｃｈｉｌｉ提出一种动态程序切片前向算法，他们提出了可移动块的概念，认为程序可以看成是由若干个可移动块组成。通过从源程序中删除可移动块来构造动态程序切片。程序执行期间，执行到每个块的出口处，算法确定这个被执行的块是否应该包含在相应的动态切片中。常用的动态算法主要有３种１２７Ｊ：（１）Ａｇｒａｗａｌ和Ｈｏｒｇａｎ等人提出的基于动态依赖图的切片算法【３ｌＪ对于动态程序切片而言，我们可以通过执行原程序并记录其执行历史，构建原程序的动态依赖图，在程序依赖图上使用图形可达性获得程序切片。但是，构建动态依赖图时，语句的不同出现可能会受不同语句的影响，因此在动态依赖图中，语句的不同出现要用不同的节点来表示，这样空间开销较大，这在一定程度上了该方法的使用。（２）Ｋｏｒｅｌ和Ｙａｌａｍａｎｃｈ订ｉ提出的基于可移动块的切片前向计算方澍３２Ｊ在这种算法中，程序可以看成由若干个基本块组成，当程序执行到一个基本块的出口时，算法确定是否应将该基本块包括进相应的动态切片中。这种算法无需存储动态依赖图，空间开销小，但对包含循环的程序来说，该算法可能会产生不确切的结果。（３）Ｇｙｉｍｏｔｈｙ提出的基于程序Ｄ／ｕ表达式计算动念切片的方浏圳利用程序Ｄ／Ｕ表达式，计算某条语句执行时影响其变量定义的所有语句，进而求出动态切片。一个程序Ｄ／Ｕ表达式记录了一条语句中变量的定义和引用情况。使用Ｄ／Ｕ表达式，可将程序的控制依赖和数据依赖同等看待，从而不需要使用动态依赖图，这样就可以计算出与使用动态依赖图同样的动态切片来，其空间开销较小１３４Ｊ３．５ｌ”Ｊ。动态切片算法的实现本文采用的动态切片算法主要是参考文献【２７】中提出的基于前向分析的动态切片算法。在本文提出的算法中，引入控制依赖关系来表示程序中谓词的覆盖范围，通过控制依赖关系的层层传递，可以清晰地表示出源程序的结构，这与文献【２７】提出的支配关系有异曲同工之妙。但在计算算法的过程中，分析问题的角度有所不同，本文的算法比文献提出的算法更为简洁。计算程序切片必须依照一定的切片准则，前面介绍过静态切片准则和动态切片准则，下面再给出一个动态切片表达式的定义、变量被定义和变量被使用的定义以及控制依赖关系的定义。定义３．４动态切片准则：动态切片准则用～个三元组（ｘ，ｓ“，ｖ）表示，２６河海人学硕士论文第二章程序切Ｊｌ技术１ｊ动态切片算法其中ｘ表示程序的输入，ｓ表示程序中的某条语句，ｓ“表示程序在第ｋ步执行语句ｓ，ｖ表示程序的变量，ｖ可以是单个变量也可以是变量集合的子集。定义３．５动态切片表达式：给定动态切片准则Ｃ＝（ｘ，ｓ。，ｖ），Ｓ１ｉｃｅ（ｋ，ｖ）是兴趣点ｓ。处变量ｖ的动态程序切片。Ｓ１ｉｃｅ（ｖ）表示在当前执行位置处变量ｖ的动态程序切片，即在当前执行位置处影响变量ｖ的语句。其中ｓ“表示程序在第ｋ步执行语句ｓ，对于一条特定的程序路径而言，ｋ是一组从１开始的有序数列。定义３．６变量被定义：如果变量ｖ的值在ｎ处被修改，则称变量ｖ在ｎ处被定义，以Ｄｅｆ（ｎ）表示ｎ处定义变量的集合。定义３．７变量被引用：如果变量ｖ的值在ｎ处被使用，则称变量ｖ在ｎ处被引用，以Ｕｓｅ（ｎ）表示ｎ处引用变量的集合。定义３．８控制依赖关系：设ｓ。，ｓ：是程序Ｐ中的两条语句或语句块，ｓ。，ｓ。∈Ｎ，如果语句ｓ。的执行结果直接决定语句ｓ：的执行与否，则称语句ｓ：控制依赖于语句ｓ。，或称语句ｓ，控制语句ｓ。，记做ｓ：＝ＢｅＣｏｎｔｒ０１ｅｄＢｙ（ｓ，）或ｓ，＝Ｃｏｎｔｒｏｌ（ｓ２）。引入控制依赖关系，一是为了：当程序中存在谓词嵌套时，每个谓词的权力范围不同，控制依赖关系确定了每条语句的直接控制依赖语句，从而间接地确定程序的结构；二是为了：代替控制依赖图，由于程序依赖图的存储空间开销较大，使用控制依赖关系代替控制依赖图，使用变量被定义和被引用的关系来代替数据依赖图，这样可以完整地表示程序依赖图。控制依赖关系可以在程序预处理阶段给出，在计算程序执行路径时，根据程序流程图得到执行路径，同时也可以得到控制依赖关系。３．５．１算法思想本文引入控制依赖关系来表示程序中谓词的覆盖范围，对某个变量而言，如果当前执行语句与该变量没有任何依赖关系，且与兴趣点处的语句没有控制依赖关系，则删除该条语句，否则就加入程序切片中。计算程序切片，首先要构造相应的切片准则Ｃ＝（ｘ，ｓ。，ｖ），算法将按照这个切片准则，以某个节点ｓ。为兴趣点，构造各个变量对应的程序切片。在计算程序切片过程中，首先分析源程序，获得源程序中的控制语句以及存在的控制依赖关系，然后根据语句ｓ是否为控制语句分别讨论如何计算程序切片ｏ（１）ｓ为控制语句：在这种情况下，如果控制语句中的谓词条件被满足，ｓ必定属于该处的程序切片，将语句ｓ加入程序切片的同时，还要将ｓ中出现的变量在执行ｓ语句前的程序切片加入其中。如果控制语句中的谓词条件不被满足，河海人学硕Ｌ．论文第三章程序切片技术与动态切片算法对于该处的切片来说应该包含语句ｓ以及ｓ中出现的变量在执行ｓ语句前的程序切片，而对于下一步执行的语句来说需要重置成执行ｓ语句前的切片状态，在算法中用ｓｌｉｃｅ（ｖ）表示当前切片的状态或为表示为计算下一个程序切片所保留的切片状态，而用ｓｌｉｃｅ（ｋ，ｖ）表示第ｋ步对应的兴趣点的程序切片。（２）ｓ为简单语句：在这种情况下首先考虑变量ｖ是否在该处定义，如果被定义，即ｖ的值在ｓ处被改变，那么ｓ属于变量ｖ的切片；否则的话还要考虑ｓ是否受控制依赖，如果最近被执行的一条控制语句恰好是ｓ的控制语句且执行ｓ后变量ｖ未被修改，那么可以将此时的切片重置为控制语句执行前的程序切片，否则就不改变当前程序切片的状态。３．５．２算法过程输入：程序Ｐ以及相关的控制依赖关系、切片准则Ｃ＝（ｘ，ｓｑ，Ｖ）；输出：在执行位置ｑ处变量集合Ｖ中各个变量ｖ的动态切片。初始化：Ｆｏｒａ１１ｖ∈Ｖｓｌｉｃｅ（ｖ）＝ｓｌｉｃｅ（ｋ，ｖ）＝①：执行过程：Ｆｏｒ（１≤ｋ≤ｑ）计算每一步对应的程序切片：Ｉｆ（ｓ是控制语句）Ｉｆ（ｓ中的谓词不被满足）｛ｓｌｉｃｅ（ｖ）＝ｓｌｉｃｅ（ｋ，ｖ）：／／记录上步中的程序切片；ｓｌｉｃｅ（ｋ，Ｖ）＝ｓｌｉｃｅ（ｋ，Ｖ）ｕ｛ｓ）ｕＵｖ∈ｗＰ（ｓ）ｓｌｉｃｅ（ｋ，Ｖ）；／／记录第ｋ步时的程序切片；）Ｅ１ｓｅ／／ｓ中的谓词被满足ｓｌｉｃｅ（Ｖ）＝ｓｌｉｃｅ（ｋ，Ｖ）＝ｓｌｉｃｅ（ｋ，Ｖ）ｕ｛ｓ）ｕＥｌｓｅＵｖ∈艄Ｐ（ｓ）ｓｌｉｃｅ（ｋ，Ｖ）；ｉｆ（ｓ为简单语句）Ｉｆ（ｖ∈Ｄｅｆ（ｓ））ｓｌｉｃｅ（ｖ）＝ｓｌｉｃｅ（ｋ，ｖ）＝ｓｌｉｃｅ（ｖ）ｕ｛ｓ｝ｏＥｌｓｅｉｆ（最近执行的一条控制语句＝＝ｃｏｎｔｒｏｌ（ｓ）且执行ｃｏｎｔｒ０１（ｓ）后变量ｖ未被修改）ｓｌｉｃｅ（ｖ）＝ｓｌｉｃｅ（ｋ，ｖ）＝执行ｃｏｎｔｒ０１（ｓ）前的程序切片；Ｅ】ｓｅ河海大学硕一Ｉ：论文第三章程序切片技术与动态切片算法ｓｌｉｃｅ（ｖ）＝ｓｌｉｃｅ（ｋ，ｖ）＝ｓｌｉｃｅ（ｖ）：算法终止：ｋ＝ｑ。该算法与文献【２７】中提出的算法相比，层次更清楚，代码更简单，利用此算法得出的程序切片与利用文献【２７】中算法得出的程序切片基本一致。３．６动态程序切片生成实例根据上节中给出的计算程序切片的算法，可以计算出各个变量在实际运行过程中对应于各个兴趣点处的程序切片。实例如下：ｉｎｔ１２ｍ，ｎ，ｉ，ａ［５］：ｓｃａｎｆ（“％ｄ％ｄ…％ｄ”，＆ｍ，＆ｎ，＆ａ［１］，＆ａ［２］，…＆ａ［５］）：ｍａｘ＝ａ［１］：ｍｉｎ＝ａ［１］：ｓｕｍ＝ａ［１］：ｉ＝ｍ＋１：３４５６ｗｈｉｌｅ（ｉ＜＝ｎ）｛７８ｉｆ（ｍａｘ＜ａ［ｉ］）ｍａｘ＝ａ［ｉ］：ｉｆ（ｍｉｎ＞ａ［ｉ］）ｍｉｎ＝ａ［ｉ］：ｓｕｍ＝ｓｕｍ＋ａ［ｉ］：ｉ＝ｉ＋ｍ：９ｌＯ１１１２｝１３ｐｒｉｎｔｆ（“％ｄ％ｄ％ｄ＼ｎ’’，ｍａｘ，ｍｉｎ，ｓｕｍ）：任选一程序输入ｘ为：ｍ＝２，ｎ＝５，ａ＝｛１，２，３，４，５），在此输入下，程序的实际执行路径为：Ｐａｔｈ＝＜１１，２２，３３，４４，５５，６６，７７，８８，９９，１１ｍ，１２１１，６他，７１３，８１４，９１５，１１１６，１２１７，６１８，１３悖＞路径中的ｓ“表示第ｋ步时执行第ｓ条语句，记录了整条路径的执行过程。构造切片准则Ｃ＝（ｘ，１３１９，ｖ），ｖ是程序中变量集合｛ｍｉｎ，ｍａｘ，ｓｕｍ，ｉ），计算出的切片结果如下表所示：２９河海大学硕士论义第三章程序切片技术与动态切片算法表３—１程序关于兴趣点的动态切片Ｓ１ｉｃｅ（ｍａｘ）初始１１２２３３４４５５６６７７①中ｌ，ｌ。ｌ，１，２２２２５，５，６６，７①①①ｌ，１，ｌ，１，１，７８８１，２，５，６，７，８９９１，２，３，５，６，７，１１１０８，９７，１，Ｓ１ｉｃｅ（ｍｉｎ）①①①３３３３，２，５，３，６５，６，①Ｓｌｉｃｅ（ｓｕｍ）①①中①①ｌ，５，４，６５，６，１，ｌ，Ｓｌｉｃｅ（ｉ）１。４ｌ。１，４４，５５，６６，７ｌ，２，１，２，ｌ，２，７２，５，ｌ，３，５，６ｌ，４，５，６ｌ，５，６ｌ，３，５，６，９１，９３，４，５，６，１，３，５，６，９１，２，５，６，８３，５，６ｌ，４，５，６，ｌｌｌ，５，６１２¨ｌ，２，５，６，７，８１，３，５，６ｌ，４，５，６，１ｌ１，５，６，１２６１ｌ，２，５，６，７，８，１２７，ｌ，３，５，６，１２ｌ，４，５，６，１１，１２１，５，６，１２７ｍｌ，２，５，６，８，１２１，７，１，２，８，３，３，１２５，５，６，ｌ，２，４，５，６，ｌ，８，ｌ，２，１２５，５，６，７，７，８，１１，１２６，１２ｌ，４，５，６，１１，１２８１４ｌ，２，５，６，７，８，１２６，１２９惦ｌ，２，３，５，６，７，８，９，１２ｌ，１２ｌ，３，５，６，９，１，３，４，５，６，ｌ，１２１，３，５，６，９，９，１１，１２３，５，６，１２１，４，５，６，１ｌ，１２１１１６ｌ，２，５，６，７，８，１２５，６，１２１２１７ｌ，２，５，６，７，８，１２ｌ，３，５，６，１２１，４，５，６，ｌｌ，１２ｌ，５，６，１２６懈ｌ，２，５，６，７，８，１２７，１，３，５，６，１２ｌ，４，５，６，１ｌ，１２ｌ，５，６，１２１３１９１，２，５，６，８，１２１，３，５，６，１２ｌ，４，５，６，１ｌ，１２ｌ，５，６，１２河海大学硕士论文第三章程序切片技术与动态切ＪＩ算法注：（１）与参考文献【２７】相比，本文中改正了部分程序代码，生成的程序切片也有所改进。如果按照文献【２７】中的算法，在７门处生成关于变量ｍｉｎ的切片为｛ｌ，３，５，６，７，１２），这比本文中的算法得到的切片多一条语句７。（２）由于本程序中的语句ｌ是读于输入数据的语句，所以应该将该语句加入所有的程序切片中。由表３一ｌ可以直观地看出，无论在哪一个兴趣点执行的切片都要比执行原程序简单的多。算法验证：假设输入ｍ＝２，ｎ＝５，ａ＝｛１，２，３，４，５｝，求程序执行后ｓｕｍ的值。分析：由于程序只需要求ｓｕｍ一个变量的值，如果执行所有源程序，显然不是一种最好的方法。程序切片就是一种将程序简化的有效方法。步骤：根据表３—１中给出的动态切片可以看到在兴趣点１３１９处得到的关于变量ｓｕｍ的切片为｛１，４，５，６，１１，１２｝，由此得到的简单程序片断如下：１４５６ｓｃａｎｆ（“％ｄ％ｄ…％ｄ”，＆ｍ，＆ｎ，＆ａ［１］，＆ａ［２］，…＆ａ［５］）：ｓｕｍ＝ａ［１］：ｉ＝ｍ＋ｌ：ｗｈｉｌｅ（ｉ＜＝ｎ）｛１ｌｓｕｍ＝ｓｕｍ＋ａ［ｉ］：ｉ＝ｉ＋ｍ：１２｝执行该程序切片，通过计算可以得到ｓｕｍ＝９。比较：执行源程序的结果为：ｍａｘ＝５，ｍｉｎ＝ｌ，ｓｕｍ＝９。很显然，根据程序切片计算得出的结果和执行源程序的结果一致。优点：使用程序切片简化了源程序，减少了程序代码量，对于一个复杂的程序来说，可以明显地节约运行时间。在后面的应用中，对于某一个节点的切片来说，在调整数据的时候会多次使用到，所以节约的运行时间与调整数据的次数成正比，这样也就更能体现出切片技术的优势。当然，如果题目要求计算三个变量的值，那样三次执行程序切片的代价肯定要比执行一遍源程序的代价大得多。由于在后面的运用中，一般在每次调用程序切片时，只涉及到单个变量，而不可能是所有变量，这样的话，选用程序切片技术就会起到非常积极有效的作用。河海大学硕：卜论文第三章程序切片技术与动态切片算法３．７本章小结程序切片技术作为一种分析和理解程序的技术，广泛应用于软件工程的各个周期，尤其是回归测试和程序调试方面。本文尝试将动态程序切片技术应用到测试用例生成的算法上，提高搜索算法的效率。本章介绍了程序切片的定义、分类、切片准则以及动态切片算法。通过一个简单的实例，根据给定的输入和切片准则，生成程序中各变量在兴趣点处的动态切片，并用实例验证切片的正确性。３２河海人学硕．１：论文第四章设计与实现第四章设计与实现目前市场上已经出现不少自动化单元测试用具，比如Ｃ＋＋Ｔｅｓｔ，ＶｉｓｕｌＵｎｉｔ２．Ｏ。Ｃ＋＋Ｔｅｓｔ是专门针对Ｃ／Ｃ＋＋的单元级测试用具，可以自动测试Ｃ／Ｃ＋＋类、函数或部件，能够自动测试代码构造、测试代码的功能性和维护代码的完整性。ＶｉｓｕｌＵｎｉｔ２．０是一款图形化自动单元测试工具，可以自动生成测试代码、用例框架以及边界测试用例等等。但是，一般来说自动化测试工具对于测试用例的生成还有待进一步提高。本文围绕测试用例生成这个中心，依次介绍了测试路径的生成、基于复合谓词的分组搜索算法，以及搜索算法中引入的切片技术，看似形散，实则神不散。三方面的内容都对测试用例生成的搜索算法起到了积极有效的作用，改进了原有的搜索算法，提高了算法的效率。为此，本文参阅相关文献［３７卜［４０】中关于测试用例自动生成的一些介绍，将前面三章介绍的内容串接起来，设计出一个通过路径覆盖方法实现测试用例生成的系统框架，详细介绍了每个模块的功能以及整个系统的流程。相比用手工的方式生成测试用例而言，如果能设计出一个自动地生成软件测试用例的系统，那对软件测试人员来说将是一大幸事，可以帮助测试人员摆脱复杂乏味费事的寻找测试用例的工作。要设计出完整的测试用例生成的系统，那么需要将测试路径的生成、谓词的分析、初始数据的输入、程序切片的生成等部分内容进行程序化。但事实上，谓词分析这一部分属于对语义的分析，并非是本论文的研究重点。所以，在本论文中，给出一种测试用例生成的框架以及部分能实现的模块的算法，具体的实现有待进一步研究。４．１测试用例自动生成的框架本文在前面几章内容介绍的基础上，提出了一种由程序预处理模块、路径生成器、谓词分析器、切片生成模块、测试数据调整模块等部分组成的框架。由下图４—１所示：河海人学硕卜论文第四章设计与实现图４一ｌ测试用例自动生成框架其中，程序预处理模块主要负责对源程序进行分析处理的功能，具体包括对程序语句的标识、记录输入变量、寻找控制语句等。路径生成器主要负责程序路径的生成，在第二章中已经给出简单的路径生成算法。通过路径生成器的处理，生成程序的所有路径，每条路径由各语句前的标识和执行步骤组成。谓词分析器主要负责程序控制语句中谓词或复合谓词的分析和处理。利用第三章中介绍的分支函数，将控制语句中的谓词或复合谓词转化成相应的分支函数，并对复合谓词中出现的变量进行分组分析，以便在调整测试数据的时候使用。另外，分析谓词分析器生成的分支函数，确定部分变量的初始输入，对于不能确定的变量，可以选择随机生成的方法。切片生成模块主要是针对动态程序切片的生成。将其放入数据调整模块中，在数据需要调整的时候执行切片生成模块。在数据调整模块中，根据选定的路径和输入数据的初始值执行源程序，当实际路径与给定路径不一致的时候，生成关于该兴趣点的动态程序切片，并按照基本复合谓词的分组搜索算法和动态确定步长的方法调整变量的值，再次执行动态程序切片，最终生成符合给定路径的测试数据。河海人学硕上论文第四章设计与实现算法的优越性：本文提出的测试用例自动生成框架集合了谓词分析器、切片生成器等概念，将切片技术适当的融入其中。该框架是本文提出的搜索算法的模块化表现形式，与以往的爬山算法相比，主要有两方面的优点：一是解决了复合谓词的问题，提出了分组搜索算法，提高了搜索效率；二是引入了切片技术，在重复搜索数据时，精简了代码量，加快了搜索时间。４．２测试用例自动生成的流程根据上一节中介绍的测试用例自动生成的框架，可以将框架转化为如下几步流程：ｌ、将源程序输入程序预处理模块中，对源程序进行语句标识、记录输入变量、寻找控制语句等操作。２、将预处理过的程序分别装入路径生成器和谓词分析器中。在路径生成器中生成程序所有的路径，由各语句前的标识表示。在谓词分析器中，生成所有控制语句中简单谓词或复合谓词的分支函数，并将复合函数中的搜索方向一致的变量分为一组，以便在数据调整时使用。同时，生成输入变量的初始值。３、选定一条程序路径，用变量的初始值执行源程序，比较程序实际执行路径与给定路径，以两条路径出现不一致ｆｊ｛ｆ最近的分支点为兴趣点，以待下一步中生成动态程序切片。４、将上一步中兴趣点的信息输入切片生成模块中，生成动态的程序切片。５、根据第二步中得到的分支函数及变量搜索方向的信息，根据分支函数极小化的原则，选取适当的步长，调整输入变量的数据，在程序动态切片上执行（不必在源程序上执行，以此提高执行速度）。６、重复步骤５，反复调整输入数据，直到分支函数的当前值满足该路径的要求，即生成适合的测试数据。７、从路径生成器中选定其余路径，执行３—５的步骤，生成程序完整的测试用例。４．３设计与实现根据本章第一节中给出的系统框架结构，可以将系统分为程序预处理模块、路径生成模块、谓词分析模块、切片生成模块和数据调整模块。４．３．１程序预处理模块实现的思路河海大学硕十论文第四章设计与实现由于程序预处理模块设计不是本文讲述的重点，所以简单介绍一下设计的思路。该模块主要足对源程序进行预处理，从而获取源程序中的相关数据信息。具体实现的思路是：以文本模式按行读取源程序，并依次标记每行语句，即在每条语句前加上相应的行号；对每条语句的内容进行辨别，标记控制语句以及控制依赖关系；寻找程序的输入变量。简单程序过程如下：装入源程序：ｎ＝ｌ：ｉ＝ｌ：ｗｈｉｌｅ（第ｎ行语句不为空）｛ｒｅａｄ（第ｎ行语句）：ｉｆ（碰到ｓｃａｎｆ等读入语句）将其中的输入变量记入到输入变量的数组Ｖｉｎ［］中：ｉｆ（碰到ｉｆ／ｗｈ“ｅ等控制语句）｛在该语句前标识ｉ：将行号ｉ记入控制语句数组ｃｔｒｏｌｓ口中：ｉ＋＋：｝ｉｆ（碰剑分号结尾的语句）｛在该语句前标识ｉ：ｉ＋＋：｝ｎ＋＋：｝预处理模块主要为下一步的路径生成和谓词分析提供必要的信息。路径生成模块的思想及主要算法在第二章中已经做出详细介绍。４．３．２谓词分析器的实现谓词分析器主要负责程序控制语句中谓词或复合谓词的分析和处理。利用第三章中介绍的分支函数，将控制语句中的谓词或复合谓词转化成相应的分支函数，并对复合谓词中出现的变量进行分组分析，以便在调整测试数据的时候使用。３６河海人学硕士论文第四章设计与实现另外，分析谓词分析器生成的分支函数，确定部分变量的初始输入，对于不能确定的变量，可以选择随机生成的方法。算法步骤描述：ＰｒｅｄｉｃａｔｅＡｎａｌｙｓｅ（ｐｒｏｇｒａｍ）｛ＣＳ＝ｇｅｔＣｏｎｔｒ０１Ｓｅｎｔｅｎｃｅ（ｐｒｏｇｒａｍ）：／／获取程序的控制语句Ｐｒｅｄｉｃａｔｅ［］＝ｇｅｔＰｒｅｄｉｃａｔｅ（ＣＳ）：／／获取控制语句中的谓词（复合谓词）ＢＦ［］＝ＰｒｅｄｉｃａｔｅＴｏＦｕｎｃｔｉｏｎ（Ｐｒｅｄｉｃｔｅ［］）：／／将谓词转换成分支函数Ｖａｒ［］＝ｇｅｔＶａｒｉａｂｌｅ（ＢＦ［］）：ＳｅｔＩｎｉｔｉａｌＶａｌｕｅ（Ｖａｒ［］，ＢＦ［］）：Ｇｒｏｕｐｉ／／获取分支函数中的变量／／没置变量的初始值／／对变量进行分组ｎｇ（Ｖａｒ［］）：ｌ４．３．３切片生成模块的实现切片生成模块主要负责动态程序切片的生成。首先，根据输入变量的初始值执行源程序，当实际路径与给定路径不一致的时候，生成关于该兴趣点的动态程序切片，调整变量的值，再次执行动态程序切片，最终生成符合给定路径的测试数据。图４—１中将切片生成模块放入测试数据调整模块中，因为切片生成模块是在数据需要调整时调用，如果输入变量的初始值就能满足程序路径，那么切片生成模块就不需要执行。动态程序切片生成的具体过程在第三章中已经详细给出，这罩就不重复叙述。４．３．４数据调整模块数据调整模块是整个测试用例生成的搜索算法的核心。数据调整实际上就是在搜索中寻找符合条件的测试数据。在第二章中，针对程序中出现的复合谓词给出了一种基于复合谓词的测试用例生成的分组搜索算法。结合程序切片模块，将数据调整模块实现的算法步骤描述如下：（１）执行谓词分析器中生成的输入变量的初始值，并寻找第一个与给定路径不一致的兴趣点：（２）（３）根据切片准则，生成该兴趣点处的动态程序切片；根据谓词分析器中的变量分组，对分组中变量数目最多的一组变量按各自的动态步长进行调整；用调整后的输入变量值执行该兴趣点的动念切片，如果还不符合３７（４）河海大学硕上论文第叫章设计与实现分支函数，则继续调整数据，（一般来说，动态步长法能快速定位输入变量的值空间，所以如果需要再次凋整时，先对其它输入变量调整。）循环执行步骤（４），直到输入变量满足此处的分支谓词；（５）满足此处兴趣点后，继续执行程序，直到发现下一个与指定路径不一致的兴趣点，重复（２）、（３）、（４）步骤；如果到程序结束，都符合给定路径，则将该输入变量的数据作为一组测试数据保存下来，退出数据调整模块，继续生成下一组测试数据。４．３．５实例本节以学生管理系统中奖学金查询模块作为测试对象，根据上面提出的框架结构的流程来说明测试用例生成的方法和步骤。学生管理系统主要管理学生的学籍信息、课程信息、成绩信息，并提供课表查询、成绩查询、奖学金查询等查询功能。下面介绍的奖学会查询模块的主要功能是：在输入三门课程成绩时，如果三门总分高于或等于２４０，且最低分高于或等于８０分，即可获得一等奖学金；如果三门总分高于或等于２４０，且最低分高于或等于７５分，即可获得二等奖学金；如果三门总分高于或等于２４０，且最低分高于或等于７０分，即可获得三等奖学金；如果有一门最高分达９０分以上，且最低分不低于６０分，则可以获得单项奖学金，如果有至少一门低于６０分，则提示需要重修。程序流程图：３８河海大学硕卜论文第四章设计与实现图４—２程序流程图程序代码如下：ｆｌｏａｔｉｎｔｌ２３ａ［３］，ｍａｘ，ｍｉｎ：Ｔ，ｉ，ｓｃｈ０１ａｒｓｈｉｐ：ｓｃａｎｆ（“％ｄ％ｄ％ｄ＂，＆ａ［１］，＆ａ［２］，＆ａ［３］）：ｍａｘ＝ａ［１］：ｍｉｎ＝ａ［１］：３９河海大学硕士论文第四章设计与实现４５Ｔ＝０：ｉ＝２：６ｗｈｉｌｅ（ｉ＜＝３）｛７８ｉｆ（ｍａｘ＜ａ［ｉ］）ｍａｘ＝ａ［ｉ］：ｉｆ（ｍｉｎ＞ａ［ｉ］）ｍｉｎ＝ａ［ｉ］：ｉ＋＋：９１０１ｌ｝１２１３１４１５ｉｆ（ａ［１］＋ａ［２］＋ａ［３］＞＝２４０）｛ｉｆ（ｍｉｎ＞＝８０）｛Ｔ＝ｌ：ｓｃｈｏｌａｒｓｈｉｐ＝１０００：１６ｐｒｉｎｔｆ（“恭喜你获得了一等奖学金！”）：ｅｘｉｔ（Ｏ）：）１７１８１９２０Ｅｌｓｅｉｆ（ｍｉｎ＞＝７５）｛Ｔ＝２：ｓｃｈｏｌａｒｓｈｉｐ＝５００：ｐｒｉｎｔｆ（“恭喜你获得了二等奖学金！”）：ｅｘｉｔ（０）：）２１２２２３２４Ｅｌｓｅｉｆ（ｍｉｎ＞＝７０）｛Ｔ＝３：ｓｃｈ０１ａｒｓｈｉｐ：３００：ｐｒｉｎｔｆ（“恭喜你获得了三等奖学金！”）：ｅｘｉｔ（Ｏ）：｝）２５ｉｆ（ｍａｘ＞＝９０＆＆ｍｉｎ＞＝６０＆＆Ｔ＝＝Ｏ）｛Ｔ＝５：ｓｃｈ０１ａｒｓｈｉｐ＝２００：２６２７２８ｐｒｉｎｔｆ（“恭喜你获得了单项奖学金！”）：）河海人学硕上论文第四章设计‘ｊ实现２９３０３１Ｅ１ｓｅｉｆ（ｍｉｎ＜６０）｛Ｔ＝一１：ｐｒｉｎｔｆ（“你的成绩不理想，需要重修！”）：）３２ｅｌｓｅｐｒｉｎｔｆ（“这次没有获得奖学金，继续努力”）：（１）根据测试用例生成的流程进行分析第一步：将程序代码放入程序预处理器中进行分析；将程序语句进行编码（已标注在代码前），标记控制语句，寻找程序的输入变量等。将ｗｈｉｌｅ、ｆｏｒ、ｉｆ等语句标记为控制语句，输入变量为ａ［１］，ａ［２］，ａ［３］。第二步：将预处理过的程序装入谓词生成器中，生成相应的分支函数（语句ｓ处的分支函数用Ｆｓ表示）：Ｆ６＝ｉ一３：Ｆ７＝ｍａｘ—ａ［ｉ］：Ｆ９＝ａ［ｉ卜ｍｉｎ：Ｆ１２＝２４０一（ａ［１］＋ａ［２］＋ａ［３］）：Ｆ１３＝８０—ｍｉｎ：Ｆ１７＝７５一ｍｉｎ：Ｆ２１＝７０—ｍｉｎ：Ｆ２５＝ｍａｘ（（９０—ｍａｘ），（６０一ｍｉｎ），ａｂｓ（Ｔ一０））：Ｆ２９＝ｍｉｎ一６０：由于只有Ｆ１２中含有输入变量，暂且将ａ［１］，ａ［２］，ａ［３］三个输入变量的初始值设为该分支函数的一个临界点，均为８０。第三步：生成程序执行路径；第四步：选定一条执行路径，根据输入变量的初始值执行程序。（２）路径生成过程１、分析ｗｈ“ｅ循环部分，本程序中循环执行两次，所以将循环结构转变成执行两遍的顺序结构。如图４—３所示：４ｌ河海大学硕＿Ｊ：论文第四章设汁与实现图４—３部分语句流图循环执行一遍的基本路径为｛６，７，（８，空），９，（１０，空），１１）；用笛卡儿积的方式可以将基本路径拓展成四条路径分别为：｛６，７，８，９，１０，１１）；｛６，７，８，９，１１）；｛６，７，９，１０，ｌｌ｝；｛６，７，９，儿）；循环执行两遍，相当于对上面四条路径再做一次笛卡儿积，可以生成１６条路径，分别为：｛６，７，８，９，ｌＯ，１１，６，７，８，９，１０，１１｝；｛６，７，８，９，１０，１１，６，７，８，９，１１｝；｛６，７，８，９，１０，１１，６，７，９，１０，１１）；｛６，７，８，９，１０，１ｌ，６，７，９，１ｌ｝；｛６，７，８，９，１１，６，７，８，９，１０，１１｝；｛６，７，８，９，１１，６，７，８，９，１１）；｛６，７，８，９，１１，６，７，９，１０，１ｌ｝：｛６，７，８，９，ｌｌ，６，７，９，１１｝；｛６，７，９，ｌＯ，１１，６，７，８，９，１０，１１｝；｛６，７，９，１０，１ｌ，６，７，８，９，１ｌ｝；｛６，７，９，１０，１１，６，７，９，ｌＯ，ｌ１）；｛６，７，９，１０，１１，６，７，９，１ｌ｝：４２河海大学硕士论文第四章设计０实现｛６，７，９，１１，６，７，８，９，１０，１１｝；｛６，７，９，１ｌ，６，７，８，９，１１｝；｛６，７，９，ｌｌ，６，７，９，１０，ｎ｝；｛６，７，９，１ｌ，６，７，９，１ｌ｝；２、分析由ｉｆ条件语句控制的分支结构，本程序中语句块１２—２４和语句块２５—３１分别为两个ｉｆ控制语句块。前一个控制语句块下只有一个分支语句块，但是又嵌套下一级的控制语句块；后一个有两个分支语句块。用语句流图可以表示为：图４—４部分语句流图这是一个比较复杂的带嵌套的分支语句结构，得到第一次基本路径为：｛１２，（１３，空），２５，（２６—２８，２９，３２）｝，首先做第一次笛卡儿乘积，然后对其中的控制语句１３、２９利用递归算法展开，最后得到所有子路径。由于路径条数较多，选取其中一条典型的路径，用做后面的执行路径：｛１２，１３，１７，２ｌ，２５，２６，２７，２８｝。４３河海人学硕士论文第ｐｑ幸设计与实现（３）执行过程选定一条完整的执行路径Ｐａｔｈｌ＝｛１１，２２，３３，４４，５５，６６，７７，８８，９９，１１１０，６１１，７１２，９１３，１０１４，１１１５，１２１６，１３１７，１７‘８，２１１９，２５２０，２６２１，２７２２，２８２３）。执行过程如图４—５所示：图４—５执行过程不意图根据图４—５所示，用输入变量（８０，８０，８０）执行程序，得到第一个兴趣点为７１，构造此处关于变量ｍａｘ的程序切片｛１，２，５，６，７），此处谓词分支函数Ｆ７＝ｍａｘ—ａ［２］，此时变量ｍａｘ＝ａ［１］＝８０，为满足分支函数极小化原则，向分支函数减小的方向调整，所以调整ａ［２］为８１，并执行程序切片。用调整后的输入变量（８０，８１，８０）执行程序，得到第二个兴趣点９１３，构造此处关于变量ｍｉｎ的程序切片（１，３，５，６，９，ｌＯ，１１），此处的谓词分支函数Ｆ９＝ａ［３卜ｍｉｎ，此时变量ｍｉｎ＝ａ［１］＝８０，调整ａ［３］为７９，并执行程序切片。继续用调整后的变量（８０，８１，７９）执行程序，得到第三个兴趣点１７１８，构造此处关于变量ｍｉｎ的程序切片｛１，３，５，６，９，１０，１１，１２，１３，１７），此处谓词分支函数Ｆ１７＝７５一ｍｉｎ，此时ｍｉｎ＝ａ［３］，所以调整ａ［３］＝７４，调整过程中执行切片遇到语句１２处的分支函数Ｆ１２＝２４０一（ａ［１］＋ａ［２］＋ａ［３］），为了满足该分支函数，同时调整ａ［１］和ａ［２］，以步长为ｌ调整３次后，ａ［１］＝８３，ａ［２］＝８４。用调整后的变量（８３，８４，７４）执行程序，得到第四个兴趣点２ｌ坩，此处的情况和上一步的情况类似，最后调整ａ［１］＝８６，ａ［２］＝８７，ａ［３］＝６９。继续执行源程序，遇到第五个兴趣点２５２０，此处复合谓词对应的分支函数Ｆ２５＝ｍａｘ（（９０一ｍａｘ），（６０一ｍｉｎ），ａｂｓ（Ｔ一０）），由于（６０一ｍｉｎ）和ａｂｓ（Ｔ一０）／Ｊ、于等于零，满足子分支函数定义，所以只需调整变量ｍａｘ的值。此时ｍａｘ＝ａ［２］＝８７，为满足分支函数条件，调整ａ［２］为９０。再次执行程序，可以发现能够顺利执行至程序结束。所以，得到对应于该路径的测试数据为（８６，河海人学硕上论文第叫章设计‘ｊ实现９０，６９）。补充说明：对于兴趣点２５２０处复合谓词对应的分支函数Ｆ２５＝ｍａｘ（（９０—ｍａｘ），（６０一ｍｉｎ），ａｂｓ（Ｔ一０）），如果此时的ｍａｘ和ｍｉｎ的值分别为７０和５０，那么需要对ｍａｘ和ｍｉｎ同时搜索。前者的动态步长为９０—７０＝２０，后者的动态步长为６０一５０＝１０，所以可以一次调整为９０和６０。生成一组测试数据后，将测试数据保存，然后重新选择新的执行路径，依次生成所有的测试数据。（４）执行结果所谓的测试用例就是由测试数据、执行结果、预期结果组成的一系列信息。可以用如下的形式表示为：测试数据测试用例ｌ：（８６，９０，６９）执行结果获单项奖学金预期结果获单项奖学金（５）算法比较与原有爬山算法相比，论文中提到的测试用例生成方法不但引入了程序切片技术，还针对复合谓词的情况，提出了分组搜索算法。在数据调整过程中，无需执行源程序，只需要执行相应的程序切片即可。与参考文献［２７］中提到的切片算法相比，本文在调整数据的时候，根据变量的搜索方向进行分组，并设定了动态步长的调整方法，减少了调整次数。例如在兴趣点２５２０处复合谓词对应的分支函数Ｆ２５＝ｍａｘ（（９０一ｍａｘ），（６０一ｍｉｎ），ａｂｓ（Ｔ一０）），如果此时的ｍａｘ和ｍｉｎ的值分别为７０和５０，采用参考文献［２７］中的算法，那么需要对ｍａｘ和ｍｉｎ两个变量分别搜索，如果采用步长为１，那么对于ｍａｘ变量需要调整２０次，同样，对于ｍｉｎ变量需要调整１０次，这样一共需要调整３０次。而本文中采用的算法同时对ｍａｘ和ｍｉｎ进行探索，并采用动态步长的计算方法，一次就可以调整到合适的变量值。对于含有复杂的复合谓词的程序而言，采用复合谓词的分组搜索算法，大大改进了搜索效率。动态步长的引入，也减少了调整次数，从而获得了一种比较高效的测试用例生成算法。（６）结论通过实例可以证明使用本文提出的通过路径覆盖的搜索算法可以得到给定路径上的测试数据，依次执行所有的给定路径，便可以得到所有的测试数据。本文所提出的搜索算法在原有爬山算法的基础上，引入了复合谓词的解决方法以及程序切片技术，在调整数据的时候，仅执行相应的程序切片，并４５河海大学硕上论文第四章设计‘ｊ实现根据动态步长调整数据，这些对于提高算法效率都起到了积极的作用。４．４本章小结本章主要提出了测试用例生成的系统框架，由程序预处理模块、路径生成器、谓词分析器、切片生成模块、测试数据调整模块等部分组成。描述了各个模块的功能以及整个系统的流程。最后通过实例，依据系统提出的流程，生成了特定执行路径下的测试用例。河海人学硕上论文第五章总结‘ｊ展望第五章５．１本文的主要工作总结与展望本文讨论了一种在白盒测试方法下基于路径覆盖的测试用例生成方法。通过分析程序结构，计算出程序的所有可执行路径，然后根据执行路径依次生成特定路径下的测试用例。为了适应复杂的程序结构，文中引入了复合谓词的概念，利用分支函数极小化的方法逐步逼近合适的测试数据。文中给出了对应于简单谓词的分支函数定义以及对应于复合谓词的扩展分支函数定义。并通过实例介绍了利用分支函数极小化方法实现测试数据搜索的过程。另一方面，在进行数据调整（数据搜索）时，需要反复执行源程序以验证测试数据是否符合给定的测试路径。为了减少程序代码的执行量，引入了动态程序切片技术。程序切片抽取了程序中与某一变量相关的代码片断，忽略了暂时无关的代码行，大大简化了程序的代码量。本文详细介绍了切片技术的发展、切片的分类、切片准则、切片算法思想，提出了一种引入控制依赖关系的动态切片算法，通过实例验证了切片算法的可行性。最后，本文通过参阅相关文献，分析和总结后，提出了一种通过路径覆盖实现测试用例生成的系统框架，给出了该系统的框架图，详细说明了系统的流程，以及各个模块应该实现的功能，并给出了部分模块的算法思想。最后以学生管理系统中奖学金查询模块为实例，演示了该模块执行时的流程，并生成了给定路径下的测试数据。５．２进一步的工作本文围绕测试用例生成这个概念，提出了通过路径覆盖实现测试用例生成的分组搜索算法。论文给出了一种测试用例生成的框架，并详细叙述了各个模块的功能。通过实例可以验证框架各模块的可行性，但对于整个系统能否用代码完全实现，还需要进行进一步的研究。所以，这有待于今后将模块功能细化，并逐步用代码实现。特别是程序预处理模块，需要对程序进行语义分析，将一般语句和控制语句区分开，并对的语句进行标识。控制语句虽然不是一条以分号结尾的语句，但为了方便谓词分析，需要将控制语句标识成单独的语句。另外，谓词分析模块，需要对各控制语句中的谓词进行分析，并自动转化成分支函数。对于有些谓词中包含的中间变量，需要转化成与输入变量相关的表达式。另一方面，文中所涉及的待测程序具有一定的局限性，文中只给出了输入变４７河海人学硕上论文第五章总结与展望量为整数的情况，对于输入数据为实型数、字符串、特殊数据结构的一些情况还未提出相应的方法。事实上，对于输入变量为字符串类型等情况时，不适合使用逐步搜索的算法，可以对其单独考虑。所以，如果将测试用例生成设计成一个完成的、可行的系统，那就需要对特殊输入的变量单独考虑。本文只是结合了路径覆盖方法、复合谓词、程序切片等内容，对测试用例生成这个方面做了一些初步的研究。希望能对软件测试的发展尽一点绵薄之力。河海大学硕Ｌ．论文致谢致谢在论文完成之际，谨向我的导师陈金水教授表示深深的感谢！从本科毕业设计开始，陈老师就成为我学习上的导师，生活中的朋友。三年多来，陈老师在生活上给我无微不至的关怀；在学术上给我悉心指导与教育。本文从选题、理论研究、实验分析到论文撰写都得到了陈老师的悉心指导和无私帮助。陈老师在繁忙的工作中抽出大量时间关心我的课题进展，并对本论文进行了严格的审查和细致的修改，特别是陈老师经常从一大早开始工作一直到很晚才离开办公室，让我倍受感动。陈老师严谨求实的治学态度，对事业的孜孜追求、以及对学生科研能力、工作作风、思维方法的培养和谆谆教诲，将让我终生难忘，终生受益。特向他致以崇高的敬意和衷心的感谢！感谢实验室的所有同学、已经毕业的师兄师姐和还在继续学习的师弟师妹，他们共同创造了宽松的学习环境和良好的学习氛围，并且给予我许多有益的启迪。特别感谢三位舍友，在三年的学习和生活中给了我很多帮助，陪我度过了愉快的学习时光。感谢我的父母和家人，他们为我付出了很多，给了我很多很多无私的关怀和帮助。他们的关心和支持是我的坚强后盾，他们对我无私的爱永远是我积极生活、认真完成学业的动力！感谢在百忙之中抽出时间审阅论文和参加答辩的各位老师，谢谢你们提出的宝贵建议。最后要感谢所有关心和帮助过我的老师、同学和朋友们１４９河海大学硕上论文参考文献参考文献［１］ＧｌｅｎｆｏｒｄＪ．Ｍｙｅｒｓ．软件测试的艺术Ｔｈｅ机械Ｔ业出版社，２００６．［２］ＲｏｎＰ眦ｏｎ．软件测试．计算机应用研究，机械工业出版社，２００６．［３］陈胜军．软件测试方法的研究．安徽电子信息职业技术学院学报，２００６年第１期，第５卷．［４］池万乐．软件测试技术的应用．电脑知识与技术，研究与开发曾凌峰．浅谈软件测试方法．科技资讯，２００６Ｎｏ．３ＡｒｔｏｆＳｏｆｔｗａｒｅＴｅｓｔｉｎｇ．［６］万琳．路径测试用例白动生成中的搜索算法分析．计算机工程，第３２卷第ｌ期２００６年１月．［７］易云辉，汪闰人．基于遗传算法的软件测试用例生成系统模型．科技广场，２００６．６．［８］李必信．程序切片技术及其应用．科学出版社，２００６．［９］毛颖．测试用例自动生成系统研究与实现．电子科技人学，２００７年４月．［１０］ＣｏｗａｒｄＰＤ．Ｓｙｍｂｏｌｉｃｅｘｅｃｕｔｉｏｎａｎｄｔｅｓｔｉｎｇ．ＩｎｆｏｒｍａｔｉｏｎａｎｄＳｏｆｔｗａｒｅＴｅｃｈｎ０１０９ｙ，Ａｃｏｎｓｔｒａｉｎｔｓ０１ｖｅｒ１９９ｌ，ａｎｄｏｆ３３（１），ｐｐ．５３—６４．［１１］ＺｈａｎｇＪ，ａｎａｌｙｓｉｓ．ＷａｎｇＸ．ｉｔｓａｐｐｌｉｃａｔｉｏｎｔｏｐａｔｈｆｅａｓｉｂｉｌｉｔｙＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇ＆ＫｎｏｗｌｅｄｇｅＩｎｔｅｒｎａｔｉｏｎａｌ２００ｌ，Ｊｏｕｒｎａｌｐｐ．１３９—１５６．ＭａｔｈｕｒＥｎｇｉｎｅｅｒｉｎｇ，１１（２），Ｐ．［１２］ＮｅｅｌａｍＧｕｐｔａ，ＡｄｉｔｙａａｎａｎｄＭａｒｙｒｅｌａｘａｔｉｏｎＬｏｕＳｏｆｔ’ａ．ＡｕｔｏｍａｔｅｄＡＣＭｔｅｓｔｄａｔａｇｅｎｅｒａｔｉｏｎｕｓｉｎｇｉｔｅｒａｔｉｖｅｍｅｔｈｏｄ．ＳＩＧＳＯＦＴＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇＮｏｔｅｓ，２３（６），Ｎｏｖｅｍｂｅｒ，ｔｅｓｔ１９９８，ｄａｔａｐｐ．２３１—２４４．ＩＥＥＥＴｒａｎｓｏｎ［１３］ＫｏｒｅｌＢ．Ａｕｔｏｍａｔｅｄ１９９０，ｓｏｆｔｗａｒｅｇｅｎｅｒａｔｉｏｎ．ＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇ，１６（８），ｐｐ．８７０一８７９．ｔｅｓｔ［１４］ＫｏｒｅｌＢ，Ａ１一ＹａｍｉＡＭ．Ａｕｔｏｍａｔｅｄｒｅｇｒｅｓｓｉｏｎｇｅｎｅｒａｔｉｏｎ．ＰｒｏｃｏｆｔｈｅＡＣＭＳＩＧＳＯＦＴＩｎｔ．Ｆｌｏｒｉｄａ，Ｓｙｍｐ．ｐｐ．ＯｎＳｏｆｔｗａｒｅＴｅｓｔｉｎｇａｎｄＡｎａｌｙｓｉｓ，ＣｌｅａｒｗａｔｅｒＢｅａｃｈ，ＵＳＡ，１９９８，１４３—１５２．Ａｓｔｒａｔｅｇｙｆｏｒｔｅｓｔ［１５］ＪｏｎｅｓＢＦ，ＥｙｒｅｓＤＥ，ｂｒａｎｃｈａｎｄＳｔｈａｍｅｒＨ—Ｈ．ｆａｕｌｔ—ｂａｓｅｄｕｓｉｎｇｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ１９９８，ｔｏａｕｔｏｍａｔｅｉｎｇ．ＴｈｅＣｏｍｐｕｔｅｒＪｏｕｒｎａｌ，４ｌ（２），ｐｐ．９８一１０７．［１６］荚伟，谢军闾，奚红宁，高仲仪．遗传算法在软件测试数据生成中的应用．北京航空航天大学学报，１９９８，２４（４）：４３４—４３７．［１７］ＭｉｃｈａｅｌＣＣ，ＭｃＧｒａｗｑＳｃｈａｔｚＭＡ．Ｇｅｎｅｒａｔｉｎｇｓｏｆｔｗａｒｅｔｅｓｔｏｎｄａｔａｂｙ１０．ｅＶｏｌｕｔｉｏｎ．ＩＥＥＥＴｒａｎｓＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇ，２００１，２７（１２）：１０８５一ｌｌ［１８］夏辉，宋昕，千理．基于Ｚ路径覆盖的测试Ｈｊ例自动生成技术研究．河海人学硕Ｊ二论文参考文献《现代电子技术》，２００６年第６期．［１９］伦立军，丁雪梅，李英梅．路径覆盖自动生成技术研究［２０］ｗｅｉｓｅｒＭ．Ｐｒｏｇｒａｍｏｎｓｌｉｃｉｎｇ．１９８４，ＩＥＥＥＴｒａｎｓＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇ，ＳＥ—ｌＯ（４）：３５２—３５７．［２１］ＫａｒｌＪ．Ｏｔｔｅｎｓｔｅｉｎ，ＴｈｅＡＣＭｐｒｏｇｒａｍＬｉｎｄａＭ．０ｔｔｅｎｓｔｅｉｎ．ｉｎａｄｅｐｅｎｄｅｎｃｅｇｒａｐｈＮｏｔｉｃｅｓ，ｓｏｆｔｗａｒｅｄｅｖｅｌｏｐｍｅｎｔｅｎｖｉｒｏｎｍｅｎｔ．ＳＩＧＰＬＡＮ１９８４，１９（５）：１７７—１８４．ＴｅｓｔＤａｔａＧｅｎｅｒａｔｉｏｎ．１９９０．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎ［２２］ＢｏｇｄａｎＫｏｒｅｌ．ＡｕｔｏｍａｔｅｄＳｏｆｔｗａｒｅＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇ，ＶＯＬ．１６．Ｎ０．８．Ａｕｇｅｓｔ［２３］张勇翔，李必信，郊国梁．程序切片技术的研究与应用．计算机科学，２０００，２７（１）．［２４］ＣｈｒｉｓｔｏｎＳｔｅｉｎｄｌ．Ｐｈ．ＤＴｈｅｓｉｓ．１９９９．ＰｒｏｇｒａｍＳ１ｉｃｉｎｇｆｏｒＯｂｊｅｃｔ—ＯｒｉｅｎｔｅｄＰｒｏｇｒａｍｍｉｎｇＬａｎｇｕａｇｅｓ．［２５］刘万春，李顺华，朱玉文．基于改进的Ｚ路径覆盖策略的路径生成算法．计算机｜Ｔ程与设计，２００５。２６（１２）．［２６］贺青春，叶柏龙．完全路径覆盖测试法．矿业研究与开发，２００７，２７（１）．［２７］王雪莲．程序切片技术研究及其在软件测试数据生成中的应用．北京化工大学，２００５年６月．［２８］王雪莲，赵瑞莲，李立健．一种用丁测试数据生成的动态程序切片算法．计算机应用，２００５年６月．［２９］李必信，方祥圣，袁海，郑国梁．一种基丁程序切片技术的软件测试方法．计算机科学，２００ｌ，Ｖ０１．２８．［３０］刘勇，曾明．基于数据流的软件测试序列自动生成技术研究．微电子学与计算机．２００５，２２（５）．［３１］Ｈ．Ａｇｒａｗａｌ，Ｊ．Ｒ．Ｈｏｒｇａｎ．１９９０，ＤｙｎａｍｉｃＰｒｏｇｒａｍＳｌｉｃｉｎｇ．ＳＩＧＰＬＡＮＮＯｔｉｃｅｓ，６：２４６—２５６．Ｆｏｒｗａｒｄｃｏｍｐｕｔａｔｉｏｎｏｆｄｙｎａｍｉｃｏｎ［３２］Ｂ．Ｋｏｒｅｌ，ＩｎＳ．Ｙａｌａｍａｎｃｈｉｌｉ．ｏｆｔｈｅｐｒｏｇｒａｍｓ１ｉｃｅｓ．Ｐｒｏｃｅｅｄｉｎｇｓ１９９４ＩｎｔｅｒｎａｔｉｏｎａｌＳｙｍｐｏｓｉｕｍＳｏｆｔｗａｒｅＴｅｓｔｉｎｇａｎｄＡｎａｌｙｓｉｓ（ＩＳＳＴＡ），［３３］ＦｒａｎｋＴｉｐ．ＡＳｅａｔｔｌｅ，ｏｆＷａｓｈｉｎｇｔｏｎ，ｓ１ｉｃｉｎｇＡｕｇｕｓｔ，１９９４．ｓｕｒｖｅｙｐｒｏｇｒａｍｔｅｃｈｎｉｑｕｅｓ．ＪｏｕｒｎａｌｏｆＰｒｏｇｒａｍｍｉｎｇＬａｎｇｕａｇｅｓ，１９９５，３（３）：１２１—１８９．［３４］Ａ．Ｂｅｓｚｅｄｅｓ，ＤｙｎａｍｉｃＩｎａｎｄＴ．Ｇｅｒｇｅｌｙ，Ｚｓ．Ｍ．Ｓｚａｂｏ，Ｊ．ＣｓｉｒｉｋａｎｄＴ．Ｇｙｉｍ’ｏｔｈｙ．ｌａｒｇｅｓｌｉｃｉｎｇｍｅｔｈｏｄｔｈｅｆｏｒｍａｉｎｔｅｎａｎｃｅｏｆＦｉｆｔｈＣｏｎｐｒｏｇｒａｍｓ．ＰｒｏｃｅｅｄｉｎｇｓｏｆＥｕｒｏｐｅａｎＣｏｎｆｅｒｅｎｃｅＭａｒ，２００１，ＳｏｆｔｗａｒｅＭａｉｎｔｅｎａｎｃｅｐｐ．１０５一ｌ１３．Ｒｅｅｎｇｉｎｅｅｒｉｎｇ（ＣＳＭＲ２００１），ＩＥＥＥＣｏｍｐｕｔｅｒＳｏｃｉｅｔｙ，５１河海大学硕十论文参考文献［３５］Ｔ．Ｇｙｉｍｏｔｈｙ，ｆｏｒＡ．Ｂｅｓｚｅｄｅｓ，Ｌｆｏｒｇａｃｓ．ＡｎＥｆｆｉｃｉｅｎｔＲｅｌｅｖａｎｔ１９９９，ＳｌｉｃｉｎｇＭｅｔｈｏｄＤｅｂｕｇｇｉｎｇ．ＳｏｆｔｗａｒｅＥｎｇｉｎｅｅｒｉｎｇＮｏｔｅ，２４（６）：３０３—３２１．ａｎｄＡ１９０ｒｉｔｈｍｓｆｏｒｔｈｅＮｅｘｔ［３６］Ｊ．Ｖｅｒｔｏｍｍｅｎ，ＧｅｎｅｒａｔｉｏｎＣｏｎｆｅｒｅｎｃｅｏｆＢ．Ｖａｎｄｅｒｍｅｕｌｅｎ．ＫｎｏｌｅｄｇｅＴｅｓｔｉｎｇＭｅｔｈｏｄｓＳｙｓｔｅｍｓ．ＭａｎａｇｅｍｅｎｔＴｈｅＦｕｔｕｒｅＢｕｓｉｎｅｓｓＴｅｃｈｎ０１０９ｙ２００４．Ｍａｒｃｈ１２—１３．ＴｅｓｔＤａｔａＧｅｎｅｒａｔｉｏｎ：ＡＳｕｒｖｅｙ．［３７］ＰｈｉｌＭｃＭｉｎｎ．Ｓｅａｒｃｈ—ｂａｓｅｄＳｏｆｔｗａｒｅＶｅｒｉｆｉｃａｔｉｏｎｏｎＳｏｆｔｗａｒｅＴｅｓｔｉｎｇ，ａｎｄＲｅｌｉａｂｉｌｉｔｙ，２００４，１４（２）：１０５—１５６．［３８］ＪｏｎＥｄｖａｒｄｓｓｏｎ．ＡＳｕｒｖｅｙＡｕｔｏｍａｔｉｃＴｅｓｔＤａｔａＧｅｎｅｒａｔｉｏｎ．［３９］王震．软件测试用例自动生成系统研究开发．两安理工大学硕十论文，２００４．儿．［４０］朱菊．软件自动化测试框架ＴＡＦ及其应用．河海大学硕士论文，２００６．５．５２基于路径覆盖的测试用例生成算法研究

作者：

学位授予单位：

李煜河海大学

1.学位论文 杜磊 ICS软件测试过程的定制与实施 2006

软件测试技术是保证软件质量的主要手段之一，而软件测试过程则是软件测试得以有效实施的保证。随着对软件质量的关注，软件测试过程已成为软件工程领域的一个重要分支。软件测试过程采用一系列的思想、技术和工具，达到生产高质量的软件的目的。InterChangeServer(ICS)软件测试过程的定制与实施将软件测试过程理论和实践相结合，为企业提高软件质量，降低开发成本发挥了重要作用。

本文首先介绍了软件测试过程，包括各种测试方法、测试技术、工具、思想、管理手段以及软件测试过程的各个阶段。然后本文介绍了在ICS项目中如何根据企业的需要定制软件测试过程。最后介绍了在软件测试过程实施中面临的问题和解决的办法并给出了ICS软件测试过程的实施方案。本文着重探讨了如何根据企业的自身情况定制软件测试过程，还介绍了软件测试过程实施中所遇到的管理和技术问题，以及解决这些问题的方法和注意事项。在本文中还探讨了如何评估和改进软件测试过程，以及在具体的改进过程中需要怎样操作和注意哪些问题。

ICS软件测试过程以统一软件测试过程(UnitedTestProcess)为主体，结合极限编程(extremeProgramming，XP)中的测试技术，综合使用各种测试工具和管理思想，定制并实现了一个完整的软件测试过程。它的特点是符合ICS的软件测试需要，过程完备、流程清晰、分工明确，是可重复的、已定义的、可度量的。在ICS测试过程的实施中，主要以自动化测试为主，大大缩短了测试时间，降低了测试成本和缺陷的发生率，提高了软件的质量，增加了客户的满意度。

2.会议论文 苏亚 做好软件测试 提高软件质量 2003

本文讨论了软件质量的重要性,分析了软件测试的目的、原则、方法、活动,提出了加强软件测试对提高软件质量的作用.

3.学位论文 熊策 软件质量控制技术的研究与应用 2004

随着计算机应用领域的扩大,软件质量越来越成为国内外工业界和学术界关注的焦点,对软件质量控制技术和方法的研究也成为软件工程领域的一个重要课题.长期以来,我国软件质量都上不去,软件缺乏竞争力.究其根源,缺乏软件开发和维护的正确方法以及忽视软件开发过程的质量控制乃是最为关键的原因.提高国产软件质量,打造民族产业品牌,在信息产业部的这个号召下,已有越来越多的企业和研究机构把精力投入到这方面的科研与实践中来.笔者在这个大的课题中,主要进行了三个方面的研究:如何使用CMM模型实施软件过程改进,提高软件质量;如何利用面向对象方法和RUP框架进行软件开发,控制软件质量;如何在面向对象软件开发中运用软件测试技术,保障软件质量.并在课题的实际开展中,根据需要设计和实现了一个软件质量控制辅助工具.文章分为七部分.第一部分讲述了本课题来源、研究背景及国内外发展现状,指明了课题的具体研究内容.第二部分说明了软件质量的内涵和评价体系,阐述了软件工程的层次结构及其和软件质量的关系,对CMM,OO方法和RUP框架,软件测试这三种在软件质量控制中具有重要作用的技术和方法做了深入的研究.第三部分着眼于探讨CMM的实施策略.先分析国内软件企业实施CMM中普遍遇到的问题,然后结合保网公司的实际情况,提出了相应的CMM的实施策略,详细阐述了CMM2的几个关键过程域活动在具体项目\"银保通\"中的开展,展示了CMM的实施效果,验证了该策略的有效性.第四部分结合实际项目\"银保通\"系统的开发详细阐述了怎样灵活高效的使用OO方法和RUP框架保证项目的成功和软件产品的质量.第五部分在对OO测试技术深入研究的基础上,对\"银保通\"单元测试、集成测试和系统测试中的若干测试策略做了具体分析.第六部分对笔者参与开发的质量控制辅助工具QCAT的设计和实现做了详细的阐述,对其中运用的关键技术做了清晰的说明.第七部分对笔者在软件质量控制方面做的研究和实践进行了总结,并展望了今后的研究方向和工作.

4.期刊论文 张元华.王峻.ZHANG Yuan-hua.WANG Jun 通过软件测试提高航空电台软件质量 -电讯技术2006,46(3)

为了提高软件质量,进行软件测试是一种重要手段.介绍了软件测试的基本流程和方法,并通过实例验证了方法的有效性.

5.学位论文 马志敏 基于风险的软件测试两阶段模型研究 2008

随着信息技术应用的日益增长,计算机软件系统已经渗透到社会的经济、生活、安全等多个方面。人们对软件作用的期望值也越来越高,软件的质量和软件功能的可靠性逐渐成为人们关注的焦点。软件测试作为软件开发过程中保证软件质量非常重要的一个工程阶段,也逐渐被软件开发组织所重视。 根据全面质量管理理论,现代的测试不再是编码后的一个子过程,而是要将测试过程与开发过程并行进行,力争将缺陷控制在开发过程的早期,从而有效缩短开发周期,降低质量风险。

在软件测试的过程中,我们需要投入一定的人力和物力资源。软件开发的经验表明,软件测试需要消耗大量的资源。有些软件项目因为资源分配不合理,造成软件测试不充分或者项目延期,造成严重的后果。因此,科学的测试策略,合理的资源分配方案,是提高测试效率,保证软件质量的重点。 本文从软件测试的研究现状出发,对在资源有限的条件下,如何有效地规划测试工作,更好的保证软件质量这个问题,从以下几个方面展开研究：

一、论文分析并针对已有的基于风险测试模型存在的种种不足,对原有模型进行了改进。在原有模型的风险识别阶段,依据软件质量度量标准,从软件产品本身、用户和过程三个方面考虑,建立模块风险因素指标体系,更加全面地选取风险因素,并结合主成分分析法筛选出主要的风险因素,建立更加客观和合理的模块风险度量指标体系。

二、论文构建了基于风险的软件测试两阶段模型。第一阶段运用已有模型的方法,通过估计软件中各个功能模块的风险相对值,进行优先级排序,并据此分配测试资源,进行首轮探测性测试,得出相关缺陷数据。第二阶段,根据第一阶段所得数据,运用软件可靠性模型G-O模型估计各个模块的总缺陷数,再根据缺陷分布建立资源的最优分配模型,进行第二轮测试,使各个模块剩余缺陷数最少,以达到动态调整测试资源,提高软件可靠性的目的。

三、论文将基于风险的软件测试两阶段模型运用于某外汇交易中心操作风险管理系统的测试过程中,并结合具体的软件系统给出实施步骤,验证该模型的可行性和实用性。

基于风险的软件测试两阶段模型把定性分析和定量分析、软件测试与风险管理科学地结合在一起,在原有基于风险测试模型上进行改进和扩充,是以软件模块的质量风险为主要参考依据来进行测试资源分配的一种改进策略,是促进资源优化配置,提高测试有效性的行之有效的测试策略。

6.学位论文 万邦睿 基于CMMI的软件测试过程度量研究 2007

随着信息技术的迅猛发展，计算机软件已渗透到社会生活的方方面面。与此同时，软件项目规模的不断壮大、功能的增强和复杂度的增加，软件的成本、进度、质量也变得更加难以控制，这使得软件差错的经济代价和社会代价不断上升。因此，如何生产出高质量的软件产品成为软件产业生死攸关的问题。

软件测试作为保证软件质量的一种重要手段，在软件的生命周期中具有十分重要的地位。有研究表明：越早发现软件中存在的问题，开发费用就越低，软件质量越高，软件发布后的维护费用越低。而业界普遍认为，除了软件测试技术以外，一个好的、成熟的软件测试过程能够最大限度的保证软件测试的有效性，进而保证软件产品的质量。

软件度量技术在软件工程领域的研究中占据着重要的地位，它是改进过程的有效途径之一。通过对过程的度量，可以使过程规范化、可视化；通过对度量数据的分析，可以测量出过程的有效性以及存在的问题；通过度量信息跟踪和监督过程状态，能够为过程管理提供决策支持，降低过程承担的风险。可通过在软件测试过程中引入过程度量，保证软件测试过程的有效性，最终实现软件产品质量的保证和提高。因此，对软件测试过程的度量研究具有十分重要的意义。

集成能力成熟度模型CMMI是一个成功的、广泛使用的软件过程改进模型。众所周知，软件测试和软件度量是软件过程中不可分割的一部分，所以CMMI包含了一系列支持软件测试过程改进和软件度量分析的过程域，并且这些过程域在CMMI的连续式表示模型中是允许被软件组织单独实现的。

本文正是运用CMMI各个过程域中对软件测试和软件度量的支持框架、实际指导、过程分析等，结合传统的过程度量方法、技术，对软件测试过程度量进行了研究。本文研究的主要工作集中在以下三个方面：

(1)定义了一个基于CMMI的软件测试过程。按照CMMI开展度量和分析的要求，任何对过程的度量都是建立在清晰的过程定义上的。因此，本文在分析了现有的软件测试过程模型优缺点以及CMMI对软件测试扩展的基础上，定义了一个基于CMMI的软件测试过程。

(2)提出了一个基于CMMI的软件测试过程度量元选取模型。如何有效地选择度量元是研究软件测试过程度量的一个重要方面。本文分析了常见的过程度量建模方法的不足，并根据CMMI提供的要求和原则，建立了一个基于CMMI的软件测试过程度量元选取模型—C-G模型。该模型是以CMMI到GQ(I)M的映射关系作基础，包括了相应的度量定义、剪裁原则和CMMI相关过程域等。本文以需求验证这个应用案例证明了模型的可行性。

(3)提出了一个软件测试过程度量数据分析模型。如何分析应用选取度量元的度量数据是研究软件测试过程度量的另一个重要方面。本文分析了统计过程控制的相关理论和贝叶斯网络的相关理论，在两者结合的基础上，建立了一个软件测试过程度量数据分析模型。定义了该模型的详细执行流程，并以新设计测试用例这个应用案例证明了模型的可行性。

7.期刊论文 陈开颜.王希武.孙会珺.李惠君.赵强 软件质量与软件测试 -河北省科学院学报2004,21(2)

软件测试是软件质量保证的关键步骤,笔者从技术、工具和管理三个角度出述了软件测试对软件质量的影响.

8.学位论文 刘烁 基于UML的CPN模型在软件测试中的应用 2007

软件测试是保证软件质量的重要手段，也是软件开发过程中一项非常重要的工作。一直以来，国内的很多软件企业对于软件测试的重要性缺乏足够的认识，测试水平不高，软件质量无法得到保证。质量有问题的软件会导致无法预测的后果，因而如何保证软件质量以及如何最大限度地提高软件质量就成为一个重要课题。

传统的测试理论与方法并不完全适合用于新兴的面向对象软件系统。随着面向对象分析和面向对象设计的成熟，如何对面向对象软件进行测试是一个非常值得研究的问题，也是测试领域的一个难题。现代测试理论规定软件必须在其生命周期的全过程进行测试，很多测试不能简单地靠手工测试实现，必然会导致自动化测试的产生和应用。

UML在被工业界广泛接受的同时也成为学术界遵循的一种标准建模语言。许多面向对象软件测试的研究都围绕从UML模型构造软件模型开展。研究基于UML模型的软件测试有利于把测试工作提前到软件开发周期的早期进行。但UML模型属于半形式化模型，往往无法自动生成测试用例。而Petri网作为离散系统的建模和分析工具，适合于描述系统中顺序、并发、冲突以及同步等关系，拥有丰富的系统描述手段和系统行为分析技术。将UML模型与Petri网相结合，能够弥补其数学支持的不足。国内已有基于Petri网模型的软件测试研究，但较为少见。

国外有文献提出了CPN模型和UML图表到CPN模型的映射方法，并将其应用于模型检测领域。我们发现CPN模型经过改进也可以运用于面向对象的类测试和簇级测试。

为此，本文主要做了以下几方面的工作：

首先，以基于模型的测试用例的自动化生成为主线，提出了基于UML的CPN模型的测试框架。

其次，在介绍国外文献中的CPN模型和UML图表到CPN模型的映射方法的基础上，针对软件测试的具体需要，对CPN模型做出了相应改进，并在时间准确性方面，进一步完善了映射的算法。

再次，在研究基于状态覆盖准则的基础上，提出了库所-变迁覆盖准则，并介绍了基于此覆盖准则的测试用例生成策略。

最后，构建了自动化测试用例生成工具，工具包括四个部分：模型转化工具、用例生成工具、代码插装工具和信息比较工具。实验内容主要包括使用已实现的工具，从任意包含完整信息的MDL文件中提取有用信息生成对应的CPN模型。实验证明将基于UML的CPN模型引入基于模型的软件测试是可行的。

9.会议论文 齐俊臣.彭道勇.刘春和 重视软件测试提高软件质量与可靠性 2005

随着软、硬件技术的发展，计算机的应用领域越来越厂，而其中软件的功能越来越强大，软件也越来越复杂。这就使保证软件的质量和高可靠性面临巨大的挑战。特别是对于我们导弹武器系统，包括电子化指挥系统、任务规划系统、测发控系统、一气行控制系统等，都用到了大量的软件。软件的微小瑕疵就可能对生命安全、天文数字的巨额财产甚至对造成严重威胁。要提高导弹武器系统的可靠性，必需要提高软件的质量，软件测试是解决软件问题的有效办法。本文对软件测试的必要性和重要性进行了论证,并介绍了软件测试的基本理论和方法。

10.学位论文 章恒翀 软件测试管理系统的研究和实践 2002

现在的软件系统对软件质量的要求越来越高.如何提高软件质量有两个关键因素：过程质量的控制和软件产品本身的质量.在传统的软件测试中,比如V模型,人们只对软件产品本身进行测试,对于过程质量则很少进行管理.这将导致很多软件质量的隐患.在该文中,我们不仅分析了软件测试的基本技术,也根据实际工作情况分析了软件测试的过程.对于软件测试,我们不仅要强调软件产品本身的测试,也要强对软件的生产过程进行监测.在这种情况下,依据软件测试的各种管理模型-W模型、H模型和测试成熟度模型,我们形成了自己的测试体系.这种体系以W模型为基础,并结合H模型的反馈原理和TMM的过程控制概念.为了将这种测试体系应用到实现的软件测试中,我们构建了一个软件测试工具-软件测试管理系统.在该系统中,以上述的测试体系为基础,以测试用例和测试缺陷的管理为核心,并加强对角色的权限控制.通过该系统的使用,不仅能够对软件产品本身进行检测.还能够对软件开发过程进行监控,从而更大程度上保证了软件质量.

本文链接：http://d.g.wanfangdata.com.cn/Thesis_Y1267740.aspx

授权使用：东南大学图书馆(wfdndx)，授权号：93a283bd-340f-4a86-a32e-9e0e00fd770d

下载时间：2010年10月13日