[Top] [Prev] [Next] [Index] [TOC]

Chapter 11

Regress: A Tool for Effective Regression Testing

The purpose of regression testing is to ensure that changes made to software, such as adding new features or modifying existing features, do not adversely affect features of the software that should not change. It is not cost-effective to rerun all the tests in a regression suite; a method is needed to reduce the testing effort. Regress is just such a tool which supports test set minimization and test prioritization. It helps testers identify a representative subset of tests which should be re-executed to revalidate modified software.

11.1 Background

No matter how well conceived and tested software is, it will eventually have to be modified in order to fix bugs or respond to changes in user specifications. Regression testing must be conducted to confirm that recent program changes have not adversely affected existing features and new tests must be created to test new features. Testers might rerun all test cases generated at earlier stages to ensure that the program behaves as expected. However, as a program evolves the regression test set grows larger, old tests are rarely discarded, and the expense of regression testing grows. Repeating all previous test cases in regression testing after each minor software revision or patch is often impossible due to time pressure and budget constraints. On the other hand, for software revalidation, arbitrarily omitting test cases used in regression testing is risky. Thus, we need to investigate methods to select small subsets of effective fault-revealing regression test cases to revalidate software. It is for this purpose that Regress, a test set minimization and prioritization tool, was developed.

Regress supports test set minimization to reduce the number of test cases contained in a test set without loss of code coverage. In other words, it minimizes a test set to find a minimal subset in terms of the number of test cases that preserves the code coverage with respect to a certain criterion (block, decision, c-use, p-use or all-uses as explained in Section 3.3, What Does ATAC Do?) of the original test set. Regress also supports test set prioritization by sorting tests in increasing order of additional coverage per cost.

For test set minimization, Regress uses an implicit enumeration algorithm with reductions to find the optimal subset based on all tests examined. In addition, to determine the exact minimized subset, Regress also provides options to select a fast but approximate solution based on greedy heuristics in case the exact solution is not obtained in reasonable time. For test set prioritization, Regress first selects a test case which gives the maximal coverage with respect to a given criterion per unit cost. Subsequent tests are selected based on their additional coverage per unit cost.

When testers can only afford to re-execute a few regression tests, they can either use every test case in the minimized subset for software revalidation or select as many tests as possible on the basis of test case priority, i.e., starting from the top of the prioritized test list. The rationale behind these two techniques is the following:

  1. The correlation between the fault detection capability of a test set and its code coverage on a program is higher than that between the fault detection capability and test set size. Insufficient testing such as long hours of test case execution that do not increase code coverage can lead to an incorrect assessment of program reliability.

  2. No matter how a test set is generated, its minimized test sets have a size/effectiveness advantage over the original set in terms of fewer test cases with little or no compromise in the strength of revealing faults.

  3. In general, a reduced set of tests selected by minimization/prioritization can detect faults not detected by a reduced set of the same size selected in a random or arbitrary way. Null hypothesis testing indicates that such effectiveness advantage of minimization/prioritization over randomization does not just happen by chance.

In practice, depending on the available resources, a trade-off between what we can do in regression testing and what we can afford to do is applied to determine which test, among those necessary, should be re-executed first, and which one has lower priority or is to be omitted from re-execution. Our experience suggests that although neither test set minimization nor prioritization can reduce the cost of testing the current release, it may significantly reduce the cost of testing future releases of a software system. This savings arises because less time is spent maintaining, documenting, executing, and evaluating the output of smaller test sets.

The remainder of this chapter is organized as follows: Section 11.2 describes how to conduct test set minimization via a character-based user interface, Section 11.3 describes how to perform test set prioritization via a character-based user interface and Section 11.4 explains how these procedures are executed via a graphical user interface.

11.2 Test set minimization via a character-based user interface

In this section we explain how test set minimization is done via a character-based user interface. The same wordcount program as used before is used here. To copy these files, create a new directory, cd to it, and copy the contents of the directory in which the tutorial files are installed into the new directory. For the illustrations in this chapter, we will use: (1) two c files: main.c and wc.c, (2) three data files: input1, input2, and input3, (3) the Makefile and (4) the tests_regress script. Compile the wordcount program with ATAC. Refer to Appendix A, Platform Specific Information to determine the correct command to execute for your setup.

After the compilation, two .atac files (main.atac for main.c and wc.atac for wc.c) and the executable wordcount(.exe) are created. Note, one .atac file is created for each instrumented .c file, i.e., the .c files compiled with ATAC.

Now let's repeat all the tests executed in Chapter 2, ATAC: A Tutorial, and assign costs to each of these tests, as specified in Section 7.6, Assigning Cost to Test Cases.To save typing, these commands have been collected in a script file called tests_regress(.bat). Figure 11-1 lists the commands it executes. First, remove all files with a .trace suffix. Then run the script by typing tests_regress. While the script is running, you will see some `error' messages because the tests are executing lines of code designed to handle error conditions. 

 ===== These tests are executed =====

 wordcount input1          
 wordcount -x input1      
 wordcount < input1      
 wordcount nosuchfile   
 wordcount -wlc input1 
 wordcount input1 input2 
 wordcount "-?"         
 wordcount -l input1   
 wordcount -w input1  
 wordcount -l < input1    
 wordcount -w < input1   
 wordcount -c < input1  
 wordcount -l nosuchfile 
 wordcount -lx input1   
 wordcount input1 nosuchfile
 wordcount empty           
 wordcount input3         

 ===== These cost assignments are executed ======

 atactm  -n wordcount.1   -c 120  wordcount.trace
 atactm  -n wordcount.2   -c 50   wordcount.trace
 atactm  -n wordcount.3   -c 20   wordcount.trace
 atactm  -n wordcount.4   -c 10   wordcount.trace
 atactm  -n wordcount.5   -c 40   wordcount.trace
 atactm  -n wordcount.6   -c 60   wordcount.trace
 atactm  -n wordcount.7   -c 80   wordcount.trace
 atactm  -n wordcount.8   -c 20   wordcount.trace
 atactm  -n wordcount.9   -c 10   wordcount.trace
 atactm  -n wordcount.10  -c 70   wordcount.trace
 atactm  -n wordcount.11  -c 50   wordcount.trace
 atactm  -n wordcount.12  -c 50   wordcount.trace
 atactm  -n wordcount.13  -c 50   wordcount.trace
 atactm  -n wordcount.14  -c 40   wordcount.trace
 atactm  -n wordcount.15  -c 60   wordcount.trace
 atactm  -n wordcount.16  -c 20   wordcount.trace
 atactm  -n wordcount.17  -c 150  wordcount.trace
Figure 11-1 Commands executed by the tests_regress script

After the script finishes, run atac with the -q option to print out the cumulative coverage with respect to each test case. The output of: 

	prompt:> atac -q main.atac wc.atac wordcount.trace
is in Figure 11-2. From this figure, it is obvious that some tests are redundant in terms of coverage. A minimal cost subset of these tests which has the same block, decision and all- uses coverage as the original set can be obtained by executing the command: 
	prompt:> atac -Mq main.atac wc.atac wordcount.trace


% blocks      % decisions   % C-Uses      % P-Uses      test

(cumulative)  (cumulative)  (cumulative)  (cumulative)  

------------- ------------- ------------- ------------- ------------- 

69(35/51)     57(20/35)     45(41/92)     71(22/31)     wordcount.1

80(41/51)     66(23/35)     50(46/92)     74(23/31)     wordcount.2

86(44/51)     71(25/35)     53(49/92)     81(25/31)     wordcount.3

90(46/51)     74(26/35)     55(51/92)     84(26/31)     wordcount.4

100(51)       86(30/35)     72(66/92)     84(26/31)     wordcount.5

100(51)       89(31/35)     80(74/92)     87(27/31)     wordcount.6

100(51)       91(32/35)     80(74/92)     87(27/31)     wordcount.7

100(51)       97(34/35)     85(78/92)     94(29/31)     wordcount.8

100(51)       100(35)       87(80/92)     97(30/31)     wordcount.9

100(51)       100(35)       90(83/92)     97(30/31)     wordcount.10

100(51)       100(35)       92(85/92)     97(30/31)     wordcount.11

100(51)       100(35)       93(86/92)     97(30/31)     wordcount.12

100(51)       100(35)       95(87/92)     97(30/31)     wordcount.13

100(51)       100(35)       96(88/92)     97(30/31)     wordcount.14

100(51)       100(35)       97(89/92)     97(30/31)     wordcount.15

100(51)       100(35)       100(92)       97(30/31)     wordcount.16

100(51)       100(35)       100(92)       100(31)       wordcount.17
Figure 11-2 The cumulative coverage per test case
The output so generated is displayed in Figure 11-3 with tests in order of decreasing added coverage per unit cost. Since ATAC minimization does not modify the .trace file, for those tests which are not included in the minimal subset such as wordcount.1, their corresponding trace information remains in the trace file unless it is deleted explicitly by atactm with the -d option (see Section 7.5, Deleting Test Cases). After this minimization, test set size is reduced from 17 to 16. A bigger size reduction can be obtained by doing minimization with respect to a different coverage criterion (see Section 11.2.3, Minimizing by Coverage Criteria). 

      % blocks      % decisions   % C-Uses      % P-Uses      test
      (cumulative)  (cumulative)  (cumulative)  (cumulative)  
      ------------- ------------- ------------- ------------- ------------- 
      75(38/51)     66(23/35)     49(45/92)     71(22/31)     wordcount.9
      80(41/51)     74(26/35)     66(61/92)     81(25/31)     wordcount.16
      84(43/51)     77(27/35)     68(63/92)     84(26/31)     wordcount.4
      90(46/51)     83(29/35)     72(66/92)     90(28/31)     wordcount.3
      92(47/51)     89(31/35)     76(70/92)     94(29/31)     wordcount.8
      92(47/51)     91(32/35)     85(78/92)     97(30/31)     wordcount.6
      98(50/51)     94(33/35)     87(80/92)     97(30/31)     wordcount.14
      100(51)       97(34/35)     90(83/92)     97(30/31)     wordcount.5
      100(51)       97(34/35)     93(86/92)     97(30/31)     wordcount.11
      100(51)       97(34/35)     96(88/92)     97(30/31)     wordcount.12
      100(51)       97(34/35)     97(89/92)     97(30/31)     wordcount.2
      100(51)       97(34/35)     98(90/92)     97(30/31)     wordcount.13
      100(51)       97(34/35)     99(91/92)     97(30/31)     wordcount.15
      100(51)       97(34/35)     100(92)       97(30/31)     wordcount.10
      100(51)       100(35)       100(92)       97(30/31)     wordcount.7
      100(51)       100(35)       100(92)       100(31)       wordcount.17
Figure 11-3 The minimal subset with the same block, decision and all-uses coverage as the original test set

11.2.1 Forcing Tests to be in the Minimal Set

There are some tests that you always want to be included in the minimal set regardless of whether they provide additional cost-effective code coverage, such as tests that detect previously fixed programming faults. You can force the inclusion of such tests in the minimal set by giving them a cost of 0 using atactm.

11.2.2 Choosing a Reduced Subset after Minimization

In some cases, a cost effective test set need not be minimal. Suppose you only have two hours to execute some subset of your regression test set; then you would like to execute the most effective subset during that time. You may wish to make the cost versus effectiveness trade-off decision yourself. In this case you can run ATAC minimization with the -K option to print out a cumulative summary of the cost. For example, a cumulative summary as shown in Figure 11-4 for tests in Figure 11-1 is generated by entering: 
	prompt:> atac -MKq  main.atac wc.atac wordcount.trace


        cost   % blocks      % decisions   % C-Uses      % P-Uses      test
        (cum)  (cumulative)  (cumulative)  (cumulative)  (cumulative)  
        ------ ------------- ------------- ------------- ------------- ------------- 
        10     75(38/51)     66(23/35)     49(45/92)     71(22/31)     wordcount.9
        30     80(41/51)     74(26/35)     66(61/92)     81(25/31)     wordcount.16
        40     84(43/51)     77(27/35)     68(63/92)     84(26/31)     wordcount.4
        60     90(46/51)     83(29/35)     72(66/92)     90(28/31)     wordcount.3
        80     92(47/51)     89(31/35)     76(70/92)     94(29/31)     wordcount.8
        140    92(47/51)     91(32/35)     85(78/92)     97(30/31)     wordcount.6
        180    98(50/51)     94(33/35)     87(80/92)     97(30/31)     wordcount.14
        220    100(51)       97(34/35)     90(83/92)     97(30/31)     wordcount.5
        270    100(51)       97(34/35)     93(86/92)     97(30/31)     wordcount.11
        320    100(51)       97(34/35)     96(88/92)     97(30/31)     wordcount.12
        370    100(51)       97(34/35)     97(89/92)     97(30/31)     wordcount.2
        420    100(51)       97(34/35)     98(90/92)     97(30/31)     wordcount.13
        480    100(51)       97(34/35)     99(91/92)     97(30/31)     wordcount.15
        550    100(51)       97(34/35)     100(92)       97(30/31)     wordcount.10
        630    100(51)       100(35)       100(92)       97(30/31)     wordcount.7
        780    100(51)       100(35)       100(92)       100(31)       wordcount.17
Figure 11-4 The minimal subset with the same block, decision and all-uses coverage as the original test set (includes cost)
From this summary it is easy to identify a subset of the tests that achieve a given level of coverage at reduced cost. For example, all tests together have cost 780. However, the first four tests in the minimal set achieve at least 90% block coverage at a total cost of 60, a fraction of the entire cost of the minimal set.

11.2.3 Minimizing by Coverage Criteria

With the -m{bcdepu} option, ATAC minimization can be limited to computing a minimal subset for a selected set of coverage measure(s). The argument to -m selects one or more coverage measures: e selects function-entry coverage, b block coverage, d decision coverage, c c-use coverage, p p-use coverage, and u all-uses coverage (see Section 3.3, What Does ATAC Do?, for an explanation of these measures). For example, the minimal subset generated for tests in Figure 11-1, as shown in Figure 11-5, is limited to block and decision coverage by entering: 
	prompt:> atac -Mq -mbd main.atac wc.atac wordcount.trace
In this case, test set size is reduced to from 17 to 6, which corresponds to a major size reduction. 

           % blocks      % decisions   test
           (cumulative)  (cumulative)  
           ------------- ------------- ------------- 
           75(38/51)     66(23/35)     wordcount.9
           86(44/51)     77(27/35)     wordcount.3
           94(48/51)     83(29/35)     wordcount.14
           98(50/51)     91(32/35)     wordcount.15
           100(51)       97(34/35)     wordcount.12
           100(51)       100(35)       wordcount.7
Figure 11-5 The minimal subset with respect to the block and decision coverage

11.2.4 Minimizing by File

ATAC minimization can compute a minimal test set for selected testable attributes found in the .atac files submitted on its argument list. For example, the minimal test set generated for tests in Figure 11-1 is limited to blocks, decisions and all-uses found in main.c by entering: 
	prompt:> atac -M main.atac wordcount.trace
The output of this appears in Figure 11-6. 

% blocks      % decisions   % C-Uses      % P-Uses      test

------------- ------------- ------------- ------------- ------------- 

66(25/38)     48(11/23)     42(31/74)     50(8/16)      wordcount.9

24(9/38)      17(4/23)      11(8/74)      25(4/16)      wordcount.4

37(14/38)     22(5/23)      12(9/74)      31(5/16)      wordcount.3

66(25/38)     48(11/23)     42(31/74)     50(8/16)      wordcount.8

58(22/38)     39(9/23)      46(34/74)     56(9/16)      wordcount.6

26(10/38)     22(5/23)      14(10/74)     12(2/16)      wordcount.14

76(29/38)     57(13/23)     47(35/74)     50(8/16)      wordcount.5

47(18/38)     39(9/23)      20(15/74)     38(6/16)      wordcount.11

47(18/38)     39(9/23)      20(15/74)     38(6/16)      wordcount.12

21(8/38)      17(4/23)      9(7/74)       12(2/16)      wordcount.2

37(14/38)     30(7/23)      19(14/74)     25(4/16)      wordcount.13

58(22/38)     39(9/23)      34(25/74)     56(9/16)      wordcount.15

47(18/38)     39(9/23)      20(15/74)     38(6/16)      wordcount.10

18(7/38)      17(4/23)      8(6/74)       12(2/16)      wordcount.7

100(38)       100(23)       100(74)       100(16)       == all ==
Figure 11-6 The minimal subset with respect to main.c

11.2.5 Minimizing by Function

With the -F option, ATAC minimization can be limited to computing a minimal test set for selected testable attributes found in a selected set of functions. For example, the minimal test set generated for tests in Figure 11-1 is limited to the functions main and count by entering: 
	prompt:> atac -M -F main -F count main.atac wc.atac wordcount.trace

11.2.6 Minimizing by Test Case

By default, ATAC minimization computes a minimal test set after reconciling all test case trace information recorded in a given .trace file against all .atac files submitted on the command line. You can compute a minimal test set with respect to selected test cases by using the -n option. A minimal test set is generated with respect to the block coverage of the first nine test cases of those in Figure 11-1 by entering: 
        prompt:> atac -MKq -mb -n "wordcount.?" main.atac wc.atac wordcount.trace
The output generated is in Figure 11-7. 

         cost   % blocks      test

         (cum)  (cumulative)  

         ------ ------------- ------------- 

         20     53(27/51)     wordcount.3

         30     65(33/51)     wordcount.4

         70     94(48/51)     wordcount.5

         120    100(51)       wordcount.2
Figure 11-7 The minimal subset with respect to wordcount.1 to wordcount.9
Notice that tests can be named by using wild card characters. These wild cards are the same as those used by the UNIX-like command processor in naming files (*, ?, [...]). In some cases, quotation marks may be needed to prevent the command processor from expanding the test names as file names. Also, multiple instances of the -n argument may be submitted on a single command line. Sometimes it is necessary to select all tests other than those that have been named. The -x option is used to select the complement of all tests specified using one or more instances of the -n option. For example, entering: 
        prompt> atac -MKq -mb -x -n "wordcount.?" main.atac wc.atac wordcount.trace
computes a minimal test set with respect to block coverage for all tests in Figure 11-1 except the first nine. The generated summary report is displayed in Figure 11-8. 

              cost   % blocks      test
              (cum)  (cumulative)  
              ------ ------------- ------------- 
              20     53(27/51)     wordcount.16
              70     86(44/51)     wordcount.11
              110    94(48/51)     wordcount.14
              160    98(50/51)     wordcount.13
              210    100(51)       wordcount.12
Figure 11-8 The minimal subset with respect to all tests except wordcount.1 to wordcount.9

11.3 Test set prioritization via a character-based user interface

In this section we explain how test set prioritization is performed via a character-based user interface. To begin, we assume the same main.atac, wc.atac and wordcount.trace as those in Section 11.2 are used. You can then print out the cumulative cost and coverage of each test in increasing order per additional coverage by entering: 
	prompt:> atac -Q main.atac wc.atac wordcount.trace
The corresponding output is in Figure 11-9. Test wordcount.9 is selected as the first test because it gives the maximum coverage with respect to block, decision, c-use and p-use per unit cost. Subsequent tests are selected based on their additional coverage with respect to these four criteria per unit cost. In our case, wordcount.16 is selected after wordcount.9 because it gives the maximal additional block, decision, c-use and p-use coverage per unit cost. 

cost   % blocks      % decisions   % C-Uses      % P-Uses      test

(cum)  (cumulative)  (cumulative)  (cumulative)  (cumulative)  

------ ------------- ------------- ------------- ------------- ------------- 

10     75(38/51)     66(23/35)     49(45/92)     71(22/31)     wordcount.9

30     80(41/51)     74(26/35)     66(61/92)     81(25/31)     wordcount.16

40     84(43/51)     77(27/35)     68(63/92)     84(26/31)     wordcount.4

60     90(46/51)     83(29/35)     72(66/92)     90(28/31)     wordcount.3

80     92(47/51)     89(31/35)     76(70/92)     94(29/31)     wordcount.8

140    92(47/51)     91(32/35)     85(78/92)     97(30/31)     wordcount.6

180    98(50/51)     94(33/35)     87(80/92)     97(30/31)     wordcount.14

220    100(51)       97(34/35)     90(83/92)     97(30/31)     wordcount.5

270    100(51)       97(34/35)     93(86/92)     97(30/31)     wordcount.11

320    100(51)       97(34/35)     96(88/92)     97(30/31)     wordcount.12

370    100(51)       97(34/35)     97(89/92)     97(30/31)     wordcount.2

420    100(51)       97(34/35)     98(90/92)     97(30/31)     wordcount.13

480    100(51)       97(34/35)     99(91/92)     97(30/31)     wordcount.15

550    100(51)       97(34/35)     100(92)       97(30/31)     wordcount.10

630    100(51)       100(35)       100(92)       97(30/31)     wordcount.7

780    100(51)       100(35)       100(92)       100(31)       wordcount.17

900    100(51)       100(35)       100(92)       100(31)       wordcount.1
Figure 11-9 Prioritized tests based on block, decision and all-uses
With the prioritized test list available, we can decide where the cut-off should be. For example, suppose you want to select a subset of all the tests shown in Figure 11-9 with maximal possible coverage and a total cost less than 220 for your regression testing. Your subset should contain tests {9, 16, 4, 3, 8, 6, 14, 5}. On the other hand, if your subset has to achieve the same block coverage as the original set (100% in this case) and its cost should be the least, then run the following command: 
	prompt:> atac -MKq -mb main.atac wc.atac wordcount.trace
to get the minimal set with respect to the block coverage1. The output generated is shown in Figure 11-10. 

    cost   % blocks      test
    (cum)  (cumulative)  
    ------ ------------- ------------- 
    20     53(27/51)     wordcount.3
    30     65(33/51)     wordcount.4
    70     94(48/51)     wordcount.5
    110    100(51)       wordcount.14
Figure 11-10 A minimized subset with 100% block coverage

11.4 Test set minimization and prioritization via a graphical user interface

We now repeat test set minimization and prioritization via a graphical user interface using the same main.atac, wc.atac and wordcount.trace files as those in Section 11.2. Since the current version of the Toolsuite's graphical interface does not support all the features discussed in Section 11.2 and Section 11.3, we will only illustrate those that are supported. Invoke the graphical interface of the Toolsuite by typing: 
	prompt:> xsuds main.atac wc.atac wordcount.trace
Then, pull down the ``Tool'' menu and select the ``xregress'' option. Click on the ``TestCases'' button in the top button bar to see the cumulative coverage by test case with respect to the selected coverage criteria. By default, five criteria -- function-entry, block, decision, c-use and p-use -- are selected. The resulting window appears in Figure 11-11 with tests listed in the order of decreasing added coverage per unit cost.

Figure 11-11 Test cases window of Regress in greedy_order with all five coverage criterion selected
Click with the left mouse button on ``function_entry'', ``decision'', ``c_use'' and ``p_use'' in the middle button bar to deselect these criteria. This makes block coverage the only selected criterion and updates the test case window accordingly, as shown in Figure 11-12. A shortcut for this is to click on ``block'' with the right mouse button which will deselect every criterion except block.

Figure 11-12 The updated test case window in greedy_order with only the block coverage criterion selected

By default, Regress is in greedy_order which sorts test cases in order of increasing cost per additional coverage. You can switch to optimal_order to do the test set minimization by clicking on the ``Minimize_in'' button in the middle button bar and selecting ``optimal_order''. The updated test cases window is displayed in Figure 11-13. The Test cases frame at the lower-right corner shows ``4 of 17'' indicating that only the first four tests (wordcount.3, wordcount.4, wordcount.5 and wordcount.14) are included in the minimized subset with the same block coverage as the original test set. The same output can be obtained via the character-based interface by entering the following on the command line: 

	prompt:> atac -M -mb main.atac wc.atac wordcount.trace

Figure 11-13 The updated test case window in optimal_order with only the block coverage criterion selected
The only difference is that the character-based command only returns tests in the minimized set and ignores others, whereas the test case window in Regress lists all tests including those not in the minimized set.

To quit Regress click on the ``File'' button in the top button bar and select ``exit''.


1 The option -K can be omitted if you don't want to include cost as part of the output.


[Top] [Prev] [Next] [Index] [TOC]