Skip to main content

Section D.8 Exercise Sheet 8

1. Assertions.

Write assertions inside the gap marked by ... such that the function supersum always terminates.

int supersum(int a, int b, int c) {
    assert(c >= 0);

    ...

    int x = 0;
    for (int i = a; x < b; i = i + c) {
        x = x + i;
    }
    return x;
}

202207281550

202206031400
Solution.

int supersum(int a, int b, int c) {
    assert(c >= 0);

    assert(
        // the program terminates without entering the loop
        (b <= 0) ||

        // the loop stops after the first iteration 
        (a >= b) ||  

        // i will be positive eventually and therefore x will eventually be greater than b
        (c > 0)  ||

        // x will be increased by the positive value a in every iteration 
        (c == 0 && a > 0)
    );

    int x = 0;
    for (int i = a; x < b; i = i + c) {
        x = x + i;
    }
    return x;
}
Tip: To get detailed error messages, it makes sense to split a conjunctive assertion into multiple assertions. For example, it makes sense to write assert(x>=0); assert(y>=0); instead of assert(x>=0 && y>=0);.

2. Mixed Bag: Tests.

  1. Which bugs can be found with black-box and white-box testing respectively?

  2. Is the coverage of program branches and statements a good measure for black-box tests? Why?

  3. What is the difference between statement coverage, branch coverage and path coverage in a C program? Can you achieve full branch coverage without covering all statements?

  4. Can you specify a program for which none of the coverage variants can be achieved?

202207281550

202206031400
Solution.
  1. Function-based testing (black-box testing) tests for correctness of the specification, i.e. if the program as a whole returns the expected output for a given input. It does not assume any knowledge about the implementation. Here, missing functionality can be found, which is not the case for white-box testing. White-box tests also test individual parts of the program to achieve a coverage of the program code that is as high as possible. Errors are often found in internal methods, where they are difficult to find with black-box testing.

  2. No, since the coverage of the code is not prioritized, but the consistency of the program behaviour with the specification. In black-box testing, knowledge about the implementation details and internal methods is missing, high coverage does not correlate with the precision of the black-box tests.

    An example:

    void f(int x) {
        if (x < 0)
            error();
        else
            ok();
    }
    
    If f is called only at one specific point in the program, e.g. with value \(4\text{,}\) then no black-box test can cover the then-branch, and would therefore have low coverage in this function although the specification could be covered well.

  3. For full statement coverage, every statement in the program must be executed at least once. For full branch coverage, every branch must be taken at least once. Full path coverage does not only require that every branch and every statement must be executed, but also that every possible program path is followed, i.e. that all possible sequences of statements are executed. It is not possible to cover all branches without covering all statements. If one has taken all branches, then one also visited every statement.

  4. For programs containing dead code, full coverage cannot be achieved. Example:

    void f(int x) {
        if (false)
            x = 42;
        else
            x = 1;
        return;
    }
    

3. Coverage.

Take a look at the following program:

char* convert (int x){
    char* string = NULL;
    if (x == 1) {
        string = "ONE";
    }
    else if (x == 2) {
        string = "TWO";
    }
    return string;
}

  1. Write a test suite that covers all statements.

  2. Extend your test suite such that all branches are covered.

202207281550

202206031400
Solution.
  1. void test_one() {
        char* one = convert(1);
        assert(strcmp(one, "ONE") == 0);
    }
    
    void test_two() {
        char* two = convert(2);
        assert(strcmp(two, "TWO") == 0);
    }
    

  2. void test_three() {
        char* empty = convert(3);
        assert(empty == NULL);
    }
    

4. Coverage revisited.

Take a look at the following function:

void substr(char* dest, int begin, int end, char* data) {
    int delta = 0;
    if (end < 0) {
        delta = -end;
    }
  
    if (delta == 0) {
        if (begin <= end) {
            for (int i = begin; i < end; ++i) {
                dest[i - begin] = data[i];
            }
        }
        dest[end - begin] = '\0';
    } else {
        int i = begin;
        if (data[i + delta] != '\0') {
            for (; data[i + delta] != '\0'; ++i) {
                dest[i - begin] = data[i];
            }
        }
        dest[i - begin] = '\0';
    }
}

  1. Describe the function in one or two sentences.

  2. Write a test suite that covers all statements.

  3. Extend your test suite such that it covers all branches as well.

202207281550

202206031400
Solution.
  1. The program copies a substring from data to dest, starting at begin and ending at end. If the index is negative, it is interpreted relative to the end of the string.

  2. // end is negative
    void test_neg_end() {
      char data[16];
      char * input = "TestMessage!";
      substr(data, 4, -1, input);
      printf("%s\n", data);
      assert(!strcmp("Message", data));
    }
    
    // end is positive
    void test_pos_end() {
      char data[16];
      char * input = "TestMessage!";
      substr(data, 0, 4, input);
      printf("%s\n", data);
      assert(!strcmp("Test", data));
    }
    

  3. void test_branch_pos_end_noloop() {
      char data[16];
      char * input = "TestMessage!";
      substr(data, 5, 5, input);
      printf("%s\n", data);
      assert(!strcmp("", data));
    }
    
    void test_branch_neg_end_noloop() {
      char data[16];
      char * input = "TestMessage!";
      substr(data, 4, -8, input);
      printf("%s\n", data);
      assert(!strcmp("", data));
    }
    

5. Test Suite.

Take a look at the following C program:

int rec(int a, int b, int n) {
    if (n == 0) {
        return a + b;
    }
    if (b == 0) {
        if (n == 1) {
            return 0;
        } else if (n == 2) {
            return 1;
        } else {
            return a;
        }
    }
    return rec(a, rec(a, b - 1, n), n - 1);
}

  1. Shortly describe what the program does.

  2. Write a test suite for the program which covers all statements.

  3. Extend your test suite such that it covers all branches, if possible.

202207281550

202206031400
Solution.
  1. The function can be used to compute the ackerman function. The ackerman function is not primitively recursive, which has the consequence that you cannot compute it without using some form of indefinite iteration (e.g. while loops). Definite iteration (e.g. for loops) alone is not powerful enough.

  2. void test_n_zero() {
        int res = rec(2, 3, 0);
        assert(res == 5);
    }
    
    void test_b_zero_n_one() {
        int res = rec(2, 0, 1);
        assert(res == 0);
    }
    
    void test_b_zero_n_two() {
        int res = rec(2, 0, 2);
        assert(res == 1);
    }
    
    void test_b_zero_n_not_one_or_two() {
        int res = rec(2, 0, 3);
        assert(res == 2);
    }
    
    void test_one_step() {
        int res = rec(2, 1, 1);
        assert(res == 2);
    }
    

  3. Here, we cannot cover all statements without also covering all branches. We are therefore already done.

6. Functional Tests.

The test suite for the function roots given as an example in the Testing chapter of the lecture notes (Example 7.3.3) does not cover all cases. Write additional tests for the cases that are not covered yet.

202207281550

202206031400
Solution.
  • The polynomial is quadratic and has no rational roots.

    void test_quadratic_none(void) {
        double r[2];
        int res = roots(1, 0, 1, r);
        assert(res == 0);
    }
    

  • The polynomial is quadratic and has exactly one rational root.

    void test_quadratic_one(void) {
        double r[2];
        int res = roots(3, 0, 0, r);
        assert(res == 1 && r[0] == 0.0);
    }
    

  • The polynomial is quadratic and has exactly two rational roots.

    void test_quadratic_two(void) {
        double r[2];
        int res = roots(1, 0, -1, r);
        assert(res == 2);
        assert((r[0] == 1.0 && r[1] == -1.0)
            || (r[1] == 1.0 && r[0] == -1.0));
    }
    

7. Wrong Maximum.

The following function should return the index of the first occurrence of the maximum value of an array. For this purpose the function is given a pointer to an array of integers and the size of this array. If the array is empty, the function should return -1.

int maximum(int* array, int size) {
    int max = 0;
    int pos = -1;

    for(int i = 0; i < size - 1; i++) {
        if (array[i] >= max) {
            max = array[i];
            pos = i;
        }
    }

    return max;
}

  1. Write tests that detect all the errors in this function. Can you think of further mistakes that could be made? Write also tests to cover these.

  2. What needs to be changed about this function for it to work correctly?

202207281550

202206031400
Solution.
  1. Some possible tests for our implementation of the maximum function:
    // General test for function maximum
    void test_maxium_big_positive() {
        // Do you have any idea where the numbers come from? ;)
        int a[5] = {60221023, 9832, 19891033, 299792458, 27315};
    
        int pos = maximum(a, 5);
    
        assert(pos == 3);
    }
    
    // Tests the maximum function for negative numbers
    void test_maximum_negative() {
        int a[5] = {-42, -1, -31415, -12, -69};
    
        int pos = maximum(a, 5);
    
        assert(pos == 1);
    }
    
    // Tests whether the upper bound of the array gets taken into account
    void test_maximum_last_position() {
        int a[5] = {-5, -4, -3, -2, -1};
    
        int pos = maximum(a, 5);
    
        assert(pos == 4);
    }
    
    // Tests whether the lower bound of the array gets taken into account
    // (this is an additional test which covers a possible mistake)
    void test_maximum_first_position() {
        int a[5] = {-1, -2, -3, -4, -5};
    
        int pos = maximum(a, 5);
    
        assert(pos == 0);
    }
    
    // Test if occurence with lowest index gets picked
    void test_maximum_multiple_positions() {
        int a[4] = {1, 2, 1, 2};
    
        int pos = maximum(a, 4);
    
        assert(pos == 1);
    }
    
    // Tests if maximum function works on an "empty array"
    // (this is an additional test which covers a possible mistake)
    void test_maximum_empty_array() {
        int* a = (int*) null;
    
        int pos = maximum(a, 0);
    
        assert(pos == -1);
    }
    
  2. The corrected version of the function may looks like this:
    int maximum(int* array, int size) {
        assert(size >= 0);
        if (size == 0) {
            return -1;
        }
    
        int max = array[0];
        int pos = 0;
    
        for (int i = 0; i < size; i++) {
            if (array[i] > max) {
                max = array[i];
                pos = i;
            }
        }
    
        return pos;
    }