A reasoning-based approach to dynamic domain reduction in test data generation | International Journal on Software Tools for Technology Transfer Skip to main content
Springer Nature Link
Log in

A reasoning-based approach to dynamic domain reduction in test data generation

  • Regular Paper
  • Published:
International Journal on Software Tools for Technology Transfer Aims and scope Submit manuscript

Abstract

In this article, a new criterion, domain coverage, for white box testing is introduced. In search of the biggest subdomains for input variables exercising a given path, the variable domains are broken down into overlapping subregions in such a way that the resultant subregions either exercise or deviate from the path. To this aim, an incremental method is applied to detect the subregions, covering the longest subpaths from the start of the given path. The detected subdomain is further subdivided, and this process is repeated as far as the path is fully covered. If no subdomain is detected, the method is backtracked. The backtrack begins with the subdomain covering the longest subpath at the beginning of the given path, but this time the subdomain is divided into relatively smaller subregions, compared with the last time. A directed acyclic graph representation of each input variable domain is used to ignore re-examination of those subdomains which deviate from the path. Conducted experiments reveal that our proposed domain-oriented algorithm outperforms the existing path-oriented test data generation algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17

Similar content being viewed by others

References

  1. Hermadi, I., Lokan, C., Sarker, R.: Dynamic stopping criteria for search-based test data generation for path testing. Inf. Softw. Technol. 56(4), 395–407 (2014)

    Article  Google Scholar 

  2. Alshahwan, N., Harman, M.: Coverage and fault detection of the output-uniqueness test selection criteria. In: Proceedings of the 2014 International Symposium on Software Testing and Analysis. ACM (2014)

  3. Varshney, S., Mehrotra, M.: A differential evolution based approach to generate test data for data-flow coverage. In: Computing, Communication and Automation (ICCCA), 2016 International Conference on. IEEE (2016)

  4. Feyzi, F., Parsa, S.: Incorporating static fault-proneness analysis into statistical fault localization. J. Syst. Softw. 136, 39–58 (2018)

    Article  Google Scholar 

  5. Feyzi, F., Parsa, S.: A program slicing-based method for effective detection of coincidentally correct test cases. Computing (2018). https://doi.org/10.1007/s00607-018-0591-z

    MathSciNet  MATH  Google Scholar 

  6. Feyzi, F., Parsa, S.: Inforence: effective fault localization based on information-theoretic analysis and statistical causal inference. Front. Comput. Sci. (2018). https://doi.org/10.1007/s11704-017-6512-z

  7. Offutt, A.J., Jin, Z., Pan, J.: The dynamic domain reduction procedure for test data generation. Softw. Pract. Exp. 29(2), 167–93 (1999)

    Article  Google Scholar 

  8. Baldoni, R., Coppa, E., D’Elia, D.C., Demetrescu, C., Finocchi, I.: A survey of symbolic execution techniques. ArXiv preprint arXiv:1610.00502 (2016)

  9. Gotlieb, A., Petit, M.: Constraint reasoning in path-oriented random testing. In: Computer Software and Applications, 2008. COMPSAC’08. 32nd Annual IEEE International. IEEE (2008)

  10. Gotlieb, A., Petit, M.: Path-oriented random testing. In: Proceedings of the 1st International Workshop on Random Testing. ACM (2006)

  11. Gotlieb, A., Petit, M.: A uniform random test data generator for path testing. J. Syst. Softw. 83(12), 2618–2626 (2010)

    Article  Google Scholar 

  12. Stapleton, G.: A survey of reasoning systems based on Euler diagrams. Electron. Notes Theor. Comput. Sci. 134, 127–151 (2005)

    Article  MATH  Google Scholar 

  13. Chow, S., Ruskey, F.: Drawing area-proportional Venn and Euler diagrams. In: International Symposium on Graph Drawing, vol. 2912 (2003)

  14. Swoboda, N., Allwein, G.: Using DAG transformations to verify Euler/Venn homogeneous and Euler/Venn FOL heterogeneous rules of inference. Softw. Syst. Model 3(2), 136–149 (2004)

    Article  Google Scholar 

  15. Swoboda, N.: Implementing Euler/Venn reasoning systems. In: Diagrammatic Representation and Reasoning, pp. 371–386. Springer, London (2002)

  16. Su, T., et al.: A survey on data-flow testing. ACM Comput. Surv. (CSUR) 50(1), 5 (2017)

    Article  Google Scholar 

  17. Galeotti, J.P., Fraser, G., Arcuri, A.: Improving search-based test suite generation with dynamic symbolic execution. In: Software Reliability Engineering (ISSRE), 2013 IEEE 24th International Symposium on. IEEE (2013)

  18. Zhang, Z., et al.: An empirical study on constraint optimization techniques for test generation. Sci. China Inf. Sci. 60(1), 012105 (2017)

    Article  Google Scholar 

  19. Ali, S., et al.: Improving the performance of OCL constraint solving with novel heuristics for logical operations: a search-based approach. Empir. Softw. Eng. 21(6), 2459–2502 (2016)

    Article  Google Scholar 

  20. Kempka, J., McMinn, P., Sudholt, D.: Design and analysis of different alternating variable searches for search-based software testing. Theor. Comput. Sci. 605, 1–20 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  21. Korel, B.: Automated software test data generation. IEEE Trans. Softw. Eng. 16(8), 870–879 (1990)

    Article  Google Scholar 

  22. Malhotra, R., et al.: Comparison of search based techniques for automated test data generation. Int. J. Comput. Appl. 95(23), 4–8 (2014)

    Google Scholar 

  23. Suresh, Y., Rath, S.K.: A genetic algorithm based approach for test data generation in basis path testing. ArXiv preprint arXiv:1401.5165 (2014)

  24. Bueno, P.M.S., Jino, M., Wong, W.E.: Diversity oriented test data generation using metaheuristic search techniques. Inf. Sci. 259, 490–509 (2014)

    Article  Google Scholar 

  25. Varshney, S., Mehrotra, M.: Search based software test data generation for structural testing: a perspective. ACM SIGSOFT Softw. Eng. Notes 38(4), 1–6 (2013)

    Article  Google Scholar 

  26. Feyzi, F., Parsa, S.: Bayes-TDG: effective test data generation using Bayesian belief network: towards failure-detection effectiveness and maximum coverage. IET Softw (2018). https://doi.org/10.1049/iet-sen.2017.0112

    Google Scholar 

  27. Nikravan, E., Feyzi, F., Parsa, S.: Enhancing path-oriented test data generation using adaptive random testing techniques. In: Knowledge-Based Engineering and Innovation (KBEI), 2015 2nd International Conference on. IEEE (2015)

  28. Ferguson, R., Korel, B.: The chaining approach for software test data generation. ACM Trans. Softw. Eng. Methodol. 5(1), 63–86 (1996)

    Article  Google Scholar 

  29. Korel, B.: Dynamic method for software test data generation. Softw. Test. Verif. Reliab. 2(4), 203–213 (1992)

    Article  Google Scholar 

  30. Godefroid P., Klarlund N., Sen K.: DART: directed automated random testing. In: ACM Sigplan Notices, vol. 40. No. 6. ACM (2005)

  31. Sen, K., Marinov, D., Agha, G.: CUTE: a concolic unit testing engine for C. In: ACM SIGSOFT Software Engineering Notes, vol. 30, no. 5. ACM (2005)

  32. Tillmann, N., De Halleux, J.: Pex–white box test generation for. net. In: Tests and Proofs, pp. 134–153 (2008)

  33. Bottaci, L.: Instrumenting programs with flag variables for test data search by genetic algorithm. In: Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation. Morgan Kaufmann Publishers Inc. (2002)

  34. Harman, M., Jones, B.F.: Search-based software engineering. Inf. Softw. Technol. 43(14), 833–839 (2001)

    Article  Google Scholar 

  35. Huang, J.C.: Detection of data flow anomaly through program instrumentation. IEEE Trans. Softw. Eng. 5(3), 226–236 (1979)

    Article  MATH  Google Scholar 

  36. Fraser, G., Arcuri, A.: Evolutionary generation of whole test suites. In: Quality Software (QSIC), 2011 11th International Conference on. IEEE (2011)

  37. Anand, S., P̆as̆areanu, C.S., Visser, W.: JPF-SE: A symbolic execution extension to Java PathFinder. In: Proceedings of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’07), pp. 134–138. Springer, Berlin (2007)

  38. Jussien, N., Rochart, G., Lorca, X.: Choco: an open source java constraint programming library. In: CPAIOR’08 Workshop on Open-Source Software for Integer and Contraint Programming (OSSICP’08) (2008)

  39. Zhao, R., Lyu, M.R., Min, Y.: Automatic string test data generation for detecting domain errors. Softw. Test. Verif. Reliab. 20(3), 209–236 (2010)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Engineering, Iran University of Science and Technology, Tehran, Iran

    Esmaeel Nikravan & Saeed Parsa

Authors
  1. Esmaeel Nikravan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Saeed Parsa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Saeed Parsa.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nikravan, E., Parsa, S. A reasoning-based approach to dynamic domain reduction in test data generation. Int J Softw Tools Technol Transfer 21, 351–364 (2019). https://doi.org/10.1007/s10009-018-0493-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10009-018-0493-6

Keywords

Search

Navigation