Print indd

3.1
Analyzing the Program
Since the key concept of the approach requires to know the addresses of the
loops within the binary, the first action is to investigate the instruction stream
and to create a CFG consisting of basic blocks. A basic block is defined by
Cooper as a maximal length sequence of instructions with only one entry at the
beginning and one exit at the end [
4
]. It allows a more abstract view on the
control flow and is used in compilers to analyze the program. There are two
possibilities to create a CFG. The first one is to perform a static analysis of
the binary file. Reverse engineering tools often provide this functionality and
offer a library to use within other software. For the means of this paper, this
would suffice. However, the implementation created here uses another method
to build a CFG that also delivers information about the actual control flow
during the execution. It takes the instruction trace of a fast functional simulation
for this purpose. Thereby, the loops and basic blocks can be annotated by the
amount of times they were executed. Additionally, dead code is not taken into
account. With this knowledge, future enhancements of this methodology might
for example use different amounts of accurate iterations for each loop depending
on the information gathered from the first run. As of now, a plain CFG extracted
from the program under test is enough.
As depicted in Fig.
1
, the next step is to find the loops within the CFG. For
this, the dominance relationship between the basic blocks inside a function is
required. If a node
A in a graph dominates another node B, it means that all
paths that reach
B starting from the function entry block also must contain A.
This relationship can be extracted by a simple textbook algorithm that is fast

---

A Hybrid Approach for Runtime Analysis
89
enough in most occasions [
5
]. A loop consists of basic blocks in between a loop
entry block dominating all instructions in the loop body and the backward edge
returning to the loop entry. Irreducible loops without an unambiguous head are
not taken into account within this work. Since functions called within loops are
difficult to handle, a simplification is introduced. A set called “considered blocks”
is created that contains all basic blocks of the loop body. Additionally, all called
functions are visited and their basic blocks including the basic blocks of other
functions called within them are inserted recursively. The set is used to find
out if a certain loop is already left or still executed but currently calls another
function. While this approach is simple to determine the basic control flow of a
program, sophisticated cases containing complex call hierarchies within a loop
are not satisfactorily handled. Furthermore, the start and end addresses of all
basic blocks are saved to allow the identification of the currently executed block
by using the current program counter of the simulated architecture. Additional
information that can be annotated to the nodes of the CFG is the amount of
executions of a basic block in case an instruction stream was analyzed.
Another simplification that is implemented into the presented system is that
only the outer loops are taken into account. This is sensible since all iterations
of the inner loops are run during one iteration of an outer loop. However, this
is not true for inner loops with different runtimes during each iteration of the
outer loop. Thus, future improvements of this methodology might need to also
take inner loops into account.