How to reason about array access in VST?

Question

I have a trouble proving a trivial array access function (file arr.c):

int get(int* arr, int key)
{
    return arr[key];
}

which is translated by clightgen arr.c to (file arr.v):

...
Definition f_get := {|
  fn_return := tint;
  fn_callconv := cc_default;
  fn_params := ((_arr, (tptr tint)) :: (_key, tint) :: nil);
  fn_vars := nil;
  fn_temps := nil;
  fn_body :=
(Sreturn (Some (Ederef
                 (Ebinop Oadd (Etempvar _arr (tptr tint))
                   (Etempvar _key tint) (tptr tint)) tint)))
|}.
...

Here is the proof start (verif_arr.v):

Require Import floyd.proofauto.
Require Import arr.

Local Open Scope logic.
Local Open Scope Z.

Definition get_spec :=
  DECLARE _get
    WITH sh : share, k : Z, arr : Z->val, vk : val, varr : val
    PRE [_key OF tint, _arr OF (tptr tint)]
        PROP (0 <= k < 100; forall i, 0 <= i < 100 -> is_int (arr i))
        LOCAL (`(eq vk) (eval_id _key);
               `(eq varr) (eval_id _arr);
               `isptr (eval_id _arr))
        SEP (`(array_at tint sh arr
                        0 100) (eval_id _arr))
    POST [tint] `(array_at tint sh arr
                           0 100 varr) &&
                 local(`(eq (arr k)) retval).

Definition Vprog : varspecs := nil.
Definition Gprog : funspecs := get_spec :: nil.

Lemma body_get: semax_body Vprog Gprog f_get get_spec.
Proof.
  start_function.
  name karg _key.
  name arrarg _arr.
  forward.

After performing the forward (the last line in verif_arr.v) I've got the following goal:

 array_at tint sh arr 0 100 arrarg
 |-- !!(False /\ False /\ arr k = Vundef) &&
     array_at tint sh arr 0 100 arrarg

Which implies False, so I can not prove it. However, the c-implementation is trivial, and the proof just started.

Now to the Question:

What is wrong with the spec, why it got to an unprovable goal?

VST version:

Definition svn_rev := "6834P".
Definition release := "1.5".
Definition date := "2014-10-02".

CompCert version: 2.4

Coq version:

The Coq Proof Assistant, version 8.4pl3 (January 2014)
compiled on Jan 19 2014 23:14:16 with OCaml 4.01.0

score 2 · Accepted Answer · answered Jan 12 '15 at 13:59

In "standard" Verifiable-C, memory references cannot occur in expressions except at top level within a load statement:

x = a[e];    or     x = *(e.field);  (same as    x = e->field;)

where e is any expression that does not access memory.

Or, a store statement, a[e1] = e2; or e1->field = e2; where e1 and e2 do not access memory.

A memory reference must not occur within a return statement. You'll have to factor your program as follows:

int x;
x = arr[key];
return x;

and then go ahead with the proof.

We are considering extensions, i.e. "nonstandard" Verifiable C, in which memory references can be nested inside expressions in other contexts; but it is not at all clear that this is a good way to reason about programs. It will be worth the experiment.

The reason you're getting "False" in your precondition is that the expression arr[key] does not type-check as a valid expression, since it contains a memory reference. We need to work on better error-message feedback in such situations.

How to reason about array access in VST?

1 Answers1