В компьютерном программировании целочисленное переполнение происходит, когда арифметическая операция над целыми числами пытается создать числовое значение, которое находится за пределами диапазона, который может быть представлен заданным количеством цифр — либо больше максимального, либо меньше минимального представимого значения.
Наиболее распространенным результатом переполнения является то, что наименее значимые представимые цифры результата сохраняются; говорят, что результат циклически обходит максимум (т. е. по модулю степени основания , обычно два в современных компьютерах, но иногда десять или другое число). На некоторых процессорах, таких как графические процессоры (GPU) и цифровые сигнальные процессоры (DSP), которые поддерживают арифметику насыщения , переполненные результаты будут ограничены , т. е. установлены на минимальное значение в представимом диапазоне, если результат ниже минимума, и установлены на максимальное значение в представимом диапазоне, если результат выше максимума, а не циклически обходят.
Для некоторых приложений, таких как таймеры и часы, перенос при переполнении может быть желательным. Стандарт C11 гласит, что для беззнаковых целых чисел перенос по модулю является определенным поведением, и термин «переполнение» никогда не применяется: «вычисление, включающее беззнаковые операнды, никогда не может переполниться». [1]
Ширина регистра процессора определяет диапазон значений, которые могут быть представлены в его регистрах. Хотя подавляющее большинство компьютеров может выполнять арифметику с множественной точностью над операндами в памяти, что позволяет числам быть произвольной длины и избегать переполнения, ширина регистра ограничивает размеры чисел, с которыми можно работать (например, складывать или вычитать) с использованием одной инструкции на операцию. Типичные ширины двоичных регистров для беззнаковых целых чисел включают:
Когда беззнаковая арифметическая операция дает результат, превышающий указанный выше максимум для N-битного целого числа, переполнение уменьшает результат до N-й степени числа 2 по модулю , сохраняя только наименее значимые биты результата и фактически вызывая циклический переход .
В частности, умножение или сложение двух целых чисел может привести к получению неожиданно малого значения, а вычитание из небольшого целого числа может привести к возврату к большому положительному значению (например, сложение 8-битных целых чисел 255 + 2 дает результат 1, что равно 257 mod 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 переполнение беззнаковых целых чисел определено как циклическое, в то время как переполнение знаковых целых чисел вызывает неопределенное поведение .
Реализация обнаружения переполнения во время выполнения 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 до Beta 1.7.3; позже она была исправлена в Beta 1.8. Та же ошибка существовала и в Minecraft Bedrock Edition, но с тех пор была исправлена. [28] [ ненадежный источник? ]
В игре Lamborghini American Challenge для Super Nintendo Entertainment System (SNES) игрок может сделать так, что его сумма денег упадет ниже 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]