WikiSort.ru - Не сортированное

Целочи́сленное переполне́ние (англ. 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 and 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 or C++).
   • Любые проверки безопасности на стороне клиента должны быть продублированы на стороне сервера, чтобы не допустить CWE-602. Злоумышленник может миновать проверку на стороне клиента, изменив сами значения непосредственно после прохождения проверки или модифицируя клиента, чтобы полностью убрать проверки.
3. Реализации:
   • Проводите валидацию любых поступивших извне числовых данных, проверяя что они находятся внутри ожидаемого диапазона. Проверяйте обязательно как минимальный порог, так и максимальный. Используйте беззнаковые числа, где это возможно. Это упростит проверки на переполнение.
   • Исследуйте все необходимые нюансы языка программирования, связанные с численными вычислениями (CWE-681). Как они представляются, какие различия между знаковыми и беззнаковыми, 32-битными и 64-битными, проблемы при кастовании (обрезка, знаково-беззнаковое приведения типов — выше) и как обрабатываются числа, слишком маленькие или, наоборот, большие для их машинного представления. Также убедитесь, что используемый вами тип (например, int или long) покрывают необходимый диапазон представления
   • Подробно изучите полученные от компилятора предупреждения и устраните возможные проблемы безопасности, такие как несоответствия знаковости операндов при операциях с памятью или использование неинициализированных переменных. Даже если уязвимость совсем небольшая, это может привести к опасности для всей системы.

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

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

Примеры из жизни

1 int  addsi (int lhs , int  rhs) {
2     errno = 0;
3     if (((( lhs+rhs)^lhs)&(( lhs+rhs)^rhs))
4     >> (sizeof(int)*CHAR_BIT -1)) {
5         error_handler("OVERFLOW  ERROR", NULL , EOVERFLOW);
6         errno = EINVAL;
7     }
8     return  lhs+rhs;
9 }

См. также

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

Примечания