Издательский дом ООО "Гейм Лэнд"ЖУРНАЛ ХАКЕР 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 с ключами по умолчанию

fooproc near

pushebp; открываем кадр

movebp, esp;стека

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

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

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

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

fooendp

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

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

fooproc near

pushebp; открываем

movebp, esp;кадр

subesp, 18h;стека

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

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

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

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

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

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

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

fooendp

__addvsi3proc near

pushebp; открываем

movebp, esp; кадр

subesp, 8; стека

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

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

call__i686_get_pc_thunk_bx;грузим thunk в EBX

addebx, 122Fh; -> GLOBAL_OFFSET_TABLE

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

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

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

jsshort loc_8048410

cmpedx, ecx; if ((a + b) >= a)

jgeshort loc_8048400; goto OK

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

call_abort; то имело место переполнение

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

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

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

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

movesp, ebp; закрываем

popebp;кадр стека

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

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

cmpedx, ecx; if ((a+b) < a)

jgshort loc_80483F5;GOTO _abort

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

__addvsi3endp

Сложение с флагом ‘-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("%f\n", f = f * f);

}

}

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

{

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

}

}

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

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

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

Содержание
загрузка...
Журнал Хакер #151Журнал Хакер #150Журнал Хакер #149Журнал Хакер #148Журнал Хакер #147Журнал Хакер #146Журнал Хакер #145Журнал Хакер #144Журнал Хакер #143Журнал Хакер #142Журнал Хакер #141Журнал Хакер #140Журнал Хакер #139Журнал Хакер #138Журнал Хакер #137Журнал Хакер #136Журнал Хакер #135Журнал Хакер #134Журнал Хакер #133Журнал Хакер #132Журнал Хакер #131Журнал Хакер #130Журнал Хакер #129Журнал Хакер #128Журнал Хакер #127Журнал Хакер #126Журнал Хакер #125Журнал Хакер #124Журнал Хакер #123Журнал Хакер #122Журнал Хакер #121Журнал Хакер #120Журнал Хакер #119Журнал Хакер #118Журнал Хакер #117Журнал Хакер #116Журнал Хакер #115Журнал Хакер #114Журнал Хакер #113Журнал Хакер #112Журнал Хакер #111Журнал Хакер #110Журнал Хакер #109Журнал Хакер #108Журнал Хакер #107Журнал Хакер #106Журнал Хакер #105Журнал Хакер #104Журнал Хакер #103Журнал Хакер #102Журнал Хакер #101Журнал Хакер #100Журнал Хакер #099Журнал Хакер #098Журнал Хакер #097Журнал Хакер #096Журнал Хакер #095Журнал Хакер #094Журнал Хакер #093Журнал Хакер #092Журнал Хакер #091Журнал Хакер #090Журнал Хакер #089Журнал Хакер #088Журнал Хакер #087Журнал Хакер #086Журнал Хакер #085Журнал Хакер #084Журнал Хакер #083Журнал Хакер #082Журнал Хакер #081Журнал Хакер #080Журнал Хакер #079Журнал Хакер #078Журнал Хакер #077Журнал Хакер #076Журнал Хакер #075Журнал Хакер #074Журнал Хакер #073Журнал Хакер #072Журнал Хакер #071Журнал Хакер #070Журнал Хакер #069Журнал Хакер #068Журнал Хакер #067Журнал Хакер #066Журнал Хакер #065Журнал Хакер #064Журнал Хакер #063Журнал Хакер #062Журнал Хакер #061Журнал Хакер #060Журнал Хакер #059Журнал Хакер #058Журнал Хакер #057Журнал Хакер #056Журнал Хакер #055Журнал Хакер #054Журнал Хакер #053Журнал Хакер #052Журнал Хакер #051Журнал Хакер #050Журнал Хакер #049Журнал Хакер #048Журнал Хакер #047Журнал Хакер #046Журнал Хакер #045Журнал Хакер #044Журнал Хакер #043Журнал Хакер #042Журнал Хакер #041Журнал Хакер #040Журнал Хакер #039Журнал Хакер #038Журнал Хакер #037Журнал Хакер #036Журнал Хакер #035Журнал Хакер #034Журнал Хакер #033Журнал Хакер #032Журнал Хакер #031Журнал Хакер #030Журнал Хакер #029Журнал Хакер #028Журнал Хакер #027Журнал Хакер #026Журнал Хакер #025Журнал Хакер #024Журнал Хакер #023Журнал Хакер #022Журнал Хакер #021Журнал Хакер #020Журнал Хакер #019Журнал Хакер #018Журнал Хакер #017Журнал Хакер #016Журнал Хакер #015Журнал Хакер #014Журнал Хакер #013Журнал Хакер #012Журнал Хакер #011Журнал Хакер #010Журнал Хакер #009Журнал Хакер #008Журнал Хакер #007Журнал Хакер #006Журнал Хакер #005Журнал Хакер #004Журнал Хакер #003Журнал Хакер #002Журнал Хакер #001