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

Целочи́сленное переполне́ние (англ. integer overflow) — ситуация в компьютерной арифметике, при которой вычисленное в результате операции значение не может быть помещено в n-битный целочисленный тип данных. Различают переполнение через верхнюю границу представления и через нижнюю (англ. Underflow).

Пример: сложение двух переменных размером 8 бит с записью результата в переменную того же размера:

${\displaystyle 210_{10}+61_{10}=11010010_{2}+00111101_{2}=?}$

${\displaystyle {\begin{array}{c}{\begin{array}{cc}+&{\begin{array}{c}11010010_{2}\\00111101_{2}\end{array}}\\\end{array}}\\\hline {\begin{array}{cc}&{\color {Red}1}00001111_{2}\end{array}}\end{array}}}$

возникает переполнение.

При этом в результат записывается не ожидаемое ${\displaystyle 271_{10}={\color {Red}1}00001111_{2}}$, а ${\displaystyle 15_{10}=00001111_{2}}$. Вычисление здесь произошло по модулю 2ⁿ, а арифметика по модулю циклическая, то есть 255+1=0 (при n = 8). Данная ситуация переполнения фиксируется вычислительной машиной установкой специальных битов регистра флагов Overflow и Carry (пункт 3.4.3.1 Combined Volume: Volume 1^[1]). При программировании на языке ассемблера такую ситуацию можно напрямую установить, например, вручную проверив состояние регистра флагов после выполнения операции (пункт 7.3.13.2 Combined Volume: Volume 1^[1]).

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

Переполнение может возникнуть в исходном коде вследствие ошибки программиста или его недостаточной бдительности к входным данным^[2].

• Несоответствие знакового и беззнакового. Если числа представляются на вычислителе в дополнительном коде, то одному потоку бит соответствуют различные числа. В 32-битной арифметике знаковому −1 соответствует беззнаковое 4294967295 (верхняя граница представления). То есть приведение одного типа к другому может привести к значительной разнице в значении. Этот тип ошибки часто является последствием signedness error ( and), то есть неправильного приведения типов между типами разной знаковости
• Проблема срезки. Возникает, если число интерпретируется как целое меньшей длины. В таком случае только младшие биты останутся в числе. Старшие отбросятся, что приведет к изменению численного значения
• Знаковое расширение. Стоит помнить, что при приведении знакового числа к типу большей длины происходит копирование старшего бита, что в случае интерпретации как беззнаковое приведет к получению очень большого числа^[3]

Возможность переполнения широко используется программистами, например, для хеширования и криптографии, генерирования случайных чисел и нахождения границ представления типа^[4]. В то же время, например, по стандарту языков C и C++, беззнаковые вычисления выполняются по модулю 2, в то время как знаковое переполнение является классическим примером^[5] неопределённого поведения^[6].

Такой вид некорректности в коде ведёт к следующим последствиям^[4]:

1. Компиляция может пойти неожиданным образом. Из-за наличия неопределённого поведения в программе, оптимизации компилятора могут изменить поведение программы.
2. Бомба замедленного действия. На текущей версии ОС, компилятора, опций компиляции, структурной организации программы и т. д. всё может работать, а при любом изменении, например, появлении более агрессивных оптимизаций, сломаться.
3. Иллюзия предсказуемости. Конкретная конфигурация компилятора может иметь вполне определённое поведение, например компиляторы языков C и C++ обычно реализуют операции по модулю 2ⁿ и для знаковых типов (только интерпретированных в дополнительном коде), если отключены агрессивные оптимизации. Однако, надеяться на такое поведение нельзя, иначе есть риск эффекта «бомбы замедленного действия»
4. Образование диалектов. Некоторые компиляторы предоставляют дополнительные опции для того, чтобы доопределить неопределённое поведение. Например, и GCC, и Clang поддерживают опцию -fwrapv, обеспечивающую выше описанное (в пункте 3) поведение.

Изменение стандарта может привести к новым проблемам с переполнением. К примеру, 1<<31 было зависимым от реализации в стандартах ANSI C и C++98, в то время как стали неопределённым в C99 и C11 (для 32-битных целых).^[4]

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

Основные последствия для безопасности^[7]:

• Для доступности. Возможный отказ системы (окно для DoS-атак)
• Для целостности. Неавторизированный доступ к данным
• Для конфиденциальности. Исполнение стороннего кода, обход защитного механизма

Классически переполнение может быть эксплуатировано через переполнение буфера.

img_t* table_ptr; /*struct containing img data, 10kB each*/
int num_imgs;
...
num_imgs = get_num_imgs();
table_ptr = (img_t*)malloc(sizeof(img_t)*num_imgs);
...

Данный пример^[7] иллюстрирует сразу несколько уязвимостей. Во-первых, слишком большой num_imgs приведёт к выделению огромного буфера, из-за чего программа может потребить все ресурсы системы или вызвать её крах.

Другая уязвимость в том, что если num_imgs ещё больше, это приведёт к переполнению аргумента malloc. Тогда выделится лишь небольшой буфер. При записи в него произойдёт переполнение буфера, последствиями чего могут стать: перехват контроля над исполнением, исполнение кода злоумышленника, доступ к важной информации.^[8]

Защита от подобного поведения должна проводиться на нескольких уровнях^[7]:

1. Планирования и требований к программе:
   • Убедитесь, что все протоколы взаимодействия между компонентами строго определены. В том числе, что все вычисления вне границ представления будут обнаружены. И требуйте строгого соответствия этим протоколам.
   • Используйте язык программирования и компилятор, которые не позволяет этой уязвимости воплотиться, либо позволяют легче её обнаружить, либо выполняют авто-проверку границ. Инструменты, которые предоставляются компилятором, включают санитайзеры (например, Address Sanitizer^[англ.] или Undefined Behavior Sanitizer).
2. Архитектуры программы:
   • Используйте проверенные библиотеки или фреймворки, помогающие проводить вычисления без риска непредсказуемых последствий. Примеры включают такие библиотеки, как SafeInt (C++) или IntegerLib (C или C++).
   • Любые проверки безопасности на стороне клиента должны быть продублированы на стороне сервера, чтобы не допустить CWE-602. Злоумышленник может миновать проверку на стороне клиента, изменив сами значения непосредственно после прохождения проверки или модифицируя клиента, чтобы полностью убрать проверки.
3. Реализации:
   • Проводите валидацию любых поступивших извне числовых данных, проверяя что они находятся внутри ожидаемого диапазона. Проверяйте обязательно как минимальный порог, так и максимальный. Используйте беззнаковые числа, где это возможно. Это упростит проверки на переполнение.
   • Исследуйте все необходимые нюансы языка программирования, связанные с численными вычислениями (CWE-681). Как они представляются, какие различия между знаковыми и беззнаковыми, 32-битными и 64-битными, проблемы при кастовании (обрезка, знаково-беззнаковое приведения типов — выше) и как обрабатываются числа, слишком маленькие или, наоборот, большие для их машинного представления. Также убедитесь, что используемый вами тип (например, int или long) покрывают необходимый диапазон представления
   • Подробно изучите полученные от компилятора предупреждения и устраните возможные проблемы безопасности, такие как несоответствия знаковости операндов при операциях с памятью или использование неинициализированных переменных. Даже если уязвимость совсем небольшая, это может привести к опасности для всей системы.

Другие правила, позволяющие избежать этих уязвимостей, опубликованы в стандарте CERT C Secure Coding Standard в 2008 году, включают^[9]:

• Не пишите и не используйте функции обработки строкового ввода, если они обрабатывают не все случаи
• Не используйте битовые операции над знаковыми типами
• Вычисляйте выражения на типе большего размера перед сравнением или присваиванием в меньший
• Будьте внимательны перед приведением типа между числом и указателем
• Убедитесь, что вычисления по модулю или результаты деления не приводят к последующему делению на ноль
• Используйте intmax_t или uintmax_t для форматированного ввода-вывода пользовательских числовых типов

В статье^[4] в качестве предмета исследования программ на языках C и C++ на целочисленное переполнение подробно исследуется один из самых широко применимых и известных тестовых пакетов SPEC, используемый для измерений производительности. Состоит он из фрагментов наиболее распространённых задач, как то: тестов вычислительной математики, компиляции, работы с базами данных, диском, сетью и прочее.

Результаты анализа SPECCINT2000 показывают наличие 219 статических источников переполнения в 8 из 12 бенчмарков, из которых 148 использовали беззнаковое переполнение и 71 — знаковое (снова неопределённое поведение). В то же время, беззнаковое переполнение тоже не всегда намеренное и может являться ошибкой и источником уязвимости (например, Listing 2 той же статьи^[4]).

Также был проведён тест на «бомбы замедленного действия» в SPECCINT2006. Его идеей является в каждом месте неопределённого поведения вернуть случайное число и посмотреть, к каким последствиям это может привести. Если оценивать неопределённое поведение с точки зрения стандарта C99/C++11, то тест не пройдут целых 6 бенчмарков из 9.

int addsi (int lhs, int rhs) {
    errno = 0;
    if (((( lhs+rhs)^lhs)&(( lhs+rhs)^rhs)) >> (sizeof(int)*CHAR_BIT -1)) {
        error_handler("OVERFLOW ERROR", NULL, EOVERFLOW);
        errno = EINVAL;
    }
    return lhs + rhs;
}

Данный фрагмент кода^[4] из пакета IntegerLib проверяет, могут ли быть lhs и rhs сложены без переполнения. И ровно в строчке 3 это переполнение может возникнуть (при сложении lhs+rhs). Это UB, так как lhs и rhs — знакового типа. Кроме этого, в данной библиотеке найдено ещё 19 UB-переполнений.

Также авторы сообщили разработчикам о 13 переполнениях в SQLite, 43 в SafeInt, 6 в GNU MPC library, 30 в PHP, 18 в Firefox, 71 в GCC, 29 в PostgreSQL, 5 в LLVM и 28 в Python. Большинство из ошибок были вскоре исправлены.

Известный пример целочисленного переполнения происходит в игре Pac-Man и его прямых продолжениях (Ms. Pac-Man, Jr. Pac-Man и др.)^[10]. В случае Pac Man переполнение переменной, отвечающей за номер уровня, приводило к «экрану смерти», в котором половина отображаемой картинки выглядела нечитаемой, а сама игра становилась непроходимой.

Такая же проблема якобы была в игре Sid Meier's Civilization и известна как Ядерный Ганди^[11]. Согласно легенде, на определённом этапе игры с очень миролюбивым Ганди, происходит «переполнение через 0» уровня враждебности, результатом чего может стать ядерная война с Ганди. На самом деле, такой миф появился лишь с выходом Civilization V, где параметр его искусственного интеллекта, регулирующий создание и использование ядерного вооружения, имеет наивысшее значение 12, что не противоречило тому, что Ганди является одним из самых миролюбивых лидеров в игре^[12].

Ещё одним примером является глюк в SimCity 2000^[13]: если сумма денег на счету игрока превысит 2³¹, она станет отрицательной, что приведет к поражению. Похожая проблема была в Diablo III, в которой одним из обновлений был повышен лимит максимальной суммы сделок. Если сумма превышала 2³¹, то игрок после завершения сделки оставался с прибылью в 2³² игровой валюты^[14]

• Переполнение буфера
• Переполнение стека