От переводчика:

Переводы статьи про неопределённое поведение в языке C от Криса Латтнера, одного из ведущих разработчиков проекта LLVM, вызвали большой интерес, и даже некоторое непонимание со стороны тех, кто не встречался с описываемыми явлениями на практике. В своей статье Крис даёт ссылку на блог Джона Реджера, и на его статью от 2010 года, посвящённую UB в C и C++. Но в блоге Реджера есть и гораздо более новые статьи на эту тему (что не отменяет ценность старых, однако).

Я хочу предложить вашему вниманию свежую статью «Undefined Behavior in 2017». Статья в оригинале имеет очень большой объём, и я разбил её на части.

В первой части речь пойдёт о разных инструментах поиска UB: ASan, UBSan, TSan и т.д.
ASan — Address Sanitizer от компании Google, разработанный на основе LLVM.
UBSan — Undefined Behavior Sanitizer, предназначен для обнаружения различных UB в программах на C и C++, доступен для Clang и GCC.
TSan — Thread Sanitizer, предназначен для обнаружения UB в многопоточных программах.
Если вам эта тема покажется далёкой от практики, я рекомендую дождаться продолжения, потому что в конце вас ждёт поистине огромный список UB языка С++ (их должно быть около 200!)
И я рекомендую прочитать также старые статьи Реджера, они не утратили актуальности.
Об авторе: Джон Реджер является профессором Computer Science в университете штата Юта в США.

Мы часто слышим, что некоторые люди утверждают, что проблемы, вытекающие из неопределённого поведения (UB) в C и C++ в основном решены путём широкого распространения инструментов динамической проверки, таких, как ASan, UBSan, MSan и TSan. Мы здесь покажем очевидное: несмотря на то, что в последние годы произошло множество прекрасных улучшений в этих инструментах, проблемы UB далеки от разрешения, и рассмотрим ситуацию в деталях.

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

Проблема с инструментами динамической отладки заключается в том, что они ничего не делают, чтобы помочь нам справиться с самыми плохими случаями UB: про которые нам неизвестно, как они сработают при тестировании, но кто-то другой может выяснить, как UB будет проявляться в релизе и использовать его как уязвимость. Проблема сводится к качественному тестированию, что сложно. Инструменты, такие, как afl-fuzz хороши, но они вряд ли даже начали затрагивать большие программы. Один из способов для того, чтобы обойти проблему тестирования, заключается в том, чтобы использовать статические инструменты обнаружения UB. Они непрерывно совершенствуются, но уверенный и точный статический анализ не обязательно проще сделать, чем достичь хорошего тестового покрытия. Конечно, две этих техники направлены на решение одной проблемы, идентификации возможных путей исполнения программы, но с разных сторон. Эта проблема всегда была очень сложна, и, возможно, всегда таковой будет. Было написано очень много о нахождении UB путём статического анализа, в этой статье мы сфокусируемся на на динамических инструментах. Другой путь решения проблемы тестирования — это использования инструментов «смягчения» UB: они превращают неопределённое поведение в определённое при использовании C и C++, эффективно достигая некоторых преимуществ использования безопасных языков программирования. Трудности в проектировании инструментов, «смягчающих» UB, следующие:

— не сломать код в «краевых» случаях (corner cases)
— иметь низкие накладные расходы
— не добавлять дополнительных уязвимостей, например, требуя линковки с непроверенной рантайм-библиотекой
— затруднять возможность атаки
— сочетаться друг с другом (в противоположность, некоторые инструменты отладки, такие, как ASan и TSan, не совместимы, и требуют двух запусков тестового набора для проекта, в котором нужны оба инструмента).

Прежде, чем рассматривать отдельные случаи UB, давайте определим наши цели. Они применимы к любому компилятору C и C++.

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

Цель 2: каждый случай UB должен быть либо документирован, либо диагностироваться компилятором как фатальная ошибка, либо иметь опциональный механизм «смягчения», удовлетворяющий предыдущим требованиям. Это сложнее. Мы полагаем, что это может быть достигнуто на многих платформах. Ядра операционных систем и другой код, для которого быстродействие является критически важным, нуждается в использовании других технологий, таких, как формальные методы. В оставшейся части статьи мы рассмотрим текущую ситуацию для различных классов неопределённого поведения.

Начнём с большого класса UB.

Нарушения безопасности пространства памяти (Spatial Memory Safety Violations)

Описание: Доступ за пределы хранилища и даже создание таких указателей является UB в C и C++. В 1988 году червь Морриса намекнул на то, что нас ожидает в следующие N лет. Как мы знаем, N >= 29, и возможно, значение N достигнет 75.

Отладка: Valgrind и ASan являются отличными инструментами отладки. Во многих случаях ASan лучше, потому что вносит меньшие накладные расходы. Оба инструмента представляют адреса как 32- или 64-битные значения, и резервируют запретную красную зону вокруг валидных блоков. Это надёжный подход, он позволяет бесшовно работать с обычными бинарными библиотеками, на использующими данный инструмент, и также поддерживает обычный код, в котором есть операции преобразования указателей в целые.

Valgrind работает из исполняемого кода, не может вставлять красные зоны между стековыми переменными, т.к. размещение объектов на стеке уже закодировано в значениях смещения в инструкциях, обращающихся к стеку, и невозможно поменять адреса обращения к стеку «на лету». В результате, Valgrind имеет ограниченную поддержку в обнаружении ошибок с манипуляцией объектов на стеке. ASan работает во время компиляции и вставляет красные зоны вокруг стековых переменных. Стековые переменные малы и многочисленны, и адресное пространство и соображения локальности предотвращают использование очень больших красных зон. С дефолтными настройками, адреса двух смежных локальных целых переменных x и y будут разделены шестнадцатью байтами. Другими словами, верификации, производимые ASan и Valgrind касаются только размещения объектов в памяти, и размещение объектов при включенной верификации отличается от размещения объектов без применения инструментов верификации.

Некоторый недостаток ASan и Valgrind заключается в том, что они могут пропустить UB, если какой-то код был удалён оптимизатором, и не может быть запущен, как в примере.

Смягчение: У нас давно есть механизм смягчения для небезопасных операций с памятью, включая ASLR, «стековые канарейки», «защищённые аллокаторы», и NX-биты.

ASLR

рандомизация размещения адресного пространства (Address space layout randomization) — технология, применяемая в операционных системах, при использовании которой случайным образом изменяется расположение в адресном пространстве процесса важных структур данных, а именно образов исполняемого файла, подгружаемых библиотек, кучи и стека.
https://en.wikipedia.org/wiki/Address_space_layout_randomization
Прим. перев.

стековые канарейки

«стековые канарейки» (stack canary) — название происходит от канарейки, которую брали с собой шахтёры, чтобы заметить повышенную концентрацию рудничного газа.
Метод защиты от атаки переполнением буфера, при котором перед адресом возврата в стековом фрейме записывается «канареечное значение». Любая попытка переписать адрес, используя переполнение буфера приведёт к тому, что канареечное значение будет переписано и переполнение буфера будет обнаружено.
Прим. перев.

защищённые аллокаторы

«защищённые аллокаторы» (hardened allocators) — аллокаторы памяти в LLVM, предназначенные для дополнительного смягчения уязвимостей, связанных с динамически распределяемой памятью. Подробнее см.: https://llvm.org/docs/ScudoHardenedAllocator.html
Прим. перев.

NX bit

NX bit — Атрибут (бит) NX-Bit (англ. no execute bit) — бит запрета исполнения, добавленный в страницы для реализации возможности предотвращения выполнения данных как кода. Используется для предотвращения уязвимости типа «переполнение буфера». Подробнее см.: https://en.wikipedia.org/wiki/NX_bit
Прим. перев.

Позднее стали доступны production-grade CFI (контроль целостности потока управления). Другая интересная недавняя разработка — это идентификация указателей в ARMv8.3. В этой статье даётся обзор средств смягчения UB, связанных с безопасностью памяти.

Серьёзный недостаток ASan как средства смягчения UB показан здесь:

$ cat asan-defeat.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char a[128];
char b[128];

int main(int argc, char *argv[]) {
  strcpy(a + atoi(argv[1]), "owned.");
  printf("%s\n", b);
  return 0;
}
$ clang-4.0 -O asan-defeat.c
$ ./a.out 128
owned.
$ clang-4.0 -O -fsanitize=address -fno-common asan-defeat.c
$ ./a.out 160
owned.
$

Другими словами, ASan просто заставит атакующего вычислить другое смещение для того, чтобы испортить нужный регион памяти. (Спасибо Юрию Грибову за то, что подсказал, что нужно использовать -fno-common flag в ASan.)

Для того, чтобы смягчить этот вариант неопределённого поведения, должна производиться реальная проверка выхода за границы, а не простая проверка того, что каждый доступ к памяти происходит в валидном регионе. Безопасность памяти является здесь золотым стандартом. Хотя существует много академических работ по безопасности памяти, и некоторые демонстрируют подходы с приемлемыми накладными расходами и хорошей совместимостью с существующим ПО, они не получили широкого распространения. Checked Cis — очень крутой проект в этой области.

Заключение:Инструменты отладки для ошибок такого рода очень хороши. Возможно существенно смягчить этот тип UB, но для того, чтобы полностью его устранить, понадобится полная безопасность типов и памяти.

Нарушение безопасности временных объектов памяти (Temporal Memory Safety Violations)

Описание: Нарушение безопасности временных объектов памяти — это любое использование локации памяти после истечения её времени жизни. Сюда включается адресация автоматических переменных вне области жизни этих переменных, использование после освобождения, использование «висячего» указателя (dangling pointer) для чтения или записи, двойное освобождение, которое может быть очень опасно на практике, т.к. free() изменяет метаданные, которые обычно принадлежат освобождаемому блоку. Если блок уже освобождён, запись в эти данные может повредить данные, используемые для других целей, и, в принципе, может иметь такие же последствия, как любая другая невалидная запись.

Отладка:ASan разработан для обнаружения багов «использование после освобождения», которые часто приводят к трудновоспроизводимому, ошибочному поведению. Он делает такую проверку, помещая освобождённые блоки в «карантин», предотвращая их немедленное переиспользование. Для некоторых программ и входных данных это может увеличить потребление памяти и снизить локальность. Пользователь может сконфигурировать размер карантина, чтобы найти компромисс между ложноположительными срабатываниями и использованием ресурсов.

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

Нарушение безопасности временных объектов памяти в программе ниже вызывает разницу в поведении при дефолтной оптимизации и при -O2. ASan может обнаружить проблему в программе без оптимизации, но только если установлена опция detect_stack_use_after_return, и только если не была скомпилирована с оптимизацией.

$ cat temporal.c
#include <stdio.h>

int *G;

int f(void) {
  int l = 1;
  int res = *G;
  G = &l;
  return res;
}

int main(void) {
  int x = 2;
  G = &x;
  f();
  printf("%d\n", f());
}
$ clang -Wall -fsanitize=address temporal.c
$ ./a.out 
1
$ ASAN_OPTIONS=detect_stack_use_after_return=1 ./a.out 
=================================================================
==5425==ERROR: AddressSanitizer: stack-use-after-return ...
READ of size 4 at 0x0001035b6060 thread T0
^C
$ clang -Wall -fsanitize=address -O2 temporal.c
$ ./a.out 
32767
$ ASAN_OPTIONS=detect_stack_use_after_return=1 ./a.out 
32767
$ clang -v
Apple LLVM version 8.0.0 (clang-800.0.42.1)
...

В некоторых других примерах санитайзер не может обнаружить UB, которое было удалено оптимизатором, и, таким образом, является безопасным, так как удалённый код с UB не может иметь последствий. Но здесь не такой случай! Программа бессмысленна в любом случае, но неоптимизированная программа работает детерминированно, как если бы переменная x была объявлена статической, тогда как оптимизированная программа, в которой ASan не нашёл ничего подозрительного, не ведёт себя детерминированно и раскрывает внутреннее состояние, не предназначенное для того, чтобы его можно было увидеть:

$ clang -Wall -O2 temporal.c
$ ./a.out 
1620344886
$ ./a.out 
1734516790
$ ./a.out 
1777709110

Смягчение: Как обсуждалось выше, ASan не предназначен для защиты от уязвимостей, но различные защищённые аллокаторы доступны, и используют ту же стратегию карантина для того, чтобы закрыть уязвимость «использование после освобождения».

Заключение: Использовать ASan (вместе с “ASAN_OPTIONS=detect_stack_use_after_return=1” для тестирования в небольших случаях). При разных уровнях оптимизации могут ловится ошибки, которые не будут ловиться при других уровнях.

Переполнение целых (Integer Overflow)

Описание: не бывает антипереполнения целых, но может быть переполнение в обоих направлениях. Переполнение знаковых целых, это UB, сюда включается INT_MIN / -1, INT_MIN % -1, минус INT_MIN, сдвиги отрицательных чисел, сдвиг влево числа с единицей после знакового бита, а также (иногда), сдвиг влево числа с единицей в знаковом бите.
Деление на ноль и сдвиг на величину, больше разрядности числа, это UB, как для знаковых, так и для беззнаковых чисел. Также см.: Understanding Integer Overflow in C/C++

Отладка: UBSan — очень хороший инструмент для поиска UB, связанного с целыми числами. Так как UBSan работает на уровне исходников, он очень надёжен. Существуют некоторые странности, относящиеся к вычислениям времени компиляции, например, некоторая программа может ловить исключение, если она скомпилирована как C++11, и не ловить при компиляции в C11, мы думаем, что это соответствует стандартам, но не вдавались в подробности. У GCC есть своя версия UBSan, но ей нельзя доверять на 100%, там константы сворачиваются перед тем, как выполняется проход этого инструмента.

Смягчение: UBSan в «trapping mode» (когда ловится UB, процесс прекращается без вывода диагностики) может быть использован для смягчения UB. Это эффективно и не добавляет уязвимостей. Частично Android использует UBSan для смягчения этого типа UB. Хотя переполнение целых, это, в основном, логическая ошибка, в C и C++ такие ошибки особенно опасны, потому что могут привести к нарушениям безопасности памяти. В языках с безопасным доступом к памяти, они гораздо менее опасны.

Заключение: Целочисленное UB не очень сложно отловить, UBSan, это всё, что вам для этого нужно. Проблема в том, что смягчение целочисленного UB приводит к появлению избыточности. Например, при этом SPEC CPU 2006 выполняется на 30% медленнее. Здесь много мест для улучшения, и устранение проверок переполнения там, где оно не может повредить, и сделать остальные проверки менее мешающими для оптимизатора циклов. Кто, то, обладающий достаточными ресурсами, должен сделать это.

Strict Aliasing Violations

Описание: Правила “strict aliasing" в стандартах C и C++ позволяют компилятору позволяют компилятору предполагать, что если два указателя ссылаются на разные типы, они не указывают на один объект. Это позволяет выполнять прекрасные оптимизации, но есть риск поломать программы с более гибким взглядом на вещи (а это, по приблизительным оценкам, 100% больших программ на C и C++). Для более подробного обзора см. раздел 1-3 этой статьи (будет опубликовано в следующей части. прим. перев.).

Отладка: Текущее состояние инструментов отладки для нарушений «strict aliasing» слабое. Компиляторы выдают предупреждения в некоторых простых случаях, но эти предупреждения очень ненадёжны. libcrunch предупреждает, что указатель преобразован в тип «указатель на что-то», хотя фактически указывает на что-то другое. Это позволяет выполнять преобразования типов через указатель на void, но отлавливает неверные преобразования указателей, которые также являются этим типом UB. благодаря стандарту C и тому, как компиляторы С интерпретируют, что они могут сделать при оптимизации TBAA (type-based alias analysis), libcrunch не является ни надёжным (он не отлавливает некоторые нарушения, которые происходят при выполнении программы), ни полным (он предупреждает о преобразовании указателей, если оно выглядит подозрительно, но не нарушает стандарт).

Смягчение: Это просто: передаёте компилятору флаг (-fno-strict-aliasing), и он отключает оптимизацию, основанную на strict aliasing. В результате компилятор опирается на старую добрую модель памяти, где могут выполняться более или менее произвольные преобразования между типами указателей, и результирующий код ведёт себя, как ожидалось. Из «большой тройки», такому UB подвержены только GCC и LLVM, MSVC не реализует такой класс оптимизаций.

Заключение: Чувствительный к данному UB код нуждается в тщательной проверке: всегда подозрительно и опасно преобразовывать указатели во что-то, кроме char *. Как альтернатива, можно просто выключить оптимизацию TBAA, используя флаг, и убедившись, что никто не скомпилирует код без использования этого флага.

Нарушение выравнивания (Alignment Violations)

Описание: RISC-процессоры имеют тенденцию запрещать доступ к памяти по невыровненным адресам. С другой стороны, программы C и C++, с использованием невыровненного доступа, имеют UB, вне зависимости от целевой архитектуры. Исторически мы смотрели на это сквозь пальцы, вначале потому, что x86/x64 поддерживает невыровненный доступ, во-вторых, потому, что компиляторы до сих пор не использовали это UB для оптимизаций. Но и в этом случае, есть прекрасная статья, объясняющая, как компилятор может сломать код с невыровненным доступом на x64. Код в статье нарушает strict aliasing, в добавок к нарушению выравнивания, и падает (проверялось на GCC 7.1.0 в OS X), несмотря на флаг -fno-strict-aliasing.

Отладка: UBSan может обнаруживать нарушения выравнивания.

Смягчение: неизвестно

Заключение: используйте UBSan

Циклы, не выполняющие операций ввода-вывода и не завершающиеся (Loops that Neither Perform I/O nor Terminate)

Описание: Циклы в коде C или C++, не выполняющие операций ввода-вывода и не завершающиеся, являются неопределёнными и могут быть произвольно завершены компилятором. См. эту статью и эту заметку.

Отладка: нет инструментальных средств

Смягчение: Нет, кроме избегания слишком сильно оптимизирующих компиляторов.

Заключение: Это UB не является проблемой практического характера (даже если и неприятно для кого-то из нас).

Состязания данных (Data Races)

Описание: состязания данных происходят, когда участок памяти доступен более чем одному потоку, и как минимум одному из них — на запись, и доступ не синхронизирован механизмами типа блокировок. Состязания данных приводят к UB в современных версиях C и C++ (они не имеют смысла в старых версиях, так как эти стандарты не описывали многопоточный код).

Прим. перев.

Здесь я не соглашусь с автором, так как многопоточный код мог быть запущен с помощью API операционной системы, такого, как, например, POSIX Threads, и это можно сделать в любых версиях C и C++, неважно, насколько старых. Также код, обрабатывающий прерывания в микроконтроллере, может приводить к аналогичным эффектам при совместном доступе к данным с основным циклом программы. Это также не зависит от года стандарта C и С++. Прим. перев.

Описание: TSan — прекрасный детектор динамических состязаний памяти. Существуют другие похожие инструменты, такие, как плагин Helgrind для Valgrind, но мы их не использовали в последнее время. Использование детекторов динамических состязаний осложняется фактом, что состязание очень трудно заставить сработать, и хуже всего то, что их срабатывание зависит от количества ядер, алгоритма планировщика потоков, от того, что ещё запущено на тестовой машине, от фаз луны и т.д.

Смягчение: не создавайте потоков

Заключение: Для этого конкретного UB есть хорошая идея: если вам не нравятся объекты блокировки, то не используйте код, выпоняющийся параллельно, используйте вместо него атомарные действия.

Модификации с нарушением точек следования (Unsequenced Modifications)

Описание: В С, «точка следования» ограничивает то, насколько рано или поздно выражение с побочным эффектом, такое, как x++, возымеет эффект. C++ имеет другую, но более-менее эквивалентную формулировку этого правила. В обоих языках, модификации с нарушением точек следования приводят к UB.

Отладка: некоторые компиляторы генерируют предупреждение при очевидных нарушениях правил следования:

$ cat unsequenced2.c
int a;

int foo(void) {
  return a++ - a++;
}
$ clang -c unsequenced2.c
unsequenced2.c:4:11: warning: multiple unsequenced modifications to 'a' [-Wunsequenced]
  return a++ - a++;
          ^     ~~
1 warning generated.
$ gcc-7 -c unsequenced2.c -Wall
unsequenced2.c: In function 'foo':
unsequenced2.c:4:11: warning: operation on 'a' may be undefined [-Wsequence-point]
   return a++ - a++;
          ~^~

Однако, небольшое косвенное нарушение не вызывает предупреждений:

$ cat unsequenced.c
#include <stdio.h>

int main(void) {
  int z = 0, *p = &z;
  *p += z++;
  printf("%d\n", z);
  return 0;
}
$ gcc-4.8 -Wall unsequenced.c ; ./a.out
0
$ gcc-7 -Wall unsequenced.c ; ./a.out
1
$ clang -Wall unsequenced.c ; ./a.out
1

Смягчени��: Неизвестно, однако можно почти тривиально определить порядок, в котором будут выполняться побочные эффекты. Язык Java является примером того, как это делается. У нас был трудный период, когда мы верили, что такое ограничение помешает любому современному оптимизирующему компилятору. Если комитет по стандартизации поверит от всего сердца, что это не так, разработчики компиляторов должны будут следовать правилам. В идеале, все основные компиляторы должны в таких случаях поступать одинаково.

Заключение: С некоторой практикой, не очень сложно заметить потенциальное нарушение точек следования при кодревью. Мы должны беспокоиться при виде очень сложных выражений с побочными эффектами. Это бывает в легаси-коде, но посмотрите, он же до сих пор работает, значит, возможно, это не проблема. На самом деле, эта проблема должна быть исправлена в компиляторах.

Не-UB, относящееся к нарушениям точек следования является «неопределённой последовательностью» (indeterminately sequenced), в которой операторы могут выполняться в порядке, задаваемом компилятором. Примером служит порядок вызова двух функций при вычислении f(a(), b()). Этот порядок должен быть определён тоже. Слева направо, например. Здесь не будет никаких потерь быстродействия, если не рассматривать совсем безумные ситуации.

Продолжение следует.

UB-2017. Часть 1