Как происходит «переполнение стека» и как его предотвратить?

Question

Как происходит переполнение стека и как лучше всего предотвратить его, или как его предотвратить, особенно на веб-серверах, но другие примеры также были бы интересны?

Answer 1

Stack

В этом контексте стек является последним входным, первым выходным буфером, в который вы помещаете данные во время работы вашей программы. «Последний пришел, первый вышел» (LIFO) означает, что последнее, что вы вставляете, это всегда первое, что вы возвращаете - если вы помещаете 2 стека в стек, «А», а затем «В», то первое, что вы вставляете со стека будет «B», а затем «A».

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

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

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

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

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

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

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

Встроенные системы

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

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

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

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

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

Веб-серверы

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

-Adam

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

char hugeArray[100000000];

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

Answer 6

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

Когда вы совершаете вызов метода, функции или процедуры, «стандартный» способ или выполнение вызова состоит из:

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

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

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

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

Answer 7

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

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

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

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

Answer 8

Что? Никто не любит тех, кого охватывает бесконечный цикл?

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

Answer 9

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

Проверить эту тему:

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