fixes the bug that was producing unreachable blocks #856
Conversation
Some significant problems can happen if one of our rooters give us some wrong roots. We can even miss instructions and build a wrong cfg. So this PR removes wrong roots on the early stages of the disassembler, so they don't influence of the late ones.
ivg
left a comment
ivg
left a comment
There was a problem hiding this comment.
the proposed algorithm looks insufficient and it will still allow invalid roots to pass through the stage1.
Why can't we just after stage 1 is completed remove all initial roots that didn't prove to be valid?
Also, does this removal play nice with the case when we have several code segments?
lib/bap_disasm/bap_disasm_rec.ml
Outdated
| addr : addr; | ||
| visited : Span.t; | ||
| visited : Span.t; | ||
| insns : Addr.Set.t; |
There was a problem hiding this comment.
misleading name, let's name it valid instead
lib/bap_disasm/bap_disasm_rec.ml
Outdated
| | r :: roots when Span.mem s.visited r -> | ||
| loop {s with roots} | ||
| if Set.mem s.insns r then loop {s with roots} | ||
| else loop {s with roots; inits = Set.remove s.inits r} |
There was a problem hiding this comment.
This code will remove an invalid root only in case if we have discovered that it is invalid before we extract it from the worklist. Since the worklist is an unordered sequence, this won't work in general.
|
speaking about several segments case, this removal plays nice, just because the roots from other segment are not taking in account even without these changes. |
ivg
changed the title
2 participants
The root of the problem was the rooter, which was producing roots that were pointing in the middle of an instruction. Since the disassembler was cutting a block on the start of each root this led to an incorrect CFG with non-connected components.
It's fine for a rooter to produce such garbage, however, the disassembler shall not take rooter's output as granted. The new implementation keeps track of the set of addresses that start valid instructions and once this set is fully discovered removes those roots that do not belong to this set.