Article

Constraint-Based approaches to the covering test problem

Authors:

Steven Prestwich,

Evgeny SelenskyAuthors Info & Claims

CSCLP'04: Proceedings of the 2004 joint ERCIM/CoLOGNET international conference on Recent Advances in Constraints

Pages 172 - 186

https://doi.org/10.1007/11402763_13

Published: 23 June 2004 Publication History

Abstract

Covering arrays have been studied for their applications to drug screening and software and hardware testing. In this paper, we model the problem as a constraint program. Our proposed models exploit non-binary (global) constraints, redundant modelling, channelling constraints, and symmetry breaking constraints. Our initial experiments show that with our best integrated model, we are able to either prove optimality of existing bounds or find new optimal values for arrays of moderate size. Local search on a SAT-encoding of the model is able to find improved bounds on larger problems.

References

[1]

S. Y. Boroday and I. S. Grunskii. Recursive Generation of Locally Complete Tests. Cybernetics and Systems Analysis 28:20-25, 1992.

[2]

B. Cha and K. Iwama. Adding New Clauses for Faster Local Search. Proceedings of the Fourteenth National Conference on Artificial Intelligence, American Association for Artificial Intelligence 1996, pp. 332-337.

Digital Library

[3]

C. Cheng, A. Dimitresku, and P. Schroeder. Generating Small Combinatorial Test Suites to Cover Input-Output Relationships. Third International Conference On Quality Software (QSIC), USA, 2003, pp. 76-83.

Digital Library

[4]

D. M. Cohen, S. R. Dalal, M. L. Fredman, and G. C. Patton. The AETG System: An Approach to Testing Based on Combinatorial Design. IEEE Transactions on Software Engineering 23:437-444, 1997.

Digital Library

[5]

D. M. Cohen, S. R. Dalal, J. Parelius, and G. C. Patton. The Combinatorial Design Approach to Automatic Test Generation. IEEE Software, 1996, pp. 83-86.

Digital Library

[6]

D. Z. Du and F. K. Wang. Combinatorial Group Testing and Its Applications. World Scientific, 1991.

[7]

P. Flener, A. M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, J. Pearson, and T. Walsh. Breaking Row and Column Symmetries in Matrix Models. P. van Hentenryck, editor, Proceedings of the Eighth International Conference on Principles and Practice of Constraint Programming, 2002, pp. 462-476.

Digital Library

[8]

P. Flener, A. M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, and T. Walsh. Matrix Modelling: Exploiting Common Patterns in Constraint Programming. A.M. Frisch, editor, Proceedings of the International Workshop on Reformulating Constraint Satisfaction Problems, 2002, pp. 27-41.

[9]

G. Friedman, A. Hartman, K. Nagin, T. Shiran. Projected State Machine Coverage for Software Testing. ACM SIGSOFT International Symposium on Software Testing and Analysis, Roma, Italy, ACM Press, 2002, pp. 134-143.

Digital Library

[10]

A. M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, and T. Walsh. Global Constraints for Lexicographic Orderings. P. van Hentenryck, editor, Proceedings of the Eighth International Conference on Principles and Practice of Constraint Programming, 2002, pp. 93-108.

Digital Library

[11]

A. Hartman and L. Raskin. Problems and Algorithms for Covering Arrays. Discrete Mathematics 284:149-156, 2004.

Digital Library

[12]

J. Huller. Reducing Time to Market With Combinatorial Design Method Testing. Proceedings of the 2000 International Council on Systems Engineering (INCOSE) Conference, 2000.

[13]

A. B. Kahng and S. Reda. Combinatorial Group Testing Methods for the BIST Diagnosis Problem.Proceedings of Asia and South Pacific Design Automation Conference, 2004.

Digital Library

[14]

K. Kask and R. Dechter. GSAT and Local Consistency. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, Morgan Kaufmann 1995, pp. 616-622.

Digital Library

[15]

N. Kobayashi. Design and Evaluation of Automatic Test Generation Strategies for Functional Testing of Software. PhD Thesis, Osaka University, 2002.

[16]

Y. Lei and K. C. Tai. In-Parameter Order: a Test Generation Strategy for Pairwise Testing. Third IEEE High Assurance Systems Engineering Symposium, 1998, pp. 254-161.

Digital Library

[17]

K. J. Nurmela. Lower Bounds on 2-Covering Arrays by Exhaustive Search. Twenty-Fifth Australasian Conference on Combinatorial Mathematics and Combinatorial Computing, 2000.

[18]

S. D. Prestwich. Negative Effects of Modeling Techniques on Search Performance. Annals of Operations Research 118:137-150, Kluwer Academic Publishers, 2003.

[19]

J.-C. Régin. Generalized Arc Consistency for Global Cardinality Constraints. Proceedings of the Eighth National Conference on Artificial Intelligence, 1996, pp. 25-32.

Digital Library

[20]

A. Renyi. Foundations of Probability. Wiley, New York, 1971.

[21]

B. Selman, H. Kautz, and B. Cohen. Noise Strategies for Improving Local Search. Twelfth National Conference on Artificial Intelligence, AAAI Press, 1994, pp. 337- 343.

Digital Library

[22]

B. Selman, H. Levesque, and D. Mitchell. A New Method for Solving Hard Satisfiability Problems. Tenth National Conference on Artificial Intelligence, MIT Press, 1992, pp. 440-446.

Digital Library

[23]

G. Seroussi and N. H. Bshouty. Vector Sets for Exhaustive Testing of Logic Circuits. IEEE Transactions Information Theory 34:513-522, 1988.

Digital Library

[24]

D. T. Tang and C. L. Chen. Iterative Exhaustive Pattern Generation for Logic Testing. IBM Journal of Research and Development 28:212-219, 1984.

Digital Library

[25]

D. T. Tang and L. S. Woo. Exhaustive Test Pattern Generation With Constant Weight Vectors. IEEE Transactions Computers 32:1145-1150, 1983.

Digital Library

[26]

E. P. K. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.

Cited By

Ansótegui CManyà FOjeda JSalvia JTorres E(2022)Incomplete MaxSAT approaches for combinatorial testingJournal of Heuristics10.1007/s10732-022-09495-328:4(377-431)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s10732-022-09495-3
Nie CLeung H(2011)The Minimal Failure-Causing Schema of Combinatorial TestingACM Transactions on Software Engineering and Methodology10.1145/2000799.200080120:4(1-38)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1145/2000799.2000801
Nie CLeung H(2011)A survey of combinatorial testingACM Computing Surveys10.1145/1883612.188361843:2(1-29)Online publication date: 4-Feb-2011
https://dl.acm.org/doi/10.1145/1883612.1883618
Show More Cited By

Recommendations

Constraint Models for the Covering Test Problem

Covering arrays can be applied to the testing of software, hardware and advanced materials, and to the effects of hormone interaction on gene expression. In this paper we develop constraint programming models of the problem of finding an optimal ...
Enhancing constraint based test generation by local search
ICSCA '17: Proceedings of the 6th International Conference on Software and Computer Applications

The core operation of symbolic execution based test data generation is to generate a path constraint in terms of input variables for a selected path. Solutions to the path constraint are test data which will be used to execute the target path. So far, ...
Constraint Hierarchies as Semiring-Based CSPs
ICTAI '09: Proceedings of the 2009 21st IEEE International Conference on Tools with Artificial Intelligence

Constraints provide an effective means for the high-level modeling and reasoning of various problems. In particular, soft constraints are useful since they treat over-constrained problems that naturally arise in real-life applications. Therefore, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CSCLP'04: Proceedings of the 2004 joint ERCIM/CoLOGNET international conference on Recent Advances in Constraints

June 2004

215 pages

ISBN:3540251766

Editors:
Boi V. Faltings
Artificial Intelligence Lab, Ecole Polytechnique Fédérale de Lausanne, Station 14, Lausanne, Switzerland
,
Adrian Petcu
Artificial Intelligence Lab, Ecole Polytechnique Federale de Lausanne (EPFL), Station 14, Lausanne, (Switzerland)
,
François Fages
Artificial Intelligence Lab, Projet Contraintes, INRIA Rocquencourt, BP105, Domaine de Voluceau, Le Chesnay Cedex, France
,
Francesca Rossi
Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Trieste 63, Padova, Italy

Sponsors

CoLogNET: CoLogNET
ERCIM: European Research Consortium for Informatics and Mathematics

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 June 2004

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ansótegui CManyà FOjeda JSalvia JTorres E(2022)Incomplete MaxSAT approaches for combinatorial testingJournal of Heuristics10.1007/s10732-022-09495-328:4(377-431)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s10732-022-09495-3
Nie CLeung H(2011)The Minimal Failure-Causing Schema of Combinatorial TestingACM Transactions on Software Engineering and Methodology10.1145/2000799.200080120:4(1-38)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1145/2000799.2000801
Nie CLeung H(2011)A survey of combinatorial testingACM Computing Surveys10.1145/1883612.188361843:2(1-29)Online publication date: 4-Feb-2011
https://dl.acm.org/doi/10.1145/1883612.1883618
Banbara MMatsunaka HTamura NInoue K(2010)Generating combinatorial test cases by efficient SAT encodings suitable for CDCL SAT solversProceedings of the 17th international conference on Logic for programming, artificial intelligence, and reasoning10.5555/1928380.1928389(112-126)Online publication date: 10-Oct-2010
https://dl.acm.org/doi/10.5555/1928380.1928389
Bryce RColbourn CLipson H(2007)One-test-at-a-time heuristic search for interaction test suitesProceedings of the 9th annual conference on Genetic and evolutionary computation10.1145/1276958.1277173(1082-1089)Online publication date: 7-Jul-2007
https://dl.acm.org/doi/10.1145/1276958.1277173
Cohen MDwyer MShi JHierons RMuccini H(2006)Coverage and adequacy in software product line testingProceedings of the ISSTA 2006 workshop on Role of software architecture for testing and analysis10.1145/1147249.1147257(53-63)Online publication date: 17-Jul-2006
https://dl.acm.org/doi/10.1145/1147249.1147257
Colbourn CMartirosyan STrung TWalker R(2006)Roux-type constructions for covering arrays of strengths three and fourDesigns, Codes and Cryptography10.1007/s10623-006-0020-841:1(33-57)Online publication date: 1-Oct-2006
https://dl.acm.org/doi/10.1007/s10623-006-0020-8

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents