Simplifying Complex Expression in Reverse Code Engineering

Some parts of a software system that you reverse engineer may contain complex expressions. The first question is whether you need to simplify those complex expressions? In many cases, you need to, because the basic notion of reverse engineering is to understand what's going on, not to make it even slightly more complex. Now, the second question is: how to deal with  such complex expression?

There are several avenues to deal with the complexity. I found these steps to be useable:

1. "Translate" the expressions into propositional variables. Just to make it more readable. For example: the (i < sizeof(MY_DATA)) expression could be "translated" as propositional variable A,  and so on.
2. Once you have the propositions in place. You now have several options to minimize the present expressions. 
• If the number of propositional variable is less than or equal to four, Karnaugh Maps (K-Map) is enough. See http://en.wikipedia.org/wiki/Karnaugh_map
• If the number of propositional variable is more than four but less than ten, then Quine-McCluskey algorithm ( http://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm ) is attractive because the processing time is "bearable" and could help finding the most simplified form precisely. Unfortunately, due to the exponential run-tim nature of the  Quine-McCluskey, any values above ten probably requires unpractical amount of time.
• If the number of propositional variable is equal-to or more than ten, then the most attractive option is the Espresso heuristic (http://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer ).

Anyway, I think that it's a very seldom case to encounter software code that uses closes to ten propositional variables in a single expression unless the programmer who wrote the code is a very unskilled or do so intentionally. 

---

Post a Comment