Document Open Access Logo

Building High Strength Mixed Covering Arrays with Constraints

Authors Carlos Ansótegui , Jesús Ojeda , Eduard Torres

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.12.pdf
  • Filesize: 0.78 MB
  • 17 pages

Document Identifiers

Author Details

Carlos Ansótegui
  • Logic & Optimization Group (LOG), University of Lleida, Spain
Jesús Ojeda
  • Logic & Optimization Group (LOG), University of Lleida, Spain
Eduard Torres
  • Logic & Optimization Group (LOG), University of Lleida, Spain

Funding

Supported by MICINNs PROOFS (PID2019-109137GB-C21) and FPU fellowship (FPU18/ 02929).

Cite As Get BibTex

Carlos Ansótegui, Jesús Ojeda, and Eduard Torres. Building High Strength Mixed Covering Arrays with Constraints. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CP.2021.12

Abstract

Covering arrays have become a key piece in Combinatorial Testing. In particular, we focus on the efficient construction of Covering Arrays with Constraints of high strength. SAT solving technology has been proven to be well suited when solving Covering Arrays with Constraints. However, the size of the SAT reformulations rapidly grows up with higher strengths. To this end, we present a new incomplete algorithm that mitigates substantially memory blow-ups. The experimental results confirm the goodness of the approach, opening avenues for new practical applications.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
Keywords
  • Combinatorial Testing
  • Covering Arrays
  • Maximum Satisfiability

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Carlos Ansótegui and Felip Manyà. Mapping problems with finite-domain variables into problems with boolean variables. In SAT 2004 - The Seventh International Conference on Theory and Applications of Satisfiability Testing, 10-13 May 2004, Vancouver, BC, Canada, Online Proceedings, pages 1-15, 2004. Google Scholar
  2. Carlos Ansótegui, Felip Manyà, Jesus Ojeda, Josep M. Salvia, and Eduard Torres. Incomplete maxsat approaches for combinatorial testing. arXiv, abs/2105.12552, 2021. URL: http://arxiv.org/abs/2105.12552.
  3. Carlos Ansótegui, Jesus Ojeda, António Pacheco, Josep Pon, Josep M. Salvia, and Eduard Torres. Optilog: A framework for sat-based systems. In Chu-Min Li and Felip Manyà, editors, Theory and Applications of Satisfiability Testing - SAT 2021 - 24th International Conference, Barcelona, Spain, July 5-9, 2021, Proceedings, volume 12831 of Lecture Notes in Computer Science, pages 1-10. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-80223-3_1.
  4. Carlos Ansótegui, Idelfonso Izquierdo, Felip Manyà, and José Torres Jiménez. A max-sat-based approach to constructing optimal covering arrays. Frontiers in Artificial Intelligence and Applications, 256:51-59, 2013. Google Scholar
  5. Fahiem Bacchus, Matti Järvisalo, and Ruben Martins. MaxSAT Evaluation 2019 : Solver and Benchmark Descriptions. Technical Report Department of Computer Science Report Series B-2019-2, University of Helsinki, 2019. Google Scholar
  6. Mutsunori Banbara, Haruki Matsunaka, Naoyuki Tamura, and Katsumi Inoue. Generating combinatorial test cases by efficient sat encodings suitable for cdcl sat solvers. In Christian G. Fermüller and Andrei Voronkov, editors, Logic for Programming, Artificial Intelligence, and Reasoning, pages 112-126, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  7. Armin Biere. Lingeling, plingeling and treengeling entering the sat competition 2013. In SAT Competition 2013, 2013. Google Scholar
  8. Armin Biere. CaDiCaL at the SAT Race 2019. In Marijn Heule, Matti Järvisalo, and Martin Suda, editors, Proc. of SAT Race 2019 - Solver and Benchmark Descriptions, volume B-2019-1 of Department of Computer Science Series of Publications B, pages 8-9. University of Helsinki, 2019. Google Scholar
  9. Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors. Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications. IOS Press, 2009. Google Scholar
  10. Mehra N. Borazjany, Linbin Yu, Yu Lei, Raghu Kacker, and Rick Kuhn. Combinatorial testing of ACTS: A case study. In Fifth IEEE International Conference on Software Testing, Verification and Validation, ICST 2012, Montreal, QC, Canada, April 17-21, 2012, pages 591-600, 2012. Google Scholar
  11. Renée C. Bryce, Charles J. Colbourn, and Myra B. Cohen. A framework of greedy methods for constructing interaction test suites. In 27th International Conference on Software Engineering (ICSE 2005), 15-21 May 2005, St. Louis, Missouri, USA, pages 146-155, 2005. Google Scholar
  12. Myra B Cohen, Matthew B Dwyer, and Jiangfan Shi. Constructing interaction test suites for highly-configurable systems in the presence of constraints: A greedy approach. IEEE Transactions on Software Engineering, 34(5):633-650, 2008. Google Scholar
  13. Jacek Czerwonka. Pairwise testing in real world. In Proc. of the Twenty-fourth Annual Pacific Northwest Software Quality Conference, 10-11 October 2006, Portland, Oregon, pages 419-430, 2006. Google Scholar
  14. Feng Duan, Yu Lei, Linbin Yu, Raghu N. Kacker, and D. Richard Kuhn. Optimizing ipog’s vertical growth with constraints based on hypergraph coloring. In 2017 IEEE International Conference on Software Testing, Verification and Validation Workshops, ICST Workshops 2017, Tokyo, Japan, March 13-17, 2017, pages 181-188, 2017. Google Scholar
  15. Niklas Eén and Niklas Sörensson. Translating Pseudo-Boolean Constraints into SAT. Journal on Satisfiability, Boolean Modeling and Computation, 2(1-4):1-26, January 2006. Publisher: IOS Press. Google Scholar
  16. Ian P Gent and Peter Nightingale. A new encoding of alldifferent into sat. In International Workshop on Modelling and Reformulating Constraint Satisfaction, pages 95-110, 2004. Google Scholar
  17. Arnaud Gotlieb, Aymeric Hervieu, and Benoit Baudry. Minimum pairwise coverage using constraint programming techniques. In 2012 IEEE Fifth International Conference on Software Testing, Verification and Validation, pages 773-774, 2012. URL: https://doi.org/10.1109/ICST.2012.174.
  18. Aymeric Hervieu, Dusica Marijan, Arnaud Gotlieb, and Benoit Baudry. Practical minimization of pairwise-covering test configurations using constraint programming. Information and Software Technology, 71:129-146, 2016. URL: https://doi.org/10.1016/j.infsof.2015.11.007.
  19. Brahim Hnich, Steven Prestwich, and Evgeny Selensky. Constraint-based approaches to the covering test problem. In Boi V. Faltings, Adrian Petcu, François Fages, and Francesca Rossi, editors, Recent Advances in Constraints, pages 172-186, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  20. Brahim Hnich, Steven D. Prestwich, Evgeny Selensky, and Barbara M. Smith. Constraint Models for the Covering Test Problem. Constraints, 11(2):199-219, July 2006. Google Scholar
  21. Serdar Kadioglu. Column generation for interaction coverage in combinatorial software testing, 2017. URL: http://arxiv.org/abs/1712.07081.
  22. D. Richard Kuhn, Dolores R. Wallace, and Albert M. Gallo. Software fault interactions and implications for software testing. IEEE Trans. Software Eng., 30(6):418-421, 2004. Google Scholar
  23. Daniel Le Berre and Anne Parrain. The Sat4j library, release 2.2. Journal on Satisfiability, Boolean Modeling and Computation, 7(2-3):59-64, 2010. Publisher: IOS Press. Google Scholar
  24. Elizabeth Maltais and Lucia Moura. Finding the best CAFE is np-hard. In LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings, pages 356-371, 2010. Google Scholar
  25. Toru Nanba, Tatsuhiro Tsuchiya, and Tohru Kikuno. Using satisfiability solving for pairwise testing in the presence of constraints. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E95.A(9):1501-1505, 2012. Google Scholar
  26. Changhai Nie and Hareton Leung. A survey of combinatorial testing. ACM Computing Surveys (CSUR), 43(2):1-29, 2011. Google Scholar
  27. Itai Segall, Rachel Tzoref-Brill, and Eitan Farchi. Using binary decision diagrams for combinatorial test design. In Proceedings of the 2011 International Symposium on Software Testing and Analysis, page 254–264, New York, NY, USA, 2011. Association for Computing Machinery. Google Scholar
  28. Evgeny Selensky. CSPLib problem 045: The covering array problem. URL: http://www.csplib.org/Problems/prob045.
  29. Akihisa Yamada, Armin Biere, Cyrille Artho, Takashi Kitamura, and Eun-Hye Choi. Greedy combinatorial test case generation using unsatisfiable cores. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering, ASE 2016, page 614–624, New York, NY, USA, 2016. Association for Computing Machinery. Google Scholar
  30. Akihisa Yamada, Takashi Kitamura, Cyrille Artho, Eun-Hye Choi, Yutaka Oiwa, and Armin Biere. Optimization of combinatorial testing by incremental SAT solving. In 8th IEEE International Conference on Software Testing, Verification and Validation, ICST 2015, Graz, Austria, April 13-17, 2015, pages 1-10, 2015. Google Scholar
  31. L. Yu, F. Duan, Y. Lei, R. N. Kacker, and D. R. Kuhn. Constraint handling in combinatorial test generation using forbidden tuples. In 2015 IEEE Eighth International Conference on Software Testing, Verification and Validation Workshops (ICSTW), pages 1-9, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact