Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[Pattern independent restructuring] 'NoneType' object is not iterable #213

Open
NeoQuix opened this issue Apr 6, 2023 · 4 comments
Open

[Pattern independent restructuring] 'NoneType' object is not iterable #213

NeoQuix opened this issue Apr 6, 2023 · 4 comments
Labels
bug Something isn't working priority-high High priority issue

Comments

@NeoQuix
Copy link
Collaborator

NeoQuix commented Apr 6, 2023

What happened?

Error in bin/refsutil.exe in 0x1400ba588
[pipeline.py:107 run()] ERROR - Failed to decompile ?MapView@@YAEPEAU_MscFileObject@@PEAT_LARGE_INTEGER@@KKPEAEPEAPEAX3@Z, error during stage pattern-independent-restructuring: 'NoneType' object is not iterable
Traceback (most recent call last):
  File "/home/neoquix/Git-Repos/DeWolf/decompile.py", line 76, in <module>
    main(Decompiler)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/util/commandline.py", line 80, in main
    task = decompiler.decompile(function_name, options)
  File "/home/neoquix/Git-Repos/DeWolf/decompile.py", line 51, in decompile
    pipeline.run(task)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/pipeline.py", line 109, in run
    raise e
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/pipeline.py", line 102, in run
    instance.run(task)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/controlflowanalysis/restructuring.py", line 45, in run
    self.restructure_cfg()
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/controlflowanalysis/restructuring.py", line 81, in restructure_cfg
    AcyclicRegionRestructurer(self.t_cfg, self.asforest).restructure()
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/controlflowanalysis/restructuring_commons/acyclic_restructuring.py", line 44, in restructure
    self._construct_ast_for_region(restructurable_region, node)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/controlflowanalysis/restructuring_commons/acyclic_restructuring.py", line 69, in _construct_ast_for_region
    restructured_region_root = self._construct_refined_ast(seq_node)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/controlflowanalysis/restructuring_commons/acyclic_restructuring.py", line 92, in _construct_refined_ast
    ConditionBasedRefinement.refine(self.asforest)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/controlflowanalysis/restructuring_commons/condition_based_refinement.py", line 35, in refine
    if_refinement._condition_based_refinement()
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/controlflowanalysis/restructuring_commons/condition_based_refinement.py", line 51, in _condition_based_refinement
    newly_added_sequence_nodes = self._structure_sequence_node(seq_node)
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/pipeline/controlflowanalysis/restructuring_commons/condition_based_refinement.py", line 95, in _structure_sequence_node
    for child in list(sequence_node.children):
  File "/home/neoquix/Git-Repos/DeWolf/decompiler/structures/ast/ast_nodes.py", line 274, in children
    if set(self._sorted_children) != set(children):
TypeError: 'NoneType' object is not iterable

How to reproduce?

Decompile refsutil at 0x1400ba588.

Affected Binary Ninja Version(s)

3.3.3996
@NeoQuix NeoQuix added bug Something isn't working priority-high High priority issue labels Apr 6, 2023
@NeoQuix
Copy link
Collaborator Author

NeoQuix commented Apr 12, 2023

Again as in #189, SeqNode has None type as children field because of NetworkXUnfeasible in reachability_graph.py L.93, caused by sequence_node._sorted_children = sibling_reachability.sorted_nodes() in condition_based_refinement.py L.79.

Wasn't the fix, that the networkx error should not result in the first place?
Maybe instead of returning None, simply crash with an error.

@ebehner
Copy link
Collaborator

ebehner commented Apr 21, 2023

I found the transformation after which we can not sort the children anymore.
However, the problem behind this seems to be more complicated.

We do an "invalid" transformation in

dewolf/decompiler/pipeline/controlflowanalysis/restructuring_commons/ast_processor.py

Line 146 in bdb0eac

self._extract_conditional_returns()
.
More precisely, in this function we search for a condition node cn with two branches tb and fb, where exactly one ends with a return statement. For simplicity, let the true branch tb end with a return. Then we extract the false-branch fb from the condition node and make sure that the condition node, now only having the true branch, is executed before the false-branch child. We do this by updating the reachability of the code-nodes.
In general, this is no problem, because nodes with opposite conditions can not reach each other. However, in this sample, all code nodes that are contained in the false-branch reach the once in the true-branch, thus after the extraction, we add that all code nodes contained in the true-branch reach the once in the false-branch.

One solution would be to remove the reachability between the code-nodes of the true and false branch of a condition node. These should never be able to reach each other.

However, something like this should not happen, and it happens in this sample only because the SSA-form seems to be incorrect. The condition *var_0 == 0 occurs three times, where var_0 has the same SSA-value rbx#4 in all cases, but the value *var_0 changes once. We do not capture this with the SSA-form. Thus, to give all three conditions the same symbol is false.

For reference, the initial cfg after the lifting
start_cfg

and the cfg before the restructuring
cfg

How do we want to solve this?

@ebehner
Copy link
Collaborator

ebehner commented Apr 27, 2023

  • Add memory version to conditions
  • for dereference and function calls check also the memory-version for symbols.

@ebehner ebehner removed their assignment Apr 28, 2023
@mm4rks
Copy link
Collaborator

mm4rks commented Sep 17, 2023 •
edited
Loading

duplicate with minimal sample #337

@mm4rks mm4rks mentioned this issue Sep 17, 2023
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working priority-high High priority issue
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@ebehner @mm4rks @NeoQuix