Constrained Random Testing

Motivation and Problems

It is difficult for the writer of software to devise tests which expose problems in a program because the programmer is used to following the logical flow of the program, while software errors are often reached by following unusual patterns of usage. However, the end-user does not have the preconceptions of normal usage held by the programmer and may well follow such usage. In addition, the "functional envelope", the total number of different sets of input stimulus that even a simple program could receive is vast, and achieving coverage with tests is a correspondingly huge task.

One approach to the problem is to generate pseudo-random stimulus. A procedure uses a random number generator to repetitively choose from any one of the possible operator widget interactions available to the user, and invokes it. While this can generate stimulus with high productivity, it presents other problems:

The TSIPPwb Random Testing Feature

The TSIPPwb is provided with a random testing facility which addresses these concerns and has been used to find several obscure problems. The command "randomTest::randomTest" is declared with the "opt" package and takes a number of optional parameters. A summary listing can be obtained with the command "randomTest::randomTest -help". The following table gives a more detailed description.
Options to the command "randomTest::randomTest"
Flag Type Default Value Description
-opLimit int (0) Limit on the number of operations to be performed in the test, 0 implying unlimited
-opLog string () Pathname of a file to which a continuous audit of operations will be written
-seed int (88888) Seed, passed to srand () on the first call to this procedure
-monWin boolflag (true) Display a special toplevel window with the status of the testing. Unfortunately, depending on the window manager that you use, this may not appear on top, although this is necessary if it is to be of use.
-userErrorLog string () File to which statistics on the occurrence of user errors are written
-maxMultiView int (5) Maximum number of MultiViews that may be created simultaneously
-minMultiView int (0) Minimum number of MultiViews that may be created simultaneously
-maxMotion int (25) Number of motion binding invocations between press and release
-minSelect float (0.0) Rubber band selection must select from an area of at least this amount of the view in each direction
-minZoom float (0.7) Zoom is constrained to change the view within the range (minZoom, 1/minZoom)
-minTool float (0.4) Modeling tool definitions are constrained to cover the view within the range (minTool, 1/minTool)
-minCreate float (0.1) Objects must be sized by at least this amount of the view in each direction
-motionDelta int (30) Number of pixels change between consecutive motion binding invocations
-milliseconds int (0) Period between internal consistency checks within each MultiView. USE "-checkSelected" instead.
-checkSelected boolflag (false) After each operation, check the consistency of the canvas selection with selectedObjects
-checkShaders boolflag (false) After each operation, check the correctness of the AutoDestruct usage counters of all Shaders
-checkVertexSet boolflag (false) After each operation, check that all Polygon vertex linking is bi-directional
-checkAggregate boolflag (false) After each operation, check that all Aggregations are properly owned by Freehand and MultiView
-maxRender_ms int (100) Rendering operations are aborted after the specified number of milliseconds (never if zero)
-maxMemory float (100.0) MultiViews will be deleted if the program is using more than the specified percentage of memory. NOT RECOMMENDED

General Test Control

The options shown in black are general controls which specify the seed for the random number generator, the log files to be generated, whether a small interactive monitor window is to be created showing the progress of the test, and the test duration. This latter control, "-opLimit" is key to the investigation of a problem, as explained in Problem Investigation.

Statistical Test Control

The options shown in green constrain the behavior of the program to prevent excessive resource consumption and make the tests cover the functional envelope effectively. For example, rendering operations in TSIPP are often slow. It is considered valuable to invoke a rendering operation because the TSIPPwb performs certain operations only on rendering, but the rendering operation itself is likely to complete if it begins successfully.  Therefore, the option "-maxRender_ms" causes an "after" command to be set up to terminate the rendering after a certain time, 100 ms by default. Limiting the number of MultiViews constrains memory resource use.

In addition, the operations and their parameters are selected using a weighted random deviate, to guide the test while not precluding unusual paths. The weightings are hard-coded in lists within the randomTest procedure code. For example, the probability of MultiView deletion is slightly higher than MultiView creation, and object deletion more likely than copying. These biases keep the memory usage down. An experimental option "-maxMemory" is not recommended: it relies on the memory size of the program reported by "ps" - this does not appear to reduce when objects are deleted. Consequently, using the feature is likely to result in all MultiViews being deleted. Even if this problem could be overcome, tests may not be reproducible because memory usage could reach a threshold at a different point in time on each run due to competition for resource from other programs.

Constraints on the amount of Zoom and the sizes of objects which are created helps to avoid size constraints in SIPP/TSIPP.

Internal Consistency Monitoring

Flags shown in red enable internal consistency checks which are performed after each operation. Although verifying the internal consistency is not equivalent to checking the function of the program, they expose a class of problems which are some of the most unpredictable in their affect as perceived by the user and difficult to analyze and correct.

Problem Investigation

The Random Testing would normally be carried out as follows.
  1. Initially, the flag "-opLimit" would not be be used, so that the test continues indefinitely.
  2. If a problem occurs, then this could result in different symptoms, such as
  3. In the case of a Tcl error then a stack trace will be generated. In the other cases, the log file generated with the flag "-opLog <filename>" will be essential to understanding the problem.  At the end of this file you will find details of the last command executed successfully and possibly the failed command, and in particular the operation numbers of these commands.
  4. The test should be re-run specifying an opLimit slightly less than the number of the operation where the test failed. Specifically, if the test fails on operation <n>, then specifying "-opLimit <n>" will cause all but the failing operations to be executed. Note that the random number generator is only initialized on the first run of this procedure, irrespective of whether a value is provided with the flag "-seed". Therefore, it would then be possible to rerun the failing operation with "-opLimit 1".
  5. If possible, the problem should be fixed in such a way that the behavior of the program during the random test prior to the point of failure is unchanged, in order that the failing test case can be applied to the modified program.

User Error Log

When the TSIPPwb recognizes certain operator errors, a dialog box is presented containing an error message and the user is asked to confirm that it has been read. If such an operator error is generated during a random test, no interaction with the user occurs, but the message is stored and a file is generated containing a consolidated list of these errors. The file is rewritten whenever a user error occurs. An example file is shown in the following table. Amazingly, it contains one case of the error that the StdCamera is being pointed straight up or down. As the StdCamera may be moved throughout a sphere of motion, to a position defined with floating point numbers, this is highly unlikely to arise during a random test.
Log file generated with the flag "-userErrorLog"
7534 Need to render this frame before it can be fixed
1772 New items created since rendering - use the "Render" button to correct this
3891 STD_CAMERA cannot be copied - other items will be copied
3737 STD_CAMERA cannot be deleted - other items will be deleted
1 TSIPP returned the following error while processing a Cone - "". Try to edit the image to avoid this.
7 TSIPP returned the following error while processing a Cuboid - "sizes X Y and Z must be > 0.0".  Try to edit the image to avoid this.
14 TSIPP returned the following error while processing a Ellipsoid- " radius X Y and Z must be > 0.0".  Try to edit the image to avoid this.
9 TSIPP returned the following error while processing a StdCamera - "The position and point may not be the same".  Try to edit the image to avoid this.
1 TSIPP returned the following error while processing a StdCamera - "The view vector (position to point) and up vector may not be parallel". Try to edit the image to avoid this.
382 This handle motion on an item of class StdCamera has caused a problem - "divide by zero".  Try to edit the image differently to avoid this.

Tips and Tricks