Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Aliasing pre-condition not processed correctly if is_fresh clause it not standalone #8492

Open
hanno-becker opened this issue Nov 4, 2024 · 3 comments · May be fixed by #8494
Open

Aliasing pre-condition not processed correctly if is_fresh clause it not standalone #8492

hanno-becker opened this issue Nov 4, 2024 · 3 comments · May be fixed by #8494
Labels
bug pending merge soundness Soundness bug? Review and add "aws" if it is, or remove "soundness" if it isn't.

Comments

@hanno-becker
Copy link

hanno-becker commented Nov 4, 2024

CBMC Version: 6.3.1

The following proves successfully:

void dummy0(int *r, int *a)
__CPROVER_requires(__CPROVER_is_fresh(r, sizeof(*r)))
__CPROVER_requires(r == a)
__CPROVER_assigns(*r)
__CPROVER_ensures(*a==42) {
  *r = 42;
}

/*
goto-cc harness.c --function harness -o a.out
goto-instrument --dfcc harness --enforce-contract dummy0 a.out b.out
cbmc b.out
*/
void harness(void) {
  int *r;
  int *a;
  dummy0(r, a);
}

The following does not:

void dummy0(int *r, int *a)
__CPROVER_requires(r != NULL && __CPROVER_is_fresh(r, sizeof(*r)))
__CPROVER_requires(r == a)
__CPROVER_assigns(*r)
__CPROVER_ensures(*a==42) {
  *r = 42;
}

/*
goto-cc harness.c --function harness -o a.out
goto-instrument --dfcc harness --enforce-contract dummy0 a.out b.out
cbmc b.out
*/
void harness(void) {
  int *r;
  int *a;
  dummy0(r, a);
}

Even if the r != NULL clause is redundant, this is surprising -- is there dedicated logic for detecting is_fresh clauses which only works when is_fresh is used at the top-level in a requires clause?

@remi-delmas-3000
Copy link
Collaborator

remi-delmas-3000 commented Nov 4, 2024

This harness gets into a state where r == a and *r != *a:

void dummy0(int *r, int *a)
__CPROVER_requires(r != NULL && __CPROVER_is_fresh(r, sizeof(int)) && r == a)
__CPROVER_assigns(*r)
__CPROVER_ensures(*a == 42) {
  int *dummy_r_before = r;
  int *dummy_a_before = a;
  int dummy_star_r_before = *r;
  int dummy_star_a_before = *a;
  __CPROVER_assert(r == a, " r == a before");
  __CPROVER_assert(*r == *a, "*r == *a before");
  *r = 42;
  int *dummy_r_after = r;
  int *dummy_a_after = a;
  int dummy_star_r_after = *r;
  int dummy_start_a_after = *a;
  __CPROVER_assert(r == a, " r == a after");
  __CPROVER_assert(*r == *a, "*r == *a after");
}
[dummy0.assertion.1] line 15  r == a before: SUCCESS
[dummy0.assertion.2] line 16 *r == *a before: FAILURE
[dummy0.assigns.1] line 17 Check that *r is assignable: SUCCESS

[dummy0.assertion.3] line 22  r == a after: SUCCESS
[dummy0.assertion.4] line 23 *r == *a after: FAILURE

with trace for dummy0.assertion.2

  dummy_r_before=&dynamic_object$10 (00000010 00000000 00000000 00000000 00000000 00000000 00000000 00000000)
State 475 file cases.c function dummy0 line 12 thread 0
  dummy_a_before=&dynamic_object$10 (00000010 00000000 00000000 00000000 00000000 00000000 00000000 00000000)
State 483 file cases.c function dummy0 line 13 thread 0
  dummy_star_r_before=268435502 (00010000 00000000 00000000 00101110)
State 491 file cases.c function dummy0 line 14 thread 0
  dummy_star_a_before=268435498 (00010000 00000000 00000000 00101010)

and trace for dummy0.assertion.4

State 473 file cases.c function dummy0 line 11 thread 0
  dummy_r_before=&dynamic_object$10 (00000010 00000000 00000000 00000000 00000000 00000000 00000000 00000000)
State 475 file cases.c function dummy0 line 12 thread 0
  dummy_a_before=&dynamic_object$10 (00000010 00000000 00000000 00000000 00000000 00000000 00000000 00000000)
State 483 file cases.c function dummy0 line 13 thread 0
  dummy_star_r_before=268435498 (00010000 00000000 00000000 00101010)
State 491 file cases.c function dummy0 line 14 thread 0
  dummy_star_a_before=268435498 (00010000 00000000 00000000 00101010)
State 498 file cases.c function dummy0 line 17 thread 0
State 499 file cases.c function dummy0 line 17 thread 0
State 500 file cases.c function dummy0 line 17 thread 0
State 523 file cases.c function dummy0 line 17 thread 0
State 531 file cases.c function dummy0 line 17 thread 0
State 533 file cases.c function dummy0 line 18 thread 0
  dummy_r_after=&dynamic_object$10 (00000010 00000000 00000000 00000000 00000000 00000000 00000000 00000000)
State 535 file cases.c function dummy0 line 19 thread 0
  dummy_a_after=&dynamic_object$10 (00000010 00000000 00000000 00000000 00000000 00000000 00000000 00000000)
State 543 file cases.c function dummy0 line 20 thread 0
  dummy_star_r_after=42 (00000000 00000000 00000000 00101010)
State 551 file cases.c function dummy0 line 21 thread 0
  dummy_start_a_after=268435498 (00010000 00000000 00000000 00101010)
  file cases.c function dummy0 line 23 thread 0

Interestingly, the counter examples disappear if i break down the conjunction into separate clauses:

void dummy0(int *r, int *a)
__CPROVER_requires(r != NULL)
__CPROVER_requires(__CPROVER_is_fresh(r, sizeof(int)))
__CPROVER_requires(r == a)
__CPROVER_assigns(*r)
__CPROVER_ensures(*a == 42) {
 int *dummy_r_before = r;
 int *dummy_a_before = a;
 int dummy_star_r_before = *r;
 int dummy_start_a_before = *a;
 __CPROVER_assert(r == a, " r == a before");
 __CPROVER_assert(*r == *a, "*r == *a before");
 *r = 42;
 int *dummy_r_after = r;
 int *dummy_a_after = a;
 int dummy_star_r_after = *r;
 int dummy_start_a_after = *a;
 __CPROVER_assert(r == a, " r == a after");
 __CPROVER_assert(*r == *a, "*r == *a after");
}
[dummy0.postcondition.1] line 10 Check ensures clause of contract contract::dummy0 for function dummy0: SUCCESS
...
[dummy0.assertion.1] line 15  r == a before: SUCCESS
[dummy0.assertion.2] line 16 *r == *a before: SUCCESS
...
[dummy0.assertion.3] line 22  r == a after: SUCCESS
[dummy0.assertion.4] line 23 *r == *a after: SUCCESS

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

@remi-delmas-3000
Copy link
Collaborator

remi-delmas-3000 commented Nov 4, 2024

Minimum reproducer

/* cbmc main.c */
void main(void) {
  int *r;
  int *a;
  bool tmp_if_expr;
  if(r==NULL) {
    goto L1;
  }
  r = malloc(4);
  __CPROVER_assume(r);
  tmp_if_expr = true;
  goto L2;
L1:
  tmp_if_expr = false;
L2:
  __CPROVER_assume(tmp_if_expr); 
  
  // if `r == NULL` held in the initial state, `malloc` was skipped, `tmp_if_expr` set to `false` and `__CPROVER_assume(false)` was executed. Since progress stops on an assume false, none of the downstream assertions will be reached with `r == NULL`.

  // if `r != NULL` held in the initial state,  `malloc` was executed, `r` was updated to a point to a fresh object, and `tmp_if_expr` set to `true` and `__CPROVER_assume(true)` was executed. Execution continue with `r` pointing to a fresh object.
  
  __CPROVER_assume(r == a);
  __CPROVER_assert(a == r, "a == r before");
  __CPROVER_assert(*a == *r, "*a == *r before");
  *r = 42;
  __CPROVER_assert(a == r, "a == r after");
  __CPROVER_assert(*a == *r, "*a == *r after");
}

@tautschnig
Copy link
Collaborator

The problem is that the value set that we use for dereferencing during symbolic execution does not have any value for a (as only assignments, but not assumptions, trigger updates to the value set).

@tautschnig tautschnig self-assigned this Nov 4, 2024
@tautschnig tautschnig added bug soundness Soundness bug? Review and add "aws" if it is, or remove "soundness" if it isn't. labels Nov 4, 2024
tautschnig added a commit to tautschnig/cbmc that referenced this issue Nov 4, 2024
Value sets and constant propagation are our only sources of points-to
information when resolving dereferences in goto-symex. Therefore,
assuming or branching on equalities of pointer-typed variables must have
us consider both of their value sets to be equal. Else we may end up
with spurious counterexamples as seen with the enclosed regression test
(where we previously did not have any known value for `a`).

Fixes: diffblue#8492
@tautschnig tautschnig linked a pull request Nov 4, 2024 that will close this issue
4 tasks
@tautschnig tautschnig removed their assignment Nov 4, 2024
hanno-becker added a commit to pq-code-package/mlkem-native that referenced this issue Nov 4, 2024
Previously, when a function under proof would assume a pointer to
a structure, the verification harness would construct an instance
of that structure on the stack and pass its address.

This approach is unsound, because it adds to the contractual assumptions
of the function the specifics of the function invocation in the test
harness. For example, a missing bounds constraint in the spec might
go undetected just because the stack-allocated variable happens to
satisfy it.

The most robust way to deal with this, so it seems, is to minimize
the harnesses to merely pass uninitialized variables of the right type
to the function under proof. In particular, where a pointer is expected,
pass an uninitialized pointer, rather than the address of a stack allocated
structure.

Also, remove redundant `x != NULL` preconditions when `IS_FRESH(x,...)`
is assumed. This is not only redundant, but also error prone because of
diffblue/cbmc#8492.

This commit implements those changes for all harnesses implemented so far.

Signed-off-by: Hanno Becker <beckphan@amazon.co.uk>
hanno-becker added a commit to pq-code-package/mlkem-native that referenced this issue Nov 4, 2024
Previously, when a function under proof would assume a pointer to
a structure, the verification harness would construct an instance
of that structure on the stack and pass its address.

This approach is unsound, because it adds to the contractual assumptions
of the function the specifics of the function invocation in the test
harness. For example, a missing bounds constraint in the spec might
go undetected just because the stack-allocated variable happens to
satisfy it.

The most robust way to deal with this, so it seems, is to minimize
the harnesses to merely pass uninitialized variables of the right type
to the function under proof. In particular, where a pointer is expected,
pass an uninitialized pointer, rather than the address of a stack allocated
structure.

Also, remove redundant `x != NULL` preconditions when `IS_FRESH(x,...)`
is assumed. This is not only redundant, but also error prone because of
diffblue/cbmc#8492.

This commit implements those changes for all harnesses implemented so far.

As it turns out, a few specs were incorrect because of missing IS_FRESH
annotations, hidden by the correct allocation in the harness.

Signed-off-by: Hanno Becker <beckphan@amazon.co.uk>
tautschnig added a commit to tautschnig/cbmc that referenced this issue Nov 5, 2024
Value sets and constant propagation are our only sources of points-to
information when resolving dereferences in goto-symex. Therefore,
assuming or branching on equalities of pointer-typed variables must have
us consider both of their value sets to be equal. Else we may end up
with spurious counterexamples as seen with the enclosed regression test
(where we previously did not have any known value for `a`).

Fixes: diffblue#8492
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug pending merge soundness Soundness bug? Review and add "aws" if it is, or remove "soundness" if it isn't.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants