runtimeverification / runtimeverification/haskell-backend

Cannot simplify proof dealing with indirect equalities

Open
#2,032 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

investigation
Dominant language
Haskell
Stars
224
Forks
43
PR merge metrics
No merged PRs in 30d

Description

I have a module where I want to assert things about a Map in the pre-condition, and use that knowledge to check a post condition. Attached is the generated bug report. This example comes from porting the benchmark proofs of KEVM over to the Haskell backend. Here is the K definition:

module TEST
    imports DOMAINS

    configuration
        <k> $PGM:Foo </k>
        <mem> .Map </mem>

    syntax Foo ::= doIt ( Int , Int )
    rule <k> doIt(K, V) => . ... </k>
         <mem> M => M [ K <- V +Int #lookup(M, K) ] </mem>

    syntax Int ::= #lookup ( Map , Int ) [function, functional, smtlib(lookup)]
 // ---------------------------------------------------------------------------
    rule #lookup( (KEY |-> VAL:Int) _M , KEY ) => VAL modInt 256
    rule #lookup(                    M , KEY ) => 0              requires notBool KEY in_keys(M)
    rule #lookup( (KEY |-> VAL    ) _M , KEY ) => 0              requires notBool isInt(VAL)

endmodule

And the specification module:

requires "test.k"
 
module TEST-SPEC
    imports TEST

    rule <k> doIt(K, V1) => . ... </k>
         <mem> S => S [ K <- ?V3 ] </mem>
      requires 0 <=Int V1 andBool V1 <Int 256
       andBool #lookup(S, K) ==Int V2
       andBool 0 <=Int V2 andBool V2 <Int 256
       andBool 0 <=Int V2 +Int V1 andBool V2 +Int V1 <Int 256

       ensures ?V3 ==Int V2 +Int V1
endmodule

In the output counterexample, I get this clause in the side-condition (i):

  #Not ( #Exists ?V3 . {
      ?V3 ==Int V2 +Int V1
    #Equals
      true
    }
  #And
    {
      S [ K:Int <- V1 +Int #lookup ( S , K ) ]
    #Equals
      S [ K:Int <- ?V3:Int ]
    } )

But we also have in the path condition (ii):

  {
    true
  #Equals
    #lookup ( S , K ) ==Int V2
  }

So it should be able to simplify (i) using (ii) to see that it's infeasible, and prune this branch, is my thinking.

Here is the generated bug report: test.tar.gz

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the attached test.tar.gz bug report and the TEST and TEST-SPEC definitions, then inspect the generated counterexample's side-condition (i) alongside path condition (ii). Reproduce the indirect-equality case and determine whether simplification can use the #lookup equality to prune the branch; done means the infeasible branch is simplified away.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
backend
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.