Ошибка n 39 численное переполнение данные потеряны переполнение

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

Целочисленное переполнение может быть продемонстрировано с помощью одометр переполнение, механическая версия явления. Все цифры устанавливаются на максимум 9, и следующее приращение белой цифры вызывает каскад переходящих добавлений, устанавливающих все цифры на 0, но нет более высокой цифры (цифра 100000), которая могла бы измениться на 1, поэтому счетчик сбрасывается в ноль. Это обертывание в отличие от насыщения.

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

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

Состояние переполнения может привести к непредвиденным результатам. В частности, если возможность не была предвидена, переполнение может поставить под угрозу надежность программы и безопасность.

. Для некоторых приложений, таких как таймеры и часы, может быть желательным перенос при переполнении. В стандарте C11 указано, что для беззнаковых целых чисел перенос по модулю является определенным поведением, и термин «переполнение» никогда не применяется: «вычисление, включающее беззнаковые операнды, никогда не может переполниться».

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

Содержание

• 1 Источник
• 2 Флаги
• 3 Варианты определения и неоднозначность
• 4 Методы решения проблем целочисленного переполнения
  • 4.1 Обнаружение
  • 4.2 Предотвращение
  • 4.3 Обработка
  • 4.4 Явное распространение
  • 4.5 Поддержка языка программирования
  • 4.6 Насыщенная арифметика
• 5 Примеры
• 6 См. Также
• 7 Ссылки
• 8 Внешние ссылки

Источник

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

• 4 бита: максимальное представимое значение 2-1 = 15
• 8 битов: максимальное представимое значение 2-1 = 255
• 16 бит: максимальное представляемое значение 2-1 = 65 535
• 32 бита: максимальное представляемое значение 2-1 = 4294967 295 (наиболее распространенная ширина для персональных компьютеров с 2005 года),
• 64 биты: максимальное представляемое значение 2-1 = 18,446,744,073,709,551,615 (наиболее распространенная ширина для персональных компьютеров процессоров, по состоянию на 2017 год),
• 128 бит: максимальное представляемое значение 2-1 = 340,282,366,920,938,463,463,374,607,431,768,211,455

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

В частности, умножение или сложение двух целых чисел может привести к неожиданно маленькому значению, а вычитание из маленького целого числа может вызвать перенос на большое положительное значение (например, сложение 8-битных целых чисел 255 + 2 дает 1, что составляет 257 по модулю 2, и аналогичным образом вычитание 0 — 1 дает 255, дополнение до двух представление -1).

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

Если переменная имеет тип целое число со знаком, программа может сделать предположение, что переменная всегда содержит положительное значение. Целочисленное переполнение может привести к переносу значения и стать отрицательным, что нарушает предположение программы и может привести к неожиданному поведению (например, сложение 8-битного целого числа 127 + 1 дает -128, дополнение до двух до 128). (Решением этой конкретной проблемы является использование целочисленных типов без знака для значений, которые программа ожидает и предполагает, что они никогда не будут отрицательными.)

Флаги

Большинство компьютеров имеют два выделенных флага процессора для проверки условия переполнения.

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

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

Варианты определения и неоднозначность

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

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

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

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

Методы решения проблем целочисленного переполнения

Обработка целочисленного переполнения в различных языках программирования

Обнаружение

Реализация обнаружения переполнения во время выполнения UBSanдоступна для Компиляторы C.

В Java 8 есть перегруженные методы, например, такие как Math.addExact (int, int) , которые выбрасывают ArithmeticException в случае переполнения.

Группа реагирования на компьютерные чрезвычайные ситуации (CERT) разработала целочисленную модель с неограниченным диапазоном значений (AIR), в значительной степени автоматизированный механизм устранения переполнения и усечения целых чисел в C / C ++ с использованием обработки ошибок времени выполнения.

Предотвращение

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

Обработка

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

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

Явное распространение

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

Поддержка языков программирования

В языках программирования реализованы различные методы предотвращения случайного переполнения: Ada, Seed7 (и некоторые варианты функциональных языков) запускают условие исключения при переполнении, тогда как Python (начиная с версии 2.4) легко преобразует внутреннее представление числа в соответствии с его ростом, в конечном итоге представляя его как long— чьи возможности ограничены только доступной памятью.

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

Насыщенная арифметика

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

Примеры

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

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

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

30 апреля 2015 года Федеральное управление гражданской авиации США объявил, что прикажет операторам Boeing 787 периодически перезагружать его электрическую систему, чтобы избежать целочисленного переполнения, которое может привести к потере электроэнергии и развертыванию воздушной турбины, и Boeing развернул обновление ПО в четвертом квартале. Европейское агентство по авиационной безопасности последовало 4 мая 2015 года. Ошибка возникает через 2 центсекунды (248,55134814815 дней), указывая на 32-битное подписанное целое число.

. очевидно в некоторых компьютерных играх. В аркадной игре Donkey Kong, невозможно продвинуться дальше 22 уровня из-за целочисленного переполнения его времени / бонуса. Игра берет номер уровня, на котором находится пользователь, умножает его на 10 и добавляет 40. Когда они достигают уровня 22, количество времени / бонуса равно 260, что слишком велико для его 8-битного регистра значений 256, поэтому он сбрасывается. до 0 и дает оставшиеся 4 как время / бонус — слишком мало для завершения уровня. В Donkey Kong Jr. Math при попытке вычислить число, превышающее 10 000, отображаются только первые 4 цифры. Переполнение является причиной знаменитого уровня «разделенного экрана» в Pac-Man и «Ядерного Ганди» в Civilization. Это также привело к появлению «Дальних земель» в Minecraft, которые существовали с периода разработки Infdev до Beta 1.7.3; однако позже это было исправлено в Beta 1.8, но все еще существует в версиях Minecraft Pocket Edition и Windows 10 Edition. В игре Super Nintendo Lamborghini American Challenge игрок может заставить свою сумму денег упасть ниже 0 долларов во время гонки, будучи оштрафованным сверх лимита оставшихся денег после уплаты сбора за гонка, в которой происходит сбой целого числа, и игрок получает на 65 535 000 долларов больше, чем он получил бы после отрицательного результата. Подобный сбой происходит в S.T.A.L.K.E.R.: Clear Sky, где игрок может упасть до отрицательной суммы, быстро путешествуя без достаточных средств, а затем перейти к событию, где игрока ограбят и у него заберут всю валюту. После того, как игра попытается забрать деньги игрока на сумму в 0 долларов, игроку выдается 2147482963 игровой валюты.

В структуре данных Покемон в играх с покемонами число полученных очков опыта хранится в виде 3-байтового целого числа. Однако в первом и втором поколениях группа опыта со средней медленной скоростью, которой требуется 1 059 860 очков опыта для достижения 100 уровня, по расчетам имеет -54 очка опыта на уровне 1. Поскольку целое число не имеет знака, значение превращается в 16 777 162. Если покемон набирает менее 54 очков опыта в битве, то покемон мгновенно перескакивает на 100-й уровень. Кроме того, если эти покемоны на уровне 1 помещаются на ПК, и игрок пытается их вывести, игра вылетает., из-за чего эти покемоны навсегда застревают на ПК. В тех же играх игрок, используя Редкие Конфеты, может повысить уровень своего Покемона выше 100 уровня. Если он достигает уровня 255 и используется другая Редкая Конфета, то уровень переполняется до 0 (из-за того, что уровень кодируется в один байт, например, 64 16 соответствует уровню 100).

Ошибка целочисленной подписи в коде настройки стека, выпущенная компилятором Pascal, помешала Microsoft / IBM MACRO Assembler Version 1.00 (MASM), DOS программа 1981 года и многие другие программы, скомпилированные с помощью того же компилятора, для работы в некоторых конфигурациях с объемом памяти более 512 КБ.

Microsoft / IBM MACRO Assembler (MASM) версии 1.00 и, вероятно, все другие программы, созданные с помощью того же Компилятор Паскаля имел ошибку переполнения целого числа и подписи в коде настройки стека, что не позволяло им работать на новых машинах DOS или эмуляторах в некоторых распространенных конфигурациях с более чем 512 КБ памяти. Программа либо зависает, либо отображает сообщение об ошибке и выходит в DOS.

В августе 2016 года автомат казино в Resorts World Casino распечатал призовой билет на 42 949 672,76 долларов в результате ошибки переполнения. Казино отказалось выплатить эту сумму, назвав это неисправностью, используя в свою защиту то, что в автомате четко указано, что максимальная выплата составляет 10 000 долларов, поэтому любой превышающий эту сумму приз должен быть результатом ошибки программирования. Верховный суд штата Айова вынес решение в пользу казино.

См. Также

• Переполнение буфера
• Переполнение кучи
• Переключение указателя
• Тестирование программного обеспечения
• буфер стека переполнение
• Статический анализ программы
• Сигнал Unix

Ссылки

Внешние ссылки

• Фракция № 60, Базовое целочисленное переполнение
• Фракция № 60, Целочисленная защита большого цикла
• Эффективная и Точное обнаружение целочисленных атак
• Классификация угроз WASC — Целочисленные переполнения
• Общие сведения о целочисленном переполнении в C / C ++
• Двоичное переполнение — двоичная арифметика
• Стандарт ISO C11

The previous postings all commented on the C99 standard, but in fact this guarantee was already available earlier.

The 5th paragraph of Section 6.1.2.5 Types

of the C89 standard states

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting unsigned
integer type is reduced modulo the number that is one greater than
the largest value that can be represented by the resulting unsigned integer type.

Note that this allows C programmers to replace all unsigned divisions by some constant to be replaced by a multiplication with the inverse element of the ring formed by C’s modulo 2^N interval arithmetic.

And this can be done without any «correction» as it would be necessary by approximating the division with a fixed-point multiplication with the reciprocal value.

Instead, the Extended Euclidian Algorithm can be used to find the inverse Element and use it as the multiplier. (Of course, for the sake of staying portable, bitwise AND operations should also be applied in order to ensure the results have the same bit widths.)

It may be worthwhile to comment that most C compilers already implement this as an optimization. However, such optimizations are not guaranteed, and therefore it might still be interesting for programmers to perform such optimizations manually in situations where speed matters, but the capabilities of the C optimizer are either unknown or particularly weak.

And as a final remark, the reason for why trying to do so at all: The machine-level instructions for multiplication are typically much faster than those for division, especially on high-performance CPUs.

The previous postings all commented on the C99 standard, but in fact this guarantee was already available earlier.

The 5th paragraph of Section 6.1.2.5 Types

of the C89 standard states

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting unsigned
integer type is reduced modulo the number that is one greater than
the largest value that can be represented by the resulting unsigned integer type.

Note that this allows C programmers to replace all unsigned divisions by some constant to be replaced by a multiplication with the inverse element of the ring formed by C’s modulo 2^N interval arithmetic.

And this can be done without any «correction» as it would be necessary by approximating the division with a fixed-point multiplication with the reciprocal value.

Instead, the Extended Euclidian Algorithm can be used to find the inverse Element and use it as the multiplier. (Of course, for the sake of staying portable, bitwise AND operations should also be applied in order to ensure the results have the same bit widths.)

It may be worthwhile to comment that most C compilers already implement this as an optimization. However, such optimizations are not guaranteed, and therefore it might still be interesting for programmers to perform such optimizations manually in situations where speed matters, but the capabilities of the C optimizer are either unknown or particularly weak.

And as a final remark, the reason for why trying to do so at all: The machine-level instructions for multiplication are typically much faster than those for division, especially on high-performance CPUs.

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

Целочи́сленное переполне́ние (англ. integer overflow) — ситуация в компьютерной арифметике, при которой вычисленное в результате операции значение не может быть помещено в n-битный целочисленный тип данных. Различают переполнение через верхнюю границу представления и через нижнюю (англ. Underflow).

Пример: сложение двух переменных размером 8 бит с записью результата в переменную того же размера:

[math]displaystyle{ 210_{10} + 61_{10} = 11010010_{2} + 00111101_{2} = ? }[/math]

[math]displaystyle{
begin{array}{c}
begin{array}{cc}
+ & begin{array}{c}
11010010_{2}
00111101_{2}
end{array}
end{array}
hline
begin{array}{cc}
& {color{Red}1}00001111_{2}
end{array}
end{array}
}[/math]

возникает переполнение.

При этом в результат записывается не ожидаемое [math]displaystyle{ 271_{10} = {color{Red}1}00001111_2 }[/math], а [math]displaystyle{ 15_{10} = 00001111_2 }[/math]. Стоит отметить, что вычисление здесь произошло по модулю 2ⁿ, а арифметика по модулю циклическая, то есть 255+1=0 (при n = 8). Данная ситуация переполнения фиксируется вычислительной машиной установкой специальных битов регистра флагов Overflow и Carry (пункт 3.4.3.1 Combined Volume: Volume 1^[1]). При программировании на языке ассемблера такую ситуацию можно напрямую установить, например, вручную проверив состояние регистра флагов после выполнения операции (пункт 7.3.13.2 Combined Volume: Volume 1^[1]).

Происхождение проблемы

Битность регистра определяет диапазон данных, представимый в нём. Диапазоны представления для целых типов в бинарных вычислительных машинах:

Переполнение может возникнуть в исходном коде вследствие ошибки программиста или его недостаточной бдительности к входным данным^[2].

• Несоответствие знакового и беззнакового. Если числа представляются на вычислителе в дополнительном коде, то одному потоку бит соответствуют различные числа. В 32-битной арифметике знаковому −1 соответствует беззнаковое 4294967295 (верхняя граница представления). То есть приведение одного типа к другому может привести к значительной разнице в значении. Этот тип ошибки часто является последствием signedness error ( and), то есть неправильного приведения типов между типами разной знаковости
• Проблема срезки. Возникает, если число интерпретируется как целое меньшей длины. В таком случае только младшие биты останутся в числе. Старшие отбросятся, что приведет к изменению численного значения
• Знаковое расширение. Стоит помнить, что при приведении знакового числа к типу большей длины происходит копирование старшего бита, что в случае интерпретации как беззнаковое приведет к получению очень большого числа^[3]

Риски для безопасности

Возможность переполнения широко используется программистами, например, для хеширования и криптографии, генерирования случайных чисел и нахождения границ представления типа^[4]. В то же время, например, по стандарту языков C и C++, беззнаковые вычисления выполняются по модулю 2, в то время как знаковое переполнение является классическим примером^[5] неопределённого поведения^[6].

Такой вид некорректности в коде ведёт к следующим последствиям^[4]:

1. Компиляция может пойти неожиданным образом. Из-за наличия неопределённого поведения в программе, оптимизации компилятора могут изменить поведение программы.
2. Бомба замедленного действия. На текущей версии ОС, компилятора, опций компиляции, структурной организации программы и т. д. всё может работать, а при любом изменении, например, появлении более агрессивных оптимизаций, сломаться.
3. Иллюзия предсказуемости. Конкретная конфигурация компилятора может иметь вполне определённое поведение, например компиляторы языков C и C++ обычно реализуют операции по модулю 2ⁿ и для знаковых типов (только интерпретированных в дополнительном коде), если отключены агрессивные оптимизации. Однако, надеяться на такое поведение нельзя, иначе есть риск эффекта «бомбы замедленного действия»
4. Образование диалектов. Некоторые компиляторы предоставляют дополнительные опции для того, чтобы доопределить неопределённое поведение. Например, и GCC, и Clang поддерживают опцию -fwrapv, обеспечивающую выше описанное (в пункте 3) поведение.

Изменение стандарта может привести к новым проблемам с переполнением. К примеру, 1<<31 было зависимым от реализации в стандартах ANSI C и C++98, в то время как стали неопределённым в C99 и C11 (для 32-битных целых).^[4]

Также, последствиями такой ошибки могут быть и другие, например переполнение буфера.

Эксплуатация и последствия

Основные последствия для безопасности^[7]:

• Для доступности. Возможный отказ системы (окно для DoS-атак)
• Для целостности. Неавторизированный доступ к данным
• Для конфиденциальности. Исполнение стороннего кода, обход защитного механизма

Классически переполнение может быть эксплуатировано через переполнение буфера.

img_t* table_ptr; /*struct containing img data, 10kB each*/
int num_imgs;
...
num_imgs = get_num_imgs();
table_ptr = (img_t*)malloc(sizeof(img_t)*num_imgs);
...

Данный пример^[7] иллюстрирует сразу несколько уязвимостей. Во-первых, слишком большой num_imgs приведёт к выделению огромного буфера, из-за чего программа может потребить все ресурсы системы или вызвать её крах.

Другая уязвимость в том, что если num_imgs ещё больше, это приведёт к переполнению аргумента malloc. Тогда выделится лишь небольшой буфер. При записи в него произойдёт переполнение буфера, последствиями чего могут стать: перехват контроля над исполнением, исполнение кода злоумышленника, доступ к важной информации.^[8]

Предотвращение проблемы

Защита от подобного поведения должна проводиться на нескольких уровнях^[7]:

1. Планирования и требований к программе:
   • Убедитесь, что все протоколы взаимодействия между компонентами строго определены. В том числе, что все вычисления вне границ представления будут обнаружены. И требуйте строгого соответствия этим протоколам
   • Используйте язык программирования и компилятор, которые не позволяет этой уязвимости воплотиться, либо позволяют легче её обнаружить, либо выполняют авто-проверку границ. Инструменты, которые предоставляются компилятором, включают санитайзеры (например, Address Sanitizer^[en] или Undefined Behavior Sanitizer).
2. Архитектуры программы:
   • Используйте проверенные библиотеки или фреймворки, помогающие проводить вычисления без риска непредсказуемых последствий. Примеры включают такие библиотеки, как SafeInt (C++) или IntegerLib (C или C++).
   • Любые проверки безопасности на стороне клиента должны быть продублированы на стороне сервера, чтобы не допустить CWE-602. Злоумышленник может миновать проверку на стороне клиента, изменив сами значения непосредственно после прохождения проверки или модифицируя клиента, чтобы полностью убрать проверки.
3. Реализации:
   • Проводите валидацию любых поступивших извне числовых данных, проверяя что они находятся внутри ожидаемого диапазона. Проверяйте обязательно как минимальный порог, так и максимальный. Используйте беззнаковые числа, где это возможно. Это упростит проверки на переполнение.
   • Исследуйте все необходимые нюансы языка программирования, связанные с численными вычислениями (CWE-681). Как они представляются, какие различия между знаковыми и беззнаковыми, 32-битными и 64-битными, проблемы при кастовании (обрезка, знаково-беззнаковое приведения типов — выше) и как обрабатываются числа, слишком маленькие или, наоборот, большие для их машинного представления. Также убедитесь, что используемый вами тип (например, int или long) покрывают необходимый диапазон представления
   • Подробно изучите полученные от компилятора предупреждения и устраните возможные проблемы безопасности, такие как несоответствия знаковости операндов при операциях с памятью или использование неинициализированных переменных. Даже если уязвимость совсем небольшая, это может привести к опасности для всей системы.

Другие правила, позволяющие избежать этих уязвимостей, опубликованы в стандарте CERT C Secure Coding Standard в 2008 году, включают^[9]:

• Не пишите и не используйте функции обработки строкового ввода, если они обрабатывают не все случаи
• Не используйте битовые операции над знаковыми типами
• Вычисляйте выражения на типе большего размера перед сравнением или присваиванием в меньший
• Будьте внимательны перед приведением типа между числом и указателем
• Убедитесь, что вычисления по модулю или результаты деления не приводят к последующему делению на ноль
• Используйте intmax_t или uintmax_t для форматированного ввода-вывода пользовательских числовых типов

Примеры из жизни

Исследование SPECCINT

В статье^[4] в качестве предмета исследования программ на языках C и C++ на целочисленное переполнение подробно исследуется один из самых широко применимых и известных тестовых пакетов SPEC, используемый для измерений производительности. Состоит он из фрагментов наиболее распространённых задач, как то: тестов вычислительной математики, компиляции, работы с базами данных, диском, сетью и прочее.

Результаты анализа SPECCINT2000 показывают наличие 219 статических источников переполнения в 8 из 12 бенчмарков, из которых 148 использовали беззнаковое переполнение и 71 — знаковое (снова неопределённое поведение). В то же время, беззнаковое переполнение тоже не всегда намеренное и может являться ошибкой и источником уязвимости (например, Listing 2 той же статьи^[4]).

Также был проведён тест на «бомбы замедленного действия» в SPECCINT2006. Его идеей является в каждом месте неопределённого поведения вернуть случайное число и посмотреть, к каким последствиям это может привести. Если оценивать неопределённое поведение с точки зрения стандарта C99/C++11, то тест не пройдут целых 6 бенчмарков из 9.

Примеры из других программных пакетов

int addsi (int lhs, int rhs) {
    errno = 0;
    if (((( lhs+rhs)^lhs)&(( lhs+rhs)^rhs)) >> (sizeof(int)*CHAR_BIT -1)) {
        error_handler("OVERFLOW ERROR", NULL, EOVERFLOW);
        errno = EINVAL;
    }
    return lhs + rhs;
}

Данный фрагмент кода^[4] из пакета IntegerLib проверяет, могут ли быть lhs и rhs сложены без переполнения. И ровно в строчке 3 это переполнение может возникнуть (при сложении lhs+rhs). Это UB, так как lhs и rhs — знакового типа. Кроме этого, в данной библиотеке найдено ещё 19 UB-переполнений.

Также авторы сообщили разработчикам о 13 переполнениях в SQLite, 43 в SafeInt, 6 в GNU MPC library, 30 в PHP, 18 в Firefox, 71 в GCC, 29 в PostgreSQL, 5 в LLVM и 28 в Python. Большинство из ошибок были вскоре исправлены.

Другие примеры

Известный пример целочисленного переполнения происходит в игре Pac-Man, так же, как и в других играх серии: Ms. Pac-Man, Jr. Pac-Man. Также этот глюк появляется в Pac-Man Google Doodle в качестве так называемого «пасхального яйца».^[10] Здесь же на уровне 256 можно наблюдать «экран смерти», а сам уровень называют «уровнем разделенного экрана». Энтузиасты дизассемблировали исходный код, пытаясь исправить ошибку модифицированием игры.

Такая же проблема якобы была в игре Sid Meier’s Civilization и известна как Ядерный Ганди^[11]. Согласно легенде, на определённом этапе игры с очень миролюбивым Ганди, происходит переполнение через 0 уровня враждебности, результатом чего может стать ядерная война с Ганди. На самом деле, такой миф появился лишь с выходом Civilization V, где параметр его искусственного интеллекта, регулирующий создание и использование ядерного вооружения, имеет наивысшее значение 12, что не противоречило тому, что Ганди является одним из самых миролюбивых лидеров в игре^[12].

Ещё одним примером является глюк в SimCity 2000^[13]. Здесь дело в том, что бюджет игрока стал очень большим, а после перехода через 2³¹ внезапно стал отрицательным. Игра оканчивается поражением.

Этот глюк из Diablo III. Из-за одного из изменений патча 1.0.8, игровая экономика сломалась. Максимальную сумму для сделок повысили с 1 млн до 10 млн. Стоимость покупки переполнялась через 32-битный тип, а при отмене операции возвращалась полная сумма. То есть игрок оставался с прибылью в 2³² игровой валюты^[14]

См. также

• Переполнение буфера
• Переполнение стека

Примечания

Действие по умолчанию зависит от процессора, компилятора и настроек. На MIPS, например, его «классические» компиляторы превращали сложение знаковых в команду add, которая генерирует исключение при переполнении, а беззнаковых — addu, которая не генерирует. Но gcc, clang уже такого не делали, всё через addu. На x86 — родные команды add, sub игнорируют переполнение (точнее, ставят флаг CF или OF, но не генерируют исключение).
Компиляторы современного типа считают, что переполнения в операциях с целыми со знаком не должно быть, иногда из-за этого возникают интересные эффекты — вот самый убойный пример из тех, что я видел. Стандарт тут действует по принципу «мы вам даём возможность писать максимально эффективно, потому что это C, а не учебный язык, а защита от кривостей — ваша проблема». В отличие от них, для целых без знака определено поведение как для арифметики по модулю 2**N, где N — количество битов в значении. Это различие возникло из-за того, что не было извесно в общем случае, какое представление целых со знаком будет из набора: прямой код (sign and magnitude), обратный код (1ʼs complement), дополнительный код (0ʼs complement, но на устоявшемся уже жаргоне twoʼs complement), это сейчас можно смело говорить, что кроме дополнительного кода вариантов нет. Но потом это различие было реально заабьюзено на возможность делать хитрые оптимизации на основании предположения о непереполнении.

Для C++ есть, например, библиотечка (шаблонный заголовочный файл) SafeInt3 от Microsoft, под свободной лицензией; ею можно покрыть все основные операции, хотя она весьма стара, не использует специфику процессоров (даже x86) и оттого во многих случаях неэффективна — там, где достаточно одного OF или CF, или overflow builtins от GCC, она городит много сложных расчётов.

Для C придётся всё писать вручную, заменяя обычные операции на свои эквиваленты функциями или макросами.

Про новые встроенные функции последних gcc и clang (__builtin_add_overflow, __builtin_mul_overflow и вся группа) уже писали. На них можно всегда получить урезанное (оно же wrapped) значение операции (как в 16 битах 30000 + 30000 -> -5536), и признак переполнения, и можно получать каждый из них безопасно (не будет неожиданных оптимизаций). Но и без них можно сделать достаточно неплохо. Например, в случае сложения двух int, проверка вида a > INT_MAX - b, если b > 0, иначе a < INT_MIN - b, достаточна, чтобы проверить разрешимость сложения. Самое тяжёлое тут проверка умножения без поддержки компилятора: единственным всегда работающим вариантом считается проверка делением, а это очень дорого. Я считаю, что overflow builtins надо ввести во все стандарты (кроме нынешнего набора add, mul, div добавить ещё shl).

Теги: Переполнение целых, переполнение целых без знака, int overflow, unsigned overflow.

int sum1(int a, int b, int *overflow) {
	int c = 0;
	if (a > 0 && b > 0 && (INT_MAX - b < a) || 
		a < 0 && b < 0 && (INT_MIN - b > a)) {
		*overflow = 1;
	} else {
		*overflow = 0;
		c = a + b;
	}
	return c;
}

int sum2(int a, int b, int *overflow) {
	signed long long c = (signed long long) a + (signed long long) b;
	if (c < INT_MAX && c > INT_MIN) {
		*overflow = 0;
		c = a + b;
	} else {
		*overflow = 1;
	}
	return (int) c;
}

int sum3(int a, int b, int *overflow) {
	int noOverflow = 1;
	int c = a + b;
	__asm {
		jno NO_OVERFLOW
		mov noOverflow, 0
	NO_OVERFLOW:
	}
	if (noOverflow) {
		*overflow = 0;
	} else {
		*overflow = 1;
	}
	return c;
}

mov noOverflow, 0

unsigned usumm(unsigned a, unsigned b, int *overflow) {
	unsigned c = a + b;
	if (c < a || c < b) {
		*overflow = 1;
	} else {
		*overflow = 0;
	}
	return c;
}

#include <conio.h>
#include <stdio.h>
#include <limits.h>

int sum1(int a, int b, int *overflow) {
	int c = 0;
	if (a > 0 && b > 0 && (INT_MAX - b < a) || 
		a < 0 && b < 0 && (INT_MIN - b > a)) {
		*overflow = 1;
	} else {
		*overflow = 0;
		c = a + b;
	}
	return c;
}

int sum2(int a, int b, int *overflow) {
	signed long long c = (signed long long) a + (signed long long) b;
	if (c < INT_MAX && c > INT_MIN) {
		*overflow = 0;
		c = a + b;
	} else {
		*overflow = 1;
	}
	return (int) c;
}

int sum3(int a, int b, int *overflow) {
	int noOverflow = 1;
	int c = a + b;
	__asm {
		jno NO_OVERFLOW
		mov noOverflow, 0
	NO_OVERFLOW:
	}
	if (noOverflow) {
		*overflow = 0;
	} else {
		*overflow = 1;
	}
	return c;
}

unsigned usumm(unsigned a, unsigned b, int *overflow) {
	unsigned c = a + b;
	if (c < a || c < b) {
		*overflow = 1;
	} else {
		*overflow = 0;
	}
	return c;
}

void main() {
	int overflow;
	int sum;
	unsigned usum;
	//sum1
	sum = sum1(3, 5, &overflow);
	printf("%d + %d = %d (%d)n", 3, 5, sum, overflow);
	sum = sum1(INT_MAX, 5, &overflow);
	printf("%d + %d = %d (%d)n", INT_MAX, 5, sum, overflow);
	sum = sum1(INT_MIN, -5, &overflow);
	printf("%d + %d = %d (%d)n", INT_MIN, -5, sum, overflow);
	sum = sum1(INT_MAX, INT_MIN, &overflow);
	printf("%d + %d = %d (%d)n", INT_MAX, INT_MIN, sum, overflow);
	sum = sum1(-10, -20, &overflow);
	printf("%d + %d = %d (%d)n", -10, -20, sum, overflow);
	//sum2
	sum = sum2(3, 5, &overflow);
	printf("%d + %d = %d (%d)n", 3, 5, sum, overflow);
	sum = sum2(INT_MAX, 5, &overflow);
	printf("%d + %d = %d (%d)n", INT_MAX, 5, sum, overflow);
	sum = sum2(INT_MIN, -5, &overflow);
	printf("%d + %d = %d (%d)n", INT_MIN, -5, sum, overflow);
	sum = sum2(INT_MAX, INT_MIN, &overflow);
	printf("%d + %d = %d (%d)n", INT_MAX, INT_MIN, sum, overflow);
	sum = sum2(-10, -20, &overflow);
	printf("%d + %d = %d (%d)n", -10, -20, sum, overflow);
	//sum3
	sum = sum3(3, 5, &overflow);
	printf("%d + %d = %d (%d)n", 3, 5, sum, overflow);
	sum = sum3(INT_MAX, 5, &overflow);
	printf("%d + %d = %d (%d)n", INT_MAX, 5, sum, overflow);
	sum = sum3(INT_MIN, -5, &overflow);
	printf("%d + %d = %d (%d)n", INT_MIN, -5, sum, overflow);
	sum = sum3(INT_MAX, INT_MIN, &overflow);
	printf("%d + %d = %d (%d)n", INT_MAX, INT_MIN, sum, overflow);
	sum = sum3(-10, -20, &overflow);
	printf("%d + %d = %d (%d)n", -10, -20, sum, overflow);
	//usum
	usum = usumm(10u, 20u, &overflow);
	printf("%u + %u = %u (%d)n", 10u, 20u, usum, overflow);
	usum = usumm(UINT_MAX, 20u, &overflow);
	printf("%u + %u = %u (%d)n", UINT_MAX, 20u, usum, overflow);
	usum = usumm(20u, UINT_MAX, &overflow);
	printf("%u + %u = %u (%d)n", 20u, UINT_MAX, usum, overflow);
	getch();
}

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

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

Состояние переполнения может привести к непреднамеренному поведению. В частности, если возможность не была предвидена, переполнение может поставить под угрозу надежность программы и безопасность.

Для некоторых приложений, таких как таймеры и часы, может быть желательно перенос при переполнении. В C11 Стандарт утверждает, что для беззнаковых целых чисел перенос по модулю является определенным поведением, и термин «переполнение» никогда не применяется: «вычисление с участием беззнаковых операндов никогда не может переполниться».^[1]

На некоторых процессорах вроде графические процессоры (GPU) и цифровые сигнальные процессоры (DSP), которые поддерживают арифметика насыщения, результаты переполнения будут «закреплены», то есть установлены на минимальное или максимальное значение в представимом диапазоне, а не на перенос.

Источник

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

• 4 бита: максимальное представимое значение 2⁴ — 1 = 15
• 8 бит: максимальное представимое значение 2⁸ − 1 = 255
• 16 бит: максимальное представимое значение 2¹⁶ − 1 = 65,535
• 32 бита: максимальное представимое значение 2³² — 1 = 4 294 967 295 (наиболее распространенная ширина для персональных компьютеров с 2005 г.),
• 64 бита: максимальное представимое значение 2⁶⁴ — 1 = 18 446 744 073 709 551 615 (наиболее распространенная ширина для персонального компьютера Процессоры, по состоянию на 2017 год),
• 128 бит: максимальное представимое значение 2¹²⁸ − 1 = 340,282,366,920,938,463,463,374,607,431,768,211,455

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

В частности, умножение или сложение двух целых чисел может привести к неожиданно маленькому значению, а вычитание из небольшого целого числа может вызвать перенос на большое положительное значение (например, сложение 8-битных целых чисел 255 + 2 дает 1, что является 257 мод 2⁸, и аналогично вычитание 0-1 дает 255, a два дополнения представление −1).

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

Если переменная имеет целое число со знаком типа, программа может сделать предположение, что переменная всегда содержит положительное значение. Целочисленное переполнение может привести к переносу значения и стать отрицательным, что нарушает предположение программы и может привести к неожиданному поведению (например, сложение 8-битного целого числа 127 + 1 дает -128, дополнение до двух до 128). (Решением этой конкретной проблемы является использование целочисленных типов без знака для значений, которые программа ожидает и предполагает, что они никогда не будут отрицательными.)

Флаги

Большинство компьютеров имеют два выделенных флага процессора для проверки условий переполнения.

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

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

Варианты определения и неоднозначность

Для беззнакового типа, когда идеальный результат операции находится за пределами представимого диапазона типа и возвращаемый результат получается путем упаковки, это событие обычно определяется как переполнение. Напротив, стандарт C11 определяет, что это событие не является переполнением, и заявляет, что «вычисление с участием беззнаковых операндов никогда не может переполниться».^[1]

Когда идеальный результат целочисленной операции выходит за пределы представимого диапазона типа и возвращаемый результат получается путем ограничения, то это событие обычно определяется как насыщение. Использование различается в зависимости от того, является ли насыщение переполнением или нет. , условия переноса переполнены^[2]и насыщающий перелив^[3]может быть использован.

Термин «потеря значимости» чаще всего используется для математики с плавающей запятой, а не для целочисленной.^[4]Но можно найти много ссылок на целочисленное исчезновение.^{[5][6][7][8][9]}Когда используется термин целочисленное отсутствие переполнения, это означает, что идеальный результат был ближе к минус бесконечности, чем представимое значение выходного типа, ближайшее к минус бесконечности. Когда используется термин целочисленное недополнение, определение переполнения может включать все типы переполнения или только включают случаи, когда идеальный результат был ближе к положительной бесконечности, чем представимое значение выходного типа, ближайшее к положительной бесконечности.

Когда идеальный результат операции не является точным целым числом, значение переполнения может быть неоднозначным в крайних случаях. Рассмотрим случай, когда идеальный результат имеет значение 127,25, а максимальное представимое значение типа вывода равно 127. Если переполнение определяется как Если идеальное значение находится за пределами представимого диапазона выходного типа, то этот случай будет классифицирован как переполнение. Для операций, которые имеют четко определенное поведение округления, может потребоваться отложить классификацию переполнения до тех пор, пока не будет применено округление. Стандарт C11^[1]определяет, что преобразования из числа с плавающей запятой в целое число должны округляться в сторону нуля. Если для преобразования значения 127,25 с плавающей запятой в целое число используется C, то сначала следует применить округление, чтобы получить идеальное целое число на выходе 127. Так как округленное целое число находится на выходе диапазон, стандарт C не классифицирует это преобразование как переполнение.

Методы решения проблем целочисленного переполнения

Обработка целочисленного переполнения в различных языках программирования

Обнаружение

Реализация обнаружения переполнения во время выполнения UBSan доступен для Компиляторы C.

В Java 8 есть перегруженные методы, например как Math.addExact (целое, целое), который бросит ArithmeticException в случае переполнения.

Группа реагирования на компьютерные чрезвычайные ситуации (CERT) разработала целочисленную модель с неограниченным диапазоном значений (AIR) — в значительной степени автоматизированный механизм для устранения переполнения и усечения целых чисел в C / C ++ с использованием обработки ошибок времени выполнения.^[13]

Избегание

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

Умение обращаться

Если ожидается, что может произойти переполнение, тогда в программу можно вставить тесты, чтобы определить, когда это произойдет, и выполнить другую обработку, чтобы смягчить его. Например, если важный результат, вычисленный из переполнения пользовательского ввода, программа может остановиться, отклонить ввод и, возможно, предложить пользователю другой ввод, вместо того, чтобы программа продолжала работу с недопустимым переполненным вводом и, возможно, как следствие, неисправна. Этот полный процесс можно автоматизировать: можно автоматически синтезировать обработчик для целочисленного переполнения, где обработчик, например, является чистым выходом.^[14]

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

Явное распространение

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

Поддержка языков программирования

В языках программирования реализованы различные методы защиты от случайного переполнения: Ада, Семя7 (и некоторые варианты функциональных языков) запускают условие исключения при переполнении, а Python (начиная с версии 2.4) легко преобразует внутреннее представление числа в соответствии с его ростом, в конечном итоге представляя его как длинный — чьи возможности ограничены только доступной памятью.^[15]

На языках с нативной поддержкой Арифметика произвольной точности и безопасность типа (Такие как Python или же Common Lisp ), числа автоматически увеличиваются до большего размера при возникновении переполнения или при возникновении исключений (сигнализация условий) при наличии ограничения диапазона. Таким образом, использование таких языков может помочь смягчить эту проблему. Однако в некоторых таких языках все еще возможны ситуации, когда может произойти целочисленное переполнение. Примером является явная оптимизация пути кода, который профилировщик считает узким местом. В случае Common Lisp, это возможно с помощью явного объявления для аннотирования переменной типа машинного слова (fixnum)^[16] и понизить уровень безопасности типа до нуля^[17] для конкретного блока кода.^{[18][19][20][21]}

Насыщенная арифметика

В компьютерная графика или же обработка сигналов, обычно работают с данными в диапазоне от 0 до 1 или от -1 до 1. Например, возьмите оттенки серого image, где 0 представляет черный цвет, 1 представляет белый цвет, а значения между ними представляют оттенки серого. Одна операция, которую можно поддержать, — это осветление изображения путем умножения каждого пиксель на константу. Насыщенная арифметика позволяет просто слепо умножать каждый пиксель на эту константу, не беспокоясь о переполнении, просто придерживаясь разумного результата, что все эти пиксели больше 1 (т.е. «ярче белого» ) становится белым, а все значения «темнее черного» становятся черными.

Примеры

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

Складываем среднее арифметическое двух чисел и делим их на два, как это делается во многих случаях. алгоритмы поиска, вызывает ошибку, если сумма (хотя и не результирующее среднее) слишком велика для представления и, следовательно, переполняется.^[22]

Необработанное арифметическое переполнение в программном обеспечении рулевого управления двигателем было основной причиной аварии во время первого полета 1996 г. Ариана 5 ракета.^[23] Считалось, что программное обеспечение не содержит ошибок, так как оно использовалось во многих предыдущих полетах, но в них использовались ракеты меньшего размера, которые генерировали меньшее ускорение, чем Ariane 5. К сожалению, часть программного обеспечения, в которой произошла ошибка переполнения, даже не требовалась. запускался для Ariane 5 в то время, когда он привел к отказу ракеты — это был процесс режима запуска для меньшего предшественника Ariane 5, который остался в программном обеспечении, когда он был адаптирован для новой ракеты. Кроме того, фактической причиной сбоя была ошибка в технической спецификации того, как программное обеспечение справлялось с переполнением, когда оно было обнаружено: оно выполнило диагностический дамп на свою шину, которая должна была быть подключена к испытательному оборудованию во время тестирования программного обеспечения во время разработки. но был связан с двигателями рулевого управления ракеты во время полета; сброс данных сильно отклонил сопло двигателя в сторону, что вывело ракету из-под контроля аэродинамики и ускорило ее быстрое разрушение в воздухе.^[24]

30 апреля 2015 г. Федеральное управление гражданской авиации объявил, что закажет Боинг 787 операторы периодически перезагружают свою электрическую систему, чтобы избежать целочисленного переполнения, которое может привести к потере электроэнергии и набегающая воздушная турбина развертывание, и Boeing развернул обновление программного обеспечения в четвертом квартале.^[25] В Европейское агентство авиационной безопасности последовало 4 мая 2015 года.^[26] Ошибка возникает через 2 сотых секунды (248,55134814815 дней), что указывает на 32-битный подписанный целое число.

Ошибки переполнения очевидны в некоторых компьютерных играх. В аркадной игре Осел Конг, невозможно продвинуться дальше 22 уровня из-за целочисленного переполнения по времени / бонусу. Игра берет номер уровня, на котором находится пользователь, умножает его на 10 и добавляет 40. Когда они достигают уровня 22, количество времени / бонуса равно 260, что слишком велико для его 8-битного регистра значений 256, поэтому он сбрасывается. до 0 и дает оставшиеся 4 в качестве времени / бонуса — слишком мало для завершения уровня. В Donkey Kong Jr. Math, при попытке вычислить число больше 10 000 показывает только первые 4 цифры. Перелив — причина знаменитого уровень «разделенный экран» в Pac-Man^[27] и «Ядерный Ганди» в Цивилизация.^[28] Это также привело к появлению «Дальних земель» в Шахтерское ремесло который существовал с периода разработки Infdev до Beta 1.7.3; однако позже он был исправлен в Beta 1.8, но все еще существует в версиях Pocket Edition и Windows 10 Edition. Шахтерское ремесло.^[29] в Супер Нинтендо игра Lamborghini American Challenge, игрок может заставить свою сумму денег упасть ниже 0 долларов во время гонки, будучи оштрафованным сверх лимита оставшихся денег после уплаты сбора за гонку, что приводит к сбоям в работе целого числа и дает игроку на 65 535 000 долларов больше, чем он имел бы после прохождения отрицательный.^[30] Аналогичный глюк возникает в S.T.A.L.K.E.R .: Чистое небо где игрок может упасть до отрицательной суммы, быстро путешествуя без достаточных средств, а затем перейдя к событию, где игрока ограбят и у него отберут всю его валюту. После того, как игра попытается забрать деньги игрока на сумму в 0 долларов, игроку предоставляется 2147482963 игровой валюты.^[31]

В структуре данных Покемон в играх с покемонами количество полученных очков опыта хранится в виде 3-байтового целого числа. Однако в первом и втором поколениях группа опыта со средней медленной скоростью, которой требуется 1 059 860 очков опыта для достижения 100 уровня, по расчетам имеет -54 очка опыта на уровне 1. Поскольку целое число не имеет знака, значение превращается в 16 777 162. Если покемон набирает менее 54 очков опыта в битве, то покемон мгновенно перескакивает на 100-й уровень. Кроме того, если эти покемоны на уровне 1 помещаются на ПК, и игрок пытается их вывести, игра вылетает. , из-за чего эти покемоны навсегда застревают на ПК. В тех же играх игрок, используя Редкие Конфеты, может повысить уровень своего Покемона выше 100 уровня. Если он достигает уровня 255 и используется другая Редкая Конфета, то уровень переполняется до 0 (из-за того, что уровень кодируется в один байт, например, 64₁₆ соответствует уровню 100).^{[32][33][34][35]}

Microsoft / IBM MACRO Assembler (MASM) версии 1.00 и, вероятно, все другие программы, созданные тем же компилятором Pascal, имели целочисленное переполнение и ошибку подписи в коде настройки стека, что препятствовало их запуску на новых машинах DOS или эмуляторах с некоторыми распространенными конфигурации с объемом памяти более 512 КБ. Программа либо зависает, либо отображает сообщение об ошибке и выходит в DOS.^[36]

В августе 2016 года автомат казино в Курорты мира Казино распечатало призовой билет на 42 949 672,76 долларов в результате ошибки переполнения. Казино отказалось выплатить эту сумму, назвав это неисправностью, используя в свою защиту то, что в автомате четко указано, что максимальная выплата составляет 10 000 долларов, поэтому любой превышающий эту сумму приз должен быть результатом ошибки программирования. В Верховный суд Айовы вынесено решение в пользу казино.^[37]

Смотрите также

• Переполнение буфера
• Переполнение кучи
• Модульная арифметика
• Указатель swizzling
• Тестирование программного обеспечения
• Переполнение буфера стека
• Статический анализ программы
• Сигнал Unix

Рекомендации

внешняя ссылка

• Фракция № 60, Основные целочисленные переполнения
• Фрак № 60, Целочисленная защита большого цикла
• Эффективное и точное обнаружение целочисленных атак
• Классификация угроз WASC — целочисленные переполнения
• Понимание целочисленного переполнения в C / C ++
• Двоичное переполнение — двоичная арифметика
• Стандарт ISO C11

Целочи́сленное переполне́ние (англ. integer overflow) — ситуация в компьютерной арифметике, при которой вычисленное в результате операции значение не может быть помещено в n-битный целочисленный тип данных. Различают переполнение через верхнюю границу представления и через нижнюю (англ. Underflow).

Пример: сложение двух переменных размером 8 бит с записью результата в переменную того же размера:

возникает переполнение.

При этом в результат записывается не ожидаемое , а . Стоит отметить, что вычисление здесь произошло по модулю 2ⁿ, а арифметика по модулю циклическая, то есть 255+1=0 (при n = 8). Данная ситуация переполнения фиксируется вычислительной машиной установкой специальных битов регистра флагов Overflow и Carry (пункт 3.4.3.1 Combined Volume: Volume 1^[1]). При программировании на языке ассемблера такую ситуацию можно напрямую установить, например, вручную проверив состояние регистра флагов после выполнения операции (пункт 7.3.13.2 Combined Volume: Volume 1^[1]).

Происхождение проблемы

Битность регистра определяет диапазон данных, представимый в нём. Диапазоны представления для целых типов в бинарных вычислительных машинах:

Переполнение может возникнуть в исходном коде вследствие ошибки программиста или его недостаточной бдительности к входным данным^[2].

• Несоответствие знакового и беззнакового. Если числа представляются на вычислителе в дополнительном коде, то одному потоку бит соответствуют различные числа. В 32-битной арифметике знаковому −1 соответствует беззнаковое 4294967295 (верхняя граница представления). То есть приведение одного типа к другому может привести к значительной разнице в значении. Этот тип ошибки часто является последствием signedness error ( and), то есть неправильного приведения типов между типами разной знаковости
• Проблема срезки. Возникает, если число интерпретируется как целое меньшей длины. В таком случае только младшие биты останутся в числе. Старшие отбросятся, что приведет к изменению численного значения
• Знаковое расширение. Стоит помнить, что при приведении знакового числа к типу большей длины происходит копирование старшего бита, что в случае интерпретации как беззнаковое приведет к получению очень большого числа^[3]

Риски для безопасности

Возможность переполнения широко используется программистами, например, для хеширования и криптографии, генерирования случайных чисел и нахождения границ представления типа^[4]. В то же время, например, по стандарту языков C и C++, беззнаковые вычисления выполняются по модулю 2, в то время как знаковое переполнение является классическим примером^[5] неопределённого поведения^[6].

Такой вид некорректности в коде ведёт к следующим последствиям^[4]:

1. Компиляция может пойти неожиданным образом. Из-за наличия неопределённого поведения в программе, оптимизации компилятора могут изменить поведение программы.
2. Бомба замедленного действия. На текущей версии ОС, компилятора, опций компиляции, структурной организации программы и т. д. всё может работать, а при любом изменении, например, появлении более агрессивных оптимизаций, сломаться.
3. Иллюзия предсказуемости. Конкретная конфигурация компилятора может иметь вполне определённое поведение, например компиляторы языков C и C++ обычно реализуют операции по модулю 2ⁿ и для знаковых типов (только интерпретированных в дополнительном коде), если отключены агрессивные оптимизации. Однако, надеяться на такое поведение нельзя, иначе есть риск эффекта «бомбы замедленного действия»
4. Образование диалектов. Некоторые компиляторы предоставляют дополнительные опции для того, чтобы доопределить неопределённое поведение. Например, и GCC, и Clang поддерживают опцию -fwrapv, обеспечивающую выше описанное (в пункте 3) поведение.

Изменение стандарта может привести к новым проблемам с переполнением. К примеру, 1<<31 было зависимым от реализации в стандартах ANSI C и C++98, в то время как стали неопределённым в C99 and C11 (для 32-битных целых).^[4]

Также, последствиями такой ошибки могут быть и другие, например переполнение буфера.

Эксплуатация и последствия

Основные последствия для безопасности^[7]:

• Для доступности. Возможный отказ системы (окно для DoS-атак)
• Для целостности. Неавторизированный доступ к данным
• Для конфиденциальности. Исполнение стороннего кода, обход защитного механизма

Классически переполнение может быть эксплуатировано через переполнение буфера.

img_t table_ptr; /*struct containing img data, 10kB each*/
int num_imgs;
...
num_imgs = get_num_imgs();
table_ptr = (img_t*)malloc(sizeof(img_t)*num_imgs);
...

Данный пример^[7] иллюстрирует сразу несколько уязвимостей. Во-первых, слишком большой num_imgs приведёт к выделению огромного буфера, из-за чего программа может потребить все ресурсы системы или вызвать её крах.

Другая уязвимость в том, что если num_imgs ещё больше, это приведёт к переполнению аргумента malloc. Тогда выделится лишь небольшой буфер. При записи в него произойдёт переполнение буфера, последствиями чего могут стать: перехват контроля над исполнением, исполнение кода злоумышленника, доступ к важной информации.^[8]

Предотвращение проблемы

Защита от подобного поведения должна проводиться на нескольких уровнях^[7]:

1. Планирования и требований к программе:
   • Убедитесь, что все протоколы взаимодействия между компонентами строго определены. В том числе, что все вычисления вне границ представления будут обнаружены. И требуйте строгого соответствия этим протоколам
   • Используйте язык программирования и компилятор, которые не позволяет этой уязвимости воплотиться, либо позволяют легче её обнаружить, либо выполняют авто-проверку границ. Инструменты, которые предоставляются компилятором, включают санитайзеры (например, Address Sanitizer или Undefined Behavior Sanitizer) .
2. Архитектуры программы:
   • Используйте проверенные библиотеки или фреймворки, помогающие проводить вычисления без риска непредсказуемых последствий. Примеры включают такие библиотеки, как SafeInt (C++) или IntegerLib (C or C++).
   • Любые проверки безопасности на стороне клиента должны быть продублированы на стороне сервера, чтобы не допустить CWE-602. Злоумышленник может миновать проверку на стороне клиента, изменив сами значения непосредственно после прохождения проверки или модифицируя клиента, чтобы полностью убрать проверки.
3. Реализации:
   • Проводите валидацию любых поступивших извне числовых данных, проверяя что они находятся внутри ожидаемого диапазона. Проверяйте обязательно как минимальный порог, так и максимальный. Используйте беззнаковые числа, где это возможно. Это упростит проверки на переполнение.
   • Исследуйте все необходимые нюансы языка программирования, связанные с численными вычислениями (CWE-681). Как они представляются, какие различия между знаковыми и беззнаковыми, 32-битными и 64-битными, проблемы при кастовании (обрезка, знаково-беззнаковое приведения типов — выше) и как обрабатываются числа, слишком маленькие или, наоборот, большие для их машинного представления. Также убедитесь, что используемый вами тип (например, int или long) покрывают необходимый диапазон представления
   • Подробно изучите полученные от компилятора предупреждения и устраните возможные проблемы безопасности, такие как несоответствия знаковости операндов при операциях с памятью или использование неинициализированных переменных. Даже если уязвимость совсем небольшая, это может привести к опасности для всей системы.

Другие правила, позволяющие избежать этих уязвимостей, опубликованы в стандарте CERT C Secure Coding Standard в 2008 году, включают^[9]:

• Не пишите и не используйте функции обработки строкового ввода, если они обрабатывают не все случаи
• Не используйте битовые операции над знаковыми типами
• Вычисляйте выражения на типе большего размера перед сравнением или присваиванием в меньший
• Будьте внимательны перед приведением типа между числом и указателем
• Убедитесь, что вычисления по модулю или результаты деления не приводят к последующему делению на ноль
• Используйте intmax_t или uintmax_t для форматированного ввода-вывода пользовательских числовых типов

Примеры из жизни

Исследование SPECCINT

В статье^[4] в качестве предмета исследования программ на языках C и C++ на целочисленное переполнение подробно исследуется один из самых широко применимых и известных тестовых пакетов SPEC, используемый для измерений производительности. Состоит он из фрагментов наиболее распространённых задач, как то: тестов вычислительной математики, компиляции, работы с базами данных, диском, сетью и прочее.

Результаты анализа SPECCINT2000 показывают наличие 219 статических источников переполнения в 8 из 12 бенчмарков, из которых 148 использовали беззнаковое переполнение и 71 — знаковое (снова неопределённое поведение). В то же время, беззнаковое переполнение тоже не всегда намеренное и может являться ошибкой и источником уязвимости (например, Listing 2 той же статьи^[4]).

Также был проведён тест на «бомбы замедленного действия» в SPECCINT2006. Его идеей является в каждом месте неопределённого поведения вернуть случайное число и посмотреть, к каким последствиям это может привести. Если оценивать неопределённое поведение с точки зрения стандарта C99/C++11, то тест не пройдут целых 6 бенчмарков из 9.

Примеры из других программных пакетов

1 int  addsi (int lhs , int  rhs) {
2     errno = 0;
3     if (((( lhs+rhs)^lhs)&(( lhs+rhs)^rhs))
4     >> (sizeof(int)*CHAR_BIT -1)) {
5         error_handler("OVERFLOW  ERROR", NULL , EOVERFLOW);
6         errno = EINVAL;
7     }
8     return  lhs+rhs;
9 }

Данный фрагмент кода^[4] из пакета IntegerLib проверяет, могут ли быть lhs и rhs сложены без переполнения. И ровно в строчке 3 это переполнение может возникнуть (при сложении lhs+rhs). Это UB, так как lhs и rhs — знакового типа. Кроме этого, в данной библиотеке найдено ещё 19 UB-переполнений.

Также авторы сообщили разработчикам о 13 переполнениях в SQLite, 43 в SafeInt, 6 в GNU MPC library, 30 в PHP, 18 в Firefox, 71 в GCC, 29 в PostgreSQL, 5 в LLVM и 28 в Python. Большинство из ошибок были вскоре исправлены.

Другие примеры

Известный пример целочисленного переполнения происходит в игре Pac-Man, так же, как и в других играх серии: Ms. Pac-Man, Jr. Pac-Man. Также этот глюк появляется в Pac-Man Google Doodle в качестве так называемого «пасхального яйца».^[10] Здесь же на уровне 256 можно наблюдать «экран смерти», а сам уровень называют «уровнем разделенного экрана». Энтузиасты дизассемблировали исходный код, пытаясь исправить ошибку модифицированием игры.

Такая же проблема появляется в игре Civilization 4 и известна как Nuclear Gandhi^[11]. Дело в том, что после заключения партнёрских соглашений с очень миролюбивым Ганди, происходит переполнение через 0 уровня враждебности, результатом чего может стать ядерная война с Ганди.

Ещё одним примером является глюк в SimCity 2000^[12]. Здесь дело в том, что бюджет игрока стал очень большим, а после перехода через 2³¹ внезапно стал отрицательным. Игра оканчивается поражением.

Этот глюк из Diablo III. Из-за одного из изменений патча 1.0.8, игровая экономика сломалась. Максимальную сумму для сделок повысили с 1 млн до 10 млн. Стоимость покупки переполнялась через 32-битный тип, а при отмене операции возвращалась полная сумма. То есть игрок оставался с прибылью в 2³² игровой валюты^[13]

См. также

• Переполнение буфера
• Переполнение стека

Примечания