基于约束组合的测试用例生成

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

清华大学辅仁网/2017-07-07

基于约束组合的测试用例生成

白晓颖, 黄军

清华大学计算机科学与技术系, 北京 100084

Case generation by constraints combinatorial testing

BAI Xiaoying, HUANG Jun

Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

摘要:

输出: BibTeX | EndNote (RIS)

摘要系统输入参数常有多种约束条件，且约束之间相互关联。违背约束条件及约束之间的依赖关系，是软件中常见的缺陷。当参数数量多、输入空间大时，组合测试可在保证覆盖率的同时有效降低测试代价。该文针对约束及约束组合的故障检测问题，将约束覆盖作为测试充分性准则，提出约束条件的组合测试方法。以典型的在线交易平台会员注册服务为例，对比OA（orthogonal array）、IPO（in-parameter order）和OFOT（one factor one time）3种组合算法应用于约束组合时的性能表现。实验选取不同的故障模式和实验配置，对3种组合算法从生成时间、故障检测能力、用例规模等方面进行了比较。实验结果表明：OA算法生成时间短、用例规模小且相对稳定、故障检测能力中等，适合迭代优化。

关键词 ：软件测试,组合测试,约束组合,测试生成

Abstract：The inputs parameters to software systems usually have various constraints correlated to each other. However, the input often violates the required constraints and constraint correlations. When there are many parameters with a large input domain, combinatorial testing can be used to reduce the test cost while ensuring test coverage. This paper defines a test adequacy criterion for constraint coverage using constrained combinatorial testing to detect conflicts caused by violating the constraints and constraint combinations. The system was applied to a member registration service for an online payment platform. Three typical combinatorial algorithms, OA (orthogonal array), IPO (in parameter order) and OFOT (one factor one time), were compared in forward their speeds, defect detection efficiency, and test case size using different configurations and parameter settings. The results showed that the OA algorithm was fast, produced fewer, more stable test cases with a reasonable defect detection efficiency, so this algorithm is good for iterative optimizations.

Key words：software testing combinatorial testing constraints combination test generation

收稿日期: 2016-04-19 出版日期: 2017-03-25

ZTFLH:

TP311.5

引用本文:

白晓颖, 黄军. 基于约束组合的测试用例生成[J]. 清华大学学报（自然科学版）, 2017, 57(3): 225-233.
BAI Xiaoying, HUANG Jun. Case generation by constraints combinatorial testing. Journal of Tsinghua University(Science and Technology), 2017, 57(3): 225-233.

链接本文:

http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2017.26.001或 http://jst.tsinghuajournals.com/CN/Y2017/V57/I3/225

图表:

图1 会员子系统与其他子系统的关系

图2 约束求解算法

表1 4约束OFOT生成结果

图3 正交表选择算法

表2 4条约束OA 生成结果

图4 修改后算法

表3 4条约束IPOG 生成结果

表4 会员注册参数约束

表5 会员注册服务故障设置

表6 实验配置

图5 IPOG 算法用例数随约束数量变化

图6 OA 和OFOT算法用例数随约束数量变化

图7 IPOG 算法耗时随约束数量变化

图8 OFOT算法耗时随约束数量变化

图9 OA 算法耗时随约束数量变化

图10 因子数不同的故障发现比例

图11 约束组合取值不同的4因子故障发现比例

参考文献:

[1]	Nie C, Leung H. A survey of combinatorial testing[J].ACM Computing Surveys (CSUR), 2011, 43(2):33-63.
[2]	Petke J. Constraints:The future of combinatorial in-teraction testing[C]//Proceedings of the Eighth International Workshop on Search-Based Software Testing. Piscataway, NJ, USA:IEEE Press, 2015:17-18.
[3]	Kilani Y, Alsarhan A, Bsoul M, et al. Soft Computing Applications[M]. Timisoara:Springer International Publishing, 2016.
[4]	Mercan H, Yilmaz C. Towards unified combinatorial interaction testing[J]. arXiv Preprint arXiv, 2016:1602. 06599.
[5]	Hnich B, Prestwich S D, Selensky E, et al. Constraint models for the covering test problem[J]. Constraints, 2006, 11(2-3):199-219.
[6]	Cohen M B, Colbourn C J, Ling A C H. Augmenting simulated annealing to build interaction test suites[C]//14th International Symposium on Software Reliability Engineering 2003. Denver, CO, USA:IEEE Press, 2003:394-405.
[7]	Cohen M B, Dwyer M B, Shi J. Exploiting constraint solving history to construct interaction test suites[C]//Testing:Academic and Industrial Conference Practice and Research Techniques-Mutation, 2007. Washington DC, USA:IEEE Press, 2007:121-132.
[8]	Cohen M B, Dwyer M B, Shi J. Constructing interaction test suites for highly configurable systems in the presence of constraints:A greedy approach[J]. IEEE Transactions on Software Engineering, 2008, 34(5):633-650.
[9]	Czerwonka J. Pairwise testing in the real world:Practical extensions to test-case scenarios[C]//Proceedings of 24th Pacific Northwest Software Quality Conference. Portland, Oregon, USA, 2006:419-430.
[10]	Tung Y W, Aldiwan W S. Automating test case gen-eration for the new generation mission software system[C]//2000 IEEE Aerospace Conference Proceedings. Big Sky, MT, USA:IEEE Press, 2000:431-437.
[11]	Cohen M B, Dwyer M B, Shi J. Interaction testing of highly configurable systems in the presence of constraints[C]//Proceedings of the 2007 International Symposium on Software Testing and Analysis. London, UK:ACM, 2007:129-139.
[12]	Cherif A, Imine A. A constraint-based approach for generating transformation patterns[J]. arXiv Preprint arXiv, 2015:1512.07684.
[13]	Choi Y, Byun T. Constraint-based test generation for automotive operating systems[J]. Software & Systems Modeling, 2015:1-18.
[14]	Bryce R C, Colbourn C J. Prioritized interaction testing for pairwise coverage with seeding and constraints[J]. Information and Software Technology, 2006, 48(10):960-970.
[15]	Banbara M, Matsunaka H, Tamura N, et al. Generating combinatorial test cases by efficient SAT encodings suitable for CDCL SAT solvers[C]//Logic for Programming, Artificial Intelligence, and Reasoning. Dakar, Senegal:Springer Berlin Heidelberg, 2010:112-126.
[16]	侯可佳, 白晓颖, 周立柱. 一种基于多约束组合的多租户系统配置测试技术[J].计算机学报,2016, 39(2):237-252.HOU Kejia, BAI Xiaoying, ZHOU Lizhu. Web service test data generation using interface semantic contract[J]. Chinese Journal of Computers, 2016, 39(2):237-252. (in Chinese)
[17]	Lei Y, Tai K C. In-parameter-order:A test generation strategy for pairwise testing[C]//High Assurance Systems Engineering Symposium, 1998. Proceedings. Third IEEE International. Washington DC, USA:IEEE Press, 1998:254-261.
[18]	Lei Y, Kacker R, Kuhn D R, et al. IPOG/IPOG-D:Efficient test generation for multiway combinatorial testing[J]. Software Testing, Verification and Reliability, 2008, 18(3):125-148."

[1]	崔宝江, 王福维, 郭涛, 柳本金. 基于污点信息的函数内存模糊测试技术研究[J]. 清华大学学报（自然科学版）, 2016, 56(1): 7-13.