442 lines
15 KiB
Org Mode
442 lines
15 KiB
Org Mode
#+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 <stdio.h>
|
||
|
||
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 <stdio.h>
|
||
#include <string.h>
|
||
|
||
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 <inttypes.h>
|
||
#include <malloc.h>
|
||
#include <stddef.h>
|
||
#include <stdio.h>
|
||
|
||
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 <stdio.h>
|
||
|
||
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 <stdio.h>
|
||
|
||
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 <stdio.h>
|
||
#include <stdlib.h>
|
||
|
||
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 <stdio.h>
|
||
#include <stdlib.h>
|
||
#include <string.h>
|
||
|
||
|
||
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* Исправьте данный код так, чтобы исключить потенциальную уязвимость.
|