Массивы
From Wiki.conus.info
Массив это просто набор переменных в памяти, обязательно лежащих рядом, одного типа.
#include <stdio.h> int main() { int a[20]; int i; for (i=0; i<20; i++) a[i]=i*2; for (i=0; i<20; i++) printf ("a[%d]=%d\n", i, a[i]); return 0; };
Компилируем:
_TEXT SEGMENT _i$ = -84 ; size = 4 _a$ = -80 ; size = 80 _main PROC ; Line 4 push ebp mov ebp, esp sub esp, 84 ; 00000054H ; Line 8 mov DWORD PTR _i$[ebp], 0 jmp SHORT $LN6@main $LN5@main: mov eax, DWORD PTR _i$[ebp] add eax, 1 mov DWORD PTR _i$[ebp], eax $LN6@main: cmp DWORD PTR _i$[ebp], 20 ; 00000014H jge SHORT $LN4@main ; Line 9 mov ecx, DWORD PTR _i$[ebp] shl ecx, 1 mov edx, DWORD PTR _i$[ebp] mov DWORD PTR _a$[ebp+edx*4], ecx jmp SHORT $LN5@main $LN4@main: ; Line 11 mov DWORD PTR _i$[ebp], 0 jmp SHORT $LN3@main $LN2@main: mov eax, DWORD PTR _i$[ebp] add eax, 1 mov DWORD PTR _i$[ebp], eax $LN3@main: cmp DWORD PTR _i$[ebp], 20 ; 00000014H jge SHORT $LN1@main ; Line 12 mov ecx, DWORD PTR _i$[ebp] mov edx, DWORD PTR _a$[ebp+ecx*4] push edx mov eax, DWORD PTR _i$[ebp] push eax push OFFSET $SG2463 call _printf add esp, 12 ; 0000000cH jmp SHORT $LN2@main $LN1@main: ; Line 14 xor eax, eax ; Line 15 mov esp, ebp pop ebp ret 0 _main ENDP
Однако, ничего особенного, просто два цикла, один заполняет цикл, второй печатает его содержимое. Команда shl ecx, 1 используется для умножения ECX на 2, об этом ниже: Сдвиги.
Под массив выделено в стеке 80 байт, это 20 элементов по 4 байта.
То что сделает GCC 4.4.1:
public main main proc near ; DATA XREF: _start+17�o var_70 = dword ptr -70h var_6C = dword ptr -6Ch var_68 = dword ptr -68h i_2 = dword ptr -54h i = dword ptr -4 push ebp mov ebp, esp and esp, 0FFFFFFF0h sub esp, 70h mov [esp+70h+i], 0 ; i=0 jmp short loc_804840A loc_80483F7: mov eax, [esp+70h+i] mov edx, [esp+70h+i] add edx, edx ; edx=i*2 mov [esp+eax*4+70h+i_2], edx add [esp+70h+i], 1 ; i++ loc_804840A: cmp [esp+70h+i], 13h jle short loc_80483F7 mov [esp+70h+i], 0 jmp short loc_8048441 loc_804841B: mov eax, [esp+70h+i] mov edx, [esp+eax*4+70h+i_2] mov eax, offset aADD ; "a[%d]=%d\n" mov [esp+70h+var_68], edx mov edx, [esp+70h+i] mov [esp+70h+var_6C], edx mov [esp+70h+var_70], eax call _printf add [esp+70h+i], 1 loc_8048441: cmp [esp+70h+i], 13h jle short loc_804841B mov eax, 0 leave retn main endp
Пока ничего интересного.
Однако, вот что интересно. Индексация массива это просто массив[индекс]. Возможно, если вы присмотритесь к коду, в цикле печати значений массива через printf() вы не увидите проверок индекса, меньше ли он двадцати? А что будет если он будет больше двадцати? Эта одна из особенностей Си, за которую его, собственно, ругают.
Вот код который и компилится и работает:
#include <stdio.h> int main() { int a[20]; int i; for (i=0; i<20; i++) a[i]=i*2; printf ("a[100]=%d\n", a[100]); return 0; };
Вот в это (MSVC 2010):
_TEXT SEGMENT _i$ = -84 ; size = 4 _a$ = -80 ; size = 80 _main PROC ; Line 4 push ebp mov ebp, esp sub esp, 84 ; 00000054H ; Line 8 mov DWORD PTR _i$[ebp], 0 jmp SHORT $LN3@main $LN2@main: mov eax, DWORD PTR _i$[ebp] add eax, 1 mov DWORD PTR _i$[ebp], eax $LN3@main: cmp DWORD PTR _i$[ebp], 20 ; 00000014H jge SHORT $LN1@main ; Line 9 mov ecx, DWORD PTR _i$[ebp] shl ecx, 1 mov edx, DWORD PTR _i$[ebp] mov DWORD PTR _a$[ebp+edx*4], ecx jmp SHORT $LN2@main $LN1@main: ; Line 11 mov eax, DWORD PTR _a$[ebp+400] push eax push OFFSET $SG2460 call _printf add esp, 8 ; Line 13 xor eax, eax ; Line 14 mov esp, ebp pop ebp ret 0 _main ENDP
У меня оно при запуске выдало вот это:
a[100]=760826203
Это просто что-то, что волею случая лежало в стеке рядом с массивом, через 400 байт от его первого элемента.
Действительно, а как могло бы быть иначе? Иначе, компилятору нужно было бы встроить какой-то код, где каждый раз проверять индекс на соответствие пределам массива, что дополнительные затраты по времени работы.
Итак, мы прочитали какое-то число из стека явно нелегально, а что если мы запишем? Именно.
Вот что мы пишем:
#include <stdio.h> int main() { int a[20]; int i; for (i=0; i<30; i++) a[i]=i; return 0; };
И вот что имеем на ассемблере:
_TEXT SEGMENT _i$ = -84 ; size = 4 _a$ = -80 ; size = 80 _main PROC ; Line 4 push ebp mov ebp, esp sub esp, 84 ; 00000054H ; Line 8 mov DWORD PTR _i$[ebp], 0 jmp SHORT $LN3@main $LN2@main: mov eax, DWORD PTR _i$[ebp] add eax, 1 mov DWORD PTR _i$[ebp], eax $LN3@main: cmp DWORD PTR _i$[ebp], 30 ; 0000001eH jge SHORT $LN1@main ; Line 9 mov ecx, DWORD PTR _i$[ebp] mov edx, DWORD PTR _i$[ebp] ; явный промах компилера. эта команда лишняя mov DWORD PTR _a$[ebp+ecx*4], edx ; а здесь в качестве второго операнда подошел бы ECX jmp SHORT $LN2@main $LN1@main: ; Line 11 xor eax, eax ; Line 12 mov esp, ebp pop ebp ret 0 _main ENDP
Запускаете скомпиленную прогу, и она падает. Немудрено. Но давайте теперь узнаем, где именно.
Отладчик я уже давно не использую, так как надоело для всяких мелких задач вроде подсмотреть состояние регистров, запускать что-то, двигать мышей, итд. Поэтому я написал очень минималистическую утилиту для себя, generic tracer, коей обхожусь.
Помимо всего прочего, я могу использовать мою утилиту просто чтобы посмотреть где и какое исключение произошло. Итак, пробую:
generic tracer 0.4 (WIN32), http://conus.info/gt New process: C:\PRJ\...\1.exe, PID=7988 EXCEPTION_ACCESS_VIOLATION: 0x15 (<symbol (0x15) is in unknown module>), ExceptionInformation[0]=8 EAX=0x00000000 EBX=0x7EFDE000 ECX=0x0000001D EDX=0x0000001D ESI=0x00000000 EDI=0x00000000 EBP=0x00000014 ESP=0x0018FF48 EIP=0x00000015 FLAGS=PF ZF IF RF PID=7988|Process exit, return code -1073740791
Итак, следите внимательно за регистрами.
Исключение произошло по адресу 0x15. Это явно нелегальный адрес для кода. Мы там как-то очутились, причем, сами того не хотели. Интересен также тот факт что в EBP хранится 0x14, а в ECX и EDX - 0x1D.
И еще немного изучим разметку стека.
После того как управление передалось в _main, в стек было сохранено значение EBP. Затем, для массива + переменной i было выделено 84 байта. Это (20+1)*sizeof(int). ESP сейчас указывает на переменную _i в локальном стеке и при следующем PUSH, что-либо заталкиваемое в стек появится рядом с _i.
Вот так выглядит стек пока мы находится внутри _main:
ESP: 4 байта для i ESP+4: 80 байт для массива a[20] ESP+84 сохраненное EBP ESP+88 адрес возврата
Команда a[19]=чего_нибудь записывает последний int в пределах массива. Команда a[20]=чего_нибудь записывает чего_нибудь на место где лежит сохраненный EBP. Обратите внимание на состояние регистров на момент падения процесса. В нашем случае, в 20-й элемент записалось значение 20. И вот все дело в том, что заканчиваясь, функция восстанавливала значение EBP, и 20 в десятичной системе это как раз 0x14. Далее выполнилась инструкция RET, которая на самом деле POP EIP. Она вытащила из стека адрес возврата (это адрес в функции, которая вызвала _main), а там было записано 21 в десятичной системе, то есть 0x15. И вот процессор оказался по этому адресу, но кода там нет, так что случилось исключение.
Добро пожаловать! Это называется buffer overflow.
Замените массив int на массив char, создайте специальную строку, просуньте её в ту софту, в ту функцию, которая не проверяя длину строки запишет её в слишком короткий буфер, и вы сможете указать программе, по какому именно адресу перейти. Не все так просто в реальности, конечно, но началось все с этого.
http://en.wikipedia.org/wiki/Stack_buffer_overflow
Однако, в наше время пытаются бороться с этой напастью, не взирая на безалаберность кодеров. В MSVC есть опции вроде:
/RTCs Stack Frame runtime checking /GZ Enable stack checks (/RTCs)
Описания защит, которые компилятор может вставлять в код:
http://en.wikipedia.org/wiki/Buffer_overflow_protection
Один из методов, это в начале функции вставлять в область локальных переменных некоторое случайное значение и перед выходом это число проверять. И если проверка не прошла, то не выполнять инструкцию RET а остановиться. Процесс зависнет, но это лучше чем удаленная атака на ваш хост.
Попробуем то же самое в GCC 4.4.1. У нас выходит такое:
public main main proc near a = dword ptr -54h i = dword ptr -4 push ebp mov ebp, esp sub esp, 60h mov [ebp+i], 0 jmp short loc_80483D1 loc_80483C3: mov eax, [ebp+i] mov edx, [ebp+i] mov [ebp+eax*4+a], edx add [ebp+i], 1 loc_80483D1: cmp [ebp+i], 1Dh jle short loc_80483C3 mov eax, 0 leave retn main endp
Запуск этого в Linux выдаст: Segmentation fault.
Если запустить полученное в отладчике GDB, получим:
(gdb) r Starting program: /home/dennis/RE/1 Program received signal SIGSEGV, Segmentation fault. 0x00000016 in ?? () (gdb) info registers eax 0x0 0 ecx 0xd2f96388 -755407992 edx 0x1d 29 ebx 0x26eff4 2551796 esp 0xbffff4b0 0xbffff4b0 ebp 0x15 0x15 esi 0x0 0 edi 0x0 0 eip 0x16 0x16 eflags 0x10202 [ IF RF ] cs 0x73 115 ss 0x7b 123 ds 0x7b 123 es 0x7b 123 fs 0x0 0 gs 0x33 51 (gdb)
Значения регистров немного другие чем в примере win32, это потому что разметка стека чуть другая.
Еще немного о массивах
Теперь понятно, почему нельзя написать в исходнике что-то вроде:
void f(int size) { int a[size]; ... };
Все просто потому, чтобы выделять место под массив в локальном стеке или же сегменте данных (если массив глобальный), компилятору нужно знать его размер, чего он, на стадии компиляции, разумеется знать не может.
Если вам нужен массив произвольной длины, то выделите столько через malloc(), затем обращайтесь к выделенному блоку байт как к массиву того типа, который вам нужен.
Многомерные массивы
Многомерный массив выглядит внутри так же как и линейный.
Попробуем:
#include <stdio.h> int a[10][20][30]; void insert(int x, int y, int z, int value) { a[x][y][z]=value; };
В итоге (MSVC 2010):
_DATA SEGMENT COMM _a:DWORD:01770H _DATA ENDS PUBLIC _insert _TEXT SEGMENT _x$ = 8 ; size = 4 _y$ = 12 ; size = 4 _z$ = 16 ; size = 4 _value$ = 20 ; size = 4 _insert PROC ; Line 6 push ebp mov ebp, esp ; Line 7 mov eax, DWORD PTR _x$[ebp] imul eax, 2400 ; 00000960H mov ecx, DWORD PTR _y$[ebp] imul ecx, 120 ; 00000078H lea edx, DWORD PTR _a[eax+ecx] mov eax, DWORD PTR _z$[ebp] mov ecx, DWORD PTR _value$[ebp] mov DWORD PTR [edx+eax*4], ecx ; Line 8 pop ebp ret 0 _insert ENDP _TEXT ENDS
В принципе, ничего удивительного. В insert() для индексирования нужного элемента массива, три входных аргумента перемножаются так, чтобы представить массив трехмерным.
GCC 4.4.1:
public insert insert proc near x = dword ptr 8 y = dword ptr 0Ch z = dword ptr 10h value = dword ptr 14h push ebp mov ebp, esp push ebx mov ebx, [ebp+x] mov eax, [ebp+y] mov ecx, [ebp+z] lea edx, [eax+eax] mov eax, edx shl eax, 4 sub eax, edx imul edx, ebx, 600 add eax, edx lea edx, [eax+ecx] mov eax, [ebp+value] mov dword ptr ds:a[edx*4], eax pop ebx pop ebp retn insert endp
