Целочисленное переполнение
В компьютерном программировании переполнение целых чисел происходит, когда арифметическая операция над целыми числами пытается создать числовое значение, находящееся за пределами диапазона, который может быть представлен заданным количеством цифр — либо выше максимального, либо ниже минимального представимого значения.
Наиболее распространенным результатом переполнения является сохранение наименее значимых представимых цифр результата; Говорят, что результат округляется вокруг максимума (т.е. по модулю степени основания , обычно двух в современных компьютерах, но иногда десяти или другого числа). На некоторых процессорах, таких как графические процессоры (GPU) и цифровые сигнальные процессоры (DSP), которые поддерживают арифметику насыщения , результаты переполнения будут фиксироваться , т.е. устанавливаться на минимальное значение в представимом диапазоне, если результат ниже минимума, и устанавливаться на максимум. значение в представимом диапазоне, если результат превышает максимум, а не округляется.
Условие переполнения может привести к непредвиденному поведению. программы В частности, если такая возможность не была предусмотрена, переполнение может поставить под угрозу надежность и безопасность .
Для некоторых приложений, таких как таймеры и часы, может быть желательным перенос при переполнении. Стандарт C11 гласит, что для беззнаковых целых чисел перенос по модулю является определенным поведением, и термин «переполнение» никогда не применяется: «вычисление, включающее беззнаковые операнды, никогда не может переполниться». [1]
Происхождение [ править ]
Ширина регистра процессора определяет диапазон значений, которые могут быть представлены в его регистрах. Хотя подавляющее большинство компьютеров могут выполнять арифметические операции с множественной точностью над операндами в памяти, позволяя числам быть произвольной длины и избегать переполнения, ширина регистра ограничивает размеры чисел, с которыми можно работать (например, складывать или вычитать), используя одна инструкция на операцию. Типичные ширины двоичного регистра для беззнаковых целых чисел включают:
- 4-битный : максимальное представимое значение 2 4 − 1 = 15
- 8-бит : максимальное представимое значение 2 8 − 1 = 255
- 16 бит : максимальное представимое значение 2 16 − 1 = 65,535
- 32-битный : максимальное представимое значение 2 32 − 1 = 4 294 967 295 (наиболее распространенная ширина для персональных компьютеров по состоянию на 2005 г.). [update]),
- 64-битный : максимальное представимое значение 2 64 − 1 = 18 446 744 073 709 551 615 (наиболее распространенная ширина центральных процессоров (ЦП) персональных компьютеров по состоянию на 2024 г. [update]),
- 128 бит : максимальное представимое значение 2 128 − 1 = 340,282,366,920,938,463,463,374,607,431,768,211,455
Когда беззнаковая арифметическая операция дает результат, превышающий указанный выше максимум для N-битного целого числа, переполнение уменьшает результат до модуля N-й степени 2, сохраняя только младшие значащие биты результата и эффективно вызывая перенос .
В частности, умножение или сложение двух целых чисел может привести к получению неожиданно малого значения, а вычитание из маленького целого числа может привести к переходу к большому положительному значению (например, сложение 8-битных целых чисел 255 + 2 приводит к 1, что это 257 мод 2 8 , и аналогично вычитание 0 - 1 приводит к 255, двоичному представлению числа -1).
Подобный циклический обход может нанести ущерб безопасности: если в качестве количества байтов, выделяемых для буфера, используется значение переполнения, буфер будет выделен неожиданно малым размером, что потенциально может привести к переполнению буфера, которое, в зависимости от использования буфера, может привести к его переполнению. очередь, вызывает выполнение произвольного кода.
Если переменная имеет целочисленный тип со знаком, программа может предположить, что переменная всегда содержит положительное значение. Целочисленное переполнение может привести к переносу значения и стать отрицательным, что нарушает предположение программы и может привести к неожиданному поведению (например, сложение 8-битного целого числа 127 + 1 приводит к -128, двоичному дополнению 128). (Решением этой конкретной проблемы является использование целочисленных типов без знака для значений, которые программа ожидает и предполагает, что они никогда не будут отрицательными.)
Флаги [ править ]
Большинство компьютеров имеют два выделенных флага процессора для проверки условий переполнения.
Флаг переноса устанавливается, когда результат сложения или вычитания, учитывая операнды и результат как беззнаковые числа, не умещается в заданное количество бит. Это указывает на переполнение с переносом или заимствованием старшего бита . Сразу после операции сложения с переносом или вычитания с заимствованием содержимое этого флага будет использоваться для изменения регистра или ячейки памяти, содержащей старшую часть многословного значения.
Флаг переполнения устанавливается, когда результат операции над числами со знаком не имеет того знака, который можно было бы предсказать по знакам операндов, например, отрицательный результат при сложении двух положительных чисел. Это указывает на то, что произошло переполнение, и результат со знаком, представленный в форме дополнения до двух, не умещается в заданное количество битов.
Варианты определений и двусмысленность [ править ]
Для беззнакового типа, когда идеальный результат операции находится за пределами представимого диапазона типа, а возвращаемый результат получается путем переноса, это событие обычно определяется как переполнение. Напротив, стандарт C11 определяет, что это событие не является переполнением, и утверждает, что «вычисление, включающее беззнаковые операнды, никогда не может переполниться». [1]
Когда идеальный результат целочисленной операции находится за пределами представимого диапазона типа, а возвращаемый результат получается путем ограничения, то это событие обычно определяется как насыщение. Использование варьируется в зависимости от того, является ли насыщение переполнением или нет. Чтобы устранить двусмысленность, термины, оборачивающие перенос, переполняются. [2] и насыщающий перелив [3] можно использовать.
Можно найти множество ссылок на целочисленное опустошение. [4] [5] [6] [7] [8] Когда используется термин «недополнение целого числа», это означает, что идеальный результат был ближе к отрицательной бесконечности, чем представимое значение выходного типа, ближайшее к отрицательной бесконечности. В зависимости от контекста определение переполнения может включать все типы, включая опустошение, или оно может включать только случаи, когда идеальный результат был ближе к положительной бесконечности, чем представимое значение выходного типа, наиболее близкое к положительной бесконечности.
Если идеальный результат операции не является точным целым числом, в крайних случаях значение переполнения может быть неоднозначным. Рассмотрим случай, когда идеальный результат имеет значение 127,25, а максимальное представимое значение выходного типа равно 127. Если переполнение определяется как идеальное значение, находящееся за пределами представимого диапазона выходного типа, тогда этот случай будет классифицироваться как переполнение. Для операций с четко определенным поведением округления классификацию переполнения, возможно, придется отложить до тех пор, пока не будет применено округление. Стандарт C11 [1] определяет, что преобразования из числа с плавающей запятой в целое число должны округляться в сторону нуля. Если C используется для преобразования значения с плавающей запятой 127,25 в целое число, то сначала следует применить округление, чтобы получить идеальное целочисленное значение 127. Поскольку округленное целое число находится в диапазоне выходных значений, стандарт C не будет классифицировать это преобразование как переполнение. .
Непоследовательное поведение [ править ]
Поведение при возникновении переполнения может быть неодинаковым при всех обстоятельствах. Например, в языке Rust , хотя функциональность предоставляется пользователям для выбора и контроля, поведение базового использования математических операторов естественным образом фиксировано; однако это фиксированное поведение различается для программ, созданных в режиме «отладки», и программ, созданных в режиме «релиз». [9] В C переполнение целого числа без знака определено для переноса, тогда как переполнение целого числа со знаком вызывает неопределенное поведение .
Методы решения проблем целочисленного переполнения [ править ]
Язык | Беззнаковое целое число | Целое число со знаком |
---|---|---|
Есть | по модулю модуль типа | поднять Constraint_Error |
С , С++ | по модулю степени двойки | неопределенное поведение |
С# | степень по модулю 2 в непроверяемом контексте; System.OverflowException вызывается в проверенном контексте [10] | |
Ява | степень двойки по модулю (char — единственный беззнаковый примитивный тип в Java) | по модулю степени двойки |
JavaScript | все числа имеют плавающую запятую двойной точности, кроме нового BigInt | |
МАТЛАБ | Встроенные целые числа насыщают. Целые числа с фиксированной точкой, настраиваемые для переноса или насыщения | |
Питон 2 | — | преобразовать в длинный тип (bigint) |
Сид7 | — | поднять OVERFLOW_ERROR [11] |
Схема | — | конвертировать в bigNum |
Симулинк | настраивается для обертывания или насыщения | |
Смолток | — | конвертировать в LargeInteger |
Быстрый | Вызывает ошибку, если не используются специальные операторы переполнения. [12] |
Обнаружение [ править ]
Реализация обнаружения переполнения во время выполнения UBSan
( дезинфицирующее средство неопределенного поведения ) доступно для компиляторов C.
В Java 8 есть перегруженные методы , например Math.addExact(int, int)
, который выдаст ArithmeticException
в случае переполнения.
Группа реагирования на компьютерные чрезвычайные ситуации (CERT) разработала целочисленную модель As-if Infinitely Ranged (AIR) — в значительной степени автоматизированный механизм для устранения переполнения и усечения целых чисел в C/C++ с использованием обработки ошибок во время выполнения. [13]
Избегание [ править ]
Назначая переменным типы данных, которые достаточно велики, чтобы содержать все значения, которые могут быть вычислены и сохранены в них, всегда можно избежать переполнения. Даже если доступное пространство или фиксированные типы данных, предоставляемые языком программирования или средой, слишком ограничены, чтобы можно было безопасно выделять переменные больших размеров, тщательно упорядочивая операции и заранее проверяя операнды, часто можно заранее гарантировать что результат никогда не будет больше, чем можно сохранить. Инструменты статического анализа , формальная проверка и методы проектирования по контракту могут использоваться для более надежной и надежной гарантии того, что случайное переполнение не произойдет.
Обработка [ править ]
Если ожидается, что может произойти переполнение, в программу можно вставить тесты, чтобы определить, когда это произойдет или вот-вот произойдет, и выполнить другую обработку для смягчения этого явления. Например, если важный результат, вычисленный в результате переполнения пользовательского ввода, программа может остановиться, отклонить ввод и, возможно, предложить пользователю ввести другой ввод, вместо того, чтобы программа продолжила работу с недопустимым переполненным вводом и, возможно, как следствие, дала сбой.
У процессоров обычно есть способ обнаружить это и поддержать сложение чисел, превышающих размер их регистра, обычно с использованием бита состояния. Этот метод называется арифметикой множественной точности. Таким образом, можно выполнять побайтовое сложение операндов, ширина которых превышает байт: сначала добавляют младшие байты, сохраняют результат и проверяют на переполнение; затем добавьте старшие байты и, если необходимо, добавьте перенос из младших байтов, а затем сохраните результат.
Обработка возможного переполнения вычисления иногда может представлять собой выбор между выполнением проверки перед вычислением (чтобы определить, произойдет ли переполнение) или после него (чтобы определить, вероятно ли это произошло, на основе результирующего значения). Поскольку некоторые реализации могут генерировать условие ловушки при переполнении целого числа, наиболее переносимые программы проверяют перед выполнением операции, которая может переполниться.
Поддержка языков программирования [ править ]
Языки программирования реализуют различные методы предотвращения случайного переполнения: Ada , Seed7 и некоторые варианты функциональных языков вызывают условие исключения при переполнении, в то время как Python (начиная с версии 2.4) плавно преобразует внутреннее представление числа в соответствии с его ростом, в конечном итоге представляя его как long
– чьи возможности ограничены только доступной памятью. [14]
В языках с встроенной поддержкой арифметики произвольной точности и безопасности типов (таких как Python , Smalltalk или Common Lisp ) числа автоматически увеличиваются до большего размера при возникновении переполнения или выдаются исключения (сигнализируются условия), когда существует ограничение диапазона. Таким образом, использование таких языков может помочь смягчить эту проблему. Однако в некоторых таких языках все же возможны ситуации, когда может произойти целочисленное переполнение. Примером может служить явная оптимизация пути кода, который профилировщик считает узким местом. В случае Common Lisp это возможно с помощью явного объявления для аннотации типа переменной к слову машинного размера (fixnum). [15] и снизить уровень безопасности типа до нуля [16] для конкретного блока кода. [17] [18] [19] [20]
В отличие от старых языков, таких как C, некоторые новые языки, такие как Rust, предоставляют встроенные функции, которые позволяют легко обнаруживать и выбирать пользователю способ обработки переполнения в каждом конкретном случае. В Rust, хотя использованию базовых математических операторов, естественно, не хватает такой гибкости, пользователи могут альтернативно выполнять вычисления с помощью набора методов, предоставляемых каждым из целочисленных примитивных типов. Эти методы дают пользователям несколько вариантов выбора между выполнением операции проверки (или переполнения ) (которая указывает, произошло ли переполнение через тип возвращаемого значения); «непроверенная» операция; операция, выполняющая перенос, или операция, выполняющая насыщение числовых границ.
Насыщенная арифметика [ править ]
В компьютерной графике или обработке сигналов обычно работают с данными в диапазоне от 0 до 1 или от –1 до 1. Например, возьмем изображение в оттенках серого , где 0 представляет черный цвет, 1 представляет белый, а значения между ними представляют оттенки. серого цвета. Одна из операций, которую можно поддержать, — это осветление изображения путем умножения каждого пикселя на константу. Насыщенная арифметика позволяет просто слепо умножать каждый пиксель на эту константу, не беспокоясь о переполнении, просто придерживаясь разумного результата, что все эти пиксели больше 1 (т. е. «ярче белого» ) просто становятся белыми, а все значения «темнее черного». «Просто стань черным.
Примеры [ править ]
Непредвиденное арифметическое переполнение является довольно распространенной причиной ошибок программы . Такие ошибки переполнения может быть трудно обнаружить и диагностировать, поскольку они могут проявиться только для очень больших наборов входных данных, которые с меньшей вероятностью будут использоваться в проверочных тестах.
Взятие среднего арифметического двух чисел путем их сложения и деления на два, как это делается во многих алгоритмах поиска , приводит к ошибке, если сумма (но не результирующее среднее) слишком велика для представления и, следовательно, переполняется. [21]
В период с 1985 по 1987 год арифметическое переполнение в Therac-25 аппаратах лучевой терапии , а также отсутствие аппаратных средств контроля безопасности стали причиной смерти по меньшей мере шести человек от передозировки радиации. [22]
Необработанное арифметическое переполнение в программном обеспечении управления двигателем стало основной причиной крушения первого полета ракеты Ariane 5 в 1996 году . [23] Программное обеспечение считалось безошибочным, поскольку оно использовалось во многих предыдущих полетах, но в них использовались ракеты меньшего размера, которые создавали меньшее ускорение, чем Ariane 5. К сожалению, часть программного обеспечения, в которой возникала ошибка переполнения, даже не требовалась. работавший на Ariane 5 в то время, когда ракета вышла из строя: это был процесс режима запуска для меньшего предшественника Ariane 5, который оставался в программном обеспечении, когда он был адаптирован для новой ракеты. Кроме того, истинной причиной сбоя был недостаток в технической спецификации того, как программное обеспечение справлялось с переполнением при его обнаружении: оно делало диагностический дамп на свою шину, которая должна была быть подключена к тестовому оборудованию во время тестирования программного обеспечения во время разработки. но во время полета был подключен к рулевым двигателям ракеты; сброс данных сильно отклонил сопло двигателя в сторону, что вывело ракету из-под аэродинамического управления и ускорило ее быстрое разрушение в воздухе. [24]
30 апреля 2015 года Федеральное управление гражданской авиации США объявило, что прикажет операторам Boeing 787 периодически перезагружать его электрическую систему, чтобы избежать целочисленного переполнения, которое может привести к отключению электроэнергии и срабатыванию напорной воздушной турбины , а компания Boeing развернула обновление программного обеспечения в четвертый квартал. [25] Европейское агентство авиационной безопасности последовало примеру 4 мая 2015 года. [26] Ошибка возникает через 2 31 сотые доли секунды (около 249 дней), обозначающие 32-битное со знаком целое число .
Ошибки переполнения очевидны в некоторых компьютерных играх. В Super Mario Bros. для NES сохраненное количество жизней представляет собой знаковый байт (в диапазоне от -128 до 127), что означает, что игрок может безопасно иметь 127 жизней, но когда игрок достигает своей 128-й жизни, счетчик обнуляется. живет (хотя счетчик чисел перед этим дает сбой) и перестает вести счет. Таким образом, если игрок затем умрет, игра немедленно закончится. Это вызвано переполнением данных игры, которое было ошибкой программирования, поскольку разработчики, возможно, не думали, что можно заработать такое количество жизней.
В аркадной игре Donkey Kong невозможно пройти уровень 22 из-за целочисленного переполнения времени/бонуса. Игра вычисляет время/бонус, беря номер уровня, на котором находится пользователь, умножая его на 10 и прибавляя 40. Когда он достигает 22 уровня, число времени/бонуса становится 260, что слишком велико для 8-битного 256. регистр значения, поэтому он переполняется до значения 4 – слишком короткого для завершения уровня. В Donkey Kong Jr. Math при попытке вычислить число больше 10 000 отображаются только первые 4 цифры. Переполнение — причина знаменитого уровня «разделённого экрана» в Pac-Man . [27] Подобная ошибка также привела к появлению Far Lands в Minecraft Java Edition, существовавшей с периода разработки Infdev до бета-версии 1.7.3; позже это было исправлено в бета-версии 1.8. Та же ошибка существовала и в Minecraft Bedrock Edition, но с тех пор была исправлена. [28]
В для Super Nintendo Entertainment System (SNES) игре Lamborghini American Challenge игрок может привести к тому, что его сумма денег упадет ниже 0 долларов во время гонки, будучи оштрафована сверх лимита оставшихся денег после уплаты сбора за гонку, что приводит к сбою в целом числе. и дает игроку на 65 535 000 долларов больше, чем он мог бы получить после отрицательного результата. [29]
IBM – Microsoft Macro Assembler (MASM) версии 1.00 и, вероятно, все другие программы, созданные тем же компилятором Pascal , имели целочисленное переполнение и ошибку знака в коде настройки стека, что не позволяло им работать на новых машинах DOS или эмуляторах под некоторыми распространенными конфигурации с объемом памяти более 512 КБ. Программа либо зависает, либо отображает сообщение об ошибке и выходит в DOS. [30]
В августе 2016 года казино автомат Resorts World напечатал призовой билет на сумму 42 949 672,76 долларов США из-за ошибки переполнения. Казино отказалось выплатить эту сумму, назвав это неисправностью, используя в свою защиту то, что в автомате четко указано, что максимальная выплата составляет 10 000 долларов, поэтому любой приз, превышающий эту сумму, должен быть результатом ошибки в программировании. Комиссия по азартным играм штата Нью-Йорк вынесла решение в пользу казино. [31]
См. также [ править ]
- Перенос (арифметика)
- Переполнение буфера
- Переполнение буфера стека
- Переполнение кучи
- Модульная арифметика
- Ядерный Ганди
- Указатель крутится
- Тестирование программного обеспечения
- Статический анализ программы
- Unix-сигнал
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б с Сотрудники ИСО. «ISO/IEC 9899:2011 Информационные технологии. Языки программирования — C» . ANSI.org .
- ^ «Перенос при переполнении — MATLAB & Simulink» . www.mathworks.com .
- ^ «Насыщение при переполнении — MATLAB & Simulink» . www.mathworks.com .
- ^ «CWE — CWE-191: Целочисленное опустошение (перенос или перенос) (3.1)» . cwe.mitre.org .
- ^ «Переполнение и потеря типов данных в Java — DZone Java» . dzone.com .
- ^ Мир, Табиш (4 апреля 2017 г.). «Целочисленное переполнение/недополнение и неточность чисел с плавающей запятой» . Medium.com .
- ^ «Целочисленное переполнение и переполнение буфера при обработке метаданных MP4 в libstagefright» . Мозилла .
- ^ «Предотвращение переполнения и опустошения буфера» . разработчик.apple.com .
- ^ «Операторные выражения — Справочник по Rust» . Rust-lang.org . Проверено 12 февраля 2021 г.
- ^ БиллВагнер (8 апреля 2023 г.). «Выбрано и не отмечено (Справочник по C#)» . msdn.microsoft.com .
- ^ Руководство Seed7 , раздел 16.3.3 OVERFLOW_ERROR.
- ^ Язык программирования Swift. Свифт 2.1 издание. 21 октября 2015 г.
- ^ Как будто целочисленная модель с бесконечным диапазоном
- ^ Документация Python , раздел 5.1 Арифметические преобразования.
- ^ « Декларации ТИП » . Common Lisp HyperSpec .
- ^ « Декларация ОПТИМИЗАЦИЯ » . Common Lisp HyperSpec .
- ^ Редди, Абхишек (22 августа 2008 г.). «Особенности Common Lisp» .
- ^ Пирс, Бенджамин К. (2002). Типы и языки программирования . МТИ Пресс. ISBN 0-262-16209-1 .
- ^ Райт, Эндрю К.; Феллейзен, Матиас (1994). «Синтаксический подход к правильности типов» . Информация и вычисления . 115 (1): 38–94. дои : 10.1006/inco.1994.1093 .
- ^ Макракис, Ставрос (апрель 1982 г.). «Безопасность и мощность». Заметки по разработке программного обеспечения ACM SIGSOFT . 7 (2): 25–26. дои : 10.1145/1005937.1005941 . S2CID 10426644 .
- ^ «Дополнительно, дополнительно — прочтите все об этом: почти все двоичные поиски и сортировки слиянием не работают» . googleresearch.blogspot.co.uk . 2 июня 2006 г.
- ^ Бойлер, Патрик (5 июля 2021 г.). «Когда маленькие ошибки в программном обеспечении вызывают большие проблемы» . Блог Грио . Проверено 16 июля 2023 г.
- ^ Глейк, Джеймс (1 декабря 1996 г.). «Ошибка и сбой» . Нью-Йорк Таймс . Проверено 17 января 2019 г.
- ^ Официальный отчет об инциденте с неудачным запуском Ariane 5.
- ^ Муавад, Джад (30 апреля 2015 г.). «ФАУ предписало исправить возможную потерю мощности в Боинге 787» . Нью-Йорк Таймс .
- ^ «US-2015-09-07: Электроэнергия – деактивация» . Директивы по летной годности . Европейское агентство авиационной безопасности . 4 мая 2015 г.
- ^ Питтман, Джейми. «Досье Пак-Мэна» .
- ^ «Далекие земли» . Майнкрафт Вики . Проверено 24 сентября 2023 г.
- ^ Архивировано в Ghostarchive и Wayback Machine : «Lamborghini American Challenge SPEEDRUN (13:24)» . Ютуб . 14 марта 2019 г.
- ^ Ленклуд, Кристоф (21 апреля 2017 г.). «Отладка IBM MACRO Assembler версии 1.00» .
- ^ Кравец, Давид (15 июня 2017 г.). «Извините, мэм, вы не выиграли 43 миллиона долларов – произошел сбой в игровом автомате » . Арс Техника .
Внешние ссылки [ править ]
- Phrack #60, Базовые целочисленные переполнения
- Phrack #60, Целочисленная защита с помощью большого цикла
- Эффективное и точное обнаружение целочисленных атак
- Классификация угроз WASC – целочисленные переполнения
- Понимание целочисленного переполнения в C/C++
- Двоичное переполнение – двоичная арифметика
- Стандарт ИСО С11