Войти
Целочисленное переполнение может быть продемонстрировано с помощью одометр переполнение, механическая версия явления. Все цифры устанавливаются на максимум 9, и следующее приращение белой цифры вызывает каскад переходящих добавлений, устанавливающих все цифры на 0, но нет более высокой цифры (цифра 100000), которая могла бы измениться на 1, поэтому счетчик сбрасывается в ноль. Это обертывание в отличие от насыщения. В компьютерном программировании, целочисленное переполнение происходит, когда арифметическая операция пытается создать числовое значение, которое находится за пределами диапазона, который может быть представлен заданным числом цифр - выше максимального или ниже минимального представимого значения.
Наиболее частым результатом переполнения является сохранение наименее значимых представимых цифр результата; считается, что результат оборачивается вокруг максимума (т.е. по модулю степень системы счисления, обычно два в современных компьютерах, но иногда десять или другое основание).
Состояние переполнения может привести к непредвиденным результатам. В частности, если возможность не была предвидена, переполнение может поставить под угрозу надежность программы и безопасность.
. Для некоторых приложений, таких как таймеры и часы, может быть желательным перенос при переполнении. В стандарте C11 указано, что для беззнаковых целых чисел перенос по модулю является определенным поведением, и термин «переполнение» никогда не применяется: «вычисление, включающее беззнаковые операнды, никогда не может переполниться».
На некоторых процессорах, таких как графические процессоры (графические процессоры) и процессоры цифровых сигналов (DSP), которые поддерживают арифметику насыщения, результаты переполнения будут «ограничены», т. е. установлены на минимум или максимум значение в представляемом диапазоне, а не обертывается.
ширина регистра процессора определяет диапазон значений, которые могут быть представлены в его регистрах. Хотя подавляющее большинство компьютеров может выполнять арифметические операции с множественной точностью для операндов в памяти, позволяя числам быть произвольно длинными и избегать переполнения, ширина регистра ограничивает размеры чисел, с которыми можно работать (например, складывать или вычитать) с использованием одна инструкция на операцию. Типичная двоичная ширина регистра для целых чисел без знака включает:
Когда арифметическая операция дает результат, превышающий указанный выше максимум для 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 долларов, поэтому любой превышающий эту сумму приз должен быть результатом ошибки программирования. Верховный суд штата Айова вынес решение в пользу казино.
