Skip to content
GitLab
Projects Groups Topics Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in
  • F frama-c
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributor statistics
    • Graph
    • Compare revisions
  • Issues 168
    • Issues 168
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 0
    • Merge requests 0
  • Deployments
    • Deployments
    • Releases
  • Packages and registries
    • Packages and registries
    • Container Registry
    • Model experiments
  • Monitor
    • Monitor
    • Incidents
  • Analytics
    • Analytics
    • Value stream
    • Repository
  • Wiki
    • Wiki
  • Activity
  • Graph
  • Create a new issue
  • Commits
  • Issue Boards
Collapse sidebar
  • pub
  • frama-c
  • Issues
  • #907
Closed
Open
Issue created Jan 12, 2015 by Jochen Burghardt@burghardt

axiom "addr_le_def" given to Alt-Ergo considered too weak

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
  • fill_loop_inv_xx5_preserved_Alt-Ergo.mlw
  • fill.c
  • fill4.c
  • fill5.c
  • fill4r.c
  • find_arr.c
  • find_ptr.c
  • find_ptr_foo_post_Alt-Ergo_modified.mlw
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information
Assignee
Assign to
Time tracking