C Object Preparer's Handbook
Table of Contents
- Overview
- Object Selection
- Object Organization
- Aristotle Usage
- Initial Object Setup
- Test Creation
- Coverage-Based Testing
- Gathering final test histories and test timings
- Fault Localization
- Generating Fault-Matrices
1. Overview
This document describes the steps we follow to set up a typical, less than 30 KLoc C program as an experiment object. It is written primarily as a set of instructions to persons who have set up these objects, and who continue to set up others, but it is also valuable as an aid to understanding the object setup, and choices made in that setup.
NOTE: In this document we focus on the "new" organization for C objects. Some details on the previous organization is available in the Appendix to this Document.
2. Object Selection
We seek C objects with qualifications as described in:
Initially, we want objects that definitely meet the four 1st-tier required-qualities, and that appear to meet (or can't be determined not to meet) the three 2nd-tier required-qualities.
After we have a collection of these, we determine which of these are worth considering further by seeing if they do in fact meet the 2nd-tier requirements. Completing this task requires downloading the objects.
Also part of this task is ensuring that you can build and run all versions of the program that we are considering using, and seeing what sort of output is involved. We need outputs that can be easily automatically checked by comparing with saved outputs. So, programs that manipulate the screen or produce graphical output where we'd have to save screen-dumps are not good candidates at this time. Programs that produce text output to the screen and/or output to files are fine. We also desire programs that are deterministic, or can be made so (see item 5.c below). This means that programs involving concurrency and heavy thread use might not be suitable.
3. Object Organization
After selecting objects we organize them into a format that supports later experimentation.
We have an agreed-on format described in the:
object directory specification
Read this format file and look at existing objects for examples. You'll be starting by working in the "versions" area, then later in "inputs" and "testplans" and "scripts", as we get to later tasks.
Note: It is important that you set the
environment variable "experiment_root" before working with
any of the SIR objects. This variable should provide the absolute path to the
directory into which you have placed the SIR object directories. This enables
scripts and tools to resolve needed paths without hardcoding system
specific paths.
4. Coverage tools.
We have used Aristotle to gather test coverage data for C object programs, as follows.
(Note: the Aristotle system that we use is not at this time publicly available, but other coverage tools could be substituted, and instructions on heir use substituted here.)
The instructions for use of Aristotle are:
- Configure your account to run Aristotle tools.
- Now, to learn how to use several specific Aristotle tools that you'll need, see the file:
- Finally, see if the specific tools and process outlined in the instructions you just followed work on your object. One issue here will be step 3 of those instructions -- you may have to add things to your compilation command to get your program to compile and link.
5. Initial Object Setup
For programs in the less than 20K range, we put them into single files to accommodate the Aristotle tool, which analyzes only single files.
(Note: It should be possible to accommodate multiple-file objects in this same infrastructure, if not using Aristotle, by including Makefiles for them. If these yield single executables they could likely be handled without special effort by our make-test-script tools.)
To create single-file object versions, we cat all the .c files that make up that version into one file. Header files can remain in multiple files. So the vk directory for version k contains a set of zero or more header files, and one .c file.
Of course, there are many complexities here. Putting .c files together may cause some problems, especially with global declarations at the tops of files, and multiple header file inclusions. These problems have to be resolved, but ultimately, any program that builds from multiple .c files should be able to reduce to one that builds from a single .c file.
Provide a Makefile that builds each version. It should initially require only a simple compilation command, perhaps with includes of libraries, since the source is in one file. Next, to build the instrumented version of the source program the Makefile should be modified to take the build-st and build-bt targets, as described in section 2 of the object directory specification.
IMPORTANT: we want the versions to look as similar to each other as possible. Put them all together in the same way. The diffs we see when diffing your single file versions should be the same as those we'd see if we diff'ed the pairs of files from the versions prior to their concatenation.
For some objects, we might decide to also exempt certain libraries provided with the code from the merging step, and keep those libraries separate, and assume that we're testing the code that is not included in the libraries.
Note that for some program versions, for example make, we have inadvertently disabled configuration support for compiling on multiple platforms, and the programs may not work on such others. It is possible, however, to look at the original distributions of objects contained in the tar packages, and use those materials to allow such objects to work on other systems. Here are some further comments about this.
6. Test Creation
Tests for the C objects in the repository are constructed using one of two methods. The primary (and preferred) method involves creating TSL specifications that are translated into test frames and subsequently into the actual tests. The second method used by the C objects is expect-send scripts. These test scripts utilize the Expect tool which provides a script-based mechanism for testing command-line interactive objects.
- TSL Specification Creation
TSL is a "Test Specification Language" used to write spec-based tests for a software system. When you write a test spec in this language, we have a tool that translates your spec into "test frames", from which you then generate tests.
To accomplish this task you should first read a paper on TSL: "The Category-Partition Method for Specifying and Generating Functional Tests" Thomas Ostrand and Marc Balcer, Communications of the ACM, Volume 31, Number 6, June 1988, pp 676-686. (The paper is available in the ACM Digital Library online).
Next, read the documentation on our TSL tool and TSL format (which is almost the same as the format described in the paper). This is contained in the file:
What you need to do is write a TSL spec for your base version, based on its documentation. (Or perhaps this is multiple TSL specs, since each spec corresponds to some portion of the functionality of the system.)
You need to ensure that this spec results in a sufficient but not excessive number of test frames. (For our 10 - 20K line programs, we decided that 500-2000 frames was the target range.) Add constraints to the TSL spec if necessary to reduce the number of frames.
Subsequent versions should be able to "inherit" this specification, or most of it, and may need additional tests based on new functionality, which can be encoded in an additional specification added to that version, or in a further refined TSL spec.
- TSL Test Creation
Creating test cases involves determining what inputs and input files are required, setting up those input files, and encoding the tests in a STImpL file. A program called "make-test-script" (MTS) transforms STImpL files into various types of scripts that can be used to automatically execute the tests or gather traces for the tests.
The format of the STImpL file, the types of scripts created by running MTS, and the usage of MTS, are described in file:
- Test and Script Validation
After you have created a STImpL specification for TSL tests, you should perform several validation tasks, that will help us determine if there are problems with the objects or tools. Details on the tasks are in:
Note that, as detailed in steps 1 and 2 of these instructions, this may reveal sources of nondeterminism. These need to be made deterministic. Also, all outputs must go to stdout, not stderr. (These requirements are necessary to allow automated regression testing with automated checking of outputs via output-differencing; these requirements arise partly due to the sheer volume of data we deal with in our experiments, but they are also typical requirements faced by testers in everyday testing activities, and the mechanisms we use to get around them are also used by test engineers in practice.) For details see:
- Expect Script Specification
Expect scripts provide a mechanism to automate actions to an object's user interface and capture the resultant output generated by these actions. Expect scripts contain a sequence of actions produced by send script operations, and expected results captured by expect script operations. The expect script tests typically are constructed to generate an output compatible with file difference comparison tools (diff, cmp, etc.). Objects in the repository using expect scripts have shell scripts provided to automate the execution of the expect scripts and collect the test output files into the common output location specified in the object directory specification
Expect script creation is similar to TSL test creation in that a sequence of sent actions result in consistent expected results. Expect scripts differ from TSL however in that these scripts are standalone and do not require transformation by the MTS tools into functional scripts. Generally, the same caveats noted for TSL scripts (object documentation based, with a sufficient but not excessive number of test frames) and storage of the test scripts follows the object directory specification guidelines. It is prudent to provide shell or Perl scripts that automate process of copying and executing the expect scripts as part of the object package in order for others to reproduce your fault matrices and seeded fault comparisons. Delivering README files within the scripts directory and the testplans.alt directories also help future users to run the expect test scripts suite upon the object.
7. Coverage-Based Testing
Once all TSL tests have been created, to create coverage-based tests for branch coverage adequacy, see:
(These instructions assume use of Aristotle, but other tools could be substituted.)
After creating the coverage based tests, repeat the validation tasks that were performed with TSL based tests with these new tests:
8. Gathering test histories and test timings
After performing all validation tasks for both TSL and coverage based tests, test histories can be generated as follows.
(These instructions assume use of Aristotle, but other tools could be substituted.)
After collecting final test histories, collect test timings as described in:
9. Fault Localization
Next, we want to find or create faults. There are two approaches for doing this in the objects:
- Find Existing faults, as described in:
- Seed faults, as described in:
10. Generating Fault-Matrices
After seeding faults in the versions, we can generate fault-matrices summarizing the relationship of test cases to faults, as described in:
Appendix
Previous C objects were organized somewhat differently than the newer objects described above in this document. Some details are provided here.