В компьютерном программировании переполнение целого числа происходит , когда арифметическая операция пытается создать числовое значение, находящееся за пределами диапазона, который может быть представлен заданным количеством цифр — либо выше максимального, либо ниже минимального представимого значения.
Наиболее распространенным результатом переполнения является сохранение наименее значимых представимых цифр результата; Говорят, что результат обертывается вокруг максимума (т.е. по модулю степени счисления , обычно двух в современных компьютерах, но иногда десяти или другого основания).
Состояние переполнения может привести к непредвиденному поведению. В частности, если такая возможность не была предусмотрена, переполнение может поставить под угрозу надежность и безопасность программы .
Для некоторых приложений, таких как таймеры и часы, может быть желательным перенос при переполнении. Стандарт C11 гласит, что для беззнаковых целых чисел перенос по модулю является определенным поведением, и термин «переполнение» никогда не применяется: «вычисление, включающее беззнаковые операнды, никогда не может переполниться». [1]
На некоторых процессорах, таких как графические процессоры (GPU) и процессоры цифровых сигналов (DSP), которые поддерживают арифметику насыщения , переполненные результаты будут «ограничены», т.е. установлены на минимальное или максимальное значение в представимом диапазоне, а не перевернуты.
Ширина регистра процессора определяет диапазон значений, которые могут быть представлены в его регистрах. Хотя подавляющее большинство компьютеров могут выполнять арифметические операции с множественной точностью над операндами в памяти, позволяя числам быть произвольной длины и избегать переполнения, ширина регистра ограничивает размеры чисел, с которыми можно работать (например, складывать или вычитать), используя одна инструкция на операцию. Типичные ширины двоичного регистра для беззнаковых целых чисел включают:
Когда беззнаковая арифметическая операция дает результат, превышающий указанный выше максимум для 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]
Назначая переменным типы данных, которые достаточно велики, чтобы содержать все значения, которые могут быть вычислены и сохранены в них, всегда можно избежать переполнения. Даже когда доступное пространство или фиксированные типы данных, предоставляемые языком программирования или средой, слишком ограничены, чтобы можно было безопасно выделить переменные больших размеров, тщательно упорядочивая операции и заранее проверяя операнды, часто можно заранее гарантировать что результат никогда не будет больше, чем можно сохранить. Инструменты статического анализа , формальная проверка и методы проектирования по контракту могут использоваться для более надежной и надежной гарантии того, что случайное переполнение не произойдет.
Если ожидается, что может произойти переполнение, то в программу можно вставить тесты, чтобы определить, когда это произойдет или вот-вот произойдет, и выполнить другую обработку для смягчения этого явления. Например, если важный результат, вычисленный в результате переполнения пользовательского ввода, программа может остановиться, отклонить ввод и, возможно, предложить пользователю ввести другой ввод, вместо того, чтобы программа продолжила работу с недопустимым переполненным вводом и, возможно, как следствие, дала сбой.
У процессоров обычно есть способ обнаружить это и поддержать сложение чисел, превышающих размер их регистра, обычно с использованием бита состояния. Этот метод называется арифметикой множественной точности. Таким образом, можно выполнять побайтовое сложение операндов шириной больше байта: сначала складывают младшие байты, сохраняют результат и проверяют на переполнение; затем добавьте старшие байты и, если необходимо, добавьте перенос из младших байтов, а затем сохраните результат.
Обработка возможного переполнения при вычислении иногда может представлять собой выбор между выполнением проверки перед вычислением (чтобы определить, произойдет ли переполнение) или после него (чтобы оценить вероятность того, что оно произошло, на основе результирующего значения). Поскольку некоторые реализации могут генерировать условие ловушки при переполнении целого числа, наиболее переносимые программы проверяют перед выполнением операции, которая может переполниться.
Если значение слишком велико для сохранения, ему можно присвоить специальное значение, указывающее, что произошло переполнение, а затем все последующие операции будут возвращать это значение флага. Такие значения иногда называют NaN , что означает «не число». Это полезно для того, чтобы проблему можно было проверить один раз в конце длительного расчета, а не после каждого шага. Это часто поддерживается в аппаратном обеспечении с плавающей запятой, называемом FPU .
Языки программирования реализуют различные методы предотвращения случайного переполнения: 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]
В игре 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]