Merged
Conversation
The dependencies are computed through a list of blocs (IRA). APIs `.get*` return an iterator on DiGraph(DependencyNode). Each DiGraph contains only relevant DependencyNode, which stand for an element at a given line in a given basic block. That way, outputs contain each elements involved in the target value computation. Different outputs stand for different path through blocks (loop, ...). This algorithm has been co-developped with @serpillere.
serpilliere
added a commit
that referenced
this pull request
Feb 20, 2015
Feature: dependency graphs
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Introduce
DependencyGraph, computing dependencies of elements.The dependencies are computed through a list of blocs (
IRA).APIs
.get*return an iterator onDependencyResult. Each one contains only relevantDependencyNode, which stand for an element at a given line in a given basic block. That way, outputs contain each elements involved in the targets' value computation.Different outputs stand for different path through blocks (loop, if-then-else statements, ...).
In addition, the
DependencyResultclass offers some API, such as:DiGraphoutputBy defining explicit dependencies as dependencies only involved by instruction semantics (unlike those involved by branching), the sub-algorithm
NoMemoryseems sound and complete.The standard one (best effort) suffers from memory aliases.
This algorithm has been co-developped with @serpilliere .
An example of use is joined to this PR, through an IDA plug-in.
For instance, the source code of
example/samples/simple_test.binis (example/samples/simple_test.c):Let's invoke the script on the

return ret;statement (offset 0x88).Once launch is pressed, a first path is highlight.

Line dependencies are added as comments (here the stack, and the constant
0x1003).In addition, on the console (we track
EAX):By pressing
Shift+N, one can get every solutions one after one:Regression tests are based on 10 graphs with different layout.