The old version was unnecessarily convoluted, and had a bug that caused
invalid iterators to be dereferenced in some corner cases.
This commit reworks the DFS and makes it cleaner and easier to follow,
while fixing the iterator dereference bug.
The DLAStep SimplifyInstanceAtOffset0 now only triggers if the parent
node has the child-at-offset-0 node as its only successor, or when the
child-at-offset-0 doesn't have other predecessors.
Doing this guarantees that it's impossible for another predecessor of
the child-at-offset-0 to start seeing memory accesses that were
initially relative to the parent.
This condition is slightly more restrictive than the previous one, but
it takes into consideration some far reaching consequences.
If SimplifyInstanceAtOffset0 aggressively like we did before, DLA can
end up inferring types in some memory locations, like executable
segments, for which there aren't clues in the binary.
This isn't bad per se, but if DLA does that, the newly recovered type is
identified as non-executable data, causing misdecompilation because
rev.ng doesn't decompile memory regions that it understands as non
executable.
This commit, making SimplifyInstanceAtOffset0 less aggressive, makes it
play better with the rest of the assumptions of the decompilation
pipeline.
It also relaxes a decompilation test that was previously working by
chance and that was effectively beyond the current expressive power of
reasoning for DLA at the moment.
Before this commit the breadth-first traversal was more convoluted and
it used a broken criterion for bailing out, resulting sometimes in
considering a pointer edge as if it was an instance edge.
This in turn caused bugs to the point of the DLA Graph failing
verification.
This commit rewrites and simplifies the main traversal and comparisons
in DeduplicateField to make them robust against these bugs.
Before this commit the code was wrong in 2 ways:
- if failed to iterate on children, because it iterated a range that was
effectively [begin, begin) instead of [begin, end)
- the update of the ARootNext iterator in the loop was broken, but it
was impossible to realize that since the loop was never taken
This commit fixes both these intertwined problems.
Before this commit, the DLAStep MergePointeesOfPointerUnion wasn't
really equipped for dealing with LayoutTypeSystemNodes representing
types imported from Model.
There was some code that tried to deal with them but it was mostly an
afterthought and it wasn't robust.
This commit fixes that, and is able to handle a strict superset of the
scenarios envisioned before, while preserving the property that nodes
representing types imported from Model should be preserved (in
particular their size).
Before this commit, DLA didn't do any checks on the validity of the
model::PrimitiveTypes that it generated.
This could cause invalid PrimitiveTypes to be generated, with weird
sizes not supported by the Model.
This commit fixes this problem, generating empty model::StructTypes with
the proper sizes instead.
Before this commit, DLA's frontend was representing information about
string literals in a way that had a bad outcome: very often, all (or
most) places in the binary that were using string literals ended up
collapsed on the DLA graph on the same node, causing all their types to
be a weird struct.
This was wrong, and it was the result of an aggressive creation of
equality edges.
This commit avoids to emit equality edges, and replaces them with
instance edges, that represent the fact that a call to StringLiteral
actually returns a type that represents a pointer to char.
Before this commit, the method could partly fail in moving the edge
target even in legitimate scenarios, because of a bug in how it fixed up
the Successors link in the edge source.
This commit fixes the bug.
Now CompactCompatibleArrays runs after ArrangeAccessesHierarchically.
Rearranging the accesses hierarchically first allows the following step,
that compacts compatible arrays, to achieve better results, and overall
recover much better looking arrays.
This commit extends the CompactCompatibleArrays DLAStep to also consider
non-strided accesses.
Strided accesses are still always considered first, and they are still
considered the only real source of information on arrays, but after
having tried to compact all the compatible arrays,
CompactCompatibleArrays now also considers non-strided instance edges to
see if they can be compacted with the rest of the inferred array.
This has shown to handle gracefully a number of real-world examples and
reduce unions.
Before this commit, the CompactCompatibleArray DLAStep had that caused
the compaction to be sensible to the order of the pairs of edges that
were compacted, and that also caused the compaction operation to overrun
the end of the containing struct in some corner cases.
This commit fixes both bugs.
Now the compaction routine is not ordering-sensitive anymore.
For each pair of edges <A, B> to compact it tries to compact them in 2
possible ways: by aligning A to B shifting A to lower offsets, and by
aligning B to A shifting B to lower offsets.
If both succeed, it picks the best result among the two, which doesn't
depend on the ordering of A and B.
This fixes the order-sensitiveness.
While reworking this logic, the logic was fixed so that if any of the
two compaction attempts causes to overrun the end of the containing
struct, the attempt is not considered successful anymore, and it's
discarded altogether.
Alessandro Di Federico