Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/1276958.1277173acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
Article

One-test-at-a-time heuristic search for interaction test suites

Published: 07 July 2007 Publication History

Abstract

Algorithms for the construction of software interaction test suites have focussed on the special case of pairwise coverage; less is known about efficiently constructing test suites for higher strength coverage. The combinatorial growth of t-tuples associated with higher strength hinders the efficacy of interaction testing. Test suites are inherently large, so testers may not run entire test suites. To address these problems, we combine a simple greedy algorithmallwith heuristic search to construct and dispense one test at a time. Our algorithm attempts to maximize the number of t-tuples covered by the earliest tests so that if a tester only runs a partial test suite, they test as many t-tuples as possible.allHeuristic search is shown to provide effective methods for achieving such coverage.

References

[1]
R. C. Bryce, Y. Chen, and C. J. Colbourn. Biased covering arrays for progressive ranking and composition of web services. International Journal of Simulation and Process Modeling, to appear.
[2]
R. C. Bryce and C. J. Colbourn. Prioritized interaction testing for pairwise coverage with seeding and avoids. Information and Software Technology Journal (IST, Elsevier), 40(10):960--970, Oct. 2006.
[3]
R. C. Bryce and C. J. Colbourn. A density-based greedy algorithm for higher strength covering arrays. submitted for review.
[4]
R. C. Bryce and C. J. Colbourn. The density algorithm for pairwise interaction testing. Journal of Software Testing, Verification, and Reliability, to appear.
[5]
R. C. Bryce, C. J. Colbourn, and M. B. Cohen. A framework of greedy methods for constructing interaction tests. In Intl. Conference on Software Engineering (ICSE), pages 146--155, May 2005.
[6]
K. Burr and W. Young. Combinatorial test techniques: Table-based automation, test generation, and code coverage. In Intl. Conference on Software Testing Analysis and Review, pages 503--513, Oct. 1998.
[7]
M. Chateauneuf and D. L. Kreher. On the state of strength-three covering arrays. J. Combin. Des., 10(4):217--238, 2002.
[8]
C. Cheng, A. Dumitrescu, and P. Schroeder. Generating small combinatorial test suites to cover input-output relationships. In Intl. Conference on Quality Software (QSIC), pages 76--82, Nov. 2003.
[9]
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 Trans. on Software Engineering, 23(7):437--44, Oct. 1997.
[10]
D. M. Cohen, S. R. Dalal, J. Parelius, and G. C. Patton. The combinatorial design approach to automatic test generation. IEEE Software, 13(5):82--88, Oct. 1996.
[11]
M. B. Cohen, C. J. Colbourn, P. B. Gibbons, and W. B. Mugridge. Constructing test suites for interaction testing. In Intl. Conference on Software Engineering (ICSE), pages 28--48, May 2003.
[12]
M. B. Cohen, C. J. Colbourn, and A. C. H. Ling. Constructing strength three covering arrays with augmented annealing. Discrete Mathematics, to appear.
[13]
C. J. Colbourn. Combinatorial aspects of covering arrays. Le Matematiche (Catania), 58:121--167, 2004.
[14]
C. J. Colbourn. Covering array tables, July 2006. public.asu.edu/<ccolbou/src/tabby/catable.html, accessed on January 15, 2007.
[15]
S. R. Dalal, A. Karunanithi, J. Leaton, G. Patton, and B. M. Horowitz. Model-based testing in practice. In Intl. Conference on Software Engineering,(ICSE), pages 285--294, May 1999.
[16]
G. Dueck. New optimization heuristics -- the great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104(1):86--92, Jan. 1993.
[17]
S. Dunietz, W. K. Ehrlich, B. D. Szablak, C. L. Mallows, and A. Iannino. Applying design of experiments to software testing. In Intl. Conference on Software Engineering, pages 205--215, Oct. 1997.
[18]
A. Hartman and L. Raskin. Problems and algorithms for covering arrays. Discrete Math., 284(1--3):149--156, Jul. 2004.
[19]
B. Hnich, S. Prestwich, and E. Selensky. Constraint-based approaches to the covering test problem. Lecture Notes in Computer Science, 3419(1):172--186, Mar. 2005.
[20]
D. Kuhn and M. Reilly. An investigation of the applicability of design of experiments to software testing. In 27th Annual NASA Goddard/IEEE Software Engineering Workshop, pages 91--95, Oct. 2002.
[21]
D. R. Kuhn, D. R. Wallace, and A. M. Gallo. Software fault interactions and implications for software testing. IEEE Trans. on Software Engineering, 30(6):418--421, Oct. 2004.
[22]
K. Nurmela. Upper bounds for covering arrays by tabu search. Discrete Applied Math., 138(9):143--152, Mar. 2004.
[23]
Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Prentice-Hall, Chapter 4, 1995.
[24]
Toshiaki Shiba, Tatsuhiro Tsuchiya, and Tohru Kikuno. Using artificial life techniques to generate test cases for combinatorial testing. In Intl. Conference on Computer Software and Applications Conference (COMPSAC), pages 72--77, Sep. 2004.
[25]
J. Stardom. Metaheuristics and the search for covering and packing arrays. Masters thesis, Simon Fraser University, 2001.
[26]
K.C. Tai and Y. Lei. A test generation strategy for pairwise testing. IEEE Trans. on Software Engineering, 28(1):109--111, Jan. 2002.
[27]
Y.W. Tung and W.S. Aldiwan. Automating test case generation for the new generation mission software system. In IEEE Aerospace Conference, pages 431--37, Mar. 2000.
[28]
R. C. Turban. Algorithms for covering arrays. Ph.D. Thesis, Arizona State University, Department of Computer Science and Engineering, May 2006.
[29]
A. W. Williams. Determination of test configurations for pair-wise interaction coverage. Testing of communicating systems: Tools and techniques. In Intl. Conference on Testing Communicating Systems, pages 59--74, Oct. 2000.
[30]
C. Yilmaz, M. B. Cohen, and A. Porter. Covering arrays for efficient fault characterization in complex configuration spaces. IEEE Transactions on Software Engineering, 31(1):20--34, Jan. 2006.

Cited By

View all
  • (2024)Efficient Greedy Algorithms with Accuracy Guarantees for Combinatorial RestrictionsSN Computer Science10.1007/s42979-023-02548-95:2Online publication date: 1-Feb-2024
  • (2022)Flexible Combinatorial Interaction TestingIEEE Transactions on Software Engineering10.1109/TSE.2020.301031748:3(1030-1066)Online publication date: 1-Mar-2022
  • (2021)Comparing Fault Detection Efficiencies of Adaptive Random Testing and Greedy Combinatorial Testing for Boolean-SpecificationsInternational Journal of Performability Engineering10.23940/ijpe.21.01.p11.11412217:1(114)Online publication date: 2021
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation
July 2007
2313 pages
ISBN:9781595936974
DOI:10.1145/1276958
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. covering arrays
  2. great flood
  3. heuristic search
  4. hill climbing
  5. simulated annealing
  6. software interaction testing
  7. t-way interaction testing
  8. tabu search
  9. test suite prioritization

Qualifiers

  • Article

Conference

GECCO07
Sponsor:

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 06 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Efficient Greedy Algorithms with Accuracy Guarantees for Combinatorial RestrictionsSN Computer Science10.1007/s42979-023-02548-95:2Online publication date: 1-Feb-2024
  • (2022)Flexible Combinatorial Interaction TestingIEEE Transactions on Software Engineering10.1109/TSE.2020.301031748:3(1030-1066)Online publication date: 1-Mar-2022
  • (2021)Comparing Fault Detection Efficiencies of Adaptive Random Testing and Greedy Combinatorial Testing for Boolean-SpecificationsInternational Journal of Performability Engineering10.23940/ijpe.21.01.p11.11412217:1(114)Online publication date: 2021
  • (2021)SATuneProceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE51524.2021.9678761(330-342)Online publication date: 15-Nov-2021
  • (2021)A Comparison of Fault Detection Efficiency Between Adaptive Random Testing and Greedy Combinatorial Testing for Control Logics in Nuclear Industrial Distributed Control SystemsIEEE Access10.1109/ACCESS.2021.30871659(84021-84033)Online publication date: 2021
  • (2020)An Interleaving Approach to Combinatorial Testing and Failure-Inducing Interaction IdentificationIEEE Transactions on Software Engineering10.1109/TSE.2018.286577246:6(584-615)Online publication date: 1-Jun-2020
  • (2020)T-way Strategy for (Sequence Less Input Interaction) Test Case Generation Inspired by Fish Swarm Searching AlgorithmCyber Security and Computer Science10.1007/978-3-030-52856-0_12(155-166)Online publication date: 30-Jul-2020
  • (2019)CHiP: A Configurable Hybrid Parallel Covering Array ConstructorIEEE Transactions on Software Engineering10.1109/TSE.2018.283775945:12(1270-1291)Online publication date: 1-Dec-2019
  • (2019)Effective product-line testing using similarity-based product prioritizationSoftware and Systems Modeling (SoSyM)10.1007/s10270-016-0569-218:1(499-521)Online publication date: 1-Feb-2019
  • (2018)Test-Algebra-Based Fault Location Analysis for the Concurrent Combinatorial TestingIEEE Transactions on Reliability10.1109/TR.2018.283344967:3(802-831)Online publication date: Sep-2018
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media