Переполнение в компьютерной арифметике

Введение

Ошибка компьютерной арифметики

В компьютерном программировании переполнение целых чисел происходит, когда арифметическая операция пытается создать числовое значение, выходящее за пределы диапазона, который может быть представлен заданным количеством цифр – либо превышающее максимальное, либо опускающееся ниже минимального представимого значения. Наиболее распространенным результатом переполнения является сохранение младших значащих цифр результата; говорят, что результат циклически переходит через максимальное значение (то есть вычисляется по модулю степени основания системы счисления, обычно двойки в современных компьютерах, но иногда десятки или другое основание). Состояние переполнения может приводить к нежелательному поведению. В частности, если эта возможность не была учтена, переполнение может скомпрометировать надежность и безопасность программы. Для некоторых приложений, таких как таймеры и часы, циклическое переполнение может быть желательным. Стандарт C11 утверждает, что для беззнаковых целых чисел модульное завершение является определенным поведением, и термин "переполнение" неприменим: "вычисление с использованием беззнаковых операндов никогда не может привести к переполнению". На некоторых процессорах, таких как графические процессоры (GPU) и цифровые сигнальные процессоры (DSP), поддерживающих арифметику насыщения, переполненные результаты будут "ограничены", то есть установлены на минимальное или максимальное значение в представимом диапазоне, а не циклически перенесены.

Флаги

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

Вариации определения и двусмысленность

Для неподписанного типа, когда идеальный результат операции выходит за пределы представляемого диапазона типа, а возвращаемый результат получается путем переполнения, такое событие обычно определяется как переполнение. В отличие от этого, стандарт C11 определяет, что это событие не является переполнением, и утверждает: "вычисление с использованием неподписанных операндов никогда не может вызвать переполнение", и может использоваться насыщающееся переполнение. Часто встречаются упоминания о целочисленном истоке (underflow). Когда используется термин "целочисленный исток", это означает, что идеальный результат был ближе к отрицательной бесконечности, чем минимальное представимое значение типа результата. В зависимости от контекста, определение переполнения может включать все типы, включая исток, или только случаи, когда идеальный результат был ближе к положительной бесконечности, чем максимальное представимое значение типа результата. Когда идеальный результат операции не является целым числом, значение переполнения может быть неоднозначным в граничных случаях. Например, если идеальный результат равен 127,25, а максимальное представимое значение типа результата равно 127, то, если переполнение определяется как выход идеального значения за пределы представляемого диапазона типа результата, этот случай будет классифицирован как переполнение. Для операций с чётко определённым поведением округления классификацию переполнения может потребоваться отложить до применения округления. В стандарте C11 в языке C переполнение неподписанных целых чисел определяется как циклическое, а переполнение знаковых целых чисел приводит к неопределённому поведению.

Методы решения проблем переполнения целых чисел

+ Обработка переполнения целых чисел в различных языках программирования
Язык Неподписанное целое число Подписанное целое число
Ada остаток от деления на модуль типа вызов ошибки Constraint Error
C, C++ остаток от деления на степень двойки неопределенное поведение
C# остаток от деления на степень 2 в неконтролируемом контексте; System.OverflowException генерируется в контролируемом контексте
Java остаток от деления на степень двойки (char – единственный неподписанный примитивный тип в Java) остаток от деления на степень двойки
JavaScript все числа – числа с плавающей точкой двойной точности, за исключением BigInt
MATLAB встроенные целые числа насыщаются. Целые числа с фиксированной точкой могут быть настроены на обертывание или насыщение
Python 2 преобразование в тип long (bigint)
Seed7 вызов ошибки OVERFLOW ERROR
Scheme преобразование в bigNum
Simulink может быть настроен на обертывание или насыщение
Smalltalk преобразование в LargeInteger
Swift вызывает ошибку, если не используются специальные операторы переполнения.

Обнаружение

Реализация обнаружения переполнения во время выполнения UBSan (санитайзер неопределенного поведения) доступна для C-компиляторов. В Java 8 существуют перегруженные методы, например, которые выбрасывают исключение в случае переполнения. Команда реагирования на компьютерные инциденты (CERT) разработала модель целых чисел с бесконечным диапазоном (AIR) – во многом автоматизированный механизм для устранения переполнения и усечения целых чисел в C/C++ с использованием обработки ошибок во время выполнения.

Избегание

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

Обработка

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

Явное размножение

Если значение слишком велико для хранения, ему может быть присвоено специальное значение, указывающее на переполнение, и все последующие операции будут возвращать это значение как флаг. Такие значения иногда называют NaN (Not a Number – «не число»). Это позволяет проверить наличие проблемы один раз в конце сложного вычисления, а не после каждого шага. Такая поддержка часто реализована в аппаратном обеспечении для работы с числами с плавающей точкой, называемом FPU.

Поддержка языков программирования

Языки программирования реализуют различные методы смягчения случайного переполнения: Ada, Seed7 и некоторые варианты функциональных языков генерируют исключение при переполнении, в то время как Python (начиная с версии 2.4) плавно преобразует внутреннее представление числа, чтобы соответствовать его росту, в конечном итоге представляя его как long, чьи возможности ограничены только доступной памятью. В языках с нативной поддержкой арифметики произвольной точности и типобезопасности (таких как Python, Smalltalk или Common Lisp) числа автоматически приводятся к большему размеру при переполнении, либо генерируются исключения (сигнализируются условия), если существует ограничение диапазона. Использование таких языков может помочь смягчить эту проблему. Однако в некоторых таких языках все еще возможны ситуации, когда может произойти переполнение целых чисел. Примером может служить явная оптимизация участка кода, который профилировщик выявляет как узкое место. В случае Common Lisp это возможно путем использования явного объявления для аннотирования типа переменной как "машинное слово" (fixnum) и понижения уровня типобезопасности до нуля для конкретного блока кода. В резком контрасте со старыми языками, такими как C, некоторые новые языки, такие как Rust, предоставляют встроенные функции, позволяющие легко обнаруживать переполнение и предоставлять пользователю возможность выбора способа его обработки в каждом конкретном случае. В Rust, хотя использование базовых математических операторов не обладает такой гибкостью, пользователи могут выполнять вычисления альтернативно, используя набор методов, предоставляемых каждым из примитивных целочисленных типов. Эти методы предоставляют пользователям несколько вариантов: выполнение проверочной (или переполняющейся) операции (которая указывает, произошло ли переполнение через тип возвращаемого значения); "непроверяемая" операция; операция, выполняющая перенос, или операция, выполняющая насыщение на числовых границах.

Насыщенная арифметика

В компьютерной графике или обработке сигналов обычно работают с данными, значения которых находятся в диапазоне от 0 до 1 или от -1 до 1. Например, рассмотрим градации серого изображения, где 0 соответствует черному цвету, 1 – белому, а промежуточные значения – оттенкам серого. Одной из операций, которую может потребоваться реализовать, является повышение яркости изображения путем умножения каждого пикселя на константу. Насыщенная арифметика позволяет просто умножать каждый пиксель на эту константу, не беспокоясь о переполнении, поскольку значения, превышающие 1 (то есть "ярче белого"), просто становятся белыми, а значения, меньшие 0 ("темнее черного") – черными.

Примеры

Непредвиденное арифметическое переполнение является довольно распространенной причиной ошибок в программах. Такие ошибки переполнения бывает трудно обнаружить и диагностировать, поскольку они могут проявляться только при обработке очень больших наборов входных данных, которые реже используются в ходе валидационных тестов. Вычисление среднего арифметического двух чисел путем их сложения и деления на два, как это делается во многих поисковых алгоритмах, приводит к ошибке, если сумма (хотя и не полученное среднее) слишком велика для представления и, следовательно, происходит переполнение. В период с 1985 по 1987 год арифметическое переполнение в аппаратах для лучевой терапии Therac 25, а также отсутствие аппаратных средств обеспечения безопасности, привели к смерти как минимум шести человек в результате передозировки радиации. Необработанное арифметическое переполнение в программном обеспечении управления двигателем стало основной причиной крушения первого полета ракеты Ariane 5 в 1996 году. Программное обеспечение считалось безошибочным, поскольку оно использовалось во многих предыдущих полетах, но те полеты осуществлялись с использованием меньших ракет, которые создавали меньшее ускорение, чем у Ariane 5. Парадоксально, но часть программного обеспечения, в которой произошла ошибка переполнения, даже не должна была работать для Ariane 5 в момент, когда она привела к аварии ракеты: это был процесс запуска для меньшего предшественника Ariane 5, который остался в программном обеспечении при его адаптации для новой ракеты. Более того, истинной причиной аварии был дефект в технической спецификации, определяющей, как программное обеспечение обрабатывает переполнение при его обнаружении: оно выполняло диагностическую дампинг в свою шину, которая во время разработки программного обеспечения была подключена к тестовому оборудованию, но во время полета была подключена к двигателям управления ракетой; дампинг данных резко отклонил сопло двигателя в сторону, что вывело ракету из-под аэродинамического контроля и привело к ее быстрому разрушению в воздухе. 30 апреля 2015 года Федеральное управление гражданской авиации США объявило о приказе операторам Boeing 787 периодически перезагружать электрическую систему, чтобы избежать переполнения целого числа, которое может привести к потере электроэнергии и активации ветряной турбины, а Boeing выпустил обновление программного обеспечения в четвертом квартале. Европейское агентство по авиационной безопасности последовало этому примеру 4 мая 2015 года. Ошибка возникает через 231 сотую секунды (около дней), что указывает на 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. Такая ошибка также вызвала Far Lands в Minecraft Java Edition, которые существовали с периода разработки Infdev до бета-версии 1.7.3; позже она была исправлена в бета-версии 1.8. Та же ошибка также существовала в Minecraft Bedrock Edition, но с тех пор была исправлена. В игре Lamborghini American Challenge для Super Nintendo Entertainment System (SNES) игрок может заставить сумму денег упасть ниже $0 во время гонки, будучи оштрафованным на сумму, превышающую остаток денег после оплаты гоночного взноса, что приводит к сбою целого числа и дает игроку $65 535 000 больше, чем он имел бы после ухода в минус. IBM–Microsoft Macro Assembler (MASM) версии 1.00 и, вероятно, все другие программы, созданные тем же компилятором Pascal, имели переполнение целого числа и ошибку знаковости в коде настройки стека, что не позволяло им работать на новых машинах DOS или эмуляторах в некоторых распространенных конфигурациях с более чем 512 КБ памяти. Программа либо зависает, либо отображает сообщение об ошибке и выходит в DOS. В августе 2016 года игровой автомат в казино Resorts World выдал выигрышный билет на сумму $42 949 672,76 в результате ошибки переполнения. Казино отказалось выплачивать эту сумму, назвав ее неисправностью, и в качестве защиты использовало тот факт, что на автомате четко указано, что максимальный выигрыш составляет $10 000, поэтому любой выигрыш, превышающий эту сумму, должен быть результатом программной ошибки. Комиссия по азартным играм штата Нью-Йорк вынесла решение в пользу казино.

Unanticipated arithmetic overflow is a fairly common cause of program errors. Such overflow bugs may be hard to discover and diagnose because they may manifest themselves only for very large input data sets, which are less likely to be used in validation tests. Taking the arithmetic mean of two numbers by adding them and dividing by two, as done in many search algorithms, causes error if the sum (although not the resulting mean) is too large to be represented and hence overflows. Between 1985 and 1987, arithmetic overflow in the Therac 25 radiation therapy machines, along with a lack of hardware safety controls, caused the death of at least six people from radiation overdoses. An unhandled arithmetic overflow in the engine steering software was the primary cause of the crash of the 1996 maiden flight of the Ariane 5 rocket. The software had been considered bug free since it had been used in many previous flights, but those used smaller rockets which generated lower acceleration than Ariane 5. Frustratingly, the part of the software in which the overflow error occurred was not even required to be running for the Ariane 5 at the time that it caused the rocket to fail: it was a launch regime process for a smaller predecessor of the Ariane 5 that had remained in the software when it was adapted for the new rocket. Further, the true cause of the failure was a flaw in the engineering specification of how the software dealt with the overflow when it was detected: it did a diagnostic dump to its bus, which would have been connected to test equipment during software testing during development but was connected to the rocket steering motors during flight; the data dump drove the engine nozzle hard to one side which put the rocket out of aerodynamic control and precipitated its rapid breakup in the air. On 30 April 2015, the U. S. Federal Aviation Administration announced it will order Boeing 787 operators to reset its electrical system periodically, to avoid an integer overflow which could lead to loss of electrical power and ram air turbine deployment, and Boeing deployed a software update in the fourth quarter. The European Aviation Safety Agency followed on 4 May 2015. The error happens after 231 hundredths of a second (about days), indicating a 32 bit signed integer. Overflow bugs are evident in some computer games. In Super Mario Bros. for the NES, the stored number of lives is a signed byte (ranging from −128 to 127) meaning the player can safely have 127 lives, but when the player reaches their 128th life, the counter rolls over to zero lives (although the number counter is glitched before this happens) and stops keeping count. As such, if the player then dies it's an immediate game over. This is caused by the game's data overflow that was an error of programming as the developers may not have thought said number of lives could be earned. In the arcade game Donkey Kong, it is impossible to advance past level 22 due to an integer overflow in its time/bonus. The game calculates the time/bonus by taking the level number a user is on, multiplying it by 10, and adding 40. When they reach level 22, the time/bonus number is 260, which is too large for its 8 bit 256 value register, so it overflows to a value of 4 – too short to finish the level. In Donkey Kong Jr. Math, when trying to calculate a number over 10,000, it shows only the first 4 digits. Overflow is the cause of the famous "split screen" level in Pac Man. Such a bug also caused the Far Lands in Minecraft Java Edition which existed from the Infdev development period to Beta 1.7.3; it was later fixed in Beta 1.8. The same bug also existed in Minecraft Bedrock Edition but has since been fixed. In the Super Nintendo Entertainment System (SNES) game Lamborghini American Challenge, the player can cause their amount of money to drop below $0 during a race by being fined over the limit of remaining money after paying the fee for a race, which glitches the integer and grants the player $65,535,000 more than it would have had after going negative. IBM–Microsoft Macro Assembler (MASM) version 1.00, and likely all other programs built by the same Pascal compiler, had an integer overflow and signedness error in the stack setup code, which prevented them from running on newer DOS machines or emulators under some common configurations with more than 512 KB of memory. The program either hangs or displays an error message and exits to DOS. In August 2016, a casino machine at Resorts World casino printed a prize ticket of $42,949,672.76 as a result of an overflow bug. The casino refused to pay this amount, calling it a malfunction, using in their defense that the machine clearly stated that the maximum payout was $10,000, so any prize exceeding that had to be the result of a programming bug. The New York State Gaming Commission ruled in favor of the casino.