[Switch Restructuring] Insert CaseNodes

[ebehner]

Proposal

The MissingCaseFinder searches for possible cases that were not found/there when constructing the initial switch. Now, we insert such a potential case node only if the corresponding case constant does not exist. However, there are cases where we still can insert the missing case.

Consider the following decompiled code (test_switch.zip test7_b):

int test7_b() {
    int var_0;
    int * var_1;
    printf("Enter week number(1-7): ");
    var_1 = &var_0;
    __isoc99_scanf(0x804c025, var_1);
    if (var_0 == 0x190) {
        printf("Thursday");  // <---------- missing case
    }
    switch(var_0) {
    case 0x0:
        printf("Monday");
        break;
    case 0x6:
        printf("Saturday");
        break;
    case 0x9:
        printf("Sunday");
        break;
    case 0xc:
        printf("Tuesday");
        break;
    case 0x22:
        printf("Wednesday");
        break;
    case 0x190:
    case 0x1f4:
        printf("Friday");
        break;
    default:
        printf("Invalid input! Please enter week number between 1-7.");
    }
    return 0;
}

The preferred output would be:

int test7_b() {
    int var_0;
    int * var_1;
    printf("Enter week number(1-7): ");
    var_1 = &var_0;
    __isoc99_scanf(0x804c025, var_1);
    switch(var_0) {
    case 0x0:
        printf("Monday");
        break;
    case 0x6:
        printf("Saturday");
        break;
    case 0x9:
        printf("Sunday");
        break;
    case 0xc:
        printf("Tuesday");
        break;
    case 0x22:
        printf("Wednesday");
        break;
    case 0x190:
        printf("Thursday");
    case 0x1f4:
        printf("Friday");
        break;
    default:
        printf("Invalid input! Please enter week number between 1-7.");
    }
    return 0;
}

A similar example is test18 in the same executable, we currently have:

int test18() {
    int var_0;
    int * var_1;
    printf("Enter week number(1-7): ");
    var_1 = &var_0;
    __isoc99_scanf(0x804c025, var_1);
    switch(var_0) {
    case 1:
        printf("Monday");
        var_0 += 0x1f4;
        break;
    case 0x1f4:
        printf("Friday");
        break;
    }
    if ((var_0 != 1) && (var_0 != 12)) {
        printf("Invalid input! Please enter week number between 1-7."); // <---------- do not find default do due missing case
    }
    else {
        printf("Tuesday"); // <---------- missing case
    }
    printf("the number is %d", var_0);
    return 0;
}

But we would like to have the following output:

int test18() {
    int var_0;
    int * var_1;
    printf("Enter week number(1-7): ");
    var_1 = &var_0;
    __isoc99_scanf(0x804c025, var_1);
    switch(var_0) {
    case 1:
        printf("Monday");
        var_0 += 0x1f4;
    case 12:
        printf("Tuesday");
        break;
    case 0x1f4:
        printf("Friday");
        break;
    default:
        printf("Invalid input! Please enter week number between 1-7.");
    }
    printf("the number is %d", var_0);
    return 0;
}

Remark: test18 also has another problem, see Bug #19

Approach

Find a good way to check whether it is possible to insert a case node whose case constant already exists. It is important to consider the reachability of the nodes.

[ebehner]

see also the sample of Issue #34

[ebehner]

Additionally: In missing_case_finder.py line 216, two case candidates can have the same constant. At the moment, we add the first that fits. However, this may not be the best solution.

• Check for the same constants and merge?
• If this is not the case, find the most suitable (easiest in complexity?)
• Check which can be added without conflict?

[ebehner]

/cib

[github-actions[bot]]

Branch issue-20-_Switch_Restructuring_Insert_CaseNodes created!