Целочисленное переполнение

Целочисленное переполнение возникает, когда результат арифметической операции не укладывается в диапазон, представимый заданным количеством разрядов. В программировании используются, как правило, двоичные целые числа, однако переполнение возможно в любой позиционной системе счисления с ограниченным количеством знаков. Например, для шестиразрядной десятичной системы: 999999 + 1 приведёт к невозможному результату. Аналогично, для четырёхразрядной двоичной — 1111 + 1 также приведёт к выходу за границы. В обоих случаях требуется дополнительный разряд для представления результата, но он отсутствует.

Во всех средах программирования целые числа ограничены максимальным и минимальным значением, определяемым шириной разрядности и признаком знаковости (signed/unsigned). Стандартный тип целого числа зависит от платформы и используемого языка программирования. Кроме стандартных существуют целые с уменьшенной ([short]) или увеличенной ([long]) разрядностью. Также применяются целые с произвольной точностью (англ. arbitrary-precision), ограниченные предустановленной точностью или объёмом памяти.

Большинство АЛУ аппаратно работают с беззнаковыми числами. Для поддержки отрицательных чисел используется абстракция знакового типа, чаще всего — представление в дополнительном коде (two's complement). Например, знаковое 32-битное целое использует старший бит для знака, а остальные 31 бит — для значения числа. Если при операции происходит перенос выше 31-го бита, знак затирается, и получается переполнение; аппаратное устройство не контролирует это — обнаружение и обработка переполнения остаётся на уровне программы.

При использовании беззнаковых целых максимальной ширины АЛУ, результат не может быть шире регистра; АЛУ при этом устанавливает флаг переноса. При установленном флаге программа может распознать факт переполнения.

Обработка переполнения требует специальной логики: если результат оказался повреждён, могут возникать дополнительные ошибки в вычислениях.

Использование операций над целыми, совпадающими по разрядности с АЛУ, как правило, наиболее производительно. Для работы с числовыми типами, превышающими разрядность регистра, применяются расширения SIMD, например SSE2 для 64-битных операций на x86, AVX — до 512 бит^[1].

Когда результат беззнаковой операции превышает максимальное значение для N-битного целого, происходит переполнение — результат выражается по модулю 2^N, «оборачивается», остаются только младшие биты.

Например, при сложении 8-битных чисел: 255 + 2 = 1 (так как 257 mod 256 = 1), а 0 − 1 = 255 (что в дополнительном коде соответствует −1).

Оборачиваемое переполнение может приводить к проблемам безопасности: если переполненное значение используется как размер выделяемого буфера, выделяется меньший буфер, что может привести к переполнению буфера и выполнению произвольного кода.

Если для переменной используется знаковый тип, программа может предполагать всегда положительное значение. Переполнение может привести к переходу в область отрицательных чисел, нарушая предположения, что способствует ошибкам. Например, 127 + 1 = −128 для 8-битного знакового. Для предотвращения таких ошибок рекомендуется использовать беззнаковые типы для значений, которые не должны быть отрицательными.

Большинство процессоров имеют два флага для контроля переполнения.

Флаг переноса (carry flag) устанавливается, если результат сложения или вычитания (для беззнаковых чисел) не укладывается в указанный битовый разряд — это указывает на переполнение с переносом или заимствованием из старшего бита. Этот флаг используется при выполнении многоразрядных сложений по частям.

Флаг переполнения (overflow flag) выставляется, если результат операции над знаковыми числами не соответствует ожидаемому знаку (например, отрицательный результат при сложении двух положительных чисел), что сигнализирует о переполнении диапазона знаковых чисел.

Для беззнаковых типов часто термин «переполнение» употребляют по отношению к оборачиванию результата, однако стандарт C11 указывает, что для беззнаковых типов это не переполнение^[28].

Если результат операции ограничивается пределами (насыщающая арифметика), такое событие называют насыщением. Для уточнения рекомендуется использовать термины «оборачиваемое переполнение» (англ. wrapping overflow)^[29] и «насыщающее переполнение» (англ. saturating overflow)^[30].

Термин «целочисленное недополнение» некорректен: переполнение связано только с границей по разрядам, а не со знаком числа. Хотя в литературе встречается термин integer underflow, он не имеет строгого основания, правильнее говорить о переполнении, выходе за границы массива или ошибках приведения типов.^{[31][32][33][34]} Истинное арифметическое недополнение возможно только для операций с плавающей запятой.

При преобразованиях типов и операциях с пограничными случаями, термин переполнение может быть неоднозначен. Например, преобразование числа 127,25 в тип с максимумом 127: при округлении к нулю результат может не считаться переполнением по стандарту C11^[28].

Поведение при переполнении зависит от языка и обстоятельств. Например, в языке Rust оно различается между сборкой в режиме отладки и релиза^[35]. В C переполнение беззнаковых целых приводит к оборачиванию, для знаковых — к неопределённому поведению.

Для обнаружения переполнения во время выполнения применяются, например, средства UBSan в компиляторах C.

В Java 8 реализованы перегруженные методы, такие как англ. addExact(int, int), которые возбуждают исключение англ. ArithmeticException при переполнении.

Компьютерная команда реагирования на инциденты CERT разработала модель AIR (As-if Infinitely Ranged) для автоматической ликвидации переполнений и усечения целых в C/C++ посредством обработки ошибок во время выполнения^[38].

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

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

В аппаратуре поддерживается обработка многобайтовых операций с контролем флагов переноса (многоточечная арифметика).

Обработка переполнения может осуществляться как до вычисления (проверка возможности возникновения), так и после (анализ результата на допустимость). Для переносимости предпочтительно тестировать заранее.

В некоторых языках (например Ada) и функциональных системах по умолчанию возбуждается исключение при переполнении, в других (например Python с версии 2.4) используется динамическое расширение числа до long.

Языки с поддержкой арифметики произвольной точности и безопасностью типов (Python, Smalltalk, Common Lisp) автоматически увеличивают разрядность при необходимости, либо возбуждают исключения. Однако целочисленное переполнение может возникать и здесь — при явной оптимизации критичных блоков кода, например, аннотируя переменную как fixnum (машинное целое) в Common Lisp^{[39][40][41][42][43][44]}.

Современные языки, такие как Rust, предоставляют функции для явного управления обработкой переполнения (checked/unchecked/wrapping/saturating операции).

В компьютерной графике и обработке сигналов часто используются данные в диапазоне от 0 до 1 или от −1 до 1 (например, оттенки серого). Насыщающая арифметика позволяет автоматически ограничить яркость или координату до предельно допустимого значения, вместо оборачивания результата.

Неожиданное арифметическое переполнение — типичная причина программных ошибок. Такие баги могут долго не замечаться, так как проявляются лишь при больших значениях данных.

Пример: вычисление среднего двух чисел как (a+b)/2 может привести к переполнению суммы даже при допустимом результате среднего^[45].

В 1985–1987 годах ошибка переполнения в медицинских аппаратах Therac-25 приведла к гибели шести пациентов из-за передозировки облучения^[46].

Переполнение стало причиной аварии ракеты Ariane 5 в 1996 году: необработанное переполнение в коде управления двигателями привело к крушению носителя^[47]. Программный модуль, вызвавший ошибку, даже не требовался для данного запуска — он был унаследован от предыдущей версии программного обеспечения. Диагностический дамп, вызванный ошибкой переполнения, напрямую управлял исполнительным устройством, вызывая потерю управляемости ракеты.

В апреле 2015 года Федеральное управление гражданской авиации США предписало операторам Boeing 787 периодически перезагружать электросистему, чтобы избежать переполнения целочисленного счётчика, приводящего к потере питания; компания Boeing выпустила обновление ПО^[48][49]. Ошибка возникала после истечения 2³¹ сотых секунды (около 248 дней), что указывает на использование 32-битного знакового целого.

Переполнение встречается и в видеоиграх. В Super Mario Bros. счётчик жизней реализован как знаковый байт (от −128 до 127): при достижении 128 жизней происходит обнуление, что приводит к мгновенному завершению игры при следующей смерти. Аналогичные баги присутствовали в ряде классических игр (например, Donkey Kong, Pac-Man^[50], Minecraft^[51]).

IBM–Microsoft Macro Assembler (MASM) версии 1.00 и другие программы, скомпилированные с использованием того же Pascal-компилятора, имели ошибку переполнения и неверной интерпретации знака целого числа при инициализации стека, из-за чего не запускались на некоторых новых машинах с DOS и с большим объёмом памяти^[52].

В 2016 году в казино Resorts World из-за бага переполнения игровой автомат выдал выигрыш $42 949 672,76; после разбирательства комиссия признала это ошибкой программного обеспечения и аннулировала выигрыш, поскольку максимальная выплата была явно ограничена правилами^[53].