runtimeverification / runtimeverification/mir-semantics
#switchMatch function causes invalid branches
Open
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
bitRangeInthook. We should usetruncateinstead, which is a simple bitmask here (result is unsigned). - (major) The way it is defined allows
#switchMatchto yieldtruefor 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 yieldtruefor 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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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