Management homework help

/in /by

 

Implementation of the AETG algorithm that generates combinatorial test suites.

 

AETG is a commercial tool that generates combinatorial test suites.  Essentially, the AETG algorithm constructs a covering array, or mixed level covering array that is used to represent the test suite. A covering array,, is an N x k array.  In every N x t subarray, each t-tuple occurs at least λ times. In our application, t is the strength of the coverage of interactions, k is the number of factors, and v is the number of  levels. A mixed level covering array, , is an N x k array. Let , and consider the subarray of size N x t obtained by selecting columns of the MCA. There are   distinct t-tuples that could appear as rows, and an MCA requires that each appear at least once. This variant of the covering array provides the flexibility to represent test suites for systems in which components are not restricted to having the exact same number of parameters.  (In the application to combinatorial testing, we treat only the case when λ = 1.)

 

This literature on AETG will help you to implement the algorithm:

 

  • M. Cohen, S. R. Dalal, M. L. Fredman, and G. C. Patton. The AETG system: an approach to testing based on combinatorial design. IEEE Transactions on Software Engineering (1997), 23(7):437-44.
  • M. Cohen, S. R. Dalal, M. L. Fredman, and G. C. Patton. Method and system for automatically generating efficient test cases for systems having interacting elements United States Patent, Number 5,542,043, 1996.
  • M. Cohen, S. R. Dalal, J. Parelius, and G. C. Patton. The combinatorial design approach to automatic test generation. IEEE Software (1996), 13(5):83-8.

 

 

Additional notes:

  1. The AETG algorithm will generate test suites for any strength. In this assignment, you are only required to implement the algorithm for 2-way coverage.
  2. For this assignment, you are not required to take strings as input. You may simply give every factor and every level a unique numerical identifier. For instance, the input in Table 1 may be represented as shown in Table 2:

 

Hardware Operating System Network

Connection

 Memory

 
PC Windows XP Dial-up 64MB
Laptop Linux DSL 128MB
PDA Solaris Cable 256MB

Table 1 – A component based system with four factors that each have three levels

 

0 3 6 9
1 4 7 10
2 5 8 11

Table 2 – A component based system with four factors that each have three levels. (Factor  has levels 0, 1, 2; factor   has levels 3, 4, 5; factor  has levels 6, 7, 8; factor  has levels 9, 10, 11).

 

  1. You should provide sample input files with a description of the format of the files or prompt the user for the number of factors and levels so that the grader can easily grade your program.
  2. You may implement the program in your choice of programming language.
  3. Your program may end up using too much time or memory for larger inputs, so you will need to be careful in your implementation. The papers do not describe the exact implementation details for the exact data structures that they use. It is expected that you can effectively make decisions that lead to a fast and efficient implementation.
  4. Since there is randomization in your algorithm, you will run your program 100 times for each input and report the average size and execution time for each input. You should also use 50 candidates as done in the AETG literature.
  5. You will report the results of your algorithm for several inputs for which AETG has published results. Of course, it is possible that your results will slightly vary from their reported results since there is randomization in the algorithm. However, if your results are off by more than 20% for any inputs larger than 3^4, you have a bug in your program.
  6. You should strive to implement an efficient solution. To receive credit for this assignment, your algorithm cannot run for longer than 10 minutes to find a solution.
  7. You are only required to implement a solution for up to 2-way coverage. However, if you implement a solution for n-way coverage and report results for up to 5-way coverage, you will receive a certificate for 100% credit on the pop quiz of your choice.

 

 

Submission

 

Part 1 – Implementation and results (95%)

  1. Code – You should provide your code and if applicable, your makefile. Please zip the files before e-mailing them to our course e-mail address. If there is an “exe” in your email, gmail will not allow the email to come through, so don’t do this!
  2. Submit a Document with your Results – your results should be close to those published in the AETG literature. You should provide output files for each input such that each output file contains the best covering array generated for that input. You will lose 20% credit if you do not submit your output files. You will also complete the following table with the results from your program:

 

Input Your best result Your average result Your worst result Average execution time mAETG
200
17
8
42
9
95

 

  1. Submit output files using this format – The TA will use a program to confirm that all pairs are covered in your solution. You must use this format for your output.

9

 

1 4 7 9

1 5 8 11

2 4 8 10

2 3 7 11

0 5 7 10

2 5 6 9

1 3 6 10

0 4 6 11

0 3 8 9

 

Here is a commented version of the output format, but please do not include comments in your output files. This is for instructional use only:

 

9  // There are 9 tests in my solution

 

1 4 7 9     // This is test case 1 (i.e., one level for each factor is assigned)

1 5 8 11   // This is test case 2

2 4 8 10

2 3 7 11

0 5 7 10

2 5 6 9

1 3 6 10

0 4 6 11

0 3 8 9

 

  1. Grading of code – No credit will be given for code that does not compile or if the size of the solutions are not within 20% of the results reported in the AETG literature (with exception to input 3^4). No credit will be given to code that takes longer than 10 minutes to run on any of the above inputs. Your code must be object-oriented and use well named methods and variables. There will be a 10% penalty if the code is not commented. You can receive 50% credit if you program fully works only for covering arrays, but not mixed-level covering arrays.

 

 

Part 2 – Written question (5%)

The AETG algorithm does not actually have a logarithmic guarantee on the size of the test suites. Explain why.

 

Extra credit

  1. If you implement the algorithm for 3-way coverage, you will receive 20% extra credit. (Code for the sample inputs above must run in <3 minutes.)
  2. If you implement the algorithm for n-way coverage, with results reported for 3-way, 4-way, and 5-way coverage, you will receive 30% extra credit. (Code for the sample inputs above must run in <5 minutes.)
  3. TA’s will select one assignment as their favorite to receive 30% extra credit. They will consider the design, documentation, and speed of the code.