Unstable tests generation for signed/unsigned loops [C standard test]

Open belous-dp opened this issue 3 years ago • 1 comments

Description Tests generation for for loops is broken. Somehow the tests for one function depend on another function, although the functions themselves do not depend on each other. The issue is somehow related to the sign of the numbers.

To Reproduce Steps to reproduce the behaviour:

Step 1: generate tests for the following source code

int sum_up_to(unsigned int n) {
    int i = 1;
    int sum = 0;
    while (i <= n) {
        sum = sum + i;
        i = i + 1;
    }
    if (sum == 21) {
        return -1;
    }
    return sum;
}

int sum_up_to_correct(unsigned int n) {
    unsigned int i = 1;
    unsigned int sum = 0;
    while (i <= n) {
        sum += i;
        i++;
    }
    if (sum == 21U) {
        return -1;
    }
    return 1;
}

int for_loop(int n) {
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += i;
    }
    if (sum == 21) {
        return n;
    }
    if (sum < 10) {
        return n * 100;
    }
    return 2;
}

int for_loop_unsigned(unsigned int n) {
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += i;
    }
    if (sum == 21) {
        return n;
    }
    if (sum < 10) {
        return n * 100;
    }
    return 2;
}

unsigned int for_loop_unsigned_correct(unsigned int n) {
    unsigned int sum = 0;
    for (unsigned int i = 1; i <= n; ++i) {
        sum += i;
    }
    if (sum == 21) {
        return n;
    }
    if (sum < 10U) {
        return n * 100U;
    }
    return 2U;
}

Generated tests:

// Some tests for function 'sum_up_to' were skipped, as execution of function is out of timeout.

// Some tests for function 'sum_up_to_correct' were skipped, as execution of function is out of timeout.

// Some tests for function 'for_loop' were skipped, as execution of function is out of timeout.

// Some tests for function 'for_loop_unsigned' were skipped, as execution of function is out of timeout.

// Some tests for function 'for_loop_unsigned_correct' were skipped, as execution of function is out of timeout.

TEST(regression, sum_up_to_test_1)
{
    int actual = sum_up_to(0U);
    EXPECT_EQ(0, actual);
}

TEST(regression, sum_up_to_correct_test_1)
{
    int actual = sum_up_to_correct(0U);
    EXPECT_EQ(1, actual);
}

TEST(regression, sum_up_to_correct_test_2)
{
    int actual = sum_up_to_correct(6U);
    EXPECT_EQ(-1, actual);
}

TEST(regression, for_loop_test_1)
{
    int actual = for_loop(0);
    EXPECT_EQ(0, actual);
}

TEST(regression, for_loop_test_2)
{
    int actual = for_loop(6);
    EXPECT_EQ(6, actual);
}

TEST(regression, for_loop_test_3)
{
    int actual = for_loop(4);
    EXPECT_EQ(2, actual);
}

TEST(regression, for_loop_unsigned_test_1)
{
    int actual = for_loop_unsigned(0U);
    EXPECT_EQ(0, actual);
}

TEST(regression, for_loop_unsigned_correct_test_1)
{
    unsigned int actual = for_loop_unsigned_correct(0U);
    EXPECT_EQ(0U, actual);
}

The first function (sum_up_to) is not fully covered, while the second function (sum_up_to_correct) is. Same with other functions: for_loop is covered and that's OK. for_loop_unsigned isn't covered and that's also OK (perhaps because the source code isn't correct: there's signed-unsigned comparison that is implementation defined, and thus UB. However, from the user's point of view, I'd like to get warnings or error tests focused on this problem). There're not enough tests for the for_loop_unsigned_correct function, thus it isn't fully covered.

Step 2 Now let's change the function for_loop_unsigned_correct: add U in the comparison if (sum == 21), so the result is if (sum == 21U). It is clear that this function is independent of the others. It is also clear that this change doesn't affect the overall correctness of the function: in the first case 21 was implicitly promoted to 21U by the compiler during comparison, and in the second case 21 is explicitly unsigned.

So the source code is:

int sum_up_to(unsigned int n) {
    int i = 1;
    int sum = 0;
    while (i <= n) {
        sum = sum + i;
        i = i + 1;
    }
    if (sum == 21) {
        return -1;
    }
    return sum;
}

int sum_up_to_correct(unsigned int n) {
    unsigned int i = 1;
    unsigned int sum = 0;
    while (i <= n) {
        sum += i;
        i++;
    }
    if (sum == 21U) {
        return -1;
    }
    return 1;
}

int for_loop(int n) {
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += i;
    }
    if (sum == 21) {
        return n;
    }
    if (sum < 10) {
        return n * 100;
    }
    return 2;
}

int for_loop_unsigned(unsigned int n) {
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += i;
    }
    if (sum == 21) {
        return n;
    }
    if (sum < 10) {
        return n * 100;
    }
    return 2;
}

unsigned int for_loop_unsigned_correct(unsigned int n) {
    unsigned int sum = 0;
    for (unsigned int i = 1; i <= n; ++i) {
        sum += i;
    }
    if (sum == 21U) {
        return n;
    }
    if (sum < 10U) {
        return n * 100U;
    }
    return 2U;
}

Generated tests:

TEST(regression, sum_up_to_test_1)
{
    int actual = sum_up_to(0U);
    EXPECT_EQ(0, actual);
}

TEST(regression, sum_up_to_test_2)
{
    int actual = sum_up_to(6U);
    EXPECT_EQ(-1, actual);
}

TEST(regression, sum_up_to_correct_test_1)
{
    int actual = sum_up_to_correct(0U);
    EXPECT_EQ(1, actual);
}

TEST(regression, sum_up_to_correct_test_2)
{
    int actual = sum_up_to_correct(6U);
    EXPECT_EQ(-1, actual);
}

TEST(regression, for_loop_test_1)
{
    int actual = for_loop(0);
    EXPECT_EQ(0, actual);
}

TEST(regression, for_loop_test_2)
{
    int actual = for_loop(6);
    EXPECT_EQ(6, actual);
}

TEST(regression, for_loop_test_3)
{
    int actual = for_loop(4);
    EXPECT_EQ(2, actual);
}

TEST(regression, for_loop_unsigned_test_1)
{
    int actual = for_loop_unsigned(0U);
    EXPECT_EQ(0, actual);
}

TEST(regression, for_loop_unsigned_correct_test_1)
{
    unsigned int actual = for_loop_unsigned_correct(0U);
    EXPECT_EQ(0U, actual);
}

TEST(regression, for_loop_unsigned_correct_test_2)
{
    unsigned int actual = for_loop_unsigned_correct(6U);
    EXPECT_EQ(6U, actual);
}

TEST(regression, for_loop_unsigned_correct_test_3)
{
    unsigned int actual = for_loop_unsigned_correct(4U);
    EXPECT_EQ(2U, actual);
}

Boom! sum_up_to is now fully covered. However, this function hasn't been changed since the last launch.

Generated tests for sum_up_to_correct, for_loop_unsigned remain the same (OK).

Oddly, now there're more tests for function for_loop_unsigned_correct, although the behaviour of the functions hasn't changed. Even the assembly of this two versions is the same: first version, second version!

while loops are ok Seems like this thing happens only with for loops: with while, do..while and goto generated tests coverage 100% and tests are the same in each generation. Examples:

int while_loop(int n) {
    int i = 0;
    while (i < n) {
        i = i + 1;
        if (n % i == 37)
            return 1;
        else if (i == 50)
            return 2;
    }
    return 0;
}

int while_loop_unsigned(unsigned int n) {
    int i = 0;
    while (i < n) {
        i = i + 1;
        if (n % i == 37)
            return 1;
        else if (i == 50)
            return 2;
    }
    return 0;
}

unsigned int while_loop_unsigned_correct(unsigned int n) {
    unsigned int i = 0;
    while (i < n) {
        i = i + 1;
        if (n % i == 37U)
            return 1;
        else if (i == 50U)
            return 2U;
    }
    return 0U;
}

int do_while_loop(int n) {
    int i = 0;
    do {
        i = i + 1;
        if (n % i == 37)
            return 1;
        else if (i == 50)
            return 2;
    } while (i < n);
    return 0;
}

int do_while_loop_unsigned(unsigned int n) {
    int i = 0;
    do {
        i = i + 1;
        if (n % i == 37)
            return 1;
        else if (i == 50)
            return 2;
    } while (i < n);
    return 0;
}

unsigned int do_while_loop_unsigned_correct(unsigned int n) {
    unsigned int i = 0;
    do {
        i = i + 1;
        if (n % i == 37U)
            return 1U;
        else if (i == 50U)
            return 2U;
    } while (i < n);
    return 0U;
}

int continue_break(int n) {
    int i = n, res = 0;
    do {
        res += i;
        if (res > 100) {
            break;
        }
        if (i < 20) {
            continue;
        }
    } while (false);
    return res;
}

int goto_keyword(unsigned int a) {
    unsigned int sum = 0;
    do {
        if (a == 15) {
            goto RET;
        }
        sum += a;
        a++;
    } while (a < 22);
    if (sum > 1000) {
        return 1;
    }
    return 2;
    RET: return -1;
}

Generated tests:

TEST(regression, while_loop_test_1)
{
    int actual = while_loop(0);
    EXPECT_EQ(0, actual);
}

TEST(regression, while_loop_test_2)
{
    int actual = while_loop(262144);
    EXPECT_EQ(2, actual);
}

TEST(regression, while_loop_test_3)
{
    int actual = while_loop(343143419);
    EXPECT_EQ(1, actual);
}

TEST(regression, while_loop_unsigned_test_1)
{
    int actual = while_loop_unsigned(0U);
    EXPECT_EQ(0, actual);
}

TEST(regression, while_loop_unsigned_test_2)
{
    int actual = while_loop_unsigned(255U);
    EXPECT_EQ(2, actual);
}

TEST(regression, while_loop_unsigned_test_3)
{
    int actual = while_loop_unsigned(1907531447U);
    EXPECT_EQ(1, actual);
}

TEST(regression, while_loop_unsigned_correct_test_1)
{
    unsigned int actual = while_loop_unsigned_correct(0U);
    EXPECT_EQ(0U, actual);
}

TEST(regression, while_loop_unsigned_correct_test_2)
{
    unsigned int actual = while_loop_unsigned_correct(255U);
    EXPECT_EQ(2U, actual);
}

TEST(regression, while_loop_unsigned_correct_test_3)
{
    unsigned int actual = while_loop_unsigned_correct(1907531447U);
    EXPECT_EQ(1U, actual);
}

TEST(regression, do_while_loop_test_1)
{
    int actual = do_while_loop(0);
    EXPECT_EQ(0, actual);
}

TEST(regression, do_while_loop_test_2)
{
    int actual = do_while_loop(16777216);
    EXPECT_EQ(2, actual);
}

TEST(regression, do_while_loop_test_3)
{
    int actual = do_while_loop(153383389);
    EXPECT_EQ(1, actual);
}

TEST(regression, do_while_loop_unsigned_test_1)
{
    int actual = do_while_loop_unsigned(0U);
    EXPECT_EQ(0, actual);
}

TEST(regression, do_while_loop_unsigned_test_2)
{
    int actual = do_while_loop_unsigned(16711680U);
    EXPECT_EQ(2, actual);
}

TEST(regression, do_while_loop_unsigned_test_3)
{
    int actual = do_while_loop_unsigned(2752969203U);
    EXPECT_EQ(1, actual);
}

TEST(regression, do_while_loop_unsigned_correct_test_1)
{
    unsigned int actual = do_while_loop_unsigned_correct(0U);
    EXPECT_EQ(0U, actual);
}

TEST(regression, do_while_loop_unsigned_correct_test_2)
{
    unsigned int actual = do_while_loop_unsigned_correct(16711680U);
    EXPECT_EQ(2U, actual);
}

TEST(regression, do_while_loop_unsigned_correct_test_3)
{
    unsigned int actual = do_while_loop_unsigned_correct(2752969203U);
    EXPECT_EQ(1U, actual);
}

TEST(regression, continue_break_test_1)
{
    int actual = continue_break(32);
    EXPECT_EQ(32, actual);
}

TEST(regression, continue_break_test_2)
{
    int actual = continue_break(0);
    EXPECT_EQ(0, actual);
}

TEST(regression, continue_break_test_3)
{
    int actual = continue_break(101);
    EXPECT_EQ(101, actual);
}

TEST(regression, goto_keyword_test_1)
{
    int actual = goto_keyword(128U);
    EXPECT_EQ(2, actual);
}

TEST(regression, goto_keyword_test_2)
{
    int actual = goto_keyword(67108883U);
    EXPECT_EQ(1, actual);
}

TEST(regression, goto_keyword_test_3)
{
    int actual = goto_keyword(14U);
    EXPECT_EQ(-1, actual);
}

TEST(regression, goto_keyword_test_4)
{
    int actual = goto_keyword(15U);
    EXPECT_EQ(-1, actual);
}

Environment UTBotCpp version 2022.7.0, commit 6048615 (add input/output support). "Use Deterministic Searcher" is set on.

Jul 22 '22 13:07 belous-dp

After fixing this bug, move these examples from c-example-unsupported to c-example

Sep 09 '22 15:09 belous-dp