Как избежать переполнения в c
Как обрабатывать или избегать переполнения стека в C++
в C++ переполнение стека обычно приводит к неисправимому сбою программы. Для программ, которые должны быть очень надежными, это неприемлемое поведение, особенно потому, что размер стека ограничен. Несколько вопросов о том, как справиться с проблемой.
есть ли способ предотвратить переполнение стека общей техникой. (Масштабируемое, надежное решение, которое включает в себя работу с внешними библиотеками, потребляющими много стека, так далее.)
есть ли способ обрабатывать переполнения стека в случае их возникновения? Предпочтительно, стек разматывается, пока не появится обработчик для решения этой проблемы.
есть языки, которые имеют потоки с расширяемыми стеками. Возможно ли что-то подобное в C++?
любые другие полезные комментарии по решению поведения C++ будут оценены.
5 ответов
обработка переполнения стека не является правильным решением, вместо этого вы должны убедиться, что ваша программа не переполняет стек.
не выделяйте большие переменные в стеке (где «большое» зависит от программы). Убедитесь, что любой рекурсивный алгоритм завершается после известной максимальной глубины. Если рекурсивный алгоритм может рекурсировать неизвестное количество раз или большое количество раз, либо управляйте рекурсией самостоятельно (сохраняя свой собственный динамически выделенный stack) или преобразовать рекурсивный алгоритм в эквивалентный итерационный алгоритм
программа, которая должна быть «действительно надежной», не будет использовать сторонние или внешние библиотеки, которые » съедают много стека.»
обратите внимание, что некоторые платформы уведомляют программу при переполнении стека и позволяют программе обрабатывать ошибку. В Windows, например, исключение. Это исключение не является исключением C++, хотя это асинхронное исключение. А Исключение C++ может быть вызвано только throw оператор, асинхронное исключение может быть вызвано в любое время во время выполнения программы. Это ожидается, однако, потому что переполнение стека может произойти в любое время: любой вызов функции или распределение стека может переполнить стек.
другие платформы могут иметь аналогичные методы для «обработки» ошибки переполнения стека, но любые такие методы, вероятно, страдают от той же проблемы: код, который, как ожидается, не вызовет ошибку, может вызывать ошибку.
(*) есть несколько очень редких исключений.
вы можете защитить от переполнения стека, используя хорошие методы программирования, такие как:
Это самые серьезные причины, которые я видел за последние несколько лет.
для автоматического поиска, поэтому вы должны найти некоторые инструменты статического анализа кода.
В общем, лучше всего быть активным, избегая больших переменных на основе стека и осторожным с рекурсивными вызовами.
Re: расширяемые стеки. Вы могли бы дать себе больше пространства для стека с чем-то вроде этого:
Почему перенос при целочисленном переполнении — не очень хорошая идея
Эта статья посвящена неопределённому поведению и оптимизациям компилятора, особенно в контексте знакового целочисленного переполнения.
Примечание от переводчика: в русском языке нет четкого соответствия в употребляемом контексте слова «wrap»/«wrapping». Существует математический термин «перенос», который близок к описываемому явлению, а термин «флаг переноса» (carry flag) — механизм выставления флага в процессорах при целочисленном переполнении. Другим вариантом перевода может быть фраза «вращение/переворот/оборот вокруг нуля». Она лучше отображает смысл «wrap» по сравнению с «перенос», т.к. показывает переход чисел при переполнении из положительного в отрицательный диапазон. Однако, как оказалось, эти слова смотрятся в тексте непривычно для тестовых читателей. Для упрощения в дальнейшем примем в качестве перевода термина «wrap» слово «перенос».
Компиляторы языка C (и C++) в своей работе всё чаще руководствуются понятием неопределённого поведения — представлением о том, что поведение программы при некоторых операциях не регламентировано стандартом и что, генерируя объектный код, компилятор вправе исходить из предположения, что программа таких операций не производит. Немало программистов возражало против такого подхода, поскольку сгенерированный код в этом случае может вести себя не так, как задумывал автор программы. Эта проблема становится всё острее, так как компиляторы применяют всё более хитроумные методы оптимизации, которые наверняка будут опираться на понятие неопределённого поведения.
В этом контексте показателен пример со знаковым целочисленным переполнением. Большинство разработчиков на C пишут код для машин, в которых для представления целых чисел используется дополнительный код, а сложение и вычитание в таком представлении реализованы точно так же, в беззнаковой арифметике. Если сумма двух положительных целых чисел со знаком переполнится — то есть станет больше, чем вмещает тип, — процессор выдаст значение, которое, будучи интерпретировано как двоичное дополнение знакового числа, будет считаться отрицательным. Это явление называется «переносом», поскольку результат, дойдя до верхней границы диапазона значений, «переносится» и начинается с нижней границы.
По этой причине можно иногда увидеть вот такой код на C:
Задача оператора if — обнаружить состояние переполнения (в данном случае оно возникает после прибавления 1000 к значению переменной a) и сообщить об ошибке. Проблема в том, что в C знаковое целочисленное переполнение является одним из случаев неопределённого поведения. Компиляторы с некоторых пор считают такие условия всегда ложными: если прибавить 1000 (или любое другое положительное число) к другому числу, результат не может быть меньше начального значения. Если же происходит переполнение, значит, возникает неопределённое поведение, и не допускать этого — уже (по-видимому) забота самого программиста. Поэтому компилятор может решить, что условный оператор можно целиком удалить в целях оптимизации (ведь условие всегда ложно, оно ни на что не влияет, значит, можно обойтись без него).
Проблема в том, что этой оптимизацией компилятор убрал проверку, которую программист добавил специально, чтобы выявить неопределённое поведение и обработать его. Вот тут можно посмотреть, как это происходит на практике. (Примечание: сайт godbolt.org, на котором размещён пример, очень классный! Можно редактировать код и сразу же смотреть, как его обрабатывают разные компиляторы, а их там представлено множество. Поэкспериментируйте!). Обратите внимание, что компилятор не убирает проверку на переполнение, если изменить тип на беззнаковый, поскольку поведение при беззнаковом переполнении в языке С определено (точнее, при беззнаковой арифметике результат переносится, поэтому переполнения на самом деле не происходит).
Так что же, это неправильно? Кто-то говорит, что да, хотя очевидно, что многие разработчики компиляторов считают такое решение законным. Если я правильно понимаю, основные доводы сторонников (правка: зависящего от реализации) переноса при переполнении сводятся к следующему:
Перенос при переполнении — полезное поведение?
Перенос полезен в основном тогда, когда надо отследить уже возникшее переполнение. (Если и существуют другие задачи, которые решаются переносом и не могут быть решены с помощью беззнаковых целочисленных переменных, я не могу сходу припомнить таких примеров, и подозреваю, что их немного). При том, что перенос действительно упрощает проблему использования некорректно переполненных переменных, оно определённо не является панацеей (вспомним умножение или сложение двух неизвестных величин с неизвестным знаком).
В тривиальных же случаях, когда перенос просто позволяет отследить возникшее переполнение, так же не составит труда заранее узнать, возникнет ли оно вообще. Наш пример можно переписать в следующем виде:
То есть, вместо того чтобы вычислять сумму и затем выяснять, произошло переполнение или нет, проверяя результат на математическую непротиворечивость, можно проверить, превысит ли сумма максимальное вмещаемое типом число. (Если знак обоих операндов неизвестен, проверку придётся сильно усложнить, но то же касается и проверки при переносе).
Учитывая всё это, я нахожу неубедительным аргумент, будто перенос полезен в большинстве случаев.
Перенос — это поведение, которого ожидают программисты?
С этим доводом сложнее спорить, поскольку очевидно, что код по крайней мере некоторых программистов на C предполагает семантику переноса при знаковом целочисленном переполнении. Но одного только этого факта недостаточно, чтобы считать такую семантику предпочтительной (заметьте, что некоторые компиляторы позволяют включить её, если необходимо).
Очевидное решение проблемы (ожидание программистами именно этого поведения) — сделать так, чтобы компилятор выдавал предупреждение, когда он оптимизирует код, предполагая отсутствие неопределённого поведения. К сожалению, как мы видели в примере на сайте godbolt.org по ссылке выше, компиляторы не всегда поступают таким образом (Gcc версии 7.3 — да, а версии 8.1 — нет, так что налицо шаг назад).
Семантика неопределённого поведения при переполнении не даёт заметного преимущества?
Если это замечание справедливо для всех случаев, то оно послужило бы сильным аргументом в пользу того, что компиляторы должны по умолчанию придерживаться семантики переноса, так как, пожалуй, будет лучше разрешить проверки на переполнение, пусть даже этот механизм некорректен с технической точки зрения — хотя бы уже потому, что он может использоваться в потенциально сломанном коде.
Я допускаю, что конкретно этой оптимизацией (удаление проверок математически противоречивых условий) в обычных программах на C зачастую можно пренебречь, так как их авторы стремятся к наилучшей производительности и всё равно оптимизируют код вручную: то есть, если очевидно, что данный оператор if содержит условие, которое никогда не будет истинным, программист, скорее всего, уберёт его сам. В самом деле, я выяснил, что в нескольких исследованиях эффективность такой оптимизации была поставлена под вопрос, протестирована и признана практически несущественной в рамках контрольных тестов. Однако, хотя эта оптимизация почти никогда не даёт преимущества в языке C, генераторы кода и оптимизации компиляторов в большинстве своём универсальны и могут использоваться в других языках — и для них данный вывод может быть неверен. Возьмём язык C++ с его, скажем так, традицией полагаться на оптимизатор, чтобы тот убирал избыточные конструкции в коде шаблонов, а не делать это вручную. А ведь существуют и языки, которые преобразуются транспайлером в C, и при этом избыточный код в них также оптимизируется C-компиляторами.
Кроме того, даже если сохранить проверки на переполнение, вовсе не факт, что прямая стоимость переноса целочисленных переменных будет минимальной даже на машинах, использующих дополнительный код. Архитектура Mips, например, может выполнять арифметические операции только в регистрах фиксированного размера (32 бита). Тип short int, как правило, имеет размер 16 бит, а char — 8 бит; при хранении в регистре переменной одного из этих типов её размер расширится, и, чтобы корректно перенести её, потребуется выполнить по крайней мере одну дополнительную операцию и, возможно, задействовать дополнительный регистр (чтобы вместить соответствующую битовую маску). Должен признать, что я уже давно не имел дела с кодом для Mips, так что я не уверен насчёт точной стоимости этих операций, но я уверен, что она ненулевая и что на других архитектурах RISC могут возникнуть такие же проблемы.
Стандарт языка запрещает избегать переноса переменных, если оно предполагается архитектурой?
Если разобраться, этот аргумент особенно слаб. Его суть в том, что стандарт якобы позволяет реализации (компилятору) трактовать «неопределённое поведение» лишь в ограниченных пределах. В самом же тексте стандарта — в том его фрагменте, к которому апеллируют сторонники переноса, — сказано следующее (это часть определения понятия «неопределённое поведение»):
Идея в том, что слова «полное игнорирование ситуации» не позволяют предполагать, что событие, приводящее к неопределённому поведению, — например, переполнение при сложении — не может произойти, а скорее, что если оно случается, то компилятор должен продолжить работу как ни в чем не бывало, но при этом также учитывать результат, который получится, если он пошлёт процессору запрос на выполнение такой операции (другими словами, как если бы исходный код транслировался в машинный прямолинейно и наивно).
Прежде всего, следует заметить, что этот текст дан как «примечание», а потому не является нормативным (т.е. не может что-то предписывать), согласно директиве ISO, упомянутой в предисловии к стандарту:
В соответствии с Частью 3 Директив ISO/IEC, данное предисловие, введение к тексту, примечания, сноски и примеры также носят исключительно информационный характер.
Поскольку этот фрагмент о «неопределённом поведении» является примечанием, он ничего не предписывает. Обратите внимание, что настоящее определение понятия «неопределённое поведение» звучит так:
поведение, возникающее при использовании непереносимой или некорректной программной конструкции или некорректных данных, к которому настоящий Международный Стандарт не предъявляет никаких требований.
Я выделил главную мысль: к неопределённому поведению не предъявляется никаких требований; список «возможных видов неопределённого поведения» в примечании содержит лишь примеры и не может быть окончательным предписанием. Фразу «не предъявляет никаких требований» невозможно истолковать как-то иначе.
Некоторые, развивая данный аргумент, утверждают, что независимо от текста комитет по языку, когда он формулировал эти слова, имел в виду, что поведение в целом должно соответствовать архитектуре аппаратного обеспечения, на котором выполняется программа, настолько, насколько это возможно, подразумевая наивную трансляцию в машинный код. Это может быть правдой, хотя я не видел никаких свидетельств (например, исторических документов) в защиту этого довода. Однако, даже если бы это было так, не факт, что это утверждение применимо к текущей редакции текста.
Доводы в защиту переноса по большей части несостоятельны. Пожалуй, самый сильный аргумент получается, если их объединить: на перенос иногда рассчитывают менее опытные программисты (которые не знают тонкостей языка C и неопределённого поведения в нем), и оно не снижает производительность — хотя последнее верно не во всех случаях, а первая часть неубедительна, если рассматривать её отдельно.
Лично я предпочёл бы, чтобы переполнения блокировались (trapping), а не переносились. То есть, чтобы программа падала, а не продолжала работать — с неопределённым ли поведением или потенциально некорректным результатом, ведь и в том, и в другом случае появляется уязвимость. Такое решение, конечно, немного снизит производительность на большинстве (?) архитектур, особенно на x86, но, с другой стороны, ошибки, связанные с переполнением, будут сразу выявлены и ими не получится воспользоваться или получить с их помощью некорректные результаты дальше по ходу выполнения программы. Кроме того, в теории компиляторы при таком подходе могли бы безопасно удалять избыточные проверки на переполнение, поскольку оно точно не случится, хотя, как я вижу, ни Clang, ни GСС этой возможностью не пользуются.
К счастью, и прерывание, и перенос реализованы в компиляторе, которым я пользуюсь чаще всего, — GCC. Для переключения между режимами используются аргументы командной строки -ftrapv и -fwrapv соответственно.
Действий, приводящих к неопределённому поведению, конечно же, много — целочисленное переполнение лишь одно из них. Я вовсе не считаю, что все эти случаи полезно трактовать как неопределённое поведение, и я уверен, что существует немало специфических ситуаций, когда семантика должна определяться языком или, по крайней мере, оставаться на усмотрение реализаций. И я опасаюсь излишне вольных трактовок этого понятия производителями компиляторов: если поведение компилятора не отвечает интуитивным представлениям разработчиков, особенно тех, кто лично читал текст стандарта, это может привести к реальным ошибкам; если прирост производительности в этом случае пренебрежимо мал, то лучше от таких трактовок отказаться. В одном из следующих постов я, возможно, разберу некоторые из этих проблем.
Дополнение (от 24 августа 2018 года)
Я понял, что многое из сказанного выше можно было бы написать лучше. Ниже я кратко резюмирую и поясню свои слова и добавлю несколько мелких замечаний:
Дополнительные ссылки по теме от команды PVS-Studio:
Переполнение целых чисел
Переполнение целых чисел
В ы уже знаете, что при сложении целых может происходить переполнение. Загвоздка в том, что компьютер не выдаёт предупреждения при переполнении: программа продолжит работать с неверными данными. Более того, поведение при переполнении определено только для целых без знака.
Переполнение может привести к серьёзным проблемам: обнулению и потере данных, возможным эксплойтам, трудноуловимым ошибкам, которые будут накапливаться с течением времени.
Рассмотрим несколько приёмов отслеживания переполнения целых со знаком и переполнения целых без знака.
1. Предварительная проверка данных. Мы знаем, из файла limits.h, максимальное и минимальное значение для чисел типа int. Если оба числа положительные, то их сумма не превысит INT_MAX, если разность INT_MAX и одного из чисел меньше второго числа. Если оба числа отрицательные, то разность INT_MIN и одного из чисел должна быть больше другого. Если же оба числа имеют разные знаки, то однозначно их сумма не превысит INT_MAX или INT_MIN.
В этой функции переменной overflow будет присвоено значение 1, если было переполнение. Функция возвращает сумму, независимо от результата сложения.
Обратите внимание на явное приведение типов. Без него сначала произойдёт переполнение, и неправильное число будет записано в переменную c.
3. Третий способ проверки платформозависимый, более того, его реализация будет разной для разных компиляторов. При переполнении целых (обычно) поднимается флаг переполнения в регистре флагов. Можно на ассемблере проверить значение флага сразу же после выполнения суммирования.
Здесь переменная noOverflow равна 1, если нет переполнения. jno (jump if no overflow) выполняет переход к метке NO_OVERFLOW, если переполнения не было. Если же переполнение было, то выполняется
По адресу переменной noOverflow записывается нуль.
Работа с числами без знака гораздо проще: при переполнении происходит обнуление и известно, что получившееся число заведомо будет меньше каждого из слагаемых.
Как происходит «переполнение стека» и как его предотвратить?
Как происходит переполнение стека и как лучше всего этого избежать или как предотвратить его, особенно на веб-серверах, но были бы интересны и другие примеры?
Когда вы вызываете функцию в своем коде, следующая инструкция после вызова функции сохраняется в стеке и любое пространство памяти, которое может быть перезаписано вызовом функции. Вызываемая функция может использовать больше стека для собственных локальных переменных. Когда это будет сделано, он освобождает используемое пространство стека локальной переменной, а затем возвращается к предыдущей функции.
Переполнение стека
Многие программисты делают эту ошибку, вызывая функцию A, которая затем вызывает функцию B, которая затем вызывает функцию C, которая затем вызывает функцию A. Она может работать большую часть времени, но только один раз неправильный ввод заставит ее навсегда войти в этот круг. пока компьютер не обнаружит, что стек слишком раздут.
Рекурсивные функции также являются причиной этого, но если вы пишете рекурсивно (т. Е. Ваша функция вызывает сама себя), вам необходимо знать об этом и использовать статические / глобальные переменные для предотвращения бесконечной рекурсии.
Обычно операционная система и язык программирования, который вы используете, управляют стеком, и это вне ваших рук. Вы должны посмотреть на свой граф вызовов (древовидную структуру, которая показывает из вашего main, что вызывает каждая функция), чтобы увидеть, насколько глубоко заходят ваши вызовы функций, и чтобы обнаружить циклы и рекурсию, которые не предназначены. Преднамеренные циклы и рекурсия необходимо искусственно проверять, чтобы исключить ошибки, если они вызывают друг друга слишком много раз.
Помимо хороших практик программирования, статического и динамического тестирования, на этих высокоуровневых системах мало что можно сделать.
Встроенные системы
Во встраиваемом мире, особенно в коде высокой надежности (автомобильный, авиационный, космический), вы выполняете обширный анализ и проверку кода, но вы также делаете следующее:
Языки и системы высокого уровня
Но на языках высокого уровня, работающих в операционных системах:
Веб-серверы
❓ Что такое переполнение буфера и как с ним бороться
Перевод публикуется с сокращениями, автор оригинальной статьи Megan Kaczanowski .
Даже если код написан на «безопасном» языке (например, на Python), если используются любые написанные на C, C++ или Objective C библиотеки, он все равно может быть уязвим для переполнения буфера.
Выделение памяти
Чтобы понять механизм возникновения переполнения буфера, нужно немного разобраться с выделением памяти в программы. В написанном на языке С приложении можно выделить память в стеке во время компиляции или в куче во время выполнения.
Переполнение буфера может происходить в стеке (переполнение стека) или в куче (переполнение кучи). Как правило, переполнение стека встречается чаще. Он содержит последовательность вложенных функций: каждая из них возвращает адрес вызывающей функции, к которой нужно вернуться после завершения работы. Этот возвращаемый адрес может быть заменен инструкцией для выполнения фрагмента вредоносного кода.
Поскольку куча реже хранит возвращаемые адреса, гораздо сложнее (хотя в ряде случаев это возможно) запустить эксплойт. Память в куче обычно содержит данные программы и динамически выделяется по мере ее выполнения. Это означает, что при переполнении кучи, скорее всего, перезапишется указатель функции – такой путь более сложен и менее эффективен чем переполнение стека.
Поскольку переполнение стека является наиболее часто используемым типом переполнения буфера, кратко рассмотрим, как именно они работают.
Переполнение стека
Эксплуатация уязвимости происходит внутри процесса, при этом каждый процесс имеет свой собственный стек. Когда он выполняет основную функцию, то находит как новые локальные переменные (которые будут «запушены» в начало стека), так и вызовы других функций (которые создадут новый «стекфрейм»).
Что такое stackframe?
Стек вызовов – это в основном код ассемблера для конкретной программы. Это стек переменных и стекфреймов, которые сообщают компьютеру, в каком порядке выполнять инструкции. Для каждой функции, которая еще не завершила выполнение, будет создан стекфрейм, а функция, которая выполняется в данный момент, будет находиться в верхней части стека.
Чтобы отслеживать этот процесс, компьютер хранит в памяти несколько указателей:
Для примера рассмотрим следующий код:
Стек вызовов будет выглядеть следующим образом, сразу после вызова firstFunction и выполнения оператора int x = 1+z :
Здесь main вызывает firstFunction (которая в данный момент выполняется), поэтому она находится в верхней части стека вызовов. Возвращаемый адрес – это адрес в памяти, относящийся к функции, которая его вызвала (он удерживается указателем инструкции при создании стекфрейма). Локальные переменные, которые все еще находятся в области видимости, также находятся в стеке вызовов. Когда они выполняются и выходят за пределы области действия, они удаляются из верха стека.
Пример уязвимости переполнения буфера:
Этот простой код считывает произвольное количество данных ( gets будет считывать до конца файла или символа новой строки). Рассмотрев его, можно понять опасность. Если пользователь вводит больше данных, чем помещается в выделенную для переменной область, введенная строка перезапишет следующие ячейки памяти в стеке вызовов. Если она достаточно длинная, перезапишется даже обратный адрес вызывающей функции.
Как компьютер отреагирует на это, зависит от реализации стеков и выделения памяти в конкретной системе. Реакция на переполнение буфера может быть совершенно непредсказуемой, начиная от сбоев программы и заканчивая выполнением вредоносного кода.
Почему происходит переполнение буфера?
Причина, по которой переполнение буфера стало такой серьезной проблемой, заключается в отсутствии проверки границ во многих функции управления памятью в C и C++. Хотя этот процесс сейчас довольно хорошо известен, он также очень часто эксплуатируется (например, зловред WannaCry использовал переполнение буфера).
Веб-серверы, серверные приложения и среды веб-приложений подвержены переполнению буфера. Исключение составляют написанные на интерпретируемых языках среды, хотя сами интерпретаторы тоже могут быть подвержены переполнению.
Как уменьшить влияние переполнения буфера:
Stack Underflow
Такая уязвимость возникает, когда две части программы по-разному обрабатывают один и тот же блок памяти. Например, если вы выделите массив размером X, но заполните его массивом размером x
Вы, возможно, извлекли данные, которые остались после использования этой области памяти ранее. В лучшем случае это мусор, который ничего не значит, а в худшем – конфиденциальные данные, которыми может злоупотребить злоумышленник.
Заключение
Рассмотренная уязвимость является очень серьезной угрозой стабильной работе любого продукта. Необходимо приложить все усилия и проверить ваши проекты на ее наличие, т. к. последствия могут быть весьма плачевными (уже упоминался Ransome ) и болезненными. Используйте советы из статьи и вы уменьшите вероятность успешного проникновения злоумышленников в ваш код. Удачи в обучении!