微信服务号

微信订阅号

2025-5-16- 0
Home > Archive>Volume 27, Issue 3, 2016 >593-610. DOI:10.13328/j.cnki.jos.004983
PDF HTML XML Export Cite reminder
Test Generation Approach Guided by Linear Fitting for Condition/Decision Coverage Crit
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61402222, 91318301, 61561146394); National Program on Key Basic ResearchProject of China (973 Program) (2014CB340703); Specialized Research Fund for the Doctoral Program of Higher Education (20110091120058); Project on the Integration of Industry, Education and Research of Jiangsu Province (BY2014126-03)

  • Article
    • | |
  • Metrics
    • |
  • Reference [35]
    • |
  • Related [20]
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    Condition/decision coverage(C/DC) is a frequently used coverage criteria for safety-critical software testing.It requires every decision and condition in the program have taken all possible outcomes(true or false).Existing approaches of automatic test generation for C/DC criteria are defective.For example, symbolic execution based approaches are limited by the constraint solver, which is difficult in processing non-linear constraints;hill climbing often sticks at local optima, which limits yielding of high-coverage cases;and simulated annealing and genetic algorithm need complicated configuration, which make the results unstable.In this paper, a novel test generation approach that is guided by linear fitting is proposed.The basis of the approach is to sample every decision and condition of numerical values with program instrumentation.The relationship of inputs and samples is then build with linear fitting functions.By searching the target inputs on the gradually refined functions, test case is generated with high coverage.Experiments on 25 real programs in open source projects show that the proposed approach is more effective and efficient than the genetic algorithm of test generation.

    Reference
    [1] Tassey G. The economic impacts of inadequate infrastructure for software testing. National Institute of Standards and Technology, RTI Project, 2002,7007(011).
    [2] Xiao M, El-Attar M, Reformat M, Miller J. Empirical evaluation of optimization algorithms when used in goal-oriented automated test data generation techniques. Empirical Software Engineering, 2007,12(2):183-239.[doi:10.1007/s10664-006-9026-0]
    [3] Bertolino A. Software testing research:Achievements, challenges, dreams. In:Proc. of the 2007 Future of Software Engineering. IEEE Computer Society, 2007. 85-103.[doi:10.1109/FOSE.2007.25]
    [4] RTCA. DO-178B software considerations in airborne systems and equipment certification, radio technical commission for aeronautics(RTCA). European Organization for Civil Aviation Electronics(EUROCAE). 1992.
    [5] Cadar C, Sen K. Symbolic execution for software testing:Three decades later. Communications of the ACM, 2013,56(2):82-90.[doi:10.1145/2408776.2408795]
    [6] Majumdar R, Sen K. Hybrid concolic testing. In:Proc. of the 29th Int'l Conf. on Software Engineering. Washington:IEEE Computer Society, 2007. 416-426.[doi:10.1109/ICSE.2007.41]
    [7] Bueno PMS, Jino M. Automatic test data generation for program paths using genetic algorithms. Int'l Journal of Software Engineering and Knowledge Engineering, 2002,12(6):691-709.[doi:10.1142/S0218194002001074]
    [8] Michael CC, McGraw G, Schatz M. Generating software test data by evolution. IEEE Trans. on Software Engineering, 2001,27(12):1085-1110.[doi:10.1109/32.988709]
    [9] Korel B. Automated software test data generation. IEEE Trans. on Software Engineering, 1990,16(8):870-879.[doi:10.1109/32.57624]
    [10] Korel B. Dynamic method for software test data generation. Software Testing, Verification and Reliability, 1992,2(4):203-213.[doi:10.1002/stvr.4370020405]
    [11] Mansour N, Salame M. Data generation for path testing. Software Quality Journal, 2004,12(2):121-136.[doi:10.1023/B:SQJO. 0000024059.72478.4e]
    [12] Ghani K, Clark JA. Automatic test data generation for multiple condition and MCDC coverage. In:Proc. of the 4th Int'l Conf. on Software Engineering Advances(ICSEA 2009). IEEE, 2009. 152-157.[doi:10.1109/ICSEA.2009.31]
    [13] Xanthakis S, Ellis C, Skourlas C, Le Gall A, Katsikas S, Karapoulios K. Application of genetic algorithms to software testing. In:Proc. of the 5th Int'l Conf. on Software Engineering and its Applications. 1992. 625-636.
    [14] McMinn P. IGUANA:Input generation using automated novel algorithms. A plug and play research tool. Technical Report, CS-07-14, Department of Computer Science, University of Sheffield, 2007.
    [15] Janikow CZ, Michalewicz Z. An experimental comparison of binary and floating point representations in genetic algorithms. In:Proc. of the ICGA. 1991. 31-36.
    [16] Linger RC. Cleanroom software engineering for zero-defect software. In:Proc. of the 15th Int'l Conf. on Software Engineering. IEEE Computer Society Press, 1993. 2-13.[doi:10.1109/ICSE.1993.346060]
    [17] Ramamoorthy CV, Ho S-BF, Chen W. On the automated generation of program test data. IEEE Trans. on Software Engineering, 1976,3(4):293-300.[doi:10.1109/TSE.1976.233835]
    [18] Thevenod-Fosse P, Waeselynck H. STATEMATE applied to statistical software testing. In:Proc. of the ACM SIGSOFT Software Engineering Notes. ACM Press, 1993. 99-109.[doi:10.1145/154183.154262]
    [19] Korel B. Automated test data generation for programs with procedures. In:Zeil SJ, Tracz W, eds. Proc. of the ACM SIGSOFT Software Engineering Notes. ACM Press, 1996. 209-215.[doi:10.1145/229000.226319]
    [20] McMinn P. Search-Based software testing:Past, present and future. In:Proc. of the 4th IEEE Int'l Conf. on Software Testing, Verification and Validation Workshops(ICSTW). IEEE, 2011. 153-163.[doi:10.1109/ICSTW.2011.100]
    [21] Boyer RS, Elspas B, Levitt KN. SELECT-A formal system for testing and debugging programs by symbolic execution. ACM SigPlan Notices, 1975,10(6):234-245.[doi:10.1145/390016.808445]
    [22] Howden WE. Symbolic testing and the DISSECT symbolic evaluation system. IEEE Trans. on Software Engineering, 1977,3(4):266-278.[doi:10.1109/TSE.1977.231144]
    [23] King JC. Symbolic execution and program testing. Communications of the ACM, 1976,19(7):385-394.[doi:10.1145/360248. 360252]
    [24] Godefroid P, Klarlund N, Sen K. DART:Directed automated random testing. In:Proc. of the ACM Sigplan Notices. ACM Press, 2005. 213-223.[doi:10.1145/1065010.1065036]
    [25] Cadar C, Ganesh V, Pawlowski PM, Dill DL, Engler DR. EXE:Automatically generating inputs of death. ACM Trans. on Information and System Security(TISSEC), 2008,12(2):10.[doi:10.1145/1455518.1455522]
    [26] Cadar C, Dunbar D, Engler DR. KLEE:Unassisted and automatic generation of high-coverage tests for complex systems programs. In:Proc. of the OSDI. 2008. 209-224.
    [27] Dinges P, Agha G. Solving complex path conditions through heuristic search on induced polytopes. In:Proc. of the 22nd ACM SIGSOFT Int'l Symp. on Foundations of Software Engineering. ACM Press, 2014. 425-436.[doi:10.1145/2635868.2635889]
    [28] Li Y, Su Z, Wang L, Li X. Steering symbolic execution to less traveled paths. ACM SigPlan Notices, 2013,48(10):19-32.[doi:10.1145/2544173.2509553]
    [29] Marinescu PD, Cadar C. KATCH:High-Coverage testing of software patches. In:Proc. of the 9th Joint Meeting on Foundations of Software Engineering. ACM Press, 2013. 235-245.[doi:10.1145/2491411.2491438]
    [30] Su T, Pu G, Fang B, He J, Yan J, Jiang S, Zhao J. Automated coverage-driven test data generation using dynamic symbolic execution. In:Proc. of the 8th Int'l Conf. on Software Security and Reliability(SERE). 2014. 98-107.[doi:10.1109/SERE. 2014.23]
    [31] Davis M. Hilbert's Tenth Problem is Unsolvable. American Mathematical Monthly, 1973. 233-269.[doi:10.2307/2318447]
    [32] Lakhotia K, Tillmann N, Harman M, De Halleux J. Flopsy-Search-Based floating point constraint solving for symbolic execution. In:Petrenko A, Simão A, Maldonado JC, eds. Proc. of the Testing Software and Systems. Springer-Verlag, 2010. 142-157.[doi:10.1007/978-3-642-16573-3_11]
    [33] Su T, Fu Z, Pu G, He J, Su Z. Combining symbolic execution and model checking for data flow testing. In:Proc. of the 37th Int'l Conf. on Software Engineering. ICSE, 2015.[doi:10.1109/ICSE.2015.81]
    [34] Inkumsah K, Xie T. Evacon:A framework for integrating evolutionary and concolic testing for object-oriented programs. In:Proc. of the 22nd IEEE/ACM Int'l Conf. on Automated Software Engineering. ACM Press, 2007. 425-428.[doi:10.1145/1321631. 1321700]
    [35] Tillmann N, De Halleux J. Pex-White box test generation for net. In:Proc. of the Tests and Proofs. Springer-Verlag, 2008. 134-153.[doi:10.1007/978-3-540-79124-9_10]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

汤恩义,周岩,欧建生,陈鑫.面向条件判定覆盖的线性拟合制导测试生成.软件学报,2016,27(3):593-610

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 15,2015
  • Revised:October 20,2015
  • Online: January 06,2016
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2044766Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063