Участник:HonorMan/Черновик

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

Представим, что у нас 8-битная беззнаковая арифметика. Может случится, что результатом выполнения операции должно стать число, не представимое в виде 8-битного целого. Например, умножение числа 200 на 2 даст 400, что находится за границами представления. Обычно, это означает, что будет произведено вычисление по модулю 2 и результат выйдет 145. Стоит отметить, что арифметика по модулю 2ⁿ циклическая, что иллюстрирует пример 255+1=0 (при n = 8). Данная ситуация фиксируется вычислительной машиной установкой специальных битов регистра флагов Overflow и Carry. При программировании на языке ассемблера такую ситуацию можно напрямую установить.

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

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

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

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

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

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

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

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

• Для доступности. Возможный отказ системы (окно для 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);...

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

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

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

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

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

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

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

Также был проведен тест на "бомбы замедленного действия" в 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;}

Данный фрагмент кода^[2] из пакета 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. Также этот глюк появляется в Pac-Man Google Doodle в качестве так называемого "пасхального яйца".^[6] Здесь же на уровне 256 можно наблюдать "экран смерти", а сам уровень называют "уровнем разделенного экрана". Энтузиасты дизассемблировали исходный код, пытаясь исправить ошибку модифицированием игры.

Такая же проблема появляется в игре Civilization 4 и известна как Nuclear Gandhi^[7]. Дело в том, что после заключения партнерских соглашений с очень миролюбивым Ганди, происходит переполнение через 0 уровня враждебности, результатом чего может стать ядерная война с Ганди.

Еще одним примером является глюк в SimCity2000^[8]. Здесь дело в том, что бюджет игрока стал очень большим, а после перехода через 2³¹ внезапно стал отрицательным. Игра оканчивается поражением.

Этот глюк из Diablo 3. Из-за одного из изменений патча 1.0.8, игровая экономика сломалась. Максимальную сумму для сделок повысили с 1 млн до 10 млн. Стоимость покупки переполнялась через 32-битный тип, а при отмене операции возвращалась полная сумма. То есть игрок оставался с прибылью в 2³² игровой валюты^[9]