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.

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

fixes the subroutine ordering in the run plugin #1011

Merged
merged 1 commit into from
Nov 8, 2019

Conversation

gitoleg
Copy link
Contributor

@gitoleg gitoleg commented Nov 7, 2019

When run-entry-points is set to all-subroutines, we launch all the subroutines in the topological order. The problem is that if a real callgraph doesn't have a common entry from which all subroutines
are reachable, but instead is represented as a few spanning trees, then the reverse postorder traverse of a graph will produce an ordering that is far from the topological. We address this issue by connecting roots of all trees to an artificial entry point before sorting.

Skip visited

A bonus feature is a new command line option to the run plugin that when set (on by default) will not revisit a subroutine if it was already visited. This is only applicable when a set of entry points
(or all entry points) were specified to the run plugin, and it investigates each in separate.

The justification for this behavior is that if we already had visited a subroutine, then we entered it through some other subroutine, i.e., we investigated it under a richer context, so there is no need to call it directly. Of course, this is a heuristic, so it can be disabled:

bap /bin/echo --run-entry-points=all-subroutines --run-with-repetitions

When `run-entry-points` is set to `all-subroutines`, we launch
all the subroutines in the topological order. The problem is that if a
real callgraph doesn't have a common entry from which all subroutines
are reachable, but instead is represented as a few spanning trees, then
the reverse postorder traverse of a graph will produce an ordering that
is far from the topological. We address this issue by connecting roots
of all trees to an artificial entry point before sorting.

Skip visited

A bonus feature is a new command line option to the run plugin that when
set (on by default) will not revisit a subroutine if it was already
visited. This is only applicable when a set of entry points
(or all entry points) were specified to the run plugin, and it
investigates each in separate.

The justification for this behavior, is that if we already had visited a
subroutine, then we entered it through some other subroutine, i.e., we
investigated it under a richer context, so there is no need to call it
directly. Of course, this is a heuristic,  so it can be disabled:
```
bap /bin/echo --run-entry-points=all-subroutines --run-with-repetitions
```
@gitoleg gitoleg merged commit 0479c6e into BinaryAnalysisPlatform:master Nov 8, 2019
@gitoleg gitoleg deleted the fix-run-sorting branch May 13, 2020 21:11
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.

2 participants