More Web Proxy on the site http://driver.im/

research-article

A penalty-based Tabu search for constrained covering arrays

Authors:

Philippe Galinier,

Segla Kpodjedo,

Giulio AntoniolAuthors Info & Claims

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 1288 - 1294

https://doi.org/10.1145/3071178.3071324

Published: 01 July 2017 Publication History

Abstract

Combinatorial Interaction Testing is a black-box testing technique particularly used for highly configurable software systems, which involve a number of factors (and values) that can be combined, according to some constraints. In this context, constrained covering array (CCA) is a central combinatorial problem tasked with building a test suite of minimum size and maximum coverage of the factors' interactions.

In this paper, we propose CATS (Covering Array by Tabu Search), a new penalty-based tabu search algorithm for the CCA problem. Our local search approach differs from the ones previously proposed primarily by its use of a search space that allows solutions that violate inter-factor constraints. Other prominent features of CATS are the definition of strategic moves used to restrict the neighborhood, and a technique to vary the tabu tenure throughout the search.

We performed tests with CATS on 2-way constrained problems using 35 widely used benchmarks. Results suggest that CATS consistently outperforms previous approaches, both on the size of the test suites and the needed computation times.

References

[1]

A. Calvagna, A. Gargantini, A Logic-Based Approach to Combinatorial Testing with Constraints, TAP 2008: 66--83.

Digital Library

[2]

A. Calvagna, A. Gargantini, T-wise combinatorial interaction test suites construction based on coverage inheritance, Softw. Test., Verif. Reliab. 22(7): 507--526, 2012.

Digital Library

[3]

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 TSE, vol. 23, no. 7: 437--444, 1997.

Digital Library

[4]

M. B. Cohen, C. J. Colbourn, P. B. Gibbons, and W. B. Mugridge, Constructing test suites for interaction testing, Proc. International Conference on Software Engineering, 38--48, 2003.

Digital Library

[5]

P. Galinier, J. K. Hao, A General Approach for Constraint Solving by Local Search, J. Math. Model. Algorithms 3(1): 73--88, 2004.

[6]

B. J. Garvin, M. B. Cohen, and M. B. Dwyer, An improved meta-heuristic search for constrained interaction testing, In: 1st international symposium on search based software engineering, 13--22, 2009.

Digital Library

[7]

B. J. Garvin, M. B. Cohen, and M. B. Dwyer, Evaluating improvements to a meta-heuristic search for constrained interaction testing, EMSE, vol. 16, no. 1, 61--102, 2011.

Digital Library

[8]

F. Glover, and M. Laguna, Tabu Search, Kluwer Academic Publishers, 1997.

Digital Library

[9]

A. Hartman and L. Raskin. Problems and algorithms for covering arrays. Discrete Mathematics, 284: 149--156, 2004.

Digital Library

[10]

C. Henard, M. Papadakis, Y. Le Traon, Flattening or not of the combinatorial interaction testing models?, ICST Workshops 2015: 1--4, 2015.

[11]

Y. Jia, M. B. Cohen, M. Harman, J. Petke, Learning Combinatorial Interaction Test Generation Strategies Using Hyperheuristic Search, Proc. International Conference on Software Engineering (1) 540--550, 2015.

Digital Library

[12]

R. N. Kacker, D. R. Kuhn, Y. Lei, J. F. Lawrence Combinatorial testing for software: An adaptation of design of experiments, Measurement, 46 (2013) 3745--3752

[13]

S. K. Khalsa and Y. Labiche, An orchestrated survey of available algorithms and tools for combinatorial testing, in Proc. 25th IEEE Int. Symp. Softw. Rel. Eng., 323--334, 2014.

Digital Library

[14]

D. R. Kuhn, D. R. Wallace, A. M. Gallo, Software fault interactions and implications for software testing, IEEE TSE 30(6):418--421, 2004.

Digital Library

[15]

V. V. Kuliamin, A. Petukhov, A survey of methods for constructing covering arrays, Programming and Computer Software 37(3): 121--146, 2011.

Digital Library

[16]

Y. Lei, R. Kacker, D. R. Kuhn, V. Okun, and J. Lawrence, IPOG/IPOG-D: Efficient test generation for multi-way combinatorial testing, Softw. Test., Verification Reliab., vol. 18, no. 3, 125--148, 2008.

Digital Library

[17]

J. Lin, C. Luo, S. Cai, K. Su, D. Hao, L. Zhang, TCA: An Efficient Two-Mode Meta-Heuristic Algorithm for Combinatorial Test Generation, in Proc. Automated Software Engineering 2015: 494--505

[18]

R. E. Lopez-Herrejon, S. Fischer, R. Ramler, A. Egyed, A first systematic mapping study on combinatorial interaction testing for software product lines, ICST Workshops 2015: 1--10, 2015.

[19]

C. Nie and H. Leung, A Survey of Combinatorial Testing, ACM Computing Surveys, vol. 43, no. 11, 1--29, 2011.

Digital Library

[20]

J. Petke, M. B. Cohen, M. Harman, and S. Yoo, Practical Combinatorial Interaction Testing: Empirical Findings on Efficiency and Early Fault Detection, IEEE TSE, 41(9): 901--924, 2015.

[21]

N. J.A. Sloane, Covering arrays and intersecting codes, Journal of Combinatorial Designs 1 (1993) 51--63.

[22]

A. Yamada, T. Kitamura, C. Artho, E-H. Choi, Y. Oiwa, A. Biere, Optimization of Combinatorial Testing by Incremental SAT Solving, in Proc. of Intl Conf. on Softw. Testing (ICST): 1--10, 2015.

[23]

L. Yu, Y. Lei, M. N. Borazjany, R. Kacker, and D. R. Kuhn, An efficient algorithm for constraint handling in combinatorial test generation, in Proc. of Intl Conf. on Softw. Testing (ICST), 242--251, 2013.

Digital Library

Cited By

Mohammed Fadhil HNajm Abdullah MIssam Younis M(2024)Dynamic TWGH: Client-Server Optimization for Scalable Combinatorial Test Suite GenerationBIO Web of Conferences10.1051/bioconf/2024970011597(00115)Online publication date: 5-Apr-2024
https://doi.org/10.1051/bioconf/20249700115
Guo XSong XZhou JWang F(2023)A tolerance-based memetic algorithm for constrained covering array generationMemetic Computing10.1007/s12293-023-00392-115:3(319-340)Online publication date: 29-Aug-2023
https://doi.org/10.1007/s12293-023-00392-1
Mercan HJaveed AYilmaz C(2022)Flexible Combinatorial Interaction TestingIEEE Transactions on Software Engineering10.1109/TSE.2020.301031748:3(1030-1066)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TSE.2020.3010317
Show More Cited By

Recommendations

Prioritizing Variable-Strength Covering Array
COMPSAC '13: Proceedings of the 2013 IEEE 37th Annual Computer Software and Applications Conference

Combinatorial interaction testing is a well-studied testing strategy, and has been widely applied in practice. Combinatorial interaction test suite, such as fixed-strength and variable-strength interaction test suite, is widely used for combinatorial ...
An Adaptive Penalty based Parallel Tabu Search for Constrained Covering Array Generation
Abstract Context:
The generation of the optimal constrained covering arrays is a key challenge in the research field of combinatorial testing, where a variety of Constrained Covering Array Generation (CCAG) algorithms have been ...
Backtracking based iterated tabu search for equitable coloring

An equitable k-coloring of an undirected graph G = ( V , E ) is a partition of its vertices into k disjoint independent sets, such that the cardinalities of any two independent sets differ by at most one. As a variant of the graph coloring problem (GCP),...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
217
Total Downloads

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

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mohammed Fadhil HNajm Abdullah MIssam Younis M(2024)Dynamic TWGH: Client-Server Optimization for Scalable Combinatorial Test Suite GenerationBIO Web of Conferences10.1051/bioconf/2024970011597(00115)Online publication date: 5-Apr-2024
https://doi.org/10.1051/bioconf/20249700115
Guo XSong XZhou JWang F(2023)A tolerance-based memetic algorithm for constrained covering array generationMemetic Computing10.1007/s12293-023-00392-115:3(319-340)Online publication date: 29-Aug-2023
https://doi.org/10.1007/s12293-023-00392-1
Mercan HJaveed AYilmaz C(2022)Flexible Combinatorial Interaction TestingIEEE Transactions on Software Engineering10.1109/TSE.2020.301031748:3(1030-1066)Online publication date: 1-Mar-2022
https://doi.org/10.1109/TSE.2020.3010317
Wang YWu HNiu XNie CXu J(2022)A Constrained Covering Array Generator using Adaptive Penalty based Parallel Tabu Search2022 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW)10.1109/ICSTW55395.2022.00028(82-86)Online publication date: Apr-2022
https://doi.org/10.1109/ICSTW55395.2022.00028
Wang YWu HNiu XNie CXu J(2022)An Adaptive Penalty based Parallel Tabu Search for Constrained Covering Array GenerationInformation and Software Technology10.1016/j.infsof.2021.106768143:COnline publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1016/j.infsof.2021.106768
Wu HNie CPetke JJia YHarman M(2021)Comparative Analysis of Constraint Handling Techniques for Constrained Combinatorial TestingIEEE Transactions on Software Engineering10.1109/TSE.2019.295568747:11(2549-2562)Online publication date: 1-Nov-2021
https://doi.org/10.1109/TSE.2019.2955687
Luo CLin JCai SChen XHe BQiao BZhao PLin QZhang HWu WRajmohan SZhang D(2021)AutoCCAGProceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00030(201-212)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00030
Lin JCai SHe BFu YLuo CLin QJuristo N(2021)FastCAProceedings of the 43rd International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion52605.2021.00040(77-80)Online publication date: 25-May-2021
https://dl.acm.org/doi/10.1109/ICSE-Companion52605.2021.00040
Jin HShi CTsuchiya THung CCerny TShin DBechini A(2020)Constrained detecting arrays for fault localization in combinatorial testingProceedings of the 35th Annual ACM Symposium on Applied Computing10.1145/3341105.3373952(1971-1978)Online publication date: 30-Mar-2020
https://dl.acm.org/doi/10.1145/3341105.3373952
Hasan IAhmed BPotrus MZamli K(2020)Generation and Application of Constrained Interaction Test Suites Using Base Forbidden Tuples with a Mixed Neighborhood Tabu SearchInternational Journal of Software Engineering and Knowledge Engineering10.1142/S021819402050015130:03(363-398)Online publication date: 28-Apr-2020
https://doi.org/10.1142/S0218194020500151
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents