research-article

FLOWER: optimal test suite reduction as a network maximum flow

Authors:

Arnaud Gotlieb,

Dusica MarijanAuthors Info & Claims

ISSTA 2014: Proceedings of the 2014 International Symposium on Software Testing and Analysis

Pages 171 - 180

https://doi.org/10.1145/2610384.2610416

Published: 21 July 2014 Publication History

Abstract

A trend in software testing is reducing the size of a test suite while preserving its overall quality. Given a test suite and a set of requirements covered by the suite, test suite reduction aims at selecting a subset of test cases that cover the same set of requirements. Even though this problem has received considerable attention, finding the smallest subset of test cases is still challenging and commonly-used approaches address this problem only with approximated solutions. When executing a single test case requires much manual effort (e.g., hours of preparation), finding the minimal subset is needed to reduce the testing costs. In this paper, we introduce a radically new approach to test suite reduction, called FLOWER, based on a search among network maximum flows. From a given test suite and the requirements covered by the suite, FLOWER forms a flow network (with specific constraints) that is then traversed to find its maximum flows. FLOWER leverages the Ford-Fulkerson method to compute maximum flows and Constraint Programming techniques to search among optimal flows. FLOWER is an exact method that computes a minimum-sized test suite, preserving the coverage of requirements. The experimental results show that FLOWER outperforms a non-optimized implementation of the Integer Linear Programming approach by 15-3000 times in terms of the time needed to find an optimal solution, and a simple greedy approach by 5-15% in terms of the size of reduced test suite.

References

[1]

H. Agrawal. Eﬃcient coverage testing using global dominator graphs. In Workshop on Program Analysis for Software Tools and Eng. (PASTE’99), 1999.

Digital Library

[2]

J. Black, E. Melachrinoudis, and D. Kaeli. Bi-criteria models for all-uses test suite reduction. In 26th Int. Conf. on Software Eng., pages 106–115, 2004.

Digital Library

[3]

M. Carlsson, G. Ottosson, and B. Carlson. An open–ended finite domain constraint solver. In Programming Languages: Implementations, Logics, and Programs (PLILP’97), 1997.

Digital Library

[4]

Z. Chen, X. Zhang, and B. Xu. A degraded ilp approach for test suite reduction. In 20th Int. Conf. on Soft. Eng. and Know. Eng., 2008.

[5]

V. Chvatal. A greedy heuristic for the set-covering problem. Math. of Operations Research, 4(3), 1979.

[6]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2 edition, 2001.

Digital Library

[7]

L. Ford and D. Fulkerson. Flows in Networks. Princeton University Press, 1962.

[8]

M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., NY, 1990.

Digital Library

[9]

D. Hao, L. Zhang, X. Wu, H. Mei, and G. Rothermel. On-demand test suite reduction. In Int. Conference on Software Engineerig, pages 738–748, 2012.

Digital Library

[10]

M. J. Harrold, R. Gupta, and M. L. Soffa. A methodology for controlling the size of a test suite. ACM TOSEM, 2(3):270–285, 1993.

Digital Library

[11]

C. Holzbaur. OEFAI clp(q,r) Manual Rev. 1.3.2. Austrian Research Institute for Artificial Intelligence, Vienna, AU, 1995. TR-95-09.

[12]

H.-Y. Hsu and A. Orso. Mints: A general framework and tool for supporting test-suite minimization. In 31st Int. Conf. on Soft. Eng. (ICSE’09), pages 419–429, 2009.

Digital Library

[13]

D. Jeffrey and N. Gupta. Test suite reduction with selective redundancy. In 21st International Conference on Software Maintenance, pages 549–558, 2005.

Digital Library

[14]

D. Jeffrey and R. Gupta. Improving fault detection capability by selectively retaining test cases during test suite reduction. IEEE Trans. on Soft. Eng., 33(2):108–123, 2007.

Digital Library

[15]

J. Jones and M. Harrold. Test-suite reduction and prioritization for modified condition/decision coverage. IEEE Transactions on Software Engineering, 29(3):195–209, 2003.

Digital Library

[16]

C.-T. Lin, K.-W. Tang, C.-D. Chen, and G. Kapfhammer. Reducing the cost of regression testing by identifying irreplaceable test cases. In 6th International Conference on Genetic and Evolutionary Comp. (ICGEC), pages 257–260, 2012.

Digital Library

[17]

D. Marijan, A. Gotlieb, and S. Sen. Test case prioritization for continuous regression testing: An industrial case study. In Software Maintenance (ICSM), 2013 29th IEEE International Conference on, pages 540–543, 2013.

Digital Library

[18]

M. Marre and A. Bertolino. Using spanning sets for coverage testing. IEEE Trans. on Soft. Eng., 29(11):974–984, 2003.

Digital Library

[19]

A. J. Offutt, J. Pan, and J. M. Voas. Procedures for reducing the size of coverage-based test sets. In 12th Int. Conf. on Testing Computer Soft., 1995.

[20]

J.-C. Régin. Generalized arc consistency for global cardinality constraint. In 13th Int. Conf. on Artificial Intelligence (AAAI’96), pages 209–215, 1996.

Digital Library

[21]

G. Rothermel, M. Harrold, J. Ostrin, and C. Hong. An empirical study of the effects of minimization on the fault detection capabilities of test suites. In International Conference on Software Maintenance (ICSM’98), pages 34–43, 1998.

Digital Library

[22]

G. Rothermel, M. J. Harrold, J. Ronne, and C. Hong. Empirical studies of test-suite reduction. Software Testing Verification and Reliability, 12:219–249, 2002.

[23]

E. Salecker, R. Reicherdt, and S. Glesner. Calculating prioritized interaction test sets with constraints using binary decision diagrams. In Variability-intensive System Testing Workshop (VAST’11), 2011.

Digital Library

[24]

S. Tallam and N. Gupta. A concept analysis inspired greedy algorithm for test suite minimization. In 6th Workshop on Program Analysis for Software Tools and Eng. (PASTE’05), pages 35–42, 2005.

Digital Library

[25]

E. Uzuncaova, S. Khurshid, and D. Batory. Incremental test generation for software product lines. Software Engineering, IEEE Transactions on, 36(3):309–322, 2010.

Digital Library

[26]

S. Wang, S. Ali, and A. Gotlieb. Minimizing test suites in software product lines using weight-based genetic algorithms. In Genetic and Evolutionary Computation Conference (GECCO’13), 2013.

Digital Library

[27]

W. Wong, J. Horgan, A. Mathur, and A. Pasquini. Test set size minimization and fault detection effectiveness: a case study in a space application. In 21st COMPuter Soft. and App. Conf. (COMPSAC ’97), pages 522–528, 1997.

Digital Library

[28]

W. E. Wong, J. R. Horgan, S. London, and A. P. Mathur. Effect of test set minimization on fault detection effectiveness. In 17th International Conference on Software Engineering (ICSE’95), 1995.

Digital Library

[29]

M. C. X. Qu and G. Rothermel. Configuration-aware regression testing: an empirical study of sampling and prioritization. In International Symphosium on Software Testing and Analysis, 2008.

Digital Library

[30]

Y. Yu, J. A. Jones, and M. J. Harrold. An empirical study of the effects of test-suite reduction on fault localization. In 30th International Conference on Software Engineering (ICSE’08), pages 201–210, 2008.

Digital Library

[31]

S. Zilberstein. Using anytime algorithms in intelligent systems. AI Magazine, 17(3):73–83, 1996.

Digital Library

Cited By

Baz AHuang MShi AFilkov VRay BZhou M(2024)Prioritizing Tests for Improved RuntimeProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695298(2273-2278)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695298
Krafft THauer MZweig K(2024)Black-Box Testing and Auditing of Bias in ADM SystemsMinds and Machines10.1007/s11023-024-09666-034:2Online publication date: 25-May-2024
https://doi.org/10.1007/s11023-024-09666-0
Alekseev YOnischuck MZorin AChernyi VIliyn EItsykson V(2024)ATSMJournal of Software: Evolution and Process10.1002/smr.262136:6Online publication date: 5-Jun-2024
https://dl.acm.org/doi/10.1002/smr.2621
Show More Cited By

Index Terms

FLOWER: optimal test suite reduction as a network maximum flow
1. Social and professional topics
  1. Professional topics
    1. Management of computing and information systems
      1. Software management
        Software maintenance
2. Software and its engineering
  1. Software creation and management
    1. Software post-development issues

Recommendations

Comparing and combining test-suite reduction and regression test selection
ESEC/FSE 2015: Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering

Regression testing is widely used to check that changes made to software do not break existing functionality, but regression test suites grow, and running them fully can become costly. Researchers have proposed test-suite reduction and regression test ...
Balancing trade-offs in test-suite reduction
FSE 2014: Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering

Regression testing is an important activity but can get expensive for large test suites. Test-suite reduction speeds up regression testing by identifying and removing redundant tests based on a given set of requirements. Traditional research on test-...
Evaluating test-suite reduction in real software evolution
ISSTA 2018: Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis

Test-suite reduction (TSR) speeds up regression testing by removing redundant tests from the test suite, thus running fewer tests in the future builds. To decide whether to use TSR or not, a developer needs some way to predict how well the reduced test ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA 2014: Proceedings of the 2014 International Symposium on Software Testing and Analysis

July 2014

460 pages

ISBN:9781450326452

DOI:10.1145/2610384

General Chair:
Corina S. Păsăreanu
NASA Ames, USA
,
Program Chair:
Darko Marinov
University of Illinois at Urbana-Champaign, USA

Copyright © 2014 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 the author(s) 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

SIGSOFT: ACM Special Interest Group on Software Engineering

In-Cooperation

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSTA '14

Sponsor:

SIGSOFT

ISSTA '14: International Symposium on Software Testing and Analysis

July 21 - 25, 2014

CA, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 58 of 213 submissions, 27%

Upcoming Conference

ISSTA '25

Sponsor:
sigsoft

34th ACM SIGSOFT International Symposium on Software Testing and Analysis

June 25 - 28, 2025

Trondheim , Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
373
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Baz AHuang MShi AFilkov VRay BZhou M(2024)Prioritizing Tests for Improved RuntimeProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695298(2273-2278)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695298
Krafft THauer MZweig K(2024)Black-Box Testing and Auditing of Bias in ADM SystemsMinds and Machines10.1007/s11023-024-09666-034:2Online publication date: 25-May-2024
https://doi.org/10.1007/s11023-024-09666-0
Alekseev YOnischuck MZorin AChernyi VIliyn EItsykson V(2024)ATSMJournal of Software: Evolution and Process10.1002/smr.262136:6Online publication date: 5-Jun-2024
https://dl.acm.org/doi/10.1002/smr.2621
Lin THuang CFang C(2023)Using the Deep Learning-Based Approaches for Program Debugging and Repair2023 10th International Conference on Dependable Systems and Their Applications (DSA)10.1109/DSA59317.2023.00059(443-454)Online publication date: 10-Aug-2023
https://doi.org/10.1109/DSA59317.2023.00059
Xia CZhang YHui Z(2021)Test Suite Reduction via Evolutionary ClusteringIEEE Access10.1109/ACCESS.2021.30583019(28111-28121)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3058301
Rosenbauer LStein AHähner J(2021)An Artificial Immune System for Black Box Test Case SelectionEvolutionary Computation in Combinatorial Optimization10.1007/978-3-030-72904-2_11(169-184)Online publication date: 27-Mar-2021
https://doi.org/10.1007/978-3-030-72904-2_11
Fornaia AMidolo APappalardo GTramontana E(2020)Automatic Generation of Effective Unit Tests based on Code Behaviour2020 IEEE 29th International Conference on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE)10.1109/WETICE49692.2020.00049(213-218)Online publication date: Sep-2020
https://doi.org/10.1109/WETICE49692.2020.00049
Rosenbauer LStein AHahner J(2020)An Artificial Immune System for Adaptive Test Selection2020 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI47803.2020.9308528(2940-2947)Online publication date: 1-Dec-2020
https://doi.org/10.1109/SSCI47803.2020.9308528
Mongiovì MFornaia ATramontana E(2020)REDUNET: reducing test suites by integrating set cover and network-based optimizationApplied Network Science10.1007/s41109-020-00323-w5:1Online publication date: 2-Nov-2020
https://doi.org/10.1007/s41109-020-00323-w
Mohapatra SMishra APrasad S(2020)Intelligent Local Search for Test Case MinimizationJournal of The Institution of Engineers (India): Series B10.1007/s40031-020-00480-7Online publication date: 20-Aug-2020
https://doi.org/10.1007/s40031-020-00480-7
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