ID0002047: **This issue was created automatically from Mantis Issue 2047. Further discussion may take place here.** --- | **Id** | **Project** | **Category** | **View** | **Due Date** | **Updated** | | --- | --- | --- | --- | --- | --- | | ID0002047 | Frama-Clang | Plug-in > wp | public | 2015-01-12 | 2015-02-12 | | | | | | | | | --- | --- | --- | --- | --- | --- | | **Reporter** | Jochen | **Assigned To** | correnson | **Resolution** | open | | **Priority** | normal | **Severity** | major | **Reproducibility** | always | | **Platform** | Jan2015-Neon-20140301+dev-STANC | **OS** | - | **OS Version** | xubuntu-cfe13.10 | | **Product Version** | - | **Target Version** | - | **Fixed in Version** | - | ### Description : The loop invariant "xx5" of the attached program "fill1.c" can't be proven with Alt-Ergo. The goal reads fine, viz.: goal fill_loop_inv_xx5_preserved: forall a_3,a_2,a_1,a : addr. (a_1 <> a_2) -> addr_le(a_3, a_2) -> (region(a.base) <= 0) -> (region(a_3.base) <= 0) -> addr_le(a_3, shift_sint16(a_2, 1)) However, the axiom "addr_le_def" appears to be too weak, it currently reads: axiom addr_le_def : (forall p:addr. forall q:addr [addr_le(p, q)]. (((p).base = (q).base) -> (addr_le(p, q) -> ((p).offset <= (q).offset)))) While the loop inveriant certainly should be provable, I don't see any way to prove a_3.base=a_2.base with the current version of the file. Moreover, in order for axioms "addr_le_def" and "addr_le_def1" to be a definition of "addr_le(.,.)" in terms of "=" and "<=" etc., axiom "addr_le_def" should be changed to: axiom addr_le_def : (forall p:addr. forall q:addr [addr_le(p, q)]. (addr_le(p, q) -> p.base = q.base and p.offset <= q.offset)) After that change, Alt-Ergo proves the goal without any problems. The attached file "fill_loop_inv_xx5_preserved_Alt-Ergo.mlw" contains the changed version in a comment at line 408. If my argument is right, the whole axiomatization should be reviewed to remove similar flaws, which give Frama-C a rather poor performance on address arithmetic. (For that reason, I assigned a higher severity.) ### Additional Information : Originally, I'd submitted this issue to the Alt-Ergo issue tracker, see https://github.com/OCamlPro/alt-ergo/issues/9. I'm indebted to Mohamed Iguernelala for hinting at the weak axiom "addr_le_def", where I had a blind spot. ## Attachments - [fill1.c](/uploads/e5ff187165a5e10b7858e1f325eea68a/fill1.c) - [fill_loop_inv_xx5_preserved_Alt-Ergo.mlw](/uploads/6292554fc2953d67792737e6dac31199/fill_loop_inv_xx5_preserved_Alt-Ergo.mlw) - [fill.c](/uploads/c1dcc11d568e2e09d95aeabf0b9df093/fill.c) - [fill4.c](/uploads/5ce99f117503a2df12c827af1b439520/fill4.c) - [fill5.c](/uploads/ece00cbe919a18c0800d32b0adb27fb2/fill5.c) - [fill4r.c](/uploads/81225ff5f9ecee0d89645919cbe59e44/fill4r.c) - [find_arr.c](/uploads/fec90cf4fecefaee9a7cea344c14b693/find_arr.c) - [find_ptr.c](/uploads/8430a7bbd76c8f263bd433d3cfd746d8/find_ptr.c) - [find_ptr_foo_post_Alt-Ergo_modified.mlw](/uploads/d52e028cdf21562b07c9e340031cef8c/find_ptr_foo_post_Alt-Ergo_modified.mlw)