Fun with graphs

So I figured that I would post some of the progress with EDB. I’ve been very happy with the function analysis engine that I developed, but there is one thing that it completely ignores, basic block analysis. Of course in order to identify functions it does technically break things down into blocks, but this information is discarded when a whole function is identified.

The main reason for this is that I had no real practical way to display this information in a useful way to users. A list of blocks wouldn’t do, there would simply be to many for anyone to make sense of them. Some other tools have a nice solution though…graphs :).

So I figured that it’s time EDB got a graphing plugin of sorts. And that’s where my focus has been lately. Finally after playing with the awesome QGraphicsView API, I have some results that are worth noting.

edb_graph1

As you can see, it is looking pretty nice. All of the nodes are draggable so if you don’t like how it is layed out, you can adjust it. Of course it isn’t quite ready yet, otherwise I would have just tossed it into EDB and bumped the version. There are two major things I need to figure out.

  1. How big do I make the whole scene? Right now I just go with “very big”, but eventually, I’ll have to figure this out based on the content. This is very dependant on issue #2 though…
  2. I have no automatic layout engine. Currently in my test code, I’ve manually placed each node. This is likely to prove very difficult, but I’ll get there (Obviously if any graph experts out there want to help, feel free to email me ;-)).

Beyond that, I’m feeling pretty good about how it works.

You may be wondering why I didn’t just use GraphViz. Well, to be honest, I looked into it. But there didn’t seem to be any nice and simple way to get the results into a Qt widget. As far as I can tell, the API revolves around programatically generating a .dot file, and sending that through one of the graphviz renderer’s. Then taking the output file and finally displaying it. I don’t like all the temporary files and the dependency on external programs. I’m not a fan of “front-ends” in general, otherwise EDB would just be another GDB front end.

Though if I could do a pure library solution, I could work with the temporary files. Obviously I could have missed something in graphviz, if so, let me know :).

I hope to have things nice and ready for release soon.

5 thoughts on “Fun with graphs

  1. WRS

    You probably already knew this, but the whole layout thing you’re talking about is called graph drawing… it’s a whole field of graph theory: http://en.wikipedia.org/wiki/Graph_drawing.

    I had a professor Greg Fredrickson who has done work in this area. You might want to search for graph drawing and his name. You’ll get things like this: http://www.cs.purdue.edu/research/technical_reports/1991/TR%2091-070.pdf

    Good luck trying to actually implement these academic papers :-)

  2. Matheus Izvekov

    Congratulations! Pretty impressive! Been interested in a linux debugger inspired in ollydbg since my first day with gdb :)
    Too bad I can’t test it, it segfaults when I press ok when it’s about to create a configuration file. I’ll try to figure out why later.

    Btw I am also interested in your playstation emulator. I authored a ps1 emulator myself. It’s currently unreleased, but it’s gonna be GPLv2. It already runs 90% of games, and has hle bios emulation which runs 99% of those 90%. Problem is, it’s currently 100% written in C99. I’ve tried to keep things simple, but i have so many ideas and C’s lack of templates and of at least some primitive object orientation keeps holding me back. One of my design objectives is keeping the source small and clean, with maximum code reuse as feasible. I plan on switching to C++, at least partially. And i would really love to see your code for fakestation. If you are interested in seeing my code or in cooperating I would be glad if you would contact me! I tried and failed to find your email to send this message. But now hopefully you have mine ;)

    PS: Much thanks for your good work!

  3. Jeremy

    Just for to tell you that EDB is a fucking good soft for Engineering Reverser but (there is always a “BUT”), you should implement a plugin to “search opcodes” from the beginning of the binary execution” + unlock the scrollbar to see the ASM instructions farther in the pasts + A plugin wich helps everybody -> POSSIBILITY to check What functions called What Data in DATA dump :)

    + gimme your mail :P

    bye,

  4. Evan Teran Post author

    @Jeremy, glad you like it! I’ll definitely try to implement your suggestions. One thing that i need to implementing for that is a more robust opcode comparison system. Since there are redundant encodings in x86/x86-64, plus I’d like to allow for generics in the comparison as well (like “mov [reg32], 1″ would find any 32-bit register being set to 1 with a mov. In addition I’ll need to finish the assembler so that you can search for an arbitrary opcode, not just a few from a list. I like your other ideas too. I’ll be adding them all to my todo list ;).

    As for my email, you can find it on the main codef00.com page at the bottom, but i’ll put it here too:

    eteran [at] alum [dot] rit [dot] edu

  5. p1n00n3

    Your debugger is awesome. I’m new to the reverse engineering camp and I was very sad with the quality of tools in the Linux OS for that task until I ran into your tool. Thanks a lot for your awesome work.

    p

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>