《一种基于优先级的迭代划分测试方法》由会员分享，可在线阅读，更多相关《一种基于优先级的迭代划分测试方法（17页珍藏版）》请在金锄头文库上搜索。
1、书书书第 卷第 期 年 月计算机学报 收稿日期： ； 在线出版日期： 本课题得到国家自然科学基金（ ， ， ， ） 、 软件新技术与产业化协同创新中心部分资助章晓芳， 女， 年生， 博士， 副教授， 中国计算机学会（ ） 会员， 主要研究方向为软件分析与测试、 错误定位、 强化学习等 ： 章宗长（ 通信作者） ， 男， 年生， 博士， 副教授， 中国计算机学会（ ） 会员， 主要研究方向为部分感知的马尔科夫决策过程、 强化学习、 多 系统等 ： 谢晓园， 女， 年生，博士， 教授， 中国计算机学会（ ） 会员， 主要研究方向为软件分析与测试、 错误定位、 调试、 基于搜索的软件工程等周谊成，
2、男， 年生， 硕士研究生， 主要研究方向为软件工程、 强化学习等一种基于优先级的迭代划分测试方法章晓芳） ，）章宗长）谢晓园）周谊成）（ 苏州大学计算机科学与技术学院江苏 苏州 ）（ 南京大学计算机软件新技术国家重点实验室南京 ）（ 武汉大学软件工程国家重点实验室武汉 ）摘要随机测试和划分测试是两种重要的测试方法， 关于两者在失效检测能力和效率方面的比较一直是软件测试领域的研究热点之一适应性随机测试是对随机测试的一种增强， 通过实现测试用例在输入域上的均匀分布， 提高了随机测试的失效检测能力该文从划分测试出发， 借鉴了均匀分布的思想， 提出了一种基于优先级的迭代划分测试方法（ ， ）首先迭代划
3、分输入域并选取划分后子域的中心点作为待执行的测试用例， 随后采取优先级策略， 将待执行的测试用例分为种不同优先等级并依次执行迭代划分和中心采样仅需要已知输入域的空间信息， 优先级执行则考虑了测试用例的不同空间特性， 上述种操作均仅需要很少的时间开销并力求实现测试用例在输入域上的均匀分布， 以提高失效检测能力该文通过理论分析给出了 检测出对应失效所需测试用例数量的上界， 并通过一系列实验结果表明： 在仅使用接近随机测试时间开销的情况下， 可以获得与适应性随机测试相近甚至更好的失效检测能力， 是一种高效的测试方法关键词软件测试； 划分测试； 随机测试； 适应性随机测试； 测试用例生成； 失效率；犉
4、度量中图法分类号 犇 犗 犐号 犃 狀犃 狆 狆 狉 狅 犪 犮 犺狅 犳 犐 狋 犲 狉 犪 狋 犻 狏 犲犘 犪 狉 狋 犻 狋 犻 狅 狀犜 犲 狊 狋 犻 狀 犵犅 犪 狊 犲 犱狅 狀犘 狉 犻 狅 狉 犻 狋 狔犛 犪 犿 狆 犾 犻 狀 犵 ） ，） ） ） ）（犛 犮 犺 狅 狅 犾 狅 犳犆 狅 犿 狆 狌 狋 犲 狉犛 犮 犻 犲 狀 犮 犲犪 狀 犱犜 犲 犮 犺 狀 狅 犾 狅 犵 狔，犛 狅 狅 犮 犺 狅 狑犝 狀 犻 狏 犲 狉 狊 犻 狋 狔，犛 狌 狕 犺 狅 狌，犑 犻 犪 狀 犵 狊 狌 ）（犛 狋 犪 狋 犲犓 犲 狔犔 犪 犫 狅 狉 犪 狋 狅 狉
5、狔犳 狅 狉犖 狅 狏 犲 犾犛 狅 犳 狋 狑 犪 狉 犲犜 犲 犮 犺 狀 狅 犾 狅 犵 狔，犖 犪 狀 犼 犻 狀 犵犝 狀 犻 狏 犲 狉 狊 犻 狋 狔，犖 犪 狀 犼 犻 狀 犵 ）（犛 狋 犪 狋 犲犓 犲 狔犔 犪 犫 狅 狉 犪 狋 狅 狉 狔狅 犳犛 狅 犳 狋 狑 犪 狉 犲犈 狀 犵 犻 狀 犲 犲 狉 犻 狀 犵，犠 狌 犺 犪 狀犝 狀 犻 狏 犲 狉 狊 犻 狋 狔，犠 狌 犺 犪 狀 ）犃 犫 狊 狋 狉 犪 犮 狋 ， （ ） ， ， ， （ ） ， ， ， ， ， ， 犓 犲 狔 狑 狅 狉 犱 狊 ； ； ； ； ； ；犉 引言软件测试是软件质量保证中的
6、一种重要方法，受到了学术界和工业界的广泛关注在软件测试的过程中， 一项重要的工作是在程序的输入域中选择测试用例， 用于执行待测程序以发现待测程序中的错误由于对软件整个输入域进行穷尽测试往往是不现实的， 因此如何选择尽可能少的测试用例来尽快发现程序错误变得尤为重要在现有的众多测试方法中， 随机测试 （ ， ） 和划分测试（ ， ） 是两种经典的方法随机测试服从某种概率分布（ 通常是均匀分布） ， 从整个输入域中逐个选择测试用例，输入域没有进行任何划分 ； 而划分测试则首先将输入域划分为一定数量的不相交的子域， 再从每个子域中选取一个或多个的测试用例随机测试具有简单有效、 易于理解和实现等优点，
7、然而， 由于随机测试过程中没有利用其他任何有用的信息， 其失效检测能力往往不是很理想 等人提出了适应性随机测试方法（ ， ） ， 是一种改进的随机测试方法， 通过实现测试用例在输入域上的均匀分布， 来提高随机测试的失效检测能力， 但该方法也相应地带来大量额外的计算开销划分测试通常基于相同的功能或属性进行子域的划分， 希望能获得理想的划分方式使得每个子域是同质的， 即同一子域中的所有输入均为正确的输入或导致程序失效的输入在获得有效划分的基础上， 划分测试用于选择测试用例的开销并不大， 然而， 前期的子域划分却需要耗费大量额外的时间开销因此， 关于随机测试和划分测试在失效检测能力和效率方面的比较一
8、直是软件测试领域的研究热点之一， 本文从划分测试出发， 借鉴了 均匀分布的思想， 给出了迭代划分测试方法（ ， ） 的实现框架， 并进一步提出了一种基于优先级的迭代划分测试方法（ ， ）该方法的基本思想是： 通过不断地迭代划分输入域并选取划分后子域的中心点作为待执行的测试用例， 随后采取优先级策略， 将待执行的测试用例分为种不同优先等级并依次执行中心采样和迭代划分仅需要知道输入域的空间信息优先级执行则考虑了待执行测试用例的不同空间特性， 通过约束测试用例执行的先后次序使得测试用例在两轮迭代间的分布更加均匀 的中心采样、 迭代划分和优先级执行这种操作仅需知道输入域的空间信息， 且仅耗费很少的时间
9、开销， 弥补了传统划分测试通常需要知道额外信息或往往耗费大量开销用于划分子域的不足本文的方法力求快速实现测试用例在输入域上的均匀分布， 以提高失效检测能力本文通过理论分析指出： 可以检测出对应失效所需测试用例数量的上界实验结果表明， 方法在仅使用接近 时间开销的情况下， 可以获得与 相近甚至更好的失效检测能力因此， 我们的方法将在失效检测能力和时间开销上获得良好的平衡， 是一种高效的测试方法本文第节将介绍随机测试以及划分测试的相关概念和研究现状； 第节提出 的框架及算法描述， 并给出对应的理论分析结果； 第节通过一系列实验验证理论结果， 并对比多种划分测试以及随机测试方法的失效检测能力和时间开
10、销， 探讨 的适用性； 最后是总结和未来工作相关工作为便于后续讨论， 首先给出一些相关术语的描述和解释定义 失效率（ ）在测试过程中， 假定待测程序的输入域大小为犇， 能够引发失效计算机学报 年的输入域大小为犉， 则失效率为失效输入域占整个输入域的比例， 即犉犇定义 失效模式（ ）指失效输入域的几何特性及其在输入域上的分布情况具体而言， 包括失效输入域的形状、 大小、 方位、 位置等信息 等人总结了种失效模式， 分别为块状模式、 条状模式和点状模式显然， 给定待测程序， 其失效率和失效模式是确定的， 但在测试完成前通常是未知的定义 犉 度量（犉 ）指检测到第个失效时所使用的测试用例数量的期望值
11、犉 可用于表征测试用例集的失效检测能力， 即测试用例集的有效性基于上述定义， 理论上当采用放回策略选择测试用例时， 随机测试的犉 将等于 随机测试随机测试是一种重要的测试方法， 它通常等概率地从输入域中逐个选择测试用例随机测试不仅可以独立使用， 还可以是其他众多测试方法中的重要组成部分随机测试已在工业界得到广泛应用， 特别是在规约说明和源代码不可获得或不完整的场景下， 随机测试仍然可行此外， 随机测试具有重要的统计意义， 可以从理论上分析其失效检测能力， 受到了学术界的广泛关注为了提高随机测试的失效检测能力， 等人提出了 方法该方法的提出基于以下观察： 已有众多实验研究表明引发失效的输入往往聚
12、集在某一连续的区域内， 于是， 不会引发失效的输入也同样形成了一片连续的区域因此， 如果已执行的测试用例未能引发程序失效， 那么接下来新生成的测试用例就应该与所有已执行且未能引发程序失效的测试用例的距离尽可能的远， 从而使生成的测试用例尽可能均匀地分布在整个输入域， 以便快速检测到失效区域固定规模的候选测试用例集的 算法（ ， ） 是基于距离计算的一个经典算法在选择下一个测试用例时，首先随机生成固定数量的候选测试用例， 对于每个候选测试用例犮犼， 找出犮犼与已执行测试用例集中最靠近的测试用例， 获得这两个测试用例之间的距离犱犼拥有最大距离犱犼的候选测试用例将作为下一个待执行的测试用例已有实验结
13、果表明： 相比 ， 在失效检测能力方面有显著的提高然而， 由于 在产生测试用例时需要逐一计算候选集中的测试用例与已执行的测试用例之间的距离， 所以算法的计算开销较大在此基础上， 众多研究学者提出了一系列算法来实现测试用例在输入域上的均匀分布 ， 同时，为降低 算法生成测试用例的计算开销， 提出了一些通用的技术， 例如划分（ ） 技术 、过滤（ ） 技术 、 镜像（ ） 技术 、聚类（ ） 技术 、 遗忘（ ） 技术 等特别地， 研究学者引入划分的思想， 提出了一些基于划分的 算法， 例如基于随机划分的 、 基于二分划分的 、 基于迭代划分的 、 基于格划分 的 算法众多的 实现算法具有不同的失
14、效检测能力、 不同的计算开销和各自的适用场景 等人 通过一系列实验比较了现有的 种 实现算法， 并指出： 基于距离计算的 实现算法，如 的失效检测能力较强， 基于迭代划分的 算法（ ， ） 的计算开销较小 算法的基本思想是： 以二维输入域为例， 首先将输入域划分为狆狆个格子， 每次从可选的格子集合中随机选定一个格子， 并在该格子中随机生成测试用例可选的格子集合不包含已执行的测试用例所在的格子以及与该格子相邻的所有格子当可选的格子集合为空时， 将输入域进一步划分为（狆）（狆） 个格子 通过划分来选定下一个测试用例的可选区域， 避免了大量的距离计算开销， 并保持了较高的失效检测能力 划分测试划分测
15、试首先将输入域分割成多个不相交的子域， 随后在每个子域中选择测试用例在理想的划分情况下， 每个子域中的所有元素或者都能检测出失效， 或者都无法检测出失效， 此时对于每个子域仅需要选择其中任意一个元素进行测试即可然而， 目前没有一种方法能够确保获得这样理想的划分， 除非每个子域中仅包含一个元素， 然而这样的划分测试将退化为穷尽测试 ； 此外， 在划分测试中， 对于输入域的划分往往是需要额外时间开销的， 因此， 需要衡量划分测试的划分代价是否可接受众多研究学者将划分测试和随机测试相比较 等人 提出了一种同等大小同等抽样数的划分测试策略（ ， ） ， 该策略首先将输入域划分为相等大小的子 期章晓芳等
16、：一种基于优先级的迭代划分测试方法域集合， 随后有放回地从每个子域中随机选取相同数量的测试用例当每个输入具有相同的失效概率， 和 选取相同数量的测试用例时， 检测出至少一个失效的概率（ 即犘 ） 将等于或高于 的犘 在此基础上， 等人 提出 了 更 为 通 用 的 比 例 抽 样 策 略 （ ， ） ， 要求从每个子域中有放回地随机选 取的测试 用 例 数 应 与 该 子 域 的 大 小成固定比例， 并证明了 是获得不低于 的犘 的充分必要条件当仅已知输入域的空间信息， 难以进行其他有效划分时， 是一种可行的划分测试方法 等人将划分测试与随机测试相结合， 提出了随机划分策略（ ， ） 该策略首
17、先服从某一概率分布地随机选择一个划分后的子域， 随后从选定的子域中服从等概率分布地随机选择一个测试用例为改进 的失效检测能力， 等人 提出了适应性测试（ ，） 策略， 将待测对象建模为一个受控的马尔科夫链， 通过在线收集测试历史信息来提高失效检测能力然而，的反馈机制需要预先收集测试历史信息且需要耗费大量的计算开销用于测试用例的选择近期， 等人 将与 相结合， 力求实现失效检测能力和时间开销方面的平衡尽管现有众多测试方法， 包括 、 等都试图改进 的失效检测能力， 等人在文献 中给出了一个理论证明： 除非已知失效输入域的位置， 否则即便已知失效输入域的形状、 大小、 方位等信息（ 事实上我们往往
18、无法事先获知这些信息） ， 没有一种测试策略可以保证将其犉 降低至 犉 的 因此， 的 犉 将是最优的测试用例选择策略的失效检测能力的上界已有实验研究结果表明： 的失效检测能力已经非常接近这个最优的上界 基于已有相关工作和分析， 本文从划分测试出发， 借鉴了 均匀分布的思想， 给出了一种迭代划分测试方法， 该方法是一种基于输入域空间信息的迭代测试划分方法， 较之其他基于功能、 路径或风险等信息的划分测试方法， 该方法所需的输入域空间信息容易获得且不需要做额外的预处理， 极大地减小了划分测试在预处理方面的开销同时， 本文的方法借鉴了 均匀分布的思想， 希望能在仅使用接近犚 犜时间开销的基础上，
19、获得与 相近甚至更好的失效检测能力迭代划分测试方法本节首先通过一个简单的例子来展示迭代划分测试方法 的过程， 随后给出 的实现框架，在此基础上提出了 方法， 最后从理论上分析了 和 的失效检测能力 一个例子为便于理解， 假定待测程序的输入域为二维矩形区域， 失效域为块状模式如图（）（） 所示， 首先选择输入域犃的中心点犪作为测试用例执行， 若犪未能命中失效区域， 则依据犪将输入域划分为个子区域犅犅， 分别选取犅犅的中心点犫犫作为测试用例执行； 若犫犫均未能命中失效区域， 则依据犫犫将输入域划分为 个子区域犆犆 ， 分别选取犆犆 的中心点犮犮 作为测试用例执行； 此时， 右上方子区域犆的中心点犮
20、将命中失效区域， 即检测出失效反之， 若犮犮 均未能命中失效区域， 则将迭代进行下一轮划分， 产生 个子区域图次划分产生 个子域的示意图 迭代划分测试方法（犐 犘 犜）由 节的示例可知： 将包含迭代划分、 中心采样和测试用例执行这个主要步骤 首先通过不断地迭代划分输入域并确定性地选取划分后子域的中心点作为待执行的测试用例； 随后基于执行策略， 依次执行待选测试用例当测试用例命中失效区域时， 输出已执行的测试用例数量， 否则将继续进入下一轮的迭代划分和中心点采样直至检测出程计算机学报 年序中的第个失效， 具体如算法所示算法 输入：犿维待测程序的输入域犇， 失效域犉输出： 检测到第个失效时已执行的
21、测试用例数量犉 初始化犉 ， 划分层次数狀选取犇的中心点犪执行，犉 测试用例犪命中失效区域 犉 狀 （ 迭代划分）根据已执行测试用例将当前输入域划分为犿 狀个子域（ 中心采样）采样犿 狀个子域的中心点组成待测用例集犜 犲 狊 狋 犛 犲 狋（ 用例执行）当犜 犲 狊 狋 犛 犲 狋不为空时， 根据执行策略， 依次不放回地选取测试用例狋犜 犲 狊 狋 犛 犲 狋执行，犉 测试用例狋命中失效区域 犉 狀， 转向步其中在步获得犿 狀个子域的中心点组成待测用例集后， 步（ 用例执行） 可以采用多种执行策略，包括基于等概率的执行策略， 如随机执行、 顺序执行等； 以及基于不等概率的执行策略， 如基于优先
22、级的执行等对于给定的待测程序， 在检测到第一个失效前，其失效率是确定不变的， 但在测试过程中，通常是未知的为此， 采用了迭代划分、 中心采样的策略， 通过不断执行测试用例获取关于的信息在犿维空间中，狀次划分并执行新增的犿 狀个测试用例后， 仍无法命中失效区域时， 我们可以推断出该待测程序的失效率一定小于某个值如定理所述定理 假设输入域和失效域均为犿维等距连续空间， 失效率为对于 有： 若进行了狀次划分， 共计执行了狀犻犿犻个测试用例仍无法命中失效域， 则可推断的取值范围为犿 狀证明 可用数学归纳法证明， 详见附录由定理可知， 在犿维空间中，狀次划分并执行新增的犿 狀个测试用例仍未命中失效区域时
23、， 可以推断出犿 狀换而言之， 如果犿 狀， 则最多需要狀犻犿犻个测试用例一定可以命中失效区域 基于优先级的迭代划分测试方法（犐 犘 犜 犘 犛）根据 的实现算法和定理， 我们发现： 只有待新增的犿 狀个测试用例全部被执行通过后， 才可以推断出犿 狀， 否则仍然只能推断出犿（狀）这促使我们考虑：犿 狀个测试用例在执行过程中是否能获得更多关于的信息， 不同的测试用例执行顺序是否会影响到 的失效检测能力基于上述考虑， 我们提出了基于优先级的迭代划分测试方法 ， 通过分析新增的待执行的测试用例的不同空间特性， 将测试用例分为种不同优先等级后， 依次执行， 从而获取了更多关于的信息， 可以得到当前待测
24、程序的失效率的更为细致的推断我们通过一个例子说明 如何实现基于优先级的用例执行， 如图（） 所示： 输入域和失效域均为二维等距连续空间， 假定输入域的面积为前期已进行了次划分， 已执行的个测试用例用符号“ ” 表示，次划分所产生 个子域的中心点组成待执行的测试用例集犮犮 根据这些测试用例的空间特性， 将 个测试用例分为种不同优先等级， 对应集合为犜，犜，犜， 在同一优先级的情况下， 将随机执行其中任意一个测试用例图基于优先级的测试用例执行示意图测试用例优先级取决于该测试用例的执行是否会导致当前可放入的最大失效区域面积（ 记为犛） 产生变化如图（）（） 所示， 在加入个“” 的测试用例前，犛；
25、当放入个“” 的测试用例后， 期章晓芳等：一种基于优先级的迭代划分测试方法犛将变更为 ； 在加入 个“” 的测试用例后，犛将变更为 ； 在加入最后个“” 的测试用例后，犛保持不变由此可见， 在图中，标记为“” 的测试用例属于集合犜， 优先级最高；标记为“” 的测试用例属于集合犜， 优先级次之；标记为“” 的测试用例属于集合犜， 优先级最低可放入的最大失效区域面积犛的不断缩小， 意味着随着测试用例的执行通过， 可以推断出的该待测程序的失效率的取值范围也在不断缩小， 我们可以获得更加精确的关于可能取值的推断为实现 ， 我们首先需要知道如何将待执行测试用例分类， 并分别放入犜，犜，犜集合中如图（）
26、所示， 我们为每一维经过狀次划分后得到的狀个子域的中心点， 即狀个待执行测试用例建立索引， 记为犐犽， ，狀 ， 其中下标犽表示第犽维这样， 在二维空间中， 待执行的狀个测试用例可以用（犻，犻） 唯一标记， 其中犻犐，犻犐观察图可以发现，犜中的元素需同时满足以下两个条件： （） 每一维上的索引不为或最大值（ 即犻，狀且犻，狀） ； （）犻犻 为；犜中的元素满足： 每一维上的索引为或最大值；犜则为狀个待测用例中不属于犜和犜的测试用例构成的集合当从二维空间推广到犿维空间时， 经过狀次划分得到的犿 狀个待测用例可以用（犻，犻， ，犻犿） 唯一标记， 其中犻犽犐犽此时， 可以将犿 狀个待测用例按照如下
27、规则分别放入犜，犜，犜犜中的元素满足： （） 每一维上的索引不为或最大值（ 即犻犽，狀） ； （）犻犼犻犼 为， 其中犼， ，犿犜中的元素满足： 每一维上的索引为或最大值犜为犿 狀个待测用例中不属于犜和犜的测试用例构成的集合基于上述规则， 可分别计算集合犜，犜，犜的大小对于犜而言： 由条件（） 可知， 每一维上的索引犻犽犐犽只能从， ，狀 中取值， 因此当前待选测试用例总个数为（狀）犿由条件（） 可知，测试用例需要满足犿次犻犼犻犼 为的判断， 而犻犼犻犼 取值为或的测试用例数量是相同的， 因此满足条件（） 的测试用例数量只占满足条件（） 的测试用例数量的犿， 即犜中的元素个数为（狀）犿犿对犜而
28、言， 每一维上的索引犻犽犐犽只能从，狀 中取值， 因此，犜中的元素个数为犿而犜中的元素个数则为犿 狀（狀）犿犿犿在已知每个测试用例所从属的集合后， 仅需在 的算法框架上将步（ 用例执行） 调整为基于优先级的用例执行， 算法描述如算法所示算法 输入：犿维待测程序的输入域犇， 失效域犉输出： 检测到第个失效 时 已 执 行的 测 试 用 例 数量犉 步步： 同算法（ ）（ 基于优先级的用例执行）根据优先级高低， 将犿 狀个待测用例分别放入集合犜，犜，犜依次针对集合犜犻（犻，） （犜犻）随机从犜犻选择测试用例狋犼（犼， ，犜犻） 执行犜犻犜犻狋犼 ，犉 测试用例狋犼命中失效区域 犉 狀， 转向步根据
29、 基于优先级执行测试用例的特点， 我们发现在待执行的共计犿 狀个测试用例中， 当执行了优先级最高的犜中的测试用例无法命中失效区域时， 可以推断出该待测程序的失效率一定小于某个值， 如定理所述定理 假设输入域和失效域均为犿维等距连续空间， 失效率为对于 有： 若进行了狀次划分， 共计执行了狀 犻犿犻（狀）犿犿个测试用例仍无法命中失效域， 则可推断的取值范围为犿（狀）（ ）犿证明 可用数学归纳法证明， 详见附录由定理和定理可知， 在犿维空间中， 进行狀次划分后， 需完全执行犿 狀个测试用例， 才可推断的取值范围将从犿（狀）缩小至犿 狀， 而 引入基于优先级执行测试用例， 在执行了（狀）犿犿个测试用
30、例后， 即可推断的取值范围将从犿（狀）缩小至犿（狀）（ ）犿计算机学报 年此外， 中犜的元素个数为（狀）犿犿， 因为（狀）犿犿犿狀犿， 意味着 仅需使用少于本轮待执行测试用例总量犿 狀的犿个测试用例，即可获得关于的取值范围的更细致的推断 犐 犘 犜和犐 犘 犜 犘 犛的理论分析由定理和定理可知， 当待测程序的犿 狀时， 最多需要执行狀犻犿犻个测试用例就可以命中失效区域， 而 最多在执行完第狀次划分的新增测试用例中犜，犜的测试用例后， 就可以命中失效区域当犿（狀）（ ）犿时， 仍然最多需要执行狀犻犿犻个测试用例才可以命中失效区域，而 最多在执行完第狀次划分的新增测试用例中犜的测试用例后， 就可以
31、命中失效区域因此，借助进一步对比 和 在最坏情况下的表现， 有如下分析：（） 对于 ， 令犖 为最坏情况下 所需执行的测试用例数量当犿狀犿（狀）时， 有犿（狀）犿，所以犖 犿（狀）犿犿犿犿（） 对于 ， 令犖 为最坏情况下 所需执行的测试用例数量当犿狀犿（狀）（ ）犿时， 有犿（狀）犿，所以犖 犿（狀）犿犿犿（狀）犿犿犿犿犿犿当犿（狀）（ ）犿犿（狀）时， 有犿 狀犿， 所以犖 犿狀犿狀（）犿犿犿狀犿犿狀犿犿犿狀犿犿令为上述和两 种 情 况 下犖 的 差值， 则犿犿犿犿犿犿犿犿犿犿犿犿犿当犿时，成立综上可得犖 犿犿，犿，犿犿犿，犿烅烄烆由上述分析可知， 已知待测程序的， 和 均存在着检测出对应
32、失效所需测试用例数量的上界当犿时，犖 犖 成立， 因 此 获得更紧的上界相对于随机测试的不确定性， 和 存在上界将为测试过程中测试资源的有效分配提供帮助实验结果与分析本节将给出一系列实验结果， 并围绕以下个研究问题展开分析和对比：问题 在失效检测能力和时间开销方面的表现如何？问题相对于 ， 采用基于优先级的用例执行策略是否能有效地改进算法性能？问题 在高维、 多种失效模式、 真实程序等场景下的适用性如何？ 实验设置本文首先采用仿真实验进行比较分析， 仿真实验将有利于帮助控制实验参数的变化， 涉及的参数主要包括维度、 失效率、 测试方法和实验次数， 逐一说明如下：（） 维度当待测程序有犿个输入参
33、数时， 该程序的输入域为犿维空间在仿真实验中， 将讨论维空间输入域， 并假定均为各维等距的连续空间，即维输入域为正方形，维输入域为正方体（） 失效率即失效输入域占整个输入域的比例， 显然失效率，同时假定， 失效输入域也是各维等距的连续空间（） 测试方法本次实验中将对比以下种测试方法： 有放回的随机测试将作为本实验的基准方法 根据文献 的结果， 的失效检测能力较强， 可作为基于距离计算的 期章晓芳等：一种基于优先级的迭代划分测试方法算法的代表其中， 固定候选集大小为 根据文献 的结果， 的计算开销较小， 可作为基于划分的 算法的代表其中， 划分参数狆初始化为 当仅已知输入域的空间信息时， 仍然可
34、用， 因此选取 作为传统划分测试的代表 要求从每个子域中有放回地随机选取的测试用例数应与该子域的大小成固定比例本次实验中， 为便于比较， 我们在 迭代划分所产生的每个相同大小的子域中随机选取一个测试用例， 而非固定地选取子域的中心点 本文提出的迭代划分、 中心采样的划分测试方法 本文提出的迭代划分、 中心采样和基于优先级的用例执行的划分测试方法（） 实验次数重复一定的实验次数是为了有效避免随机性对实验结果的影响在本文实验中， 涉及两个方面的随机性： 一是失效域位置的随机性， 二是测试用例选择的随机性这里， 我们重复 次实验来克服失效域位置的随机性在给定失效域位置的前提下， 通过重复 次实验来克
35、服测试用例选择的随机性给定上述实验参数配置， 实验过程如下： 首先根据维度产生输入域， 并根据失效率计算并产生失效域在每一次实验中， 随机放置失效域， 根据测试方法逐个选择测试用例当测试用例落入失效域中则认为其检测到失效， 记录当前已执行的测试用例数量犉 当完成规定实验次数时，犉 的平均值记为犉 ， 并记录实验所耗费的总时间本文实验的度量包括有效性度量和效率度量在有效性度量方面， 我们采用将各种方法的犉 与 的犉 的理论值（ 即） 的比值记为犉 来衡量各种方法在失效检测能力上相对 的改进显然，犉 越小， 则该方法相对 的改进越明显在效率度量方面， 我们采用各种方法完成一次失效检测所需的平均时间
36、， 记为犚 狌 狀 狋 犻 犿 犲来比较各种方法的计算开销 问题： 相关方法的分析与比较我们通过实验来比较 ， ， ， ， 和 这种测试方法在犉 和犚 狌 狀 狋 犻 犿 犲这两个度量上的表现实验中参数 维度为维， 失 效 率， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 维度和失效率的选取与文献 相同如图所示， 图（）（） 分别为维到维输入域下，种测试方法的犉 比较， 其中狓轴为 以便于数据的展示，狔轴为犉 类似地，如图所示， 图（）（） 分别为维到维输入域下，种 测 试 方 法 的犚 狌 狀 狋 犻 犿 犲比 较， 其 中狓轴 为 ，狔轴为犚 狌 狀 狋 犻 犿
37、 犲， 单位为 图种测试方法的犉 比较计算机学报 年以 为基准方法， 由图可知： （） 对于 和 ， 两者在犉 方面的表现类似， 在个维度下均有： 当较大时，犉 大于， 随着的减小，犉 逐渐降低、 趋于稳定且小于在给定下， 维度越高， 对应的犉 越大； （） 对于 ， 和 ， 在个维度下均有：犉 在下降至最低点后， 随着的减小，犉 逐渐增大并呈周期性波动此外， 随着维度的增加，犉 越大且波动幅度越大， 在维和维输入域下， 和 的部分犉 将大于 种方法的不同点在于，在给定的情况下， 的犉 最大， 而 的犉 最小以 为基准方法， 由图可知： （） 对于 和 ， 随着的减小，犚 狌 狀 狋 犻 犿
38、犲快速上升较之 ， 尽管在 维输入域下， 的犚 狌 狀 狋 犻 犿 犲有明显减少， 但仍然远远大于 的犚 狌 狀 狋 犻 犿 犲此外， 在维输入域下， 由于 需频繁地划分输入域， 耗费了大量的计算开销， 其犚 狌 狀 狋 犻 犿 犲与 的犚 狌 狀 狋 犻 犿 犲很接近； （） ， 和 三者的犚 狌 狀 狋 犻 犿 犲与 的犚 狌 狀 狋 犻 犿 犲相当， 随着维度的增加、的 减 小， 三 者 的犚 狌 狀 狋 犻 犿 犲将 略 大 于 的犚 狌 狀 狋 犻 犿 犲图种测试方法的犚 狌 狀 狋 犻 犿 犲比较下面我们将 与 、 、 、 逐一分析比较， 并讨论相应的原因（） 与 （ 、 ） 的讨
39、论在犉 方面， 当较大时， 仅需要通过很少次数的划分就可以检测到失效，犉 明显优于 （ 以 、 为例）当较小时， 两者的犉 相近， 的犉 较稳定， 则存在着波动在犚 狌 狀 狋 犻 犿 犲方面， 当较大时， 两者差别不大然而， 随着维度的提高和的减小， 的犚 狌 狀 狋 犻 犿 犲将远远高于 的犚 狌 狀 狋 犻 犿 犲如表所示， 当为 时， 的犚 狌 狀 狋 犻 犿 犲通 常 是 的犚 狌 狀 狋 犻 犿 犲的； 当降低至 时， 在维输入域上的时间性能比 提高了个数量级表犚 狌 狀 狋 犻 犿 犲对比（ 单位： ）失效率测试方法维度 由此可见， 随着的减小， 尽管 能够改进 的失 效 检测
40、能力， 但 是 其时 间 开 销 远 远 大 于 借鉴了 均匀分布的思想， 通过迭代划分、 中心采样和基于优先级的用例执行这个操作实现了输入域上的均匀分布， 然而这项操作均无需耗费过多的计算开销， 其时间开销保持在与 期章晓芳等：一种基于优先级的迭代划分测试方法 同一数量级此外， 当较小时， 存在着进一步改进的可能在没有任何的先验知识的情况下， 从第轮划分开始逐渐增加对的认知， 不断推断出的取值范围的变化当存在的先验知识， 特别是当可预测出的取值很小， 例如当预测出 时， 可以通过相应计算后直接进行第狀次划分， 从而节省了前面狀次划分所耗费的中心点测试用例， 从而改进了当较小时的犉 及犚 狌
41、狀 狋 犻 犿 犲（） 与 的讨论与 相比， 通过确定性的中心点采样以及基于优先级的用例执行， 可以获得较优的犉 这是因为， 在迭代划分子域里中心点采样比子域里随机采样更能确保测试用例在输入域上的均匀分布， 进而改进失效检测能力在计算开销方面，两者犚 狌 狀 狋 犻 犿 犲相当（） 与 的讨论与 相比， 引入基于优先级的用例执行， 可以获得较优的犉 这是因为， 通过指定测试用例的执行序列， 进一步在两轮迭代上通过优先级采样实现了测试用例更均匀的分布在计算开销方面， 由于引入了优先级相关的开销，犚 狌 狀 狋 犻 犿 犲略大于 为进一步验证 能够显著改进 的失效检测能力， 获得与 相近的失效检测
42、能力，我们对 与其他个对比算法即 ， ， ， ， 的犉 展开了犜 检验， 其中，显著性水平值为 双边犜 检验中， 假设犎：犃与犅不存在显著差异； 对应有假设犎：犃与犅存在显著差异当假设犎成立时， 我们将进一步开展单边犜 检验， 假设犎 ：犃不显著地大于犅； 对应有假设犎 ：犃显著地大于犅由于实验数据较多， 这里我们仅呈现了部分假设检验的结果以维输入域下， 等距选取实验中的部分取值为例， 即 ， ， ， ， ， 具 体 检 验 数 据 如 表所 示：当 时， 假设犎 均成立， 即种对比算法的犉 均 显 著 地 大 于 的犉 当 ， 时， ， ， 对应假设犎 成立， 即 ， ， 的犉 均 显 著
43、地 大 于 的犉 ； ， 对应假设犎成立，即 ， 的犉 与 的犉 不存在显著差异当 ， 时， ， 对应假设犎 成立， 即 ， 的犉 均显著地大于 的犉 ； ， ， 对应假设犎成立， 即 ， ， 的犉 与 的犉 不存在显著差异结合实验的数据和假设检验的结果， 我们可以发现： 能够显著改进 的失效检测能力， 并获得与 相近甚至更好的失效检测能力表 犐 犘 犜 犘 犛与对比算法关于犉 狉 犪 狋 犻 狅的犜 检验数据犃犅 （狆 ） （狆 ） 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎：
44、 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 犎： 综合上述比较分析， 我们可以回答问题： 在仅使用接近 时间开销的情况下， 可以达到与 相近甚至更好的失效检测能力， 在有效性和效率之间实现了良好的平衡 问题：犐 犘 犜和犐 犘 犜 犘 犛的分析与比较基于实验中关于 与 的初步结果， 我们通过实验来进一步分析 与 的特性在实验中， 维度为维， 失效率， ， ， ， ， 选取的值为狀， 是希望通过实验验证 与 中关于执行测试用例数与可推断的取值范围的关系如图所示， 图（）（） 分别为维到维输入域下， 与 的犉 比较， 其中狓轴为 ，狔轴为犉 这计算机学报 年图狀时 与
45、 的犉 比较里， 由于的取值为狀， 因此获得的数据点在狓轴上是等距的以 作为基准方法， 由图除了可以获得与图类似的结论外， 还可以获得如下结论：（） 和 在个维度下均存在犉 的最小值以维输入域为例， 当， 时，犉 取到最小值， 为 这是因为， 和 均仅需要执行条测试用例， 即取到当前维输入域的中心点时即可检测到失效同理， 在犿维输入域下， 当犿， 犿时， 仅执行条测试用例即可检测到失效， 此时犉 取到最小值， 为犿（） 在个维度下均有： 每隔固定间隔， 存在 和 的犉 非常接近的汇集点以维输入域为例， 当 ， ， ， 时， 两种方法的犉 非常接近这是因为在维输入域中， 当狀时， 在最坏情况下所
46、需的测试用例数为狀个， 而 基于优先级将待测用例分为犜，犜，犜依次执行， 在最坏情况下所需的测试用例数为犜犜， 即狀个因此， 当实验重复足够次数时， 和 的犉 将非常接近同理， 在犿维输入域下， 当犿 狀， 犿 狀时， 与 的犉 非常接近我们从实验和实验中均发现， 相对于 ， 的犉 较小， 且波动幅度较小为了进一步分析 采用基于优先级的用例执行策略对犉 的影响， 我们开展了实验在实验中， 我们选取维输入域下的特定的进行更为细化的 与 的犉 比较 维输入域下，（）犻，（）犻， ，犻， 共计 个取值；维输入域下，（）犻，（）犻， ，犻， ， 共计 个取值；维输入域下，（）犻，（）犻， ，犻， ，
47、共计 个取值实验结果如图（）（） 所示， 当取到某些特定值时， 的犉 较之 有明显的下降， 从而使得波动幅度变小我们用矩形框在图中标注出这些特殊的数据点， 通过分析这些数据点的取值发现：维输入域下，（），（）；维输入域维下，（），（）；维 输 入 域 下，（），（）这与我们在前文讨论的理论结果一致， 即当取值为犿（狀）（ ）犿（犿为维度，狀为划分次数）时， 在最坏情况下仅需执行优先级最高的犜个测试用例， 即可检测到失效； 而 在最坏情况下则需执行所有新增测试用例， 即犜犜犜个测试用例才可检测到失效因此， 引入了基 期章晓芳等：一种基于优先级的迭代划分测试方法图细化的 与 的犉 比较于优先级的用
48、例执行策略后， 的犉 较之 有明显的下降因此， 我们可以回答问题： 较之 ， 采用基于优先级的用例执行策略能够有效改进算法的犉 问题：犐 犘 犜 犘 犛的适用性分析鉴于前期的实验是面向维输入域的块状失效模式下的实验， 本节将初步探究 的适用性， 主要包括高维、 多种失效模式、 真实程序场景下 的适用性（） 维度的扩展图维输入域下 的犉 针对维输入域的块状失效模式， 失效率狀（狀， ， ） ， 获取 的犉 如图所示与前期实验观察一致， 的犉 在下降至对应的最低点后， 随着的减小，犉 逐渐增大并呈周期性波动此外， 随着维度的增加，相应的犉 越大且波动幅度越大在维和维输入域下， 存在部分犉 大于由此
49、可见， 在高维场景下仍然可用， 当较大时， 仍然保持较高的失效检测能力当较小时，犉 存在着波动因此， 如何改进 在高维的性能， 减小 的波动幅度，将是我们后续的一项重要工作（） 失效模式的扩展为验证 在多种失效模式下的适用性，我们将 分别应用于圆形失效模式和点状失效模式 图圆形失效模式下 的犉 在圆形失效模式下， 维度为维， 失效率狀（狀， ， ） ， 得到 的犉 如图所示与 在块状失效模式下的表现（ 参见 节图） 类似，犉 在下降至对应的最低点后， 随着的减小，犉 逐渐增大并呈周期性波动犉 始终小于， 说明 在圆形失效模式下仍然适用， 仍具备较强的失效检测能力计算机学报 年文献 中指出， 点
50、状失效模式的核心不在于失效区域的大小， 而在于失效区域的数量因此， 本文参考了文献 中的实验参数， 选取维度为维，失效率 ， ， ， 等大小的方形失效 区 域 的 数 量狀， ， ， ， ， ， ， 获得点状失效模式下 的犉 如图所示由图中可以获得两个结论： （） 在相同的取值下， 随着狀的增加，犉 将逐渐增大这是因为，狀的增加将直接导致单个失效区域对应的实际减小， 从而使得犉 逐渐增大； （） 在相同的狀取值下，的取值越小，犉 越大， 这一观察与前期实验结果一致图点状失效模式下 的犉 上述两个实验说明， 在圆形和点状失效模式下仍适用， 且具备较强的失效检测能力（） 真实程序的验证我们从 中选
51、择了两个程序 和 来 分 析 的 适 用 性 的输入为一个浮点数（ 狓） ， 输出为一个浮点数 的输入为两个整数和一个浮点数数组（ 犽， 狀， 犪 狉 狉 ） ，输出为一个浮点数， 即狀维数组中第犽小的数我们采用 工具随机生成变异 ， 通过选择、 简化，最终 共有 个有效变异， 共有个有效变异针对每个有效变异， 重复 次实验并分别记录 和 为检测出该变异所需测试用例的数量令犖 ，犖 分别为 次实验下 和 所需测试用例数量的均值， 令犖 为 所需测试用例数量与 所需测试用例数量的比值， 即犖 犖 犖 显然， 当犖 时， 说明 表现优于 ； 当犖 时，说明 表现劣于 在 的 个 有 效 变 异 中
52、， 存 在 个（ ） 变异， 其对应的犖 ； 存在 个变异， 其对应的犖 在 的个有效变异中， 存在个（ ） 变异， 其对应的犖 ； 仅有个变异对应的犖 为了进一步分析当犖 （ 即 劣于 ） 的情况下 与 的性能差别， 我们引入了在金融领域广泛应用的条件风险价值（ ， ） 是一种风险计量方法， 衡量了当损失超过犞 犪 犚时的平均损失， 具体定义如下：犆 犞 犪 犚（犘 狉（狉犞 犪 犚） ）犈（狉狉犞 犪 犚）显然， 给定风险临界值犞 犪 犚， 当犆 犞 犪 犚值越小时， 平均损失越小， 整体风险越小在本文实验中，犞 犪 犚与犖 相关， 当犖 时， 可认为发生损失，因此犞 犪 犚以 为例， 存
53、在 的变异，其对应的犖 ， 于是有 （犖 ） ，犆 犞 犪 犚（ ）犈（犖 犖 ） 也 就 是 说，存 在 （犖 ） ，即 的概率使得犖 ， 所有符合犖 这一条件的犖 的均值为 如图 所示：狓轴为犖 ，狔轴为落入犖 对应取值范围内的变异的个数在犖 的 个变异中有 个 变 异 对 应 的犖 ， ，犆 犞 犪 犚（ ） ， 这 表 明 尽 管 在 个 变 异 中 的表现较差， 但是 与 的表现差距不大图 的条件风险价值通过分析所有犖 的变异代码， 我们发现： 这些变异导致的失效模式是一些组合的复杂失效模式， 而并非特定的块状、 圆形或点状失效模式，因此， 未能获得较优的失效检测效果尽管如此， 通过
54、上述两个真实程序及其变异版本的验证，可知 在真实应用中是可行的， 且存在着快速检测到失效的可能此外， 失效检测能力与待测程序的特性， 特别是失效模式有着紧密的联系， 然而在真实程序中， 失效 期章晓芳等：一种基于优先级的迭代划分测试方法模式往往是未知且复杂的， 任何一种测试用例生成算法都无法保证在所有失效模式下均表现最优， 因此， 需要进一步探讨 的优势应用场景于是， 我们可以回答问题： 实验结果表明 在高维、 多种失效模式、 真实程序场景下仍然适用， 并存在着进一步优化的可能综合上述个研究问题可知： 在仅使用接近 时间开销的情况下， 可以达到与 相近甚至更好的失效检测能力， 权衡了有效性和效
55、率之间的矛盾， 是一种高效的测试方法同时， 在高维输入域、 不同的失效模式以及真实程序中也表现良好， 具有广泛的适用性此外， 实验观察证实了我们的理论分析结论， 进一步验证了 、 中关于执行测试用例数与可推断的取值范围的关系结论随机测试一直被认为是一种最为简便高效的测试用例生成方法， 但其算法本身难以实现较好的取样均匀性适应性随机测试、 划分测试等方法的提出， 从测试用例分布的角度上实现了更好的均匀性，失效检测能力在不同场景下实现了提升然而， 此类方法均需要在时间开销上有着不同程度的牺牲， 例如， 需要远高于 的生成计算开销； 传统划分测试则需要对输入域进行预处理， 以获得合理的子域划分， 而
56、划分的合理性又往往是决定失效检测能力的关键因素因此， 一直缺少一种可以在失效检测能力与计算开销之间实现良好平衡的测试用例生成方法本文提出了一种基于优先级的迭代划分测试方法 ， 很好地解决了上述关键性问题该方法通过迭代划分、 中心采样和基于优先级的用例执行策略实现了测试用例的生成和执行 结合了上述传统方法的优势， 分别解决了其所具有的局限性较之上述传统方法， 不需要对输入域进行预处理划分， 计算开销极低， 更重要的是 可以实现测试用例的高度均匀分布， 使其具有良好的失效检测能力本文通过理论分析指出了执行测试用例数与可推断的取值范围的关系， 给出了 检测失效所需测试用例数量的上界， 并通过仿真实验
57、表明， 在仅使用接近 时间开销的情况下， 可以达到与 相近甚至更好的失效检测能力未来的研究工作主要包括： （） 已有 方法的改进： 探讨是否有其他测试用例的选择方式， 使得测试用例在两轮迭代间的分布更加均匀同时， 考虑如何提高 在高维空间上性能的稳定性；（） 失效模式的扩展： 在已有块状、 圆形、 点状失效模式的基础上， 考虑组合的复杂失效区域、 失效区域在输入域中的特定位置（ 如边界、 角落、 中心等） 对算法性能的影响； （） 实验规模的扩展： 本文已采用仿真实验和部分真实程序来验证方法的有效性， 后续将增加更多较大规模真实程序的测试， 以进一步验证 方法的有效性参考文献 ， ， ： ，
58、： ， ： ， ： ， ， （） ： ， ， ， ， ， ： ， ， ， （ ） ： ， ， ， （） ： ， ， ， ： ， ， （ ） ： ， ， ，（） ： ， ， ： ， ， （） ： ， ， ， ， ： ， ， ， ， ， ： 计算机学报 年 ， ， ， ， （） ： ， ， ， （） ： ， ， ， ， （） ： ， ， ， ， ， ： ， ， ， ， （） ： ， ， ： ， ， ： ， ， ： ， ， ， ， ， （ ） ： ， ， ， ： ， ， ： ， ， ， ， ： ， ， ， ： ， ， （） ： ， ， ， ， ， （） ： ， ， ， ： ， ， ， ， ， （）
59、： ， ， ， （） ： ， ， ： ， ， （） ： ， ， ， ， ， ： ， ， ， ， ， （） ： ， ， ， ， ， ： ， ， （ ） ： ， ， ， （） ： ， ， ， ， （） ： ， ， ， ： ，： ， ， ， ： ： ， ： ， ， ， （） ： 附录 定理证明定理 假设输入域和失效域均为犿维等距连续空间， 失效率为对于 有： 若进行了狀次划分， 共计执行了狀犻犿犻个测试用例仍无法命中失效域， 则可推断的取值范围为犿 狀证明 令已执行的且尚未命中失效域测试用例数为狋，切分后新增待执行的测试用例数为狋（） 当犿 ，狀 时， 输入域和失效域均为二维平面令当前可放入的最大正
60、方形面积为犛当前狋，狋 ， 若狋更新为 （ ） ， 此时犛 ， 可推断的取值范围为犿 狀 成立（） 假定当犿，狀犽时，狋（犽）， 划分后的子域为犽个， 即狋犽， 若狋更 新 为（犽）犽， 此时犛犽， 即犽成立当狀犽时， 如附图所示， 在完成犽次划分后产生了犃犇四个区域， 各区域面积均为犽， 在犽次划分后， 输入域将划分为犽个子域， 这些子域的中点成为新增待执行的测试用例， 对于 期章晓芳等：一种基于优先级的迭代划分测试方法犃犇区域内而言， 每个区域新增个待执行测试用例，则可以确保每个区域内可放入的最大正方形面积不超过犽接下来我们考虑犃犇四个区域的相连区域（ 即图中虚线框住的十字型区域） 中是否
61、需要放入新的测试用例显然， 无需新增测试用例， 相连区域中能够放入的最大正方形面积已经小于犽因此，狋更新为（犽）犽（犽）时， 可推断的取值范围为（犽）成立附图定理证明示意图（） 假定当犿犽 ， 对于任意狀， 上述定理均成立犿犽 时， 输入域和失效域均为犽 维超立方体当进行狀次划分时， 可以分解为首先对犽 维超立方体进行狀次划分产生犽 狀个子域， 再对最后维进行狀次划分产生狀个子域因此犽 维划分后的子域数量为犽 狀狀，需新增犽 狀狀个待执行测试用例， 以确保能够放入的最大犽 维超立方体体积将小于当前划分的子域体积犽 狀狀因此，狋更新为（犽 ） （犽 ） 狀时， 可 推 断的 取 值 范 围 为（
62、犽 ）狀成立证毕定理 假设输入域和失效域均为犿维等距连续空间， 失效率为对于 有： 若进行了狀次划分， 共计执行了狀 犻犿犻（狀）犿犿个测试用例仍无法命中失效域， 则可推断的取值范围为犿（狀）（ ）犿证明 令已执行的且尚未命中失效域测试用例数为狋，切分后新增待执行的测试用例数为狋， 其中优先级最高的集合犜中的测试用例数为狋（） 当犿，狀时， 输入域和失效域均为二维平面当前狋，狋 ， 其中狋（狀）犿犿（）成立当狋更新为狋狋， 即狋时， 可推断的取值范围为犿（狀）（ ）犿（）（ ） 成立（） 假定当犿，狀犽时，狋（犽），狋犽， 其 中狋（犽）成 立， 当狋更 新 为（犽）狋时， 可推断的取值范围为
63、（犽）（ ）成立当狀犽时， 如附图所示， 在完成犽次划分后， 各区域面积均为犽（ 如图中阴影面积所示） ， 在犽次划分后，输入域将划分为犽个子域， 这些子域的中点成为新增待执行的测试用例，狋（犽）对于犽次划分后产生的（犽）个子域， 以区域犃为例， 每个区域新增“” 测试用例，则可以确保每个区域内可放入的最大正方形面积变更为犽附图定理证明示意图接下来我们考虑与区域犃相邻的共计个区域形成的相连区域（ 即图中虚线框住的十字型区域） 是否需要放入新的测试用例显然， 必须新增“” 测试用例才能确保相连区域中能够放入的最大正方形面积也小于犽于是狋（犽）成立， 当狋更新为犽狋时，可推断的取值范围为犽（ ）成
64、立（） 假定当犿犽 ， 对于任意狀， 上述定理均成立当犿犽 时， 进行狀次划分时， 可以分解为首先对犽 维超立方体进行狀次划分， 有狋（狀）犽 犽 ， 再对最后维进行狀次划分， 有狋 狀， 共需新增狋狋 （狀）犽 犽 个待执行测试用例此时可放入的最大犽 维超立方体体积为犽 维超立方体体积犽 （狀）（ ）犽 乘以最后维进行狀次划分后可放入的最大线段长度狀， 即（犽 ） （狀）（ ）犽 因此， 当狋狀 犻（犽 ） 犻（狀）犽 犽 时， 可推断的取值范围为（犽 ） （狀）（ ）犽 成立证毕计算机学报 年犣 犎 犃 犖 犌犡 犻 犪 狅 犉 犪 狀 犵， ， ， ， ， 犣 犎 犃 犖 犌犣 狅 狀 犵 犣 犺 犪 狀 犵， ， ， ， 犡 犐 犈犡 犻 犪 狅 犢 狌 犪 狀， ， ， ， ， 犣 犎 犗 犝 犢 犻 犆 犺 犲 狀 犵， ， 犅 犪 犮 犽 犵 狉 狅 狌 狀 犱 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， （ ， ， ， ） ， ， ， ， ， ， ， ， ， ， ， ， 期章晓芳等：一种基于优先级的迭代划分测试方法
