Ошибка выполнения целочисленное переполнение - Ремонт и установка крупной бытовой техники

What is an integer overflow error?
Why do i care about such an error?
What are some methods of avoiding or preventing it?

Earlz

61.8k98 gold badges301 silver badges498 bronze badges

asked Apr 14, 2010 at 21:46

Integer overflow occurs when you try to express a number that is larger than the largest number the integer type can handle.

If you try to express the number 300 in one byte, you have an integer overflow (maximum is 255). 100,000 in two bytes is also an integer overflow (65,535 is the maximum).

You need to care about it because mathematical operations won’t behave as you expect. A + B doesn’t actually equal the sum of A and B if you have an integer overflow.

You avoid it by not creating the condition in the first place (usually either by choosing your integer type to be large enough that you won’t overflow, or by limiting user input so that an overflow doesn’t occur).

answered Apr 14, 2010 at 21:51

JohnJohn

16k10 gold badges70 silver badges110 bronze badges

The easiest way to explain it is with a trivial example. Imagine we have a 4 bit unsigned integer. 0 would be 0000 and 1111 would be 15. So if you increment 15 instead of getting 16 you’ll circle back around to 0000 as 16 is actually 10000 and we can not represent that with less than 5 bits. Ergo overflow…

In practice the numbers are much bigger and it circles to a large negative number on overflow if the int is signed but the above is basically what happens.

Another way of looking at it is to consider it as largely the same thing that happens when the odometer in your car rolls over to zero again after hitting 999999 km/mi.

answered Apr 14, 2010 at 21:51

KrisKris

14.4k7 gold badges55 silver badges65 bronze badges

When you store an integer in memory, the computer stores it as a series of bytes. These can be represented as a series of ones and zeros.

For example, zero will be represented as 00000000 (8 bit integers), and often, 127 will be represented as 01111111. If you add one to 127, this would «flip» the bits, and swap it to 10000000, but in a standard two’s compliment representation, this is actually used to represent -128. This «overflows» the value.

With unsigned numbers, the same thing happens: 255 (11111111) plus 1 would become 100000000, but since there are only 8 «bits», this ends up as 00000000, which is 0.

You can avoid this by doing proper range checking for your correct integer size, or using a language that does proper exception handling for you.

answered Apr 14, 2010 at 21:52

Reed CopseyReed Copsey

552k78 gold badges1155 silver badges1373 bronze badges

An integer overflow error occurs when an operation makes an integer value greater than its maximum.

For example, if the maximum value you can have is 100000, and your current value is 99999, then adding 2 will make it ‘overflow’.

You should care about integer overflows because data can be changed or lost inadvertantly, and can avoid them with either a larger integer type (see long int in most languages) or with a scheme that converts long strings of digits to very large integers.

answered Apr 14, 2010 at 21:50

RiddariRiddari

1,7053 gold badges26 silver badges57 bronze badges

Overflow is when the result of an arithmetic operation doesn’t fit in the data type of the operation. You can have overflow with a byte-sized unsigned integer if you add 255 + 1, because the result (256) does not fit in the 8 bits of a byte.

You can have overflow with a floating point number if the result of a floating point operation is too large to represent in the floating point data type’s exponent or mantissa.

You can also have underflow with floating point types when the result of a floating point operation is too small to represent in the given floating point data type. For example, if the floating point data type can handle exponents in the range of -100 to +100, and you square a value with an exponent of -80, the result will have an exponent around -160, which won’t fit in the given floating point data type.

You need to be concerned about overflows and underflows in your code because it can be a silent killer: your code produces incorrect results but might not signal an error.

Whether you can safely ignore overflows depends a great deal on the nature of your program — rendering screen pixels from 3D data has a much greater tolerance for numerical errors than say, financial calculations.

Overflow checking is often turned off in default compiler settings. Why? Because the additional code to check for overflow after every operation takes time and space, which can degrade the runtime performance of your code.

Do yourself a favor and at least develop and test your code with overflow checking turned on.

answered Apr 14, 2010 at 23:52

dthorpedthorpe

35.3k5 gold badges75 silver badges119 bronze badges

I find showing the Two’s Complement representation on a disc very helpful.

Here is a representation for 4-bit integers. The maximum value is 2^3-1 = 7.

For 32 bit integers, we will see the maximum value is 2^31-1.

When we add 1 to 2^31-1 : Clockwise we move by one and it is clearly -2^31 which is called integer overflow

enter image description here

Ref : https://courses.cs.washington.edu/courses/cse351/17wi/sections/03/CSE351-S03-2cfp_17wi.pdf

answered Dec 29, 2020 at 17:41

mcvkrmcvkr

3,1396 gold badges38 silver badges63 bronze badges

From wikipedia:

In computer programming, an integer
overflow occurs when an arithmetic
operation attempts to create a numeric
value that is larger than can be
represented within the available
storage space. For instance, adding 1 to the largest value that can be represented
constitutes an integer overflow. The
most common result in these cases is
for the least significant
representable bits of the result to be
stored (the result is said to wrap).

You should care about it especially when choosing the appropriate data types for your program or you might get very subtle bugs.

answered Apr 14, 2010 at 21:49

Darin DimitrovDarin Dimitrov

1.0m270 gold badges3284 silver badges2923 bronze badges

From http://www.first.org/conference/2006/papers/seacord-robert-slides.pdf :

An integer overflow occurs when an integer is
increased beyond its maximum value or
decreased beyond its minimum value.
Overflows can be signed or unsigned.

P.S.: The PDF has detailed explanation on overflows and other integer error conditions, and also how to tackle/avoid them.

answered Apr 14, 2010 at 21:50

N 1.1N 1.1

12.4k6 gold badges43 silver badges61 bronze badges

I’d like to be a bit contrarian to all the other answers so far, which somehow accept crappy broken math as a given. The question is tagged language-agnostic and in a vast number of languages, integers simply never overflow, so here’s my kind-of sarcastic answer:

What is an integer overflow error?

An obsolete artifact from the dark ages of computing.

why do i care about it?

You don’t.

how can it be avoided?

Use a modern programming language in which integers don’t overflow. (Lisp, Scheme, Smalltalk, Self, Ruby, Newspeak, Ioke, Haskell, take your pick …)

answered Apr 14, 2010 at 23:17

Jörg W MittagJörg W Mittag

362k75 gold badges441 silver badges648 bronze badges

This happens when you attempt to use an integer for a value that is higher than the internal structure of the integer can support due to the number of bytes used. For example, if the maximum integer size is 2,147,483,647 and you attempt to store 3,000,000,000 you will get an integer overflow error.

answered Apr 14, 2010 at 21:50

Источник

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

Целочисленное переполнение может быть продемонстрировано с помощью одометр переполнение, механическая версия явления. Все цифры устанавливаются на максимум 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 не классифицирует это преобразование как переполнение..

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

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

Язык	Целое число без знака	Целое число со знаком
Ada	по модулю модуль типа	поднять Constraint_Error
C /C ++	по модулю степени двойки	неопределенное поведение
C#	по модулю степени 2 в непроверенном контексте; `System.OverflowException`возникает в проверенном контексте
Java	N / A	степень двойки по модулю
JavaScript	все числа имеют двойную точность с плавающей запятой, за исключением нового BigInt
MATLAB	Встроенные целые числа насыщаются. Целые числа с фиксированной запятой, настраиваемые для переноса или насыщения
Python 2	N/A	, преобразовываются в longтип (bigint)
Seed7	N / A	поднять OVERFLOW_ERROR
Схема	Н / Д	преобразовать в bigNum
Simulink	, конфигурируемый для переноса или насыщения
Smalltalk	Н / Д	преобразовать в LargeInteger
Swift	Вызывает ошибку, если не используются специальные операторы переполнения.

Обнаружение

Реализация обнаружения переполнения во время выполнения 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.

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.

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

Целочи́сленное переполне́ние (англ. 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]).

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

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

Битность	8 бит	16 бит	32 бит	64 бит
Беззнаковый	Диапазон	0..2⁸−1	0..2¹⁶−1	0..2³²−1	0..2⁶⁴−1
Диапазон (десятич.)	0..255	0..65535	0..4294967295	0.. 18446744073709551615
Знаковый	Диапазон	-2⁷.. 2⁷−1	-2¹⁵.. 2¹⁵−1	-2³¹.. 2³¹−1	-2⁶³.. 2⁶³−1
Диапазон (десятич.)	-128..127	-32768..32767	-2147483648.. 2147483647	-9223372036854775808.. 9223372036854775807

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

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

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

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

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

Компиляция может пойти неожиданным образом. Из-за наличия неопределённого поведения в программе, оптимизации компилятора могут изменить поведение программы.
Бомба замедленного действия. На текущей версии ОС, компилятора, опций компиляции, структурной организации программы и т. д. всё может работать, а при любом изменении, например, появлении более агрессивных оптимизаций, сломаться.
Иллюзия предсказуемости. Конкретная конфигурация компилятора может иметь вполне определённое поведение, например компиляторы языков C и C++ обычно реализуют операции по модулю 2ⁿ и для знаковых типов (только интерпретированных в дополнительном коде), если отключены агрессивные оптимизации. Однако, надеяться на такое поведение нельзя, иначе есть риск эффекта «бомбы замедленного действия»
Образование диалектов. Некоторые компиляторы предоставляют дополнительные опции для того, чтобы доопределить неопределённое поведение. Например, и 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]:

Планирования и требований к программе:
- Убедитесь, что все протоколы взаимодействия между компонентами строго определены. В том числе, что все вычисления вне границ представления будут обнаружены. И требуйте строгого соответствия этим протоколам
- Используйте язык программирования и компилятор, которые не позволяет этой уязвимости воплотиться, либо позволяют легче её обнаружить, либо выполняют авто-проверку границ. Инструменты, которые предоставляются компилятором, включают санитайзеры (например, Address Sanitizer^[en] или Undefined Behavior Sanitizer).
Архитектуры программы:
- Используйте проверенные библиотеки или фреймворки, помогающие проводить вычисления без риска непредсказуемых последствий. Примеры включают такие библиотеки, как SafeInt (C++) или IntegerLib (C или C++).
- Любые проверки безопасности на стороне клиента должны быть продублированы на стороне сервера, чтобы не допустить CWE-602. Злоумышленник может миновать проверку на стороне клиента, изменив сами значения непосредственно после прохождения проверки или модифицируя клиента, чтобы полностью убрать проверки.
Реализации:
- Проводите валидацию любых поступивших извне числовых данных, проверяя что они находятся внутри ожидаемого диапазона. Проверяйте обязательно как минимальный порог, так и максимальный. Используйте беззнаковые числа, где это возможно. Это упростит проверки на переполнение.
- Исследуйте все необходимые нюансы языка программирования, связанные с численными вычислениями (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]

См. также

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

Примечания

↑ ^1,0 ^1,1 Intel® 64 and IA-32 Architectures Software Developer Manuals | Intel® Software (англ.). software.intel.com. Дата обращения: 22 декабря 2017.
↑ x86 Exploitation 101: “Integer overflow” – adding one more… aaaaaaaaaaand it’s gone (англ.), gb_master’s /dev/null (12 August 2015). Дата обращения 20 декабря 2017.
↑ The Web Application Security Consortium / Integer Overflows. projects.webappsec.org. Дата обращения: 8 декабря 2017.
↑ ^4,0 ^4,1 ^4,2 ^4,3 ^4,4 ^4,5 W. Dietz, P. Li, J. Regehr, V. Adve. Understanding integer overflow in C/C #x002B; #x002B; // 2012 34th International Conference on Software Engineering (ICSE). — June 2012. — С. 760—770. — doi:10.1109/icse.2012.6227142.
↑ CWE — 2011 CWE/SANS Top 25 Most Dangerous Software Errors (англ.). cwe.mitre.org. Дата обращения: 21 декабря 2017.
↑ ISO/IEC 9899:2011 — Information technology — Programming languages — C (англ.). www.iso.org. Дата обращения: 21 декабря 2017.
↑ ^7,0 ^7,1 ^7,2 CWE-190: Integer Overflow or Wraparound (3.0) (англ.). cwe.mitre.org. Дата обращения: 12 декабря 2017.
↑ CWE-119: Improper Restriction of Operations within the Bounds of a Memory Buffer (3.0) (англ.). cwe.mitre.org. Дата обращения: 12 декабря 2017.
↑ CWE-738: CERT C Secure Coding (2008 Version) Section 04 — Integers (INT) (3.0) (англ.). cwe.mitre.org. Дата обращения: 15 декабря 2017.
↑ Map 256 Glitch (англ.), Pac-Man Wiki. Дата обращения 12 декабря 2017.
↑ Nuclear Gandhi, Know Your Meme. Дата обращения 15 декабря 2017.
↑ Артемий Леонов. Почему история о баге с «ядерным Ганди» в Civilization, скорее всего, выдумана. DTF (5 сентября 2019). Дата обращения: 24 октября 2020.
↑ Sim City 2000 Integer Overflow. Blake O’Hare. Дата обращения: 12 декабря 2017.
↑ Diablo III Economy Broken by an Integer Overflow Bug (англ.), minimaxir | Max Woolf’s Blog. Дата обращения 12 декабря 2017.

Переполнение целых знаковых чисел

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

Компьютер не может напрямую работать с бесконечно «длинными» числами — хранить все их цифры. Как бы много оперативной памяти у нас ни было — все же она конечна. Да и хранить, и обрабатывать величины, сопоставимые с числом атомов в видимой части вселенной — безнадежное занятие. Так что ограничения типов int64 или int128 не очень нас-то и ограничивают

Тем не менее при выполнении операций над целыми числами мы все же имеем шанс выпасть за пределы допустимого диапазона (например, [-2^31, 2^31-1] для int32), и тут в игру вступают особенности поддержки целых чисел для того или иного языка программирования, а также, быть может, особенности реализации конкретной платформы.

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

произойдет перенос разряда в знаковый бит, и переменная x примет отрицательное значение.

В реализации конкретного языка программирования может быть проверка флага переполнения и сообщение об ошибке. А может и не быть. Может быть гарантия «цикличности» значений (после 2^31-1 идет -2^31), а может и не быть.

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

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

Многие программисты свято верят, что переполнение чисел работает, как ожидается, «циклично» — и пишут проверки вида

if (x > 0 && a > 0 && x + a <= 0) {
    // обработай переполнение
}

Но, увы, это неопределенное поведение. И компилятор имеет полное право выкинуть такую проверку.

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

int hash_code(std::string s) {
    int h = 13;
    for (char c : s) {
        h += h * 27752 + c;
    }
    if (h < 0) h += std::numeric_limits<int>::max();
    return h;
}

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

Корректные проверки переполнения куда сложнее и тяжелее.

Так, для C++20, безопасный обобщенный код арифметических операций над целыми знаковыми числами мог бы выглядеть так

#include <concepts>
#include <type_traits>
#include <variant>
#include <limits>

namespace safe {

// Все эти проверки справедливы только для целых знаковых чисел
template <class T>
concept SignedInteger = std::is_signed_v<T>
                     && std::is_integral_v<T>;

enum class ArithmeticError {
    Overflow,
    ZeroDivision
};

template <SignedInteger I>
using ErrorOrInteger = std::variant<I, ArithmeticError>;

template <SignedInteger I>
ErrorOrInteger<I> add(I a,    // выключаем вывод параметра шаблона по
                      std::type_identity_t<I> b) // второму аргументу
{
    if (b > 0 && a > std::numeric_limits<I>::max - b) {
        // положительное переполнение
        return ArithmeticError::Overflow;
    }
    if (b < 0 && a < std::numeric_limits<I>::min - b) {
        // отрицательное переполнение
        return ArithmeticError::Overflow;
    }
    return a + b;
}

template <SignedInteger I>
ErrorOrInteger<I> sub(I a, std::type_identity_t<I> b) {
    if (b < 0 && a > std::numeric_limits<I>::max + b) {
        // положительное переполнение
        return ArithmeticError::Overflow;
    }
    if (b > 0 && a < std::numeric_limits<I>::min + b) {
        // отрицательное переполнение
        return ArithmeticError::Overflow;
    }
    return a - b;
}

template <SignedInteger I>
ErrorOrInteger<I> mul(I a, std::type_identity_t<I> b) {
   if (a == 0 || b == 0) {
       return 0;
   }

   if (a > 0) {
       if (b > 0) {
           if (a > std::numeric_limits<I>::max / b) {
              return ArithmeticError::Overflow;
           }
       } else {
           if (b < std::numeric_limits<I>::min / a) {
              return ArithmeticError::Overflow;
            }
      }
   } else {
      if (b > 0) {
          if (a < std::numeric_limits<I>::min / b) {
              return ArithmeticError::Overflow;
          }
      } else {
          if (b < std::numeric_limits<I>::max / a) {
              return ArithmeticError::Overflow;
          }
      }
   }
   return a * b;
}

template <SignedInteger I>
ErrorOrInteger<I> div(I a, std::type_identity_t<I> b) {
  if (b == 0) {
      return ArithmeticError::ZeroDivision;
  }

  if (a == std::numeric_limits<I>::min && b == -1) {
      // диапазон [min, max] несимметричный относительно 0.
      // abs(min) > max — будет переполнение
      return ArithmeticError::Overflow;
  }
  return a / b;
}


template <SignedInteger I>
ErrorOrInteger<I> mod(I a, std::type_identity_t<I> b) {
  if (b == 0) {
      return ArithmeticError::ZeroDivision;
  }

  if (b == -1) {
      // По стандарту в этом случае также неопределенное поведение при
      // a == std::numeric_limits<I>::min
      // поскольку остаток и неполное частное от деления,
      // например, на платформе x86
      // получаются одной и той же инструкцией div (idiv),
      // что потребует дополнительной обработки.
      //
      // Но совершенно ясно, что остаток от деления чего угодно на -1 равен 0
      return 0;
  }
  return a % b;
}

}

Если вам не нравится возвращать ошибку или результат, можете использовать исключения.

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

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

Итак, если вы работаете только лишь с беззнаковыми числами (unsigned), то с неопределенным поведением при переполнении никаких проблем нет — все определено как вычисления по модулю 2^N (N — количество бит для выбранного типа чисел).

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

Для выведения ограничений вам помогут отладочные assert с правильными проверками переполнения, которые нужно написать. Или включение ubsan (undefined behavior sanitizer) при сборке компиляторами clang или gcc.
А также тестовые constexpr вычисления.

Также проблемы неопределенного поведения при переполнении касаются битовых сдвигов влево для отрицательных чисел (или при сдвиге положительного числа с залезанием в знаковый бит). Начиная с C++20, стандарт требует фиксированной единой реализации отрицательных чисел — через дополнительный код (two’s complement), и многие проблемы сдвигов сняты. Тем не менее все равно стоит следовать общей рекомендации: любые битовые операции выполнять только в unsigned типах.

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

    constexpr int x = 12345678;
    constexpr uint8_t first_byte = x; // Implicit cast. Warning

Очень неприятным является переполнение целых, возникающее из-за правил integer promotion:

constexpr std::uint16_t IntegerPromotionUB(std::uint16_t x) {
    x *= x;
    return x;
}

// 65535 * 65535 mod 1<<16 = 1

static_assert(IntegerPromotionUB(65535) == 1); // won't compile

Несмотря на то, что для беззнаковых переполнение определено как взятие остатка по модулю 2^n и мы используем только беззнаковую переменную,
из-за integer promotion в этом примере возникает переполнение знакового! числа и вытекающее из этого UB. Справедливости ради, надо заметить, что такое происходит только на платформах, где размер int больше uint16_t (то есть практически везде в наши дни).

x *= x; // переписывается как x = x * x;
// тип uint16 меньше чем тип int — для * выполняется неявное приведение к int.

Полезные ссылки

https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow
https://stackoverflow.com/a/46073296
https://habr.com/ru/post/307702/

Действие по умолчанию зависит от процессора, компилятора и настроек. На 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.

Переполнение целых чисел

Вы уже знаете, что при сложении целых может происходить переполнение. Загвоздка в том, что компьютер не выдаёт предупреждения при переполнении:
программа продолжит работать с неверными данными. Более того, поведение при переполнении определено только для целых без знака.

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

Рассмотрим несколько приёмов отслеживания переполнения целых со знаком и переполнения целых без знака.

1. Предварительная проверка данных. Мы знаем, из файла limits.h, максимальное и минимальное значение для чисел типа int. Если оба числа положительные,
то их сумма не превысит INT_MAX, если разность INT_MAX и одного из чисел меньше второго числа. Если оба числа отрицательные, то разность INT_MIN и
одного из чисел должна быть больше другого. Если же оба числа имеют разные знаки, то однозначно их сумма не превысит INT_MAX или INT_MIN.

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;
}

В этой функции переменной overflow будет присвоено значение 1, если было переполнение. Функция возвращает сумму, независимо от результата сложения.

2. Второй способ проверки – взять для суммы тип, максимальное (и минимальное) значение которого заведомо больше суммы двух целых. После сложения необходимо проверить, чтобы сумма была не больше , чем INT_MAX и не меньше INT_MIN.

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;
}

Обратите внимание на явное приведение типов. Без него сначала произойдёт переполнение, и неправильное число будет записано в переменную c.

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

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;
}

Здесь переменная noOverflow равна 1, если нет переполнения. jno (jump if no overflow) выполняет переход к метке NO_OVERFLOW, если переполнения не было.
Если же переполнение было, то выполняется

mov noOverflow, 0

По адресу переменной noOverflow записывается нуль.

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

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();
}

Q&A

Всё ещё не понятно? – пиши вопросы на ящик

Функции с переменным числом параметров

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

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

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

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

Для некоторых приложений, таких как таймеры и часы, может быть желательно перенос при переполнении. В 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 не классифицирует это преобразование как переполнение.

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

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

Язык	Беззнаковое целое	Знаковое целое число
Ада	по модулю модуля типа	поднимать Constraint_Error
C /C ++	степень двойки по модулю	неопределенное поведение
C #	по модулю степени 2 в непроверенном контексте; `System.OverflowException` поднимается в проверяемом контексте^[10]
Ява	Нет данных	степень двойки по модулю
JavaScript	все числа с плавающей запятой двойной точности кроме нового BigInt
MATLAB	Встроенные целые числа насыщают. Целые числа с фиксированной запятой, настраиваемые для переноса или насыщения
Python 2	Нет данных	преобразовать в длинный тип (bigint)
Семя7	Нет данных	поднимать OVERFLOW_ERROR^[11]
Схема	Нет данных	преобразовать в bigNum
Simulink	настраивается на обертывание или насыщение
Болтовня	Нет данных	преобразовать в LargeInteger
Быстрый	Вызывает ошибку, если не используются специальные операторы переполнения.^[12]

Обнаружение

Реализация обнаружения переполнения во время выполнения 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]

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

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

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

${displaystyle 210_{10}+61_{10}=11010010_{2}+00111101_{2}=?}$

${displaystyle {begin{array}{c}{begin{array}{cc}+&{begin{array}{c}11010010_{2}0111101_{2}end{array}}end{array}}hline {begin{array}{cc}&{color {Red}1}00001111_{2}end{array}}end{array}}}$

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

При этом в результат записывается не ожидаемое ${displaystyle 271_{10}={color {Red}1}00001111_{2}}$ , а ${displaystyle 15_{10}=00001111_{2}}$ . Стоит отметить, что вычисление здесь произошло по модулю 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]).

Содержание

1 Происхождение проблемы
2 Риски для безопасности
3 Эксплуатация и последствия
4 Предотвращение проблемы
5 Примеры из жизни
- 5.1 Исследование SPECCINT
- 5.2 Примеры из других программных пакетов
- 5.3 Другие примеры
6 См. также
7 Примечания

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

Битность	8 бит	16 бит	32 бит	64 бит
Беззнаковый	Диапазон	0..2⁸−1	0..2¹⁶−1	0..2³²−1	0..2⁶⁴−1
Диапазон (десятич.)	0..255	0..65535	0..4294967295	0.. 18446744073709551615
Знаковый	Диапазон	-2⁷.. 2⁷−1	-2¹⁵.. 2¹⁵−1	-2³¹.. 2³¹−1	-2⁶³.. 2⁶³−1
Диапазон (десятич.)	-128..127	-32768..32767	-2147483648.. 2147483647	-9223372036854775808.. 9223372036854775807

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

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

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

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

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

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

Основные последствия для безопасности^[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]:

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

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

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

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

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

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 }

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

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

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

См. также

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

Примечания

↑ ¹ ² Intel® 64 and IA-32 Architectures Software Developer Manuals | Intel® Software (англ.). software.intel.com. Проверено 22 декабря 2017.
↑ x86 Exploitation 101: “Integer overflow” – adding one more… aaaaaaaaaaand it’s gone (англ.), gb_master’s /dev/null (12 августа 2015). Проверено 20 декабря 2017.
↑ The Web Application Security Consortium / Integer Overflows. projects.webappsec.org. Проверено 8 декабря 2017.
↑ ¹ ² ³ ⁴ ⁵ ⁶ W. Dietz, P. Li, J. Regehr, V. Adve. Understanding integer overflow in C/C #x002B; #x002B; // 2012 34th International Conference on Software Engineering (ICSE). — June 2012. — С. 760–770. — DOI:10.1109/icse.2012.6227142.
↑ CWE — 2011 CWE/SANS Top 25 Most Dangerous Software Errors (англ.). cwe.mitre.org. Проверено 21 декабря 2017.
↑ ISO/IEC 9899:2011 — Information technology — Programming languages — C (англ.). www.iso.org. Проверено 21 декабря 2017.
↑ ¹ ² ³ CWE-190: Integer Overflow or Wraparound (3.0) (англ.). cwe.mitre.org. Проверено 12 декабря 2017.
↑ CWE-119: Improper Restriction of Operations within the Bounds of a Memory Buffer (3.0) (англ.). cwe.mitre.org. Проверено 12 декабря 2017.
↑ CWE-738: CERT C Secure Coding (2008 Version) Section 04 — Integers (INT) (3.0) (англ.). cwe.mitre.org. Проверено 15 декабря 2017.
↑ Map 256 Glitch (англ.), Pac-Man Wiki. Проверено 12 декабря 2017.
↑ Nuclear Gandhi, Know Your Meme. Проверено 15 декабря 2017.
↑ Sim City 2000 Integer Overflow. Blake O’Hare. Проверено 12 декабря 2017.
↑ Diablo III Economy Broken by an Integer Overflow Bug (англ.), minimaxir | Max Woolf’s Blog. Проверено 12 декабря 2017.

Источник

Integer overflow can be demonstrated through an odometer overflowing, a mechanical version of the phenomenon. All digits are set to the maximum 9 and the next increment of the white digit causes a cascade of carry-over additions setting all digits to 0, but there is no higher digit (1,000,000s digit) to change to a 1, so the counter resets to zero. This is wrapping in contrast to saturating.

In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is outside of the range that can be represented with a given number of digits – either higher than the maximum or lower than the minimum representable value.

The most common result of an overflow is that the least significant representable digits of the result are stored; the result is said to wrap around the maximum (i.e. modulo a power of the radix, usually two in modern computers, but sometimes ten or another radix).

An overflow condition may give results leading to unintended behavior. In particular, if the possibility has not been anticipated, overflow can compromise a program’s reliability and security.

For some applications, such as timers and clocks, wrapping on overflow can be desirable. The C11 standard states that for unsigned integers, modulo wrapping is the defined behavior and the term overflow never applies: «a computation involving unsigned operands can never overflow.»^[1]

On some processors like graphics processing units (GPUs) and digital signal processors (DSPs) which support saturation arithmetic, overflowed results would be «clamped», i.e. set to the minimum or the maximum value in the representable range, rather than wrapped around.

Origin[edit]

The register width of a processor determines the range of values that can be represented in its registers. Though the vast majority of computers can perform multiple-precision arithmetic on operands in memory, allowing numbers to be arbitrarily long and overflow to be avoided, the register width limits the sizes of numbers that can be operated on (e.g., added or subtracted) using a single instruction per operation. Typical binary register widths for unsigned integers include:

4-bit: maximum representable value 2⁴ − 1 = 15
8-bit: maximum representable value 2⁸ − 1 = 255
16-bit: maximum representable value 2¹⁶ − 1 = 65,535
32-bit: maximum representable value 2³² − 1 = 4,294,967,295 (the most common width for personal computers as of 2005),
64-bit: maximum representable value 2⁶⁴ − 1 = 18,446,744,073,709,551,615 (the most common width for personal computer central processing units (CPUs), as of 2021),
128-bit: maximum representable value 2¹²⁸ − 1 = 340,282,366,920,938,463,463,374,607,431,768,211,455

When an unsigned arithmetic operation produces a result larger than the maximum above for an N-bit integer, an overflow reduces the result to modulo N-th power of 2, retaining only the least significant bits of the result and effectively causing a wrap around.

In particular, multiplying or adding two integers may result in a value that is unexpectedly small, and subtracting from a small integer may cause a wrap to a large positive value (for example, 8-bit integer addition 255 + 2 results in 1, which is 257 mod 2⁸, and similarly subtraction 0 − 1 results in 255, a two’s complement representation of −1).

Such wraparound may cause security detriments—if an overflowed value is used as the number of bytes to allocate for a buffer, the buffer will be allocated unexpectedly small, potentially leading to a buffer overflow which, depending on the use of the buffer, might in turn cause arbitrary code execution.

If the variable has a signed integer type, a program may make the assumption that a variable always contains a positive value. An integer overflow can cause the value to wrap and become negative, which violates the program’s assumption and may lead to unexpected behavior (for example, 8-bit integer addition of 127 + 1 results in −128, a two’s complement of 128). (A solution for this particular problem is to use unsigned integer types for values that a program expects and assumes will never be negative.)

Flags[edit]

Most computers have two dedicated processor flags to check for overflow conditions.

The carry flag is set when the result of an addition or subtraction, considering the operands and result as unsigned numbers, does not fit in the given number of bits. This indicates an overflow with a carry or borrow from the most significant bit. An immediately following add with carry or subtract with borrow operation would use the contents of this flag to modify a register or a memory location that contains the higher part of a multi-word value.

The overflow flag is set when the result of an operation on signed numbers does not have the sign that one would predict from the signs of the operands, e.g., a negative result when adding two positive numbers. This indicates that an overflow has occurred and the signed result represented in two’s complement form would not fit in the given number of bits.

Definition variations and ambiguity[edit]

For an unsigned type, when the ideal result of an operation is outside the type’s representable range and the returned result is obtained by wrapping, then this event is commonly defined as an overflow. In contrast, the C11 standard defines that this event is not an overflow and states «a computation involving unsigned operands can never overflow.»^[1]

When the ideal result of an integer operation is outside the type’s representable range and the returned result is obtained by clamping, then this event is commonly defined as a saturation. Use varies as to whether a saturation is or is not an overflow. To eliminate ambiguity, the terms wrapping overflow^[2] and saturating overflow^[3] can be used.

The term underflow is most commonly used for floating-point math and not for integer math.^[4] However, many references can be found to integer underflow.^[5]^[6]^[7]^[8]^[9] When the term integer underflow is used, it means the ideal result was closer to minus infinity than the output type’s representable value closest to minus infinity. When the term integer underflow is used, the definition of overflow may include all types of overflows, or it may only include cases where the ideal result was closer to positive infinity than the output type’s representable value closest to positive infinity.

When the ideal result of an operation is not an exact integer, the meaning of overflow can be ambiguous in edge cases. Consider the case where the ideal result has a value of 127.25 and the output type’s maximum representable value is 127. If overflow is defined as the ideal value being outside the representable range of the output type, then this case would be classified as an overflow. For operations that have well defined rounding behavior, overflow classification may need to be postponed until after rounding is applied. The C11 standard^[1] defines that conversions from floating point to integer must round toward zero. If C is used to convert the floating point value 127.25 to integer, then rounding should be applied first to give an ideal integer output of 127. Since the rounded integer is in the outputs range, the C standard would not classify this conversion as an overflow.

Inconsistent behavior[edit]

The behavior on occurrence of overflow may not be consistent in all circumstances. For example, in the language Rust, while functionality is provided to give users choice and control, the behavior for basic use of mathematic operators is naturally fixed; however, this fixed behavior differs between a program built in ‘debug’ mode and one built in ‘release’ mode.^[10] In C, unsigned integer overflow is defined to wrap around, while signed integer overflow causes undefined behavior.

Methods to address integer overflow problems[edit]

Integer overflow handling in various programming languages

Language	Unsigned integer	Signed integer
Ada	modulo the type’s modulus	`raise Constraint_Error`
C, C++	modulo power of two	undefined behavior
C#	modulo power of 2 in unchecked context; `System.OverflowException` is raised in checked context^[11]
Java	modulo power of two (char is the only unsigned primitive type in Java)	modulo power of two
JavaScript	all numbers are double-precision floating-point except the new BigInt
MATLAB	Builtin integers saturate. Fixed-point integers configurable to wrap or saturate
Python 2	—	convert to `long` type (bigint)
Seed7	—	`raise OVERFLOW_ERROR`^[12]
Scheme	—	convert to bigNum
Simulink	configurable to wrap or saturate
Smalltalk	—	convert to LargeInteger
Swift	Causes error unless using special overflow operators.^[13]

Detection[edit]

Run-time overflow detection implementation UBSan (undefined behavior sanitizer) is available for C compilers.

In Java 8, there are overloaded methods, for example Math.addExact(int, int), which will throw an ArithmeticException in case of overflow.

Computer emergency response team (CERT) developed the As-if Infinitely Ranged (AIR) integer model, a largely automated mechanism to eliminate integer overflow and truncation in C/C++ using run-time error handling.^[14]

Avoidance[edit]

By allocating variables with data types that are large enough to contain all values that may possibly be computed and stored in them, it is always possible to avoid overflow. Even when the available space or the fixed data types provided by a programming language or environment are too limited to allow for variables to be defensively allocated with generous sizes, by carefully ordering operations and checking operands in advance, it is often possible to ensure a priori that the result will never be larger than can be stored. Static analysis tools, formal verification and design by contract techniques can be used to more confidently and robustly ensure that an overflow cannot accidentally result.

Handling[edit]

If it is anticipated that overflow may occur, then tests can be inserted into the program to detect when it happens, or is about to happen, and do other processing to mitigate it. For example, if an important result computed from user input overflows, the program can stop, reject the input, and perhaps prompt the user for different input, rather than the program proceeding with the invalid overflowed input and probably malfunctioning as a consequence.

CPUs generally have a way to detect this to support addition of numbers larger than their register size, typically using a status bit. The technique is called multiple-precision arithmetic. Thus, it is possible to add two numbers each two bytes wide using just a byte addition in steps: first add the low bytes then add the high bytes, but if it is necessary to carry out of the low bytes this is arithmetic overflow of the byte addition and it becomes necessary to detect and increment the sum of the high bytes.

Handling possible overflow of a calculation may sometimes present a choice between performing a check before a calculation (to determine whether or not overflow is going to occur), or after it (to consider whether or not it likely occurred based on the resulting value). Caution should be shown towards the latter choice. Firstly, since it may not be a reliable detection method (for example, an addition may not necessarily wrap to a lower value). Secondly, because the occurrence of overflow itself may in some cases be undefined behavior. In the C language, overflow of unsigned integers results in wrapping, but overflow of signed integers is undefined behavior. Consequently, a C compiler is free to assume that the programmer has ensured that signed overflow cannot possibly occur and thus it may silently optimise out any check subsequent to the calculation that involves checking the result to detect it without giving the programmer any warning that this has been done. It is thus advisable to always implement checks before calculations, not after them.

Explicit propagation[edit]

If a value is too large to be stored it can be assigned a special value indicating that overflow has occurred and then have all successive operations return this flag value. Such values are sometimes referred to as NaN, for «not a number». This is useful so that the problem can be checked once at the end of a long calculation rather than after each step. This is often supported in floating-point hardware called FPUs.

Programming language support[edit]

Programming languages implement various mitigation methods against an accidental overflow: Ada, Seed7, and certain variants of functional languages trigger an exception condition on overflow, while Python (since 2.4) seamlessly converts internal representation of the number to match its growth, eventually representing it as long – whose ability is only limited by the available memory.^[15]

In languages with native support for arbitrary-precision arithmetic and type safety (such as Python, Smalltalk, or Common Lisp), numbers are promoted to a larger size automatically when overflows occur, or exceptions thrown (conditions signaled) when a range constraint exists. Using such languages may thus be helpful to mitigate this issue. However, in some such languages, situations are still possible where an integer overflow can occur. An example is explicit optimization of a code path which is considered a bottleneck by the profiler. In the case of Common Lisp, this is possible by using an explicit declaration to type-annotate a variable to a machine-size word (fixnum)^[16] and lower the type safety level to zero^[17] for a particular code block.^[18]^[19]^[20]^[21]

In stark contrast to older languages such as C, some newer languages such as Rust provide built-in functions that allow easy detection and user choice over how overflow should be handled case-by-case. In Rust, while use of basic mathematic operators naturally lacks such flexibility, users can alternatively perform calculations via a set of methods provided by each of the integer primitive types. These methods give users several choices between performing a checked (or overflowing) operation (which indicates whether or not overflow occurred via the return type); an ‘unchecked’ operation; an operation that performs wrapping, or an operation which performs saturation at the numeric bounds.

Saturated arithmetic[edit]

In computer graphics or signal processing, it is typical to work on data that ranges from 0 to 1 or from −1 to 1. For example, take a grayscale image where 0 represents black, 1 represents white, and the values in between represent shades of gray. One operation that one may want to support is brightening the image by multiplying every pixel by a constant. Saturated arithmetic allows one to just blindly multiply every pixel by that constant without worrying about overflow by just sticking to a reasonable outcome that all these pixels larger than 1 (i.e., «brighter than white») just become white and all values «darker than black» just become black.

Examples[edit]

Unanticipated arithmetic overflow is a fairly common cause of program errors. Such overflow bugs may be hard to discover and diagnose because they may manifest themselves only for very large input data sets, which are less likely to be used in validation tests.

Taking the arithmetic mean of two numbers by adding them and dividing by two, as done in many search algorithms, causes error if the sum (although not the resulting mean) is too large to be represented and hence overflows.^[22]

An unhandled arithmetic overflow in the engine steering software was the primary cause of the crash of the 1996 maiden flight of the Ariane 5 rocket.^[23] The software had been considered bug-free since it had been used in many previous flights, but those used smaller rockets which generated lower acceleration than Ariane 5. Frustratingly, the part of the software in which the overflow error occurred was not even required to be running for the Ariane 5 at the time that it caused the rocket to fail: it was a launch-regime process for a smaller predecessor of the Ariane 5 that had remained in the software when it was adapted for the new rocket. Further, the true cause of the failure was a flaw in the engineering specification of how the software dealt with the overflow when it was detected: it did a diagnostic dump to its bus, which would have been connected to test equipment during software testing during development but was connected to the rocket steering motors during flight; the data dump drove the engine nozzle hard to one side which put the rocket out of aerodynamic control and precipitated its rapid breakup in the air.^[24]

On 30 April 2015, the U.S. Federal Aviation Administration announced it will order Boeing 787 operators to reset its electrical system periodically, to avoid an integer overflow which could lead to loss of electrical power and ram air turbine deployment, and Boeing deployed a software update in the fourth quarter.^[25] The European Aviation Safety Agency followed on 4 May 2015.^[26] The error happens after 2³¹ hundredths of a second (about 249 days), indicating a 32-bit signed integer.

Overflow bugs are evident in some computer games. In Super Mario Bros. for the NES, the stored number of lives is a signed byte (ranging from −128 to 127) meaning the player can safely have 127 lives, but when the player reaches their 128th life, the counter rolls over to zero lives (although the number counter is glitched before this happens) and stops keeping count. As such, if the player then dies it’s an immediate game over. This is caused by the game’s data overflow that was an error of programming as the developers may not have thought said number of lives could be earned.

In the arcade game Donkey Kong, it is impossible to advance past level 22 due to an integer overflow in its time/bonus. The game calculates the time/bonus by taking the level number a user is on, multiplying it by 10, and adding 40. When they reach level 22, the time/bonus number is 260, which is too large for its 8-bit 256 value register, so it overflows to a value of 4 – too short to finish the level. In Donkey Kong Jr. Math, when trying to calculate a number over 10,000, it shows only the first 4 digits. Overflow is the cause of the famous «split-screen» level in Pac-Man.^[27] Such a bug also caused the Far Lands in Minecraft Java Edition which existed from the Infdev development period to Beta 1.7.3; it was later fixed in Beta 1.8. The same bug also existed in Minecraft Bedrock Edition but has since been fixed.^[28]

In the Super Nintendo Entertainment System (SNES) game Lamborghini American Challenge, the player can cause their amount of money to drop below $0 during a race by being fined over the limit of remaining money after paying the fee for a race, which glitches the integer and grants the player $65,535,000 more than it would have had after going negative.^[29]

A similar glitch occurs in S.T.A.L.K.E.R.: Clear Sky where the player can drop into a negative amount by fast travelling without sufficient funds, then proceeding to the event where the player gets robbed and has all of their currency taken away. After the game attempts to take the player’s money away to an amount of $0, the player is granted 2147482963 in game currency.^[30]

An integer signedness bug in the stack setup code emitted by the Pascal compiler prevented IBM–Microsoft Macro Assembler (MASM) version 1.00, a DOS program from 1981, and many other programs compiled with the same compiler, to run under some configurations with more than 512 KB of memory.

IBM–Microsoft Macro Assembler (MASM) version 1.00, and likely all other programs built by the same Pascal compiler, had an integer overflow and signedness error in the stack setup code, which prevented them from running on newer DOS machines or emulators under some common configurations with more than 512 KB of memory. The program either hangs or displays an error message and exits to DOS.^[31]

In August 2016, a casino machine at Resorts World casino printed a prize ticket of $42,949,672.76 as a result of an overflow bug. The casino refused to pay this amount, calling it a malfunction, using in their defense that the machine clearly stated that the maximum payout was $10,000, so any prize exceeding that had to be the result of a programming bug. The New York State Gaming Commission ruled in favor of the casino.^[32]

References[edit]

^ ^a ^b ^c ISO staff. «ISO/IEC 9899:2011 Information technology — Programming languages — C». ANSI.org.
^ «Wrap on overflow — MATLAB & Simulink». www.mathworks.com.
^ «Saturate on overflow — MATLAB & Simulink». www.mathworks.com.
^ Arithmetic underflow
^ «CWE — CWE-191: Integer Underflow (Wrap or Wraparound) (3.1)». cwe.mitre.org.
^ «Overflow And Underflow of Data Types in Java — DZone Java». dzone.com.
^ Mir, Tabish (4 April 2017). «Integer Overflow/Underflow and Floating Point Imprecision». medium.com.
^ «Integer underflow and buffer overflow processing MP4 metadata in libstagefright». Mozilla.
^ «Avoiding Buffer Overflows and Underflows». developer.apple.com.
^ «Operator expressions — The Rust Reference». Rust-lang.org. Retrieved 2021-02-12.
^ BillWagner. «Checked and Unchecked (C# Reference)». msdn.microsoft.com.
^ Seed7 manual, section 16.3.3 OVERFLOW_ERROR.
^ The Swift Programming Language. Swift 2.1 Edition. October 21, 2015.
^ As-if Infinitely Ranged Integer Model
^ Python documentation, section 5.1 Arithmetic conversions.
^ «Declaration TYPE«. Common Lisp HyperSpec.
^ «Declaration OPTIMIZE«. Common Lisp HyperSpec.
^ Reddy, Abhishek (2008-08-22). «Features of Common Lisp».
^ Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press. ISBN 0-262-16209-1.
^ Wright, Andrew K.; Felleisen, Matthias (1994). «A Syntactic Approach to Type Soundness». Information and Computation. 115 (1): 38–94. doi:10.1006/inco.1994.1093.
^ Macrakis, Stavros (April 1982). «Safety and power». ACM SIGSOFT Software Engineering Notes. 7 (2): 25–26. doi:10.1145/1005937.1005941. S2CID 10426644.
^ «Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken». googleresearch.blogspot.co.uk.
^ Gleick, James (1 December 1996). «A Bug and A Crash». The New York Times. Retrieved 17 January 2019.
^ Official report of Ariane 5 launch failure incident.
^ Mouawad, Jad (30 April 2015). «F.A.A. Orders Fix for Possible Power Loss in Boeing 787». New York Times.
^ «US-2015-09-07: Electrical Power – Deactivation». Airworthiness Directives. European Aviation Safety Agency. 4 May 2015.
^ Pittman, Jamey. «The Pac-Man Dossier».
^ «Minecraft Gamepedia Page». Minecraft Gamepedia.
^ Archived at Ghostarchive and the Wayback Machine: «Lamborghini American Challenge SPEEDRUN (13:24)». YouTube.
^ «Money glitch :: S.T.A.L.K.E.R.: Clear Sky General Discussions».
^ Lenclud, Christophe. «Debugging IBM MACRO Assembler Version 1.00».
^ Kravets, David (June 15, 2017). «Sorry ma’am you didn’t win $43M – there was a slot machine ‘malfunction’«. Ars Technica.

External links[edit]

Phrack #60, Basic Integer Overflows
Phrack #60, Big Loop Integer Protection
Efficient and Accurate Detection of Integer-based Attacks
WASC Threat Classification – Integer Overflows
Understanding Integer Overflow in C/C++
Binary Overflow – Binary Arithmetic
ISO C11 Standard

Источник

Overflow is a phenomenon where operations on 2 numbers exceeds the maximum (or goes below the minimum) value the data type can have. Usually it is thought that integral types are very large and people don’t take into account the fact that sum of two numbers can be larger than the range. But in things like scientific and mathematical computation, this can happen. For example, an unhandled arithmetic overflow in the engine steering software was the primary cause of the crash of the maiden flight of the Ariane 5 rocket. The software had been considered bug-free since it had been used in many previous flights; but those used smaller rockets which generated smaller accelerations than Ariane 5’s.This article will tell how this problem can be tackled.

In this article, we will only deal with integral types (and not with types like float and double)

In order to understand how to tackle this problem we will first know how numbers are stored.

About integers:

If the size of a data type is n bytes, it can store 2⁸ⁿ different values. This is called the data type’s range.
If size of an unsigned data type is n bytes, it ranges from 0 to 2⁸ⁿ-1
If size of a signed data type is n bytes, it ranges from -2^8n-1 to 2^8n-1-1
So, a short(usually 2 bytes) ranges from -32768 to 32767 and an unsigned short ranges from 0 to 65535

Consider a short variable having a value of 250.
It is stored int the computer like this (in binary format)
00000000 11111010

Complement of a number is a number with its bits toggled. It is denoted by ~
For eg. ~250 is 11111111 00000101

Negative numbers are stored using 2’s complement system. According to this system, -n=~n+1
-250 is stored as 11111111 00000110
http://stackoverflow.com/questions/1049722/what-is-2s-complement

10000000 00000000 (-32768) has no positive counterpart. Its negative is the number itself (try -n=~n+1)

11100010 01110101 will be read as 57973 if data type is unsigned while it will be read as -7563 if data type is signed. If you add 65536 (which is the range) to -7563, you get 57973.

Overflow:

Consider a data type var_t of 1 byte (range is 256):
signed var_t a,b;
unsigned var_t c,d;

If c is 200(11001000) and d is 100(01100100), c+d is 300(00000001 00101100), which is more than the max value 255(11111111). 00000001 00101100 is more than a byte, so the higher byte will be rejected and c+d will be read as 44. So, 200+100=44! This is absurd! (Note that 44=300-256). This is an example of an unsigned overflow, where the value couldn’t be stored in the available no. of bytes. In such overflows, the result is moduloed by range (here, 256).

If a is 100(01100100) and b is 50(00110010), a+b is 150(10010110), which is more than the max value 127. Instead, a+b will be read as -106 (note that -106=150-256). This is an example of a signed overflow, where result is moduloed by range(here, 256).

Detecting overflow:

Division and modulo can never generate an overflow.

Addition overflow:

Overflow can only occur when sign of numbers being added is the same (which will always be the case in unsigned numbers)
signed overflow can be easily detected by seeing that its sign is opposite to that of the operands.

Let us analyze overflow in unsigned integer addition.

Consider 2 variables a and b of a data type with size n and range R.
Let + be actual mathematical addition and a$b be the addition that the computer does.

If a+b<=R-1, a$b=a+b
As a and b are unsigned, a$b is more or equal to than both a and b.

If a+b>=R a$b=a+b-R
as R is more than both a and b, a-R and b-R are negative
So, a+b-R<a and a+b-R<b
Therefore, a$b is less than both a and b.

This difference can be used to detect unsigned addition overflow. a-b can be treated as a+(-b) hence subtraction can be taken care of in the same way.

Multiplication overflow:
There are two ways to detect an overflow:

1. if a*b>max, then a>max/b (max is R-1 if unsigned and R/2-1 if signed).
2. Let there be a data type of size n and range R called var_t and a data type of size 2n called var2_t.
Let there be 2 variables of var_t called a and b. Range of var2_t will be R*R, which will always be more than the product of a and b. hence if var2_t(a)*var2_t(b)>R overflow has happened.

Truncation:
This happens when a shorter is assigned from a longer variable. For eg, short a;long b=70000;a=b;
Only the lower bits are copied and the value’s meaning is translated.
short a;int b=57973;a=b; will also show this behaviour become -7563.
Similar behaviour will be shown if int is replaced by unsigned short.

Type conversion:
consider unsigned int a=4294967290;int b=-6; return (a==b);
This returns 1.
Whenever an operation is performed between an unsigned and a signed variable of the same type, operands are converted to unsigned.
Whenever an operation is performed between a long type and a short type, operands are converted to the long type.
The above code returned 1 as a and b were converted to unsigned int and then compared.
If we used __int64 (a 64-bit type) instead of unsigned int and 18446744073709551610 instead of 4294967290, the result would have been the same.

Type promotion:
Whenever an operation is performed on two variables of a type shorter than int, the type of both variables is converted to int. For eg. short a=32000,b=32000;cout<<a+b<<endl; would display 64000, which is more than the max value of short. The reason is that a and b were converted to int and a+b would return an int, which can have a value of 64000.

Libraries:

Microsoft Visual C++ 2010 has a header file safeint.h which has functions like safeadd,safesubtract,etc. It is a templated header file (and hence header only).

Источник

Содержание

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

Флаги

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

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

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

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

Язык	Целое число без знака	Целое число со знаком
Ada	по модулю модуль типа	поднять Constraint_Error
C /C ++	по модулю степени двойки	неопределенное поведение
C#	по модулю степени 2 в непроверенном контексте; `System.OverflowException`возникает в проверенном контексте
Java	N / A	степень двойки по модулю
JavaScript	все числа имеют двойную точность с плавающей запятой, за исключением нового BigInt
MATLAB	Встроенные целые числа насыщаются. Целые числа с фиксированной запятой, настраиваемые для переноса или насыщения
Python 2	N/A	, преобразовываются в longтип (bigint)
Seed7	N / A	поднять OVERFLOW_ERROR
Схема	Н / Д	преобразовать в bigNum
Simulink	, конфигурируемый для переноса или насыщения
Smalltalk	Н / Д	преобразовать в LargeInteger
Swift	Вызывает ошибку, если не используются специальные операторы переполнения.

Обнаружение

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

Содержание

Источник

Флаги

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

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

Обнаружение

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

Обработка

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

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

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

Примеры

См. Также

Ссылки

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

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

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

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

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

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

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

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

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

См. также

Примечания

Переполнение целых знаковых чисел

Полезные ссылки

Переполнение целых чисел

Источник

Флаги

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

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

Обнаружение

Избегание

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

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

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

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

Примеры

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

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

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

Содержание

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

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

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

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

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

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

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

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

См. также

Примечания

Origin[edit]

Flags[edit]

Definition variations and ambiguity[edit]

Inconsistent behavior[edit]

Methods to address integer overflow problems[edit]

Detection[edit]

Avoidance[edit]

Handling[edit]

Explicit propagation[edit]

Programming language support[edit]

Saturated arithmetic[edit]

Examples[edit]

See also[edit]

References[edit]

External links[edit]

About integers:

Detecting overflow:

Libraries:

Содержание

Источник

Флаги

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

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

Обнаружение

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

Обработка

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