runtimeverification / runtimeverification/haskell-backend
`get_model` returns SAT for UNSAT input
Nobody has claimed this yet.
- Dominant language
- Haskell
- Stars
- 224
- Forks
- 43
- PR merge metrics
- No merged PRs in 30d
Description
I ran into a problem in pyk when calling cterm_get_model, in that I am getting SAT back where I would expect UNSAT. The CTerm in question is:
CTerm(config=KApply(label=KLabel(name='<generatedTop>', params=()), args=(KApply(label=KLabel(name='<T>', params=()), args=(KApply(label=KLabel(name='<k>', params=()), args=(KVariable(name='K_CELL', sort=None),)), KApply(label=KLabel(name='<state>', params=()), args=(KVariable(name='STATE_CELL', sort=None),)))), KApply(label=KLabel(name='<generatedCounter>', params=()), args=(KVariable(name='GENERATEDCOUNTER_CELL', sort=None),)))), constraints=(KApply(label=KLabel(name='#Equals', params=(KSort(name='Bool'), KSort(name='GeneratedTopCell'))), args=(KToken(token='true', sort=KSort(name='Bool')), KApply(label=KLabel(name='_<Int_', params=()), args=(KVariable(name='N', sort=KSort(name='Int')), KToken(token='15', sort=KSort(name='Int')))))), KApply(label=KLabel(name='#Equals', params=(KSort(name='Bool'), KSort(name='GeneratedTopCell'))), args=(KToken(token='true', sort=KSort(name='Bool')), KApply(label=KLabel(name='_>Int_', params=()), args=(KVariable(name='N', sort=KSort(name='Int')), KToken(token='10', sort=KSort(name='Int')))))), KApply(label=KLabel(name='#Equals', params=(KSort(name='Bool'), KSort(name='GeneratedTopCell'))), args=(KToken(token='true', sort=KSort(name='Bool')), KApply(label=KLabel(name='notBool_', params=()), args=(KApply(label=KLabel(name='_andBool_', params=()), args=(KApply(label=KLabel(name='_==K_', params=()), args=(KSequence(items=()), KSequence(items=()))), KApply(label=KLabel(name='_==K_', params=()), args=(KApply(label=KLabel(name='_|->_', params=()), args=(KToken(token='$n', sort=KSort(name='Id')), KApply(label=KLabel(name='_+Int_', params=()), args=(KVariable(name='N', sort=KSort(name='Int')), KVariable(name='N', sort=KSort(name='Int')))))), KApply(label=KLabel(name='_|->_', params=()), args=(KToken(token='$n', sort=KSort(name='Id')), KApply(label=KLabel(name='_*Int_', params=()), args=(KToken(token='2', sort=KSort(name='Int')), KVariable(name='N', sort=KSort(name='Int')))))))))),))))))
or in kore:
And(sort=SortApp(name='SortGeneratedTopCell', sorts=()), left=App(symbol="Lbl'-LT-'generatedTop'-GT-'", sorts=(), args=(App(symbol="Lbl'-LT-'T'-GT-'", sorts=(), args=(App(symbol="Lbl'-LT-'k'-GT-'", sorts=(), args=(EVar(name="VarK'Unds'CELL", sort=SortApp(name='SortK', sorts=())),)), App(symbol="Lbl'-LT-'state'-GT-'", sorts=(), args=(EVar(name="VarSTATE'Unds'CELL", sort=SortApp(name='SortMap', sorts=())),)))), App(symbol="Lbl'-LT-'generatedCounter'-GT-'", sorts=(), args=(EVar(name="VarGENERATEDCOUNTER'Unds'CELL", sort=SortApp(name='SortInt', sorts=())),)))), right=And(sort=SortApp(name='SortGeneratedTopCell', sorts=()), left=Equals(op_sort=SortApp(name='SortBool', sorts=()), sort=SortApp(name='SortGeneratedTopCell', sorts=()), left=DV(sort=SortApp(name='SortBool', sorts=()), value=String(value='true')), right=App(symbol="Lbl'Unds-LT-'Int'Unds'", sorts=(), args=(EVar(name='VarN', sort=SortApp(name='SortInt', sorts=())), DV(sort=SortApp(name='SortInt', sorts=()), value=String(value='15'))))), right=And(sort=SortApp(name='SortGeneratedTopCell', sorts=()), left=Equals(op_sort=SortApp(name='SortBool', sorts=()), sort=SortApp(name='SortGeneratedTopCell', sorts=()), left=DV(sort=SortApp(name='SortBool', sorts=()), value=String(value='true')), right=App(symbol="Lbl'Unds-GT-'Int'Unds'", sorts=(), args=(EVar(name='VarN', sort=SortApp(name='SortInt', sorts=())), DV(sort=SortApp(name='SortInt', sorts=()), value=String(value='10'))))), right=Equals(op_sort=SortApp(name='SortBool', sorts=()), sort=SortApp(name='SortGeneratedTopCell', sorts=()), left=DV(sort=SortApp(name='SortBool', sorts=()), value=String(value='true')), right=App(symbol="LblnotBool'Unds'", sorts=(), args=(App(symbol="Lbl'Unds'andBool'Unds'", sorts=(), args=(App(symbol="Lbl'UndsEqlsEqls'K'Unds'", sorts=(), args=(App(symbol='dotk', sorts=(), args=()), App(symbol='dotk', sorts=(), args=()))), App(symbol="Lbl'UndsEqlsEqls'K'Unds'", sorts=(), args=(App(symbol='inj', sorts=(SortApp(name='SortMap', sorts=()), SortApp(name='SortK', sorts=())), args=(App(symbol="Lbl'UndsPipe'-'-GT-Unds'", sorts=(), args=(App(symbol='inj', sorts=(SortApp(name='SortId', sorts=()), SortApp(name='SortKItem', sorts=())), args=(DV(sort=SortApp(name='SortId', sorts=()), value=String(value='$n')),)), App(symbol='inj', sorts=(SortApp(name='SortInt', sorts=()), SortApp(name='SortKItem', sorts=())), args=(App(symbol="Lbl'UndsPlus'Int'Unds'", sorts=(), args=(EVar(name='VarN', sort=SortApp(name='SortInt', sorts=())), EVar(name='VarN', sort=SortApp(name='SortInt', sorts=())))),)))),)), App(symbol='inj', sorts=(SortApp(name='SortMap', sorts=()), SortApp(name='SortK', sorts=())), args=(App(symbol="Lbl'UndsPipe'-'-GT-Unds'", sorts=(), args=(App(symbol='inj', sorts=(SortApp(name='SortId', sorts=()), SortApp(name='SortKItem', sorts=())), args=(DV(sort=SortApp(name='SortId', sorts=()), value=String(value='$n')),)), App(symbol='inj', sorts=(SortApp(name='SortInt', sorts=()), SortApp(name='SortKItem', sorts=())), args=(App(symbol="Lbl'UndsStar'Int'Unds'", sorts=(), args=(DV(sort=SortApp(name='SortInt', sorts=()), value=String(value='2')), EVar(name='VarN', sort=SortApp(name='SortInt', sorts=())))),)))),)))))),))))))
or (somewhat) pretty-printed:
<generatedTop>
<T>
<k>
K_CELL
</k>
<state>
STATE_CELL
</state>
</T>
<generatedCounter>
GENERATEDCOUNTER_CELL
</generatedCounter>
</generatedTop>
#And { true #Equals N:Int <Int 15 }
#And { true #Equals N:Int >Int 10 }
#And { true #Equals notBool .K ==K .K andBool $n |-> N:Int +Int N:Int ==K $n |-> 2 *Int N:Int }
which is not satisfiable, since the third constraint does not hold (separately, the print is not correct, since notBool extends to both conjuncts (should be notBool ( .K ==K .K andBool $n |-> N:Int +Int N:Int ==K $n |-> 2 *Int N:Int )).
The substitution I get that supposedly satisfies this is N = 11.
Specifically, the call that is done is: result = kore_client.get_model(kore) where the kore holds the above kore term.
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
The reported entry point is kore_client.get_model(kore), using the supplied CTerm/KORE term as the reproduction. Start by tracing how that call handles the three constraints and compare its result with their satisfiability; done means the inconsistent term is reported as UNSAT and the noted pretty-printing issue is corrected.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell, python
- Domain
- api, backend
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100