Random testing

<h2 id="history-of-random-testing">History of random testing</h2>
<p>Random testing for hardware was first examined by Melvin Breuer in 1971 and initial effort to evaluate its effectiveness was done by Pratima and <a href="/facts/Vishwani_Agrawal/qYDzJBKG">Vishwani Agrawal</a> in 1975.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p><p>In software, Duran and Ntafos had examined random testing in 1984.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p><p>The use of hypothesis testing as a theoretical basis for random testing was described by Howden in <i>Functional Testing and Analysis</i>. The book also contained the development of a simple formula for estimating the number of tests <i>n</i> that are needed to have confidence at least 1-1/<i>n</i> in a failure rate of no larger than 1/n. The formula is the lower bound <i>n</i>log<i>n</i>, which indicates the large number of failure-free tests needed to have even modest confidence in a modest failure rate bound.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="overview">Overview</h2>
<p>Consider the following C++ function:
</p>
int myAbs(int x) {
    if (x > 0) { 
        return x;
    }
    else {
        return x; // bug: should be '-x'
    }
}

<p>Now the random tests for this function could be {123, 36, -35, 48, 0}. Only the value '-35' triggers the bug. If there is no reference implementation to check the result, the bug still could go unnoticed. However, an <a href="/facts/Assertion_(software_development)/lxSfLdLY">assertion</a> could be added to check the results, like:
</p>
void testAbs(int n) {
    for (int i=0; i<n; i++) {
        int x = getRandomInput();
        int result = myAbs(x);
        assert(result >= 0);
    }
}

<p>The reference implementation is sometimes available, e.g. when implementing a simple algorithm in a much more complex way for better performance. For example, to test an implementation of the <a href="/facts/Sch%25C3%25B6nhage%25E2%2580%2593Strassen_algorithm/7dLGaI4d">Schönhage–Strassen algorithm</a>, the standard "*" operation on integers can be used:
</p>
int getRandomInput() {
    // …
}

void testFastMultiplication(int n) {
    for (int i=0; i<n; i++) {
        long x = getRandomInput();
        long y = getRandomInput();
        long result = fastMultiplication(x, y);
        assert(x * y == result);
    }
}

<p>While this example is limited to simple types (for which a simple random generator can be used), tools targeting object-oriented languages typically explore the program to test and find generators (constructors or methods returning objects of that type) and call them using random inputs (either themselves generated the same way or generated using a pseudo-random generator if possible). Such approaches then maintain a pool of randomly generated objects and use a probability for either reusing a generated object or creating a new one.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<h2 id="on-randomness">On randomness</h2>
<p>According to the seminal paper on random testing by D. Hamlet
</p>
<blockquote><p>[..] the technical, mathematical meaning of "random testing" refers to an explicit lack of "system" in the choice of test data, so that there is no correlation among different tests.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a></p></blockquote>
<h2 id="strengths-and-weaknesses">Strengths and weaknesses</h2>

<p>Random testing is praised for the following strengths:
</p>
<ul><li>It is cheap to use: it does not need to be smart about the program under test.</li>
<li>It does not have any bias: unlike manual testing, it does not overlook bugs because there is misplaced trust in some code.</li>
<li>It is quick to find bug candidates: it typically takes a couple of minutes to perform a testing session.</li>
<li>If software is properly specified: it finds real bugs.</li></ul>
<p>The following weaknesses have been described :
</p>
<ul><li>It only finds basic bugs (e.g. <a href="/facts/Null_pointer/66zwVEfL">null pointer</a> dereferencing).</li>
<li>It is only as precise as the specification and specifications are typically imprecise.</li>
<li>It compares poorly with other techniques to find bugs (e.g. <a href="/facts/Static_program_analysis/b56nr6QM">static program analysis</a>).</li>
<li>If different inputs are randomly selected on each test run, this can create problems for <a href="/facts/Continuous_integration/M4RYgSzt">continuous integration</a> because the same tests will pass or fail randomly.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a></li>
<li>Some argue that it would be better to thoughtfully cover all relevant cases with manually constructed tests in a white-box fashion, than to rely on randomness.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a></li>
<li>It may require a very large number of tests for modest levels of confidence in modest failure rates. For example, it will require 459 failure-free tests to have at least 99% confidence that the probability of failure is less than 1/100.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></li></ul>
<h2 id="types-of-random-testing">Types of random testing</h2>
<h3>With respect to the input</h3>
<ul><li>Random input sequence generation (i.e. a sequence of method calls)</li>
<li>Random sequence of data inputs (sometimes called stochastic testing) - e.g. a random sequence of method calls</li>
<li>Random data selection from existing database</li></ul>
<h3>Guided vs. unguided</h3>
<ul><li>undirected random test generation - with no heuristics to guide its search</li>
<li>directed random test generation - e.g. "feedback-directed random test generation"<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> and "adaptive random testing" <a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li></ul>
<h2 id="implementations">Implementations</h2>
<p>Some tools implementing random testing:
</p>
<ul><li><a href="/facts/QuickCheck/PSTnm0fh">QuickCheck</a> - a famous test tool, originally developed for <a href="/facts/Haskell_(programming_language)/4Htv9WLu">Haskell</a> but ported to many other languages, that generates random sequences of API calls based on a model and verifies system properties that should hold true after each run.</li>
<li>Randoop - generates sequences of methods and constructor invocations for the classes under test and creates <a href="/facts/JUnit/zlddF9S2">JUnit</a> tests from these</li>
<li>Simulant - a <a href="/facts/Clojure/3JRNxKXx">Clojure</a> tool that runs simulations of various agents (e.g. users with different behavioral profiles) based on a statistical model of their behavior, recording all the actions and results into a database for later exploration and verification</li>
<li>AutoTest - a tool integrated to EiffelStudio testing automatically Eiffel code with contracts based on the eponymous research prototype.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a>·</li>
<li>York Extensible Testing Infrastructure (YETI) - a language agnostic tool which targets various programming languages (Java, JML, CoFoJa, .NET, C, Kermeta).</li>
<li>GramTest - a grammar based random testing tool written in Java, it uses BNF notation to specify input grammars.</li></ul>
<h2 id="critique">Critique</h2>
<blockquote><p>Random testing has only a specialized niche in practice, mostly because an effective oracle is seldom available, but also because of difficulties with the operational profile and with generation of pseudorandom input values.<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></p></blockquote>
<p>A <a href="/facts/Test_oracle/rR9jNEma">test oracle</a> is an instrument for verifying whether the outcomes match the program specification or not. An operation profile is knowledge about usage patterns of the program and thus which parts are more important.
</p><p>For programming languages and platforms which have contracts (e.g. Eiffel. .NET or various extensions of Java like JML, CoFoJa...) contracts act as natural oracles and the approach has been applied successfully.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> In particular, random testing finds more bugs than manual inspections or user reports (albeit different ones).<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Fuzz_testing/I1GK5kxr">Fuzz testing</a> - a kind of random testing which provides invalid input to the tested program</li>
<li><a href="/facts/Lazy_systematic_unit_testing/1qlj9Mtm">Lazy systematic unit testing#Systematic Testing</a> - a systematic way of exploring "all" method calls, as implemented e.g. by NASA's <a href="https://web.archive.org/web/20110107010258/http://babelfish.arc.nasa.gov/trac/jpf/wiki/intro/what_is_jpf">Java Path Finder</a> (which blends <a href="https://web.archive.org/web/20110106040136/http://babelfish.arc.nasa.gov/trac/jpf/wiki/intro/testing_vs_model_checking">testing with model checking</a> by limiting the state space to a reasonable size by various means)</li>
<li><a href="/facts/SystemVerilog/wkBdc179">Constrained random generation in SystemVerilog</a></li>
<li><a href="/facts/Corner_case/5H80aVq9">Corner case</a></li>
<li><a href="/facts/Edge_case/E5po5oDy">Edge case</a></li>
<li><a href="/facts/Concolic_testing/lwhRWEla">Concolic testing</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.uio.no/studier/emner/matnat/ifi/INF4290/v10/undervisningsmateriale/INF4290-RandomTesting.pdf">Random testing</a> by Andrea Arcuri.</li>
<li><a href="http://web.cecs.pdx.edu/~hamlet/random.pdf">Random testing</a> by Richard Hamlet, professor emeritus at Portland State University; a valuable list of resources at the end of the paper</li>
<li><a href="http://c2.com/cgi/wiki?RandomTesting">Random Testing wiki</a> at Cunningham & Cunningham, Inc.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Richard Hamlet (1994). "Random Testing". In John J. Marciniak (ed.). Encyclopedia of Software Engineering (1st ed.). John Wiley and Sons. ISBN 978-0471540021. <a href="978-0471540021" target="_blank">978-0471540021</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Agrawal, P.; Agrawal, V. D. (1 July 1975). "Probabilistic Analysis of Random Test Generation Method for Irredundant Combinational Logic Networks". IEEE Transactions on Computers. C-24 (7): 691–695. doi:10.1109/T-C.1975.224289. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Duran, J. W.; Ntafos, S. C. (1 July 1984). "An Evaluation of Random Testing". IEEE Transactions on Software Engineering. SE-10 (4): 438–444. doi:10.1109/TSE.1984.5010257. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Howden, William (1987). Functional Program Testing and Analysis. New York: McGraw Hill. pp. 51–53. ISBN 0-07-030550-1. <a href="0-07-030550-1" target="_blank">0-07-030550-1</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>"AutoTest - Chair of Software Engineering". se.inf.ethz.ch. Retrieved 15 November 2017. <a href="http://se.inf.ethz.ch/research/autotest/" target="_blank">http://se.inf.ethz.ch/research/autotest/</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Richard Hamlet (1994). "Random Testing". In John J. Marciniak (ed.). Encyclopedia of Software Engineering (1st ed.). John Wiley and Sons. ISBN 978-0471540021. <a href="978-0471540021" target="_blank">978-0471540021</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>"Is it a bad practice to randomly-generate test data?". stackoverflow.com. Retrieved 15 November 2017. <a href="https://stackoverflow.com/q/636353" target="_blank">https://stackoverflow.com/q/636353</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>"Is it a bad practice to randomly-generate test data?". stackoverflow.com. Retrieved 15 November 2017. <a href="https://stackoverflow.com/q/636353" target="_blank">https://stackoverflow.com/q/636353</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Howden, William (1987). Functional Program Testing and Analysis. New York: McGraw Hill. pp. 51–53. ISBN 0-07-030550-1. <a href="0-07-030550-1" target="_blank">0-07-030550-1</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>Pacheco, Carlos; Shuvendu K. Lahiri; Michael D. Ernst; Thomas Ball (May 2007). "Feedback-Directed Random Test Generation" (PDF). 29th International Conference on Software Engineering (ICSE'07). pp. 75–84. doi:10.1109/ICSE.2007.37. ISBN 978-0-7695-2828-1. ISSN 0270-5257. <a href="978-0-7695-2828-1" target="_blank">978-0-7695-2828-1</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
<li id="fn:11"><p>T.Y. Chen; F.-C. Kuo; R.G. Merkel; T.H. Tse (2010), "Adaptive random testing: The ART of test case diversity", Journal of Systems and Software, 83 (1): 60–66, doi:10.1016/j.jss.2009.02.022, hdl:10722/89054 <a href="https://figshare.com/articles/journal_contribution/26243711" target="_blank">https://figshare.com/articles/journal_contribution/26243711</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li>
<li id="fn:12"><p>"AutoTest - Chair of Software Engineering". se.inf.ethz.ch. Retrieved 15 November 2017. <a href="http://se.inf.ethz.ch/research/autotest/" target="_blank">http://se.inf.ethz.ch/research/autotest/</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li>
<li id="fn:13"><p>Richard Hamlet (1994). "Random Testing". In John J. Marciniak (ed.). Encyclopedia of Software Engineering (1st ed.). John Wiley and Sons. ISBN 978-0471540021. <a href="978-0471540021" target="_blank">978-0471540021</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li>
<li id="fn:14"><p>"AutoTest - Chair of Software Engineering". se.inf.ethz.ch. Retrieved 15 November 2017. <a href="http://se.inf.ethz.ch/research/autotest/" target="_blank">http://se.inf.ethz.ch/research/autotest/</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li>
<li id="fn:15"><p>Ilinca Ciupa; Alexander Pretschner; Manuel Oriol; Andreas Leitner; Bertrand Meyer (2009). "On the number and nature of faults found by random testing". Software Testing, Verification and Reliability. 21: 3–28. doi:10.1002/stvr.415. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li>
</ol>

Random testing open-in-new

Random testing