CSCI426/CSCI926 Software Testing and Analysis Lab – Week 5
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSCI426/CSCI926 Software Testing and Analysis
Lab – Week 5
Function cgi_decode translates a cgi-encoded string to a plain ASCII string, reversing the encoding applied by the common gateway interface (CGI) of most Web servers. CGI translates spaces to ‘+’, and translates most other non-alphanumeric characters to hexadecimal escape sequences. To reverse the translation, cgi_decode maps ‘+’ to ‘ ’, “%xy” (where x and y are hexadecimal digits) to the corresponding ASCII character, and other alphanumeric characters to themselves.
The code for cgi_decode is presented below. Draw the control flow graph (c.f. pp 8-10 in Lecture 4 slides).
1 #include "hex values .h"
2 /**
3 * @title cgi decode
4 * @desc
5 * Translate a string from the CGI encoding to plain ascii text
6 * ’+’becomes space, %xx becomes byte with hex value xx,
7 * other alphanumeric characters map to themselves
8 *
9 * returns 0 for success, positive for erroneous input
10 * 1 = bad hexadecimal digit
11 */
12 int cgi decode(char *encoded, char *decoded) {
13 char *eptr = encoded;
14 char *dptr = decoded;
15 int ok=0;
16 while (*eptr) {
17 char c;
18 c = *eptr;
19 /* Case 1: ’+’maps to blank */
20 if (c == ’+’) { 21 *dptr = ’ ’;
22 } else if (c == ’%’) {
23 /* Case 2: ’%xx’is hex for character xx */
24 int digit high = Hex Values[*(++eptr)];
25 int digit low = Hex Values[*(++eptr)];
26 /* Hex Values maps illegal digits to - 1 */
27 if ( digit high == -1 || digit low == -1 ) {
28 /* *dptr=’?’; */
29 ok=1; /* Bad return code */ 30 } else {
31 *dptr = 16* digit high + digit low;
32 }
33 /* Case 3: All other characters map to themselves */
34 } else {
35 *dptr = *eptr;
36 }
37 ++dptr;
38 ++eptr;
39 }
40 *dptr = ’/0’; /* Null terminator for string */
41 return ok;
42 }
Control flow graph for the cgi_decoder:
Lab – Week 6
Review Slides 3 – 8 and complete the following three questions.
Consider the following program. Some codes are associated with letters A – H.
1. Draw the control flow graph (CFG) for the program by using A – H as nodes.
2. Annotate each node with the definition and use of variables.
3. Draw a (direct) data dependence graph for the program. (Note the label is a def-use (du) pair.)
Q1 and Q2 solutions:
Q3 solution:
Lab – Week 7
Consider the symbolic execution of the following program1 :
1 . void foobar(int a, int b) {
2 . int x = 1, y = 0;
3 . if (a != 0) {
4 . y = 3+x;
5 . if (b == 0)
6 . x = 2*(a+b);
7 . }
8 . assert(x - y != 0);
9 . }
(1) The following table include some symbolic execution paths. C and D are symbolic (int) values of variables a and b. In the example of Path 1, a new constraint (in red) is added to the previous constraint at each execution step. Complete the constraints for Path 2 – Path 4.
(2) A path is feasible if and only if you can find concrete values of the variables to make the last constraint true. If those concrete values do not exist, a path is infeasible. Check the feasibility of the given four paths.
(3) Find out all other paths and the corresponding constraints.
Sample solution:
Lab – Week 9
1. Review the concepts of safety and liveness properties (pp. 7 in lecture slides, and pp. 125 in textbook). Answer the following question: A property like “if the button is pressed, then eventually the elevator will come” is classified as a liveness property. However, the stronger real-time version “if the button is pressed, then the elevator will arrive within 30 seconds” is technically a safety property rather than a liveness property. Why?
2. Dinning philosophers1 .
This example, originated by Dijkstra, is one of the most prominent examples in the field of concurrent systems.
Five philosophers are sitting at a round table with a bowl of rice in the middle. For the philosophers (being a little unworldly) life consists of thinking and eating (and waiting). To take some rice out of the bowl, a philosopher needs two chopsticks. In between two neighbouring philosophers, however, there is only a single chopstick. Thus, at any time only one of two neighbouring philosophers can eat. Of course, the use of the chopsticks is exclusive and eating with hands is forbidden.
Note that a deadlock scenario occurs when all philosophers possess a single chopstick. The problem is to design a protocol for the philosophers, such that the complete system is deadlock-free, i.e., at least one philosopher can eat and think infinitely often. Additionally, a fair solution may be required with each philosopher being able to think and eat infinitely often. The latter characteristic is called freedom of individual starvation.
The following obvious design cannot ensure deadlock freedom. Assume the philosophers and the chopsticks are numbered from 0 to 4. Furthermore, assume all following calculations be “modulo 5”, e.g., sticki-1 for i=0 denotes chopstick 4, and so on.
Philosopheri has sticki on his left and sticki-1 on his right side. The action requesti,i express that sticki is picked up by philosopheri . Accordingly, requesti-1,i denotes the action by means of which philosopheri picks up the (i−1)th stick. The actions releasei,i and releasei-1,i have a corresponding meaning.
The behaviour of philosopheri (called process Phili) is specified by the transition system depicted in the left part of the following figure. Solid arrows depict the synchronizations with the i-th stick, dashed arrows refer to communications with the (i−1)-th stick. The sticks are modelled as independent processes (called Sticki) with which the philosophers synchronize via actions request and release; see the right part of the following figure that represents the process of sticki . A stick process prevents philosopheri from picking up the i-th stick when philosopheri+1 is using it.2
Understand why (and how) a deadlock and starvation can happen. Propose a solution to this problem.
Sample solutions.
1. A safety property asserts that “nothing bad happens,” while a liveness property asserts that “something good eventually happens.” The real-time property (“within 30 seconds”) creates a “bad” thing that can happen, in this case passage of 30 seconds before arrival of the elevator.
2. A possible solution to this problem is to make the sticks available for only one philosopher at a time. The corresponding chopstick process is depicted in the right part of the following figure. In state availablei,j only philosopherj is allowed to pick up the i-th stick. The above-mentioned deadlock situation can be avoided by making that some sticks (e.g., the first, the third, and the fifth stick) start in state availablei,i , while the remaining sticks start in state availablei,i+1 . It can be verified that this solution is deadlock- and starvation-free.
Transition coverage subsumes state coverage, under the (reasonable) assumption that all FSM states are reachable.
Path coverage subsumes transition coverage, under the slightly stronger (but still reasonable) assumption that all states are reachable on paths from the distinguished start state. (A model that violates this assumption is not very useful.)
Path coverage also subsumes state-pair coverage: At least one of the sub-paths from r to s must be covered. However, state-pair coverage does not subsume transition coverage, nor vice versa, as illustrated by the following simple example.
For this FSM, each of the labeled states is reachable from all other labeled states, so there are 32 = 9 state pairs, including pairs like hr, ri and hs, si. All of these state pairs can be covered with one looping path, so we can satisfy the state-pairs criterion with a test suite containing just one test case:
{ht 1, t3, t4, t 1, t3i}
This test suite does not satisfy the transition coverage criterion, since transition t2 is not covered. Therefore state-pair coverage does not subsume transition coverage.
On the other hand, we can satisfy the transition coverage criterion with the follow- ing test suite containing just two test cases:
{ht2, t4, t2i, ht 1, t3i}
This second test suite does not cover several of the state-pairs, such as hs,xi, hx,xi, and hx, ri. Therefore transition coverage does not subsume state-pair coverage.
We conclude that the subsumes hierarchy, for these criteria, is
Lab – Week 9
Deterministic finite state machines (FSMs), with states representing classes of program states and transitions representing external inputs and observable program actions or outputs, are sometimes used in modeling system requirements. We can design test cases consisting of sequences of program inputs that trigger FSM transitions and the predicted program actions expected in response. We can also define test coverage criteria relative to such a model. Which of the following coverage criteria subsume which others?
• State coverage: For each state in the FSM model, there is a test case that visits that state.
• Transition coverage: For each transition in the FSM model, there is a test case that traverses that transition.
• Path coverage: For all finite-length subpaths from a distinguished start state in the FSM model, there is at least one test case that includes a corresponding subpath.
• State-pair coverage: For each state r in the FSM model, for each state s reachable from r along some sequence of transitions, there is at least one test case that passes through state r and then reaches state s.
You can use the following example to guide you to answer the above question.
Lab – Week 10
Task 1:
When designing a test suite with the category par33on method, some3mes it is useful to determine the number of test case specifica3ons that would be generated from a set of parameter characteris3cs (categories) and value classes (choices) without actually genera3ng or enumera3ng them.
Describe how to quickly determine the number of test cases in these cases:
(a) Parameter characteristics and value classes are given, but no constraints (error, single, property, or if-property) are used.
(b) Only the constraints error and single are used (without property and if property).
Task 2:
Suppose we are construc3ng a tool for combinatorial tes3ng. Our tool will read a specifica3on in exactly the same form as the input of a tool for the category par33on method, except that it will achieve pairwise coverage rather than exhaus3ve coverage of values. However, we no3ce that it is some3mes not possible to cover all pairs of choices.
For example, we might encounter the following specifica3on:
C1
V1 [ property P1 ]
V2 [ property P2 ]
C2
V3 [ property P3 ]
V4 [ property P4 ]
C3
V5 [ if P1 ]
V6 [ if P4 ]
Our tool prints a warning that it is unable to create any complete test case specifica3on that pairs value V2 with V3.
a) Explain why the values V2 and V3 cannot be paired in a test case specification.
b) Suppose the parameter characteristic C3 were instead described as follows:
C3
V5 [ if P1 ]
V6 [ if P4 ]
V7 [ error ]
Would it be sa3sfactory to cover the test obliga3on
In general, should values marked error be used to cover pairs of parameter characteris3cs?
Sample solu+ons
Task 1.
(a) If parameter characteristics and value classes are given without constraints, the number of test case specifications is the product of the number of value classes in each category. For example, if the categories are A, B, and C, category A has 5 value classes, category B has 6, and category C has 3, then the number of test cases is 5 ⇥ 3 ⇥ 6.
(b) If only error and single clauses are used, we just treat value classes with those constraints separately from unconstrained value classes. The number of test case specifications is the sum of the error and single classes, plus the product of the numbers of unconstrained value classes in each category. For example, if again the categories are A, B, and C, and A has 5 values classes, 1 of which is an error class, B has 6, 1 of which is an error class and 1 of which is a single class, and C has 3 classes, all unconstrained, then the number of test case specifications is ( 1 + 2 + 0)+(5− 1)⇥ (6− 2) ⇥ 3.
Task 2.
(a) The value V5 is not possible because it conflicts with V2. The value V6 is not possible because it conflicts with V3. After eliminating incompatible choices from category C3, there are no choices available.
(b) We should not treat erroneous values as candidates for completing a normal test case specification. The point of testing each pairing of normal values is to check for interactions between particularly pairs, and errror handling is likely to mask any such interaction.
Sample solutions
Task 1.
The following test cases are created:
int[] sample1 = {1, 2, 3, 4, 5, 6};
int[] sample2 = new int[] {}; // initialise an empty array with size 0
int[] sample3 = {-1, 0};
int[] sample4 = {-1, 0 ,1};
int[] sampel5 = {1};
A test suite meeting the statement adequacy includes: sample1, sample3 (or sample4)
A test suite meeting the loop boundary adequacy includes: sample2, sample3 (or sample4), sample5 A test suite meeting the branch coverage criterion includes: sample1, sample3 (or sample4)
Task 2.
Acceptable answers can vary. A good answer should describe parameter char- acteristics, not concrete values. Note, for example, that in our sample solution, times of the outbound departure are classified by their relation to the inbound arrival, rather than being selected from a set of concrete times. The distinction between parameter values and parameter characteristics may be slight when parameters are orthogonal or nearly so, but becomes important when the specification describes relations among parameters.
Parameter: Arriving flight
Arriving flight code
malformed [error]
not in database [error]
valid
Originating airport code
malformed [error]
not in database [error]
foreign city (relative to transfer airport)
domestic city (relative to transfer airport)
Scheduled departure time
syntactically malformed [error]
out of legal range [error]
legal
Destination airport (transfer airport)
malformed [error]
not in database [error]
valid city
Note: we are using the destination aiport of the first flight as a base for calling other airports “domestic” or “foreign,” so we don’t classify the destination airport itself except as to being domestic orforeign.
Scheduled arrival time (t0)
syntactically malformed [error]
out of legal range [error]
legal
Parameter: Departing flight
Departing flight code
malformed [error]
not in database [error]
valid
Originating airport code
malformed [error]
not in database [error]
differs from transfer airport [error]
same as transfer airport
Scheduled departure time
syntactically malformed [error]
out of legal range [error]
before arriving flight time (t0)
between t0 and t0 + DCT [if ICT-greater]
between DCT and t0 + ICT [if ICT-greater]
more than t0 + max(ICT,DCT)
equal to t0 + DCT
equal to t0 + ICT
Destination airport code
malformed [error]
not in database [error]
foreign city (relative to transfer airport)
domestic city (relative to transfer airport)
Here “foreign” means the two cities (transfer airport and destination airport) have unequal zones, and “domestic” means they have the same zone.
Scheduled arrival time
syntactically malformed [error]
out of legal range [error]
legal
Parameter: Airport connect time record
This parameter refers to the domestic and international connect time record corresponding to the transfer airport.
Domestic connect time (DCT)
not found [error]
invalid [error]
valid
International connect time (ICT)
not found [error]
invalid [error]
- 1 (not permitted)
less than domestic [single]
same as domestic
greater than domestic [property ICT-greater]
Lab – Week 11
Task 1:
Design a minimal set of test cases for the following program. Your test suite must meet the statement adequacy criterion, loop boundary adequacy criterion and branch coverage criterion.
1. public int max_absolute(int[] numbers){
2. if(numbers. length > 5)
3. return -1;
4. int max_value = 0;
5. for(int i = 0; i
6. if (numbers[i] < 0 )
7. max_value = Math.max(max_value,Math.abs(numbers[i]));
8. else max_value = Math.max(max_value, numbers[i]);
9. }
10. return max_value;
11. }
Task 2:
Derive parameter characteristics, representative values, and semantic constraints from the following specification of an Airport connection check function, suitable for generating a set of test case specifications using the category partition method.
• Airport connection check: The airport connection check is part of an (imaginary) travel reservation system. It is intended to check the validity of a single connection between two flights in an itinerary. It is described here at a fairly abstract level, as it might be described in a preliminary design before concrete interfaces have been worked out.
• Specification Signature: Valid Connection (Arriving Flight: flight, Departing Flight: flight) returns Validity Code
o Validity Code 0 (OK) is returned if Arriving Flight and Departing Flight make a valid connection (the arriving airport of the first is the departing airport of the second) and there is sufficient time between arrival and departure according to the information in the airport database described below.
o Otherwise, a validity code other than 0 is returned, indicating why the connection is not valid.
Data types
Flight: A ”flight” is a structure consisting of
• A unique identifying flight code, three alphabetic characters followed
by up to four digits. (The flight code is not used by the valid
connection function.)
• The originating airport code (3 characters, alphabetic)
• The scheduled departure time of the flight (in universal time)
• The destination airport code (3 characters, alphabetic)
• The scheduled arrival time at the destination airport.
Validity Code: The validity code is one of a set of integer values with
the following interpretations:
0: The connection is valid.
10: Invalid airport code (airport code not found in database)
15: Invalid connection, too short: There is insufficient time between arrival of first flight and departure of second flight.
16: Invalid connection, flights do not connect. The destination airport of Arriving Flight is not the same as the originating airport of Departing Flight. 20: Another error has been recognized (e.g., the input arguments may be invalid, or an unanticipated error was encountered).
Airport Database
The Valid Connection function uses an internal, in-memory table of airports which is read from a configuration file at system initialization. Each record in the table contains the following information:
• Three-letter airport code. This is the key of the table and can be used for lookups.
• Airport zone. In most cases the airport zone is a two-letter country code, e.g., ”us” for the United States. However, where passage from one country to another is possible without a passport, the airport zone represents the complete zone in which passport-free travel is allowed. For example, the code ”eu” represents the European countries
2023-07-18