自1946年第1台计算机诞生，人类迈进计算机时代以来，软件系统就作为计算机系统的重要支撑子系统登上了历史舞台，人类自此开始逐步进入信息科学时代。

随着计算机的普及应用，软件系统的重要性不断提高。然而，与计算机系统同一天诞生的软件系统，自始至终都饱受软件缺陷的困扰。计算机发展史上著名的千年虫问题，曾经给全球造成6 000亿美元的损失，人类航天史上也曾经由于软件缺陷造成多次发射或探测任务的失败，如1999年的NASA火星探测器登陆火星表面时失败。而自20世纪80年来以来，商业或军事应用系统中含有的软件缺陷所造成的软件质量问题，给用户/军方带来的损失更是不可估量。

软件缺陷作为主要因素之一，曾经导致了20世纪60年代的软件危机并由此引出了软件工程学科。在21世纪的今天，软件测试的重要性已得到计算机业界的广泛共识。软件测试的概念从早期Myers的“测试是为了发现错误而执行的一个程序或系统的过程”^[1]，即“测试目的是发现软件缺陷”，发展成为今天的IEEE610.12标准中的更为全面的面向软件质量的测试定义：“测试是在规定条件下运行系统或构件的过程，也是分析评估项目质量特性的过程”^[2]，即测试目的是为了确保软件质量。自此，软件测试领域的相关研究也成为软件工程领域的持续研究热点。

随着模块化、构件化、面向对象技术和中间件技术的应用普及，软件系统向着集成化、规模化等方向迅速发展，软件系统复杂性不断上升，软件代码规模日益庞大，复杂软件系统的软件代码规模已经达到了千万行以上级别，软件系统日益表现出开放性、动态性、不可预测性和潜在不安全性等诸多特性，为进行软件测试所设计的测试用例数量呈组合爆炸趋势。软件测试的难度与成本在不断快速攀升的同时，软件正面临着严重的信任危机，即可信性危机。

产生软件可信性危机的根源来自软件系统日益表现出的开放性、动态性、不可预测性和潜在不安全性等诸多特性。从系统角度出发，ISO/IEC 15408(信息安全评估准则)认为一个可信的组件，其操作或过程的行为在任意操作条件下是可预测的，并能很好地抵抗由其他应用软件、病毒以及一定的物理干扰造成的破坏^[3]。当前软件工程领域内对软件可信性危机的解决方法也是遵循这样一个基本原则，即意在证明一个软件系统的行为总是与预期一致。由此主旨引申出了几个与软件可信性相关的研究热点，即高可信软件程序语言与可信编程、可信软件开发方法、软件可靠性测试与评估等^[4-7]。

在可信软件开发方法研究领域中，可信软件测试过程的研究是其中的核心内容之一。可信软件测试过程的研究目标旨在研究软件测试的理论与方法，使软件测试过程成为一个可预期的过程，这种可预期的软件测试过程将对软件测试的质量有决定性作用，并进而确保软件质量和软件可信性。

回顾人类近5 000年的科学历史不难发现，在一门学科的基础理论上出现危机之时，就是该学科领域的学者需要反思之日。历史上的科学家们在解决危机时一般都有2个完全不同方向的选择：1)在原有理论基础上进行修补完善；2)返回概念的原点进行重新的描述和探索，寻求变革之道。科学实践证明，在面临重大而深刻的理论危机时，变革往往是解决理论危机的最好方法和必由之路，它有可能开启新兴学科并使人类的科学认识发生跨越式变化。

通过对软件测试可信性追根溯源的系统研究中，发现在软件测试的实践中，一般都假设软件中的潜伏缺陷是有限的。但是无法确认通过有限的测试过程是否能够发现所有的缺陷。其内在原因是有限的测试不一定能够穷尽所有可能的输入状态，也不一定能够穷尽所有可能的执行路径，从而把所有软件缺陷全部挖掘干净，因为在软件中潜伏的缺陷不是静止不变的，为了排除已经发现的缺陷需要修改软件，但在升级软件版本的过程中又可能引入新的潜伏缺陷，这是一个此消彼长的过程，它有可能收敛，也可能发散。这种认知状况导致任何现实可能的测试过程都无法确保发现软件中潜藏的所有缺陷。于是就形成这样一种信念：只要继续测试下去，总有可能发现新的软件缺陷。

这就是说，软件系统的缺陷在理论上是不可被穷尽的，软件测试只能被局限在一个有限的过程内而无法进行到底，真正把软件缺陷全部发现完毕只是一个潜在的不可达的理想目标，而不是现实目标。这样的认识影响了软件测试的可信性概念本身，阻碍了软件可信性危机的解决。因为既然在现实中发现一个软件系统的所有软件缺陷是不可能的，那就根本无法通过软件测试保证软件是没有缺陷的。既然通过软件测试无法保证软件没有缺陷，那么剩余软件缺陷的影响范围和严重性将无法预知，软件系统的质量也不可预知，软件测试的可信性失去了理论上的保障！

在此背景下，笔者认为目前在软件业界面临着一个不可回避的有关软件测试质量的基本科学问题有待研究解决，即通过软件测试，一个软件系统中的软件缺陷发现过程是否可以被穷尽？

众所周知，软件系统的行为可以被抽象为一个用例集合，而用例集合可以通过一个映射变换成为测试用例集合。因此，软件测试可被抽象为这样一个过程，即针对软件系统的构成和行为设计和执行测试用例，并据此发现和处理软件缺陷的过程。同时软件缺陷与测试用例间存在严格对应关系。

由于被测软件系统不是静止不变的，而是在持续不断地演化，与生物在演化方面有一定的相似性。被测软件在其生命周期中为了获取更好的软件质量和适应用户需求的不断变化，其自身在不断演化并产生一系列的软件测试版本，这些软件测试版本带有遗传和变异的特征：新测试版本带有旧测试版本的绝大多数特征——遗传，而外界环境的刺激会给被测软件系统带来变异，这些刺激主要来源于用户方对软件需求的变更或软件测试者在测试过程中所揭示的软件缺陷(实质是不符合既定需求)。

因此，对于上述基本科学问题，利用测试用例集合、测试用例与软件缺陷的关系及其软件测试演化的概念，可进一步描述为：在软件需求固定不变或持续变化的场景下，软件测试版本相应处于不断的演化过程中，假如针对软件测试的投入是足够的和持续不断的，软件测试是否可以穷尽测试用例全集中的所有测试用例，使被测软件系统达到理想的质量状况？

这虽然是一个理论问题，但也是探讨系列工程技术问题的基础。它刻画的是一个理想极限状态，是揭示各种测试方法和技术的共性特征和差异的基础。对这个问题的解答需要分不同情况来讨论：

第1种情况，在用户需求和被测软件功能不变的情况下，由于软件缺陷规模本身是有限的，困难在于测试用例集合的动态变化。要回答这个基本科学问题,其实质是探索是否存在这样的软件测试质量评价函数和测试用例集合动态生成机制，它能够通过有限步操作来解决测试用例集合的可穷尽性问题。具体说就是寻找这样的软件测试质量评价函数P(x)，对于任何规模软件系统的测试用例集合，都严格用非负整数n递增编号,要求P(n)能够保证如下软件缺陷递减条件：1)确认n₀号测试用例集合已经发现了软件缺陷，能够使P(n₀)为真；2)确认测试用例集合动态生成机制能够保证，只要n号测试用例集合已发现软件缺陷，能够使P(n)为真，则生成的下一个n+1号测试用例集合一定可发现软件缺陷，使P(n+1)为真；3)则软件测试过程可在有限步操作之内穷尽所有的软件缺陷；否则软件系统中的软件缺陷将不可能在本测试用例集合动态生成机制中被穷尽。

第2种情况,被测软件在测试过程中需要不断被修改，以克服已发现的软件缺陷，形成新的测试版本。新测试版本主要遗传了老测试版本的基本特征，也带有某些新的变异,可能是一个持续演化过程，将带来软件功能的变化和新软件缺陷的潜入。所以，在研究测试用例集合动态生成机制和软件测试质量评价函数P(x)时，必须考虑被测软件演化因素,在软件测试用例集合中反映出演化前后的差异,这些差异来源于对已发现的软件缺陷的消除，以及在消除软件缺陷过程中有可能潜入的新软件缺陷。当然，为最大限度减少在软件测试版本升级过程中新软件缺陷的潜入，对软件测试版本升级的过程也应该进行严格质量控制。它需要统一反映在P(x)中，不过这不是软件测试者的职责，而是软件开发者的职责，所以本文没有深入展开讨论。

针对第1种情况的问题解决，只需要在有穷域内讨论即可，而针对第2种情况的问题解决，则需要在无穷域内进行讨论，因为持续的软件测试演化使软件缺陷发现过程进入一个无穷过程，无穷理论有助于用有限/无限的开销来判定一个软件测试过程的穷尽性和可信性，数学基础理论中有关无穷的研究成果对本论文的研究将起到关键性作用。因此有必要在本论文中引入无穷理论的最新研究成果，在此基础上再依据软件测试用例集合的形式化模型对本论文提出的科学问题进行深入讨论。

1 3种主要无穷观

人类认识数至少已有30万年的历史,到19世纪末，在实无穷意义下的一种实数概念和理论已基本形成,其间经历了自然数、分数、数字“0”、负数和无理数等5个主要认识阶段,近100多年来对数系的进一步深入认识主要表现在2个方面: 1)继续探索实无穷的可能概念,以最终完成对实数本质的深入认识，建立更简捷的实数概念和理论; 2)通过对实数的组合运用,形成更复杂的数,如复数( 加入虚数) 、狭义数( 加入超复数) 和广义数( 加入向量、张量、矩阵等) ^[8]．

1.1 现有的3种主要无穷观

历史上出现过各种各样的无穷观，主要是3种。前2种是在2300多年前就已出现的相互完全对立的无穷假设，第3种是100多年前才提出的无穷假设，并已形成了完整的理论体系，在现代数学中占据统治地位。

1) 潜无穷观：假设无穷是一个永无终止的增长过程,无穷大不是数,不能参加运算。也就是说无穷只是一种说话方式而已,它表示对任何一个自然数,都能找到一个比它更大的自然数,但决不可能穷举所有的自然数。这就是说潜无穷过程的基本特征是“此外永有”。

2) 统一实无穷观：假设实无穷大是一个惟一存在的特殊数，能够参与运算,它不仅比任何有限数都大,而且不存在比实无穷大更大的数，实无穷大的任何运算结果都不会大于实无穷大,它是能够包容一切增长过程的理论极限。这就是说实无穷过程的基本特征是“此外永无”。

3) 层次实无穷观：层次实无穷观是现行的实无穷观,它假设实无穷过程可以自我完成，实无穷大是一个数，能够参与运算。但又假设实无穷大有无限多的分层,最小的实无穷大是可数无穷$\aleph $₀,更高一级的实无穷大是不可数无穷$\aleph $₁,$\aleph $₁=2^{$\aleph $₀},其他以此类推。可见层次实无穷观中虽然给出了实无穷大数，这些数都可以参与运算，但是与统一实无穷观“此外永无”的无穷主张不同，这些实无穷大仍然具有潜无穷观“此外永有”的基本特征，所以层次实无穷观实际上是潜无穷观和实无穷观的混合物。

总体来看，这3种无穷观都承认需要有无穷概念存在，差别仅仅是无穷大是否是数以及有多少个无穷大数：

潜无穷观认为在正整数域中只有不断增大的自然数([0数类])和一个不可达的潜无穷大符号ω，没有数类质变，也就没有实无穷大∞存在。

统一实无穷观认为除了潜无穷过程(其中没有数类质变)外，还有实无穷过程(其中存在数类质变)，所以在非负整数域中，除有穷的自然数(属于[0数类])外，还有超穷的趋近无穷正整数(属于[ω数类])和一个实无穷大∞。

层次实无穷观认为无穷过程中存在数类质变，所以在非负整数域中，除有穷的自然数([0数类])外，还有超穷的[ω_i数类](i=0,1,...)，[0数类]集合的基数是实无穷大$\aleph $₀，[ω_i数类]集合的基数是实无穷大$\aleph $_i+1，实无穷大∞被分解为一个无穷数列$\aleph $₀，$\aleph $₁，$\aleph $₂，$\aleph $₃，…。这些无穷观反映了在不同数域模型假设中，数域的大小及其基本性质是完全不同的，可以适应不同的应用环境。

1.2 层次无穷理论

康托尔为了把他的层次无穷主张建立在严格的逻辑框架内，成为能够自圆其说的学说，建立了朴素集合论，无穷集合理论是朴素集合论的重要组成部分之一，其要点如下^{[8, 10-12]}：

1) 有穷集合和无穷集合：如果在集合A的元素和集合B的元素之间能够建立一一对应的关系，则称集合A和集合B等势，记作|A|=|B|。如果一个集合能够和它自己的真子集等势,则这个集合称为无穷集合,否则称为有穷集合．

2) 无穷集合的大小关系：规定自然数集合N是最小的无穷集合，称为可数集合，其基数是可数无穷大$\aleph $₀。如果能找到一种一一对应方式证明无穷集合A与自然数集合N等势,则A也是可数集合，其势是可数无穷大$\aleph $₀。如果所有的方式都不能证明A与N等势,则A是更大的无穷集合，称为不可数集合,不可数集的势$\aleph $大于可数集的势$\aleph $₀．康托尔利用对角线法证明单位区间实数集合R1是不可数集合，规定它的势为$\aleph $₁=2^{$\aleph $₀}，并假定在$\aleph $₀和$\aleph $₁之间没有其他无穷集合的势存在(即连续统假设)。这就是说，单位区间实数集合R1是0级不可数集合，利用公式$\aleph $_i+1=2^{$\aleph $_i}还可获得越来越大的高级不可数集合，这些集合的势分别是$\aleph $₂,$\aleph $₃,$\aleph $₄ ...。

3) 超穷数理论：康托尔为了解释他的实无穷理论为什么在没有最大元存在的自然数集合之外(上)，还能够有更大的超穷数存在，引入了序数的3个生成原则和配套的概念及规定，建立了超穷序数理论和超穷基数理论。在自然数中，任一数n既是序数，也是基数，序数和基数可以通过后继操作同步增大。在超穷数中，任一超穷序数n^*有可能是超穷基数，也有可能不是，超穷序数和超穷基数不能通过后继操作同步增大。

超穷数理论的要点是：

① 1生成(延伸)原则： 0是自然数的(即有穷序数)的生成基，1是生成元，从0开始相继+1能够生成所有的自然数(有穷序数)，其中没有最大元出现。自然数既是有穷序数，也是有穷基数，属于[0数类]。

② 2生成(穷竭)原则：规定自然数集合{0,1,2,3,…,n,n+1,…}的基数$\aleph $₀是最小的超穷序数ω₀。以ω₀为生成基继续延伸，ω₀+1，ω₀+2，ω₀+3，…可生成越来越大的超穷序数，其中没有最大元出现，它们全部属于[ω₀数类]。[ω₀数类]中的每一个超穷序数的基数都是$\aleph $₀。

③ 3生成(限制)原则：规定[ω_i数类]中所有超穷序数组成的集合的势$\aleph $_i+1是更大的超穷序数ω_i+1，ω_i+1大于[ω_i数类]中的所有超穷序数，但本身不在[ω_i数类]中(i=0,1,2,3,…)。

2 统一无穷理论研究现状

在何华灿和何智涛共同提出的统一实无穷数域模型假设中，利用数的理想计数器模型，证明了在位数保持一致的情况下(包括有穷位、趋近无穷位和实无穷位)，非负整数的编码和非负小数的编码永远保持一样多，差别仅仅是小数点的位置不同而已。所以，如果按照传统思想认为所有的非负整数总共有∞个，所有的非负小数总共有2^∞个，那么一定有2^∞=∞的关系成立，实无穷大∞惟一存在，并且它不可能再继续增大了。这就是说，在统一实无穷数域模型假设中，所谓的“不可数集合”根本不存在，困扰数学界多年的连续统假设可以排除，由于不可数集合的排除，统一无穷理论也可以作为软件测试可信性理论的重要理论基础使用。^{[9, 12]}

2.1 统一无穷理论要点

1) 计数器的编码规律。根据数的理想计数器模型可归纳出计数器的编码规律如下：

① 穷非负整(小)数只需要用有穷位的编码表示，有穷位的编码只能表示有穷非负整(小)数，不可能越界表示趋近无穷正整(小)数。

② 近无穷正整(小)数需要用趋近无穷位的编码表示，趋近无穷位的编码可表示非负正整(小)数和趋近无穷正整(小)数，不可能越界表示实无穷大(小)。

③ 无穷大∞只能用∞位的特殊编码(1;$\underline {0 \ldots 0} $;$\underline {0 \ldots 0} $)(进位溢出信号)表示，∞位的编码可以表示有穷非负整(小)数、趋近无穷正整(小)数和实无穷大∞(实无穷小δ=1/∞)。对应的编码是∞=(1;$\underline {0 \ldots 0} $;$\underline {0 \ldots 0} $)，δ=(0.$\underline {0 \ldots 0} $;$\underline {0 \ldots 0} $; 1)。

2) 统一数学归纳法。由于潜无穷过程只能停留在[0数类]内不能达到自我完成的状态。而实无穷过程中∞可达，非负整数的生成过程可以跨越[0数类]和[ω数类]直达∞，达到自我完成的状态。所以有可能把局限于有穷自然数范围的数学归纳法进一步与超穷数中的数学归纳法结合，形成统一数学归纳法，其结论不是对任意的自然数n，P(n)为真，而是直接获得在实无穷大时P(∞)为真的结果。

3) 非负整数的生成三原则。为了建立统一无穷理论的公理系统，原则上继承了康托尔生成超穷数的三原则，并进行了必要的修改，作为生成整个非负整数域的原则，其具体内容如下：

① 1生成(延伸)原则：从0开始相继+1生成的所有非负整数都是自然数，其中没有最大元出现，属于[0数类]。生成过程中的自然数集合是一个0级潜无穷开集，用变量符号$\varpi $表示。

② 2生成(穷竭)原则：生成完毕的自然数集合是所有自然数组成的并集，是最小的趋近无穷闭集合，用常量符号ω表示，它是最小的趋近无穷正整数。以ω为生成基继续延伸，可生成越来越大的趋近无穷正整数ω+1，ω+2，ω+3，…，其中没有最大元。趋近无穷正整数既是超穷序数，也是超穷基数，属于[ω数类]。生成过程中的趋近无穷正整数集合是一个1级潜无穷开集，用变量符号∞表示。

③ 3生成(终止)原则：生成完毕的趋近无穷正整数集合是所有自然数和所有趋近无穷正整数组成的并类，规定它是惟一的实无穷真类(实无穷大)∞，所有的集合(数)包含于(小于)∞。

在统一实无穷数域模型中，非负整数是一个封闭域，其中0是最小的非负整数，称为左极限非负整数，它没有前趋，有后继；ω是中极限非负整数，它没有前趋，有后继，是承前启后的非负整数；∞是最大的非负整数，称为右极限非负整数，它没有前趋，也没有后继。$\varpi $和∞是表示开集的符号，可理解为正在不断增大、没有上限的有穷非负整数变量和超穷正整数变量。

4) 无穷编码的不变性原理ICI(infinite codes invariation，ICI)。ICI 原理由∞位计数器生成的编码数仍然是∞个，2^∞=∞。理由如下：

① 个数既可看成是几何点，也可看成是进位制编码，两者一一对应。

②∞个几何点可在一条直线上从头到尾地排列，每一个点可以拥有一个惟一的进位制编码。

③ 于实无穷大∞可达，所以完整的∞位进位制编码可按照计算器的生成顺序从小到大地排列，与直线上的点形成一一对应关系。

于是从编码的角度看∞位的二进制编码共有2^∞个，从几何点的角度看，这些编码能够与∞个整数一一对应。结果必然是2^∞=∞，这是有穷和无穷的本质差别。

5) 非负整数的内蕴性质和排序性质。 有一个定义在非负整数集合上的性质P(x)，它如满足：① P(n₀)为真，② 任意P(n)为真，则P(n+1)一定为真，称P(x)为第2类(排序类)性质。反之，它如满足：① P(n₀)为真，② 任意P(n)为真，P(n+1)不一定为真，称P(x)为第1类(内蕴类)性质。

在涉及非负整数的第1类性质的无穷性时，进入的是一个潜无穷过程，它只能遍历有穷的自然数域，潜无穷大是一个只能无限接近，但永远不可达到的目标。即有穷自然数不可穷尽，潜无穷过程不能自我完成，无法进入超穷的正整数域。

在涉及非负整数的第2类性质的无穷性时，进入的是一个实无穷过程，它可以自我完成，到达无穷大∞。即全部的有穷自然数、趋近无穷自然数和∞都可以自动生成出来。

2.2 统一无穷理论与软件测试可穷尽性研究

统一无穷理论的研究成果为本文的软件测试可穷尽性研究提供了重要的数学基础。ICI原理为可参与数学运算的惟一实无穷大∞提供了理论基础，而基于实无穷大∞可达的统一数学归纳法使得讨论趋于无穷场景下的软件测试可穷尽性有了相应方法支持，即实无穷过程中实无穷大∞具有可达性，在一定条件下可以获得P(∞)为真的结果，可帮助用有限的开销来判定一个软件测试过程的可信度。

在讨论一个无穷过程的性质P(x)，x→∞时，由于人的认识和计算机的操作都只能是有限步的，不能直接去穷尽所有的可能性，所以区分P(x)的性质属于哪一类十分重要：

当P(x)属于第2类(排序类)性质时，可通过有限步操作在理论上穷尽所有的可能性；

当P(x)属于第1类(内蕴类)性质时：

① 果P(x)具有收敛性，则可在有限步操作内、在小于允许失误概率的意义下穷尽所有的可能性；

② 果P(x)发散或者震荡，则不可能穷尽所有的可能性。

所以，如果能够在软件测试质量评价的模型中把软件测试质量评价函数P(x)控制在第2类性质中，就可以利用有限的开销自动获得穷尽所有可能性的效果，判断这个软件测试过程是绝对可信的。如果能够证明P(x)是第1类函数，它能够收敛，而且允许软件有一定的失误概率，那么就可以利用有限开销来判定这个软件是可信的。如果P(x)不收敛，是发散或者震荡的，那么也可以利用有限开销来判定这个软件是不可信的。

3 测试用例集合形式化定义

本节将通过概念剖析，对测试用例集合进行形式化定义，以便于基于统一无穷理论来研究测试用例集合的可穷尽性问题。

依据软件工程理论，软件系统与软件需求规格说明(软件设计说明)之间存在着对应关系。软件需求规格说明(软件设计说明)中描述的软件特征最终在被测软件系统中获得展现。而软件需求规格说明中的软件用例则对软件需求说明中描述的软件特征进行了覆盖(软件设计说明中的说明描述是软件需求规格说明中用例的一个变换，在理论上可构造一一对应关系)。所有软件用例组成的集合形成了软件系统行为空间。软件系统的行为可以被抽象为一个用例集合，而用例集合可以通过一个映射变换成为测试用例集合。

因此，软件测试可被抽象为这样一个过程，即依据软件设计说明或软件需求规格说明，针对软件系统的逻辑构成或系统行为设计测试用例集合，在被测软件上执行测试用例集合，并据此发现和处理软件缺陷的过程，同时软件缺陷与测试用例间存在着对应关系。

软件测试中依据从软件需求转换而来的软件测试需求，将软件用例集合转换成为软件测试用例集合，在被测软件上对期望软件中的软件特征进行覆盖和验证。

为了便于后续的形式化定义^[13]，这里将首先对期望软件和被测软件做出定义。

定义1 期望软件和被测软件。期望软件，记为S，即软件需求和软件设计所描述的软件。

被测软件，记为S′，即编码实现后的软件。

定义2 软件特征。 软件特征来自于软件需求说明或软件设计说明，是对期望软件自身固有的或者所表现出的一个具体特点的描述。

形式化上，软件特征可以被看做是关于期望软件S的一个命题，记作f_s。说明该期望软件具备某个具体特征，并且存在着相对简明的方法判定其命题真值(真/假)，特别是通过有限的测试用例的测试、自动审查或人工评审等方法。

定义3 软件特征域。由期望软件S的具有某些相同性质的特征组成的集合被称作该期望软件的一个软件特征域，记作

式中：f_i表示期望软件S的某个软件特征，N表示非负数集合。

定义4 软件特征集合与软件需求。期望软件S的所有软件特征组成的集合称作期望软件S的软件特征集合，记作Γ_S。

根据软件工程中软件需求的概念，期望软件S的软件特征集合Γ_S是软件需求的一种理论抽象。

期望软件S的软件特征之间存在着相互关系，软件特征之间既可能全部都有关联，也可能只是部分特征之间有关联。

期望软件S的软件特征之间全部都有关联是一种极限状态。在现实中，由于软件规模普遍都比较庞大，期望软件S的软件特征之间基本只是部分特征之间有关联，而在某些软件模块内部的全部软件特征之间可能存在关联。

期望软件S中，显然软件特征之间是有层次关系的。在抽象为集合概念的层面上，可以对这种层次关系进行展平，使所有软件特征以某一种顺序在集合Γ_S中排列。

定义5 软件特征全相关与软件特征部分相关。对于期望软件S的软件特征集合Γ_S或其子集，如果Γ_S或其子集中的每一个子集都与期望软件S的一个用例或程序逻辑路径存在一一对应关系，则称Γ_S或其子集中的软件特征是软件特征全相关的。

例如，期望软件S的软件特征集合Γ_S中有n个软件特征，即{f₁,f₂,f₃,…,f_n}。则Γ_S的所有子集为{},{f₁},{f₂},…,{f₁,f₂},{f₂,f₃},{f₃,f₄},…,{f₁,f₂,f₃,…,f_n-1},{ f₂,f₃,…,f_n-1,f_n},…,{f₁,f₂,f₃,…,f_n}，软件特征集合Γ_S中的软件特征全相关则指其每一个子集都对应惟一的一个用例。

对于期望软件S的软件特征集合Γ_S或其子集，如果Γ_S或其子集中的软件特征不是软件特征全相关的，只有其中的部分软件特征是软件特征全相关的，则称Γ_S或其子集中的软件特征是软件特征部分相关的。

定义6 软件特征集合幂集合。 软件特征集合Γ_S的所有子集作为元素组成的幂集，称作软件特征集合幂集合，记作2^Γ_S。

定理1 当期望软件S的软件特征全相关时，期望软件S的期望行为全集是软件特征集合Γ_S的幂集合2^Γ_S。

证明：对本定理的证明将使用反证法。

当期望软件S的软件特征是软件特征全相关时，依据软件特征全相关定义，则有Γ_S的幂集2^Γ_S的每一个元素都与一个用例存在一一对应关系，幂集2^Γ_S是期望软件S的行为集合。

假设期望软件S的行为集合2^Γ_S不是其期望行为全集，那么必定存在期望软件S的某一个用例TC₁，TC₁与期望软件S中某些软件特征元素的一个并集∪f_i对应，f_i∈Γ_S，但∪f_i却不是软件特征集合幂集合2^Γ_S中一个元素。

由于∪f_i是Γ_S是期望软件S中某些软件特征元素的一个并集并必定是Γ_S的某一个子集，由此推出，软件特征集合幂集合2^Γ_S中并没有包含软件特征集合Γ_S的所有子集，这与幂集定义相矛盾，因此本证明中假设是错误的。

根据反证法，当期望软件S的软件特征全相关时，期望软件S的期望行为全集是软件特征集合幂集合2^Γ_S成立。

推论1 当期望软件S的软件特征部分相关时，期望软件S的期望行为全集是软件特征集合Γ_S幂集合2^Γ_S的一个不完全子集。

证明：略。

在工程实践中，用于描述软件系统输入与输出之间关系的因果图/判定表方法已经间接指明了在极限条件下，软件系统的输入行为全集是其输入条件的幂集。

依据软件工程中的概念，用例是软件工程或系统工程中对系统如何反应外界请求的描述，是一种通过用户的使用场景来获取需求的技术。每个用例提供了一个或多个场景，该场景说明了系统是如何同最终用户或其他系统交互的，也就是谁可以用系统做什么，从而获得一个明确的业务目标。

基于本文定义2、3和4中的软件特征、软件特征域和软件特征集合的概念，基于软件工程中用例的概念内涵，可以说，一个用例描述了软件特征或特征域的某种组合对外界请求的响应，即软件响应请求的能力通过针对软件特征或特征域的某种陈述(命题)表现出来。

抽象来看，一个用例就是一种陈述，也就是一个命题，是针对期望软件S的软件特征或软件特征组合的一个命题。因此得到以下软件用例的定义。

定义7 软件用例。设期望软件S是软件特征全相关的，软件用例是对期望软件S的软件特征集合Γ_S幂集合2^Γ_S某个子集u_i的一个命题，记作C_ui，u_i∈2^Γ_S，Γ_S是期望软件S的软件特征集合。

定义8 软件用例集合与软件需求规格说明。期望软件S的所有软件用例C_ui组成的集合，称为软件用例集合，记为C，即

软件用例集合C形式化定义了期望软件S的行为空间，任何对用户请求的系统响应都是软件用例集合C的一个元素。依据软件需求规格说明的定义，软件用例集合C是软件需求规格说明的一种实例化展开，罗列了所有满足(也包括不满足/违反)需求规格说明的(命题)实例。

依据软件测试理论，软件测试需求来源于软件需求(包括显性的，即明确定义的，和隐含的，即虽没有明确定义，但却是“应当”或必需满足的)，是测试者依据测试委托方要求，对软件需求的重新阐述，也就是说是一种形式变换，在理论上两者是一一对应的。

定义9 软件测试需求。经过一个映射T_R，软件需求Γ_S转换为软件测试需求，记为T_R(Γ_S)。

在理论上Γ_S与 T_R(Γ_S)中的元素是一一对应的，也就是说测试中需要覆盖期望软件S的所有软件需求(软件特征)。但是在某些工程实践场景中，T_R(Γ_S)中的元素与Γ_S中的元素并不需要是满射关系。例如，只需覆盖部分软件需求的回归测试。

在测试设计与实现活动中，测试者依据软件测试需求，参考软件需求规格说明中的软件用例，设计一系列测试用例并试图覆盖软件测试需求。

测试用例是为某个测试目标而编制的一组测试输入、执行条件以及预期结果，以便测试被测软件的某个程序路径或核实是否满足某个特定测试需求。测试用例概念的实质，是通过一个测试输入序列来对一组软件特征进行覆盖来确定其是否满足需求/设计的要求。

由于软件用例集合C形式化预定义了期望软件S的期望行为空间，则在测试设计与实现活动中，测试者依据需要验证的测试需求T_R(Γ_S)，选取2^T_RΓ_S的某个子集u_i′，从软件用例集合C中选取相应的软件用例C_ui，通过一个转换T_D，形成测试用例。

基于以上的分析，得出软件测试用例和软件测试用例集合的定义如下。

定义10 软件测试用例。 依据软件测试需求T_R(Γ_S)的幂集2^T_RΓ_S的某个子集u_i′所设计的软件测试用例是对应软件用例C_ui的一个T_D变换。记作C_ui′，

定义11 软件测试用例集合。 针对软件测试需求T_RΓ_S的幂集2^T_RΓ_S所有子集所设计的软件测试用例C_ui′所组成的集合，称为软件测试用例集合，记为C′，

性质1 当|Γ_S|=|T_RΓ_S|，软件用例集合C中的元素和软件测试用例集合C′中的元素是一一对应的。

证明 显然，根据软件测试用例集合C′的定义，C′中每一个元素C_ui′都是依据2^T_R(Γ_S)中惟一的子集u_i′在2^Γ_S中寻找相应子集u_i所对应惟一元素C_ui变换而来，而|Γ_S|=|T_R(Γ_S)|，u_i和u_i′将配对出现，因此软件用例集合C中的元素和软件测试用例集合C′中的元素是一一对应的成立。

本节的研究中对软件特征与软件用例，软件用例与软件测试用例、软件测试用例与软件缺陷之间的关系进行了形式化表述。

在软件特征集合为Γ_S的情况下，软件用例集合的最大可能规模为2^Γ_S，而软件测试用例集合与软件用例集合中元素存在一一对应关系，软件测试用例集合的最大可能规模也是2^Γ_S，而由于测试过程中，软件缺陷与测试用例之间存在的单映射对应关系(即若存在一个软件缺陷，必有惟一的一个测试用例对应；而一个测试用例可能对应一个软件缺陷，也可能没有对应的软件缺陷存在)，软件缺陷的最大可能规模小于2^Γ_S。

4 软件测试可穷尽性研究

基于以上的研究成果，在讨论本文提出的基本科学问题前，需要对软件测试演化过程和软件特征集合有穷性进行讨论。

软件测试演化过程可分为测试过程中测试版本无演化、测试版本有限次演化和测试版本持续演化3种情况。

初始软件特征集合的有穷性，可分为有穷集合和无穷集合2种情况。由于期望软件S的初始特征集合是通过一个有限次迭代过程所获得的，不存在一个无穷迭代过程，因此不存在初始特征集合是无穷集合情况，即只需考虑初始软件特征集合为有穷集合。

根据以上讨论结果，以下分3种情况来研究本文提出的基本科学问题：

1) 软件测试的理想情况。

在软件测试的理想情况下，软件测试版本无演化，期望软件S的初始特征集合为有穷集合。

基于本文的定义11，由于测试版本无演化，则意味着测试过程中既没有新提出的用户需求，也没有发现需要修复的软件缺陷，测试用例C_u′i执行过程中全部通过。期望软件S的初始特征集合Γ_S为有穷集合，其势|Γ_S| = n，n∈N，N为非负整数集，测试用例集合C′的势|C′| = 2ⁿ，即测试用例集合C′仍然是一个有穷集合。

显然在此情况下，由于软件测试用例集合理论上是一个有穷集合，软件缺陷数量是有限的，理论上测试投入充足可以穷尽此测试用例集合，相应的软件缺陷发现过程也可以终止。

2) 软件测试的现实情况：软件测试版本有限次演化，期望软件S的初始特征集合为有穷集合。

由于测试版本有限次演化，则意味着测试过程既可能由于用户需求增加而增加了新的软件特征，也可能发现了需要修复的软件缺陷，并因此进行了测试版本的更新，在第k个测试版本中，测试用例集合中的测试用例执行全部通过，且无任何新增用户需求，因此不再有新的测试版本产生，软件测试版本演化过程终止。

期望软件S的初始特征集合Γ_S为有穷集合，其势|Γ_S| = n，n∈N，N为非负整数集，初始测试用例集合C′的势|C′| = 2ⁿ。 即初始测试用例集合C′是一个有穷集合。

在测试版本有限次的演化过程中，软件特征集合从初始特征集合Γ_S开始演化，每次的测试版本演化带来新增的软件特征集合△_i(Γ_S)，i∈N，N为非负整数集。依据定理1，相应的新增软件特征集合势的增量为，|△_i(Γ_S)| = m_i，i=1,2,3,…,k。进行有限次变化后的软件特征全域为Γ_S∪△₁(Γ_S)∪△₂(Γ_S)∪△₃(Γ_S)…∪△_k(Γ_S)。假设每次测试版本演化后都进行代表最大工作量的全面测试，则进行一次测试版本演化后的测试用例集合的势为2^n+m₁，而测试演化过程中总的测试用例集合的势为2ⁿ+2^n+m₁。则进行有限k次测试版本演化后，测试演化过程中总的测试用例集合C′^*的势的最大值为

显然，当初始特征集合为有穷集合，软件系统测试版本经过有限k次演化后，测试用例集合C′^*仍然是一个有穷集合，软件缺陷数量仍是有限的，软件测试用例集合在此情况下，理论上测试投入充足是可穷尽的，即投入有穷的成本可穷尽，那么相应的软件缺陷发现过程也可以终止。

3) 软件测试的极限情况：软件测试版本持续演化，期望软件S的初始特征集合为有穷集合。

测试版本持续演化，则意味着测试版本的持续更新和新的软件特征的持续增加，软件测试过程进入了一个无穷过程。

当期望软件S的初始特征集合Γ_S为有穷集合时，其势|Γ_S| = n，n∈N，N为非负整数集，初始测试用例集合C′的势|C′| = 2ⁿ。 即初始测试用例集合C′是一个有穷集合。

在测试版本持续演化过程中，软件特征集合从初始特征集合Γ_S开始演化，每次的测试版本演化带来新增的软件特征集合△_i(Γ_S)，i∈N，N为非负整数集。依据定理1，相应的新增软件特征集合势的增量为，|△_i(Γ_S)| = m_i，i=1,2,3,…,∞。进行持续演化后的软件特征全域为Γ_S∪△₁(Γ_S)∪△₂(Γ_S)∪△₃(Γ_S)…∪△_∞(Γ_S)。假设每次测试版本演化后都进行代表最大工作量的全面测试，则持续测试版本演化后，测试演化过程中总的测试用例集合C′^*的势的最大值为

由于n+m₁+m₂…+m_∞=∞，依据统一无穷理论中的ICI原理，有2^∞=∞成立，则有

这说明，当初始特征集合为有穷集合，测试版本持续演化后，测试用例集合C′^*将演化成为一个无穷集合，其势C′^*是实无穷大∞，相应的软件缺陷数量也是实无穷大∞。

由于人的认识和计算机的操作都只能是有限步的，不能直接去处理无穷的可能性。因此面对测试用例集合是一个无穷集合这样一个问题时，在软件测试过程中，可通过观察软件测试质量评价函数的性质来判定软件测试的可穷尽性。

设软件测试版本持续演化过程中，软件测试版本的质量评价函数为P(T_Sk′)，k=1,2,…,∞。

① P(T_Sk′) 属于第2类(排序类)性质时，可通过有限步操作在理论上穷尽所有的可能性。可利用有限的开销自动获得直达∞效果，从而判断持续演化中的软件测试过程是绝对可信的。

② P(T_Sk′)属于第1类(内蕴类)性质时，

a) 如果P(T_Sk′)具有收敛性，则可在有限步操作内，在小于允许失误概率的意义下获得直达∞效果，可利用有限开销来判定处于持续演化中的软件测试过程是可信的；

b) 如果P(T_Sk′)发散或者震荡，则不可能穷尽C′^*中的所有测试用例，可利用有限开销来判定持续演化中的软件测试过程是不可信的。

依据以上的讨论结果，总结如下：

1) 软件测试的理想情况：测试版本无演化，测试用例集合C′^*是一个有穷集合，测试用例可被穷尽，软件缺陷数量是有限的，软件测试可穷尽。

2) 软件测试的现实情况：测试版本有限次演化，测试用例集合C′^*是一个有穷集合，测试用例可被穷尽，软件缺陷数量是有限的，软件测试可穷尽。

3) 软件测试的极限情况：测试版本持续演化，测试用例集合C′^*是一个无穷集合，软件缺陷数量为无穷大∞，需要借助软件测试质量评价P(T_Sk′)来辅助判定软件测试可信性。

5 对以往测试可穷尽性认识的分析

从本文的研究结果来看，软件测试从理论上可以穷尽其软件缺陷发现过程。但是在实际的软件测试中，总是会有这样的感觉，只要继续进行测试，软件缺陷似乎总是不断出现。换句话说，在传统测试观念中，软件测试中总是能找到新增的测试用例，测试用例是层出不穷的，软件缺陷也是层出不穷的。

1) 理论层面的定性分析。

依据本文研究成果，软件测试中测试用例集合的大小与预先定义的软件特征数量直接相关，预先定义的软件特征数量越多越细致，软件测试中可生成的测试用例则越多，据此可发现的软件缺陷也就越多。软件特征数量的增加使得测试用例集合中测试用例数量的增加呈几何级数方式增长，软件缺陷的增长规模也类似。因此若在测试中不断细化软件特征的定义(这种情况常见于软件需求说明不完整的软件测试中，测试人员对被测软件系统的理解是不断深入的)，显然将获取快速增长的测试用例集合，显然也将依据新的软件特征定义而不断发现新的软件缺陷。

另一个方面，从测试过程来看，一般遵循从单元测试、集成测试到系统测试的几个阶段。由简入繁，自上而下的层次化测试方式占主导模式。单元测试由于代码或单元规模小，若投入测试成本充分，白盒测试中尚有可能覆盖一个软件单元的行为全集，而在集成测试阶段，测试重点转向软件单元间的接口集成，对多个软件单元的软件特征集合并集之幂集的覆盖远远不够充分，造成大量软件缺陷的遗留。而在系统测试阶段，测试时依据软件需求规格说明，但是由于测试的分工，测试也将首先从各个模块入手，其次是模块间组合，最终到系统的整体；或者从软件系统整体核心模块/流程入手，逐步向模块细节深入，这两种系统测试方式都会在某个层面上忽视了对不同模块间特征的组合关系的完整覆盖。这种对完整覆盖的忽视，注定了软件测试中实际覆盖的测试用例集合只是初始测试用例集合C′的一个非常小的子集。

2) 从定量角度对软件缺陷可能规模和软件测试投入的分析。

在工程实践中，以一般的信息管理软件系统规模来看，含有100个软件特征的期望软件S是一个小规模软件，显然这100个软件特征不可能是全相关的而只能是部分相关的。

假设一个期望软件S含有100个软件特征，这100个软件特征分布在5个软件模块中，每个软件模块含有20个软件特征，1/5模块内的软件特征是全相关的，其余模块中软件特征是部分相关的，例如只有10个软件特征是全相关的，这样的模块共有8个。则S的初始测试用例集合的势|C′|≈2²⁰+8×2¹⁰≈1.1E+6。

依据测试实践经验，针对含有100个软件特征的小型软件系统，使用手工测试方式，投入测试成本至多约为4个人月，其中有2个人月测试执行(22天/人月，每天有效工作8 h，每小时输入不同的测试用例约10个)，其他成本为测试需求分析、测试设计和测试总结等环节。测试过程中测试人员实际运行的不同的测试用例约为2×22×8×10=3 520个测试用例，发现的软件缺陷约200-300个。实际投入测试的测试用例集合的势仅为其初始测试用例集合势|^C′的约1/300，差距悬殊。因此手工测试中所投入的测试用例规模远不及与被测软件依据软件特征定义所期望的测试用例全集规模。而若使用更高效率的自动化测试工具来形式化生成测试用例全集，并自动化执行，则有可能达成对软件测试用例集合的测试覆盖。

同时，还可以从软件缺陷规模的角度来分析。软件工程领域有一个经验说法，即“80%的软件缺陷集中在20%的区域中”，这符合“80/20”原则。这个说法也可以换一下阐述角度，即运行期望软件20%的软件特征的幂集所对应的测试用例集合可以发现被测软件80%的软件缺陷。

仍以含有100个特征项的小规模软件系统为例，发现软件系统总缺陷规模的80%所需的测试用例数量为2²⁰ = 1 048 576，为百万量级，而凭经验，随被测软件质量的高低，软件缺陷规模与测试用例规模的比率在1/10~1/100间，即1万到10万量级。而依据以上的讨论，正常投入情况下，测试中只能发现约200~300个软件缺陷，约为实际规模的1/30~1/300，差距也是非常巨大的。这就可以解释为什么在软件测试实践过程，一个较有规模的被测软件，只要持续测试，总能发现新软件缺陷的现象了。并不是软件缺陷数量无限多，而是软件缺陷数量巨大，即使是一个规模不大的软件系统，在正常传统手工测试情况下，即使加倍投入下，也几乎没有可能将软件缺陷全部发现出来。

综合本节的讨论，在软件测试实际过程中，由于传统手工测试方法的局限性，由于软件特征集合规模庞大、软件缺陷规模庞大等因素的影响，在手工测试方法和正常投入的测试成本约束下，软件测试已可能达到软件缺陷的全发现和处理。因此若想达成或趋近于被测软件中软件缺陷的全发现，使用高效率的基于软件特征的测试用例自动生成技术和自动化测试技术将更有可能和实际意义。

同时，由于软件规模日益庞大，其所对应的测试用例集合规模已经是天文数字，即使采用自动化测试用例生成与自动执行，仍需考虑测试用例集合的覆盖策略问题，以节省测试成本。因此需要进一步研究如何在软件测试过程中优选测试用例，以期在有限测试成本中尽快提高软件测试覆盖，确保重要软件缺陷的优先发现。

6 结论

“通过软件测试，一个软件系统中的软件缺陷发现过程是否可以被穷尽？”是软件工程业界面临的一个不可回避的有关软件测试可信性的基本科学问题。本文围绕此科学问题开展研究，获取了以下4个方面的研究成果：

1) 从数的无穷大概念入手，将本文的讨论范围从有穷领域扩展到无穷领域，基于最新的实无穷理论研究成果，获取了利用有限开销来判断无穷软件测试过程可信性的基本方法；

2) 从软件特征定义入手，对软件测试用例集合等相关概念进行了形式化定义，得出了软件特征全相关条件下，期望软件的软件特征、软件测试用例和软件缺陷三者之间的对应关系，该成果为被测软件需投入的测试用例规模和软件缺陷规模的估算提供了理论模型；

3) 基于统一实无穷理论研究成果、统一数学归纳法和测试用例集合形式化定义，证明了在软件测试版本无演化和有限次演化情况下，软件测试用例集合是一个有穷集合，软件缺陷数量是有限的，软件测试过程是可穷尽的；在软件测试极限情况下，软件测试版本持续演化，软件测试用例集合成为一个无穷集合，测试用例数量和软件缺陷数量均为实无穷大∞，软件测试该如何开展的理论问题。

4) 基于本文的上述成果，对软件测试中软件缺陷是无法穷尽的旧有认识进行了剖析，分析了产生此种认识的根源，阐明了在软件测试过程中注重测试用例选择策略以尽快提高软件测试质量的重要性。

本文的一系列研究成果初步回答了困扰软件测试理论界多年的软件测试可穷尽性基本问题，证明了在软件测试的理想和现实情况下软件测试是可被穷尽的；而在软件测试的极限情况下，在被测软件版本持续演化进入一个无穷过程时，可通过新数学归纳法并借助软件测试质量评价函数来软件测试可信性。

科学理论应该走在具体实践的前面！我们相信本文的研究成果将在未来的软件工程实践中有应用价值——随着互联网技术不断发展、网构软件的出现与网构软件系统开放性的增强，软件系统规模将空前增大，远期可能出现超大规模软件系统频繁演化甚至持续高速演化现象，已有出现软件测试极限情况的可能性，因此本文的研究成果可为近期软件测试可信性和远期软件测试可信性研究提供一定的理论支持。