Какая ошибка программирования обычно приводит к переполнению стека во время выполнения программы

Обновлено: 04.07.2024

Эксплойты с переполнением буфера на основе стека, вероятно, являются самой блестящей и наиболее распространенной формой эксплойта для удаленного управления выполнением кода процесса. Эти эксплойты были чрезвычайно распространены 20 лет назад, но с тех пор разработчики операционных систем, разработчиков приложений и производителей оборудования приложили огромные усилия для смягчения атак переполнения стека. . Ниже мы рассмотрим, как работают переполнения на основе стека, и подробно расскажем о стратегиях смягчения последствий, которые применяются для их предотвращения.

Подробное изучение атак переполнения буфера на основе стека

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

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

Возьмите этот особенно надуманный пример:

Если вы не знаете язык программирования C, ничего страшного. В этой программе интересно то, что она создает в памяти два буфера с именами realPassword и GivenPassword как локальные переменные. В каждом буфере есть место для 20 символов. Когда мы запускаем программу, пространство для этих локальных переменных создается в памяти и специально сохраняется в стеке со всеми другими локальными переменными (и некоторыми другими вещами). Стек представляет собой очень структурированное последовательное пространство памяти, поэтому относительное расстояние между любыми двумя локальными переменными в памяти гарантированно будет относительно небольшим. После того, как эта программа создает переменные, она заполняет значение realPassword строкой, затем запрашивает у пользователя пароль и копирует предоставленный пароль в значение заданного пароля. Получив оба пароля, он сравнивает их. Если они совпадают, печатается «УСПЕХ!» Если нет, выводится «FAILURE!»

Вот пример выполнения:

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

Теперь, когда мы знаем, где находятся локальные переменные, мы можем распечатать эту область памяти:

Как уже упоминалось, стек представляет собой последовательно хранящиеся данные. Если вы знаете ASCII, то знаете, что буква «а» представлена в памяти значением 0x61, а буква «d» — 0x64. Вы можете видеть выше, что они находятся рядом друг с другом в памяти. Буфер realPassword находится сразу после буфера GivenPassword.

Теперь давайте поговорим об ошибках, которые допустил программист (я). Во-первых, разработчики никогда не должны использовать функцию gets, потому что она не проверяет, соответствует ли размер считываемых данных размеру области памяти, используемой для сохранения данных. Он просто слепо читает текст и сбрасывает его в память. Есть много функций, которые делают то же самое — они известны как неограниченные функции, потому что разработчики не могут предсказать, когда они прекратят чтение из памяти или запись в память. У Microsoft даже есть веб-страница, документирующая то, что она называет «запрещенными» функциями, включая эти неограниченные функции. Каждый разработчик должен знать эти функции и избегать их, и каждый проект должен автоматически проверять исходный код на их наличие. Все эти функции восходят к периоду, когда безопасность не была такой обязательной, как сегодня. Эти функции должны продолжать поддерживаться, потому что отказ от поддержки может привести к поломке многих устаревших программ, но их нельзя использовать ни в каких новых программах, и их следует удалять во время обслуживания старых программ.

Взгляд на взлом

Мы посмотрели на стек, заметили, что буферы располагаются в памяти последовательно, и поговорили о том, почему gets — плохая функция. Теперь давайте злоупотребим и посмотрим, сможем ли мы взломать программу ~~planet~~. Поскольку мы знаем, что у get есть проблема с чтением большего количества данных, чем следует, первое, что нужно попробовать, — это передать ему больше данных, чем может вместить буфер. Буферы состоят из 20 символов, поэтому начнем с 30 символов:

Мы ясно видим, что в памяти есть 30 экземпляров «а», несмотря на то, что мы указали место только для 20 символов. Мы переполнили буфер, но недостаточно, чтобы что-то сделать. Давайте продолжим попытки и попробуем 40 экземпляров «а».

Первое, на что следует обратить внимание, это то, что мы зашли достаточно далеко, чтобы пройти через отведенное пространство для GivenPassword и сумели изменить значение realPassword , что является огромным успехом. Однако мы не изменили его настолько, чтобы обмануть программу. Поскольку мы сравниваем 20 символов, а в буфер realPassword мы записали восемь символов, нам нужно записать еще 12 символов. Итак, попробуем еще раз, но на этот раз с 52 вхождениями "а":

Успех! Мы переполнили буфер для GivenPassword, и данные попали прямо в realPassword, так что мы могли изменить буфер realPassword на все, что захотим, до того, как произойдет проверка. Это пример атаки переполнения буфера (или стека). В данном случае мы использовали его для изменения переменных внутри программы, но его также можно использовать для изменения метаданных, используемых для отслеживания выполнения программы.

Изменение метаданных

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

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

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

Что делается для предотвращения этих эксплойтов?

Прошло почти 20 лет с момента расцвета атак с переполнением стека, и существует множество средств защиты, которые не позволяют им работать так же хорошо, как раньше. Некоторые из этих средств защиты включают канарейки стека, рандомизацию размещения адресного пространства (ASLR), предупреждения компилятора и аппаратные изменения для предотвращения выполнения кода в стеке. (Примечание: историческое обсуждение ASLR в Windows см. в отличной ветке Twitter Джона Ламберта.)

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

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

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

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

Чтобы обойти защиту канареечного стека с помощью коллекции компиляторов GNU (GCC), upi должен указать, что вы хотите отключить защиту, с помощью флага «-fno-stack-protection».

Для демонстрации скомпилируем программу без защиты и передадим ей большой буфер. В этом случае я использую небольшой встроенный perl-скрипт для создания серии из 90 экземпляров «a» и передачи их в программу example.elf:

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

Теперь повторим эксперимент, но не отключая защиту стека gcc:

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

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

Чтобы остановить атаки на основе ROP, операционные системы начали рандомизировать расположение памяти инструкций, чтобы злоумышленники не знали, где хранится нужный код. Эта рандомизация учебной памяти называется ASLR, которая перемешивает блоки памяти и делает так, что местоположение данного объекта (включая код) в памяти больше не является постоянным значением. Атака, которая сработала один раз, может не сработать снова, поскольку кода, который пытался выполнить злоумышленник, может больше не быть, что приводит к непредсказуемым результатам.

Несмотря на свою эффективность, ASLR ограничен, поскольку, как и NX, не каждый фрагмент памяти инструкций хорошо реагирует на перемещение, поэтому некоторый код должен отказаться от защиты. Даже для кода, который может обрабатывать ASLR, есть обходные пути. Наиболее распространенный обход использует ограничение, заключающееся в том, что память может быть рандомизирована только блоками. Если есть способ определить, где находится блок памяти, злоумышленник может вычислить местоположение нужной памяти из утекшего значения. К сожалению, поскольку ASLR не был встроен в операционные системы, они иногда сохраняют рандомизированное расположение чего-то важного в известном месте, подобно тому, как сотрудник выбирает хороший пароль, но прикрепляет его к заметке Post-It под клавиатурой. Такой «чит» со стороны операционной системы позволяет злоумышленникам определить местонахождение известного объекта в памяти, а затем на основе его расположения вычислить местонахождение нужного кода или объекта. Опять же, как и NX, ASLR не полностью предотвращает атаку, но делает атаки более сложными и менее успешными с точки зрения прогнозирования.

В заключение

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

Что такое ошибка StackOverflowError , что ее вызывает и что с ней делать?

Один неочевидный способ получить это: добавить строку new Object() >; в некоторый статический контекст (например, основной метод). Не работает из контекста экземпляра (выдает только InstantiationException ).

15 ответов 15

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

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

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

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

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

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

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

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

Примеры

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

Примечания

StackOverflowException использует HRESULT COR_E_STACKOVERFLOW, который имеет значение 0x800703E9. Инструкция промежуточного языка Localloc (IL) вызывает StackOverflowException . Список начальных значений свойств для объекта StackOverflowException см. в конструкторах StackOverflowException.

Применение атрибута HandleProcessCorruptedStateExceptionsAttribute к методу, вызывающему исключение StackOverflowException, не дает никакого эффекта. Вы по-прежнему не можете обработать исключение из пользовательского кода.

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

Конструкторы

Инициализирует новый экземпляр класса StackOverflowException, задавая для свойства Message нового экземпляра предоставленное системой сообщение с описанием ошибки, например "Запрошенная операция вызвала переполнение стека". Это сообщение учитывает текущую культуру системы.

Инициализирует новый экземпляр класса StackOverflowException с указанным сообщением об ошибке.

Инициализирует новый экземпляр класса StackOverflowException с указанным сообщением об ошибке и ссылкой на внутреннее исключение, которое является причиной этого исключения.

Свойства

Получает набор пар "ключ-значение", которые предоставляют дополнительную определяемую пользователем информацию об исключении.

Получает или задает ссылку на файл справки, связанный с этим исключением.

Получает или задает HRESULT, закодированное числовое значение, которое назначается определенному исключению.

Получает экземпляр Exception, вызвавший текущее исключение.

Получает сообщение, описывающее текущее исключение.

Получает или задает имя приложения или объекта, вызвавшего ошибку.

Получает строковое представление ближайших кадров в стеке вызовов.

Получает метод, выдающий текущее исключение.

Методы

Определяет, равен ли указанный объект текущему объекту.

При переопределении в производном классе возвращает исключение, являющееся основной причиной одного или нескольких последующих исключений.

Служит хеш-функцией по умолчанию.

При переопределении в производном классе устанавливает SerializationInfo с информацией об исключении.

Получает тип среды выполнения текущего экземпляра.

Создает поверхностную копию текущего объекта.

Создает и возвращает строковое представление текущего исключения.

События

Происходит при сериализации исключения для создания объекта состояния исключения, содержащего сериализованные данные об исключении.

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

Что такое Java Lang StackOverflowError?

Ошибка java. яз. StackOverflowError выдается, чтобы указать, что стек приложения исчерпан из-за глубокой рекурсии, т. е. ваша программа/скрипт слишком глубоко рекурсивна.

Что такое переполнение стека Apache spark?

Apache Spark – это механизм распределенной обработки данных с открытым исходным кодом, написанный на языке Scala, предоставляющий пользователям унифицированный API и распределенные наборы данных как для пакетной, так и для потоковой обработки. Варианты использования Apache Spark часто связаны с машинным/глубоким обучением и обработкой графов.

Что вызывает ошибку переполнения?

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

Что вызывает исключение переполнения стека?

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

Что такое ошибка переполнения стека в C++?

Определение. Переполнение стека — это программная ошибка времени выполнения, когда программа пытается использовать больше места, чем доступно в стеке времени выполнения, что обычно приводит к сбою программы.

Чем искра отличается от MapReduce?

Основное различие между Spark и MapReduce заключается в том, что Spark обрабатывает и сохраняет данные в памяти для последующих шагов, тогда как MapReduce обрабатывает данные на диске. В результате для небольших рабочих нагрузок скорость обработки данных Spark до 100 раз выше, чем у MapReduce.

Что такое переполнение стека Hadoop?

Программная библиотека Apache Hadoop — это платформа, позволяющая выполнять распределенную обработку больших наборов данных в кластерах компьютеров с использованием простых моделей программирования. Итак, «Hadoop» — это название проекта и программной библиотеки.

Что такое пример ошибки переполнения?

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

Что за ошибка переполнения?

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

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

Стек времени выполнения

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

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

Последствия ошибки

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

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

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

Причины ошибки

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

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

Однако динамическая память выделяется и освобождается довольно медленно (поскольку ею управляет операционная система). Кроме того, вы должны вручную выделять и освобождать его при предоставлении прямого доступа. Наоборот, стековая память выделяется очень быстро (на самом деле нужно всего лишь изменить значение одного регистра); более того, объекты, расположенные в стеке, автоматически уничтожаются, когда функция возвращает управление и очищает стек. Вы, естественно, не можете избавиться от желания использовать это. Следовательно, третья причина ошибки — ручное выделение программистом памяти стека. Библиотека C предоставляет для этой цели специальную функцию alloca. Интересно, что в то время как функция malloc (предназначенная для выделения динамической памяти) имеет «родственного брата», который ее освобождает (функция free), функция alloca не имеет ни одного: память освобождается автоматически, как только функция возвращает управление. Эта вещь, вероятно, усложнит проблему, поскольку вы не можете освободить память перед выходом из функции.Хотя справочная страница функции alloca четко гласит, что она «зависит от машины и компилятора; во многих системах ее нельзя использовать должным образом и она может вызывать ошибки; ее использование не рекомендуется», программисты все еще используют ее.

Примеры

В качестве примера рассмотрим фрагмент кода, выполняющий рекурсивный поиск файлов (взято из MSDN):

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

Вот пример, иллюстрирующий вторую причину, взятую из вопроса "Что может быть причиной исключения переполнения стека?" задан на Stack Overflow (это сайт вопросов и ответов, посвященный всем темам, связанным с программированием, а не только переполнению стека, как можно заключить из его названия):

Как видите, функция main запрашивает выделение памяти стека для массива int и массива с плавающей запятой, по миллиону элементов каждый, что в сумме дает немногим меньше 8 Мбайт. Если вспомнить, что Visual C++ по умолчанию резервирует под стек только 1 Мбайт, то легко ответим на этот вопрос.

И, наконец, вот пример, взятый из GitHub-репозитория проекта Flash-плеера Lightspark:

Можно надеяться, что h.getLength()-7 не станет слишком большим и в следующей строке не произойдет переполнения. Но стоит ли сэкономленное время при выделении памяти потенциального сбоя?

Заключение

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

Читайте также: