Factorials Experiments, Covering Arrays, and Combinatorial Testing | Mathematics in Computer Science Skip to main content
Springer Nature Link
Log in

Factorials Experiments, Covering Arrays, and Combinatorial Testing

  • Published:
Mathematics in Computer Science Aims and scope Submit manuscript

A Correction to this article was published on 10 May 2021

This article has been updated

Abstract

In the twenty-first century, our life will increasingly depend on software-based products and complex interconnected systems. Thus, the quality and security of software-based systems is a world-wide concern. Combinatorial testing is a versatile methodology for finding errors (bugs) and vulnerabilities in software-based systems. This paper offers a review of combinatorial testing. Combinatorial testing (CT) methods evolved from investigations which looked like factorial experiments (FE) with pass/fail outcomes. We will discuss the similarities and differences between FE and CT. Use of CT for detecting errors (bugs) in software-based systems has gained significant interest from the international software testing community. Many successful results have been reported from the use of CT to detect software errors in aerospace, automotive, defense, cybersecurity, electronic medical systems, and financial service industries. Now, combinatorial testing methods are being increasingly used to investigate vulnerabilities in software-based systems. Combinatorial testing could be useful in detecting errors and security vulnerabilities in Internet of Things, Autonomous Systems, and Artificially Intelligent Software.

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

Similar content being viewed by others

Change history

References

  1. ACM Forum on Risks (Website) (http://catless.ncl.ac.uk/Risks/)

  2. Adee, S.: The hunt for the kill switch. IEEE Spectrum 45, 34–39 (2008). https://doi.org/10.1109/MSPEC.2008.4505310

    Article  Google Scholar 

  3. Altinger, H., Wotawa, F., Schurius, M.: Testing methods used in the automotive industry: results from a survey. In: Proceedings of the 2014 Workshop on Joining AcadeMiA and Industry Contributions to Test Automation and Model-Based Testing (JAMAICA 2014), San Jose, CA, USA, July 21, 2014, pp. 1-6 (2014). https://doi.org/10.1145/2631890.2631891

  4. Ammann, P., Offutt, J.: Introduction to Software Testing. Cambridge University Press, Cambridge (2017)

    Google Scholar 

  5. Arkin, B., Stender, S., McGraw, G.: Software penetration testing. IEEE Secur. Privacy 3, 84–87 (2005). https://doi.org/10.1109/MSP.2005.23

    Article  Google Scholar 

  6. Baah, G., Podgurski, A., Harrold, M.: Causal inference for statistical fault localization. In; Proceedings of the 2010 ACM International Symposium on Software Testing and Analysis (ISSTA), Trento, Italy, July 12-16, 2010, pp. 73–84 (2010). https://doi.org/10.1145/1831708.1831717

  7. Barr, E.T., Harman, M., McMinn, P., Shahbaz, M., Yoo, S.: The oracle problem in software testing: a survey. IEEE Trans. Softw. Eng. 41, 507–525 (2015). https://doi.org/10.1109/TSE.2014.2372785

    Article  Google Scholar 

  8. Bell, K.Z., Vouk, M.A.: On effectiveness of pairwise methodology for testing network-centric software, Proceedings of the 2005 International Conference on Information & Communication Technology, Cairo, Egypt, December 5-6, 2005, pp. 221-235 (2005). https://doi.org/10.1109/ITICT.2005.1609626

  9. Bertolino, A.: Software testing research: achievements, challenges, dreams. In: Proceedings of Future of Software Engineering (FOSE), Minneapolis, MN, USA, May 23–25 (2007). https://doi.org/10.1109/FOSE.2007.25

  10. Biggio, B., Roli, F.: Wild patterns: ten years after the rise of adversarial machine learning. Pattern Recognit. 84, 317–331 (2018). https://doi.org/10.1016/j.patcog.2018.07.023

    Article  Google Scholar 

  11. Bonn, J., Fögen, K., Lichter, H.: A framework for automated combinatorial test generation, execution, and fault characterization. In: Proceedings of the 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Xian, China, April 23, 2019, pp. 224–233 (2019). https://doi.org/10.1109/ICSTW.2019.00057

  12. Box, G.E.P., Hunter, W.G., Hunter, J.S.: Statistics for Experimenters. Wiley, New York (1978)

    MATH  Google Scholar 

  13. Box, G.E.P., Draper, N.R.: Empirical Model Building and Response Surfaces. Wiley, New York (1987)

    MATH  Google Scholar 

  14. Brownlie, R., Prowse, J., Phadke, M.S.: Robust testing of AT&T PMX/Starmail using OATS. AT&T Tech. J. 71, 41–47 (1992). https://doi.org/10.1002/j.1538-7305.1992.tb00164.x

    Article  Google Scholar 

  15. Bush, K.A.: Orthogonal arrays of index unity. Ann. Math. Stat. 23, 426–434 (1952)

    Article  MathSciNet  Google Scholar 

  16. Chandrasekaran, J., Feng, H., Lei, Y., Kuhn, D.R., Kacker, R.N.: Applying combinatorial testing to data mining algorithms. In: Proceedings of the 2017 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Tokyo, Japan, March 13–17, 2017, pp. 253–261 (2017). https://doi.org/10.1109/ICSTW.2017.46

  17. Chetouane, N., Klampfl, L., Wotawa, F.: Investigating the effectiveness of mutation testing tools in the context of deep neural networks, In: Rojas, I., Joya, G., Catala, A. (eds.), Advances in Computational Intelligence. IWANN 2019. Lecture Notes in Computer Science, 11506, pp. 766–777. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-20521-8_63

  18. Chilenski, J.J., Miller, S.P.: Applicability of modified condition/decision coverage to software testing. Softw. Eng. J. 9, 193–200 (1994). https://doi.org/10.1049/sej.1994.0025

    Article  Google Scholar 

  19. Cochran, W.G., Cox, G.M.: Experimental Designs, 2nd edn. Wiley, New York (1957)

    MATH  Google Scholar 

  20. Cohen, D.M., Dalal, S.R., Kajla, A., Patton, G.C.: The automatic efficient test generator (AETG) system. In: Proceedings of the 1994 IEEE International Symposium on Software, Reliability Engineering, Monterey, CA, USA, November 6–9, 1994, pp. 303–309 (1994). https://doi.org/10.1109/ISSRE.1994.341392

  21. Cohen, D.M., Dalal, S.R., Parelius, J., Patton, G.C.: The combinatorial design approach to automatic test generation. IEEE Softw. 13, 83–89 (1996). https://doi.org/10.1109/52.536462

    Article  Google Scholar 

  22. Cohen, D.M., Dalal, S.R., Fredman, M.L., Patton, G.C.: The AETG system: an approach to testing based on combinatorial design. IEEE Trans. Softw. Eng. 23, 437–444 (1997). https://doi.org/10.1109/32.605761

    Article  Google Scholar 

  23. Cohen, M.B., Gibbons, P.B., Mugridge, W.B., Colbourn, C.J.: Constructing test suites for interaction testing. In: Proceedings of the 2003 International Conference on Software Engineering (ICSE), May 3–10, 2003, Portland, OR, USA, pp. 38–48 (2003). https://doi.org/10.1109/ICSE.2003.1201186

  24. Colbourn (Website) http://www.public.asu.edu/_ccolbou/src/tabby/catable.html

  25. Colbourn, C.J.: Combinatorial aspects of covering arrays. Le Matematiche 59, 121–167 (2004)

    MathSciNet  MATH  Google Scholar 

  26. Colbourn, C.J., Dinitz, J.H.: The CRC Handbook of Combinatorial Designs, 2nd edn. CRC Press, Boca Raton (2010)

    Book  Google Scholar 

  27. Colbourn, C.J., McClary, D.W.: Locating and detecting arrays for interaction faults. J. Comb. Optim. 15, 17–48 (2008). https://doi.org/10.1007/s10878-007-9082-4

    Article  MathSciNet  MATH  Google Scholar 

  28. Colbourn, C.J., Syrotiuk, V.R.: Coverage, location, detection, and measurement. In: Proceedings of the 2016 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Chicago, IL, USA, April 11–15, 2016, pp. 19–25 (2016). https://doi.org/10.1109/ICSTW.2016.38

  29. Cui, K., Zhou, K., Qiu, T., Li, M., Yan, L.: A hierarchical combinatorial testing method for smart phone software in wearable IoT systems. Comput. Electr. Eng. 61, 250–265 (2017). https://doi.org/10.1016/j.compeleceng.2017.06.004

    Article  Google Scholar 

  30. Czerwonka (Website) http://www.pairwise.org

  31. Dominka, S., Mandl, M., Dubner, M., Ertl, D.: Using combinatorial testing for distributed automotive features: applying combinatorial testing for automated feature-interaction-testing. In: Proceedings of the 2018 IEEE eighth Annual Computing and Communication Workshop and Conference (CCWC), Las Vegas, NV, USA, January 8–10, 2018, pp. 490–495 (2018). https://doi.org/10.1109/CCWC.2018.8301632

  32. Durumeric, Z., Kasten, J., Adrian, D., Halderman, J.A., Bailey, M., Li, F., Weaver, N., Amann, J., Beekman, J., Payer, M., Paxson, V.: The matter of Heartbleed. In: Proceedings of the 2014 ACM Internet Measurement Conference (IMC), Vancouver, Canada, November 5–7, 2014, pp. 475–488 (2014). https://doi.org/10.1145/2663716.2663755

  33. Fifo, M., Enoiu, E., Afzal, W.: On measuring combinatorial coverage of manually created test cases for industrial software. In: Proceedings of the 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Xian, China, April 22–23, 2019, pp. 264–267 (2019). https://doi.org/10.1109/ICSTW.2019.00062

  34. Finelli, G.B.: NASA software failure characterization experiments. Reliab. Eng. Syst. Saf. 32, 155–169 (1991). https://doi.org/10.1016/0951-8320(91)_90052-9

    Article  Google Scholar 

  35. Fisher, R.A.: The Design of Experiments. Oliver and Boyd, London (1935)

    Google Scholar 

  36. Forbes, M., Lawrence, J.F., Lei, Y., Kacker, R.N., Kuhn, D.R.: Refining the in-parameter-order strategy for constructing covering arrays. J. Res. Natl. Inst. Stand. Technol. 113, 287–297 (2008)

    Article  Google Scholar 

  37. Freedman, D.A.: Statistical Models: Theory and Practice. Cambridge University Press, Cambridge (2005)

    Book  Google Scholar 

  38. Garn, B., Simos, D.E.: Eris: A tool for combinatorial testing of the Linux system call interface. In: Proceeding of the 2014 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Cleveland, OH, USA, March 31–April 4, 2014, pp. 58–67 (2014). https://doi.org/10.1109/ICSTW.2014.7

  39. Garn, B., Kapsalis, I. Simos, D.E., Winkler, S.: On the applicability of combinatorial testing to web application security testing: a case study. In: Proceedings of the 2014 ACM Workshop on Joining AcadeMiA and Industry Contributions to Test Automation and Model-Based Testing (JAMAICA 2014), San Jose, CA, USA, July 21, 2014, pp. 16–21 (2014). https://doi.org/10.1145/2631890.2631894

  40. Garn, B., Simos, D.E., Zauner, S., Kuhn, D.R., Kacker, R.N.: Browser fingerprinting using combinatorial sequence testing. In: Proceedings of the 6-th Annual Symposium on Hot Topics in the Science of Security (HotSoS 2019), Nashville, TN, USA, April 1–3, 2019, Article 7 (2019). https://doi.org/10.1145/3314058.3314062

  41. Garn, B., Würfl, F., Simos, D.E.: KERIS: a CT tool of the linux kernel with dynamic memory analysis capabilities. In: Strichman, O., Tzoref-Brill, R. (eds.), Hardware and Software: Verification and Testing. HVC 2017. Lecture Notes in Computer Science, 10629, pp. 225–228. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70389-3_17

  42. Ghandehari, L., Lei, Y., Kacker, R.N., Kuhn, D.R., Kung, D., Xie, T.: A combinatorial testing-based approach to fault localization. IEEE Trans. Softw. Eng. (TSE) 46, 616–645 (2019). https://doi.org/10.1109/TSE.2018.2865935

    Article  Google Scholar 

  43. Graybill, F.A.: Theory and Application of the Linear Statistical Model. Duxbury Press, North Scituate (1976)

    MATH  Google Scholar 

  44. Grindal, M., Offutt, J.: Input parameter modeling for combination strategies. In; Proceedings of the 2007 Conference on IASTED International Multi-Conference: Software Engineering, Innsbruck, Austria, February 13–15, 2007, pp. 255–260 (2007). https://dlnext.acm.org/doi/abs/10.5555/1332044.1332085

  45. Grindal, M., Offutt, J., Mellin, J.: Managing conflicts when using combination strategies to test software. In: Proceedings of the Australian Software Engineering Conference (ASWEC), Melbourne, Vic., Australia, April 10–13, 2007, pp. 255–264 (2007). https://doi.org/10.1109/ASWEC.2007.27

  46. Grochtmann, M., Grimm, K.: Classification trees for partition testing. Softw. Test. Verif. Reliab. 3, 63–82 (1993). https://doi.org/10.1002/stvr.4370030203

    Article  Google Scholar 

  47. Hartman, A., Raskin, L.: Problems and algorithms for covering arrays. Discrete Math. 284, 149–156 (2004). https://doi.org/10.1016/j.disc.2003.11.029

    Article  MathSciNet  MATH  Google Scholar 

  48. Hedayat, A.S., Sloane, N.J.A., Stufken, J.: Orthogonal Arrays: Theory and Applications. Springer, New York (1999)

    Book  Google Scholar 

  49. Hinkelmann, K., Kempthorne, O.: Design and Analysis of Experiments, vol. 1. Wiley, New York (1994)

    MATH  Google Scholar 

  50. Jin, W., Orso, A.: F3: fault localization for field failures. Proceedings of the 2013 ACM International Symposium on Software Testing and Analysis (ISSTA), Lugano, Switzerland, July 15–20, 2013, pp. 213–223 (2013). https://doi.org/10.1145/2483760.2483763

  51. Jones, J.A., Harrold, M.J.: Empirical evaluation of the tarantula automatic fault-localization technique. In: Proceeding of the 20-th IEEE/ACM International Conference on Automated Software Engineering (ASE), Long Beach, CA, USA, November 07–11, 200, pp. 273–282 (2005). https://doi.org/10.1145/1101908.1101949

  52. Kackar, R.N.: Off-line quality control, parameter design, and the Taguchi method (with comments and response). Journal of Quality Technology 17, 176–209 (1985). https://doi.org/10.1080/00224065.1985.11978964

    Article  Google Scholar 

  53. Kacker, R.N., Lagergren, E.S., Filliben, J.J.: Taguchi’s orthogonal arrays are classical designs of experiments. J. Res. Natl. Inst. Stand. Technol. 96, 577–591 (1991)

    Article  Google Scholar 

  54. Kampel, L., Simos, D.E.: Set-Based Algorithms for Combinatorial Test Set Generation. In: Wotawa, F., Nica, M., Kushik, N. (eds.), Testing Software and Systems. ICTSS 2016. Lecture Notes in Computer Science, 9976, pp. 231–240. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-47443-4_16

  55. Kempthorne, O.: The Design and Analysis of Experiments. Wiley, New York (1952)

    Book  Google Scholar 

  56. Khalsa, S., Labiche, Y.: An orchestrated survey of available algorithms and tools for combinatorial testing. In: Proceedings of the 2014 IEEE International Symposium on Software Reliability Engineering (ISSRE), Naples, Italy, November 3–6, 2014, pp. 323–334 (2014). https://doi.org/10.1109/ISSRE.2014.15

  57. Kitsos, P., Simos, D.E., Torres-Jimenez, J., Voyiatzis, A.G.: Exciting FPGA cryptographic Trojans using combinatorial testing. In; Proceedings of the 26th IEEE International Symposium on Software Reliability Engineering (ISSRE), Gaithersburg, MD, USA, November 2–5, 2015, pp. 69–76 (2015). https://doi.org/10.1109/ISSRE.2015.7381800

  58. Kleine, K., Simos, D.E.: An efficient design and implementation of the in-parameter-order algorithm. Math. Comput. Sci. 12, 51–67 (2018). https://doi.org/10.1007/s11786-017-0326-0

    Article  MathSciNet  MATH  Google Scholar 

  59. Kuhn, D.R., Kacker, R.N., Lei, Y.: Introduction to Combinatorial Testing. CRC Press, Boca Raton (2013)

    MATH  Google Scholar 

  60. Kuhn, D.R., Kacker, R.N., Lei, Y., Simos, D.E.: Input space coverage matters. IEEE Comput. 53, 37–44 (2020). https://doi.org/10.1109/MC.2019.2951980

    Article  Google Scholar 

  61. Kuhn, D.R., Raunak, M.S., Kacker, R.N.: It doesn’t have to be like this: cybersecurity vulnerability trends, IT professional,19 (November/December 2017), pp. 66–70 (2017). https://doi.org/10.1109/MITP.2017.4241462

  62. Kuhn, D.R., Reilly, M.J.: An investigation of the applicability of design of experiments to software testing. In: Proceedings of the 27-th NASA/IEEE Software Engineering Workshop, Goddard Space Flight Center, Greenbelt, MD, USA, December 5–6, 2002, pp. 91–95 (2002). https://doi.org/10.1109/SEW.2002.1199454

  63. Kuhn, D.R., Wallace, D.R., Gallo, A.M.: Software fault interactions and implications for software testing. IEEE Trans. Softw. Eng. 30, 418–421 (2004). https://doi.org/10.1109/TSE.2004.24

    Article  Google Scholar 

  64. Lawrence, J.F., Kacker, R.N., Lei, Y., Kuhn, D.R., Forbes, M.: A survey of binary covering arrays. Electron. J. Comb. 18, Article 84 (2011). https://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p84

  65. Lei, Y., Tai, K.C.: In-parameter order: a test generation strategy for pairwise testing. In: Proceedings of the 3rd IEEE International High Assurance Systems Engineering Symposium (HASE), Washington, DC, USA, November 13–14, 1998, pp. 254–261 (1998). https://doi.org/10.1109/HASE.1998.731623

  66. Lei, Y., Kacker, R., Kuhn, D., Okun, V., Lawrence, J.: IPOG/IPOG-D: efficient test generation for multi-way combinatorial testing. Softw. Test. Verif. Reliab. 18, 125–148 (2008). https://doi.org/10.1002/stvr.381

    Article  Google Scholar 

  67. Lejay, L.V., Shasha, D.E., Palenchar, P.M., Kouranov, A.Y., Cruikshank, A.A., Chou, M.F., Coruzzi, G.M.: Adaptive combinatorial design to explore large experimental spaces: approach and validation, Systems Biology, 1, pp. 206–212 (2004).https://www.ncbi.nlm.nih.gov/pubmed/17051692

  68. Li, D., Hu, L., Gao, R., Wong, W. E., Kuhn, D.R., Kacker, R.N.: Improving MC/DC and fault detection strength using combinatorial testing. In; Proceedings of the 2017 IEEE International Conference on Software Quality, Reliability, and Security (QRS 2017), Prague, Czech Republic, July 25–29, 2017, pp. 297–303 (2017). https://doi.org/10.1109/QRS-C.2017.131

  69. Li, N., Offutt, J.: Test oracle strategies for model-based testing. IEEE Trans. Softw. Eng. (TSE) 43, 372–395 (2017). https://doi.org/10.1109/TSE.2016.2597136

    Article  Google Scholar 

  70. Li, Y., Tao, J., Wotawa, F.: Ontology-based test generation for automated and autonomous driving functions. Inf. Softw. Technol. 117, Article 106200 (2020). https://doi.org/10.1016/j.infsof.2019.106200

  71. Li, X., Gao, R., Wong, W.E., Yang, C., Li, D.: Applying combinatorial testing in industrial settings. In: Proceedings of the 2016 IEEE International Conference on Software Quality, Reliability and Security (QRS), Vienna, Austria, August 1–3, 2016, Article 16378499 (2016). https://doi.org/10.1109/QRS.2016.16

  72. Lin, D.K.J., Draper, N.R.: Projection properties of Plackett and Burman designs. Technometrics 34, 423–428 (1992)

    Google Scholar 

  73. Lin, K.M., Kackar, R.N.: Optimizing the wave soldering process. Electronic Packaging & Production, February 1986, pp. 108–115 (1986). Reprinted in Dehnad, K. (eds) Quality Control, Robust Design, and the Taguchi Method, pp. 143–157. Springer, Boston, MA, 1989. https://doi.org/10.1007/978-1-4684-1472-1_7

  74. Lott, C., Jain, A., Dalal, S.: Modeling requirements for combinatorial software testing. ACM SIGSOFT Softw. Eng. Notes 30, 1–7 (2005). https://doi.org/10.1145/1082983.1083281

    Article  Google Scholar 

  75. Ma, L., Juefei-Xu, F., Xue, M., Li, B., Li, L., Liu, Y., Zhao, J.: DeepCT: tomographic combinatorial testing for deep learning systems. In: Proceedings of the 2019 IEEE 26th International Conference on Software Analysis, Evolution and Reengineering (SANER), Hangzhou, China, February 24–27, 2019, pp. 614–618 (2019). https://doi.org/10.1109/SANER.2019.8668044

  76. Mandl, R.: Orthogonal Latin squares: an application of experiment design to compiler testing. Commun. ACM 28, 1054–1058 (1985). https://doi.org/10.1145/4372.4375

    Article  Google Scholar 

  77. Mariani, L., Hao, D., Subramanyan, R., Zhu, H.: The central role of test automation in software quality assurance. Softw. Qual. J. 25, 797–802 (2017). https://doi.org/10.1007/s11219-017-9383-5

    Article  Google Scholar 

  78. Masuyama, M.: On difference sets for constructing orthogonal arrays of index two and strength two, Reports of Statistical Application Research, 5, pp. 27–34. Union of Japanese Scientists and Engineers (JUSE), Tokyo, Japan (1957)

  79. McCulloch, C.E., Searle, S.R.: Generalized, Linear, and Mixed Models. Wiley, New York (2001)

    MATH  Google Scholar 

  80. Memon, A., Banerjee, I., Nagarajan, A.: What test oracle should i use for effective GUI testing? In; Proceedings of the 18-th IEEE International Conference on Automated Software Engineering (ASE 2003), Montreal, Canada, October 6–10, 2003, pp. 164–173 (2003). https://doi.org/10.1109/ASE.2003.1240304

  81. Mercan, H., Javeed, A., Yilmaz, C.: Flexible combinatorial interaction testing. IEEE Trans. Softw. Eng. (2020). https://doi.org/10.1109/TSE.2020.3010317

    Article  Google Scholar 

  82. Miller, R.G.: Beyond ANOVA, Basic and Applied Statistics. Wiley, New York (1986)

    Google Scholar 

  83. Montgomery, D.C.: Design and Analysis of Experiments, 3rd edn. Wiley, New York (1991)

    MATH  Google Scholar 

  84. Mouha, N., Raunak, M.S., Kuhn, D.R., Kacker, R.N.: Finding bugs in cryptographic hash function implementations. IEEE Trans. Reliab. 67, 870–884 (2018). https://doi.org/10.1109/TR.2018.2847247

    Article  Google Scholar 

  85. Nie, C., Leung, H.: A survey of combinatorial testing. ACM Computing Surveys (CSUR), 43, Article 11 (2011). https://doi.org/10.1145/1883612.1883618

  86. Nie, C., Leung, H.: The minimal failure-causing schema of combinatorial testing. ACM Trans. Softw. Eng. Methodol. (TOSEM) 20, Article 15, (2011). https://doi.org/10.1145/2000799.2000801

  87. NIST Covering array tables (Website) https://math.nist.gov/coveringarrays/

  88. NIST Combinatorial testing page (Website) https://csrc.nist.gov/projects/automated-combinatorial-testing-for-software

  89. Niu, X., Nie, C., Lei, Y., Leung, H., Wang, X.: Identifying failure-causing schemas in the presence of multiple faults. IEEE Trans. Softw. Eng. 46, 141–162 (2020). https://doi.org/10.1109/TSE.2018.2844259

    Article  Google Scholar 

  90. Niu, X., Nie, C., Leung, H., Lei, Y., Wang, X., Xu, J., Wang, Y.: An interleaving approach to combinatorial testing and failure-inducing interaction identification. IEEE Trans. Softw. Eng. 46, 584–615 (2020). https://doi.org/10.1109/TSE.2018.2865772

    Article  Google Scholar 

  91. Ostrand, T., Balcer, M.: The category-partition method for specifying and generating functional tests. Commun. ACM 31, 676–686 (1988). https://doi.org/10.1145/62959.62964

    Article  Google Scholar 

  92. Panario, D., Saaltink, M., Stevens, B., Wevrick, D.: An extension of a construction of covering arrays. J. Comb. Des. 28, 842–861 (2020). https://doi.org/10.1002/jcd.21747

    Article  MathSciNet  MATH  Google Scholar 

  93. Patil, A.H.: Design and implementation of combinatorial testing based test suites for operating systems used for internet of things, Lulu.com (2019)

  94. Pearson, S., Campos, J., Just, R., Fraser, G., Abreu, R., Ernst, M.D., Pang, D., Keller, B.: Evaluating and improving fault localization. In: Proceedings of the 39th IEEE International Conference on Software Engineering (ICSE), Buenos Aires, Argentina, May 20–28, 2017, pp. 609–620 (2017). https://doi.org/10.1109/ICSE.2017.62

  95. Peters, D., Parnas, D.: Using test oracles generated from program documentation. IEEE Trans. Softw. Eng. 24, 161–173 (1998). https://doi.org/10.1109/32.667877

    Article  Google Scholar 

  96. Pezze, M., Zhang, C.: Chapter one—Automated test oracles: a survey. Adv. Comput. 95, 1–48 (2014). https://doi.org/10.1016/B978-0-12-800160-8.00001-2

    Article  Google Scholar 

  97. Plackett, R.L., Burman, J.P.: The design of optimum multifactorial experiments. Biometrika 33, 305–325 (1946). https://www.jstor.org/stable/pdf/2332195.pdf

  98. Raghavarao, D.: Constructions and Combinatorial Problems in Design of Experiments. Wiley, New York (1971)

    MATH  Google Scholar 

  99. Raktoe, B.L., Hedayat, A.S., Federer, W.T.: Factorial Designs. Wiley, New York (1981)

    MATH  Google Scholar 

  100. Rao, C.R.: Hypercubes of strength d leading to confounded designs of factorial experiments. Bull. Calc. A Math. Soc. 38, 67–68 (1946)

    MathSciNet  MATH  Google Scholar 

  101. Sato, S., Shimokawa, H.: Methods for setting software test parameters using the design of experiments method (in Japanese), Proceedings of 4th Symposium on Quality Control in Software, Union of Japanese Scientists and Engineers (JUSE), 1984, pp. 1–8 (1984)

  102. SBA-Research/CAgen (Website) https://matris.sba-research.org/tools/cagen

  103. Searle, S.R.: Linear Models. Wiley, New York (1971)

    MATH  Google Scholar 

  104. Segura, S., Fraser, G., Sanchez, A.B., Ruiz-Cortés, A.: A survey on metamorphic testing. IEEE Trans. Softw. Eng. 42, 805–824 (2016). https://doi.org/10.1109/TSE.2016.2532875

    Article  Google Scholar 

  105. Seidel, S.A., Sarkar, K., Colbourn, C.J., Syrotiuk, V.R.: Separating interaction effects using locating and detecting arrays. In: Iliopoulos, C., Leong, H., Sung, W.K. (eds.) Combinatorial Algorithms. IWOCA 2018. Lecture Notes in Computer Science, 10979, pp. 349–360. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94667-2_29

  106. Seiden, E.: On the problem of construction of orthogonal arrays. Ann. Math. Stat. 25, 151–156 (1954)

    Article  MathSciNet  Google Scholar 

  107. Shasha, D.E., Kouranov, A.Y., Lejay, L.V., Chou, M.F., Coruzzi, G.M.: Using combinatorial design to study regulation by multiple input signals. A tool for parsimony in the post-genomics era, Plant Physiology 127, 1590–1594 (2001). http://www.plantphysiol.org/content/127/4/1590

  108. Sherwood, G.B.: Effective testing of factor combinations, Proceedings of 3rd International Conference on Software Testing, Analysis and Review (STAR-1994), Washington, DC, USA, May 8–12, 1994, pp. 151–166 (1994). http://testcover.com/pub/background/star1994_paper.pdf

  109. Shimokawa, H.: Method of generating software test cases using the experimental design (in Japanese), Report on Software Engineering SIG, Information Processing Society of Japan, No.1984-SE-040 (1985)

  110. Simos, D.E., Bozic, J., Garn, B., Leithner, M., Duan, F., Kleine, K., Lei, Y., Wotawa, F.: Testing TLS using planning-based combinatorial methods and execution framework. Softw. Qual. J. 27, 703–729 (2019). https://doi.org/10.1007/s11219-018-9412-z

    Article  Google Scholar 

  111. Simos, D.E., Garn, B., Zivanovic, J., Leithner, M.: Practical combinatorial testing for XSS Detection using Locally Optimized Attack Models. In: Proceedings of the 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Xian, China, April 22–23, 2019, pp. 122–130 (2019). https://doi.org/10.1109/ICSTW.2019.00040

  112. Simos, D.E., Zivanovic, J., Leithner, M.: Automated combinatorial testing for detecting SQL vulnerabilities in web applications. In: Proceedings of the 14th International Workshop on Automation of Software Test, collocated with 41st ACM/IEEE International Conference on Software Engineering (ICSE), Montreal, Canada, May 27, 2019, pp 56–61 (2019). https://doi.org/10.1109/AST.2019.00014

  113. Simos, D.E., Kuhn, D.R., Voyiatzis, A., Kacker, R.N.: Combinatorial methods in security testing. IEEE Comput. 49, 80–83 (2016)

    Article  Google Scholar 

  114. Sloane, N.J.A.: (Website) http://neilsloane.com/oadir/index.html

  115. Sloane, N.J.A.: Covering arrays and intersecting codes. J. Comb. Des. 1, 51–63 (1973). https://doi.org/10.1002/jcd.3180010106

    Article  MathSciNet  MATH  Google Scholar 

  116. Smith, R., Jarman, D., Kuhn, D. R., Kacker, R. N., Simos, D., Kampel, L., Leithner, M., Gosney, G.: Applying combinatorial testing to large-scale data processing at Adobe. In: Proceedings of the 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Xian, China, April 22–23, 2019, pp.190–193 (2019). https://doi.org/10.1109/ICSTW.2019.00051

  117. Snedecor, G.W., Cochran, W.G.: Statistical Methods, 7th edn. Iowa State University Press, Ames (1980)

    MATH  Google Scholar 

  118. Su, T., Wu, K., Miao, W., Pu, G., He, J., Chen, Y., Su, Z.: A survey on data-flow testing. ACM Computing Surveys 50, Article 5 (2017). https://doi.org/10.1145/3020266

  119. Taguchi, G.: System of Experimental Design, Vol 1 and 2. Maruzen, Japan (in Japanese) (1977)

  120. Tai, K.C., Lei, Y.: A test generation strategy for pairwise testing. IEEE Transactions on Software Engineering 28, 109–111 (2002). https://doi.org/10.1109/32.979992

    Article  Google Scholar 

  121. Tao, J., Li, Y., Wotawa, F., Felbinger, H., Nica, M.: On the industrial application of combinatorial testing for autonomous driving functions. In: Proceedings of the 2019 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Xian, China, April 22–23, 2019, pp. 234-240 (2019). https://doi.org/10.1109/ICSTW.2019.00058

  122. Tatsumi, K.: Test-case design support system. In: Proceedings of the International Conference on Quality Control, Tokyo, Japan, pp. 615–620 (1987)

  123. Tatsumi, K., Watanabe, S., Takeuchi, Y., Shimokawa, H.: Conceptual support for test case design. In: Proceedings of 11th IEEE Computer Software and Applications Conference (COMPSAC), Tokyo, Japan, October 1987, pp. 285–290 (1987)

  124. Torres-Jimenez (Website) https://www.tamps.cinvestav.mx/~oc/

  125. Torres-Jimenez, Izquierdo-Marquez: Survey of covering arrays. In: Proceedings of 2013 IEEE International Symposium and Numeric Algorithms for Scientific Computing (SYNASC), Timisoara, Romania, September 23–26, 2013, pp. 20–27 (2013). https://doi.org/10.1109/SYNASC.2013.10

  126. Voas, J., Kuhn, D.R., Laplante, P.: Testing IoT systems. In: Proceedings of the 2018 IEEE Symposium on Service-Oriented System Engineering (SOSE), Bamberg, Germany, March 26–29, 2018, pp. 48–52 (2018). https://doi.org/10.1109/SOSE.2018.00015

  127. Wagner, M., Kleine, K., Simos, D.E., Kuhn, D.R., Kacker, R.N.: CAGEN: a fast combinatorial test generation tool with support for constraints and higher-index arrays. In: 2020 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Porto, Portugal, October 24–28, 2020, pp. 191–200 (2020). https://doi.org/10.1109/ICSTW50294.2020.00041

  128. Wallace, D.R., Kuhn, D.R.: Failure modes in medical device software: an analysis of 15 years of recall data. Int. J. Reliab. Qual. Saf Eng. 8, 351–371 (2001). https://doi.org/10.1142/S021853930100058X

    Article  Google Scholar 

  129. Wong, W., Gao, R., Li, Y., Abreu, R., Wotawa, F.: A survey on software fault localization. IEEE Trans. Softw. Eng. 42, 707–740 (2016). https://doi.org/10.1109/TSE.2016.2521368

    Article  Google Scholar 

  130. Wotawa, F.: On the automation of security testing. In: Proceedings of the 2016 IEEE International Conference on Software Security and Assurance (ICSSA), St. Polten, Austria, August 24–25, 2016, pp. 11–16 (2016). https://doi.org/10.1109/ICSSA.2016.9

  131. Wotawa, F., Peischl, B., Klueck, F., Nica, M.: Quality assurance methodologies for automated driving. e & i Elektrotechnik und Informationstechnik 135, 322–327 (2018). https://doi.org/10.1007/s00502-018-0630-7

    Article  Google Scholar 

  132. Wu, C.F., Hamada, M.S.: Experiments: Planning, Analysis, and Optimization, 2nd edn. Wiley, New York (2009)

    MATH  Google Scholar 

  133. Wu, H., Nie, C., Petke, J., Jia, Y., Harman, M.: Comparative analysis of constraint handling techniques for constrained combinatorial testing. IEEE Transactions on Software Engineering (Early Access) (2019). https://doi.org/10.1109/TSE.2019.2955687

  134. Xie, Q., Memon, A.: Designing and comparing automated test oracles for GUI-based software applications. ACM Trans. Softw. Eng. Methodol. (TOSEM) 16. Article 4 (2007). https://doi.org/10.1145/1189748.1189752

  135. Yan, J., Zhang, Jian: A backtracking search tool for constructing combinatorial test suites. J. Syst,. Softw. 81, 1681–1693 (2008). https://doi.org/10.1016/j.jss.2008.02.034

    Article  Google Scholar 

  136. Yang, J., Zhang, H., Fu, J.: A fuzzing framework based on symbolic execution and combinatorial testing. In: Proceedings of the 2013 IEEE International Conference on Green Computing and Communications and IEEE Internet of Things and IEEE Cyber, Physical and Social Computing, Beijing, China, August 20–23, 2013, pp. 2076-2080 (2013). https://doi.org/10.1109/GreenCom-iThings-CPSCom.2013.389

  137. Yilmaz, C., Cohen, M., Porter, A.: Covering arrays for efficient fault characterization in complex configuration spaces. IEEE Trans. Softw. Eng. (TSE) 32, 20–34 (2006). https://doi.org/10.1109/TSE.2006.8

    Article  Google Scholar 

  138. Yu, L., Lei, Y., Kacker, R.N., Kuhn, D.R.: ACTS: a combinatorial test generation tool. In: Proceedings of the 2013 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW), Luxembourg, March 18–22, 2013, pp. 370–375 (2013). https://doi.org/10.1109/ICST.2013.52

  139. Zeller, A., Hildebrandt, R.: Simplifying and isolating failure-inducing input. IEEE Trans. Softw. Eng.(TSE) 28, 183–200 (2002). https://doi.org/10.1109/32.988498

    Article  Google Scholar 

  140. Zhang, Z., Liu, X., Zhang, J.: Combinatorial testing on ID3v2 tags of MP3 files. In: Proceedings of the 2012 IEEE International Conference on Software Testing, Verification and Validation, Workshops (ICSTW), Montreal, QC, Canada, April 17–21, 2012, pp. 587–590 (2012). https://doi.org/10.1109/ICST.2012.145

  141. Zhang, Z., Zhang, J.: Characterizing failure-causing parameter interactions by adaptive testing. In; Proceedings of the 2011 ACM International Symposium on Software Testing and Analysis (ISSTA), Toronto, ON, Canada, July 17–21, 2011, pp. 331–341 (2011). https://doi.org/10.1145/2001420.2001460

  142. Zhivich, M., Cunnigham, R.: The real cost of software errors. IEEE Privacy Secur. 7, 87–90 (2009). https://doi.org/10.1109/MSP.2009.56

    Article  Google Scholar 

Download references

Acknowledgements

Feng Duan helped construct and verify covering arrays. We thank NIST reviewers Brad Alpert, Adam Pintar, and anonymous journal referees.

Author information

Authors and Affiliations

  1. National Institute of Standards and Technology, Gaithersburg, MD, 20899, USA

    Raghu N. Kacker & D. Richard Kuhn

  2. University of Texas at Arlington, Arlington, TX, 76019, USA

    Yu Lei

  3. SBA-Research, 1040, Vienna, Austria

    Dimitris E. Simos

Authors
  1. Raghu N. Kacker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D. Richard Kuhn
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yu Lei
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dimitris E. Simos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dimitris E. Simos.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Disclaimer Identification of any commercial products in this paper does not imply recommendation or endorsement by NIST.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kacker, R.N., Kuhn, D.R., Lei, Y. et al. Factorials Experiments, Covering Arrays, and Combinatorial Testing. Math.Comput.Sci. 15, 715–739 (2021). https://doi.org/10.1007/s11786-021-00502-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11786-021-00502-7

Keywords

Mathematics Subject Classification

Search

Navigation