Лекция
Привет, Вы узнаете о том , что такое переполнение стека, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое переполнение стека, стековый кадр , настоятельно рекомендую прочитать все из категории Алгоритмизация и программирование. Структурное программирование. Язык C.
Стековый кадр (фрейм) (англ. stack frame) — механизм передачи аргументов и выделения временной памяти (в процедурах языков программирования высокого уровня) с использованием системного стека; визуальное представление данных подпрограммы в стеке вызовов.
Типичный случай использования стека языком высокого уровня на примере вызова процедуры с аргументами «A, B, C» (с соглашением вызова cdecl) в сравнении с языком ассемблера
Обычно системный стек используется для сохранения адресов возврата при вызове подпрограмм, а также сохранения/восстановления значений регистров процессора.
При вызове процедуры аргументы отправляются в стек, и только потом производится вызов подпрограммы. Таким образом, процедура получает стек, на вершине которого лежит адрес возврата, а под ним — аргументы, с которыми она была вызвана.
При возвращении из процедуры (или после него, см. ниже) аргументы должны быть сняты со стека.
Если указатель стека сместить «выше» (в сторону младших адресов), то часть памяти в стеке окажется незадействованной (в том числе и при вызове третьей процедуры) и может использоваться процедурой по своему усмотрению, вплоть до момента возврата в вызвавшую ее процедуру. Таким образом, языки высокого уровня организуют переменные, существующие только внутри процедуры (язык Си называет их «автоматическими»).
Перед возвратом процедура должна вернуть указатель стека в оригинальное положение (то есть на адрес возврата).
Различные компиляторы языков высокого уровня по-разному подходят к организации стекового кадра в зависимости от особенностей аппаратной платформы и стандартов конкретного языка. Основные отличия касаются порядка передачи аргументов в стек и их снятия со стека при возврате.
Стековый кадр — удобная технология выделения временной памяти для передачи произвольного числа аргументов или внутреннего использования. Однако она имеет ряд недостатков.
Передача данных через память без необходимости замедляет выполнение программы (по сравнению с программами на языке ассемблера, в которых большинство аргументов и временных данных размещают в регистрах процессора).
Для уменьшения обращений к локальным переменным программа оптимизируется при компиляции для использования регистров вместо переменных в памяти или для хранения их промежуточных значений.
Некоторые языки используют соглашения вызова, поддерживающие передачу целочисленных аргументов через регистры.
Стековый кадр перемежает данные приложения с критическими данными — указателями, значениями регистров и адресами возврата. Это, в сочетании с архитектурными особенностями некоторых процессоров (а именно — направлением роста стека), делает злонамеренное перекрытие критических данных в результате переполнения буфера очень легко достижимым (разумеется, прежде всего, программа должна содержать ошибку, которая позволит выполнить переполнение).
Такое «неудачное», с точки зрения переполнения буфера, направление роста машинного стека имеют аппаратные платформы: X86.
Атака по переполнению буфера в стеке обычно реализуется следующим образом:
В программном обеспечении переполнение стека (англ. Об этом говорит сайт https://intellect.icu . stack overflow) возникает, когда в стеке вызовов хранится больше информации, чем он может вместить. Обычно емкость стека задается при старте программы/потока. Когда указатель стека выходит за границы, программа аварийно завершает работу.
Эта ошибка случается по трем причинам.
Простейший пример бесконечной рекурсии на Си:
int foo() {
return foo();
}
Функция будет вызывать сама себя, расходуя пространство в стеке, пока стек не переполнится и не случится ошибка сегментации.
Это рафинированный пример, и в реальном коде бесконечная рекурсия может появиться по двум причинам:
Частая причина бесконечной рекурсии — когда при каких-то крайних непроверенных обстоятельствах условие окончания рекурсии вообще не сработает.
int factorial (int n)
{
if (n == 0)
return 1;
return n * factorial(n - 1);
}
Программа уйдет в глубокую (4 млрд вызовов) рекурсию при отрицательном n.
Многие языки делают оптимизацию, именуемую «хвостовая рекурсия». Рекурсия, находящаяся в конце функции, превращается в цикл и не расходует стека. Если такая оптимизация сработает, вместо переполнения стека будет зацикливание.
Программист может написать рекурсию и ненамеренно — например, когда одну и ту же функциональность выполняют несколько перегруженных функций, и одна вызывает другую.
int Obj::getData(int index, bool& isChangeable)
{
isChangeable = true;
return getData(index);
}
int Obj::getData(int index)
{
bool noMatter;
return getData(index, noMatter);
}
В интерфейсных фреймворках наподобие Qt и VCL рекурсия может случиться, если в обработчике, например, изменения поля программист сам же это поле и изменит.
Уничтожить односвязный список можно таким кодом:
void destroyList(struct Item* it)
{
if (it == NULL)
return;
destroyList(it->next);
free(it);
}
Этот алгоритм, если список не испорчен, теоретически выполнится за конечное время, затребовав при этом O(n) стека. Разумеется, при длинном списке программа откажет. Возможные решения:
Третья большая причина переполнения стека — одноразовое выделение огромного количества памяти крупными локальными переменными. Многие авторы рекомендуют выделять память, превышающую несколько килобайт, в «куче», а не на стеке.
Пример на Си:
int foo() {
double x[1000000];
}
Массив занимает 8 мегабайт памяти; если в стеке нет такого количества памяти, случится переполнение.
Все, что уменьшает эффективный размер стека, увеличивает риск переполнения. Потоки обычно берут стека меньше, чем основная программа — поэтому программа может работать в однопоточном режиме и отказывать в многопоточном. Работающие в режиме ядра подпрограммы часто пользуются чужим стеком, поэтому при программировании в режиме ядра стараются не применять рекурсию и большие локальные переменные.
Исследование, описанное в статье про переполнение стека, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое переполнение стека, стековый кадр и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмизация и программирование. Структурное программирование. Язык C
Из статьи мы узнали кратко, но содержательно про переполнение стека
Комментарии
Оставить комментарий
Алгоритмизация и программирование. Структурное программирование. Язык C
Термины: Алгоритмизация и программирование. Структурное программирование. Язык C