`__CPROVER_forall` fails when dealing with flattening of nested structure

[hanno-becker]

I'm observing unexpected behaviour when trying to use __CPROVER_forall to access the fields of a nested array structure when cast as a flat array of cells. cc @tautschnig @remi-delmas-3000

Minimal example:

/* instructions

foo:
	goto-cc harness.c --function foo_harness -o a.out
	goto-instrument --dfcc foo_harness --enforce-contract foo a.out b.out
	cbmc b.out --bitwuzla
*/

#include <stdint.h>

typedef struct __attribute__((packed)) {
    int data[2];
} arr;

typedef struct __attribute__((packed)) {
    arr vec[2];
} arrvec;

void foo(arrvec *x)
  __CPROVER_requires(__CPROVER_is_fresh(x, sizeof(arrvec)))
  __CPROVER_requires(x->vec[1].data[0] < 42)
{
    // OK:
    __CPROVER_assert(((int*)x)[2] < 42, "");
    // NOT OK:
    __CPROVER_assert(__CPROVER_forall {unsigned k; k == 2 ==> ((int*)x)[k] < 42}, "");
    // OK:
    __CPROVER_assert(__CPROVER_forall {unsigned k; k == 2 ==> ((int (*)[2])x)[k/2][k % 2] < 42}, "");
}

void foo_harness(void) {
    arr *x;
    foo(x);
}

[tautschnig]

Taking a look. Here is a simplified version that equally fails and neither uses contracts nor requires the use of an SMT solver - cbmc harness.c will do:

typedef struct __attribute__((packed)) {
    int data[2];
} arr;

typedef struct __attribute__((packed)) {
    arr vec[2];
} arrvec;

int main() {
    arrvec A;
    arrvec *x = &A;
    __CPROVER_assume(x->vec[1].data[0] < 42);
    // OK:
    __CPROVER_assert(((int*)x)[2] < 42, "");
    // NOT OK:
    __CPROVER_assert(__CPROVER_forall {unsigned k; k == 2 ==> ((int*)x)[k] < 42}, "");
    // OK:
    __CPROVER_assert(__CPROVER_forall {unsigned k; k == 2 ==> ((int (*)[2])x)[k/2][k % 2] < 42}, "");
}

[tautschnig]

Turns out this isn't a problem related to quantifiers. The following further simplification (still equivalent to the original one) also fails:

typedef struct __attribute__((packed)) {
    int data[2];
} arr;

typedef struct __attribute__((packed)) {
    arr vec[2];
} arrvec;

int main() {
    arrvec A;
    arrvec *x = &A;
    __CPROVER_assume(x->vec[1].data[0] < 42);
    unsigned k;
    __CPROVER_assert(k != 2 || ((int*)x)[k] < 42, "");
}

It seems the problem is with field sensitivity during symbolic execution, where we appear to (spuriously) turn ((int*)x)k effectively into A.vec[0].data[k].

[hanno-becker]

@tautschnig @remi-delmas-3000 Any fix in sight?

[rod-chapman]

What behaviour were you expecting? In Michael's final example, k is uninitialized, so any reference to k looks like UB to me.

Flattened out, x is pointing at 4 integers, so k could be anything in 0 .. 3. Let's try that:

int main()
{
  arrvec A;
  arrvec *x = &A;
  __CPROVER_assume(x->vec[1].data[0] < 42);
  unsigned k;
  k = 0;
  __CPROVER_assert(k != 2 || ((int *)x)[k] < 42, "");
  k = 1;
  __CPROVER_assert(k != 2 || ((int *)x)[k] < 42, "");
  k = 2;
  __CPROVER_assert(k != 2 || ((int *)x)[k] < 42, "");
  k = 3;
  __CPROVER_assert(k != 2 || ((int *)x)[k] < 42, "");
}

then with CBMC 6.4.1

% cbmc main.c       
CBMC version 6.4.1 (cbmc-6.4.1) 64-bit arm64 macos
Type-checking main
Generating GOTO Program
Adding CPROVER library (arm64)
Removal of function pointers and virtual functions
Generic Property Instrumentation
Starting Bounded Model Checking
Passing problem to propositional reduction
converting SSA
Running propositional reduction
SAT checker inconsistent: instance is UNSATISFIABLE

** Results:
main.c function main
[main.array_bounds.1] line 15 array.vec dynamic object upper bound in x->vec[(signed long int)1]: SUCCESS
[main.array_bounds.2] line 15 array.vec[].data dynamic object upper bound in x->vec[(signed long int)1].data[(signed long int)0]: SUCCESS
[main.pointer_dereference.1] line 15 dereference failure: dead object in x->vec: SUCCESS
[main.pointer_dereference.2] line 15 dereference failure: pointer outside object bounds in x->vec: SUCCESS
[main.assertion.1] line 18 assertion: SUCCESS
[main.pointer_dereference.3] line 18 dereference failure: dead object in ((signed int *)x)[(signed long int)k]: SUCCESS
[main.pointer_dereference.4] line 18 dereference failure: pointer outside object bounds in ((signed int *)x)[(signed long int)k]: SUCCESS
[main.assertion.2] line 20 assertion: SUCCESS
[main.pointer_dereference.5] line 20 dereference failure: dead object in ((signed int *)x)[(signed long int)k]: SUCCESS
[main.pointer_dereference.6] line 20 dereference failure: pointer outside object bounds in ((signed int *)x)[(signed long int)k]: SUCCESS
[main.assertion.3] line 22 assertion: SUCCESS
[main.pointer_dereference.7] line 22 dereference failure: dead object in ((signed int *)x)[(signed long int)k]: SUCCESS
[main.pointer_dereference.8] line 22 dereference failure: pointer outside object bounds in ((signed int *)x)[(signed long int)k]: SUCCESS
[main.assertion.4] line 24 assertion: SUCCESS
[main.pointer_dereference.9] line 24 dereference failure: dead object in ((signed int *)x)[(signed long int)k]: SUCCESS
[main.pointer_dereference.10] line 24 dereference failure: pointer outside object bounds in ((signed int *)x)[(signed long int)k]: SUCCESS

** 0 of 16 failed (1 iterations)
VERIFICATION SUCCESSFUL

which doesn't look right to me, since we've only assumed that one element is < 42. What did I miss?

[hanno-becker]

@rod-chapman I don't follow, in 3 of 4 asserts, the k != 2 clause holds.

[tautschnig]

When evaluating ((int *)x)[k] < 42 the only possible value of k is 2. But I am not entirely convinced that ((int *)x)[<whatever>] is behaviour covered by the C standard. It would be ok for char * instead of int *.

That said: I know which piece in the CBMC code base is causing us to go wrong (?) here, but I am wondering whether we are mis-optimising there or the input code is the culprit.

[rod-chapman]

Oh... so we're inferring that "(k is uninitialized && not (k != 2)) infers k == 2".
Not sure that's wise.

[rod-chapman]

If your code evaluated "k != 2 || ((int *)x)[k] < 42" at runtime with k uninitialized, then it's UB, because the left hand side of the (short circuit) || operator has to be evaluated first, right?