Review Articles

Combinatorial testing: using blocking to assign test cases for validating complex software systems

Ryan Lekivetz ,

JMP Division of SAS, Cary, NC, USA

Joseph Morgan

JMP Division of SAS, Cary, NC, USA

Pages 114-121 | Received 14 Sep. 2020, Accepted 12 Mar. 2021, Published online: 06 Apr. 2021,
  • Abstract
  • Full Article
  • References
  • Citations


Testing complex software systems is an extraordinarily difficult task. Test engineers are faced with the challenging prospect of ensuring that a software system satisfies its requirements while working within a strict budget. Choosing a test suite for such an endeavour can be framed as a design of experiments problem. Combinatorial testing is a software testing methodology that may be viewed as a design of experiments approach to addressing the software testing challenge. We extend this methodology by introducing the concept of blocking factors for a test suite. We provide an example, using an open source software library, to illustrate our extension. Advantages of considering blocks are discussed, both in the design as well as after test execution, when fault localisation may be necessary.


  1. Barr, E. T., Harman, M., McMinn, P., Shahbaz, M., & Yoo, S. (2014). The oracle problem in software testing: A survey. IEEE Transactions on Software Engineering41(5), 507–525. [Crossref][Web of Science ®], [Google Scholar]
  2. Baysal, O., Godfrey, M. W., & Cohen, R. (2009). A bug you like: A framework for automated assignment of bugs. In 2009 IEEE 17th International Conference on Program Comprehension (pp. 297–298). IEEE. [Crossref], [Google Scholar]
  3. Beizer, B. (2003). Software testing techniques. Dreamtech Press. [Google Scholar]
  4. Chen, T., & Guestrin, C. (2016). Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM Sigkdd International Conference on Knowledge Discovery and Data Mining (pp. 785–794). ACM. [Crossref], [Google Scholar]
  5. Cohen, M. B., Dwyer, M. B., & Shi, J. (2007). Interaction testing of highly-configurable systems in the presence of constraints. In Proceedings of the 2007 International Symposium on Software Testing and Analysis (pp. 129–139). ACM. [Crossref], [Google Scholar]
  6. Cohen, M. B., Gibbons, P. B., Mugridge, W. B., Colbourn, C. J., & Collofello, J. S. (2003). A variable strength interaction testing of components. In Proceedings 27th Annual International Computer Software and Applications Conference. Compac 2003 (pp. 413–418). IEEE. [Crossref], [Google Scholar]
  7. Dalal, S. R., & Mallows, C. L. (1998). Factor-covering designs for testing software. Technometrics40(3), 234–243. [Taylor & Francis Online][Web of Science ®], [Google Scholar]
  8. Danziger, P., Mendelsohn, E., Moura, L., & Stevens, B. (2009). Covering arrays avoiding forbidden edges. Theoretical Computer Science410(52), 5403–5414. [Crossref][Web of Science ®], [Google Scholar]
  9. Ghandehari, L. S., Lei, Y., Kung, D., Kacker, R., & Kuhn, R. (2013, November). Fault localization based on failure-inducing combinations. In 2013 IEEE 24th International Symposium on Software Reliability Engineering (ISSRE) (pp. 168–177). IEEE. [Crossref], [Google Scholar]
  10. Harman, M., Jia, Y., & Zhang, Y. (2015). Achievements, open problems and challenges for search based software testing. In 2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST) (pp. 1–12). IEEE. [Crossref], [Google Scholar]
  11. Kuhn, D. R., Wallace, D. R., & Gallo, A. M. (2004, June). Software fault interactions and implications for software testing. IEEE Transactions on Software Engineering30(6), 418–421. [Crossref][Web of Science ®], [Google Scholar]
  12. Lekivetz, R., & Morgan, J. (2020). Covering arrays: Using prior information for construction, evaluation and tofacilitate fault localization. Journal of Statistical Theory and Practice14(1), 7. [Crossref][Web of Science ®], [Google Scholar]
  13. Morgan, J. (2018). Combinatorial testing: An approach to systems and software testing based on covering arrays. Analytic Methods in Systems and Software Testing, 131–158. [Crossref], [Google Scholar]
  14. Morgan, J., Lekivetz, R., & Donnelly, T. (2017). Covering arrays: Evaluating coverage and diversity in the presence of disallowed combinations. In 2017 IEEE 28th Annual Software Technology Conference (STC) (pp. 1–4). IEEE. [Crossref], [Google Scholar]
  15. Myers, G. J., Badgett, T., Thomas, T. M., & Sandler, C. (2004). The art of software testing (Vol. 2). Wiley Online Library. [Google Scholar]
  16. Qian, P. Z., & Wu, C. J. (2009). Sliced space-filling designs. Biometrika96(4), 945–956. [Crossref][Web of Science ®], [Google Scholar]
  17. Sarkar, K., & Colbourn, C. J. (2019). Two-stage algorithms for covering array construction. Journal of Combinatorial Designs27(8), 475–505. [Crossref][Web of Science ®], [Google Scholar]