Целочисленное переполнение - Integer overflow

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

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

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

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

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

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

Источник

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

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

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

В частности, умножение или сложение двух целых чисел может привести к неожиданно маленькому значению, а вычитание из небольшого целого числа может вызвать перенос на большое положительное значение (например, сложение 8-битных целых чисел 255 + 2 дает 1, что является 257 мод 28, и аналогично вычитание 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 (из-за того, что уровень кодируется в один байт, например, 6416 соответствует уровню 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]

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

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

  1. ^ а б c ISO. «ISO / IEC 9899: 2011 Информационные технологии - Языки программирования - C». webstore.ansi.org.
  2. ^ «Обертывание при переполнении - MATLAB и Simulink». www.mathworks.com.
  3. ^ «Насыщение при переполнении - MATLAB и Simulink». www.mathworks.com.
  4. ^ Арифметическое переполнение
  5. ^ «CWE - CWE-191: целочисленное истощение (перенос или повторение) (3.1)». cwe.mitre.org.
  6. ^ «Переполнение и потеря типов данных в Java - DZone Java». dzone.com.
  7. ^ Мир, Табиш (4 апреля 2017 г.). «Целочисленное переполнение / потеря значимости и неточность с плавающей точкой». medium.com.
  8. ^ "Целочисленное переполнение и обработка метаданных MP4 в libstagefright при переполнении буфера". Mozilla.
  9. ^ «Предотвращение переполнения и истощения буфера». developer.apple.com.
  10. ^ Билл Вагнер. «Проверено и отключено (Справочник по C #)». msdn.microsoft.com.
  11. ^ Руководство Seed7, раздел 15.2.3 OVERFLOW_ERROR.
  12. ^ Язык программирования Swift. Версия Swift 2.1. 21 октября 2015 года.
  13. ^ Как если бы бесконечно ранжированная целочисленная модель
  14. ^ Мунтян, Пол Иоан; Монперрус, Мартин; Сунь, Хао; Гроссклагс, Йенс; Эккерт, Клаудия (2019). «IntRepair: информированное восстановление целочисленных переполнений». IEEE Transactions по разработке программного обеспечения: 1. arXiv:1807.05092. Дои:10.1109 / TSE.2019.2946148. ISSN  0098-5589.
  15. ^ Документация Python, раздел 5.1 Арифметические преобразования.
  16. ^ "Декларация ТИП". Common Lisp HyperSpec.
  17. ^ "Декларация ОПТИМИЗИРОВАТЬ". Common Lisp HyperSpec.
  18. ^ Редди, Абхишек (22 августа 2008 г.). "Особенности Common Lisp".
  19. ^ Пирс, Бенджамин С. (2002). Типы и языки программирования. MIT Press. ISBN  0-262-16209-1.
  20. ^ Райт, Эндрю К .; Маттиас Фелляйзен (1994). «Синтаксический подход к правильности написания». Информация и вычисления. 115 (1): 38–94. Дои:10.1006 / inco.1994.1093.
  21. ^ Макракис, Ставрос (апрель 1982 г.). «Безопасность и мощь». Примечания по разработке программного обеспечения ACM SIGSOFT. 7 (2): 25–26. Дои:10.1145/1005937.1005941.
  22. ^ «Extra, Extra - прочтите все об этом: почти все двоичные поиски и слияния не работают». googleresearch.blogspot.co.uk.
  23. ^ Глейк, Джеймс (1 декабря 1996 г.). "Ошибка и авария". Нью-Йорк Таймс. Получено 17 января 2019.
  24. ^ Официальный отчет об инциденте с неудачным запуском Ariane 5.
  25. ^ Муавад, Джад (30 апреля 2015 г.). "Постановление ФАА о возможной потере мощности в Боинге 787". Нью-Йорк Таймс.
  26. ^ «US-2015-09-07: Электроэнергия - Деактивация». Директивы по летной годности. Европейское агентство авиационной безопасности. 4 мая 2015.
  27. ^ Питтман, Джейми. "Досье Пакмана".
  28. ^ Планкетт, Люк (2016-03-02). «Почему Ганди такой засранец в цивилизации». Котаку. Получено 2018-07-30.
  29. ^ Minecraft Gamepedia. "Страница Minecraft Gamepedia".
  30. ^ https://www.youtube.com/watch?v=aNQdQPi0xMo&t=17m55s
  31. ^ https://steamcommunity.com/app/20510/discussions/0/1484358860942756615/
  32. ^ Структура данных покемонов в поколении I
  33. ^ Структура данных покемонов в поколении II
  34. ^ Структура данных покемонов в поколении III
  35. ^ Структура данных покемонов в поколении IV
  36. ^ Lenclud, Кристоф. «Отладка IBM MACRO Assembler версии 1.00».
  37. ^ Кравец, Давид (15 июня 2017 г.). "Извините, мэм, вы не выиграли 43 миллиона долларов - произошла неисправность игрового автомата.'". Ars Technica.

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