#+SETUPFILE: https://fniessen.github.io/org-html-themes/org/theme-readtheorg.setup #+LANG: ru #+TITLE: Семинар 7: Оптимизации, уязвимость стека В этом семинаре мы изучим некоторые оптимизации, которые производят =gcc= и другие компиляторы языка С, а также войдём в роль хакера и сломаем несколько программ. * Оптимизации ** Инструменты Научитесь пользоваться [[http://godbolt.org]] для компиляции C и просмотра ассемблерного кода. *Вопрос* Как посмотреть флаги компиляции в godbolt? *Вопрос* Что означают флаги: =-O0=, =-O1=, =-O2=, =-Os=? *Вопрос* Скомпилируйте [[https://gitlab.se.ifmo.ru/programming-languages/cse-programming-languages-fall-2022/main/-/blob/master/seminar-5/printer.c][программу]] =printer.c= из семинара 5 с ключами =-O0= и =-O3= (в Godbolt можно создать две вкладки с компиляторами рядом и сравнить листинги). ** Volatile Если добавить к типу модификатор =volatile=, то действия с такими данными гарантированно будут произведены. Если из переменной в коде есть чтение, то чтение обязательно случится, а если будет запись --- произойдёт и она. Для остальных переменных это неверно: например, чтения переменных из памяти не обязательно произойдут, например, зачем читать из памяти константу если можно напрямую подставить её значение? *Вопрос* Посмотрите как с увеличением уровня оптимизаций пропадают чтения из памяти: #+begin_src c /* volatile.c */ #include void print_int(int x) { printf("%d", x); } int main() { int x = 42; volatile int y = 42; print_int(x); print_int(y); } #+end_src *Вопрос* пометьте функцию =print_int= как =static=. Что произошло в оптимизированном коде и почему? ** Пролог и эпилог При трансляции функций нередко используются понятия /пролога/ и /эпилога/ --- шаблонных фрагментов ассемблерного кода в начале и конце функции. Их цель --- установка регистра =rbp= так, чтобы он указывал на начало стекового фрейма, где лежат все интересные для функции данные. Пролог устанавливает его, как правило следующей последовательностью инструкций: #+begin_src asm push rbp mov rbp, rsp sub rsp, <сколько выделить байтов в стеке> #+end_src Эпилог возвращает =rbp= в исходное состояние. Напоминаем, что =rbp= --- callee-saved регистр. #+begin_src asm mov rsp, rbp ; отмотать стек в исходное состояние pop rbp ; восстановить rbp ret #+end_src Иногда используется также специализированная инструкция =leave=. *Вопрос* Что делает эта инструкция? ** Red zone Указатель на вершину стека =rsp= делит память на две части: в старших адресах лежит сам стек, в младшие он растёт. Мы привыкли к тому, что нельзя обращаться к младшей части памяти и что-то там хранить. Однако соглашение вызова на самом деле допускает использование части "рядом" со стеком, а именно 128 байт от =rsp= в область младших адресов: #+begin_src | | | ... | | | ├--------┤ ← rsp-128 | | | red | | zone | | | ├---^----┤ ← rsp | stack | | | #+end_src Чтобы использовать red zone необходимо, чтобы функция не вызывала другие функции. Если функция не вызывает другие функции и выделяет N байт для хранения данных в стеке, то хранить она может на самом деле N+128 байт. Рассмотрим следующий файл: #+begin_src c /* prologue-epilogue.c */ int maximum(int a, int b) { char buffer[4096]; buffer[0] = 0x7; if (a < b) return b; return a; } int main(void) { int x = maximum(42, 999); return 0; } #+end_src *Вопрос* Скомпилируйте его без оптимизаций и объясните содержимое функции =maximum=. Почему =rsp= уменьшается на это число? ** Предподсчёт значений Скомпилируйте следующий код с максимальным уровнем оптимизации и объясните, откуда там берётся строка для =printf=. #+begin_src c /* precompute.c */ #include #include int main (){ char buff[1024] = {0}; strcat(buff, "hello"); strcat(buff, " world"); printf("%s", buff); } #+end_src ** Хвостовая рекурсия *Вопрос* Вспомните, почему пару инструкций =call= + =ret= можно заменить на =jmp=, например: #+begin_src asm ... call f ret f: ... ret ; то же, что и: ... jmp f f: ... ret #+end_src Скомпилируйте и запустите следующий код: #+begin_src c /* tail-rec.c */ #include #include #include #include void print_size(size_t i) { printf("%zu" , i); } struct list { int64_t elem; struct list *next; }; struct list *c(int64_t head, struct list *tail) { struct list *h = (struct list *)malloc(sizeof(struct list)); h->elem = head; h->next = tail; return h; } size_t list_length(struct list const *l) { if (!l) return 0; return 1 + list_length(l->next); } int main(int argc, char **argv) { const size_t len = 1024 * 1024; struct list *lst = NULL; for( size_t i = 0; i < len; i++) { lst = c(i, lst); } print_size(list_length(lst)); return 0; } #+end_src Что выведется на экран? Объясните это поведение. *Задание 1* Как можно переписать функцию (какую?) чтобы программа корректно считала длину длинного списка? ** Copy elision Скомпилируйте следующий код с максимальным уровнем оптимизации. #+begin_src c /* return-value.c */ #include struct string_buffer { char data[1024]; }; __attribute__((noinline)) struct string_buffer sb_init() { return (struct string_buffer){.data = "hey"}; } volatile struct string_buffer sb; int main() { sb = sb_init(); printf("%s", sb.data); return 0; } #+end_src Объясните, зачем в функцию =sb_init= передаётся аргумент, хотя по сигнатуре у неё параметров нет. ** Restrict Скомпилируйте следующий код с максимальным уровнем оптимизации. #+begin_src c /* restrict-0.c */ void f(int *x, int *add) { *x += *add; *x += *add; } #+end_src Эта функция прибавляет к первому аргументу второй два раза; оба аргумента являются указателями на числа. Мы могли бы прибавить к первому аргументу удвоенное значение второго и это было бы быстрее. Посмотрите внимательно на ассемблерную функцию; есть ли там эта оптимизация? Если да, то почему она верна, если нет, то почему неверна? Модифицируйте код следующим образом: #+begin_src c /* restrict-1.c */ void f(int *restrict x, int *restrict add) { *x += *add; *x += *add; } #+end_src Как изменится скомпилированный код с оптимизациями? Прочитайте стр. 281--282 в "Low-level programming" смысл ключевого слова =restrict= и объясните его влияние на код. * Smash this stack ** Уязвимость форматного вывода *Вопрос* Как в функцию передаются следующие аргументы после шестого? Скомпилируйте эту программу. #+begin_src c /* printf.c */ #include int main(void) { char buffer[1024]; fgets( buffer, 1024, stdin); printf( buffer ); return 0; } #+end_src Запустите её, передавая ей строчки вида ="%x %x"=, ="%x %x %x"= и т.д. Что это за числа? Прочтите стр. 285--287 в "Low-level programming". * Перезапись адреса возврата Напомним, что адрес возврата лежит в стеке на границе стекового фрейма, сразу после сохранённого значения =rbp= (если оно сохраняется). *Вопрос* Что такое ASLR (address space layout randomization)? Отключите ASLR следующей командой: #+begin_src echo 0 | sudo tee /proc/sys/kernel/randomize_va_space #+end_src Рассмотрим следующий код. #+begin_src c /* stack-smash.c */ #include #include struct user { const char *name, *password; } const users[] = {{"Cat", "Meowmeow"}, {"Skeletor", "Nyarr"}}; void print_users() { printf("Users:\n"); for (size_t i = 0; i < sizeof(users) / sizeof(struct user); i++) { printf("%s: %s\n", users[i].name, users[i].password); } } void fill(FILE *f, char *where) { size_t read_total = 0; for (;;) { size_t read = fread(where + read_total, 1, 1, f); if (!read) break; else read_total += read; } } void vulnerable(FILE *f) { char buffer[8]; fill(f, buffer); } int main(int argc, char **argv) { vulnerable(stdin); puts("nothing happened"); } #+end_src Скомпилируйте его вот так (это отключает некоторые механизмы защиты): #+begin_src bash gcc -fno-stack-protector -z execstack -no-pie -g -o stack-smash stack-smash.c #+end_src Программа принимает на вход символы, записывает их в стековый буфер и ничего с ними не делает, выводя =Nothing happened=. Но в ней есть интересная злоумышленнику функция, которая печатает содержимое базы пользователей, в том числе их пароли. Злоумышленник может воспользоваться тем, что программист не проверяет, насколько много данных прислал злоумышленник и влезут ли они в буфер. Если же они не влезут, то программа написана так, что начнут перезаписываться... сохранённые =rbp= и адрес возврата. Злоумышленник может подавать на вход программе любые символы. Если вам необходимо передать нулевые символы или символы с необычными кодами, вы можете использовать =echo= вот так: #+begin_src echo -n -e "\x11\x40\x00\x99" # четыре байта с кодами 11 40 0 и 99 (16-ричными) #+end_src *Задание 2* Попробуйте переписать адрес возврата так, чтобы вместо возвращения из =vulnerable= в =main= запустить функцию =print_users=. Программа может аварийно завершиться, главное -- чтобы функция отработала и вывела на экран список пользователей и их паролей. *Задание 3* Исправьте уязвимость. [[img/output.png]] Вы не можете переписывать программу, можете только подавать ей на вход разные данные. Вы *можете* изучать скомпилированный файл с помощью =gdb=, запускать его, смотреть содержимое памяти. Также можно пользоваться =objdump= или =readelf=, =nm= и любыми иными средствами для узнавания адреса =print_users=. Не забывайте, что он может меняться после каждой перекомпиляции! Также не забудьте, что в памяти многобайтовые числа, в том числе адреса, хранятся в соответствии с Little Endian. ** Уязвимость форматного ввода Аналогичная уязвимость присутствует и при чтении строк привычной многим функцией =scanf= или =fscanf=. Рассмотрим следующий код: #+begin_src c /* check-pwd.c */ #include #include #include int check_password(FILE *f, const char *password) { char buffer[10]; int okay = 0; fscanf(f, "%s", buffer); if (strcmp(buffer, password) == 0) okay = 1; return okay; } int main(int argc, char **argv) { if (check_password(stdin, "password")) puts("Access granted."); else puts("Wrong password."); } #+end_src Мы читаем пароль пароль используя функцию =fscanf= и спецификатор =%s= в буфер =buffer= никак не ограничивая количество читаемых символов. Далее прочитанный пароль сравнивается с сохраненным и устанавливается флаг =okay=. При переполнении буффера может произойти замена значаения флага и пароль будет считаться введенным верно. *Задание 4* Исправьте данный код так, чтобы исключить потенциальную уязвимость.