Как происходит "stack overflow" и как вы его предотвращаете?

Стек

В этом контексте стек - это последний входящий и первый выходящий буфер, в который вы помещаете данные во время выполнения программы. Last in, first out (LIFO) означает, что последнее, что вы кладете, всегда первое, что вы получаете обратно - если вы нажмете 2 элемента в стеке, 'A' и затем 'B', то первое, что вы выскочите из стека, будет 'B', а следующее-'A'.

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

Переполнение стека

Переполнение стека - это когда вы израсходовали больше памяти для стека, чем ваша программа должна была использовать. В встраиваемых системах вы можете иметь только 256 байт для стека, и если каждая функция занимает 32 байта, то вы можете иметь только вызовы функций 8 deep-функция 1 вызывает функцию 2, которая вызывает функцию 3, которая вызывает функцию 4 .... кто вызывает функцию 8, кто вызывает функцию 9, но функция 9 перезаписывает память вне стека. Это может привести к перезаписи памяти, кода и т. д.

Многие программисты делают эту ошибку, вызывая функцию A, которая затем вызывает функцию B, которая затем вызывает функцию C, которая затем вызывает функцию A. Это может работать большую часть времени, но только один раз неправильный ввод заставит его идти по этому кругу вечно, пока компьютер не признает, что стек раздут.

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

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

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

Встроенная система

Во встроенном мире, особенно в высоконадежном коде (автомобильном, авиационном, космическом), вы делаете обширные обзоры и проверки кода, но вы также делаете следующее:

• Запретить рекурсию и циклы-принудительно с помощью политики и тестирования
• Держите код и стек далеко друг от друга (код в flash, стек в RAM, и никогда два не встретятся)
• Поместите защитные полосы вокруг стека-пустой области памяти, которую вы заполняете магическим числом (обычно это команда прерывания программного обеспечения, но здесь есть много вариантов), и сотни или тысячи раз в секунду вы смотрите на защитные полосы, чтобы убедиться, что они не были перезаписаны.
• Используйте защиту памяти (т. е. нет выполнения в стеке, нет чтения или записи только за пределами стека)
• Прерывания не вызывают вторичные функции - они устанавливают флаги, копируют данные и позволяют приложению обрабатывать их (в противном случае вы можете получить 8 глубоко в дереве вызовов функций, иметь прерывание, а затем выйти еще несколько функций внутри прерывания, вызывая выброс). У вас есть несколько деревьев вызовов - по одному для основных процессов и по одному для каждого прерывания. Если ваши прерывания могут перебивать друг друга... Ну что ж, там есть драконы...

Языки и системы высокого уровня

Но в языках высокого уровня работают на операционных системах:

• Уменьшите объем хранения локальных переменных (локальные переменные хранятся в стеке - хотя компиляторы довольно умны в этом отношении и иногда помещают большие локальные переменные в кучу, если ваше дерево вызовов неглубоко)
• Избегайте или строго ограничьте рекурсию
• Не разбивайте свои программы слишком далеко на все более мелкие функции - даже без учета локальных переменных каждый вызов функции потребляет целых 64 байта в стеке (32-битный процессор, сохранение половины регистров CPU, флаги и т. д)
• Держите дерево вызовов неглубоким (аналогично приведенному выше утверждению)

Web-сервер

Это зависит от 'sandbox', который у вас есть, можете ли вы контролировать или даже видеть стек. Скорее всего, вы можете обращаться с веб - серверами так же, как с любым другим языком и операционной системой высокого уровня-это в значительной степени не в ваших руках, но проверьте язык и стек серверов, которые вы используете. Например, можно взорвать стек на вашем сервере SQL.

-Adam

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

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

Некоторые варианты в этом случае:

• Поиск в ширину
• Хвостовая рекурсия, специфичный для .Net отличный пост в блоге (извините, 32-битный .Net)

Бесконечная рекурсия-это распространенный способ получить ошибку переполнения стека. Чтобы предотвратить-всегда убедитесь, что есть путь выхода, который будет поражен. :-)

Другой способ получить переполнение стека (по крайней мере, в C/C++,) - объявить какую-то огромную переменную в стеке.

char hugeArray[100000000];

Это все сделает.

Переполнение стека происходит, когда Джефф и Джоэл хотят дать миру лучшее место для получения ответов на технические вопросы. Слишком поздно предотвращать это переполнение стека. Это "other site" могло бы предотвратить его, не будучи грязным. ;)

Обычно переполнение стека является результатом бесконечного рекурсивного вызова (учитывая обычный объем памяти в стандартных компьютерах в настоящее время).

При вызове метода, функции или процедуры путь "standard" или выполнение вызова состоит из:

1. Нажатие направления возврата для вызова в стек(это следующее предложение после вызова)
2. Обычно пространство для возвращаемого значения резервируется в стеке
3. Выталкивание каждого параметра в стек (порядок разнится и зависит от каждого компилятора, также некоторые из них иногда хранятся в регистрах CPU для повышения производительности)
4. Собственно, я и звоню.

Таким образом, обычно это занимает несколько байт, отклоняющихся от числа и типа параметров, а также архитектуры машины.

Тогда вы увидите, что если вы начнете делать рекурсивные вызовы, стек начнет расти. Теперь стек обычно резервируется в памяти таким образом, что он растет в противоположном направлении к куче, поэтому при большом количестве вызовов без "coming back" стек начинает заполняться.

Теперь, в более старые времена переполнение стека могло произойти просто потому, что вы исчерпали всю доступную память, просто так. С моделью виртуальной памяти (до 4 ГБ в системе X86), которая была вне области действия, поэтому обычно, если вы получаете ошибку переполнения стека, ищите бесконечный рекурсивный вызов.

Что? Никто не испытывает никакой любви к тем, кого окружает бесконечная петля?

do
{
  JeffAtwood.WritesCode();
} while(StackOverflow.MakingMadBank.Equals(false));

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

Это обычно может происходить в функциях, которые вызываются в ответ на события, но которые сами могут генерировать новые события, например:

void WindowSizeChanged(Size& newsize) {
  // override window size to constrain width
    newSize.width=200;
    ResizeWindow(newSize);
}

В этом случае вызов ResizeWindow может вызвать обратный вызов WindowSizeChanged() , который вызовет ResizeWindow снова, пока не закончится стек. В подобных ситуациях вам часто нужно отложить ответ на событие до тех пор, пока не вернется кадр стека, например, отправив сообщение.

Учитывая, что это было помечено "hacking", я подозреваю, что "stack overflow", на которое он ссылается, является переполнением стека вызовов, а не переполнением стека более высокого уровня, как те, на которые ссылаются в большинстве других ответов здесь. На самом деле это не относится к каким-либо управляемым или интерпретируемым средам, таким как .NET, Java, Python, Perl, PHP, и т.д., на которых обычно пишутся веб-приложения,так что ваш единственный риск - это сам веб-сервер, который, вероятно, написан на C или C++.

Проверьте этот поток:

https://stackoverflow.com/questions/7308/what-is-a-good-starting-point-for-learning-buffer-overflow