软件系统的输入参数存在多种约束条件，且参数之间也存在相互作用，由参数违背约束条件或参数相互作用所引起的软件缺陷可以通过参数组合的方式进行测试，被称作组合测试 (combinatorial interaction testing, CIT)，CIT可以有效减少测试用例的生成数量^[1-4]。组合测试其中一个难题是如何生成尽量小的CIT组合，生成算法按照CIT组合的生成过程可以分为固定算法和进化算法2种。固定算法是从一开始就生成所有的CIT组合的算法，如Hnich等^[5]2006年提出的约束模型；进化算法则是逐步生成CIT组合的算法，如模拟退火算法^[6]、贪心算法^[7-10]等。

对于大多数真实系统来说，CIT过程是受限的，有些参数值的组合在被测系统的约束下无法使用，成为无效用例^{[5, 8, 11]}。在实际系统中约束条件将是组合测试用例生成的关键因素^[2]，越来越多的CIT测试生成研究都开始考虑约束条件^[12-14]。Bryce等^[14]将待测软件中参数或配置的约束条件分为硬约束和软约束2类，硬约束是保证系统运行的必要条件，软约束则是使系统正确行使功能所需要满足的条件。实际运行的系统中，输入数据必须满足硬约束，而可以不必满足软约束。在测试数据生成中，考虑约束限制可以减少无法执行的无效用例比例，从而提高生成效率。现有的处理约束条件方式主要分为2种：一种是在传统的不考虑约束的算法生成CIT组合之后，验证并删除不满足约束的组合；另一种是在数据生成的过程中考虑约束条件的作用，保证生成的数据全部满足约束条件。前者无法避免在生成过程中产生较多无用组合，并且经过删除后的组合难以保证覆盖率；而后者的难点在于如何保证生成的CIT组合全部满足约束条件。

任何系统的约束满足问题都可以通过一定的方式编码为boolean型的一般满足问题^[15]，因此对于约束本身可以将其视作具有True和False这2种水平值的因素。在过去的考虑约束组合的测试生成中，很少考虑不满足约束的情况^[16]。实际系统中，对于不满足约束条件的数据，系统是否能够给出合适的、预期的反馈，是反映系统鲁棒性的重要方面，即使数据满足所有约束条件，也有可能触发特定的隐藏故障，因此两方面的测试都是必要的。侯可佳等^[16]提出基于约束组合的测试方法，将约束本身看作组合对象，应用传统的组合算法OA (orthogonal array)、IPO (in-parameter order)^[17]和OFOT (one factor one time)，对约束的取值进行组合，根据组合结果指导用例生成，并对比了该方法与直接运用组合算法的传统组合测试方法，指出该方法具有生成效率更高的优势。

本文扩展了OA算法和基于IPO的IPOG (IPO generalized) 算法^[18]。对OA算法实现了在2水平下对正交表的自动选择和匹配，克服正交表仅适用于特定列数的缺点。对IPOG算法在纵向扩展时采取随机生成其他无关约束值的方式，增强IPOG算法对多约束组合的覆盖能力。

实验以某在线交易平台的会员注册服务为例，对比3种算法应用于不同约束数量和故障类型时约束组合的生成数量、性能和故障检测能力。结果显示随着约束数量增多，OFOT算法生成的总组合数呈线性增长；OA算法的组合数则主要取决于所应用的正交表，呈阶梯式增长；而IPOG生成的组合数呈指数增长。故障涉及的参数因子数量增多时，3种算法的故障检测能力急剧下降，其中OA和IPO要稍优于OFOT。随着约束数量增多IPOG算法的时间消耗呈指数式增长，OA和OFOT算法的则增长缓慢。同时，OFOT和IPO算法每次生成的约束组合不固定，OA算法则产生固定的约束组合，适合迭代优化。

1 问题定义和背景

定义1  待测软件 (software under test, SUT)^{[1, 15]}。具有n个参数p_i(i=1, 2, …, n) 被称为待测软件，这些参数可能代表系统的配置参数、内部事件或用户输入。参数p_i有a_i个具体的值，构成有限集V_i，有a_i=|V_i|。假设所有参数相互独立，即没有参数依赖于其他参数。

定义2  测试用例 (test case)。n元组t={v₁, v₂, …，v_n|v₁∈V₁, v₂∈V₂, …, v_n∈V_n}被称为测试用例。用T_all表示全部可能的测试用例集，T_all=V₁×V₂×…×V_n。如果T_all覆盖了任意τ个参数的所有取值组合，则称T_all具有τ-way覆盖强度。

定义3  约束 (constraint)。为使得系统正确运行，参数自身或参数之间需要满足的取值要求通常从系统设计、实际应用场景或领域专家中得来，用c表示。C_w={c₁^w, c₂^w, …, c_m^w}被称为约束组合, 其中c_i^w表示在组合C_w中第i个约束的取值。

以某在线交易平台的会员子系统服务为例。该系统负责在线交易领域的会员实体的管理，包括会员注册、激活、状态转换、绑定、认证、转账交易等，是联系多个子系统的核心系统。该子系统的功能以API (application program interface) 的方式与其他子系统交互 (见图 1)。

现考虑对会员系统中注册服务进行测试，则此时注册服务就是一个SUT，每一次调用服务所需要的全部参数值就称为一个测试用例。注册服务涉及到注册参数中登录名称的合法性、注册信息的合理性、会员金融交易流程和状态的合法性等多个约束，并且许多约束都与在线交易领域相关，需要领域专家给出明确的定义。在会员子系统的情境下，往往会遇到输入参数不满足约束条件的情况，为保证系统对各种输入数据都能够正确处理，对于满足和不满足约束的输入都需要进行测试。

传统的组合测试中，通常只考虑对参数取值的组合，根据参数取值组合的覆盖率差异有OFOT、Pairwise、OA和CA (covering array) 以及IPO。OFOT算法首先生成初始用例，再依次选择参数，变更取值，组成新的测试用例。Pairwise算法考察全部可能的用例，每次挑选一个用例，考察其中的两两组合是否在其他用例中都出现过，如果是则可以去掉这个用例。OA算法根据正交表设计各参数的取值，正交表格是覆盖两两参数的全部组合，且每对参数的每种组合出现次数相等的参数表，可以用L_n(a₁^k₁, a₂^k₂, …, a_m^k_m) 表示，其中n表示用例总数，a_i表示水平数，k_i表示具有a_i水平的参数个数。OFOT、Pairwise和OA算法均只有2-way的组合覆盖强度，而CA和IPO算法可以设计成任意τ-way的覆盖强度。软件中多数缺陷都是由2个因子以下的故障产生的，OFOT、OA和IPO算法在这种情况下都有较广泛的应用。

传统组合测试要求参数的水平数必须有限，然而实际系统中，参数可能具有无限或有限但难以穷举的取值空间，例如注册服务的登录名就可以是任意满足注册要求的字符串，如果应用传统组合测试算法会面临计算量过大的问题。与此同时，参数取值往往需要满足一定的约束条件，直接应用组合测试方法将会生成大量无效用例。目前对约束的处理方法主要分为2种：生成用例后删除无效用例和生成过程中避免无效组合。前者仍然会生成大量用例，而后者完全排除了无效组合的生成。在考虑SUT的鲁棒性时，一定量的无效或非法参数取值及取值组合具有更重要的作用，因此也需要生成非法数据。

将组合测试的方法应用到约束条件上，以约束条件的组合求解指导测试用例生成，便形成了约束组合测试方法。约束组合测试可以将无限的参数取值空间限制到有限的取值集合中，从而大大减少计算量。同时它考虑了满足与不满足约束的2种情况，在缩小取值空间时并没有损失测试的覆盖度。

在约束组合测试中，测试人员可以通过设置固定取值的约束来处理硬约束，但对于软约束测试人员仍需要面对2个问题：

1) 如何定义复杂参数的约束。通常对于简单可取值的约束，可以很容易地划分其取值区间，定义需要满足的约束，但是对于复杂的参数，这种方式就不再适用。

2) 对参数的约束如何求解。根据约束取值生成满足要求的参数值即为约束求解。约束求解需要决定以什么样的方式生成参数的值，当面对复杂参数时和跨越多个参数的约束时约束求解更为困难。

2 约束组合测试生成

约束组合测试生成的整个过程分为3步，即约束定义、约束组合和约束求解。

在实际系统中，大多数参数都可以用字符型或数字型来描述，本文称字符型或数字型参数为简单参数，其他以对象形式存在的参数为复杂参数。字符型参数的约束可以统一用正则表达式来描述，数字型参数的约束用数值间大小关系或数轴上的区间来描述。枚举类型是一种特殊的简单参数，可以视作符合特定正则表达式的字符型参数。复杂参数可以看作是由多个复杂参数或者简单参数递归定义而来。

本文将约束分为2类，对参数自身的约束称为单体约束 (single constraint)，对参数之间的约束称为多体约束 (among constraint)。单体约束又可以分为字符型和数字型，例如注册服务中注册名就是一个字符型约束，而证件号就是数字型约束。枚举参数证件类型分为身份证和护照，那么他需要满足的约束就是“PASSPORT|IDENTITY_CARD”这个由枚举值构成的正则表达式。多体约束依据一阶谓词逻辑分为AND型和OR型，AND型约束要求其相关参数的所有单体约束均为真，而OR型约束要求其相关参数中至少有1个的单体约束为真，其他的多体约束可以通过AND和OR的组合来构成，因此不单独分类。例如，注册服务要求注册参数中证件类型为身份证时，证件号码必须是15或18位数字，这就是一个AND型多体约束，需要证件类型和证件号码2个简单参数都满足各自的单体约束。如果要求真实姓名和昵称至少有一个是合法命名方式，这就是一个OR型多体约束。

任何服务都可以通过以上分类方式构造出其参数所具有的约束条件。通过对这些约束条件的组合和求解，可以得到满足特定约束组合要求的测试用例，通过执行这个用例就可能触发该约束组合所覆盖的故障。

在对约束进行定义和求解的过程中，会遇到复杂参数的约束定义问题和约束求解问题。

2.1 复杂参数的约束定义问题

有些复杂的参数，同时拥有简单子参数和复杂子参数，如何定义和处理这种参数的约束，生成对应约束的参数值，是约束定义时面临的主要困难。例如注册参数有银行账户和会员账号2个子参数，银行账户又有开户行和银行账号2个子参数。

对于复杂参数，本文采取约束冒泡的方式来得到它的约束。具体做法是：子参数的单体约束向上冒泡传递给父参数，子参数之间的多体约束直接在父参数中构造，在约束构造的时候从下向上地构造约束。例如在定义上述注册参数的约束时，从它的2个子参数银行账户和会员账号获得它们各自的单体约束，并且必要的话构造它们之间的多体约束。银行账户的单体约束又来自于它的2个子参数开户行和银行账号的约束冒泡。

2.2 约束求解问题

在已知约束取值的情况下，如何生成满足约束取值的参数实例对象，特别是复杂参数的实例对象，是约束求解时的主要困难，直接关系到测试效果。例如针对注册参数，就需要生成注册参数的完整对象，且满足相应的约束组合要求。

本文采用分治的方法处理约束求解问题。具体做法是：对参数自顶向下地搜索约束，并自底向上依次生成参数值，最后合成顶层参数的实例对象。在最底层的约束必然是单体约束，可以根据约束具体内容，利用正则表达式或在符合约束要求的数值空间中随机选取数值来生成对应的参数。

约束求解的另一个困难是如何处理多体约束。多体约束涉及到多个参数的取值，而这些参数自身可能还有单体约束，因此无法与单体约束一样简单生成参数对象，需要单独处理。

多体约束本质是单体约束的组合，据此本文将多体约束利用一阶谓词逻辑分解为符合要求的单体约束的集合，分别对单体约束生成参数对象，最后将所有生成的参数对象收集起来作为多体约束的生成结果。当多体约束的取值为True时，对于AND约束，要求它包含的所有约束都得到满足。对于OR约束，首先从它的约束成员中随机选取若干个 (至少1个) 约束，设置其值为True，设置剩下的约束值为False，据此分别对每个约束成员生成参数对象，收集起来作为该多体约束在True值下的生成结果。当多体约束取值为False时，只需要依据一阶谓词逻辑采取相反的操作即可。多体约束为True时的约束求解算法见图 2。

2.3 约束组合测试算法

在约束组合阶段，本文选取OFOT、OA和IPOG这3种典型算法作为约束组合生成算法，针对2水平的约束生成，对3种算法有所修改。

OFOT算法首先随机生成一组初始的约束组合，然后从这个组合中依次选取约束，以其相反值代替，作为新的约束组合，直到所有约束都被选取过。

以4条约束为例，OFOT算法一种可能的生成结果如表 1所示。

OA算法中传统的正交表对参数数量有严格限制，例如对于10个以下参数、2水平的情况，传统正交表只有L₄(2³)、L₈(2⁷) 和L₁₂(2¹¹) 可供选择。为此，在不损失覆盖度的前提下，本文对传统正交表做了表格选择扩展，以适应不同数量的参数。修改后的OA算法首先根据约束数量查找正交表的库，如果找到完全匹配的正交表则直接使用，否则使用涵盖该约束数量的最小用例的正交表。

正交表选择算法见图 3。

同样以4条约束为例，由于可供选择的正交表没有对应4个参数、2水平的表格，原始的OA算法将无法找到合适的正交表，修改后的OA算法则选取涵盖4条约束的最小正交表，即L₈(2⁷) 表，生成约束组合，如表 2所示。

传统的2-way IPOG算法首先形成所有约束所有取值的两两组合，称为pair集合，选择前2个约束的全组合约束对构成初始的约束组合表，并从pair集合中删除这些约束对。从第3个约束开始，依次使用新约束对约束组合表进行横向扩展和纵向扩展。

在横向扩展时先依次往已有的约束组合中添加新约束的取值，并从pair集合中删除因此而覆盖到的约束对。在2水平情况下已有的约束组合数量一定大于2，从而简化了IPOG算法的实现过程。对于剩下的每一条约束组合，考察新约束的取值，选择加入后覆盖pair中约束对数量最多的新约束取值构成新组合，直到剩余组合考察完毕，则完成横向扩展。

在纵向扩展时首先检查pair集合中有没有由新约束和已有约束组成的约束对，如果没有则说明新约束与已有约束的所有两两组合都已经被覆盖，纵向扩展结束，否则从已有约束组合中选择一组，将pair中未被覆盖的约束值填入替换原值，成为新的约束组合，加入约束组合表；若已考察完所有约束，但pair集合中仍然有未被覆盖的约束对，则对每个约束对依次生成覆盖其约束组合。

在保证2-way覆盖能力的前提下，为提高IPOG覆盖不同的多约束组合值的概率，修改IPOG算法使其在纵向扩展时直接由未被覆盖的约束对生成新的约束组合，不再查询已有约束组合表，在生成新约束组合时除将要被覆盖的约束对以外的其他约束取随机约束值。修改后的算法见图 4。

修改后的IPOG总体生成过程与传统IPOG算法相同，但大大减少了查询已有约束组合的计算量。对于4条约束，修改后的IPOG一种可能的生成结果如表 3所示。

3 实验

本算法针对会员子系统的会员注册服务进行实验。会员子系统是涉及在线交易的会员系统，其注册服务参数实体有10余种属性，每种属性都有取值约束，是非常典型的多约束参数。

3.1 实验设置

实验选择注册参数中9个相对需要关注的属性，定义共计7个单体约束、1个AND多体约束。如表 4所示，其中c4为AND多体约束。

为测试3种算法的用例生成数量和时间，设计2到139(正交表支持的上限) 约束的模拟实验。为测试3种约束组合算法对故障的发现能力，在服务端植入了不同类型的故障，所有故障都是在某种约束模式下有几率触发的故障。用约束编号表示约束，┐表示该约束取False值，植入故障涉及的因子数和要求的约束取值如表 5所示。

在以上定义的基础上，分别选择约束条件和故障类型进行实验配置，每种配置下每个算法的测试生成均执行10遍，每个约束组合生成25个测试用例，取10遍实验的平均值作为实验结果。实验配置如表 6所示。

3.2 实验结果

由模拟实验得到图 5-9。图 5和6显示，随着约束数量增多，3种组合算法的生成的用例数都有所增长，其中IPOG算法在约束数量超过10个之后用例数增长速度大大超过OA算法和OFOT算法，呈指数增长趋势。这也与由不同约束数的实验构成的实验序列 (e1, e2, e3, e6, e7) 相符。原因是IPOG算法首先计算所有约束两两组合的约束对，然后在横向扩展和纵向扩展中逐渐覆盖这些约束对，这个过程对于约束对的覆盖非常低效，存在大量被重复覆盖的约束对，导致覆盖约束对的速度较慢。由于在一定范围内的约束数量都会映射到同一张正交表，故OA算法生成的约束组合数呈阶梯状上升。OFOT算法则是严格按照每个约束依次变换取值的过程进行构造，因此它所产生的约束组合数必然为约束数加1，且是2-way覆盖所需要的组合数的理论下限，任何其他2-way覆盖组合算法均不可能产生比OFOT更少的组合数。由此可见：OFOT算法和OA算法的用例数总体随约束增长呈线性增长趋势，且OFOT增长速度最慢，OA生成约束组合数非常接近OFOT的。OFOT和OA算法比IPOG更适用于大量约束下对生成用例数量有限制 (例如内存限制) 的情形。

图 7-9反映了本实验中3种算法生成约束组合所用的时间，可以看到IPOG耗时呈指数增长，而OFOT和OA算法的耗时则几乎不随约束数量增多而变化，IPOG耗时的增长速度比OFOT和OA的快得多。显而易见的原因是OA和OFOT生成约束组合的数量相仿，而IPOG生成约束组合的数量远远大于OA和OFOT的。但对比图 7和5可见，IPOG在用例增长和用时增长上并不成正比，用时增长要比用例增长更快。造成IPOG消耗时间剧增的另一个原因是算法中约束取值的计算量：OA算法自载入正交表之后只需要查找正交表并代入约束取值，不需要计算具体约束的取值；OFOT算法在生成新的约束组合时只需要计算某一个约束的相反值，所涉及的计算量非常小；但IPOG在扩展时需要搜索pair集合中全部约束对来确定新约束的取值，当约束数量增多时这种计算将会花费大量时间，同时初始化和维护pair集合也需要大量计算。由此可见OA和OFOT算法在性能上也更适合大量约束的情景。

图 10来自实验序列 (e1, e5, e6, e7)，反映了3种算法对触发因子数不同的故障的发现比例。可以看到3种算法都能发现两因子单故障和两因子双故障，且对两因子双故障的发现能力均高于对两因子单故障的发现能力，OA和IPOG的故障发现能力比OFOT的稍高。当故障涉及四因子乃至更多因子时，3种算法的故障发现能力都大为下降，其中IPOG算法和OA算法略优于OFOT算法。可以说三者均不适合多因子故障的情形，但IPOG算法由于可以扩展为任意τ-way的覆盖强度，显然比只有2-way覆盖强度的OA算法和OFOT算法更适用于多因子故障。

图 11来自实验序列 (e3, e4, e6)，反映了同样是四因子故障，当故障落入不同的约束组合中时，3种算法对故障的发现能力也有所不同。可以看到，四因子故障落入不同的具体约束组合时，OA算法和IPOG算法都有一定的概率发现故障，而OFOT算法没有发现d3和d5类型故障，对d2故障的发现能力也不如其他2种算法。如果事先通过别的方式知道待测系统存在某种涉及3个以上因子的故障，2-way强度的OA算法和IPOG算法都是可以接受的选择，考虑到易于扩展到更高强度的覆盖能力，IPOG更为合适。

4 结论

OFOT算法每次只改变一个约束值，每增加一个约束也只增加一个组合，具有计算量少和用例数随约束数量线性增长的性质，适合大量约束的2-way快速测试，能够发现两因子故障，但几乎没有多因子故障发现能力。IPOG算法随着约束数量增多，用例数和消耗时间呈指数增长趋势，保证2-way覆盖能力，能够发现两因子故障，且有一定的多因子故障发现能力，不适用于约束数量巨大的情况。OA算法依据正交表构造约束组合，受到正交表支持列数上限的限制，随着约束数量增多，用例数在一定范围内固定不变且总体呈线性增长趋势，计算量少，能够发现两因子故障，且有一定的多因子故障发现能力，适合大量约束的2-way覆盖测试。此外，在约束数量确定的情况下，OFOT算法和IPOG算法每次均可能产生不同的约束组合表，OA算法则产生相同的束组合表，因此IPOG和OFOT难以迭代优化，而OA算法十分适合迭代优化，预期故障发现能力会有明显提升。可以将启发式搜索算法应用于OA生成约束组合的优化，让用例生成偏向更有可能触发故障的约束组合，提高故障检测能力。本文将传统的组合算法应用到约束上，构造了约束组合算法，使用约束冒泡的方式从约束组合中求解各约束，生成相应参数对象；通过对正交表使用扩展选择算法，实现正交表的自适应选择；通过约束和参数分类将可生成的参数值从枚举型和数值型扩展到了所有字符型、数字型和复杂对象。除此之外，本文对比了OA、IPOG和OFOT这3种典型的组合算法应用到不同数量的约束组合中的差异，以及三者对不同类型的故障的检测能力。