Skip to content

Commit

Permalink
[Extended pipeline crash] Fix Non-deterministic error (#221)
Browse files Browse the repository at this point in the history 
* Check if there is change by alias between def and use when propagating postponed aliased

---------
Co-authored-by: mari-mari <[email protected]>
Co-authored-by: Mariia Rybalka <[email protected]>
Co-authored-by: mari-mari <[email protected]>
Co-authored-by: Steffen Enders <[email protected]>
  • Loading branch information
@github-actions
github-actions[bot] authored Apr 27, 2023
1 parent e99a805 commit 546b31e
Show file tree
Hide file tree
Showing 2 changed files with 129 additions and 15 deletions.
38 changes: 23 additions & 15 deletions decompiler/pipeline/dataflowanalysis/expressionpropagationmemory.py
View file
Original file line number Diff line number Diff line change
Expand Up @@ -23,7 +23,7 @@ def run(self, task: DecompilerTask):

def perform(self, graph, iteration) -> bool:
"""
After performing normal propagation round, check if postponed aliased can be propagated
After performing normal propagation round, check if postponed aliased can be propagated.
"""
is_changed = super().perform(graph, iteration)
self._propagate_postponed_aliased_definitions()
Expand All @@ -47,20 +47,17 @@ def _definition_can_be_propagated_into_target(self, definition: Assignment, targ
:return: true if propagation is allowed false otherwise
"""
return isinstance(definition, Assignment) and not (
self._is_phi(definition)
or self._is_call_assignment(definition)
or self._is_address_into_dereference(definition, target)
or self._defines_unknown_expression(definition)
or self._contains_global_variable(definition)
or self._operation_is_propagated_in_phi(target, definition)
or self._is_invalid_propagation_into_address_operation(target, definition)
or self._resulting_instruction_is_too_long(target, definition)
or self._is_aliased_postponed_for_propagation(target, definition)
or self._definition_value_could_be_modified_via_memory_access_between_definition_and_target(definition,
target)
or self._pointer_value_used_in_definition_could_be_modified_via_memory_access_between_definition_and_target(
definition, target
)
self._is_phi(definition)
or self._is_call_assignment(definition)
or self._is_address_into_dereference(definition, target)
or self._defines_unknown_expression(definition)
or self._contains_global_variable(definition)
or self._operation_is_propagated_in_phi(target, definition)
or self._is_invalid_propagation_into_address_operation(target, definition)
or self._resulting_instruction_is_too_long(target, definition)
or self._is_aliased_postponed_for_propagation(target, definition)
or self._definition_value_could_be_modified_via_memory_access_between_definition_and_target(definition, target)
or self._pointer_value_used_in_definition_could_be_modified_via_memory_access_between_definition_and_target(definition, target)
)

def _initialize_pointers(self, cfg: ControlFlowGraph):
Expand Down Expand Up @@ -90,14 +87,25 @@ def _update_use_map(self, variable: Variable, instruction: Instruction):
def _propagate_postponed_aliased_definitions(self):
"""
Propagate definitions of aliased variables, postponed for propagation, after everything else is propagated.
Check before propagation, if there are no changes via aliases between definition and use.
See _is_aliased_postponed_for_propagation method definition for an example why we do not propagate such definitions immediately.
"""
self._initialize_maps(self._cfg)
for var in self._postponed_aliased:
uses = self._use_map.get(var)
definition = self._def_map.get(var)

if len(uses) == 1:
instruction = uses.pop()
if self._is_aliased_postponed_for_propagation(instruction, definition):
if self._definition_value_could_be_modified_via_memory_access_between_definition_and_target(
definition, instruction
) or self._pointer_value_used_in_definition_could_be_modified_via_memory_access_between_definition_and_target(
definition, instruction
):
continue
old_instr = str(instruction)
block, index = self._blocks_map.get(old_instr).pop()
instruction.substitute(var, definition.value.copy())
self._update_use_map(var, instruction)
self._update_block_map(old_instr, str(instruction), block, index)
106 changes: 106 additions & 0 deletions tests/pipeline/dataflowanalysis/test_expression_propagation_mem.py
View file
Original file line number Diff line number Diff line change
Expand Up @@ -22,6 +22,112 @@
int32 = Integer.int32_t()
int64 = Integer.int64_t()


def test_postponed_aliased_propagation_handles_aliases_correctly():
"""
+--------------------------------+
| 0. |
| var_18#1 = var_18#0 |
| func() |
| var_18#2 = var_18#1 |
| var_28#1 = &(var_18#2) |
| scanf(var_28#1) |
| var_18#3 -> var_18#2 |
| eax#1 = var_18#3 |
| var_14#4 = eax#1 |<--------var_14 is now an alias of var_18
| func() |
| var_18#4 = var_18#3 |
| var_10#1 = &(var_18#4) |
| *(var_10#1) = 0x7 |<--------var_18 is changed via deref, so does var_14, since they are aliases
| var_18#5 -> var_18#4 |
| var_14#5 = var_14#4 |<--------do not propagate old value of var_14 here, cause of change above
| eax_2#3 = var_18#5 |
| return (&(var_14#5)) + eax_2#3 |
+--------------------------------+
+---------------------------------+
| 0. |
| var_18#1 = var_18#0 |
| func() |
| var_18#2 = var_18#0 |
| var_28#1 = &(var_18#2) |
| scanf(&(var_18#2)) |
| var_18#3 -> var_18#2 |
| eax#1 = var_18#3 |
| var_14#4 = var_18#3 |
| func() |
| var_18#4 = var_18#3 |
| var_10#1 = &(var_18#4) |
| *(var_10#1) = 0x7 |
| var_18#5 -> var_18#4 |
| var_14#5 = var_14#4 |<--------this instruction should not be changed after epm
| eax_2#3 = var_18#5 |
| return (&(var_14#5)) + var_18#5 |
+---------------------------------+
"""
input_cfg, output_cfg = graphs_with_aliases()
_run_expression_propagation(input_cfg)
assert _graphs_equal(input_cfg, output_cfg)


def graphs_with_aliases():

var_18 = vars("var_18", 6, aliased=True)
var_14 = vars("var_14", 6, aliased=True)
var_28 = vars("var_28", 2, type=Pointer(int32))
var_10 = vars("var_10", 2, type=Pointer(int32))
eax = vars("eax", 2)
eax_2 = vars("eax_2", 4)
c = const(8)

in_n0 = BasicBlock(
0,
[_assign(var_18[1], var_18[0]),
_call("func", [], []),
_assign(var_18[2], var_18[1]),
_assign(var_28[1], _addr(var_18[2])),
_call("scanf", [], [var_28[1]]),
Relation(var_18[3], var_18[2]),
_assign(eax[1], var_18[3]),
_assign(var_14[4], eax[1]),
_call("func", [], []),
_assign(var_18[4], var_18[3]),
_assign(var_10[1], _addr(var_18[4])),
_assign(_deref(var_10[1]), c[7]),
Relation(var_18[5], var_18[4]),
_assign(var_14[5], var_14[4]),
_assign(eax_2[3], var_18[5]),
_ret(_add(_addr(var_14[5]), eax_2[3]))
]
)
in_cfg = ControlFlowGraph()
in_cfg.add_node(in_n0)
out_cfg = ControlFlowGraph()
out_cfg.add_node(
BasicBlock(
0,
[_assign(var_18[1], var_18[0]),
_call("func", [], []),
_assign(var_18[2], var_18[0]),
_assign(var_28[1], _addr(var_18[2])),
_call("scanf", [], [_addr(var_18[2])]),
Relation(var_18[3], var_18[2]),
_assign(eax[1], var_18[3]),
_assign(var_14[4], var_18[3]),
_call("func", [], []),
_assign(var_18[4], var_18[3]),
_assign(var_10[1], _addr(var_18[4])),
_assign(_deref(var_10[1]), c[7]),
Relation(var_18[5], var_18[4]),
_assign(var_14[5], var_14[4]),
_assign(eax_2[3], var_18[5]),
_ret(_add(_addr(var_14[5]), var_18[5]))
]
)
)
return in_cfg, out_cfg


def test_address_propagation_does_not_break_relations_between_aliased_versions():
"""
+------------------+
Expand Down

0 comments on commit 546b31e

Please sign in to comment.