runtimeverification / runtimeverification/mir-semantics

#switchMatch function causes invalid branches

Open
#622 2 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Python
Stars
52
Forks
5
PR merge metrics
No merged PRs in 30d

Description

The #switchMatch function used in the implementation of SwitchInt (via selectBlock):

  syntax Bool ::= #switchMatch   ( MIRInt , TypedValue ) [function]

  rule #switchMatch(0, typedValue(BoolVal(B)           , _, _)) => notBool B
  rule #switchMatch(1, typedValue(BoolVal(B)           , _, _)) => B
  rule #switchMatch(I, typedValue(Integer(I2, WIDTH, _), _, _)) => I ==Int bitRangeInt(I2, 0, WIDTH)

There are two potential problems:

  • (minor) the symbolic backend does not have a bitRangeInt hook. We should use truncate instead, which is a simple bitmask here (result is unsigned).
  • (major) The way it is defined allows #switchMatch to yield true for more than one case, e.g. #switchMatch(0, <expression>) and #switchMatch(1, <expression>) can both be in the same path condition (This has been observed in symbolic execution traces). This is conceptually not possible, at most one instance for the 1st argument may yield true for the same <expression> as the 2nd argument.
    The second issue is particularly relevant in interaction with #lookupDiscriminant

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 at the #switchMatch definition used by SwitchInt through selectBlock, and inspect how it interacts with #lookupDiscriminant in symbolic execution traces. Check the existing bitRangeInt usage and symbolic backend support; done means truncation is supported there and one expression cannot make multiple switch branches true on the same path.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
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.