Importance of dominators in reverse engineering

Question

Came across this question: explain the role of dominators in reverse engineering Java code.

All I can think of is that you need to be able to calculate the Dominators in a Control Graph to see if it is reducable:

1. Work out dominators
2. Identify and remove back edges
3. Check if the remaining graph is acyclic

If the graph is acylic - it is reducible. Therefore all the loops are natural loops. If its not reducible, then the code is unstructored or optimised.

Does this sound correct to you?

Answer 1

There's all kinds of reasons that dominators are interesting in program analysis, whether you are doing reverse engineering as a special case or not.

The key notion is that if X dominates Y, when Y gets executed, X has been already executed. So if you want to understand what Y is doing, and Y depends on the context in which it is executed, you're probably going to need to understand X.

There are other things you need to understand, too, such as dataflows into Y, program inputs, etc. Just this is a useful place to start.

There are lots of analysis algorithms that use dominators, each answer specific kinds of questions. Its hard to argue any of these are "the (key) role" dominators play.