基于布尔表达式约束的测试用例生成技术

doi:10.3969/j.issn.1006-2475.2019.01.016

摘要/Abstract

摘要： 布尔表达式约束在软件规格说明和程序中广泛存在，这些约束可作为软件系统的模型，成为测试用例生成依据。本文调研分析基于布尔表达式约束的测试用例生成方法，主要分为基于约束语法的测试和基于约束语义的测试。归纳总结基于约束语法测试的各种故障类型和测试策略，并比较各种测试策略的适用情形和故障检测能力，也对基于约束语义测试的各种约束获取和求解方法进行性能分析，并介绍了典型工具。最后对未来的研究发展进行展望。

关键词: 软件测试, 测试用例生成, 约束, 布尔表达式

Abstract: Constraints presented as Boolean expression exist widely in software specifications and programs, these constraints can be used as models of software systems and become the basis for test case generation. This paper investigates and analyzes test case generation methods based on constraints presented as Boolean expression, which are mainly divided into constraint syntax-based testing and constraint semantics-based testing. This paper summarizes various fault classes and test strategies in constraint syntax-based testing, and compares their applicability and fault detection capability. The paper also analyzes the performance of miscellaneous methods of getting and solving constraints in constraint semantics-based testing, and introduces typical tools. Finally, the future research and development are prospected.

Key words: software testing, test case generation, constraints, Boolean expressions

中图分类号:

TP311.5

孙溢1,阳小华1,刘杰1,余童兰1,吴志强2,陈智2. 基于布尔表达式约束的测试用例生成技术[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2019.01.016.

SUN Yi1, YANG Xiao-hua1, LIU Jie1, YU Tong-lan1, WU Zhi-qiang2, CHEN Zhi2. Test Case Generation Techniques Based on Constraints Presented as Boolean Expressions[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2019.01.016.

参考文献

［1］ MORELL L J. A theory of fault-based testing［J］. IEEE Transactions on Software Engineering, 1990,16(8):844-857.
［2］ GOTLIEB A. Constraint-based testing: An emerging trend in software testing［J］. Advances in Computers, 2015,99:67-101.
［3］孙昌爱,程庆顺. 基于故障的布尔表达式测试技术综述［J］. 计算机科学, 2013,40(3):16-23,40.
［4］ KUHN D R. Fault classes and error detection capability of specification-based testing［J］. ACM Transactions on Software Engineering and Methodology, 1999,8(4):411-424.
［5］ TSUCHIYA T, KIKUNO T. On fault classes and error detection capability of specification-based testing［J］. ACM Transactions on Software Engineering and Methodology, 2002,11(1):58-62.
［6］ LAU M F, YU Y T. On the relationships of faults for boolean specification based testing［C］// Proceedings of the 13th Australian Conference on Software Engineering. 2001:21-28.
［7］ LAU M F, YU Y T. An extended fault class hierarchy for specification-based testing［J］. ACM Transactions on Software Engineering and Methodology, 2005,14(3):247-276.
［8］ CHANDRA P, SINGH R K, SINGH Y. Review and extension of fault class hierarchy for testing boolean specification［J］. International Journal of Computer Applications in Technology, 2015,52(1):29-38.〖HJ1.6mm〗
［9］ CHEN T Y, LAU M F, SIM K Y, et al. On detecting faults for boolean expressions［J］. Software Quality Journal, 2009,17(3):245-261.
［10］KAPOOR K, BOWEN J P. Test conditions for fault classes in boolean specifications［J］. ACM Transactions on Software Engineering and Methodology, 2007,16(3):1-12.
［11］CHEN Z Y, CHEN T Y, XU B W. A revisit of fault class hierarchies in general boolean specifications［J］. ACM Transactions on Software Engineering and Methodology, 2011,20(3):1-12.
［12］PAUL T K, LAU M F. Redefinition of fault classes in logic expressions［C］// Proceedings of the 12th IEEE International Conference on Quality Software. 2012:144-153.
［13］MYERS G J. The Art of Software Testing［M］. New York: John Wiley & Sons, 1979.
［14］WEYUKER E, GORADIA T, SINGH A. Automatically generating test data from a boolean specification［J］. IEEE Transactions on Software Engineering, 1994,20(5):353-363.
［15］CHEN T Y, LAU M F. Two test data selection strategies towards testing of boolean specifications［C］// Proceedings of the 21st International Computer Software and Applications Conference. 1997:608-611.
［16］CHEN T Y, LAU M F. Test case selection strategies based on boolean specifications［J］. Software Testing, Verification and Reliability, 2001,11(3):165-180.
［17］CHEN T Y, LAU M F, YU Y T. MUMCUT: A fault-based strategy for testing boolean specifications［C］// Proceedings of the 6th Asia-Pacific Software Engineering Conference. 1999:606-613.
［18］KAMINSKI G, WILLIAMS G, AMMANN P. Reconciling perspectives of software logic testing［J］. Software Testing Verification & Reliability, 2008,18(3):149-188.
［19］TAI K C. Predicate-based test generation for computer programs［C］// Proceedings of the 15th International Conference on Software Engineering. 1993:267-276.
［20］[JP2]PARADKAR A, TAI K C.Test generation for boolean expressions［C］// Proceedings of the 6th International Symposium on Software Reliability Engineering. 1995:106-115.
［21］TAI K C. Theory of fault-based predicate testing for computer programs［J］. IEEE Transactions on Software Engineering, 1996,22(8):552-562.
［22］FOSTER K A. Sensitive test data for logic expression［J］. ACM SIGSOFT Software Engineering Notes, 1984,9(2):120-125.
［23］CHEN Z Y, XU B W, NIE C H. Comparing fault-based testing strategies of general boolean specifications［C］// Proceedings of International Computer Software and Applications Conference. 2007:621-622.
［24］李磊芳,徐宝文,陈振宇,等. 一种新的布尔规格测试用例生成算法［J］. 东南大学学报(自然科学版), 2010,40(2):291-295.
［25］PAUL T K, MAN F L, NG S. On a new detecting technique for conjunctive literal insertion fault in boolean expressions［C］// Proceedings of the 14th International Conference on Quality Software. 2014:266-275.
［26］YU L, TSAI W T. Test case generation for Boolean expressions by cell covering［J］. IEEE Transactions on Software Engineering, 2018,44(1):70-99.
［27］SUN C, ZAI Y, LIU H. Evaluating and comparing fault-based testing strategies for general boolean specifications: A series of experiments［J］. The Computer Journal, 2015,58(5):1199-1213.
［28］ALI A M, SHAIK K, KUMAR S. Test case generation using UML state diagram and OCL expression［J］. International Journal of Computer Applications, 2014,95(12):7-11.
［29］VU T D, HUNG P N, NGUYEN V H. A method for automated test data generation from sequence diagrams and object constraint language［C］// Proceedings of the 6th International Symposium on Information and Communication Technology. 2015:335-341.
［30］CHANG C K, LIN N W. A constraint-based framework for test case generation in method-level black-box unit testing［J］. Journal of Information Science and Engineering, 2016,32(2):365-387.
［31］BASA S S, SWAIN S K, MOHAPATRA D P. Genetic algorithm-based optimized test case design using UML［J］. Journal of Computer and Mathematical Sciences, 2018,6(6):1223-1238.
［32］KING J C. Symbolic execution and program testing［J］. Communications of the ACM, 1976,19(7):385-394.
［33］GODEFROID P, KLARLUND N, SEN K. DART: Directed automated random testing［C］// Proceedings of 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation. 2005:213-223.
［34］SEN K, MARINOV D, AGHA G. CUTE:A concolic unit testing engine for C［C］// Proceedings of the 10th European Software Engineering Conference held jointly with 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering. 2005:263-272.
［35］SEN K, AGHA G. CUTE and jCUTE: Concolic unit testing and explicit path model-checking tools［C］// Proceedings of 18th International Conference on Computer Aided Verification. 2006:419-423.
［36］BURNIM J, SEN K. Heuristics for scalable dynamic test generation［C］// Proceedings of the 23rd IEEE/ACM International Conference on Automated Software Engineering. 2008:443-446.
［37］CADAR C, ENGLER D. Execution generated test cases: How to make systems code crash itself［C］// Proceedings of the 12th International Conference on Model Checking Software. 2005:2-23.
［38］CADAR C, GANESH V, Pawlowski P M, et al. EXE:Automatically generating inputs of death［C］// Proceedings of the 13th ACM Conference on Computer and Communications Security. 2006:322-335.
［39］CADAR C, DUNBAR D, ENGLER D. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs［C］// Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation. 2008:209-224.
［40］CHIPOUNOV V, GEORGESCU V, ZAMFIR C, et al. Selective symbolic execution［C］// Proceedings of the 5th Workshop on Hot Topics in System Dependability(HotDep). 2009:1286-1299.
［41］AVGERINOS T, REBERT A, CHA S K, et al. Enhancing symbolic execution with veritesting［C］// Proceedings of the 36th International Conference on Software Engineering. 2014:1083-1094
［42］RAMOS D A, ENGLER D. Under-constrained symbolic execution:Correctness checking for real code［C］// Proceedings of the 24th USENIX Conference on Security Symposium. 2015:49-64.
［43］STEPHENS N, GROSEN J, SALLS C, et al. Driller:Augmenting fuzzing through selective symbolic execution［C］// Proceedings of the Network and Distributed System Security Symposium. 2016:1-16.
［44］SHOSHITAISHVILI Y, KRUEGEL C, VIGNA G, et al. SOK: (state of) the art of war: Offensive techniques in binary analysis［C］// Proceedings of 2016 IEEE Symposium on Security and Privacy. 2016:138-157.
［45］ZHOU J G, ZHANG Z Y, XIE P Z, et al. A test data generation approach for automotive software［C］// Proceedings of 2015 IEEE International Conference on Software Quality, Reliability and Security-Companion. 2015:216-220.
［46］QIAN J, LIU K, CHEN H, et al. Decomposing constraints for better coverage in test data generation［J］. International Journal of Performability Engineering, 2018,14(6):1251-1262.
［47］ZHANG Z Y, CHEN Z Y, GAO R Z, et al. An empirical study on constraint optimization techniques for test generation［J］. Science China(Information Sciences), 2017,60(1):69-83.
［48］COOK S A. The complexity of theorem-proving procedures［C］// Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. 1971:151-158.
［49］MOURA L D, DUTERTRE B, SHANKAR N. A tutorial on satisfiability modulo theories［C］// Proceedings of the 19th International Conference on Computer Aided Verification. 2007:20-36.
［50］MALBURG J, FRASER G. Search-based testing using constraint-based mutation［J］. Software Testing, Verification & Reliability, 2014,24(6):472-495.
［51］XING Y, GONG Y Z, WANG Y W, et al. A hybrid intelligent search algorithm for automatic test data generation［J］. Mathematical Problems in Engineering, 2015(10):1-15.
［52］LIN M X, HOU X M, LIU R, et al. Enhancing constraint based test generation by local search［C］// Proceedings of the 6th International Conference on Software and Computer Applications. 2017:154-158.
［53］BRAIONE P, DENARO G, MATTAVELLI A, et al. Combining symbolic execution and search-based testing for programs with complex heap inputs［C］// Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis. 2017:90-101.
［54］REYNOLDS A, TINELLI C, BARRETT C. Constraint solving for finite model finding in SMT solvers［J］. Theory and Practice of Logic Programming, 2017,17(4):1-43.

[1]	徐胜超, 叶力洪. 基于长短期记忆神经网络的容器云队列在线任务动态分配[J]. 计算机与现代化, 2022, 0(07): 79-84.
[2]	王程, 陈正鸣, 吕嘉. 面向纸板三维装箱问题的剩余空间最优算法[J]. 计算机与现代化, 2021, 0(03): 28-34.
[3]	黄欣辰, 皋军, 黄豪杰. 基于PCA降维的成对约束半监督聚类集成[J]. 计算机与现代化, 2021, 0(01): 94-99.
[4]	李运川, 王晓红, 陈思吉, 葛义攀, 李闯. 基于多核并行和动态阈值的点云配准算法[J]. 计算机与现代化, 2020, 0(09): 77-82.
[5]	许小媛, 李海波, 于本成, 刘芳. 具有对偶约束的半监督重叠社区发现方法[J]. 计算机与现代化, 2020, 0(08): 63-68.
[6]	肖支才，尹高扬，闫实 . 基于循环寻优RRT算法的无人机航迹规划[J]. 计算机与现代化, 2020, 0(02): 16-.
[7]	范新南，顾亚飞，倪建军. 改进ORB算法在图像匹配中的应用[J]. 计算机与现代化, 2019, 0(02): 1-.
[8]	李国平,邢建春,王世强. 多传感器系统含状态约束的分布式并行卡尔曼滤波算法[J]. 计算机与现代化, 2018, 0(12): 1-.
[9]	张晨光,徐珞,李宁. 一种在线测试集约减方法[J]. 计算机与现代化, 2018, 0(12): 40-.
[10]	周博1，李亚琼1，刘永波1，李守超1，宋云奎2. 面向云计算的期限约束的MapReduce作业调度方法[J]. 计算机与现代化, 2018, 0(11): 51-.
[11]	李军锋，顾滨兵，李海浩. 软件测试质量评价方法[J]. 计算机与现代化, 2018, 0(09): 38-.
[12]	李建波. 基于VSTO的文档审阅批注自动导出技术[J]. 计算机与现代化, 2018, 0(05): 56-.
[13]	向日锋，毛宇光. 基于WEHG模型的GUI软件测试用例生成方法[J]. 计算机与现代化, 2018, 0(04): 26-.
[14]	董国良1,2，臧洌1，李航1，甘露1. 一种应用于动态污点分析的路径自动生成方法[J]. 计算机与现代化, 2017, 0(7): 32-37+41.
[15]	范引娣. 基于高阶结构约束的稀疏人脸识别算法[J]. 计算机与现代化, 2016, 0(9): 73-76.