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

Question

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

Answer 1

Куча

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Веб-серверы

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

-Адам

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

char hugeArray[100000000];

Вот и все.

Answer 5

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

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 и т. д., в которых обычно пишутся веб-приложения, поэтому ваш единственный риск — это сам веб-сервер, который, вероятно, написан на С или С++.

Посмотрите эту тему:

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