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

research-article

Formal analysis of the effectiveness and predictability of random testing

Authors:

Muhammad Zohaib Iqbal,

Lionel BriandAuthors Info & Claims

ISSTA '10: Proceedings of the 19th international symposium on Software testing and analysis

Pages 219 - 230

https://doi.org/10.1145/1831708.1831736

Published: 12 July 2010 Publication History

Abstract

There has been a lot of work to shed light on whether random testing is actually a useful testing technique. Despite its simplicity, several successful real-world applications appear in the literature. Although it is not going to solve all possible testing problems, random testing is an essential tool in the hands of software testers. In this paper, we address general questions about random testing, such as how long random testing needs on average to achieve testing targets (e.g., coverage), how does it scale and how likely is it to yield similar results if we re-run random testing on the same testing problem. Due to its simplicity that makes the mathematical analysis of random testing tractable, we provide precise and rigorous answers to these questions. Our formal results can be applied to most types of software and testing criteria. Simulations are carried out to provide further support to our formal results. The obtained results are then used to assess the validity of empirical analyses reported in the literature. Results show that random testing is more effective and predictable than previously thought.

References

[1]

A. Arcuri. Theoretical analysis of local search in software testing. In Symposium on Stochastic Algorithms, Foundations and Applications (SAGA), pages 156--168, 2009.

Digital Library

[2]

A. Arcuri. Longer is better: On the role of test sequence length in software testing. In IEEE International Conference on Software Testing, Verification and Validation (ICST), pages 469--478, 2010.

Digital Library

[3]

A. Arcuri, D. R. White, J. Clark, and X. Yao. Multi-objective improvement of software using co-evolution and smart seeding. In International Conference on Simulated Evolution And Learning (SEAL), pages 61--70, 2008.

Digital Library

[4]

A. Arcuri and X. Yao. Search based software testing of object-oriented containers. Information Sciences, 178(15):3075--3095, 2008.

Digital Library

[5]

P. J. Boland, H. Singh, and B. Cukic. Comparing partition and random testing via majorization and schur functions. IEEE Transactions on Software Engineering, 29(1):88--94, 2003.

Digital Library

[6]

T. Y. Chen, F. C. Kuo, and R. Merkel. On the statistical properties of testing effectiveness measures. Journal of Systems and Software, 79(5):591--601, 2006.

Digital Library

[7]

I. Ciupa, A. Pretschner, M. Oriol, A. Leitner, and B. Meyer. On the number and nature of faults found by random testing. Software Testing, Verification and Reliability, 2009. (in press).

Digital Library

[8]

J. W. Duran and S. C. Ntafos. An evaluation of random testing. IEEE Transactions on Software Engineering, 10(4):438--444, 1984.

Digital Library

[9]

W. Feller. An Introduction to Probability Theory and Its Applications, Vol. 1. Wiley, 3 edition, 1968.

[10]

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

Digital Library

[11]

W. J. Gutjahr. Optimal test distributions for software failure cost estimation. IEEE Transactions on Software Engineering, 21(3):219--228, 1995.

Digital Library

[12]

W. J. Gutjahr. Partition testing vs. random testing: The influence of uncertainty. IEEE Transactions on Software Engineering, 25(5):661--674, 1999.

Digital Library

[13]

D. Hamlet and R. Taylor. Partition testing does not inspire confidence. IEEE Transactions on Software Engineering, 16(12):1402--1411, 1990.

Digital Library

[14]

R. Hamlet. Random testing. In Encyclopedia of Software Engineering, pages 970--978. Wiley, 1994.

[15]

M. Harman, S. G. Kim, K. Lakhotia, P. McMinn, and S. Yoo. Optimizing for the number of tests generated in search based test data generation with an application to the oracle cost problem. In International Workshop on Search-Based Software Testing (SBST), 2010.

Digital Library

[16]

M. Harman and P. McMinn. A theoretical and empirical study of search based testing: Local, global and hybrid search. IEEE Transactions on Software Engineering, 36(2):226--247, 2010.

Digital Library

[17]

L. Holst. Extreme value distributions for random coupon collector and birthday problems. Extremes, 4(2):129--145, 2001.

[18]

P. McMinn. Search-based software test data generation: A survey. Software Testing, Verification and Reliability, 14(2):105--156, 2004.

Digital Library

[19]

M. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[20]

G. Myers. The Art of Software Testing. Wiley, New York, 1979.

Digital Library

[21]

C. Pacheco, S. K. Lahiri, M. D. Ernst, and T. Ball. Feedback-directed random test generation. In IEEE International Conference on Software Engineering (ICSE), pages 75--84, 2007.

Digital Library

[22]

B. Rosén. Asymptotic normality in a coupon collector's problem. Probability Theory and Related Fields, 13(3):256--279, 1969.

[23]

S. Shioda. Some upper and lower bounds on the coupon collector problem. Journal of Computational and Applied Mathematics, 200(1):154--167, 2007.

Digital Library

[24]

T. A. Thayer, M. Lipow, and E. C. Nelson. Software Reliability. North Holland, Amsterdam, 1978.

[25]

P. Thévenod-Fosse and H. Waeselynck. An investigation of statistical software testing. Software Testing, Verification and Reliability, 1(2):5--25, 1991.

Digital Library

[26]

M. Z. Tsoukalas, J. W. Duran, and S. C. Ntafos. On some reliability estimation problems in random and partition testing. IEEE Transactions on Software Engineering, 19(7):687--697, 1993.

Digital Library

[27]

J. Wegener, A. Baresel, and H. Sthamer. Evolutionary test environment for automatic structural testing. Information and Software Technology, 43(14):841--854, 2001.

[28]

E. J. Weyuker and B. Jeng. Analyzing partition testing strategies. IEEE Transactions on Software Engineering, 17(7):703--711, 1991.

Digital Library

[29]

Y. Zhan and J. A. Clark. A search-based framework for automatic testing of matlab/simulink models. Journal of Systems and Software, 81(2):262--285, 2008.

Digital Library

Cited By

Semujju SHuang HLiu FXiang YHao Z(2023)Search-Based Software Test Data Generation for Path Coverage Based on a Feedback-Directed MechanismComplex System Modeling and Simulation10.23919/CSMS.2022.00273:1(12-31)Online publication date: Mar-2023
https://doi.org/10.23919/CSMS.2022.0027
Groce ADe Meuter WBaniassad E(2021)Let a thousand flowers bloom: on the uses of diversity in software testingProceedings of the 2021 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3486607.3486772(136-144)Online publication date: 20-Oct-2021
https://dl.acm.org/doi/10.1145/3486607.3486772
Wu HNie CPetke JJia YHarman M(2020)An Empirical Comparison of Combinatorial Testing, Random Testing and Adaptive Random TestingIEEE Transactions on Software Engineering10.1109/TSE.2018.285274446:3(302-320)Online publication date: 1-Mar-2020
https://doi.org/10.1109/TSE.2018.2852744
Show More Cited By

Index Terms

Formal analysis of the effectiveness and predictability of random testing

Recommendations

Random Testing: Theoretical Results and Practical Implications

A substantial amount of work has shed light on whether random testing is actually a useful testing technique. Despite its simplicity, several successful real-world applications have been reported in the literature. Although it is not going to solve all ...
On the Predictability of Random Tests for Object-Oriented Software
ICST '08: Proceedings of the 2008 International Conference on Software Testing, Verification, and Validation

Intuition suggests that random testing of object-oriented programs should exhibit a significant difference in the number of faults detected by two different runs of equal duration. As a consequence, random testing would be rather unpredictable. We ...
Fault detection effectiveness of source test case generation strategies for metamorphic testing
MET '18: Proceedings of the 3rd International Workshop on Metamorphic Testing

Metamorphic testing is a well known approach to tackle the oracle problem in software testing. This technique requires the use of source test cases that serve as seeds for the generation of follow-up test cases. Systematic design of test cases is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSTA '10: Proceedings of the 19th international symposium on Software testing and analysis

July 2010

294 pages

ISBN:9781605588230

DOI:10.1145/1831708

General Chair:
Paolo Tonella
Fondazione Bruno Kessler -- IRST, Italy
,
Program Chair:
Alessandro Orso
Georgia Institute of Technology, USA

Copyright © 2010 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

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: 12 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSTA '10

Sponsor:

SIGSOFT

ISSTA '10: International Symposium on Software Testing and Analysis

July 12 - 16, 2010

Trento, Italy

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

53
Total Citations
View Citations
875
Total Downloads

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

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Semujju SHuang HLiu FXiang YHao Z(2023)Search-Based Software Test Data Generation for Path Coverage Based on a Feedback-Directed MechanismComplex System Modeling and Simulation10.23919/CSMS.2022.00273:1(12-31)Online publication date: Mar-2023
https://doi.org/10.23919/CSMS.2022.0027
Groce ADe Meuter WBaniassad E(2021)Let a thousand flowers bloom: on the uses of diversity in software testingProceedings of the 2021 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3486607.3486772(136-144)Online publication date: 20-Oct-2021
https://dl.acm.org/doi/10.1145/3486607.3486772
Wu HNie CPetke JJia YHarman M(2020)An Empirical Comparison of Combinatorial Testing, Random Testing and Adaptive Random TestingIEEE Transactions on Software Engineering10.1109/TSE.2018.285274446:3(302-320)Online publication date: 1-Mar-2020
https://doi.org/10.1109/TSE.2018.2852744
Shioda S(2020)Coupon Subset Collection Problem with QuotasMethodology and Computing in Applied Probability10.1007/s11009-020-09811-zOnline publication date: 27-Jul-2020
https://doi.org/10.1007/s11009-020-09811-z
Zhang MGong YWang YJin D(2019)Unit Test Data Generation for C Using Rule-Directed Symbolic ExecutionJournal of Computer Science and Technology10.1007/s11390-019-1935-734:3(670-689)Online publication date: 10-May-2019
https://doi.org/10.1007/s11390-019-1935-7
Liang HPei XJia XShen WZhang J(2018)Fuzzing: State of the ArtIEEE Transactions on Reliability10.1109/TR.2018.283447667:3(1199-1218)Online publication date: Sep-2018
https://doi.org/10.1109/TR.2018.2834476
Qi GTsai WColbourn CLuo JZhu Z(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
https://doi.org/10.1109/TR.2018.2833449
Oliveira CAleti AGrunske LSmith-Miles K(2018)Mapping the Effectiveness of Automated Test Suite Generation TechniquesIEEE Transactions on Reliability10.1109/TR.2018.283207267:3(771-785)Online publication date: Sep-2018
https://doi.org/10.1109/TR.2018.2832072
Rehman Khan SLee SJavaid NAbdul W(2018)A Systematic Review on Test Suite Reduction: Approaches, Experiment’s Quality Evaluation, and GuidelinesIEEE Access10.1109/ACCESS.2018.28096006(11816-11841)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2809600
Holmes JGroce APinto JMittal PAzimi PKellar KO'brien J(2018)TSTLInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-016-0445-y20:1(57-78)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s10009-016-0445-y
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