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).

 

3. 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.
4. You may implement the program in your choice of programming language.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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

 

3. 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

 

4. 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.

Here are your directions:

Write a SHORT intro with no more than three sentences with one sentence being your thesis. A thesis is “a specific point that you are trying to establish – something that you are trying to convince the reader to accept”. The thesis is your conclusion, and your entire argument will be to defend the thesis. The entire point of the intro paragraph in a philosophical paper is simply to present your thesis. You honestly want as short of an intro as possible since it the meat and potatoes of the paper are in the argument. For this paper, you have two options, Utilitarianism is true or it’s not. You’ll need to pick one. Do not fence-sit. However, your thesis statement also needs to state the fundamental reason(s) that make(s) you correct. For example, if I want to argue that cereal is a better breakfast food than eggs, I can’t just blankly state that. I need to say, “Cereal is a better breakfast food than eggs because cereal is faster to prepare and I’m a horrible cook.” In that thesis, the entire paper is already given away. It gives two reasons, and that will be my argument. That’s what you want. A good thesis awards 20 points. Do not “fence-sit”. And for the record, eggs are great.

Since your thesis will be on Utilitarianism, you will need to immediately define your terms. This is absolutely the most fundamental problem in most arguments: no one knows what people are really talking about. In my cereal vs eggs example, I actually imply that cereal is not “cooked” even though they are both “prepared”. Little things like that matter A LOT when we talk about more important topics. You will describe Utilitarianism as argued by Bentham and Mill in order to best define Utilitarianism. Try to describe the differences between the two, but what is most important is what they have in common. Include examples. Good description/definition of your important terms awards 40 points.

Now that Utilitarianism has been well defined, you can argue. You will be evaluating those claims within Utilitarianism, and supporting whatever reasons you’ve given for your claim. Support can be all sorts of things, but in general, the supports should be more obviously true to help walk the reader to the truth of your thesis. Do not use a shotgun approach to argument, where you take a thousand little reasons and hope they are strongest. The simple argument is the strongest, and you should build up to your conclusion from a strong foundation. In my cereal vs eggs example, I would need to cite that cooking eggs is actually longer, I would need to tell you why time is so important (maybe because we’re all rushing to start our day), I would need to say why my poor cooking skills matter, etc. Good argumentative form awards 20 points.

The next step is done for both integrity and logic. You’ll need to respond to objections and offer concessions. In my cereal vs. eggs example, I would need to expect a reader to think “What if I have lots of time? What if it’s a Saturday? Why does your bad cooking mean I shouldn’t cook eggs for me?”. At the end of a good philosophical paper, these kinds of things are addressed. Sometimes, this is actually the longest section. Mill’s “Utilitarianism” is almost entirely objections and concessions. Concessions are valuable because, if you identify the limits of your logic, it helps people understand your claim. Moreso, it might help you realize that you need to beef up your reasons or change your claim entirely. Specifically, in this section, I want you to focus on objections. Say why someone might disagree with you, and why their reason is mistaken. This means you have to anticipate a point of disagreement and address it immediately. This strengthens your reasons for your position. In a full book, you would address any and all possible objections, but I really only need you to pick one or two that you think are most common. Good objection anticipation awards 20 points.

If you would like, you may have a concluding paragraph to summarize everything, but honestly, philosophical papers don’t always need these. Philosophy is not an English class, a History class, or a poetry class. Do whatever makes you feel comfortable; the important parts are the thesis, the definitions, the arguments, and the objections.

 

MAKE SURE YOU FOLLOW INSTRUCTIONS AND COVER ALL 4 STEPS.

Don’t plagiarize. Don’t even get close. Put quotes on anything that needs quotes. Plagiarizing on the draft counts just as much as anything else.

You need to write 2.5 pages for the draft, you’ll need a full 4 for the final. Do not fence-sit.