关于缓冲区溢出攻击的一次小测试

我们写C/C++程序的时候，用scanf，gets，strcpy什么的，编译总会有warning，这个函数是不安全的云云。到现在才明白这个所谓的不安全是怎么回事，这个关于C的历史遗留问题真的有够严重的。。。
不安全的代码，产生的bug就不是bug那么简单了，而是exploit。这个buffer overflow attack （缓冲区溢出攻击）在安全界的知名度是不言而喻的，基本上属于最经典的漏洞之一。各种利用工具和shellcode何其多哉！

抱着亲身了解下缓冲区溢出攻击的过程，顺便体验下linux下强大的gdb的心态，就拿gets（）写了个小程序练下手。

//attack.c
#include<stdio.h>
int main()
{
char s[8];
gets(s);
printf(s);
return 0;
}


生成的attack可执行文件用objdump反汇编：

080483f4 <main>:
 80483f4: 55                    push   %ebp
 80483f5: 89 e5                 mov    %esp,%ebp
 80483f7: 83 e4 f0              and    $0xfffffff0,%esp
 80483fa: 83 ec 20              sub    $0x20,%esp
 80483fd: 8d 44 24 18           lea    0x18(%esp),%eax
 8048401: 89 04 24              mov    %eax,(%esp)
 8048404: e8 fb fe ff ff        call   8048304 <gets@plt>
 8048409: 8d 44 24 18           lea    0x18(%esp),%eax
 804840d: 89 04 24              mov    %eax,(%esp)
 8048410: e8 0f ff ff ff        call   8048324 <printf@plt>
 8048415: b8 00 00 00 00        mov    $0x0,%eax
 804841a: c9                    leave  
 804841b: c3                    ret    
 804841c: 90                    nop
 804841d: 90                    nop
 804841e: 90                    nop
 804841f: 90                    nop

某个C程序的汇编代码解释

偶然看到Allan Ruin大大的某post，原意大概是：子函数内的局部变量没有初始化的话，其值应该是任意的，函数返回后会释放内存。但是为什么第二次调用的时候i的值会是777呢？之前没遇到过类似问题，毕竟是现实中不会出现的情况。但通过汇编代码大概可以研究一下的吧？
这段时间刚好在看CSAPP的GAS语法汇编，恰好拿来练手的说。


C代码如下： 版权属于Allan Ruin ：）
#include <stdio.h>
void foo(void)
{
int i;
printf("%d\n", i);
i = 777;
}
int main(void)
{
foo();
foo();
return 0;
}


ouput：
3
777

gcc -s lg_test.c

汇编代码如下


.file "lg_test.c"
.section .rodata             ;read only data segment
.LC0:
.string "%d\n"               ;printf() function's first parameter
.text
.globl foo
.type foo,@function


foo:
1  pushl %ebp              ;save old  %ebp
2  movl %esp, %ebp         ;new %ebp point to old %ebp (i.e. frame pointer)
3  subl $40, %esp          ;allocate 40 bytes on stack
4  movl $.LC0, %eax        ;move the string"%d\n" to %eax
5  movl -12(%ebp), %edx    ;use -12(%ebp) as i's value and save in %edx
6  movl %edx, 4(%esp)      ;set -12(%ebp) as the second parameter,push in stack
7  movl %eax, (%esp)       ;set  %eax( i.e. "%d\n" ) as the first parameter
8  call printf             ;call printf function(you can assume that 
                           ;it doesn't affect the existing stack frame)
9  movl $777, -12(%ebp)    ;NOTE:  -12 (%ebp) has changed
10 leave                   ;i.e.  movl %ebp, %esp ;    pop %ebp ;      
11 ret                     ;return    i.e.  pop %eip ;

merge sort & inversion

inversion 逆序数

definition: 

对数组a[].存在一对（i，j）有i < j 且 a[i] > a[j] 即为一个逆序数对

e.g.

{1,3,5,2,4,6} 逆序数为3

 i.e. (3,2) (5,2) (5,4)

Stanford open course 的第一章就是关于分而治之思想（divide and conquer）的归并排序（mergesort）。上学期去隔壁班蹭算法课的时候听了下内排序，其实理解的不够深刻。现在再看一次mergesort，确实将分治思想变现的淋漓尽致。将大问题划分成小问题，递归调用函数去解决。

mergesort的大致思路，就是将一个数组平均分成左右两个子数组，分别调用排序函数本身，返回的是两个已排序的数组，然后再将其merge起来。时间复杂度是O（n·log n)

在mergesort算法的基础上稍为改变一下就可以实现求一组数的逆序数。

单纯用for循环模拟的话，复杂度是O( n^2 ) 即n个数中取2个的组合数。

接上，一个array被分成left array[i] & right array[j]，其逆序数的组成可分为3部分：

1.left inversion     （i,j)均在left array中，即 i,j <= n/2   

2.right inversion     (i,j)均在right array中，即 i,j > n/2

3.split inversion      i在left，j在right，即 i <= n/2 ; j > n/2

计算左数组和右数组的逆序数，再加上split inversion即可得到整个数组的inversion number。问题关键成了解决split inversion。假设左右数组均已排好序（sorted B[],C[])，按mergesort的思路将两个数组合并的时候，每次从B[]取数放到合并数组(D[]),

计算B中剩余的元素个数（因为B中元素本应全部小于C中元素，若不是则必然存在逆序）。

课程练习原题是从100000的样本测试数据（txt）中计算逆序数个数，这个mergesort的模板感觉是有点怪（参数列表的问题）。开始用int count，结果溢出了。。。目测一下结果，貌似溢出的不多，改unsigned int，过了~

上代码：

#include<cstdio>

#include<fstream>

using namespace std;

int tmp[100001],a[100001];

void mergesort(int a[],int tmp[],int left,int right,unsigned int& count){   //待排序数组地址a，缓存数组tmp（节省时间，避免每次递归调用都开辟新数组）

int mid = (left + right) / 2;

if(left == right)return;     //递归分割的最小子项

mergesort(a,tmp,left,mid,count);      

mergesort(a,tmp,mid + 1,right,count);   //分别对左右数组递归调用mergesort（invoke mergesort() recursively）

for(int i = left;i <= right;i ++)tmp[i] = a[i];

int i = left;

int j = mid + 1;

for(int k = left;k <= right;k ++){    //merge two sorted array

if(i > mid)a[k] = tmp[j ++];      //judge the index of array out of size 

else if(j > right)a[k] = tmp[i ++];

else if(tmp[i] > tmp[j]){

a[k] = tmp[j ++];

count += mid + 1 - i;         //add remain number of left array(inversions with tmp[j])

}

else a[k] = tmp[i ++];

}

}

int main()

{

fstream file("d:\\IntegerArray.txt",ios::in);

if(!file)printf("exception!");

int i = 0;

unsigned int count = 0;

char s[10];

while(file >> s)

a[i ++] = atoi(s);

mergesort(a,tmp,0,99999,count);

printf("%u\n",count);

return 0;

}