# X86 Disassembly/Data Structures

## Data Structures

Few programs can work by using simple memory storage; most need to
utilize complex data objects, including **pointers**, **arrays**,
**structures**, and other complicated types. This chapter will talk
about how compilers implement complex data objects, and how the reverser
can identify these objects.

## Arrays

Arrays are simply a storage scheme for multiple data objects of the same
type. Data objects are stored sequentially, often as an offset from a
pointer to the beginning of the array. Consider the following C code:

``` C
 x = array[25];
```

Which is identical to the following asm code:

``` asm
 mov ebx, $array
 mov eax, [ebx + 25]
 mov $x, eax
```

Now, consider the following example:

``` C
 int MyFunction1()
 {
    int array[20];
    ...
```

This (roughly) translates into the following asm pseudo-code:

``` asm
 :_MyFunction1
 push ebp
 mov ebp, esp
 sub esp, 80 ;the whole array is created on the stack!!!
 lea $array, [esp + 0] ;a pointer to the array is saved in the array variable
 ...
```

The entire array is created on the stack, and the pointer to the bottom
of the array is stored in the variable \"array\". An optimizing compiler
could ignore the last instruction, and simply refer to the array via a
+0 offset from esp (in this example), but we will do things verbosely.

Likewise, consider the following example:

``` C
 void MyFunction2()
 {
    char buffer[4];
    ...
```

This will translate into the following asm pseudo-code:

``` asm
 :_MyFunction2
 push ebp
 mov ebp, esp
 sub esp, 4
 lea $buffer, [esp + 0]
 ...
```

Which looks harmless enough. But, what if a program inadvertantly
accesses buffer\[4\]? what about buffer\[5\]? what about buffer\[8\]?
This is the makings of a buffer overflow vulnerability, and (might) will
be discussed in a later section. However, this section won\'t talk about
security issues, and instead will focus only on data structures.

### Spotting an Array on the Stack

To spot an array on the stack, look for large amounts of local storage
allocated on the stack (\"sub esp, 1000\", for example), and look for
large portions of that data being accessed by an offset from a different
register from esp. For instance:

``` asm
 :_MyFunction3
 push ebp
 mov ebp, esp
 sub esp, 256
 lea ebx, [esp + 0x00]
 mov [ebx + 0], 0x00
```

is a good sign of an array being created on the stack. Granted, an
optimizing compiler might just want to offset from esp instead, so you
will need to be careful.

### Spotting an Array in Memory

Arrays in memory, such as global arrays, or arrays which have initial
data (remember, initialized data is created in the .data section in
memory) and will be accessed as offsets from a hardcoded address in
memory:

``` asm
 :_MyFunction4
 push ebp
 mov ebp, esp
 mov esi, 0x77651004
 mov ebx, 0x00000000
 mov [esi + ebx], 0x00
```

It needs to be kept in mind that structures and classes might be
accessed in a similar manner, so the reverser needs to remember that all
the data objects in an array are of the same type, that they are
sequential, and they will often be handled in a loop of some sort. Also,
(and this might be the most important part), each elements in an array
may be accessed by a *variable offset from the base*.

Since most times an array is accessed through a computed index, not
through a constant, the compiler will likely use the following to access
an element of the array:

``` asm
 mov [ebx + eax], 0x00
```

If the array holds elements larger than 1 byte (for char), the index
will need to be multiplied by the size of the element, yielding code
similar to the following:

``` asm
 mov [ebx + eax * 4], 0x11223344   # access to an array of DWORDs, e.g.    arr[i] = 0x11223344
 ...
 mul eax, $20                      # access to an array of structs, each 20 bytes long
 lea edi, [ebx + eax]              # e.g.     ptr = &arr[i]
```

This pattern can be used to distinguish between accesses to arrays and
accesses to structure data members.

## Structures

All C programmers are going to be familiar with the following syntax:

``` C
 struct MyStruct 
 {
    int FirstVar;
    double SecondVar;
    unsigned short int ThirdVar;
 }
```

It\'s called a **structure** (Pascal programmers may know a similar
concept as a \"record\").

Structures may be very big or very small, and they may contain all sorts
of different data. Structures may look very similar to arrays in memory,
but a few key points need to be remembered: structures do not need to
contain data fields of all the same type, structure fields are often
4-byte aligned (not sequential), and each element in a structure has its
own offset. It therefore makes no sense to reference a structure element
by a variable offset from the base.

Take a look at the following structure definition:

``` C
 struct MyStruct2
 {
    long value1;
    short value2;
    long value3;
 }
```

Assuming the pointer to the base of this structure is loaded into ebx,
we can access these members in one of two schemes:

+---+---+
| ` | ` |
| ` | ` |
| ` | ` |
|   |   |
| a | a |
| s | s |
| m | m |
|   |   |
| ; | ; |
| d | d |
| a | a |
| t | t |
| a | a |
|   |   |
| i | i |
| s | s |
|   |   |
| 3 | " |
| 2 | p |
| - | a |
| b | c |
| i | k |
| t | e |
|   | d |
| a | " |
| l |   |
| i | [ |
| g | e |
| n | b |
| e | x |
| d |   |
|   | + |
| [ |   |
| e | 0 |
| b | ] |
| x |   |
|   | ; |
| + | v |
|   | a |
| 0 | l |
| ] | u |
|   | e |
| ; | 1 |
| v |   |
| a | [ |
| l | e |
| u | b |
| e | x |
| 1 |   |
|   | + |
| [ |   |
| e | 4 |
| b | ] |
| x |   |
|   | ; |
| + | v |
|   | a |
| 4 | l |
| ] | u |
|   | e |
| ; | 2 |
| v |   |
| a | [ |
| l | e |
| u | b |
| e | x |
| 2 |   |
|   | + |
| [ |   |
| e | 6 |
| b | ] |
| x |   |
|   | ; |
| + | v |
|   | a |
| 8 | l |
| ] | u |
|   | e |
| ; | 3 |
| v | ` |
| a | ` |
| l | ` |
| u |   |
| e |   |
| 3 |   |
| ` |   |
| ` |   |
| ` |   |
+---+---+

The first arrangement is the most common, but it clearly leaves open an
entire memory word (2 bytes) at offset +6, which is not used at all.
Compilers occasionally allow the programmer to manually specify the
offset of each data member, but this isn\'t always the case. The second
example also has the benefit that the reverser can easily identify that
each data member in the structure is a different size.

Consider now the following function:

``` asm
 :_MyFunction
 push ebp
 mov ebp, esp
 lea ecx, SS:[ebp + 8]
 mov [ecx + 0], 0x0000000A
 mov [ecx + 4], ecx
 mov [ecx + 8], 0x0000000A
 mov esp, ebp
 pop ebp
```

The function clearly takes a pointer to a data structure as its first
argument. Also, each data member is the same size (4 bytes), so how can
we tell if this is an array or a structure? To answer that question, we
need to remember one important distinction between structures and
arrays: the elements in an array are all of the same type, the elements
in a structure do not need to be the same type. Given that rule, it is
clear that one of the elements in this structure is a pointer (it points
to the base of the structure itself!) and the other two fields are
loaded with the hex value 0x0A (10 in decimal), which is certainly not a
valid pointer on any system I have ever used. We can then partially
recreate the structure and the function code below:

``` C
 struct MyStruct3
 {
    long value1;
    void *value2;
    long value3;
 }

 void MyFunction2(struct MyStruct3 *ptr)
 {
    ptr->value1 = 10;
    ptr->value2 = ptr;
    ptr->value3 = 10;
 }
```

As a quick aside note, notice that this function doesn\'t load anything
into eax, and therefore it doesn\'t return a value.

## Advanced Structures

Lets say we have the following situation in a function:

``` asm
 :MyFunction1
 push ebp
 mov ebp, esp
 mov esi, [ebp + 8]
 lea ecx, SS:[esi + 8]
 ...
```

what is happening here? First, esi is loaded with the value of the
function\'s first parameter (ebp + 8). Then, ecx is loaded with a
pointer to the offset +8 from esi. It looks like we have 2 pointers
accessing the same data structure!

The function in question could easily be one of the following 2
prototypes:

``` C
 struct MyStruct1
 {
   DWORD value1;
   DWORD value2;
   struct MySubStruct1
   {
      ...
```

``` C
 struct MyStruct2
 {
    DWORD value1;
    DWORD value2;
    DWORD array[LENGTH];
    ...
```

one pointer offset from another pointer in a structure often means a
complex data structure. There are far too many combinations of
structures and arrays, however, so this wikibook will not spend too much
time on this subject.

## Identifying Structs and Arrays

Array elements and structure fields are both accessed as offsets from
the array/structure pointer. When disassembling, how do we tell these
data structures apart? Here are some pointers:

1.  Array elements are not meant to be accessed individually. Array
    elements are typically accessed using a variable offset
2.  Arrays are frequently accessed in a loop. Because arrays typically
    hold a series of similar data items, the best way to access them all
    is usually a loop. Specifically,
    `for(x = 0; x < length_of_array; x++)` style loops are often used to
    access arrays, although there can be others.
3.  All the elements in an array have the same data type.
4.  Struct fields are typically accessed using constant offsets.
5.  Struct fields are typically not accessed in order, and are also not
    accessed using loops.
6.  Struct fields are not typically all the same data type, or the same
    data width

## Linked Lists and Binary Trees

Two common structures used when programming are linked lists and binary
trees. These two structures in turn can be made more complicated in a
number of ways. Shown in the images below are examples of a linked list
structure and a binary tree structure.

+---+---+
| ! | ! |
| [ | [ |
| ] | ] |
| ( | ( |
| C | t |
| _ | r |
| l | e |
| a | e |
| n | - |
| g | d |
| u | a |
| a | t |
| g | a |
| e | - |
| _ | s |
| l | t |
| i | r |
| n | u |
| k | c |
| e | t |
| d | u |
| _ | r |
| l | e |
| i | . |
| s | s |
| t | v |
| . | g |
| p |   |
| n | " |
| g | t |
|   | r |
| " | e |
| C | e |
| _ | - |
| l | d |
| a | a |
| n | t |
| g | a |
| u | - |
| a | s |
| g | t |
| e | r |
| _ | u |
| l | c |
| i | t |
| n | u |
| k | r |
| e | e |
| d | . |
| _ | s |
| l | v |
| i | g |
| s | " |
| t | ) |
| . | { |
| p | w |
| n | i |
| g | d |
| " | t |
| ) | h |
| { | = |
| w | " |
| i | 3 |
| d | 0 |
| t | 0 |
| h | " |
| = | } |
| " |   |
| 4 |   |
| 0 |   |
| 0 |   |
| " |   |
| } |   |
+---+---+

Each node in a linked list or a binary tree contains some amount of
data, and a pointer (or pointers) to other nodes. Consider the following
asm code example:

``` asm
loop_top:
cmp [ebp + 0], 10
je loop_end
mov ebp, [ebp + 4]
jmp loop_top
loop_end:
```

At each loop iteration, a data value at \[ebp + 0\] is compared with the
value 10. If the two are equal, the loop is ended. If the two are not
equal, however, the pointer in ebp is updated with a pointer at an
offset from ebp, and the loop is continued. This is a classic
linked-loop search technique. This is analagous to the following C code:

``` c
struct node 
{
  int data;
  struct node *next;
};

struct node *x;
...
while(x->data != 10)
{
  x = x->next;
}
```

Binary trees are the same, except two different pointers will be used
(the right and left branch pointers).
