Skip to content

Random Testing

Jump to bottom Edit New page
John Boyland edited this page Jun 10, 2025 · 6 revisions

Overview

Random testing as implemented here generates random commands to be run in a "situation under test" (SUT) and a reference implementation. If the results differ, we have found a failure that is reported by printing a sequence or calls to the SUT and their expected results. The last printed last is the one that failed. Random testing can perform millions of tests in a reasonable length of time and almost always detects simple errors such that a student may make in a data structures course.

Random testing works best on mutable classes with single-threaded instance methods. It does not work with static methods or with concurrent programs. It does handle the following aspects:

  • multiple instances of the SUT class
  • methods that return (new) mutable objects that share state
  • methods that return immutable objects compared using equals
  • specified exception results
  • partially specified results (e.g., iteration order in a hash table)
  • presumed nontermination of a method of the SUT (a timeout of one second is used).

As the reference implementation serves as the specification, an error in the reference implementation not present in the SUT will be reported as an error in the SUT. Nontermination (timeout) in the reference implementation will be reported as an internal error.

For usability, random testing prefers to generate short sequences of calls. As a result, even if a SUT fails after a million calls, the generated test is likely to be have no more then ten or twenty calls.

Using

Random testing provided to a developer (e.g., provided by an instructor to students implementing a specification) is a Java application. When the application is run, it typically first checks that assertions are enabled, requiring that they be enabled to help with testing. Assuming that assertions are enabled, it then starts generating tests and running them in the reference implementation and the SUT and comparing the results. While proceeding, it prints out the current test size and the number of tests generated, e.g.:

// Testing sequences of 10 commands.
// 100000 tests passed
// 200000 tests passed
// 300000 tests passed

If a failure is found, a JUnit test case with the faulty test is printed, e.g.:

// Testing sequences of 10 commands.
import junit.framework.TestCase;

import java.util.Iterator;
import edu.uwm.cs351.HexTileCollection;

public class TestGen extends TestCase {
	protected void assertException(Class<?> exc, Runnable r) {
		try {
			r.run();
			assertFalse("should have thrown an exception.",true);
		} catch (RuntimeException e) {
			if (exc == null) return;
			assertTrue("threw wrong exception type: " + e.getClass(),exc.isInstance(e));
		}
	}

	public void test() {
		HexTileCollection tc0 = new HexTileCollection();
		Iterator<HexTile> i0 = tc0.iterator();
		tc0.clear(); // should terminate normally
		assertException(java.util.NoSuchElementException.class, () -> i0.next());
	}
}

Here the problem is an over-active fail-fast system.

The JUnit test suit can then be copied into a new file in the ADT and run. The developer can perform debugging on it just as with any hand-written test.

Implementing

To implement random testing, one should extend the class AbstractRandomTest parameterized by the (main) reference implementation class (REF), and the (main) class being tested, called the Situation Under Test (SUT). The new class must call the super constructor with a number of parameters (explained below). The concrete class must also implement randomCommand taking a Java library Random instance and returning a Command instance.

Values

The values involved in testing: object instances passed as parameters, used as method receivers and returned in results are divided into two classes: objects and (pure) values. Pure values must be treated the same by the REF an SUT classes, must provide an equals method, and be convertible to string form and back. Pure values need not be actually immutable in Java, only immutable during random testing.

Object types are presumed mutable with object identity, and must be declared by calling registerMutableClass with the class for the reference implementation, the class for the SUT implementation (which is often the same as the class for the reference implementation), the way the type should be printed in a test and what (unique) prefix should be used for names of instances. This is done automatically for the REF and SUT classes by the AbstractRandomTest constructor. A common secondary mutable class is an iterator. As instances of object classes are created, they are remembered in a table which associates the REF instances with the corresponding SUT instances.

Only object values can be the receivers of method calls tested.

Lifting

When we execute commands, we need to distinguish a normal termination from an exceptional termination. Thus the commands will typically take functional values that return a Result<T> for some T. We distinguish ExceptionResult from NormalResult (for pure values) and from ObjectResult (for object values). There is a further result type ChoiceResult to handle nondeterminism. A void result is handled by a void normal result.

AbstractRandomTest provides a method lift (actually several overridings thereof) to convert a functional value to a lifted functional value. It catches any exception and returns an exception result, otherwise the appropriate value result (normal versus object, depending on additional arguments---an object result requires the registration information).

Commands

The command interface for random testing provides methods that enable a command to be run and also to be printed. A command encapsulates a method call or a constructor call. It has the following methods:

  • execute(asReference) This method executes the command, either using the reference implementation or the SUT implementation, depending on the boolean parameter.
  • code(lb) This method returns a string for the command using the literal builder parameter. A literal builder is a class with a toString method that accepts a value and returns a string representation for that object. AbstractRandomTest is a literal builder itself and handle converting all object values, strings, characters and various number classes to Java code. The concrete class extending AbstractRandomTest will need to override toString to support any additional pure value classes.

There are a number of predefined classes implementing this interface, each handling different configurations of arguments: whether pure values or object values. Object values are handled by passing in the mutable class registration as well as the index of the specific value in the table of instances (not the object itself). Pure values are handled by passing in the actual value. The constructors of Command classes also take functional values representing the method or constructor being called, as well as a string to be used to generate the code. By default, this string is taken as the name of the method, the receiver is placed before with a separator dot and the arguments are separated by commas and placed in parentheses after. However, one may also use a template with dollar sign ($) followed by a zero-based (single digit) index used to refer to a particular argument. If the system detects a dollar sign in the string, the template is used with all the arguments.

The AbstractRandomTest class provides a large number of overridings of build taking different sets of parameters to construct commands calling methods with zero, one, two, three parameters with special overridings handling cases where one or more of the parameters is of object type. They usually take a lifted version of the method and the method name (or a template).

If the provided command classes are insufficient or if one needs new forms of lifting or building, the random test developer can write their own. It is recommended to follow the style used in the source of AbstractRandomTest.

Constructor parameters

The AbstractRandomTest class constructor has a number of parameters:

  • rClass The reference class
  • sClass The SUT class, class being tested
  • typename The string to used to declare something of the SUT type.
  • prefix The prefix to use for local variables of the SUT class.
  • total The maximum number of tests to generate for each size.
  • testSize The maximum length of a test to generate. We start with a limit of ten tests before clearing everything and starting over with no objects. After total tests have been generated and tested successfully, we double the test size and start over generating total tests. Initially ten, and then doubled after executing total tests. This repeats until the testSize bound is exceeded, at which point the system declares that the SUT has passed random testing.
  • assertsRequired whether to fail immediately with a message if assertions are not enabled. (Default: true)

For example, if total is 800,000 and testSize is 1000, then the system will generate 800,000 tests, starting over with new values every ten tests, for a total of 80,000 ten call tests. Then it will generate 800,000 tests again but this time in 40,000 groups of twenty tests. And then again with 20,000 groups of forty tests, 10,000 groups of eighty tests, 5,000 groups of one hundred sixty tests, 2500 groups of three hundred and twenty tests and finally 1250 groups of six hundred and forty tests. In all this means over five millions tests are run. If all the tests pass, then a congratulatory message is printed. Of course, at the very first failure, the current group is printed as a test for the use of the developer.

randomCommand

The concrete random testing class that extends AbstractRandomTest must override randomCommand to take an instance of java.util.Random and return some sort of Command (in Java, Command<?>). If there are no instances of the SUT class (detected by checking mainClass.size()) , typically it will create one by returning newCommand(). Of course if the only constructor for the SUT class requires parameters, something more complex must be done.

Otherwise, it should use the random parameter to choose among the many methods specified, choose the receiver of a method call (as appropriate) and choose any parameters. Typically a large switch is used to select a method to call and then use r.nextInt(rc.size()) to select an instance of a mutable class registered (rc) to use as a receiver. Recall that object values are represented in the command classes by an index into the list of instances so far created.

Optional overrides

There are number of other methods that are intended to be overridden. Each should be overridden by a "decoration" overriding: the super method should be called appropriately.

printHelperMethods

This method is called when printing out a failed test: it is called after the test class is started but before the test method itself is printed. If the test needs to declare extra fields or methods in the test class, they should be printed with this method after calling super.

printImports

Typically the SUT class is in a custom package and must be imported into the test (which is presumed to be declared in the default package). Print your own imports after calling super.

toString

The toString method is called to render a value in a test call. The AbstractRandomTest class defines this to handle object values, strings and numbers. If the random test needs other pure values, it should override toString and check the type of the Object argument. If it matches a type that the random test system knows, it should return a string that evaluates to the value. Otherwise, it should defer to super.

Add a custom footer
Add a custom sidebar

Clone this wiki locally