Что каждый программист на C должен знать об Undefined Behavior. Часть 2/3

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html
  • Перевод
Часть 1
Часть 2
Часть 3

В первой части нашего цикла мы обсудили, что такое неопределённое поведение, и как оно позволяет компиляторам C и C++ генерировать более высокопроизводительные приложения, чем «безопасные» языки. В этом посте мы обсудим, чем на самом деле является «небезопасный» C, объяснив некоторые совершенно неожиданные эффекты, вызываемые неопределённым поведением. В третьей части, мы обсудим, как «дружественные» компиляторы могут смягчить некоторые из таких эффектов, даже если они не обязаны это делать.

Мне нравится называть это «Почему неопределённое поведение часто пугает и ужасает программистов на C».

image

Взаимодействие оптимизаций компилятора приводит к неожиданным результатам


Современный оптимизирующий компилятор содержит множество оптимизаций, работающих в определённом порядке, иногда повторяющихся по несколько раз, и этот порядок может изменяться по мере развития компилятора (т.е. при выходе новых релизов).

Также различные компиляторы имеют существенно разные оптимизаторы. Так как оптимизации работают как различные стадии преобразования кода, могут возникать различные эффекты, когда предшествующие стадии изменили код.

Рассмотрим такой дурацкий пример (упрощенный из примера реального бага в ядре Linux), чтобы сделать это более конкретным:

void contains_null_check(int *P) {
  int dead = *P;
  if (P == 0)
    return;
  *P = 4;
}

В этом примере, код «в явном виде» производит проверку на нулевой указатель. Если компилятор запустит проход удаления недостижимого кода («Dead Code Elimination») перед проходом удаления избыточных проверок на null («Redundant Null Check Elimination»), то мы увидим, что будет выполнено два преобразования кода:

void contains_null_check_after_DCE(int *P) {
  //int dead = *P;     // deleted by the optimizer.
  if (P == 0)
    return;
  *P = 4;
}

и затем:

void contains_null_check_after_DCE_and_RNCE(int *P) {
  if (P == 0)   // Null check not redundant, and is kept.
    return;
  *P = 4;
}

Однако, оптимизатор может быть структурирован иначе, и может запустить RNCE перед DCE. Тогда будут выполнены следующие два преобразования:

void contains_null_check_after_RNCE(int *P) {
  int dead = *P;
  if (false)  // P was dereferenced by this point, so it can't be null 
    return;
  *P = 4;
}

и затем удалён избыточный код:

void contains_null_check_after_RNCE_and_DCE(int *P) {
  //int dead = *P;
  //if (false)
  //  return;
  *P = 4;
}

Для многих программистов, удаление проверки на null из функции было бы очень неожиданным (и они обвинят в баге компилятор). Однако, оба варианта, и «contains_null_check_after_DCE_and_RNCE», и «contains_null_check_after_RNCE_and_DCE», являются совершенно верной оптимизированной формой «contains_null_check» в соответствии со стандартом, и обе оптимизации важны для повышения производительности различных приложений.

Хотя это довольно простой и надуманный пример, такие вещи всё время происходят при инлайне функций. Инлайн функции открывает множество возможностей для последующих оптимизаций. Это означает, что если оптимизатор решит инлайнить функцию, будут произведены и другие локальные оптимизации, изменяющие поведение кода. Это совершенно правильно, как с точки зрения стандарта, так и с практической точко зрения, для повышения производительности.

Неопределённое поведение и безопасность не должны смешиваться


Семейство C-подобных языков программирования используется для широкого диапазона критического безопасного кода, такого как ядра, демоны setuid, web-браузеры, и пр. Этот код работает с «враждебными» входными данными и баги в нём могут привести к любого сорта проблемам в безопасности. Одно из наиболее известных преимуществ С в том, что относительно легко понять, что происходит, просто читая код.

Однако, неопределённое поведение лишает язык такого свойства. Например, большинство программистов будут считать, что «contains_null_check» в примере выше производит проверку на null. Хотя этот пример не такой страшный (этот код может что-то разрушить, если ему будет передан null, что относительно легко обнаружить при отладке) есть большое количество вполне разумно выглядящих фрагментов кода на C, которые на самом деле совершенно неверны. Эта проблема касается многих проектов (включая Linux Kernel, OpenSSL, glibc, и т.п.) и даже вынудило CERT опубликовать уведомление об уязвимости GCC (хотя лично я считаю, что все широко используемые оптимизирующие компиляторы C уязвимы, не только GCC).

Рассмотрим пример. Представим тщательно написанный код на С:

void process_something(int size) {
  // Catch integer overflow.
  if (size > size+1)
    abort();
  ...
  // Error checking from this code elided.
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

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

void process_something(int *data, int size) {
  char *string = malloc(size+1);
  read(fd, string, size);
  string[size] = 0;
  do_something(string);
  free(string);
}

Когда компиляция происходит на 64-битной платформе, есть вероятность возникновения бага, когда «size» равен INT_MAX (возможно, это размер файла на диске). Посмотрим, насколько это ужасно: при прверке кода не обнаруживается ничего, так как проверка переменной на переполнение выглядит разумно. При тестировании кода не обнаруживается проблем, если специально не тестировать этот путь выполнения. Кажется, код может считаться безопасным, пока кто-то не решит эксплуатировать уязвимость. Это очень неожиданный и довольно ужасный класс багов. К счастью, его просто починить: просто используйте «size == INT_MAX» или что-то аналогичное.

Выясняется, что переполнение целого — это проблема безопасности по многим причинам. Даже если вы используете полностью определённую целочисленную арифметику (либо используя -fwrapv, либо используя беззнаковые целые), остаётся класс возможных багов, связанных с переполнением целых. К счастью, эти баги заметны в коде и хорошо известны аудиторам безопасности.

Отладка оптимизированного кода может стать бессмысленной


Некоторые люди (например, низкоуровневые embedded-программисты, которые любят смотреть генерированный машинный код) работают с постоянно включенной оптимизацией. Так как код часто имеет баги в начале разработки, эти люди наблюдают непропорционально много неожиданных оптимизаций, которые могут привести к трудноотлаживаемым проблемам при выполнении программы. Например, случайно пропустив «i = 0» в примере «zero_array» в примере из первой статьи, мы разрешаем компилятору полностью удалить цикл (превратив zero_array в «return;») потому что это будет использованием неинициализированной переменной.

Другой интересный случай может произойти, когда есть глобальный указатель на функцию. Упрощённый пример выглядит так:

static void (*FP)() = 0;
static void impl() {
  printf("hello\n");
}
void set() {
  FP = impl;
}
void call() {
  FP();
}

который clang оптимизирует в:

void set() {}
void call() {
  printf("hello\n");
}

Он может так сделать, потому что вызов нулевого указателя не определён, что разрешает предполагать, что set() должно быть вызвано перед call(). В этом случае, разработчик забыл вызвать set(), программа не падает на разыменовании null, и код сломается, если кто-то другой сделает дебажный билд.

Такие баги отслеживаются: если вы заподозрили нечто подозрительное, попробуйте собрать с -O0, и компилятор, скорее всего, не будет выполнять оптимизаций.

«Работающий» код, использующий неопределённое поведение, может сломаться, если в компиляторе что-то изменится.

Мы рассмотрели множество случаев, когда код, который «вроде бы работает» внезапно ломается когда для компиляции используется более новая версия LLVM, или когда приложение перенесено с GCC на LLVM. Хотя LLVM и сам по себе может иметь один или два бага, чаще всего это случается из-за того, что скрытые баги в приложении проявились благодаря компилятору. Это может случится в множестве различных случаев, вот два примера:

1. неинициализированная переменная, которая принимала ранее нулевое значение по счастливой случайности, а теперь помещена в другой регистр, который не содержит ноль. Такое поведение часто проявляется при изменениях в аллокаторе регистров.

2. Переполнение массива на стеке затирает актуальные переменные вместо «мёртвых». Это происходит, когда компилятор переупорядочивает переменные на стеке, или более агрессивно упаковывает в пространство стека переменные с неперекрывающимся временем жизни.

Важная и пугающая вещь, обнаружить, что практически любая оптимизация, основанная на неопределённом поведении, может привести к багам в любой момент в будущем. Инлайн функций, разворачивание циклов, и другие оптимизации будут работать лучше, и существенная часть их делается за счёт вторичных оптимизаций, как показано выше.

Меня это очень огорчает, отчасти из-за того, что практически неизбежно начинают обвинять компилятор, а также из-за того, что огромное количество С-кода является миной замедленного действия, ждущей, чтобы взорваться. И это ещё хуже, потому что…

Не существует надёжного способа убедиться в том, что большая кодовая база не содержит UB


Это очень плохая ситуация, потому что фактически не существует надёжного способа определить, что в крупномасштабном приложении нет UB, и что оно не сломается в будущем. Есть много полезных инструментов, которые могут помочь найти некоторые баги, но ничто не даёт полной уверенности, что ваш код не сломается в будущем. Давайте рассмотрим некоторые варианты, их сильные и слабые стороны.

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

2. Clang имеет экспериментальный режим -fcatch-undefined-behavior, который вставляет рантаймовые проверки для поиска нарушений, таких, как выход за границы диапазона сдвига, некоторых простых ошибок выхода за границы массивов и т.п. Эти проверки ограничены, потому что замедляют работу приложения, и не могут помочь с разыменованием произвольного указателя (а Valgrind может), но могут найти другие важные баги. Clang также полностью поддерживает флаг -ftrapv (не путать с -fwrapv), с помощью которого можно отлавливать в рантайме баги с переполнением знаковых целых (у GCC тоже есть такой флаг, но он очень ненадёжен и забагован, по моему опыту). Вот маленькое демо -fcatch-undefined-behavior:

$ cat t.c
int foo(int i) {
  int x[2];
  x[i] = 12;
  return x[i];
}

int main() {
  return foo(2);
}
$ clang t.c 
$ ./a.out 
$ clang t.c -fcatch-undefined-behavior 
$ ./a.out 
Illegal instruction

3. Сообщения компилятора хороши для поиска некоторых классов багов, таких, как неинициализированные переменные и простые переполнения целых. Есть два главных ограничения: 1) нет динамической информации об исполнении кода и 2) анализ должен быть очень быстрым, потому что любой анализ увеличивает время компиляции.

4. Статический анализатор Clang производит гораздо более глубокий анализ, пытаясь найти баги, включая использование UB, такое, как разыменование null-указателя.

Вы можете думать о нём как об усиленном средстве анализа по сравнению с предупреждениями компилятора, так как он не имеет временных ограничений, как обычные предупреждения. Основной недостаток статического анализатора в том, что он: 1) не имеет динамической информации о процессе работы программы и 2) не интегрирован в обычный процесс разработки (хотя его интеграция с XCode 3.2. и более поздними — это фантастика).

5. Субпроект LLVM «Klee» использует символьный анализ, чтобы «попробовать каждый возможный путь» по коду для нахождения багов в коде и генерации теста. Это замечательный маленький проект который главным образом ограничен тем, что его непрактично запускать на больших приложениях.

6. Хотя я никогда его не пробовал, инструмент C-Semantics от Чаки Эллисона и Григори Росу очень интересен тем, что может найти некоторые классы багов (таких, как нарушения точек следования). Он по-прежнему находится в состоянии исследовательского прототипа, но может быть полезен для нахождения багов в (маленьких и ограниченных) программах. Я рекомендую к чтению пост Джона Реджера для того, чтобы получить больше информации.

Итак, мы имеем множество инструментов для поиска багов, но нет хорошего способа доказать, что в приложении нет UB. Представьте, что существуют тонны багов в реальных приложениях, и что С используется в широком спектре критических приложений, и это пугает. В нашей последней статье, я рассмотрю различные опции, которые имеет компилятор C, для того, чтобы обрабатывать UB, особенно уделив внимание Clang-у.
Поделиться публикацией

Комментарии 31

    0
    Я только одного не понял: как это должно работать:
    if(size > size+1)

    В моей голове даже не возникает попытка осмыслить это. Для чего тогда вообще есть INT_MAX?!
    if(size > INT_MAX-1)
      +3
      INT_MAX — это максимальное значение (знакового) целого, это очень просто: http://www.cplusplus.com/reference/climits/
      Если интерпретировать выражение (size > size+1) буквально, то оно равно true для любого значения, кроме INT_MAX, т.к. INT_MAX + 1 = INT_MIN из-за конечности разрядной сетки.
      Но в силу того, что по стандарту переполнение знакового целого — это UB, оптимизатор заменит выражение в скобках на константу true.
        +1
        fix: на false, конечно же
          0
          Вообще-то это было среднее между сарказмом и возмущением: разве не надо быть идиотом, чтобы писать код, явно порождающий UB? Тогда и на 0 делить можно, чо…
            0
            А вот попробуете вы поддержать какой-нибудь старый HP-UX или там AIX — ещё и не такое напишите.

            В частности подобный код был в свой время в скриптах autoconf'а. Собственно и сейчас там — только уже для unsigned типов.
      –4

      Ага, вот поэтому то же ядро FreeBSD компилилось максимум с -O2, а то и вообще -O0 :).

        0

        А почему проверка указателя на 0 — избыточна и может быть выкинута при оптимизации?

          +4
          Она избыточна, если присходит после разыменования указателя. То есть компилятор считает, что если указатель уже успешно разыменован, он не может быть нулевым.
            0
            Понятно.
            Неочевидное неопределённое поведение :)
              0

              А с каких пор нельзя читать из нулевого адреса? Почему компилятор считает, что "раз читают, то адрес не может быть нулевым"?

                +5
                В соответствии со стандартом, разыменование нулевого указателя является UB.
                  –2

                  Т.е. результат взятия значения по нему является UB. По какому праву компилятор выкинул последующую проверку на 0?
                  Допустим нам надо написать функцию, в которую передается указатель на запись в таблице прерывания, где мы вначале сохраняем значение вектора по этому указателю, а потом, если это адрес самого первого вектора, что-то делаем. А компилировать и запускать все будем на x86, где таблица прерываний расположена по нулевому адресу. Что тогда? Все, Сишные комптляторы в топку, меняем язык?
                  Кстати, если я правильно понял, стандарт говорит об указателе null, а не 0. А сравнение в примере идет именно с нулем.
                  ИМХО, но тут явно недоработка компилятора.

                    +2
                    Если вам нужно сделать запись в массив, расположенный по адресу 0, объявите его как volatile. Компилятор не оптимизирует доступ к volatile-переменным.
                    > об указателе null, а не 0
                    #define NULL ((void *) 0)

                    >ИМХО, но тут явно недоработка компилятора.
                    Нет.
                      +2

                      Нулевой указатель и нулевой адрес — это и правда разные понятия. Но константа 0 обозначает именно первый. Аналогично, проверка if(ptr) проверяет именно соответствие ptr нулевому указателю а не нулевому адресу.


                      Т.е. результат взятия значения по нему является UB. По какому праву компилятор выкинул последующую проверку на 0?

                      По праву того что стандарт разрешает. UB — это такая вещь после которой разрешено любое поведение программы. Как следствие, компилятор имеет право оптимизировать код из предположения что UB никогда не происходит.

                        +1
                        UB — это такая вещь после которой разрешено любое поведение программы.
                        Не только «после». До — тоже можно: However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation). (выделение моё).

                        Вот если программа никогда-никогда не вызвает UB — тогда и только тогда можно говорить о том, правильно её скомпилировал компилятор или нет.
              0
              .
                0

                Лично мне больше нравится считать С эдаким ассемблеро-заменителем. Во первых, большинство Embedded программ пишется под конкретные платформы и НЕ нуждается в переносимости. Там переносимость даже вредна. Ибо зная особенности процессора можно и нужно ими пользоваться. Во вторых, "неопределённое поведение" на самом деле вполне определённое, если мы пишем для конкретного компилятора и конкретного процессора. Я скорее за каталогизацию и документирование "определённого поведения" всех возможных компиляторов на всех возможных платформах, нежели попытку создать общий для всех и ограниченный(кастрированный), и по этому неудобный и бесполезный, сферический С в вакууме.


                Конструкция (size > size + 1) идеальна! Она не зависит от разрядности числа. Компактна. Ясна. Не требует никаких констант и их определений. На мой взгляд это одна из множества жемчужин С которые надо знать и использовать.


                Универсализация это всегда компромисс. Это как если у сложного и красивого многогранника сточить все грани до сферы. И самое вкусное оказывается за её пределами. К чёрту!

                  0
                  На мой взгляд это одна из множества жемчужин С которые надо знать и использовать.
                  Проблема в том, что это не жемчужина C. Это жемчужина какого-то другого языка.

                  Ибо зная особенности процессора можно и нужно ими пользоваться.
                  Не в том случае, когда вы пишите на C. Хотите сделать другой язык (ну там, EmC, или что-нибудь подобное) — вперёд с песней. Но не «мне больше нравится считать С» чем-то, чем он не является.

                  Чем является C — написано в стандарте языка. Точка. Он предназначен для написания переносимых программ — что значит что попытка вомпользоваться «особенностями процессора» с вероятностью 99% кончится тем, что вы вызовите UB и компилятор, рано или поздно, вам всю малину испортит.

                  Во вторых, «неопределённое поведение» на самом деле вполне определённое, если мы пишем для конкретного компилятора и конкретного процессора.
                  Нет, конечно. Все оптимизации во всех оптимизирующих компиляторах исходят из того, что неопределённого поведения в программе нет. Обеспечить подобное — обязанность программиста.

                  В каких-то отдельных случаях происходит явное доопределение (ну как, например, с -fwrapv — но таких опций десятки, а неопределённых поведений в стандарте — сотни.
                    0
                    Для использования особенностей конкретного процессора есть как минимум два «законных» способа:
                    1) ассемблерные вставки (куда оптимизатор не лезет)
                    2) intrinsic-функции, которые для этого и существуют.
                      0
                      Это уже, как бы, не совсем C. Но, как бы, в случаях, когда разработчики компилятора явно предусмотрели отход от стандарта — например определили тип __m128 как float __attribute__ ((__vector_size__ (16), __may_alias__)) — то и использовании этих вещей в соответствии с описаниями не будет UB.

                      Holix же выступает за совсем другое: без явного документирования особенностей использовать определённые UB как если бы они не были UB — исходя из того, что реально сегодня, сейчас, делает компилятор.

                      Это — путь в никуда: сегодня ваша программа собралась и, возможно, даже работает — но никто не может гарантировать что завтра, при выходе небольшой правки к компилятору (а иногда и к процессору — там тоже UB бывают, как это ни удивительно) все «не слетит с катушек».
                    0
                    «неопределённое поведение» на самом деле вполне определённое, если мы пишем для конкретного компилятора и конкретного процессора
                    Вы с implementation defined behavior не путаете часом?
                      –1
                      Путает, конечно. Я так думаю, что стандарт он открывать и читать даже не пытался, пишет «по наитию».
                        –2
                        1. Нет, не путаю.
                        2. Компилятор, внезапно, имеет абсолютно детерминированный алгоритм оптимизации, который в каждом конкретном случае приведёт к конкретному поведению.
                        3. На эту тему можно долго и много рассуждать, скоро напишу ещё, кстати.
                          –2
                          1. Нет, не путаю.
                          Таки путаете.
                          2. Компилятор, внезапно, имеет абсолютно детерминированный алгоритм оптимизации, который в каждом конкретном случае приведёт к конкретному поведению.
                          Внезапно компилятор — это ещё не всё. Рассмотрите классическую программу с UB:
                            int *p = new int[10];
                            ...
                            delete[] p;
                            ...
                            p[5] = 120; // Что случится здесь?
                          
                          Или ещё лучше:
                            int *p = new int[10];
                            p[-2] = 17;
                          

                          Поведение программы может зависеть от массы разных причин — особенно на современных системах с ASLR. И компилятор ничего с этим сделать не может.
                          3. На эту тему можно долго и много рассуждать, скоро напишу ещё, кстати.
                          Давайте-давайте. Начните с пары прамеров, описанных выше, расскажите про ваш магический компилятор (у вас же он припасён в рукаве, правда?), который что-то там конкретное гарантирует, а мы будем рассматривать его в разных системах и с разными libc, tcmalloc'ами и прочим.

                          Только боюсь не выйдет у вас ничего. Из нескольких сотен описанных в стандарте UB компилятор может отловить (и отлавливает — см. UBSAN) дай бог несколько десятков — и то негарантированно.
                            –1
                            Вы бы не так по-хамски общались, можно было бы поговорить на эту тему.
                      0
                      Вот бы было здорово, если бы при компиляции IDE сразу бы могла показать код который изменится при оптимизации. Написал разименование а потом проверку на ноль, а IDE сразу сделал код серым и сразу ясно что, что-то не то.
                        0
                        В следующей части как раз написано, в чём тут сложность.
                          0
                          С какой то из последних версий GCC(G++) вам рассказывает о «ненужных» проверках на нуль.
                          0
                          Удивлен что
                          1) не было упомянуто семейство *sanitizer (https://github.com/google/sanitizers), clang.llvm.org/docs/UndefinedBehaviorSanitizer.html Уже несколько лет регулярно пользуемся ими на дебажных билдах при прогоне тестов. Отловили в тестах приличное количество проблем которые или себя никак не проявляли или проявляли себя спорадически.
                          2) до сих пор кто-то использует супер медленный и тормозной valgrind. Что-то более или менее интенсивно потребляющее CPU или память под ним запустить практически невозможно. Asan же дает всего 2x замедление и ~2x потребление памяти. Еще одна проблема valgrind в том что множество юзкейсов связанных с таймингом на нем не воспроизводятся.

                            0
                            На URL оригинальной статьи посмотрите, да? Хинт: 2011 — это не номер авто автора.
                              0
                              Да, не обратил внимание. ИМХО с точки зрения переводчика стоило бы актуализировать некоторую информацию (для IT 6 лет это огромный срок). Тот же klee был одно время заброшен полностью. Сейчас пытаются проект возродить (судя по офиц. сайту), однако тот факт что он до сих пор собирается с llvm 3.4 несколько удручает. Опять таки, стоило бы добавить информацию про проекты упомянутые мною выше.

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

                          Самое читаемое