We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Ming-Zhe Zhang, Yun-Zhan Gong, Ya-Wen Wang, Da-Hai Jin. Unit Test Data Generation for C Using Rule-Directed Symbolic Execution[J]. Journal of Computer Science and Technology, 2019, 34(3): 670-689. DOI: 10.1007/s11390-019-1935-7
Citation: Ming-Zhe Zhang, Yun-Zhan Gong, Ya-Wen Wang, Da-Hai Jin. Unit Test Data Generation for C Using Rule-Directed Symbolic Execution[J]. Journal of Computer Science and Technology, 2019, 34(3): 670-689. DOI: 10.1007/s11390-019-1935-7

Unit Test Data Generation for C Using Rule-Directed Symbolic Execution

Funds: This work was supported by the National Natural Science Foundation of China under Grant Nos. U1736110 and 61702044.
More Information
  • Author Bio:

    Ming-Zhe Zhang received his B.E. degree in computer science and technology from Shandong Normal University, Jinan, in 2012. He is currently a Ph.D. candidate in the State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing. His current research interests mainly focus on software testing and program analysis.

  • Corresponding author:

    Ya-Wen Wang E-mail: wangyawen@bupt.edu.cn

  • Received Date: July 05, 2018
  • Revised Date: March 18, 2019
  • Published Date: May 04, 2019
  • Unit testing is widely used in software development. One important activity in unit testing is automatic test data generation. Constraint-based test data generation is a technique for automatic generation of test data, which uses symbolic execution to generate constraints. Unit testing only tests functions instead of the whole program, where individual functions typically have preconditions imposed on their inputs. Conventional symbolic execution cannot detect these preconditions, let alone converting these preconditions into constraints. To overcome these limitations, we propose a novel unit test data generation approach using rule-directed symbolic execution for dealing with functions with missing input preconditions. Rule-directed symbolic execution uses predefined rules to detect preconditions in the individual function, and generates constraints for inputs based on preconditions. We introduce implicit constraints to represent preconditions, and unify implicit constraints and program constraints into integrated constraints. Test data generated based on integrated constraints can explore previously unreachable code and help developers find more functional faults and logical faults. We have implemented our approach in a tool called CTS-IC, and applied it to real-world projects. The experimental results show that rule-directed symbolic execution can find preconditions (implicit constraints) automatically from an individual function. Moreover, the unit test data generated by our approach achieves higher coverage than similar tools and efficiently mitigates missing input preconditions problems in unit testing for individual functions.
  • [1]
    Li B, Vendome C, Linares-Vásquez M, Poshyvanyk D, Kraft N A. Automatically documenting unit test cases. In Proc. IEEE International Conference on the Software Testing, Verification and Validation, April 2016, pp.341-352.
    [2]
    Lam W, Srisakaokul S, Bassett B, Mahdian P, Xie T, Tillmann N, de Halleux J. Parameterized unit testing in the open source wild. Technical Report, IDEALS, 2015. http://hdl.handle.net/2142/88374, Dec. 2018.
    [3]
    Zhang B, Hill E, Clause J. Towards automatically generating descriptive names for unit tests. In Proc. the 31st IEEE/ACM International Conference on Automated Software Engineering, September 2016, pp.625-636.
    [4]
    Yoshida H, Tokumoto S, Prasad M R, Ghosh I, Uehara T. FSX:Fine-grained incremental unit test generation for C/C++ programs. In Proc. the 25th International Symposium on Software Testing and Analysis, July 2016, pp.106- 117.
    [5]
    DeMilli R A, Offutt A J. Constraint-based automatic test data generation. IEEE Transactions on Software Engineering, 1991, 17(9):900-910.
    [6]
    Boonstoppel P, Cadar C, Engler D. RWset:Attacking path explosion in constraint-based test generation. In Proc. the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, March 2008, pp.351-366.
    [7]
    Boyer R S, Elspas B, Levitt K N. SELECT - A formal system for testing and debugging programs by symbolic execution. ACM SIGPLAN Notices, 1975, 10(6):234-245.
    [8]
    Cadar C, Sen K. Symbolic execution for software testing:Three decades later. Communications of the ACM, 2013, 56(2):82-90.
    [9]
    Cadar C, Dunbar D, Engler D R. KLEE:Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proc. the 8th USENIX Symposium on Operating Systems Design and Implementation, December 2008, pp.209-224.
    [10]
    Ganesh V, Dill D L. A decision procedure for bit-vectors and arrays. In Proc. the 19th International Conference on Computer Aided Verification, July 2007, pp.519-531.
    [11]
    de Moura L, Bjørner N. Z3:An efficient SMT solver. In Proc. the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, March 2008, pp.337-340.
    [12]
    Tillmann N, de Halleux J. Pex-white box test generation for.NET. In Proc. the 2nd International Conference on Tests and Proofs, April 2008, pp.134-153.
    [13]
    Cadar C, Ganesh V, Pawlowski P M, Dill D L, Engler D R. EXE:Automatically generating inputs of death. ACM Transactions on Information and System Security, 2008, 12(2):Article No. 10.
    [14]
    Engler D R, Dunbar D. Under-constrained execution:Making automatic code destruction easy and scalable. In Proc. the 2007 ACM/SIGSOFT International Symposium on Software Testing and Analysis, July 2007, pp.1-4.
    [15]
    Burnim J, Sen K. Heuristics for scalable dynamic test generation. In Proc. the 23rd IEEE/ACM International Conference on Automated Software Engineering, September 2008, pp.443-446.
    [16]
    Hutchins M, Foster H, Goradia T, Ostrand T. Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria. In Proc. the 16th International Conference on Software Engineering, May 1994, pp.191-200.
    [17]
    Xing Y, Gong Y Z, Wang Y W, Zhang X Z. Branch and bound framework for automatic test case generation. SCIENTIA SINICA Informationis, 2014, 44(10):1345-1360.
    [18]
    Kernighan B W, Ritchie D M. The C Programming Language (2nd edition). Prentice hall, 1988.
    [19]
    Zhang X Z, Gong Y Z, Wang Y W, Xing Y, Zhang M Z. Automated string constraints solving for programs containing string manipulation functions. Journal of Computer Science and Technology, 2017, 32(6):1125-1135.
    [20]
    Aho A V, Sethi R, Ullman J D. Compilers:Principles, Techniques, and Tools. Addison-Wesley, 1986.
    [21]
    Lin M X, Chen Y L, Yu K, Wu G S. Lazy symbolic execution for test data generation. IET Software, 2011, 5(2):132-141.
    [22]
    Li G, Ghosh I. Lazy symbolic execution through abstraction and sub-space search. In Proc. the 9th International Haifa Verification Conference on Hardware and Software:Verification and Testing, November 2013, pp.295-310.
    [23]
    Brack-Bernsen L, Hunger H. On the "Atypical Astronomical Cuneiform Text E":A mean-value scheme for predicting lunar latitude. Archiv fur Orientforschung, 2005, 51:96-107.
    [24]
    Arcuri A, Iqbal M Z, Briand L. Formal analysis of the effectiveness and predictability of random testing. In Proc. the 19th International Symposium on Software Testing and Analysis, July 2010, pp.219-230.
    [25]
    Sen K, Marinov D, Agha G. Cute:A concolic unit testing engine for C. In Proc. the 10th European Software Engineering Conference, September 2005, pp.263-272.
    [26]
    Godefroid P, Levin M Y, Molnar D. SAGE:Whitebox fuzzing for security testing. Communications of the ACM, 2012, 55(3):40-44.
    [27]
    Yoshida H, Li G, Kamiya T, Ghosh I, Rajan S, Tokumoto S, Munakata K, Uehara T. KLOVER:Automatic test generation for C and C++ programs, using symbolic execution. IEEE Software, 2017, 34(5):30-37.
    [28]
    Ramos D A, Engler D R. Under-constrained symbolic execution:Correctness checking for real code. In Proc. the 24th USENIX Security Symposium, August 2015, pp.49-64.
    [29]
    Nori A V, Rajamani S K. An empirical study of optimizations in YOGI. In Proc. the 32nd ACM/IEEE International Conference on Software Engineering, Volume 1, May 2010, pp.355-364.
    [30]
    Zhang D, Liu D, Lei Y, Kung D, Csallner C, Wang W. Detecting vulnerabilities in C programs using trace-based testing. In Proc. the 2010 IEEE/IFIP International Conference on Dependable Systems Networks, June 2010, pp.241-250.
    [31]
    Li H, Kim T, Bat-Erdene M, Lee H. Software vulnerability detection using backward trace analysis and symbolic execution. In Proc. the 2013 International Conference on Availability, Reliability and Security, September 2013, pp.446-454.
    [32]
    Kim Y, Kim Y, Kim T, Lee G, Jang Y, Kim M. Automated unit testing of large industrial embedded software using concolic testing. In Proc. the 28th IEEE/ACM International Conference on Automated Software Engineering, November 2013, pp.519-528.
  • Related Articles

    [1]Zhong-Yi Wang, Ming-Shuai Chen, Teng-Jie Lin, Lin-Yu Yang, Jun-Hao Zhuo, Qiu-Ye Wang, Sheng-Chao Qin, Xiao Yi, Jian-Wei Yin. PARF: An Adaptive Abstraction-Strategy Tuner for Static Analysis[J]. Journal of Computer Science and Technology. DOI: 10.1007/s11390-025-5140-6
    [2]Wen-Jie Li, Jun Ma, Yan-Yan Jiang, Chang Xu, Xiao-Xing Ma. Understanding and Detecting Inefficient Image Displaying Issues in Android Apps[J]. Journal of Computer Science and Technology, 2024, 39(2): 434-459. DOI: 10.1007/s11390-022-1670-3
    [3]Gen Zhang, Peng-Fei Wang, Tai Yue, Xu Zhou, Kai Lu. MEBS: Uncovering Memory Life-Cycle Bugs in Operating System Kernels[J]. Journal of Computer Science and Technology, 2021, 36(6): 1248-1268. DOI: 10.1007/s11390-021-1593-4
    [4]Feng-Juan Gao, Yu Wang, Lin-Zhang Wang, Zijiang Yang, Xuan-Dong Li. Automatic Buffer Overflow Warning Validation[J]. Journal of Computer Science and Technology, 2020, 35(6): 1406-1427. DOI: 10.1007/s11390-020-0525-z
    [5]Gökçer Peynirci, Mete Eminaǧaoǧlu, Korhan Karabulut. Feature Selection for Malware Detection on the Android Platform Based on Differences of IDF Values[J]. Journal of Computer Science and Technology, 2020, 35(4): 946-962. DOI: 10.1007/s11390-020-9323-x
    [6]Ling-Yun Situ, Lin-Zhang Wang, Yang Liu, Bing Mao, Xuan-Dong Li. Automatic Detection and Repair Recommendation for Missing Checks[J]. Journal of Computer Science and Technology, 2019, 34(5): 972-992. DOI: 10.1007/s11390-019-1955-3
    [7]Ji Wang, Xiao-Dong Ma, Wei Dong, Hou-Feng Xu, Wan-Wei Liu. Demand-Driven Memory Leak Detection Based on Flow- and Context-Sensitive Pointer Analysis[J]. Journal of Computer Science and Technology, 2009, 24(2): 347-356.
    [8]ZHANG WenHui. Combining Static Analysis and Case-Based Search Space Partitioning for Reducing Peak Memory in Model Checking[J]. Journal of Computer Science and Technology, 2003, 18(6).
    [9]Qu Yuzhong, Wang Zhijian, Xu Jiafu. Denotational Semantics of a Simple Model of Eiffel[J]. Journal of Computer Science and Technology, 1995, 10(3): 214-226.
    [10]Hou Luoming. A General and Formal Method for the Program Static Analysis[J]. Journal of Computer Science and Technology, 1987, 2(2): 115-123.

Catalog

    Article views (74) PDF downloads (545) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return