runtimeverification / runtimeverification/haskell-backend

Unsound rewrite when using requires with partial functions

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

Nobody has claimed this yet.

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

Description

versions:

$ kompile --version
K version:    v5.6.122-0-g77b76f004a-dirty
Build date:   Thu Jun 08 22:29:39 EEST 2023

$ kore-exec --version
Kore version 0.60.0.0
Git:
  revision:     f7a90ba41aa98d79f400099e2a27156e07543540
  branch:       HEAD
  last commit:  Fri May 5 08:23:49 2023 -0600

To reproduce:
a.k

module A
  imports INT
  imports BOOL

  syntax KItem ::= "a"
  rule I:Int => a requires 10 /Int I <Int 0
  rule I:Int => a requires 10 /Int I >=Int 0
endmodule

spec.k

module SPEC
  imports A
  claim _Value:Int => a
endmodule

Command line:

$ kompile a.k --backend haskell && kprove spec.k

The proof passes, although the claim should fail when _Value is 0.

Note that the Haskell backend sends partial functions to z3 (i.e. it sends things like 10 /Int I < 0) without attempting to translate them properly - I think that Z3 division is undefined in the sense that it can be ANY value, while the K division is undefined in the sense that it has NO value.

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 by reproducing the issue with a.k, spec.k, kompile a.k --backend haskell, and kprove spec.k. Then inspect the Haskell backend's handling of partial functions sent to Z3 and compare it with K's undefined-function semantics. Done means the claim no longer passes for the value 0 and the behavior is covered by a regression test.

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
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.