Skip to content

DefExc: Define widen by join.#97

Merged
michael-schwarz merged 3 commits intomasterfrom
def_exc_join
Sep 14, 2020
Merged

DefExc: Define widen by join.#97
michael-schwarz merged 3 commits intomasterfrom
def_exc_join

Conversation

@jerhard
Copy link
Copy Markdown
Member

@jerhard jerhard commented Sep 11, 2020

Previously, DefExc used the widening operator as implemented by Lattice.StdCousot -- which is not a valid widening operator (as of now), because it just returns the second argument:

module StdCousot =
struct
let widen x y = y
let narrow x y = x
end

So now we define the widen simply by the join for DefExc.

More generally speaking, there are 16 includes of StdCousot in the code base (not counting those in arrayDomain_deprecated and intDomain_unused). At some of these places, the widen might not be overridden and the resulting behavior might be unsound.

Previously, DefExc used the widening operator as implemented by
Lattice.StdCousot -- which is not a valid widening operator (as of now),
because if it just returns the second argument.
@jerhard
Copy link
Copy Markdown
Member Author

jerhard commented Sep 11, 2020

We maybe should consider to simply remove widen from Lattice.StdCousot, as to be sound, it would either have to rely on a passed join operator (given that our domains only have finite ascending chains), or always would have to return top.

@vogler
Copy link
Copy Markdown
Collaborator

vogler commented Sep 11, 2020

Searching for S.Dom.widen, the only place where we don't do S.Dom.widen old (S.Dom.join old tmp) in the solver seems to be this:

if HM.mem globals x then S.Dom.widen old tmp

So, as it's used currently, it shouldn't be unsound (except for slr3 maybe).

We should probably just remove StdCousot alltogether. In order to replace widen with let widen = B.join, it'd need to be functorized.

There are not really any good default implementations for narrowing
and (in particular) for widening that can be defined by a module.
@jerhard
Copy link
Copy Markdown
Member Author

jerhard commented Sep 11, 2020

I tried to remove StdCousot here, but somehow it makes test 09/03 fail, because some races are not detected anymore.

…/ narrow

If something includes another domain and then redefines join (meet), widen (narrow) needs to be redefined as well
@jerhard
Copy link
Copy Markdown
Member Author

jerhard commented Sep 14, 2020

Ok, now that @michael-schwarz fixed it, should we just merge this?

@michael-schwarz michael-schwarz merged commit 3d3e37f into master Sep 14, 2020
@michael-schwarz michael-schwarz deleted the def_exc_join branch September 14, 2020 11:17
@michael-schwarz
Copy link
Copy Markdown
Member

Apparently this behavior was intended and the solvers are written in a way such that they always did a join, before calling widen (as Ralf mentioned above).
However, in today's Gobcon the consensus was that this should be abandoned and that every domain needs to specify widen in a way s.t. join a b \leq widen a b.

michael-schwarz added a commit that referenced this pull request Oct 1, 2020
This was erroneously changed to `narrow = meet` in #97
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants