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

research-article

One test to rule them all

Authors:

Kevin KellarAuthors Info & Claims

ISSTA 2017: Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis

Pages 1 - 11

https://doi.org/10.1145/3092703.3092704

Published: 10 July 2017 Publication History

Abstract

Test reduction has long been seen as critical for automated testing. However, traditional test reduction simply reduces the length of a test, but does not attempt to reduce semantic complexity. This paper extends previous efforts with algorithms for normalizing and generalizing tests. Rewriting tests into a normal form can reduce semantic complexity and even remove steps from an already delta-debugged test. Moreover, normalization dramatically reduces the number of tests that a reader must examine, partially addressing the ``fuzzer taming'' problem of discovering distinct faults in a set of failing tests. Generalization, in contrast, takes a test and reports what aspects of the test could have been changed while preserving the property that the test fails. Normalization plus generalization aids understanding of tests, including tests for complex and widely used APIs such as the NumPy numeric computation library and the ArcPy GIS scripting package. Normalization frequently reduces the number of tests to be examined by well over an order of magnitude, and often to just one test per fault. Together, ideally, normalization and generalization allow a user to replace reading a large set of tests that vary in unimportant ways with reading one annotated summary test.

References

[1]

NumPy. http://www.numpy.org.

[2]

SymPy. http://www.sympy.org/en/index.html.

[3]

What is ArcPy? http://resources.arcgis.com/EN/HELP/MAIN/10.1/index.html#// 000v000000v7000000.

[4]

J. Andrews, Y. R. Zhang, and A. Groce. Comparing automated unit testing strategies. Technical Report 736, Department of Computer Science, University of Western Ontario, December 2010.

[5]

J. H. Andrews, L. C. Briand, and Y. Labiche. Is mutation an appropriate tool for testing experiments? In International Conference on Software Engineering, pages 402–411, 2005.

Digital Library

[6]

A. Arcuri and L. Briand. A hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering. Software Testing, Verification and Reliability, 24(3):219–250, 2014.

Digital Library

[7]

A. Arcuri, M. Z. Z. Iqbal, and L. C. Briand. Formal analysis of the effectiveness and predictability of random testing. In International Symposium on Software Testing and Analysis, pages 219–230, 2010.

Digital Library

[8]

Y. Chen, A. Groce, C. Zhang, W.-K. Wong, X. Fern, E. Eide, and J. Regehr. Taming compiler fuzzers. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 197–208, 2013.

Digital Library

[9]

D. Coppit, J. Yang, S. Khurshid, W. Le, and K. Sullivan. Software assurance by bounded exhaustive testing. IEEE Transactions on Software Engineering, 31(4):328– 339, Apr. 2005.

Digital Library

[10]

E. Daka, J. Campos, J. Dorn, G. Fraser, and W. Weimer. Generating readable unit tests for Guava. In Search-Based Software Engineering - 7th International Symposium, SSBSE 2015, Bergamo, Italy, September 5-7, 2015, Proceedings, pages 235–241, 2015.

[11]

E. Daka, J. Campos, G. Fraser, J. Dorn, and W. Weimer. Modeling readability to improve unit tests. In Foundations of Software Engineering, ESEC/FSE, pages 107–118, 2015.

Digital Library

[12]

A. Danial. CLOC: Count lines of code. https://github.com/AlDanial/cloc.

[13]

L. M. de Moura and N. Bjørner. Z3: an efficient SMT solver. In Tools and Algorithms for the Construction and Analysis of Systems, pages 337–340, 2008.

Digital Library

[14]

N. Dershowitz. Termination of rewriting. Journal of Symbolic Computing, 3(1):69– 115, 1987.

Digital Library

[15]

erezbibi. https://pypi.python.org/pypi/my xml/0.1.1.

[16]

M. Ernst, J. Cockrell, W. Griswold, and D. Notkin. Dynamically discovering likely program invariants to support program evolution. In International Conference on Software Engineering, pages 213–224, 1999.

Digital Library

[17]

M. Fowler. Domain-Specific Languages. Addison-Wesley Professional, 2010.

Digital Library

[18]

G. Fraser and A. Arcuri. EvoSuite: automatic test suite generation for objectoriented software. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, ESEC/FSE ’11, pages 416–419. ACM, 2011.

Digital Library

[19]

G. Fraser and A. Zeller. Generating parameterized unit tests. In Proceedings of the 2011 International Symposium on Software Testing and Analysis, ISSTA ’11, pages 364–374, New York, NY, USA, 2011. ACM.

Digital Library

[20]

P. Gastin, P. Moro, and M. Zeitoun. Minimization of counterexamples in SPIN. In SPIN Workshop on Model Checking of Software, pages 92–108. Springer-Verlag, 2004.

[21]

A. Groce, M. A. Alipour, C. Zhang, Y. Chen, and J. Regehr. Cause reduction: Delta-debugging, even without bugs. Journal of Software Testing, Verification, and Reliability. accepted for publication.

Digital Library

[22]

A. Groce, M. A. Alipour, C. Zhang, Y. Chen, and J. Regehr. Cause reduction for quick testing. In IEEE International Conference on Software Testing, Verification and Validation, pages 243–252. IEEE, 2014.

Digital Library

[23]

A. Groce and M. Erwig. Finding common ground: Choose, assert, and assume. In International Workshop on Dynamic Analysis, pages 12–17, 2012.

Digital Library

[24]

A. Groce, K. Havelund, G. Holzmann, R. Joshi, and R.-G. Xu. Establishing flight software reliability: Testing, model checking, constraint-solving, monitoring and learning. Annals of Mathematics and Artificial Intelligence, 70(4):315–349, 2014.

Digital Library

[25]

A. Groce, G. Holzmann, and R. Joshi. Randomized differential testing as a prelude to formal verification. In International Conference on Software Engineering, pages 621–631, 2007.

Digital Library

[26]

A. Groce and R. Joshi. Random testing and model checking: Building a common framework for nondeterministic exploration. In Workshop on Dynamic Analysis, pages 22–28, 2008.

Digital Library

[27]

A. Groce and D. Kroening. Making the most of BMC counterexamples. Electron. Notes Theor. Comput. Sci., 119(2):67–81, Mar. 2005.

Digital Library

[28]

A. Groce and J. Pinto. A little language for testing. In NASA Formal Methods Symposium, pages 204–218, 2015.

[29]

A. Groce, J. Pinto, P. Azimi, and P. Mittal. TSTL: a language and tool for testing (demo). In ACM International Symposium on Software Testing and Analysis, pages 414–417, 2015.

Digital Library

[30]

A. Groce, J. Pinto, P. Azimi, P. Mittal, J. Holmes, and K. Kellar. TSTL: the template scripting testing language. https://github.com/agroce/tstl.

[31]

A. Groce and W. Visser. What went wrong: Explaining counterexamples. In SPIN Workshop on Model Checking of Software, pages 121–135, 2003.

Digital Library

[32]

K. Halas. MutPy 0.4.0. https://pypi.python.org/pypi/MutPy/0.4.0.

[33]

R. Hamlet. When only random testing will do. In International Workshop on Random Testing, pages 1–9, 2006.

Digital Library

[34]

J. Holmes, A. Groce, and A. Alipour. Mitigating (and exploiting) test reduction slippage. In Workshop on Automated Software Testing, 2016.

Digital Library

[35]

J. Holmes, A. Groce, J. Pinto, P. Mittal, P. Azimi, K. Kellar, and J. O’Brien. TSTL: the template scripting testing language. International Journal on Software Tools for Technology Transfer, 2017. Accepted for publication.

[36]

G. Huet and D. C. Oppen. Equations and rewrite rules: A survey. Technical report, Stanford, CA, USA, 1980.

Digital Library

[37]

G. Jenks. SortedContainers introduction. http://www.grantjenks.com/docs/ sortedcontainers/introduction.html.

[38]

H. Jin, K. Ravi, and F. Somenzi. Fate and free will in error traces. In Tools and Algorithms for the Construction and Analysis of Systems, pages 445–458, 2002.

Digital Library

[39]

Y. Lei and J. H. Andrews. Minimization of randomized unit test cases. In International Symposium on Software Reliability Engineering, pages 267–276, 2005.

Digital Library

[40]

A. Leitner, M. Oriol, A. Zeller, I. Ciupa, and B. Meyer. Efficient unit test case minimization. In International Conference on Automated Software Engineering, pages 417–420, 2007.

Digital Library

[41]

V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10:707–710, 1966.

[42]

C. Parnin and A. Orso. Are automated debugging techniques actually helping programmers? In International Symposium on Software Testing and Analysis, pages 199–209, 2011.

Digital Library

[43]

L. Pike. SmartCheck: automatic and efficient counterexample reduction and generalization. In ACM SIGPLAN Symposium on Haskell, pages 53–64, 2014.

Digital Library

[44]

J. Regehr, Y. Chen, P. Cuoq, E. Eide, C. Ellison, and X. Yang. Test-case reduction for C compiler bugs. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 335–346, 2012.

Digital Library

[45]

J. Ruderman. Bug 329066 - Lithium, a testcase reduction tool (delta debugger). https://bugzilla.mozilla.org/show bug.cgi?id=329066, 2006.

[46]

J. Ruderman. Introducing jsfunfuzz, 2007. http://www.squarefree.com/2007/08/ 02/introducing-jsfunfuzz/.

[47]

J. Ruderman. Releasing jsfunfuzz and DOMFuzz. https://www.squarefree.com/ 2015/07/28/releasing-jsfunfuzz-and-domfuzz/, 2015.

[48]

user1689822. python AVL tree insertion. http://stackoverflow.com/questions/ 12537986/python-avl-tree-insertion.

[49]

X. Yang, Y. Chen, E. Eide, and J. Regehr. Finding and understanding bugs in C compilers. In ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 283–294, 2011.

Digital Library

[50]

A. Zeller and R. Hildebrandt. Simplifying and isolating failure-inducing input. Software Engineering, IEEE Transactions on, 28(2):183–200, 2002.

Digital Library

[51]

C. Zhang, A. Groce, and M. A. Alipour. Using test case reduction and prioritization to improve symbolic execution. In International Symposium on Software Testing and Analysis, pages 160–170, 2014.

Digital Library

[52]

S. Zhang. Practical semantic test simplification. In International Conference on Software Engineering, pages 1173–1176, 2013.

Digital Library

Cited By

Xu ZTian YZhang MZhang JLiu PJiang YSun C(2024)T-Rec: Fine-Grained Language-Agnostic Program Reduction Guided by Lexical SyntaxACM Transactions on Software Engineering and Methodology10.1145/369063134:2(1-31)Online publication date: 30-Aug-2024
https://dl.acm.org/doi/10.1145/3690631
Dutta SSelvam JJain AMisailovic SCadar CZhang X(2021)TERA: optimizing stochastic regression tests in machine learning projectsProceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3460319.3464844(413-426)Online publication date: 11-Jul-2021
https://dl.acm.org/doi/10.1145/3460319.3464844
Bluemke IMalanowska A(2021)Software Testing Effort Estimation and Related ProblemsACM Computing Surveys10.1145/344269454:3(1-38)Online publication date: 17-Apr-2021
https://dl.acm.org/doi/10.1145/3442694
Show More Cited By

Index Terms

One test to rule them all
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

A novel approach for test suite reduction based on requirement relation contraction
SAC '08: Proceedings of the 2008 ACM symposium on Applied computing

The goal of test suite reduction is to satisfy all testing requirements with the minimum number of test cases. Existing techniques can be applied well on the constructed test suite. However, it is possible and necessary to optimize testing requirements ...
Test Case Reduction Using Data Mining Technique

Software testing is a process of ratifying the functionality of software. It is a crucial area which consumes a great deal of time and cost. The time spent on testing is mainly concerned with testing large numbers of unreliable test cases. The authors' ...
A suite of tools for making effective use of automatically generated tests
ISSTA 2017: Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis

Automated test generation tools (we hope) produce failing tests from time to time. In a world of fault-free code this would not be true, but in such a world we would not need automated test generation tools. Failing tests are generally speaking the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA 2017: Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis

July 2017

447 pages

ISBN:9781450350761

DOI:10.1145/3092703

General Chair:
Tevfik Bultan
University of California at Santa Barbara, USA
,
Program Chair:
Koushik Sen
University of California at Berkeley, USA

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 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSTA '17

Sponsor:

SIGSOFT

ISSTA '17: International Symposium on Software Testing and Analysis

July 10 - 14, 2017

CA, Santa Barbara, 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

9
Total Citations
View Citations
398
Total Downloads

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

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xu ZTian YZhang MZhang JLiu PJiang YSun C(2024)T-Rec: Fine-Grained Language-Agnostic Program Reduction Guided by Lexical SyntaxACM Transactions on Software Engineering and Methodology10.1145/369063134:2(1-31)Online publication date: 30-Aug-2024
https://dl.acm.org/doi/10.1145/3690631
Dutta SSelvam JJain AMisailovic SCadar CZhang X(2021)TERA: optimizing stochastic regression tests in machine learning projectsProceedings of the 30th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3460319.3464844(413-426)Online publication date: 11-Jul-2021
https://dl.acm.org/doi/10.1145/3460319.3464844
Bluemke IMalanowska A(2021)Software Testing Effort Estimation and Related ProblemsACM Computing Surveys10.1145/344269454:3(1-38)Online publication date: 17-Apr-2021
https://dl.acm.org/doi/10.1145/3442694
Gopinath RNemati HZeller A(2021)Input AlgebrasProceedings of the 43rd International Conference on Software Engineering10.1109/ICSE43902.2021.00070(699-710)Online publication date: 22-May-2021
https://dl.acm.org/doi/10.1109/ICSE43902.2021.00070
Bai GRothermel GBae D(2020)Improving students' testing practicesProceedings of the ACM/IEEE 42nd International Conference on Software Engineering: Companion Proceedings10.1145/3377812.3381401(218-221)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377812.3381401
Holmes JGroce A(2020)Using mutants to help developers distinguish and debug (compiler) faultsSoftware Testing, Verification and Reliability10.1002/stvr.172730:2Online publication date: 13-Jan-2020
https://doi.org/10.1002/stvr.1727
Kalhauge CPalsberg JDumas MPfahl DApel SRusso A(2019)Binary reduction of dependency graphsProceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3338906.3338956(556-566)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3338906.3338956
Groce AFlikkema PHolmes JYu TMarinov D(2017)Towards automated composition of heterogeneous tests for cyber-physical systemsProceedings of the 1st ACM SIGSOFT International Workshop on Testing Embedded and Cyber-Physical Systems10.1145/3107091.3107094(12-15)Online publication date: 13-Jul-2017
https://dl.acm.org/doi/10.1145/3107091.3107094
Holmes JGroce ABultan TSen K(2017)A suite of tools for making effective use of automatically generated testsProceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3092703.3098220(356-359)Online publication date: 10-Jul-2017
https://dl.acm.org/doi/10.1145/3092703.3098220

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