Handling the Edge-Case Search-Space Explosion: A Case for Randomized Testing
For much of software testing the traditional quiver of unit, integration and system testing suffices. Your inputs typically have a main case and a small set of well understood edge cases you can cover. But: periodically, we come upon software problems where the range of acceptable inputs and the number of potential code paths is simply too large to have an acceptable degree of confidence in correctness of a software unit (be it a function, module, or entire system).
Enter The Fuzzer
When we hit this case at Sumo we’ve recently started applying a technique well known in the security-community but less commonly used in traditional development: fuzzing. Fuzzing in our context refers to randomized software testing on valid and invalid inputs. In the software development world, fuzzing is commonly used to test compilers, the classic case of an exploding search space. It has also gained traction recently in the Haskell community with QuickCheck, a module that can automagically build test cases for your code and test it against a given invariant. ScalaCheck aims to do the same for Scala, the language we use primarily at Sumo Logic.
The long and short of it is this: scala.util.Random coupled with a basic understanding of the range of inputs is better at thinking of edge cases than I am.
At Sumo, our product centers around a deep query language rife with potential edge cases to handle. We recently started replacing portions of the backend system with faster, more optimized, alternatives. This presented us with a great opportunity to fuzz both code paths against hundreds of thousands of randomly generated test queries and verify the equivalence of the results.
Fuzzers are great because they have no qualms about writing queries like “??*?r.” No human will ever write that query. I didn’t think about testing out that query. That doesn’t mean that no human will never be impacted by the underlying bug (*’s allowed the query parts to overlap on a document. Whoops.)
Of course, I probably should have caught that bug in unit testing. But there is a limit to the edge cases we can conceive, especially when we get tunnel vision around what we perceive to be the weak spots in the code. Your fuzzer doesn’t care what you think the weak spots are, and given enough time will explore all the meaningful areas of the search space. A fuzzer is only constrained by your ability define the search space and the time you allow it to run.
Fuzzing is especially useful if you already have a piece of code that is trusted to produce correct results. Even in the new-code case, however, fuzzing can still be invaluable for finding inputs that throw you into infinite loops or cause general crashes. In light of this, here at Sumo we’ve incorporated another test category into our hierarchy — Fuzzing tests, which sit in between unit tests and integration tests in our cadre of tests.
There are issues associated with incorporating random testing into your workflow. One should be rightfully concerned that your tests will be inherently flaky. Tests that whose executions are unpredictable, by necessity, have an associated stigma in the current testing landscape which rightfully strives for reproducibility in all cases.
In light of this, we’ve established best practices for addressing those concerns in the randomized testing we do at Sumo.
- Each run of a randomized test should utilize a single random number generator throughout. The random number generator should be predictably seeded (System.currentTimeMillis() is popular), and that seed should be logged along with the test run.
- The test should be designed to be rerunnable with a specific seed.
- The test should be designed to output specific errors that can trivially (or even automatically) be pulled into a deterministic test suite.
- All errors caught by a randomized test should be incorporated into a deterministic test to prevent regressions.
Following these guidelines allows us to create reproducible, actionable and robust randomized tests and goes a long way towards finding tricky corner cases before they can ever manifest in production.
(To see the end result of all of our programming efforts, please check out Sumo Logic Free.)