Ошибка переполнения стека может приводить к

Стек (или магазин) — структура данных в программировании, работающая по принципу магазина с патронами: последний помещеннный в него объект, обрабатывается первым.

Приработе со стекам часто приходится сталкиваться с двумя типичными ошибками: переполненем стека и опустошением стека.

Переполнение стека (stack overflow) — одна из типичных ошибок при работе со стеком, состоящая в попытке добавить в стек элемент, когда память, отведенная для хранения стека полностью занята.

В случае, если стек моделируется на базе массива, добавляемое значение может быть записано за пределы отведенного для хранения стека памяти, что приведет к повреждению другие данных, обрабатываемых программой. Это нередко приводит к трудно выявляемым ошибками типа «порчи памяти». Поэтому при реализации стека на основе массива необходимо перед каждой операцией добавления элемента проверять, не переполнен ли стек.

Если стек моделируется на связанном списке, то переполнение стека обычно возникает только при исчерпании доступной для программы оперативной памяти. В этом случае программа завершается с диагностикой «Недостаточно памяти».

Причиной переполнения стека обычно является зацикливание на участке программы, где количество операций добавления в стек превышает количество операций извлечения из стека. Другая причина переполнения стека — слишком большая глубина рекурсивных вызовов подпрограмм, что может говорить о неудачно выбранном алгоритме решения задачи.

Опустошение стека (stack underflow) — другая типичная ошибка при работе со стеком, состоящая в попытке извлечь значение пустого стека.

В случае, если стек моделируется на базе массива, то при его опустошении в качестве результата операции может быть возвращено случайное («мусорное») значение из области памяти, не отведенной для хранения стека. Это скорее всего приведет к неверной работе программы. Кроме того, при попытке пополнить стек после его ошибочного опустошения, данные могут быть записаны в постороннюю область памяти, что приведет к тем же непредсказуемым последствиям, что и переполнение стека.

Если стек моделируется на связанном списке, то ошибка опустошения стека выражается в попытке обращения по недействительному указателю. Обычно это немедленно приводит к завершению программы с диагностикой «защита памяти».

Причиной опустошения стека обычно является зацикливание на участке программы, где количество операций извлечения из стека превышает количество операций добавления в стек. Другая причина переполнения стека — несогласованность операций пополнения и извлечения из стека. Например, если подпрограмма ожидает получить больше параметров, чем ей передается при вызове через стек.

Чтобы избегать ошибок при работе со стеком нужно следовать двум правилам.

1. При реализации операций со стеком всегда проверять, не приведет ли затребованное действие к переполнению или опустошению стека. Если нарушение обнаружено, то выдавать соответствующую диагностику и отказывать в выполнении операции.

2. При каждой операции использования стека проверять успешность ее, выполнения и в случае возникновения ошибки принимать соответствующие меры.

Описанные правила безопасности приводят к тому, что программный код оказывается перегружен проверками. По этой причине более эффективным методом является уведомление об ошибках в работе со стеком при помощи механизма исключений или прерываний (например, конструкция  try … throw в языке С++).

Дополнительно в базе данных Генона: 

• Что такое стек в программировании?
• Для чего используются указатели в программировании?

Ссылки по теме:

• cyberforum.ru — реализация стека на С++ с использованием исключений 
• ru.wikipedia.org — Википедия: Переполнение буфера
• codenet.ru — рассматривается уязвимость Windows за счет использования переполнения стека  
• sdteam.com — статья «Переполнения стека»
• xakep.ru — статья «Переполнение буфера в стеке», Хакер, №2, 2003

From Wikipedia, the free encyclopedia

In software, a stack overflow occurs if the call stack pointer exceeds the stack bound. The call stack may consist of a limited amount of address space, often determined at the start of the program. The size of the call stack depends on many factors, including the programming language, machine architecture, multi-threading, and amount of available memory. When a program attempts to use more space than is available on the call stack (that is, when it attempts to access memory beyond the call stack’s bounds, which is essentially a buffer overflow), the stack is said to overflow, typically resulting in a program crash.^[1]

Causes[edit]

Infinite recursion[edit]

The most-common cause of stack overflow is excessively deep or infinite recursion, in which a function calls itself so many times that the space needed to store the variables and information associated with each call is more than can fit on the stack.^[2]

An example of infinite recursion in C.

int foo() 
{
     return foo();
}

The function foo, when it is invoked, continues to invoke itself, allocating additional space on the stack each time, until the stack overflows resulting in a segmentation fault.^[2] However, some compilers implement tail-call optimization, allowing infinite recursion of a specific sort—tail recursion—to occur without stack overflow. This works because tail-recursion calls do not take up additional stack space.^[3]

Some C compiler options will effectively enable tail-call optimization; for example, compiling the above simple program using gcc with -O1 will result in a segmentation fault, but not when using -O2 or -O3, since these optimization levels imply the -foptimize-sibling-calls compiler option.^[4] Other languages, such as Scheme, require all implementations to include tail-recursion as part of the language standard.^[5]

Very deep recursion[edit]

A recursive function that terminates in theory but causes a call stack buffer overflow in practice can be fixed by transforming the recursion into a loop and storing the function arguments in an explicit stack (rather than the implicit use of the call stack). This is always possible because the class of primitive recursive functions is equivalent to the class of LOOP computable functions. Consider this example in C++-like pseudocode:

void function (argument) 
{
  if (condition)
    function (argument.next);

}

stack.push(argument);
while (!stack.empty())
{
  argument = stack.pop();
  if (condition)
    stack.push(argument.next);
}

A primitive recursive function like the one on the left side can always be transformed into a loop like on the right side.

A function like the example above on the left would not be a problem in an environment supporting tail-call optimization; however, it is still possible to create a recursive function that may result in a stack overflow in these languages. Consider the example below of two simple integer exponentiation functions.

int pow(int base, int exp) {
    if (exp > 0)
        return base * pow(base, exp - 1);
    else
        return 1;
}

int pow(int base, int exp) {
    return pow_accum(base, exp, 1);
}

int pow_accum(int base, int exp, int accum) {
    if (exp > 0)
        return pow_accum(base, exp - 1, accum * base);
    else
        return accum;
}

Both pow(base, exp) functions above compute an equivalent result, however, the one on the left is prone to causing a stack overflow because tail-call optimization is not possible for this function. During execution, the stack for these functions will look like this:

pow(5, 4)
5 * pow(5, 3)
5 * (5 * pow(5, 2))
5 * (5 * (5 * pow(5, 1)))
5 * (5 * (5 * (5 * pow(5, 0))))
5 * (5 * (5 * (5 * 1)))
625

pow(5, 4)
pow_accum(5, 4, 1)
pow_accum(5, 3, 5)
pow_accum(5, 2, 25)
pow_accum(5, 1, 125)
pow_accum(5, 0, 625)
625

Notice that the function on the left must store in its stack exp number of integers, which will be multiplied when the recursion terminates and the function returns 1. In contrast, the function at the right must only store 3 integers at any time, and computes an intermediary result which is passed to its following invocation. As no other information outside of the current function invocation must be stored, a tail-recursion optimizer can «drop» the prior stack frames, eliminating the possibility of a stack overflow.

Very large stack variables[edit]

The other major cause of a stack overflow results from an attempt to allocate more memory on the stack than will fit, for example by creating local array variables that are too large. For this reason some authors recommend that arrays larger than a few kilobytes should be allocated dynamically instead of as a local variable.^[6]

An example of a very large stack variable in C:

int foo() 
{
     double x[1048576];
}

On a C implementation with 8 byte double-precision floats, the declared array consumes 8 megabytes of data; if this is more memory than is available on the stack (as set by thread creation parameters or operating system limits), a stack overflow will occur.

Stack overflows are made worse by anything that reduces the effective stack size of a given program. For example, the same program being run without multiple threads might work fine, but as soon as multi-threading is enabled the program will crash. This is because most programs with threads have less stack space per thread than a program with no threading support. Because kernels are generally multi-threaded, people new to kernel development are usually discouraged from using recursive algorithms or large stack buffers.^[7]

See also[edit]

• Buffer overflow
• Call stack
• Heap overflow
• Stack buffer overflow
• Double fault

References[edit]

External links[edit]

• The reasons why 64-bit programs require more stack memory Archived 2017 November 4 at the Wayback Machine

Другие ответы довольно хорошо охватывали ПК. Я затрону некоторые проблемы во встроенном мире.

Встроенный код имеет нечто похожее на segfault. Код хранится в каком-то энергонезависимом хранилище (как правило, в эти дни, но в некотором роде ROM или PROM). Для этого требуется специальные операции по его настройке; нормальный доступ к памяти может считываться из него, но не записывать на него. Кроме того, встроенные процессоры обычно имеют большие разрывы в своих картах памяти. Если процессор получает запрос на запись для памяти, который доступен только для чтения, или если он получает запрос на чтение или запись для адреса, который физически не существует, процессор обычно выдает аппаратное исключение. Если у вас подключен отладчик, вы можете проверить состояние системы, чтобы найти, что пошло не так, как с дампом ядра.

Там нет гарантии, что это произойдет для. Стек можно разместить в любом месте в ОЗУ, и это обычно будет рядом с другими переменными. Результатом, как правило, является повреждение этих переменных.

Если ваше приложение также использует кучу (динамическое распределение), то обычно назначается раздел памяти, где стек начинается в нижней части этого раздела и расширяется вверх, а куча начинается в верхней части этого раздела и расширяется вниз. Понятно, что это означает, что динамически распределенные данные станут первой жертвой.

Если вам не повезло, вы можете даже не заметить, когда это произойдет, а затем вам нужно выяснить, почему ваш код не ведет себя правильно. В самом ироническом случае, если переписываемые данные являются указателями, тогда вы все равно можете получить аппаратное исключение, когда указатель попытается получить доступ к недопустимой памяти, но это будет через некоторое время после, и естественным предположением будет обычно то, что оно ошибка в вашем коде.

Встроенный код имеет общий шаблон, чтобы справиться с этим, то есть «водяным знаком» стека, инициализируя каждый байт до известного значения. Иногда компилятор может это сделать; или иногда вам может потребоваться реализовать его самостоятельно в стартовом коде перед main(). Вы можете оглянуться назад с конца стека, чтобы найти, где он больше не установлен для этого значения, и в этот момент вы знаете отметку с высоким уровнем воды для использования стека; или, если все это неверно, вы знаете, что у вас переполнение. Общепринятым (и хорошей практикой) для встроенных приложений является постоянное голосование в качестве фоновой операции и возможность сообщать об этом в диагностических целях.

Предоставив возможность отслеживать использование стека, большинство компаний установит приемлемую наихудшую маржу, чтобы избежать переполнения. Обычно это где-то от 75% до 90%, но всегда будет запас. Это не только позволяет предположить, что есть худший худший случай, который вы еще не видели, но также облегчает жизнь для будущего развития, когда нужно добавить новый код, который использует больше стека.

В программном обеспечении переполнение буфера стека или переполнение буфера стека происходит, когда программа записывает в адрес памяти в стеке вызовов программы вне предполагаемой структуры данных, которая обычно представляет собой буфер фиксированной длины. Ошибки переполнения буфера стека возникают, когда программа записывает в буфер, расположенный в стеке, больше данных, чем фактически выделено для этого буфера. Это почти всегда приводит к повреждению смежных данных в стеке, а в случаях, когда переполнение было инициировано по ошибке, часто приводит к сбою или неправильной работе программы. Переполнение буфера стека — это тип более общей ошибки программирования, известной как переполнение буфера (или переполнение буфера). Переполнение буфера в стеке с большей вероятностью нарушит выполнение программы, чем переполнение буфера в куче, потому что стек содержит адреса возврата для всех активных вызовов функций.

Переполнение буфера стека может быть вызвано намеренно как часть атаки, известной как разбивание стека . Если уязвимая программа работает с особыми привилегиями или принимает данные от ненадежных сетевых узлов (например, веб-сервера ), то ошибка является потенциальной уязвимостью безопасности. Если буфер стека заполнен данными, полученными от ненадежного пользователя, то этот пользователь может повредить стек таким образом, чтобы внедрить исполняемый код в запущенную программу и взять под контроль процесс. Это один из самых старых и надежных методов для злоумышленников получить несанкционированный доступ к компьютеру.

Содержание

• 1 Использование переполнения буфера стека
• 2 Различия, связанные с платформой
  • 2.1 Растущие стеки
• 3 Схемы защиты
  • 3.1 Канарейки стека
  • 3.2 Неисполняемый стек
  • 3.3 Рандомизация
• 4 Примечательные примеры
• 5 См. Также
• 6 Ссылки

Использование буфера стека overflows

Канонический метод использования переполнения буфера на основе стека — перезапись адреса возврата функции указателем на данные, контролируемые злоумышленником (обычно в самом стеке). Это проиллюстрировано с помощью strcpy() в следующем примере:

#include void foo (char * bar) {char c [12]; strcpy (c, bar); // без проверки границ} int main (int argc, char ** argv) {foo (argv [1]); возврат 0; }

Этот код берет аргумент из командной строки и копирует его в локальную переменную стека c. Это отлично работает для аргументов командной строки меньше 12 символов (как вы можете видеть на рисунке B ниже). Любые аргументы длиной более 11 символов приведут к повреждению стека. (Максимальное количество безопасных символов на единицу меньше размера буфера здесь, потому что в языке программирования C строки заканчиваются нулевым байтовым символом. Таким образом, для ввода из двенадцати символов требуется тринадцать байтов для хранения, за вводом следует нулевым байтом контрольного значения. Нулевой байт затем завершается перезаписью области памяти, которая на один байт выходит за пределы буфера.)

Программный стек в foo ()с различными входами:

Обратите внимание, что на рисунке C выше, когда в командной строке указан аргумент размером более 11 байт foo ()перезаписывает данные локального стека, сохраненный кадр указатель, а главное — адрес возврата. Когда foo ()возвращает, он выталкивает адрес возврата из стека и переходит к этому адресу (т.е. начинает выполнять инструкции с этого адреса). Таким образом, злоумышленник перезаписал адрес возврата указателем на буфер стека char c [12], который теперь содержит данные, предоставленные злоумышленником. При фактическом использовании переполнения буфера стека строка «A» вместо этого будет шеллкодом, подходящим для платформы и желаемой функции. Если у этой программы были особые привилегии (например, бит SUID установлен для запуска от имени суперпользователя ), то злоумышленник мог использовать эту уязвимость, чтобы получить привилегии суперпользователя на уязвимой машине.

Злоумышленник также может изменить значения внутренних переменных, чтобы воспользоваться некоторыми ошибками. В этом примере:

#include #include void foo (char * bar) {float My_Float = 10.5; // Адрес = 0x0023FF4C char c [28]; // Addr = 0x0023FF30 // Напечатает 10.500000 printf ("My Float value =% f  n", My_Float); / * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~ Карта памяти: @: c выделенная память #: выделенная память My_Float * c * My_Float 0x0023FF30 0x0023FF4C | | @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.com memcpy поместит 0x1010C042 (little endian) в значение My_Float. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~ * / memcpy (c, bar, strlen (bar)); // без проверки границ... // напечатает 96.031372 printf ("My Float value =% f  n", My_Float); } int main (int argc, char ** argv) {foo ("моя строка слишком длинная !!!!!  x10  x10  xc0  x42"); возврат 0; }

Различия, связанные с платформой

У ряда платформ есть тонкие различия в их реализации стека вызовов, которые могут повлиять на способ работы эксплойта переполнения буфера стека. Некоторые машинные архитектуры хранят адрес возврата верхнего уровня стека вызовов в регистре. Это означает, что любой перезаписанный адрес возврата не будет использоваться до последующего раскручивания стека вызовов. Другой пример специфической для машины детали, которая может повлиять на выбор методов эксплуатации, — это тот факт, что большинство архитектур машин в стиле RISC не допускают невыровненный доступ к памяти. В сочетании с фиксированной длиной для машинных кодов операций это машинное ограничение может сделать переход к технике ESP практически невозможным (за одним исключением, когда программа фактически содержит маловероятный код для явного перехода к регистру стека).

Растущие стеки

В рамках темы переполнения буфера стека часто обсуждается, но редко встречается архитектура, в которой стек растет в противоположном направлении. Это изменение в архитектуре часто предлагается в качестве решения проблемы переполнения буфера стека, поскольку любое переполнение буфера стека, происходящее в том же кадре стека, не может перезаписать указатель возврата. Дальнейшее расследование заявленной защиты показало, что это в лучшем случае наивное решение. Любое переполнение, происходящее в буфере из предыдущего кадра стека, по-прежнему будет перезаписывать указатель возврата и допускать злонамеренное использование ошибки. Например, в приведенном выше примере указатель возврата для fooне будет перезаписан, потому что переполнение фактически происходит внутри фрейма стека для memcpy. Однако, поскольку буфер, который переполняется во время вызова memcpy, находится в предыдущем фрейме стека, указатель возврата для memcpyбудет иметь численно больший адрес памяти, чем буфер. Это означает, что вместо перезаписи указателя возврата для fooбудет перезаписан указатель возврата для memcpy. В лучшем случае это означает, что рост стека в противоположном направлении изменит некоторые детали того, как можно использовать переполнение буфера стека, но это не приведет к значительному сокращению количества уязвимых ошибок.

Схемы защиты

За прошедшие годы был разработан ряд схем целостности потока управления для предотвращения злонамеренной эксплуатации переполнения буфера стека. Обычно их можно разделить на три категории:

• Обнаружение переполнения буфера стека и, таким образом, предотвращение перенаправления указателя инструкции на вредоносный код.
• Предотвращение выполнения вредоносного кода из стека без прямого обнаружения переполнение буфера стека.
• Произвести случайное изменение пространства памяти, чтобы поиск исполняемого кода стал ненадежным.

Стек канареек

Стек канареек, названный по аналогии с канарейкой в ​​угле mine, используются для обнаружения переполнения буфера стека до того, как может произойти выполнение вредоносного кода. Этот метод работает путем помещения небольшого целого числа, значение которого выбирается случайным образом при запуске программы, в памяти непосредственно перед указателем возврата стека. Большинство переполнений буфера перезаписывают память с более низких адресов памяти на более высокие, поэтому, чтобы перезаписать указатель возврата (и, таким образом, получить контроль над процессом), необходимо перезаписать канареечное значение. Это значение проверяется, чтобы убедиться, что оно не изменилось, прежде чем процедура использует указатель возврата в стеке. Этот метод может значительно увеличить сложность использования переполнения буфера стека, поскольку он заставляет злоумышленника получить контроль над указателем инструкции некоторыми нетрадиционными способами, такими как повреждение других важных переменных в стеке.

Невыполняемый стек

Другой подход к предотвращению эксплуатации переполнения буфера стека заключается в применении политики памяти в области памяти стека, которая запрещает выполнение из стека (W ^ X, «Запись XOR Execute»). Это означает, что для выполнения шелл-кода из стека злоумышленник должен либо найти способ отключить защиту выполнения из памяти, либо найти способ разместить полезную нагрузку шелл-кода в незащищенной области памяти. Этот метод становится все более популярным сейчас, когда аппаратная поддержка флага отсутствия выполнения доступна в большинстве процессоров для настольных ПК.

Хотя этот метод определенно приводит к провалу канонического подхода к эксплуатации переполнения буфера стека, он не лишен проблем. Во-первых, обычно находят способы хранить шелл-код в незащищенных областях памяти, таких как куча, и поэтому очень мало нужно менять способ эксплуатации.

Даже если бы это было не так, есть другие способы. Самым ужасным является так называемый метод return to libc для создания шелл-кода. В этой атаке вредоносная полезная нагрузка будет загружать стек не с шелл-кодом, а с правильным стеком вызовов, так что выполнение будет направлено на цепочку стандартных вызовов библиотеки, обычно с эффектом отключения защиты памяти от выполнения и разрешения шелл-коду работать в обычном режиме. Это работает, потому что выполнение никогда не переносится в сам стек.

Вариантом return-to-libc является возвратно-ориентированное программирование (ROP), которое устанавливает серию адресов возврата, каждый из которых выполняет небольшую последовательность выбранной машиной инструкции в рамках существующего программного кода или системных библиотек, последовательность которых заканчивается возвратом. Каждый из этих так называемых гаджетов выполняет простую манипуляцию с регистрами или аналогичное выполнение перед возвратом, и объединение их вместе достигает целей злоумышленника. Можно даже использовать «безвозвратное» программирование, ориентированное на возврат, используя инструкции или группы инструкций, которые ведут себя так же, как инструкция возврата.

Рандомизация

Вместо отделения кода от данных, другой метод смягчения последствий — введение рандомизации в область памяти исполняемой программы. Поскольку злоумышленнику необходимо определить, где находится исполняемый код, который можно использовать, либо предоставляется исполняемая полезная нагрузка (с исполняемым стеком), либо она создается с использованием повторного использования кода, например, в ret2libc или в программировании, ориентированном на возврат (ROP). Рандомизация структуры памяти, как концепция, не позволяет злоумышленнику узнать, где находится какой-либо код. Однако реализации обычно не все рандомизируют; обычно сам исполняемый файл загружается по фиксированному адресу, и, следовательно, даже когда ASLR (рандомизация разметки адресного пространства) комбинируется с невыполняемым стеком, злоумышленник может использовать эту фиксированную область памяти. Следовательно, все программы должны быть скомпилированы с использованием PIE (независимые от позиции исполняемые файлы), чтобы даже эта область памяти была рандомизирована. Энтропия рандомизации отличается от реализации к реализации, и достаточно низкая энтропия сама по себе может быть проблемой с точки зрения грубого форсирования пространства памяти, которое рандомизируется.

Примечательные примеры

• Червь Morris в 1988 г. частично распространился за счет использования переполнения буфера стека на сервере Unix finger. [1]
• Червь Witty в 2004 г. распространился, эксплуатируя переполнение буфера стека в Internet Security Systems BlackICE Desktop Agent. [2]
• Червь Slammer в 2003 г. распространился, эксплуатируя переполнение буфера стека на SQL-сервере Microsoft. [3]
• Червь Blaster в Распространение 2003 г. за счет использования переполнения буфера стека в службе Microsoft DCOM.
• Существует несколько примеров Wii, позволяющих запускать произвольный код в неизмененной системе.. «Сумеречный хак», который включает в себя длинное имя лошади главного героя в The Legend of Zelda: Twilight Princess и «Smash Stack» для Super Smash Bros. Brawl, который включает использование SD-карты для загрузки специально подготовленного файла в редактор игровых уровней. Хотя оба могут использоваться для выполнения любого произвольного кода, последний часто используется для простой перезагрузки самой Brawl с применением модификаций.

См. Также

• Рандомизация компоновки адресного пространства
• Переполнение буфера
• Стек вызовов
• Компьютерная безопасность
• ExecShield
• Защита исполняемого пространства
• Эксплойт (компьютерная безопасность)
• Атака форматной строки
• Переполнение кучи
• Целочисленное переполнение
• бит NX
• PaX
• Возврат-ориентированное программирование
• Linux с усиленной безопасностью
• Переполнение стека
• Нарушение хранилища
• Уязвимость (вычисления)

Ссылки