Integer Overflow bugs
Hello everyone, In this Post we will take a look at one of the most troublesome yet not very known type of software bugs: Integer overflows.
Back to school:
Bits, bytes, and words
The most fundamental unit of computer memory is the bit. A bit can be a tiny magnetic region on a hard disk, a tiny dent in the reflective material on a CD or DVD, or a tiny transistor on a memory stick. Whatever the physical implementation, the important thing to know about a bit is that, like a switch, it can only take one of two values: it is either “on” or “off”.
A collection of 8 bits is called a byte and (on the majority of computers today) a collection of 4 bytes, or 32 bits, is called a word. Each individual data value in a data set is usually stored using one or more bytes of memory, but at the lowest level, any data stored on a computer is just a large collection of bits.
The number of bytes and words used for an individual data value will vary depending on the storage format, the operating system, and even the computer hardware, but in many cases, a single letter or character of text takes up one byte and an integer, or whole number, takes up one word. A real or decimal number takes up one or two words depending on how it is stored.
For example, the text “hello” would take up 5 bytes of storage, one per character. The text “12345” would also require 5 bytes. The integer 12,345 would take up 4 bytes (1 word), as would the integers 1 and 12,345,678. The real number 123.45 would take up 4 or 8 bytes, as would the values 0.00012345 and 12345000.0.
What is an integer ?
An integer, in the context of computing, is a variable capable of representing a real number with no fractional part. Integers are typically the same size as a pointer on the system they are compiled on (i.e. on a 32 bit system, an integer is 32 bits long, on a 64 bit system, such as SPARC, an integer is 64 bits long).
Integers, like all variables are just regions of memory. When we talk about integers, we usually represent them in decimal, as that is the numbering system humans are most used to. Computers, being digital, cannot deal with decimal, so internally to the computer integers are stored in binary. Binary is another system of representing numbers which uses only two numerals, 1 and 0, as opposed to the ten numerals used in decimal. As well as binary and decimal, hexadecimal (base sixteen) is often used in computing as it is very easy to convert between binary and hexadecimal.
Integers are commonly stored using a word of memory, which is 4 bytes or 32 bits, so integers from 0 up to 4,294,967,295 (this is the maximum of unsigned integers)
Since it is often necessary to store negative numbers, there needs to be a mechanism to represent negative numbers using only binary. The way this is accomplished is by using the most significant bit (MSB) of a variable to determine the sign: if the MSB is set to 1, the variable is interpreted as negative; if it is set to 0, the variable is positive.
not all variables are signed, meaning they do not all use the MSB to determine whether they are positive or negative. These variable are known as unsigned and can only be assigned positive values, whereas variables which can be either positive or negative are called signed.
A signed integer ranges from -2147483648 to 2147483647. An unsigned integer is a 32-bit ranges from 0 to 4294967295. The signed integer is represented in twos complement notation.
What is an integer overflow:
We have two unsigned integers, a and b, both of which are 32 bits long. We assign to a the maximum value a 32 bit integer can hold, and to b we assign 1 We add a and b together and store the result in a third unsigned 32 bit integer called r:
Now, since the result of the addition cannot be represented using 32 bits, the result, in accordance with the ISO standard, is reduced modulo 0x100000000.
Reducing the result using modulo arithmetic basically ensures that only the lowest 32 bits of the result are used, so integer overflows cause the result to be truncated to a size that can be represented by the variable. This is often called a “wrap around”, as the result appears to wrap around to 0.
To make it easier, imagine that you are driving you car and you already made 999999 kilometres with it . now when you drive another kilometre the counter will be reset to 0. what happened ?? Same as the previous example the counter wasn’t supposed to hold value of 1000000 so it went back to 0.
Since an integer is a fixed size there is a fixed maximum value it can store. When an attempt is made to store a value greater than this maximum value it is known as an integer overflow. 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 ISO C99 standard says that an integer overflow causes “undefined behavior”, meaning that compilers conforming to the standard may do anything they like from completely ignoring the overflow to aborting the program. Most compilers seem to ignore the overflow, resulting in an unexpected or erroneous result being stored.
Examples
Example 1
in this first example we will see how an integer overflow can lead to another vulnerability which is a heap overflow. let’s check is code
this code will allocate space to a file(let’s say it is code in a file transfer app) by adding it’s size and name so if the file_size is 16 and name_size is 4 the code will allocate 20 bytes.
But if file_size is 4294967295 and we want to add 4 the allocated space will become 3. So the application allocated 3 bytes of space for a file with over 4294967295 bytes in size. this will create a heap overflow in our program which can lead to a huge security problem.
Example 2
now this is another example from a CTF challenge: When we connect to the server, we’re given a number and we’re prompted for a number to make it negative
The solution is to cause an integer overflow. 2,147,483,647 is the maximum positive value for a 32-bit signed integer, so if we enter that it should cause an integer overflow when added to the server’s number:
so when we added 2147483647 to 440902 the cpu was unable to store the result because it’s the greater than a singed integer could store what happened is that variable went back -2147483648 ( remember your car counter ??) and started calculating from there…
Example 3
The vulnerability here is an unsigned integer overflow. The challenge does not allow us to add more than 100 bonus points, but we can take away more than 100. Therefore, if we take away our current score we get to 0 , and if we take away one more point we get to 0xffffffff We can see that we manage to put our score to the value 4294967295 ( 0xffffffff in hex) and therefore validate the test!
Real world scenarios
Conclusion
Integer overflows can be extremely dangerous, partly because it is impossible to detect them after they have happened. If an integer overflow takes place, the application cannot know that the calculation it has performed is incorrect, and it will continue under the assumption that it is. Even though they can be difficult to exploit, and frequently cannot be exploited at all, they can cause unexpected behaviour, which is never a good thing in a secure system.
Целочисленное переполнение — Integer overflow
Целочисленное переполнение может быть продемонстрировано с помощью одометр переполнение, механическая версия явления. Все цифры устанавливаются на максимум 9, и следующее приращение белой цифры вызывает каскад переходящих добавлений, устанавливающих все цифры на 0, но нет более высокой цифры (цифра 100000), которая могла бы измениться на 1, поэтому счетчик сбрасывается в ноль. Это обертывание в отличие от насыщения.
В компьютерном программировании, целочисленное переполнение происходит, когда арифметическая операция пытается создать числовое значение, которое находится за пределами диапазона, который может быть представлен заданным числом цифр — выше максимального или ниже минимального представимого значения.
Наиболее частым результатом переполнения является сохранение наименее значимых представимых цифр результата; считается, что результат оборачивается вокруг максимума (т.е. по модулю степень системы счисления, обычно два в современных компьютерах, но иногда десять или другое основание).
Состояние переполнения может привести к непредвиденным результатам. В частности, если возможность не была предвидена, переполнение может поставить под угрозу надежность программы и безопасность.
. Для некоторых приложений, таких как таймеры и часы, может быть желательным перенос при переполнении. В стандарте C11 указано, что для беззнаковых целых чисел перенос по модулю является определенным поведением, и термин «переполнение» никогда не применяется: «вычисление, включающее беззнаковые операнды, никогда не может переполниться».
На некоторых процессорах, таких как графические процессоры (графические процессоры) и процессоры цифровых сигналов (DSP), которые поддерживают арифметику насыщения, результаты переполнения будут «ограничены», т. е. установлены на минимум или максимум значение в представляемом диапазоне, а не обертывается.
Содержание
- 1 Источник
- 2 Флаги
- 3 Варианты определения и неоднозначность
- 4 Методы решения проблем целочисленного переполнения
- 4.1 Обнаружение
- 4.2 Предотвращение
- 4.3 Обработка
- 4.4 Явное распространение
- 4.5 Поддержка языка программирования
- 4.6 Насыщенная арифметика
Источник
ширина регистра процессора определяет диапазон значений, которые могут быть представлены в его регистрах. Хотя подавляющее большинство компьютеров может выполнять арифметические операции с множественной точностью для операндов в памяти, позволяя числам быть произвольно длинными и избегать переполнения, ширина регистра ограничивает размеры чисел, с которыми можно работать (например, складывать или вычитать) с использованием одна инструкция на операцию. Типичная двоичная ширина регистра для целых чисел без знака включает:
- 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 долларов, поэтому любой превышающий эту сумму приз должен быть результатом ошибки программирования. Верховный суд штата Айова вынес решение в пользу казино.
What is an integer overflow error?
What is an integer overflow error? Why do i care about such an error? What are some methods of avoiding or preventing it?
10 Answers 10
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).
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.
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.
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.
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.
Integer overflow ошибка как исправить
Ironically, often the invalid code involves checking for these integer limits. For example the following may overflow and so is invalid:
Undefined Behavior
[note from Sep 2013: The MIT CSAIL lab have a great paper summarising cases of the more general problem of undefined behavior in C programs, and they have subsequently released STACK, a new tool for finding undefined behavior bugs by finding dead code, which can be used to find cases like described above. Note these «ignored code» issues can even occur with unsigned integers, which gives more importance to using automated tools like this to flag such cases.]
clang >= 3.3 and GCC >= 4.9 have the -fsanitize=undefined option to enable the UndefinedBehaviorSanitizer (ubsan) to detect various undefined behaviors at runtime. Specifics relating to integer overflow detection are mentioned below. Also tis-interpreter developed through a Linux foundation grant, is available as of Apr 2016, and will interpret C source to identify undefined behavior.
Finding integer overflow issues
At compile time
Note none of these options warn or change the operation of the above example for unsigned integers – only signed integer overflow is catered for. Note also the -Wconversion warning which is quite awkward to avoid, but again useful when writing new code. Note also that one can give the compiler hints about signed integers to avoid certain warnings. For example one can use the gnulib assume macro to indicate an int is always positive like assume(optind > 0); .
At run time
Avoiding integer overflow issues
[Update Jul 2014: CERT has good examples on avoiding overflow with signed integers for various operations.]
Following is a more involved example where we want to round a value, with an initial naïve approach susceptible to overflow. The above overflows as the file size approaches OFF_T_MAX. I.E. the result will go negative as file_size + n/2 rolls over OFF_T_MAX. One might be tempted to use implicit promotion to unsigned as follows: However the above will fail when _FILE_OFFSET_BITS=64. I.E. when off_t is wider than int. If we had used long instead of int then we have the same issue on 32 bit systems. Generally issues porting between platforms with different width ints are a common source of these overflow bugs. The examples below, show how to handle this overflow using the 3 techniques mentioned above, with the «implicit promotion» probably being most appropriate for this situation.
Integer overflow in other languages
Rust being a programming language designed to protect against bugs, has explicit protection in this area. In debug mode, integer overflows panic by default, while reverting to the C wrapping behavior in release mode. In addition there is no undefined operation wrt overflows, and so is much easier to reason about. For details see this post on integer overflow in rust.
Python being higher level has integer objects abstracted from the base machine integer hardware, and so integers do not overflow, and are constrained only by available memory. Note however floats do map to base hardware and so overflow like in C.