Издательский дом ООО "Гейм Лэнд"ЖУРНАЛ ХАКЕР 109, ЯНВАРЬ 2008 г.

Трюки от Крыса

Крис Касперски

Хакер, номер #109, стр. 120

О переполняющихся буферах написано много, о переполнении целочисленных/вещественных переменных — чуть меньше, а ведь это одна из фундаментальных проблем языка Си, доставляющая программистам массу неприятностей и порождающая целых ворох уязвимостей разной степени тяжести, особенно если программа пишется сразу для нескольких платформ. Как быть, что делать? Мыщъх делится своим личным боевым опытом (с учетом всех травм и ранений, полученных в ходе сражений), надеясь, что читатели найдут его полезным, а я тем временем в госпитале с сестричкой…

Закон суров, но он закон!

Фундаментальность проблемы переполнения целочисленных переменных имеет двойственную природу. Стандарт декларирует, что результат выражения (a+b) в общем случае неопределен (undefined) и зависит как от архитектурных особенностей процессора, так и от характера компилятора. Положение усугубляется тем, что Си (в отличие от Паскаля, например) вообще ничего не говорит о разрядности типов данных, больших, чем байт. long int вполне может равняться int. И хотя начиная с ANSI C99 появились типы int32_t, int64_t, а некоторые компиляторы (в частности, MS VC) еще черт знает с какой версии поддерживают нестандартные типы _int32 и _int64, проблема определения разрядности переменных остается. Одним процессорам выгоднее обрабатывать 64-битные данные, другим — 32-битные, и потому выбирать тип «на вырост», то есть с расчетом, чтобы в него точно влезли обозначенные значения, — расточительно и негуманно.

К тому же гарантии, что переполнение не произойдет, у нас нет. Обычно при переполнении наблюдается либо изменение знака числа (небольшое знаковое отрицательное превращается в большое беззнаковое), либо заворот по модулю, физическим аналогом которого могут служить обычные механические часы. Хинт: 3+11=2, а вовсе не 14! Вот так неожиданность! И ищи потом, на каком этапе вычислений данные превращаются в винегрет! А искать можно долго, и ошибки возникают даже в полностью отлаженных программах, стоит только скормить им непредвиденную последовательность входных данных.

LIA-1 (смотри приложение «H» к Стандарту ANSI C99) говорит, что в случае отсутствия заворота при переполнении знаковых целочисленных переменных компилятор должен генерировать сигнал (ну или, в терминах Microsoft, выбрасывать исключение). Поскольку знаковый бит на x86-процессорах расположен по старшему адресу, заворота не происходит, и некоторые компиляторы учитывают это обстоятельство при генерации кода. В частности, GCC поддерживает специальный флаг ‘-ftrapv’. Посмотрим, как он работает?

Исходная функция, складывающая два знаковых числа типа int

foo(int a, int b)

{

return a+b;

}

Компиляция компилятором GCC с ключами по умолчанию

foo proc near

push ebp ; открываем кадр

mov ebp, esp ; стека

mov eax, [ebp+arg_4] ; грузим аргумент b в EAX

add eax, [ebp+arg_0] ; EAX := (a + b)

pop ebp ; закрываем кадр стека

retn ; возвращаем сумму (a+b) в EAX

foo endp

Очевидно, что результат работы этой функции непредсказуем, и, если сумма двух int'ов не влезет в отведенную разрядность, нам вернется черт знает что. А вот теперь используем флаг ‘-ftrapv’:

Компиляция компилятором GCC с ключом ‘-ftrapv’

foo proc near

push ebp ; открываем

mov ebp, esp ; кадр

sub esp, 18h ; стека

mov eax, [ebp+arg_4] ; грузим аргумент b в EAX

mov [esp+18h+var_14], eax ; передаем аргумент b функции __addvsi3

mov eax, [ebp+arg_0] ; грузим аргумент a в EAX

mov [esp+18h+var_18], eax ; передаем аргумент a Функции __addvsi3

call __addvsi3 ; __addvsi3(a, b); // безопасное сложение

leave ; закрываем кадр стека

retn ; возвращаем сумму (a+b) в EAX

foo endp

__addvsi3 proc near

push ebp ; открываем

mov ebp, esp ; кадр

sub esp, 8 ; стека

mov [ebp+var_4], ebx ; сохраняем EBX в локальной переменной

mov eax, [ebp+arg_4] ; грузим аргумент b в EAX

call __i686_get_pc_thunk_bx ;грузим thunk в EBX

add ebx, 122Fh ; -> GLOBAL_OFFSET_TABLE

mov ecx, [ebp+arg_0] ; грузим аргумент a в ECX

test eax, eax ; определяем знак аргумента b

lea edx, [eax+ecx] ; EDX := a + b

js short loc_8048410

cmp edx, ecx ; if ((a + b) >= a)

jge short loc_8048400 ; goto OK

loc_80483F5: ; если ((a+b)<a)…

call _abort ; то имело место переполнение

lea esi, [esi+0] ; и мы абортаемся

loc_8048400: ; нормальное продолжение программы

mov ebx, [ebp+var_4] ; восстанавливаем EBX

mov eax, edx ; перегоняем в EAX (a+b)

mov esp, ebp ; закрываем

pop ebp ; кадр стека

retn ; возвращаем (a+b) в EAX

loc_8048410: ; работаем со знаковыми

cmp edx, ecx ; if ((a+b) < a)

jg short loc_80483F5 ; GOTO _abort

jmp short loc_8048400 ; -> нормальное продолжение

__addvsi3 endp

Сложение с флагом ‘-ftrapv’ безопасно, но… как же оно тормозит! Кстати, на уровне оптимизации ‘-O2’ и выше флаг ‘-ftrapv’ игнорируется. Но даже без всякой оптимизации он не ловит переполнения при умножении и, что самое печальное, поддерживается не всеми компиляторами.

Пишем закон сами!

На самом деле для «безопасного» сложения чисел у нас есть все необходимые ингредиенты. Причем оно будет работать с любым компилятором на любом уровне оптимизации и с достаточно приличной скоростью (уж во всяком случае побыстрее, чем __addvsi3 в реализации от GGC).

Функция безопасного сложения двух переменных типа int в простейшем случае выглядит так:

Функция безопасного сложения

#include <limits.h> // здесь содержатся лимиты всех типов

int safe_add(int a, int b)

{

if(INT_MAX - b < a) return _abort(ERROR_CODE);

return a + b;

}

Дизассемблерный листинг не приводится за ненадобностью. Если компилятор заинлайнит safe_add, то мы имеем следующий оверхид: одно лишнее ветвление, одно лишнее сравнение и одно лишнее вычитание. Конечно, в особо критичных фрагментах (да еще и в глубоко вложенных циклах) этот оверхид непременно даст о себе знать, и в таком случае лучше отказаться от safe_add и пойти другим путем. Например, обосновать, что переполнения (в данном месте) не может произойти в принципе даже при обычном сложении.

Отправляемся в плаванье

Вещественные переменные, в отличие от целочисленных, работают чуть медленнее, хотя… это еще как сказать! С учетом того, что ALU- и FPU-блоки современных ЦП работают параллельно, для достижения наивысшей производительности целочисленные и вещественные переменные должны использоваться совместно (конкретная пропорция определяется типом и архитектурой процессора).

Главное, что x86 и некоторые другие ЦП поддерживают генерацию исключений при переполнении вещественных переменных. Но умолчанию она выключена, и включить ее, увы, средствами чистого Си нельзя, но вот если прибегнуть к функциям API или нестандартным расширениям…

Рассмотрим следующую программу:

Активация исключений при работе с вещественными переменными

#include <float.h>

#include <stdio.h>

main()

{

// объявляем вещественную переменную

// (это может быть также и float)

double f = 666;

// считываем значение управляющего слова

// сопроцессора через MS-specific функцию

int cw = _controlfp(0, 0);

// задействуем исключения для следующих ситуаций

cw &=~(EM_OVERFLOW|EM_UNDERFLOW|EM_INEXACT|EM_ZERODIVIDE|EM_DENORMAL);

// обновляем содержимое управляющего слова сопроцессора

_controlfp( cw, MCW_EM );

__try{ // в блоке try мы будем делать исключения

while(1) // в бесконечном цикле вычисляем f = f*f

{ // выводя его содержимое на экран

printf("%fn", f = f * f);

}

}

except(puts("in filter"), 1) // а тут мы ловим возникающие исключения!

{

puts("in except"); // для упрощения обработка исключений опущена

}

}

В зависимости от компилятора (и процессора) этот пример будет тормозить в большей или меньшей степени. В частности, на x86 вещественное деление намного быстрее целочисленного. С другой стороны, компилятор MS VC выполняет вещественное сложение в разы медленнее главным образом потому, что не умеет сохранять промежуточный результат вычислений в регистрах сопроцессора и постоянно загружает/выгружает их в переменные, находящиеся в памяти. GCC такой ерундой не страдает, и при переходе с целочисленных переменных на вещественные быстродействие не только не падает, но местами даже и возрастает.

Кроме того, вещественные переменные имеют замечательное значение «не число», которое очень удобно использовать в качестве индикатора ошибки. У целочисленных с этим настоящая проблема. Одни функции возвращают 0, другие - -1, в результате чего возникает путаница, а если и 0, и -1 входят в диапазон допустимых значений, возвращаемых функцией, приходится не по-детски извращаться, возвращая код ошибки в аргументе, переданном по указателю или же через исключения.

А с вещественными переменными все просто и удобно. И это удобство стоит небольшой платы производительностью.

Содержание
ttfb: 5.8128833770752 ms