Black box test cases for insertion procedure

Question

insertion_procedure (int a[], int p [], int N)
{
    int i,j,k;
    for (i=0; i<=N; i++) p[i] = i;
    for (i=2; i<=N; i++)
    {
        k = p[i];
        j = 1;
        while (a[p[j-1]] > a[k]) {p[j] = p[j-1]; j--}
        p[j] = k;
    }
}

What would be few good test cases for this particular insertion procedure?

Answer 1

If I read this function correctly any input with this property a[0] > a[2] will seg fault

First loop through for (i=2; i<=N; i++)

Tracing the variables in my head.

1. i = 2
2. k = p[i] == 2
3. j = 1
4. p[j-1] = p[0] == 0
5. Because a[0] > a[2] while loop condition is true, therefore j-- == 0
6. Next evaulation of while condition will do: while (a[p[-1] > k) -> SEGFAULT

That might be a good test :-)

It doesn't look like there is any useful input that would make that while loop run more than once without a segfault so I'd say there is a logic error there

Answer 2

I would start with these

• a negative number in a[]. What should the result be?
• a negative number in p[].
• a negative number N.
• an empty a array.
• an empty p array.
• N = 0

Looking at the implementation (I don't programm in c), I suspect some of these will AV.

In a nutshell, you should at least do a boundary analysis of your input parameters and device a test for each parameter with each value out of bound, on the boundary and inbound.

Example
If you have 1 parameter and determine the bounds are 0 and 10, it should result in 6 testcases. You should pass in -1, 0, 1, 9, 10 and 11.

Further study
As the ammount of parameters grows, it will quickly become impossible to test all combinations. This is where all-pairs testing would come in handy.