Branch testing with MS Copilot

Task 1 (student 1) 

 Using MS Copilot  identify branches for the insertSort function. Assign a tag to for each identified branch.  Present the list of statements with tags. Write the prompt and the chatbot answer. Discuss the result - compare it with the previous page of the book. 

Prompt for MS Copilot:

This is code for insert sort algorithm in C: void insertSort(int a[], int length) { int i, j, value; for (i = 1; i < length; ++i) { value = a[i]; for (j = i - 1; j >= 0 && a[j] > value; --j) { a[j + 1] = a[j]; } a[j + 1] = value; } }. Branch testing, identify branches for the insertSort function. Assign a tag to for each identified branch. Present the list of statements with tags

Answer from chatbot:

Branch testing involves identifying branches—conditional paths the code can take—within the function. In your insertSort function, we have the following branches:

Identified Branches:

1. Loop entry conditions (for both loops)

   • for (i = 1; i < length; ++i) { → Tag: B1 (Outer loop)

   • for (j = i - 1; j >= 0 && a[j] > value; --j) { → Tag: B2 (Inner loop)

2. Loop body execution

   • The body of the inner loop executes when the condition j >= 0 && a[j] > value is true → Tag: B3

   • The statement a[j + 1] = a[j]; occurs when the inner loop executes → Tag: B4

3. Loop exit conditions

   • a[j + 1] = value; after the inner loop terminates → Tag: B5

Summary of Statements with Tags:

This breakdown helps in designing test cases that ensure all branches are covered. If you'd like, I can help formulate some test cases to validate each path

 Task 2 (student 2) 

 Using MS Copilot generate the Control Flow Graph in the DOT language for the insertSort function. Label the edges of the CFG. Discuss the result - compare the CFG with the graph created by a human. 

Prompt for MS Copilot:

can you generate the CFG graph in dot for this function insertSort(int a[], int length) { int i, j, value; for (i = 1; i < length; ++i) { value = a[i]; for (j = i - 1; j >= 0 && a[j] > value; --j) { a[j + 1] = a[j]; } a[j + 1] = value; } }

MS Copilot code for the CFG in DOT language

digraph InsertSortCFG {
    start [shape=Mdiamond, label="Start"];
    end [shape=Msquare, label="End"];

    loopEntry [label="for (i = 1; i < length; ++i)"];
    assignValue [label="value = a[i]"];
    innerLoopEntry [label="for (j = i - 1; j >= 0 && a[j] > value; --j)"];
    shiftElement [label="a[j + 1] = a[j]"];
    insertValue [label="a[j + 1] = value"];
    updateOuterLoop [label="Next iteration"];

    start -> loopEntry [label="Entry"];
    loopEntry -> assignValue [label="i < length"];
    loopEntry -> end [label="i >= length"];
    assignValue -> innerLoopEntry [label="Prepare for shifting"];
    innerLoopEntry -> shiftElement [label="j >= 0 && a[j] > value"];
    shiftElement -> innerLoopEntry [label="Continue shifting"];
    innerLoopEntry -> insertValue [label="Exit shifting"];
    insertValue -> updateOuterLoop [label="Insert value"];
    updateOuterLoop -> loopEntry [label="Next iteration"];
}

Picture 1. MS Copilot CFG in DOT language

Human written code for the CFG in DOT language

digraph G {
start -> b1;
b1 -> b2 [label="EP1"]

b2 -> end[label="EP5"]
b2 -> b4
b4 -> b5[label="EP2"]

b5 -> b6
b6 -> b8
b8 -> b7[label="EP3"]
b6 ->b9
b7 -> b6
b9->b3 [label="EP4"]
b3->b2

start [shape=Mdiamond];
end [shape=Msquare];
}

Picture 2. Human written CFG in DOT language

Comparison of the Control Flow Graphs for insertSort: MS Copilot vs Human-Generated

When we compare the control flow graphs (CFGs) generated by MS Copilot and the one created by a human, we notice differences not just in how the loops are represented, but in the overall structure and granularity of the graph. While Copilot simplifies the flow into fewer nodes, this simplification leads to a less detailed representation of the program's logic. The human-generated graph, on the other hand, captures more of the nuances and individual steps in the algorithm, providing a clearer picture of the control flow.

1. MS Copilot-Generated CFG

Graph Structure:

The Copilot-generated graph condenses multiple operations into a few key nodes. Here’s how it looks:

• Start Node: This initiates the flow.

• Outer Loop: The outer loop (for (i = 1; i < length; ++i)) is represented as a single node called loopEntry. This node combines the initialization (i = 1), the loop condition (i < length), and the increment (i++) into one node, which oversimplifies the logic.

• Assign Value: The assignment value = a[i] is represented by the assignValue node, which is straightforward and easy to understand.

• Inner Loop: Similarly, the entire inner loop (for (j = i - 1; j >= 0 && a[j] > value; --j)) is represented as a single node, innerLoopEntry, which is a problem for understanding the individual operations in the loop.

• Shift and Insert: The operations of shifting elements and inserting the value (a[j + 1] = a[j] and a[j + 1] = value) are each captured by their respective nodes (shiftElement and insertValue).

• Next Iteration: The transition to the next iteration of the outer loop is handled by the updateOuterLoop node.

Key Issues with Copilot’s Graph:

1. Oversimplification of Loops: By combining the entire outer loop and inner loop logic into single nodes, Copilot makes it difficult to follow the individual steps that happen within these loops. There’s no clear separation between the initialization, condition check, and increment/decrement of the loops. This can be confusing for someone trying to understand or debug the program’s behavior.

2. Lack of Clarity in Flow: Copilot’s graph, while simple, sacrifices important details. For example, it doesn’t break down the condition checking and increment/decrement in the loops. As a result, the flow through these critical points in the algorithm is harder to follow.

3. Edge Labels: Although Copilot provides labeled edges (like "Entry", "i < length"), these are useful but don’t provide as much detail as they could about the specific operations happening at each step. There’s no clear indication of the individual components of the loops.

---

2. Human-Generated CFG

Graph Structure:

The human-generated graph provides a much more granular and detailed view of the control flow:

• Start Node: Just like the Copilot graph, the flow starts with the start node.

• Outer Loop: The outer loop is broken down into three distinct nodes:

  • B1 handles the initialization (i = 1).

  • B2 handles the condition check (i < length).

  • B3 handles the increment (i++).

  By breaking the loop down this way, the human-generated graph provides more transparency about the sequence of operations in the outer loop. It allows us to clearly see when the loop starts, checks the condition, and increments the loop variable.

• Assign Value: The assignment value = a[i] is represented by B4, which is straightforward.

• Inner Loop: The inner loop is split into three distinct nodes:

  • B5 handles the condition check (j >= 0 && a[j] > value).

  • B6 handles the decrement (--j).

  • B7 handles the continuation or exit of the loop.

  This breakdown of the inner loop makes it much easier to understand how the inner loop operates. We can see exactly when the condition is checked, when j is decremented, and when the loop exits.

• Shift and Insert: Nodes B8 and B9 capture the operations of shifting elements and inserting the value into the array. These are straightforward and easy to follow.

Why This Is Better:

1. Detailed Breakdown: The human-generated graph gives us a much clearer picture of what’s happening in both the outer and inner loops. Each step—initialization, condition check, and increment/decrement—is broken down into separate nodes, which makes it easier to trace the flow of control.

2. Clearer Flow: By splitting up the loop logic, it’s easier to understand how the program moves from one step to the next. You can see exactly where the program checks conditions, where it updates variables, and where the loop continues or exits.

3. Improved Debugging: If you were to debug this program, the human-generated graph would make it easier to identify where things might be going wrong, especially within the loops. It provides more granular details about each individual operation.

---

3. Key Differences and Issues with Copilot’s Approach

1. Loop Representation:

• Copilot: Combines the outer and inner loops into single nodes, hiding the steps involved in each loop (initialization, condition check, increment/decrement).

• Human: Breaks the loops down into their components, showing the initialization, condition check, and increment/decrement separately.

2. Node Granularity:

• Copilot: The nodes for shifting elements and inserting the value are separated, but the major flaw is in the handling of the loops. The lack of detail in loop representation makes it harder to understand the program’s control flow.

• Human: Provides more detailed and granular nodes, not just for the shifting and inserting, but for the entire loop process. This helps anyone studying the algorithm follow along with each individual step.

3. Edge Labels:

• Copilot: Uses descriptive edge labels like "Entry" and "i < length," which provide some guidance but don’t fully capture the actions taking place at each step.

• Human: Uses abstract labels like EP1, EP2, but the granularity of the graph compensates for the lack of descriptive edge labels.

---

Conclusion:

The Copilot-generated CFG is simpler and more compact, but it fails to provide a complete breakdown of the loops. By combining the loop conditions, initializations, and increments into a single node, it makes the control flow harder to follow. This is a major issue because loops are a crucial part of how the insertSort function works, and Copilot's approach skips over the details that would help a reader understand the process step-by-step.

On the other hand, the human-generated CFG provides a much clearer and more detailed representation of the algorithm’s flow. By breaking the loops into their individual parts—initialization, condition checking, and incrementing/decrementing—it offers a more transparent look at the program’s logic. This level of detail is especially helpful for anyone trying to understand how the algorithm operates or for debugging purposes.

In summary, Copilot’s simplification of the loops makes the graph less useful for truly understanding the control flow of the insertSort function. The human-generated graph, while more complex, offers a more accurate and understandable view of the algorithm’s execution, making it a better choice for someone studying or debugging the program.

 Task 3. (student 3) 

Convince Copilot to write a branch test for the function insertSort in the C language. Write the prompt and the chatbot answer. Discuss the result, compare it with the code written by a human in the previous section of the book.

Prompt for MS Copilot:

write a branch test for the function insertSort in the C language

Answer from chatbot:

Sure! A branch test aims to check all possible execution paths in a function, ensuring that each branch of conditional statements is tested. Here's an example of a branch test for an insertSort function in C:

#include <stdio.h>
#include <assert.h>

// Function to perform insertion sort
void insertSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // Move elements that are greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Function to check if an array is sorted
int isSorted(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i - 1]) {
            return 0; // Not sorted
        }
    }
    return 1; // Sorted
}

// Branch Test Cases
void testInsertSort() {
    // Test empty array
    int arr1[] = {};
    insertSort(arr1, 0);
    assert(isSorted(arr1, 0));

    // Test single element array
    int arr2[] = {42};
    insertSort(arr2, 1);
    assert(isSorted(arr2, 1));

    // Test already sorted array
    int arr3[] = {1, 2, 3, 4, 5};
    insertSort(arr3, 5);
    assert(isSorted(arr3, 5));

    // Test reverse sorted array
    int arr4[] = {5, 4, 3, 2, 1};
    insertSort(arr4, 5);
    assert(isSorted(arr4, 5));

    // Test random unsorted array
    int arr5[] = {3, 1, 4, 1, 5, 9};
    insertSort(arr5, 6);
    assert(isSorted(arr5, 6));

    printf("All branch tests passed!\n");
}

int main() {
    testInsertSort();
    return 0;
}

This test suite covers various cases:

• An empty array

• A single-element array

• Already sorted data

• Reverse sorted data

• Random unsorted data

It ensures that all conditional branches in insertSort are exercised. If all assertions pass, the sorting function is likely working correctly for different scenarios.

Conclusion:

In the above test, we can see that MS Copilot did not focus carefully on testing all branches and wrote a redundant test.