已阅读5页,还剩9页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
i 覆盖阵列( , , )can t k v上界的推导 摘 要 软件测试方面的局限性已经严重阻碍了元件化软件产品的发展。 我们希望能够将所有的测试情况很好地构建出来, 通过数学方法做到 尽可能多地测试元件之间的相互关系并节省时间和财力。 覆盖阵列(; , , )ca n t k v是一个nk的矩阵,使得每一个nt的子矩 阵至少包含v个元素中的t个,其中t是矩阵的强度。nt的子矩阵代 表元件之间相互关系集合的子集合。为了进行软件测试,我们主要通 过以下两种方法来构建覆盖阵列:一、通过改进的代数和组合构造, 产生更小的覆盖阵列;二、通过设计一种效率更高的搜索算法,构造 更小的覆盖阵列。 stein 和 lov sz 首次在1和2中使用 stein- lov sz 定理,即贪心 算法, 来研究一些组合覆盖问题。 g rard cohen、 simon litsyn 和 gilles z mor 在2中用这一定理解决了一些编码的问题。stein- lov sz 定理 可以用来进行组合设计中的一些存在性证明, 它比概率方法具有更好 的可构造性。 本文主要通过列举一些例子来详细说明构造覆盖阵列的过程, 并 提供覆盖阵列的一个新上界。 关键词:覆盖阵列、贪心算法、软件测试 ii derivation of upper bound of covering array number ( , , )can t k v abstract a covering array(; , , )ca n t k v is an nk array such that every nt sub- array contains all t- tuples from v symbols at least once, where t is the strength of the array. one application of these objects is to generate software test suites to cover all t- sets of component interactions. methods for construction of covering arrays for software testing have focused on two main areas. the first is finding algorithms to find smaller covering arrays more quickly. the second is refining computational search algorithms to find smaller covering arrays more quickly. in this paper, we examine some new cut- paste techniques for strength the base method, this is augmented annealing. this method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. we present a few examples of specific constructions and provide new bounds for some strength three covering arrays. component- based software development poses many challenges for the software tester. interactions among components are often complex and abundant. components may not be designed with the final product in mind which leaves them prone to unexpected interaction faults. ideally we want to test all possible interactions, but this is usually infeasible either time- wise or cost- wise. we are, therefore, interested in generating test suite that provide coverage of as many interactions as possible. keywords: covering arrays, software test, stein- lov sz theorem 上海交通大学 学位论文原创性声明 本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得 的成果。除文中已经注明引用的内容外,本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名:宋磊 日期:2 0 0 9 年 1 月 1 5 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权上海交 通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密,在 年解密后适用本授权书。 本学位论文属于 不保密。 (请在以上方框内打“” ) 学位论文作者签名:宋磊 指导教师签名:邓大萌 日期:2 0 0 9 年 1 月 1 5 日 日期:2 0 0 9 年 1 月 1 5 日 上海交通大学工程硕士学位论文 第一章 绪论 1 第一章 绪论 1.1 基本介绍 软件测试方面的局限性已经严重阻碍了元件化软件产品的发展。由于元件之间的 相互作用十分复杂,所以并非特定针对某一种产品而设计的元件构建在一起,就容易 产生意想不到的错误。理想状态下,我们希望测试元件之间所有可能的相互关系,但 是这通常会消耗巨大的财力和时间。我们希望能够将所有的测试情况很好地构建出 来,通过数学方法做到尽可能多地测试元件之间的相互关系并节省时间和财力。 在测试软件元件之间相互关系的过程中所遇到的问题普遍存在于农业、 药学和医 学等领域。由于能够借助覆盖阵列和正交矩阵来表达所遇到的上述问题,所以我们把 覆盖阵列和正交矩阵作为主要的组合对象。而本文主要讨论覆盖阵列,我们先给出一 些定义,然后阐述为何覆盖阵列能够表达软件元件之间的相互关系,并介绍覆盖阵列 在软件测试当中的应用。 1.2 覆盖阵列 覆盖阵列( ; , , )ca n t k v 是一个nk的矩阵,使得每一个nt的子矩阵至少包含 v个元素中的t个元素至少次,其中t是矩阵的强度。当n未知时,覆盖阵列表达为 ( , , )ca t k v ,如果1 =,我们忽略下标,用(; , , )ca n t k v表达覆盖阵列。用( , , )can t k v 代表能够生成覆盖阵列(; , , )ca n t k v的最小的行数,例如(2,5,3)11can=6。 在软件测试中,k代表元件的种类或数量,每个元件存在v种配置,所有的测试 结果可以通过一个nk的矩阵表达,每一组代表一个测试情况。每一列代表一种元 上海交通大学工程硕士学位论文 第一章 绪论 2 件,列向量中的数值代表一种特定配置。如表 1.1 所示,每一列向量都代表一种元件, 每一行向量代表发生在这种元件上所有可能的测试结果。 表 1.1 软件测试实例中,表达元件相互关系的所有测试结果 raid 操作系统 存储设置 硬盘接口 raid 操作系统 存储设置 硬盘接口 raid5 novell 128mb u 160- sata raid1 linux 64mb u 320 raid5 novell 64mb u 320 raid5 novell 256mb u 160- scsi raid1 novell 256mb u 320 raid1 linux 256mb u 160- scsi raid1 xp 128mb u 320 raid5 xp 256mb u 320 raid5 linux 256mb u 160- sata raid5 xp 64mb u 160- sata raid1 novell 128mb u 160- scsi raid0 novell 256mb u 160- sata raid0 linux 64mb u 160- sata raid0 xp 256mb u 160- scsi raid0 xp 128mb u 160- sata raid0 linux 128mb u 160- scsi raid1 linux 128mb u 160- sata raid1 xp 64mb u 160- scsi raid0 novell 128mb u 320 raid5 xp 128mb u 160- scsi raid5 linux 64mb u 160- scsi raid0 xp 64mb u 320 raid5 linux 128mb u 320 raid1 novell 64mb u 160- sata raid0 novell 64mb u 160- scsi raid0 linux 256mb u 320 raid1 xp 256mb u 160- sata 在软件系统中,每一种元件可能存在不同数量的配置,我们定义一个nk的矩 阵 12 (; , ,(,.,) k mca n t k v vv代表这种情况(更多了解请参阅7) ,其中 1 k ii vv = =, 每列i从集合 i s中选取元素, ii sv=,nt子矩阵的行至少取t元组的值一次。 构造覆盖阵列的计算搜索方法包括贪心算法和标准的组合搜索方法(例如,模拟 退火算法5,6,7,8,9) 。 模拟退火算法是一种现代启发式算法,实质上是局部搜索法的推广。模拟退火算 法克服了局部搜索方法局部最优的缺点, 但它也同样面临解的表示和邻域结构设计问 题,这要针对具体问题特点进行设计,好的设计方法能使算法只在可行解域内进行搜 索,否则,会扩大搜索空间,增加搜索时间。当所有可能的测试结果数量较少时,相 上海交通大学工程硕士学位论文 第一章 绪论 3 比其他解决方法,模拟退火算法更具优势;但是如果可能的测试结果数量增加以及潜 在解决方法的减少,模拟退火算法可能就会陷入困境或者需要花费相当长的运行时 间。总体来说,模拟退火算法是一种通用、高效、健壮、可行的随机近似算法,并且 可以较容易地并行实现以进一步提高运行效率,适合求解大规模组合优化问题,具有 很高的实用价值。 下面详细介绍贪心算法。 1.3 贪心算法 贪心算法是把一个复杂问题分解成一系列较为简单的局部最优选择,每一步选择 都是对当前解的一个扩展,直到获得问题的完整解。贪心算法的典型应用是求解最优 化问题,而且对许多问题都能得到整体最优解,即使不能得到整体最优解,通常也是 最优解的很好近似。 1.3.1 贪心算法的设计思想 作为一种算法设计技术,贪心算法是一种简单有效的方法。贪心算法并不是从整 体优先考虑,他所做出的选择只是在某种意义上的局部最优。如果一个问题的最优解 只能通过蛮力法穷举得到,则贪心算法不失为寻找问题近似最优解的一个较好办法。 贪心算法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,而 且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。这种局部最优选择 并不总能获得整体最优解,但通常能获得近似最优解。从许多可以用贪心算法求解的 问题中看到,这类问题一般具有两个重要性质:最优子结构性质和贪心选择性质。 1.3.2 贪心算法的求解过程 贪心算法通常用来求解最优化问题,它犹如登山一样,一步一步向前推进,从某 一个初始状态出发,根据当前的局部最优策略,以满足约束方程为条件,以使目标函 上海交通大学工程硕士学位论文 第一章 绪论 4 数增长最快(或最慢)为准则,在候选集合中进行一系列的选择,以便尽快构成问题 的可行解。一般来说,用贪心算法求解问题应该考虑如下几个方面: (1)候选集合c:为了构造问题的解决方案,有一个候选集合c作为问题的可 能解,即问题的最终解均取自于候选集合c。 (2)解集合s:随着贪心选择的进行,解集合s不断扩展,直到构成一个满足 问题的完整解。 (3)解决函数:检查解集合s是否构成问题的完整解。 (4)选择函数:即贪心策略,这是贪心算法的关键,它指出哪个候选对象最有 希望构成问题的解,选择函数通常和目标函数有关。 (5)可行函数:检查解集合s中加入一个候选对象是否可行,即解集合s扩展 后是否满足约束条件。 开始时解集合s为空,然后使用选择函数按照某种贪心策略,从候选集合c中选 择一个元素x,用可行函数去判断集合s加入x后是否可行,如果可行,把x合并到 解集合s中,并把它从候选集合c中删去;否则,丢弃x,从候选集合c中根据贪心 策略再选择一个元素,重复上述过程,直到找到一个满足解决函数的完整解。 贪心算法是在少量计算的基础上做出贪心选择而不急于考虑以后的情况, 这样一 步一步扩充解, 每一步均是建立在局部最优解的基础上, 而每一步又都扩大了部分解。 因为每一步所做出的选择仅基于少量的信息,因而贪心法的效率通常很高。 上海交通大学工程硕士学位论文 第二章 覆盖阵列的 can(t,k,v)的上界推导 5 第二章 覆盖阵列( , , )can t k v的上界推导 2.1 贪心算法的理论推导 stein和 lov sz首次在1和2中使用 stein- lov sz定理,即贪心算法,来研究一 些组合覆盖问题。g rard cohen、simon litsyn和 gilles z mor 在2中用这一定理解 决了一些编码的问题。 stein- lov sz 定理可以用来进行组合设计中的一些存在性证明,它比概率方法具 有更好的可构造性。我们介绍一下 stein- lov sz定理。这些证明也可参见1和2。 定理 1.3.1 3 记a为一个nm的(0,1)矩阵,假设每一行至少含有v个1 ,每 一列至多有a个1 ,则存在一个nk的子矩阵c,使得c中不含全零行。其中 /(/ )ln(/ )(1ln )kn amvamva+。 证明:用构造法构造子矩阵c。令 a aa=,记 a a 中两两不相交并且有a个1 的列的最大数目为 a k (或许0 a k =) ,删除这些列及与其相关联的所有的行(即列元 素中1所在的行)后,得到一个 () aa kmk 的矩阵,记为 1a a ,其中 aa knak= 显然,矩阵 1a a 的每列最多有1a个1 (如果超过1a个1 ,那就只能是有 a个1 ,而含有a个1的列已经被删除) 。记 1a a 中两两不相交并且有1a个1 的列的最大数目为 1a k (或许1 0 a k =) ,删除这些列及与其相关联的所有的行(即列 上海交通大学工程硕士学位论文 第二章 覆盖阵列的 can(t,k,v)的上界推导 6 元素中1所在的行)后,得到一个 11 () aaa kmkk 的矩阵,记为 2a a ,其中 11 (1) aa knak = 依此进行,此类操作至多可进行a次。被删除的列的并集构造成我们所期望的子 矩阵c。其中 1 a i i kk = = 算法的第一步已经得到结论 aa knak= 我们定义 1a kn + = 则 1aa a kk k a + = 以此类推 1 ,1,., . ii i kk kia i + = 因为矩阵 1i a中,每一行至少包含v个1 ,每一列至多包含1i个1 ,我们 就得到了 i k 的一个上界 1 (1)(.)(1). iai vkimkkim + 进一步得到 1112 1 11 . (1)(1)(2)1 2 aa iiaaa i ii kkkkkk kkk iaa aa aa + = =+ /(/ )(1/1/(1). 1/2)n amvaa+ 上海交通大学工程硕士学位论文 第二章 覆盖阵列的 can(t,k,v)的上界推导 7 命题得证。 备注 1.3.2 在定理 1.3.1 的证明过程中,利用贪心算法每次只能构造出我们所期 望构造的子矩阵c的一列。每进行一次操作,都有新的一列加入到子矩阵c中,子矩 阵c使得未被覆盖的行的数量达到最大。当所有的行都被覆盖后,操作结束。我们可 以利用 stein- lov sz定理获得一些组合数组的界。 虽然利用stein- lov sz定理得到的结果和利用基本概率方法得到的结果都不能令 人满意,但是基本概率方法是非构造性的证明,而利用贪心算法 stein- lov sz定理得 到的结果更偏重与构造性证明。 2.2 覆盖阵列( , , )can t k v的上界推导 受 stein- lov sz 定理思想的启发,从由所有的测试结果组成的nk矩阵当中取t 列,使这t列尽可能多的覆盖测试结果,其中t列中每个元素从1,2,3,.,v中取值。 在 stein- lov sz 定理中,(/ )(1ln )kmva+,其中 ( ) k t a =, k mv=, k t vv =, 经推导可得 ( )() ( , , )1 ln tk t can t k vv+。 上海交通大学工程硕士学位论文 第三章 全文总结 8 第三章 全文总结 3.1 主要结论 在第六届国际组合会议上, 受 colbourn教授关于覆盖阵列的相关讲座以及邓老师 关于贪心算法的讲座的启发,希望借用贪心算法来解决覆盖阵列的边界问题。本文推 导出覆盖阵列的一个上界。 3.2 研究展望 如何构建覆盖阵列无论在组合数学领域,还是计算机领域都是一个非常具有挑战 性的课题,其在软件测试组的设计领域应用十分广泛,发展也非常迅速。由于目标问 题的规模逐渐增大,计算机搜索技术无论在速度还是准确性上都不能令人感到满意。 虽然组合技术在某些具体实例上展现出其快速和准确的特点,但是缺乏一般性。通过 构造覆盖阵列,能够将目标问题分解成诸多可以解决的小问题。期望通过深入的研究 可以获得更好的覆盖阵列( , , )can t k v的上界。 上海交通大学工程硕士学位论文 附录 1 9 参 考 文 献 1 l.lov se, on the ratio of optimal integral and fractional covers, discrete mathematics, vol.13, 1975, 383- 390. 2 s.k.stein, two combinatorial covering problems, j.combinatorial th., ser.a, vol.16, 1974, 391- 397. 3 g rard cohen, simon litsyn and gilles z mor, on greedy algorithms in coding theory, ieee transactions on information theory, vol.42, no 6(1996), 2053- 2057. 4 m.a.chateauneuf, d.l.kreher, on the state of strength- three covering arrays, j.combin. designs 10(4)(2002)217- 238. 5 d.m. cohen, s.r. dalal, m.l.fredma, g.c. patton, the aetg system: an approach to testing based on combinatorial design, ieee trans. software eng. 23(7)(1997)437- 444. 6 m.b.cohen, c.j.colbourn, p.b.gibbons, w.b.mugridge, con
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 建筑工地安全施工管理
- 申请改进办公设施函(6篇)范文
- 环保处罚案件听证程序介入函4篇范本
- 住宅小区垃圾分类投放管理实施手册
- 电力行业维护部门主管运维管理绩效考核表
- 古兵器修复师绩效衡量表
- 制造业生产技术协调员绩效评定表
- 家装材料进场验收操作手册
- 2026年生产部产能扩容计划审批确认函(7篇)
- 花卉育苗病虫害防治应急处理速查表
- 《油气输送管道工程水平定向钻穿越设计规范》SYT 6968-2021
- 海南省天一联考2025-2026学年上学期期末高二物理试卷(含答案)
- 学堂在线 人工智能 章节测试答案
- 中国协会薪酬管理制度
- 医疗器械使用专业培训证明(5篇)
- 动设备管理制度
- 浪潮存储AS520E操作手册
- 《土地经济学》课程教学大纲
- JC-T2723-2022预应力混凝土实心方桩
- 腹股沟斜疝的护理
- (21)-《计算机组成与结构》-华为-鲲鹏处理器
评论
0/150
提交评论