Часто в контексте безопасного программирования упоминают проблему целочисленног
переполнения (integer overflow). А возможно ли отловить эту ситуацию в C/C++ коде? Вед
процессоры (по крайней мере x86) имеют среди EFLAGS флаг Overflow Flag, получается
что чисто технически такая возможность имеется, да и оверхэд на проверку флага в регистре не должен быть большим (думается так). Либо проблема в постановке вопроса и переполнение нужно не отлавливать, а не допускать никогда? Значит ли последнее, что целочисленные типы принципиально не подходят для любых вычислений?
P.S. Вопрос возник в связи с тем, что в существующем коде (наблюдаемом мной) широк
используется int для арифметических расчетов и ничто не защищает от переполнений, гипотетически они могут остаться незамеченными (логикой). И в большинстве случаев с большой вероятностью все в норме (реальные значения невелики), но иногда...
Ответы
Ответ 1
Официально в стандарте языка записано, если я не путаю, что переполнение знаковы
целочисленных типов зависит от реализации (может генерироваться исключение, может игнорироваться), а беззнаковых игнорируется - значение приводится в представимый диапазон.
Т.е. получается примерно так - сам C/C++ встроенных переносимых средств обнаружения переполнения не имеет.
Но всегда можно использовать дополнительные методы, которые позволят по данным операнда
выяснить, будет ли переполнение при выполнении операции. Масса таких вещей описана в книге Г. Уоррена Алгоритмические трюки для программистов.
Ну и как иллюстрация, насколько легко пропустить это переполнение - у Страуструп
в Программирование. Принципы и практика... есть одна программка, в которой вычислялс
ряд для ex, что ли - и она у него в разнос шла. Он честно написал, что раньше, мол, я думал, что это связано с потерей точности в double, и вроде даже так и написал в первом издании книги, а потом ко второму изданию дошло, что на самом деле это переполнение целочисленных значений при вычислении факториала. Если уж даже Страуструп... :)
Ответ 2
Действие по умолчанию зависит от процессора, компилятора и настроек. На MIPS, например
его "классические" компиляторы превращали сложение знаковых в команду add, которая генерируе
исключение при переполнении, а беззнаковых - addu, которая не генерирует. Но gcc, clang уже такого не делали, всё через addu. На x86 - родные команды add, sub игнорируют переполнение (точнее, ставят флаг CF или OF, но не генерируют исключение).
Компиляторы современного типа считают, что переполнения в операциях с целыми со знако
не должно быть, иногда из-за этого возникают интересные эффекты - вот самый убойны
пример из тех, что я видел. Стандарт тут действует по принципу "мы вам даём возможность писать максимально эффективно, потому что это C, а не учебный язык, а защита от кривостей - ваша проблема".
Для C++ есть, например, библиотечка (шаблонный заголовочный файл) SafeInt3 от Microsoft
под свободной лицензией; ею можно покрыть все основные операции, хотя она не использует специфику процессоров (даже x86) и оттого во многих случаях неэффективна - там, где достаточно одного OF или CF, она городит много сложных расчётов.
Для C придётся всё писать вручную, заменяя обычные операции на свои эквиваленты функциями или макросами.
UPDATE: про новые встроенные функции последних gcc и clang (__builtin_add_overflow
__builtin_mul_overflow и вся группа)уже писали. Но и без них можно сделать достаточно неплохо. Например, в случае сложения двух int, проверка вида a > INT_MAX - b, если b > 0, иначе a < INT_MIN - b, достаточна, чтобы проверить разрешимость сложения.
Ответ 3
Хоть и не приветствуются ответы только из ссылок, но вот нашел хороший материал (
т.ч. там код проверок, вызовет ли переполнение (более обще -- безопасно ли) сложение, вычитание, умножение и деление целых):
https://www.securecoding.cert.org/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow
с обсуждениями и т.п.
Update
Поскольку при поиске ответа всегда хочется сразу увидеть конкретный код, помогающи
в решении задачи (а не гадать, например, как правильно написать условие проверки для вычитания, уже зная правильный ответ для сложения), приведу тут некоторые из материалов по этой ссылке, которые можно использовать как образцы для своих программ.
Проверка перед сложением:
#include
void f(signed int si_a, signed int si_b) {
signed int sum;
if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
/* Handle error */
} else {
sum = si_a + si_b;
}
/* ... */
}
Проверка перед вычитанием:
#include
void func(signed int si_a, signed int si_b) {
signed int diff;
if ((si_b > 0 && si_a < INT_MIN + si_b) ||
(si_b < 0 && si_a > INT_MAX + si_b)) {
/* Handle error */
} else {
diff = si_a - si_b;
}
/* ... */
}
Проверка перед умножением:
#include
void func(signed int si_a, signed int si_b) {
signed int result;
if (si_a > 0) { /* si_a is positive */
if (si_b > 0) { /* si_a and si_b are positive */
if (si_a > (INT_MAX / si_b)) {
/* Handle error */
}
} else { /* si_a positive, si_b nonpositive */
if (si_b < (INT_MIN / si_a)) {
/* Handle error */
}
} /* si_a positive, si_b nonpositive */
} else { /* si_a is nonpositive */
if (si_b > 0) { /* si_a is nonpositive, si_b is positive */
if (si_a < (INT_MIN / si_b)) {
/* Handle error */
}
} else { /* si_a and si_b are nonpositive */
if ( (si_a != 0) && (si_b < (INT_MAX / si_a))) {
/* Handle error */
}
} /* End if si_a and si_b are nonpositive */
} /* End if si_a is nonpositive */
result = si_a * si_b;
}
Проверка перед делением:
(или вычислением остатка)
#include
void func(signed long s_a, signed long s_b) {
signed long result;
if ((s_b == 0) || ((s_a == LONG_MIN) && (s_b == -1))) {
/* Handle error */
} else {
result = s_a / s_b;
}
/* ... */
}
Ну, если кому не лень вытащить оттуда остальной (относящийся к вопросу ТС) код (
также описание всех существенных моментов) сюда и аккуратно его оформить, милости просим.
Ответ 4
Попробую резюмировать: легче избежать проблемы (продумав детально арифметику), чем потом ее (неприятно) обнаруживать и обрабатывать.
Решения с перехватом либо зависят от компилятора, либо представляют собой отказ о
непосредственно встроенных типов. Полагаю, подходящим решением (кроме работы с память
и коллекциями, разрешающими индексацию) может стать использование чисел с плавающей запятой, т.к. они более приближены к естественной арифметике (в плане бесконечностей, деления на 0).
В книге "24 смертных греха компьютерной безопасности" Ховарда, Лебланка, Вьеги встретил такое решение:
учет размеров типов (см. другие ответы);
простота кода;
явное преобразование типов;
использование SafeInt (by Дэвид Лебланк)
при использовании gcc, компилировать с флагом -ftrapv (при переполнении знаковы
целочисленных вызывается abort());
использование беззнаковых целых для работы с памятью и индексами массивов (слегка облегчает последствия);
Ответ 5
В Visual C++ можно использовать функции из Intsafe.h, например для умножения:
#include
#include
#include
#include
#include
int _tmain(int argc, _TCHAR* argv[])
{
ULONGLONG a=100000000000, b=5000000000, c;
HRESULT hr = ULongLongMult(a,b,&c);
if(SUCCEEDED(hr)) printf("Result is %llu",c);
else if(hr == INTSAFE_E_ARITHMETIC_OVERFLOW) printf("Overflow");
return 0;
}
Данные функции определены как inline, и их реализация зависит от архитектуры. Функция ULongLongMult:
На 64-битных архитектурах использует intrinsic-функцию компилятора _umul128, поэтому должна быть довольно эффективной.
На 32-битных архитектурах использует специальный алгоритм расчета с разбиением чисе
на 2 32-битных части (результат вычисляется по формуле a.b * c.d = (a*c*2^64) + (a*d*2^32) + (b*c*2^32) + (b*d)), и переполнение обнаруживается проверкой определенных битов в промежуточных результатах.
Комментариев нет:
Отправить комментарий