Test Case Generation Techniques Based on Constraints Presented as Boolean Expressions

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

CLC Number:

TP311.5

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.

References

［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]	WANG Cheng, CHEN Zheng-ming, LYU Jia. Optimal Algorithm of Remaining Space for 3D Packing Problem of Paperboard [J]. Computer and Modernization, 2021, 0(03): 28-34.
[2]	HUANG Xin-chen, GAO Jun, HUANG Hao-jie. Semi-supervised Clustering Ensemble with Pairwise Constraints Based on PCA Dimension Reduction [J]. Computer and Modernization, 2021, 0(01): 94-99.
[3]	XU Xiao-yuan, LI Hai-bo, YU Ben-cheng, LIU Fang. Semi-supervised Overlapping Community Finding with Pairwise Constraints [J]. Computer and Modernization, 2020, 0(08): 63-68.
[4]	ZHANG Chen-guang, XU Luo, LI Ning. An Online Optimizing Approach for Test Suite [J]. Computer and Modernization, 2018, 0(12): 40-.
[5]	LI Guo-ping， XING Jian-chun, WANG Shi-qiang. Decentralized Parallel Kalman Filter for Multi-sensor System with State Constraints [J]. Computer and Modernization, 2018, 0(12): 1-.
[6]	LI Jun-feng, GU Bin-bing, LI Hai-hao. Evaluation Method for Software Testing Quality [J]. Computer and Modernization, 2018, 0(09): 38-.
[7]	LI Jian-bo. Auto-exporting Technology for Word Review Comments Based on VSTO [J]. Computer and Modernization, 2018, 0(05): 56-.
[8]	XIANG Rifeng, MAO Yuguang. GUI Software Test Case Generation Method Based on WEHG Model [J]. Computer and Modernization, 2018, 0(04): 26-.
[9]	ZENG Jin-wei1, ZHANG Peng-cheng1, LI Wen-rui2， ZHOU Xin-li3 . A Multi-label Metamorphic Relations Prediction Approach Based on RBF Neural Network [J]. Computer and Modernization, 2016, 0(12): 1-6,11.
[10]	WANG Wang1, XIA Feng2, CHEN Zhe1, HUANG Zhiqiu1. An Automated Testing and Monitoring Platform for Largescale Server Cluster [J]. Computer and Modernization, 2014, 0(9): 137-142.
[11]	LIU Bo, HUANG Zhi-qiu, WANG Shan-shan. A Method of Service Evolution for Controlling Risk of Privacy Exposure [J]. Computer and Modernization, 2014, 0(10): 76-80,107.
[12]	QU Chi-wen. Research on Class-level Test Methods for State Diagram [J]. Computer and Modernization, 2012, 208(12): 136-138,.
[13]	XU Yongjie;ZHU Xiaodong;WANG Yigang. GUI Test Case Generation Based on Interaction Eventflow Model [J]. Computer and Modernization, 2012, 8(08): 32-36.
[14]	CAO Jing;SHAO Zong-you. Research on Evaluation Method of Software Testing Cost [J]. Computer and Modernization, 2011, 193(9): 210-214.
[15]	XIA Yu-hui ;LI Ming;WAN Lin;WANG Hong-yan . Static Detecting Method for Fault Model [J]. Computer and Modernization, 2011, 1(2): 0-80.