search

cea-sec / miasm

Reverse engineering framework in Python
https://miasm.re/
GNU General Public License v2.0
3.44k stars 471 forks source link

SSA naive back-translation algorithm produces incorrect results #823

Open rcx opened 6 years ago

rcx commented 6 years ago

Hi! I remember I saw your talk at defcon.

So, I decided to take a look at the SSA destruction algorithm, since you mentioned that was one of the weak points of the project.

https://github.com/cea-sec/miasm/blob/master/miasm2/analysis/ssa.py

The problem is that this naive translation in which all variables x_i in a phi node phi(x_1, x_2, x_3, etc. are replaced with a single variable, x, produces incorrect results in some situations. Two famous examples of this in literature are the "swap problem" and "lost copy problems". Here is a good source on it: https://www.inf.ed.ac.uk/teaching/courses/copt/lecture-4-from-ssa.pdf

For example, since the semantics of phi statements is that all phi statements in the basic block are executed simultaneously, you could have for example:

y_1 = phi(y_0, x_1)
x_1 = phi(x_0, y_1)

here the variables x and y are swapped, but a naive backtranslation produces an incorrect result:

y = x
x = y

clearly the value of y is clobbered. You would need to introduce a temporary variable.

I'll contribute some code later to address this if I can. Anyways, great work on the project!

rcx commented 6 years ago

(shameless self-plug)

If you are looking for a reference implementation of some popular algorithms for it, there is Sreedhar et al. and Boissinot et al..

serpilliere commented 6 years ago

Hi! Glad to hear from you :smiley: I can't wait to see your implementation!

By the way: in the example you gave, is it the very same assignblock (which means assignments are in parallel, and then x and y are really swapped), or is it a sequence of assignblock?

Thanks!

rcx commented 6 years ago

The phi statements are in parallel.

On Fri, Aug 17, 2018 at 12:54 serpilliere notifications@github.com wrote:

Hi! Glad to hear from you 😃 I can't wait to see your implementation!

By the way: in the example you gave, is it the very same assignblock (which means assignments are in parallel, and then x and y are really swapped), or is it a sequence of assignblock?

Thanks!

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/cea-sec/miasm/issues/823#issuecomment-413926118, or mute the thread https://github.com/notifications/unsubscribe-auth/APrQvVzmPLRMjNUx9FyUEeGykG6SMVB-ks5uRvVPgaJpZM4V_nvq .

serpilliere commented 6 years ago

Hi!

After an analysis done with @commial, it seems we don't have the swap problem, as the resulting created copies are also assigned in parallel. For the lost copy, you are totally right: we did a little toy example, and it messes around!

Thanks for the issue!

serpilliere commented 6 years ago

Hi! Did you do some progress on the un-ssa stuff? Cheers!

rcx commented 6 years ago

Hi! Sorry, I’ve been really busy with university.

The biggest hurdle for me is I don’t understand the codebase for this project that well. If you could give me a few pointers I could probably work it out.

On Sat, Sep 8, 2018 at 10:52 serpilliere notifications@github.com wrote:

Hi! Did you do some progress on the un-ssa stuff? Cheers!

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/cea-sec/miasm/issues/823#issuecomment-419648034, or mute the thread https://github.com/notifications/unsubscribe-auth/APrQvVLN27eEhmBHW1tYJpt-0phzofuwks5uY9mbgaJpZM4V_nvq .

serpilliere commented 6 years ago

No problem :smiley:

We will look at that in a near future with @commial : we are very interested to have a correct implementation of the un-ssa algorithm in Miasm.

rcx commented 6 years ago

Great. I’d be happy to help. The algorithm shouldn’t be too hard. We just need to track liveness ranges of variables and look at their intersections to determine how to allocate the copies.

On Mon, Sep 10, 2018 at 01:51 serpilliere notifications@github.com wrote:

No problem 😃

We will look at that in a near future with @commial https://github.com/commial : we are very interested to have a correct implementation of the un-ssa algorithm in Miasm.

— You are receiving this because you modified the open/close state.

Reply to this email directly, view it on GitHub https://github.com/cea-sec/miasm/issues/823#issuecomment-419794952, or mute the thread https://github.com/notifications/unsubscribe-auth/APrQvTtn4k3v7JDpV0YmiHWKEsxs2NGUks5uZf3KgaJpZM4V_nvq .