USB Mass Storage

This project deals with …..

How to debug a corrupted stack

Is your stacktrace really corrupted?

by Salvatore Iovene on 17 October 2006 — Posted in Howtos, Coding, Articles

You may encounter, during your debugging sessions, the `stack corruption’ problem. Usually you will find it out after seeing your program run into a segmentation fault. Otherwise, it must mean that some very malicious and subtle code has been injected into your program, usually through a buffer overrun. What is a buffer overrun? Let’s examine the following short C code:

#include <stdio.h>

void bar(char* str) {
    char buf[4];
    strcpy( buf, str );
}

void foo() {
    printf("Hello from foo!");
}

int main(void) {
    bar("This string definitely is too long, sorry!");
    foo();
    return 0;
}

There’s clearly something wrong with it: as you can see, we are copying `str’ to `buf’ without first checking the size of `str’. First of all there is a security issue, because if `str’ didn’t just come from a fixed string like in this case, but got inputted from somewhere (maybe on a website), then there could be a string long enough to overwrite the code of `foo’, and run malicious code on its behalf. What we have here, anyhow, is just a segmentation fault. Let’s debug the program.

(gdb) file stack
Reading symbols from /home/siovene/stack...done.
(gdb) run
Starting program: /home/siovene/stack

Program received signal SIGSEGV, Segmentation fault.
0x6f6c206f in ?? ()
(gdb) backtrace
#0  0x6f6c206f in ?? ()
#1  0x202c676e in ?? ()
#2  0x72726f73 in ?? ()
#3  0xbf002179 in ?? ()
#4  0xb7df9970 in __libc_start_main ()
      from /lib/tls/i686/cmov/libc.so.6
Previous frame inner to this frame (corrupt stack?)

Obviously something must have gone wrong.

In order to better understand what is going on, let’s make a step back, and let’s examine

a working example instead:
#include <stdio.h>

void bar(char* str) {
    char buf[4];
    strcpy( buf, str );
}

void foo() {
    printf("Hello from foo!");
}

int main(void) {
    bar("abc");
    foo();
    return 0;
}

This is the same code, but it’s been stripped off of the long string that caused the
segmentation fault, and in its place we find a harmless 3 character string: `abc’.
Let’s name the program stack.c anc compile it with debug informaion:
$> gcc -g -o stack stack.c

Now let’s debug it:
(gdb) file stack
Reading symbols from /home/siovene/stack...done.
(gdb) break bar
Breakpoint 1 at 0x80483ca: file stack.c, line 5.
(gdb) run
Starting program: /home/siovene/stack

Breakpoint 1, bar (str=0x8048545 "abc") at stack.c:5
5         strcpy( buf, str );

We have entered the bar() function, let’s examine the backtrace:
(gdb) backtrace
#0  bar (str=0x8048545 "abc") at stack.c:5
#1  0x0804840e in main () at stack.c:13

What is the address of the bar() function?
(gdb) print bar
$1 = {void (char *)} 0x80483c4

Let’s now be paranoid and check this out producing a dump of our executable:
$> objdump -tD stack > stack.dis

Open the file with your favorite editor and look for `80483c4′, the address of bar():
080483c4 <bar>:
 80483c4: 55                    push   %ebp
 80483c5: 89 e5                 mov    %esp,%ebp
 80483c7: 83 ec 28              sub    $0x28,%esp
 80483ca: 8b 45 08              mov    0x8(%ebp),%eax
 80483cd: 89 44 24 04           mov    %eax,0x4(%esp)
 80483d1: 8d 45 e8              lea    0xffffffe8(%ebp),%eax
 80483d4: 89 04 24              mov    %eax,(%esp)
 80483d7: e8 0c ff ff ff        call   80482e8
 80483dc: c9                    leave
 80483dd: c3                    ret

Perfect, that’s our function. But now let’s get curious.
Where’s the stack pointer in the CPU registers?
(gdb) info registers
eax            0x0      0
ecx            0xb7ed11b4       -1209200204
edx            0xbff04f60       -1074770080
ebx            0xb7ecfe9c       -1209205092
esp            0xbff04f10       0xbff04f10
ebp            0xbff04f38       0xbff04f38
esi            0xbff04fd4       -1074769964
edi            0xbff04fdc       -1074769956
eip            0x80483ca        0x80483ca
eflags         0x282    642
cs             0x73     115
ss             0x7b     123
ds             0x7b     123
es             0x7b     123
fs             0x0      0
gs             0x33     51

The `esp’ register, on the architecture this article is written on, is the stack pointer.
Its address is 0xbff04f10. Let’s examine the memory at that point:
(gdb) x/20xw 0xbff04f10
0xbff04f10:  0x00000000   0x08049638   0xbff04f28   0x080482b5
0xbff04f20:  0xb7ecfe90   0xbff04f34   0xbff04f48   0x0804843b
0xbff04f30:  0xbff04fdc   0xb7ecfe9c   0xbff04f48   0x0804840e
0xbff04f40:  0x08048545   0x08048480   0xbff04fa8   0xb7db3970
0xbff04f50:  0x00000001   0xbff04fd4   0xbff04fdc   0x00000000

With this command we have told GDB to examine 20 words in exadecimal format
at the address 0xbff04f10. That’s because the value of the stack pointer is the
address of the back-chain pointer to the previous stack frame. So address 0×00000000 is the
address of the previous stack frame. But 0×00000000 is put in the stack frame in concurrence of
the program entry point, i.e. the main() function. This agrees with the fact that we know bar()
was called by main()!
Everything looks ok and in place, since the program works perfectly we weren’t expecting anything
different. Let’s now do the same with the faulty program. At the moment of the segmentation fault,
the backtrace looked like this:
(gdb) backtrace
#0  0x6f6c206f in ?? ()
#1  0x202c676e in ?? ()
#2  0x72726f73 in ?? ()
#3  0xbf002179 in ?? ()
#4  0xb7df9970 in __libc_start_main ()
      from /lib/tls/i686/cmov/libc.so.6
Previous frame inner to this frame (corrupt stack?)

To see exactly what goes on, it would be better to debug it more carefully:
(gdb) file stack
Reading symbols from /home/siovene/stack...done.
(gdb) break bar
Breakpoint 1 at 0x80483ca: file stack.c, line 5.
(gdb) run
Starting program: /home/siovene/stack

Breakpoint 1, bar (str=0x8048580
                    "This string definitely is too long, sorry!")
                  at stack.c:5
5         strcpy( buf, str );
(gdb) next
6       }
(gdb) next
0x6f6c206f in ?? ()
(gdb) next
Cannot find bounds of current function



Let’s then try to follow back the stacktrace, as we did previously:
(gdb) backtrace
#0  0x6f6c206f in ?? ()
#1  0x202c676e in ?? ()
#2  0x72726f73 in ?? ()
#3  0xbf002179 in ?? ()
#4  0xb7e9b970 in __libc_start_main ()
      from /lib/tls/i686/cmov/libc.so.6
Previous frame inner to this frame (corrupt stack?)

(gdb) info registers
eax            0xbfeed1e0       -1074867744
ecx            0xb7ea4c5f       -1209381793
edx            0x80485ab        134514091
ebx            0xb7fb7e9c       -1208254820
esp            0xbfeed200       0xbfeed200
ebp            0x6f742073       0x6f742073
esi            0xbfeed294       -1074867564
edi            0xbfeed29c       -1074867556
eip            0x6f6c206f       0x6f6c206f
eflags         0x246    582
cs             0x73     115
ss             0x7b     123
ds             0x7b     123
es             0x7b     123
fs             0x0      0
gs             0x33     51

(gdb) x/20xw 0xbfeed200
0xbfeed200:  0x202c676e   0x72726f73   0xbf002179   0xb7e9b970
0xbfeed210:  0x00000001   0xbfeed294   0xbfeed29c   0x00000000
0xbfeed220:  0xb7fb7e9c   0xb7fee540   0x08048480   0xbfeed268
0xbfeed230:  0xbfeed210   0xb7e9b932   0x00000000   0x00000000
0xbfeed240:  0x00000000   0xb7feeca0   0x00000001   0x08048300

(gdb) x/20xw 0x202c676e
0x202c676e:     Cannot access memory at address 0x202c676e

There’s only one explanation to that: the stack memory has been overwritten and now contains
gibberish. We have been very unlucky with our example, but this gave us the tools to imagine
another case. Let’s assume the stack got actually corrupted not because it was overwritten
accidentally, but because GDB was failing to build it. In this case you are still able to
navigate it backwards. All you need to do it keep following the value of the stack frames,
starting from the `esp’ register, until you reach 0×000000. Write all the addresses down, and
then use `objdump’ to obtain the disassembly and symbols information from the binary. All is left,
now, is to check the names of the symbols matching the pinned up addresses.
If you can actually do that, than you have successfully reconstructed your stacktrace.
It wasn’t really corrupted by a bug in your program, but simply GDB missed to keep it up with it.
 
 

Binary Search Tree

/* Binary search Tree */

#include <stdio.h>
#include <stdlib.h>

#define SUCCESS 0
#define FAILURE 1

int bst_insert(int);
void bst_print_inorder(void);

struct bstn {
    int data;
    struct bstn *left;
    struct bstn *prev;
    struct bstn *right;
};

#define BSTN_SIZE sizeof(struct bstn)

struct bstn *root = NULL;

int input[] = {25,5,36,4,2,85,42,65,7,22,51};

main()
{
    int i, ret;
    int ipsz = sizeof(input)/sizeof(int);

    printf(“Size of array is %d\n”, ipsz);

    /* Create a BST */
    for(i=0; i<ipsz; i++) {
        ret = bst_insert(input[i]);

        if (ret != SUCCESS) {
            printf(“Failed to create a binary search tree\n”);
            return FAILURE;
        }
    }

    /* Print values by accessing the BST inorder */
    bst_print_inorder();

}
/* Insertion */

int bst_insert(int value)
{
    struct bstn *ptr, *place_holder;
    int left_right = 0;
    if (root == NULL) {
        root = malloc(BSTN_SIZE);

        if (root == NULL) {
            printf(“Resource unavailable”);
            return FAILURE;
        }
        root->data = value;
        root->left = NULL;
        root->right = NULL;
        root->prev = NULL;
    } else {
        ptr = root;
        place_holder = root;

        while(ptr != NULL) {
            if(ptr->data >= value) {
                place_holder = ptr;
                left_right = 1;
                ptr = ptr->left;
            } else {
                place_holder = ptr;
                left_right = 2;
                ptr = ptr->right;
            }
        }

        if(left_right == 1) {
            place_holder->left = malloc(BSTN_SIZE);

            if (place_holder->left == NULL) {
                printf(“Resource unavailable”);
                return FAILURE;
            }

            place_holder->left->data = value;
            place_holder->left->prev = place_holder;
            place_holder->left->left = NULL;
            place_holder->left->right = NULL;
        } else if(left_right == 2 ) {
            place_holder->right = malloc(BSTN_SIZE);

            if (place_holder->right == NULL) {
                printf(“Resource unavailable”);
                return FAILURE;
            }

            place_holder->right->data = value;
            place_holder->right->prev = place_holder;
            place_holder->right->left = NULL;
            place_holder->right->right = NULL;
        } else {
            printf(“Insertion error in the BST\n”);
            return FAILURE;
        }

    }
    return SUCCESS;
}

/* Deletion */

/* Search */

/* Depth of a tree */

/* Printing inorder */
void bst_print_inorder(struct bstn *ptr, int left_middle_right)
{
    struct bstn *ptr = root, *place_holder = root;
    if(root == NULL) {
        printf(“BST not created\n”);
        return;
    }

    if(left_middle_right == 1) {
        /* Go to the left most node */
        while(ptr != NULL) {
            place_holder = ptr;
            ptr = ptr->left;
        }

        printf(“%d\t”, place_holder->data);

        while(place_holder->prev != NULL) {
            printf(“%d\t”, place_holder->prev->data);
            printf(“%d\t”, place_holder->prev->right->data);
        }
     
        bst_print_inorder(place_holder->prev, 2);
    } else if(left_middle_right == 2) {
    } else if(left_middle_right == 3) {
    } else {
        printf(“Incorrect Usage \n”);
        return;
    }

}

Sorting stability

Stability

Stable sorting algorithms maintain the relative order of records with equal keyshttp://en.wikipedia.org/wiki/Strict_weak_ordering (i.e., sort key values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.

When equal elements are indistinguishable, such as with integers, or more generally, any data where the entire element is the key, stability is not an issue. However, assume that the following pairs of numbers are to be sorted by their first component:

(4, 2)  (3, 7)  (3, 1)  (5, 6)

In this case, two different results are possible, one which maintains the relative order of records with equal keys, and one which does not:

(3, 7)  (3, 1)  (4, 2)  (5, 6)   (order maintained)
(3, 1)  (3, 7)  (4, 2)  (5, 6)   (order changed)

Unstable sorting algorithms may change the relative order of records with equal keys, but stable sorting algorithms never do so. Unstable sorting algorithms can be specially implemented to be stable. One way of doing this is to artificially extend the key comparison, so that comparisons between two objects with otherwise equal keys are decided using the order of the entries in the original data order as a tie-breaker. Remembering this order, however, often involves an additional space cost.

Sorting based on a primary, secondary, tertiary, etc. sort key can be done by any sorting method, taking all sort keys into account in comparisons (in other words, using a single composite sort key). If a sorting method is stable, it is also possible to sort multiple times, each time with one sort key. In that case the keys need to be applied in order of increasing priority.

Example: sorting pairs of numbers as above by first, then second component:

(4, 2)  (3, 7)  (3, 1)  (4, 6) (original)

(3, 1)  (4, 2)  (4, 6)  (3, 7) (after sorting by second component)
(3, 1)  (3, 7)  (4, 2)  (4, 6) (after sorting by first component)

On the other hand:

(3, 7)  (3, 1)  (4, 2)  (4, 6) (after sorting by first component)
(3, 1)  (4, 2)  (4, 6)  (3, 7) (after sorting by second component, 
                                order by first component is disrupted)

Selection Sort

Complexity: O(n^2)   { O of n square)

Space Complexity: О(n) total, O(1) auxiliary

Key Properties:

1. Outperforms “bubble sort” and “gnome sort”
2. Outperformed  by “insertion sort”
3. “Insertion sort” or “selection sort” are both typically faster for small arrays (i.e. fewer than 10-20 elements).
4. “Selection sort” will perform identically regardless of the order of the array, whearas “Insertion sort’s” running time can vary considerably if the array is already sorted or “close to sorted.”

Psuedocode:

for i ← 0 to n-2 do
    min ← i
    for j ← (i + 1) to n-1 do
        if A[j] < A[min]
            min ← j
    swap A[i] and A[min]

Analysis:

Selecting the lowest element requires scanning all n elements (this takes n – 1 comparisons) and then swapping it into the first position. Finding  the  next lowest element  requires scanning  the remaining n – 1 elements and so on, for (n – 1) + (n – 2) + … + 2 + 1 = n * (n – 1) / 2 ∈ Θ(n²) comparisons (by Arithmetic progression). Each of these scans requires one swap for n – 1 elements (the final element is already in place).

Determine if an integer is signed or not …..

int v; // we want to find the sign of v

int sign; // the result goes here

// CHAR_BIT is the number of bits per byte (normally 8).

The obvious way is to use

sign = -(v < 0);// but this would involve CPU to branch using the EFLAGS register.

The portable way

sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT – 1));

A non portable way

sign = v >> (sizeof(int) * CHAR_BIT – 1);

Bit Twiddling Hacks

Some intresting Bit twiddling Hacks

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Toggling selected bits in a integer

The following in NOT a generic solution. You have to construct the masks for each case.

—————————————————————————————
#include

/* In the following example bits 0, 2, 6
* are toggled. The MASK has to be calculated
* seperately for differenct cases.
*/

#define MASK_NON_TOGGLED_BITS 0xFFFFFFBA
#define MASK_TOGGLED_BITS 0x45

main()
{
int num=0xEB, result, tmp, tmp1;
tmp = num & MASK_NON_TOGGLED_BITS;
tmp1 = num & MASK_TOGGLED_BITS;

result = tmp + (~tmp1 & MASK_TOGGLED_BITS);
printf(“toggled result: %x :num %x\n”,result, num);
}
————————————————————————————–

Counting the number of set bits in an integer, determine if a number is power of 2

This program also has a definition to determine if a given number is  “power of two”

#include <stdio.h>

unsigned int countones(unsigned int, unsigned char);

#define new_power_of_two(x) \
(((x)&(x-1)) == 0)

main()
{
unsigned int result, num = 0xFFF0F0F0;

result = countones(num, 1);
printf(“M1::Number of ones in integer is %d\n”, result);

result = countones(num, 2);
printf(“M2::Number of ones in integer is %d\n”, result);

result = countones(num, 3);
printf(“M3::Number of ones in integer is %d\n”, result);
printf(“Is power of two %d\n”, new_power_of_two(1512));

}

unsigned int countones(unsigned int num, unsigned char method)
{
if (method == 1) {
int count = sizeof(unsigned int) * 8;
int result = 0;
while(count) {
result += (num & 1);
num =  num>>1;
count–;
}
return result;
} else if (method == 2) {

//Prefered Method

unsigned int x = num;
const unsigned int m1 = 0x55555555;
const unsigned int m2 = 0x33333333;
const unsigned int m4 = 0x0f0f0f0f;
const unsigned int m8 = 0x00ff00ff;
const unsigned int m16 = 0x0000ffff;

x = (x & m1 ) + ((x >>  1 ) & m1 );
x = (x & m2 ) + ((x >>  2 ) & m2 );
x = (x & m4 ) + ((x >>  4 ) & m4 );
x = (x & m8 ) + ((x >>  8 ) & m8 );
x = (x & m16) + ((x >> 16) & m16);
return x;

// Brain Kerninghan’s method, This logic woks in O(number of bits set)….

} else if (method == 3) {
unsigned int v = num; // count the number of bits set in v
unsigned int c = 0; // c accumulates the total bits set in v
for (c = 0; v; c++) {
printf(“num is %x::::num&(num-1) is %x\n”, v, v&(v-1));
v &= v – 1; // clear the least significant bit set
}
return c;
}
}

Memory Leaks

http://www.cs.virginia.edu/woda2004/slides/maebe.ppt

Memory Leaks
•What
–Allocating memory without releasing later
•Why bad
–Reduce performance
–May cause crashes
•How to solve
–Find out where exactly memory is leaked

Physical Leaks
•What
–Last pointer to a block of memory is destroyed
•Causes
–Pointer overwrite
–Free block containing pointer
–Stack shrinks
•Important information:
–Allocation site of block
–Location where last pointer is lost
–Assignment location of last pointer

Logical Leaks
•What
–Reachable pointer available, but block never freed
•Important information
–Allocation site of block
–Where are these pointers?