Как тестируется SQLite

1. Введение

Надежность и устойчивость SQLite частично достигается благодаря тщательному тестированию.

Начиная с версии 3.42.0 (2023-05-16), библиотека SQLite состоит примерно из 155,8 КСЛОК кода на C. (КСЛОК означает тысячи «строк исходного кода», или, другими словами, строк кода без учёта пустых строк и комментариев). Для сравнения, у проекта в 590 раз больше кода и сценариев тестов — 92053,1 КСЛОК.

1.1. Резюме

• Четыре независимо разработанные тестовые среды
• 100% покрытие тестами ветвей в рабочей конфигурации
• Миллионы и миллионы тестовых случаев
• Тесты на нехватку памяти
• Тесты на ошибки ввода-вывода
• Тесты на сбои и отключение питания
• Тесты на уязвимости (fuzz tests)
• Тесты на граничные значения
• Тесты с отключённой оптимизацией
• Регрессионные тесты
• Тесты на повреждённые файлы базы данных
• Широкое использование assert() и проверок во время выполнения
• Анализ Valgrind
• Проверки на неопределённое поведение
• Списки проверок

2. Тестовые среды

Для тестирования ядра библиотеки SQLite используются четыре независимые тестовые среды. Каждая среда разработана, поддерживается и управляется отдельно от других.

1. Тесты TCL — оригинальные тесты для SQLite. Они находятся в одном каталоге с ядром SQLite и, как и ядро SQLite, находятся в общественном доступе. Тесты TCL являются основными тестами, используемыми во время разработки. Тесты TCL написаны на языке сценариев TCL. Сама тестовая среда TCL состоит из 27,2 КСЛОК кода на C, используемого для создания интерфейса TCL. Тестовые сценарии содержатся в 1390 файлах размером 23,2 МБ. Существует 51445 различных тестовых случаев, но многие тестовые случаи параметризованы и выполняются несколько раз (с различными параметрами), так что при полном запуске теста выполняется миллионы отдельных тестов.

2. Тестовая среда TH3 — набор закрытых тестов, написанных на C, которые обеспечивают 100% покрытие тестами ветвей (и 100% покрытие тестами MC/DC) для ядра библиотеки SQLite. Тесты TH3 разработаны для выполнения на встроенных и специализированных платформах, которые не поддерживают TCL или другие сервисы рабочих станций. Тесты TH3 используют только опубликованные интерфейсы SQLite. TH3 состоит примерно из 76,9 МБ или 1055,4 КСЛОК кода на C, реализующего 50362 различных тестовых случаев. Тесты TH3 сильно параметризованы, поэтому полный тест с полным охватом выполняет около 2,4 миллиона различных тестовых экземпляров. Случаи, обеспечивающие 100% покрытие по ветвям, составляют подмножество всего набора тестов TH3. Тест в режиме ожидания перед выпуском выполняет около 248,5 миллионов тестов. Дополнительная информация о TH3 доступна отдельно.

3. Тест SQL Logic или SLT используется для запуска огромного количества SQL-запросов как против SQLite, так и против нескольких других SQL-баз данных и проверки того, что все они получают одинаковые ответы. В настоящее время SLT сравнивает SQLite с PostgreSQL, MySQL, Microsoft SQL Server и Oracle 10g. SLT выполняет 7,2 миллиона запросов, занимающих 1,12 ГБ тестовых данных.

4. Двигатель dbsqlfuzz — это закрытый фьюзер. Другие фьюзеры для SQLite изменяют либо входные SQL-данные, либо файл базы данных. Dbsqlfuzz изменяет одновременно и SQL, и файл базы данных, и поэтому способен достигать новых состояний ошибок. Dbsqlfuzz построен с использованием фреймворка libFuzzer LLVM с настраиваемым мутатором. Есть 336 файлов-зародышей. Фьюзер dbsqlfuzz выполняет около миллиарда тестовых мутаций в день. Dbsqlfuzz помогает обеспечить устойчивость SQLite к атакам с использованием вредоносных SQL-запросов или входных данных базы данных.

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

5. Программа «speedtest1.c» оценивает производительность SQLite в типичной рабочей нагрузке.
6. Программа «mptester.c» — это стресс-тест для нескольких процессов, которые одновременно читают и записывают в одну базу данных.
7. Программа «threadtest3.c» — это стресс-тест для нескольких потоков, одновременно использующих SQLite.
8. Программа «fuzzershell.c» используется для запуска некоторых тестов на уязвимости.
9. Программа «jfuzz» — это фьюзер на основе libfuzzer для входных данных JSONB для функций JSON SQL.

Все вышеперечисленные тесты должны успешно выполняться на нескольких платформах и в нескольких конфигурациях времени компиляции перед каждым выпуском SQLite.

Перед каждым коммитом в исходный код SQLite разработчики обычно запускают подмножество (называемое «veryquick») тестов TCL, состоящее из примерно 304,7 тысяч тестовых случаев. Тесты veryquick включают большинство тестов, кроме тестов на аномалии, тестов на уязвимости и тестов в режиме ожидания. Идея тестов veryquick заключается в том, что их достаточно для обнаружения большинства ошибок, но они также выполняются всего за несколько минут, а не за несколько часов.

3. Тестирование на аномалии

Тесты на аномалии — это тесты, предназначенные для проверки корректного поведения SQLite при возникновении проблем. Довольно легко создать движок SQL-базы данных, который корректно работает с правильно сформированными входными данными на работоспособном компьютере. Сложнее создать систему, которая разумно реагирует на некорректные входные данные и продолжает функционировать после сбоев системы. Тесты на аномалии предназначены для проверки последнего поведения.

3.1. Тестирование на нехватку памяти

SQLite, как и все движки SQL-баз данных, широко использует malloc() (подробности о динамическом выделении памяти в SQLite см. в отдельном отчёте по этой теме). На серверах и рабочих станциях malloc() практически никогда не терпит неудачу, и поэтому правильная обработка ошибок нехватки памяти (OOM) не является особенно важной. Однако на встроенных устройствах ошибки OOM встречаются довольно часто, и поскольку SQLite часто используется на встроенных устройствах, важно, чтобы SQLite мог корректно обрабатывать ошибки OOM.

Тестирование на OOM выполняется путём имитации ошибок OOM. SQLite позволяет приложению подставить альтернативную реализацию malloc() с помощью интерфейса sqlite3_config(SQLITE_CONFIG_MALLOC,...). Тестовые среды TCL и TH3 способны вставлять изменённую версию malloc(), которую можно настроить на ошибку после определённого количества выделений. Эти инструментированные malloc() можно настроить на ошибку только один раз, а затем начать работать снова, или продолжать ошибаться после первой ошибки. Тесты OOM выполняются циклически. На первой итерации цикла инструментированный malloc() настроен на ошибку при первом выделении. Затем выполняется некоторая операция SQLite, и проверяется, что SQLite корректно обработала ошибку OOM. Затем счётчик времени до ошибки в инструментированном malloc() увеличивается на единицу, и тест повторяется. Цикл продолжается до тех пор, пока вся операция не завершится без возникновения имитированной ошибки OOM. Такие тесты выполняются дважды: один раз с настроенным на ошибку только один раз инструментированным malloc(), а другой раз — с инструментированным malloc(), настроенным на постоянные ошибки после первой.

3.2. Тестирование на ошибки ввода-вывода

Тестирование ошибок ввода-вывода направлено на проверку того, что SQLite корректно реагирует на сбои операций ввода-вывода. Ошибки ввода-вывода могут возникнуть из-за заполненного диска, неисправности аппаратного обеспечения диска, перебоев в сети при использовании сетевой файловой системы, изменений конфигурации системы или прав доступа, которые происходят в середине операции SQL, или других проблем с аппаратным обеспечением или операционной системой. В независимости от причины, важно, чтобы SQLite мог правильно реагировать на эти ошибки, и тестирование ошибок ввода-вывода направлено на проверку этого.

Тестирование ошибок ввода-вывода аналогично по концепции тестированию ошибок OOM; имитируются ошибки ввода-вывода, и проводятся проверки для подтверждения того, что SQLite корректно реагирует на имитированные ошибки. Ошибки ввода-вывода имитируются в тестовых средах TCL и TH3 путем вставки нового объекта виртуальной файловой системы, специально настроенного для имитации ошибки ввода-вывода после определенного количества операций ввода-вывода. Как и при тестировании ошибок OOM, имитаторы ошибок ввода-вывода могут быть настроены на ошибку только один раз или на непрерывную ошибку после первой ошибки. Тесты выполняются в цикле, постепенно увеличивая точку сбоя до тех пор, пока тестовый случай не завершится без ошибок. Цикл выполняется дважды: один раз с настройкой имитатора ошибок ввода-вывода на имитацию только одной ошибки, и второй раз — с настройкой на имитацию всех операций ввода-вывода после первой ошибки.

В тестах на ошибки ввода-вывода после отключения механизма имитации ошибки ввода-вывода база данных проверяется с помощью PRAGMA integrity_check, чтобы убедиться, что ошибка ввода-вывода не привела к повреждению базы данных.

3.3. Тестирование на сбои

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

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

В тестовой среде TCL имитация сбоя выполняется в отдельном процессе. Главный процесс тестирования запускает дочерний процесс, который выполняет некоторую операцию SQLite и случайным образом завершается в середине операции записи. Специальная VFS случайным образом меняет порядок и повреждает несброшенные операции записи, чтобы смоделировать эффект буферизованных файловых систем. После завершения работы дочернего процесса исходный тестовый процесс открывает и читает тестовую базу данных и проверяет, что изменения, предпринятые дочерним процессом, либо успешно завершены, либо полностью отменены. Используется pragma integrity_check PRAGMA, чтобы убедиться, что не происходит повреждения базы данных.

Тестовая среда TH3 должна работать на встраиваемых системах, которые не обязательно имеют возможность запускать дочерние процессы, поэтому она использует VFS в оперативной памяти для имитации сбоев. Внутренняя VFS может быть настроена на создание снимка всей файловой системы после определенного количества операций ввода-вывода. Тесты на сбои выполняются в цикле. На каждой итерации цикла точка создания снимка увеличивается до тех пор, пока операции SQLite, которые тестируются, не будут завершены без попадания в момент создания снимка. Внутри цикла, после завершения операции SQLite, файловая система возвращается к снимку, и вводится случайное повреждение файлов, характерное для повреждений, которые можно ожидать после отключения электропитания. Затем база данных открывается и проверяется, чтобы убедиться, что она сформирована правильно, и что транзакция либо завершена, либо полностью отменена. Внутренняя часть цикла повторяется многократно для каждого снимка с разными случайными повреждениями каждый раз.

3.4. Тесты на сложные ошибки

Наборы тестов для SQLite также исследуют результат наложения нескольких ошибок. Например, проводятся тесты для обеспечения правильного поведения, когда ошибка ввода-вывода или ошибка OOM происходит во время попытки восстановления после предыдущего сбоя.

4. Тестирование на уязвимость

Тестирование на уязвимость направлено на установление того, что SQLite правильно реагирует на недействительные, вне диапазона или неправильно сформированные входные данные.

4.1. Тестирование на уязвимость SQL

Тестирование на уязвимость SQL заключается в создании синтаксически корректных, но абсурдных запросов SQL и их подаче в SQLite, чтобы увидеть, как оно будет на них реагировать. Обычно возвращается какая-то ошибка (например, "такой таблицы не существует"). Иногда, совершенно случайно, запрос SQL оказывается семантически корректным. В этом случае подготовленное выражение выполняется, чтобы убедиться, что оно дает разумный результат.

4.1.1. Тестирование на уязвимость SQL с использованием фреймворка American Fuzzy Lop

Концепция тестирования на уязвимость существует уже десятилетия, но эффективным методом поиска ошибок стало только в 2014 году, когда Михал Залевский разработал первый практичный фреймворк с направленным профилированием, American Fuzzy Lop или «AFL». В отличие от предыдущих фреймворков, которые генерировали случайные входные данные, AFL оснащает тестируемую программу (модифицируя выходной код ассемблера компилятора C) и использует эту оснастку для определения того, когда входные данные приводят к выполнению программы по другому пути или циклу с иным количеством повторений. Входные данные, вызывающие новое поведение, сохраняются и далее модифицируются. Таким образом, AFL может «обнаруживать» новое поведение тестируемой программы, в том числе поведение, которое разработчики никогда не задумывали.

AFL проявил эффективность в обнаружении скрытых ошибок в SQLite. Большая часть обнаруженных ошибок связана с утверждениями assert(), где условие было ложным в редких случаях. Но AFL также обнаружил немало случаев аварийного завершения работы в SQLite и даже несколько случаев, когда SQLite вычислял неверные результаты.

Благодаря своим прошлым достижениям AFL стал стандартной частью стратегии тестирования SQLite, начиная с версии 3.8.10 (2015-05-07), пока не был заменен более совершенными фреймворками в версии 3.29.0 (2019-07-10).

4.1.2. Google OSS Fuzz

Начиная с 2016 года, команда инженеров Google начала проект OSS Fuzz. OSS Fuzz использует фреймворк с направленным профилированием, работающий на инфраструктуре Google. Фреймворк автоматически загружает последние изменения для участвующих проектов, тестирует их на уязвимость и отправляет разработчикам электронные письма с сообщениями о любых проблемах. Когда исправление вносится, фреймворк автоматически распознает это и отправляет разработчикам подтверждающее письмо.

SQLite — один из многих открытых проектов, которые тестируются OSS Fuzz. Файл исходного кода test/ossfuzz.c в репозитории SQLite является интерфейсом SQLite для OSS Fuzz.

OSS Fuzz больше не находит исторических ошибок в SQLite. Но он все еще работает и иногда находит проблемы в новых изменениях кода. Примеры: [1] [2] [3].

4.1.3. Фреймворки dbsqlfuzz и jfuzz

Начиная с конца 2018 года, SQLite тестировался с помощью закрытого фреймворка «dbsqlfuzz». Dbsqlfuzz построен на базе LibFuzzer из LLVM.

Фреймворк dbsqlfuzz изменяет как входные данные SQL, так и файл базы данных одновременно. Dbsqlfuzz использует пользовательский Structure-Aware Mutator в специализированном файле входных данных, который определяет базу данных и текст SQL, которые должны быть выполнены над этой базой данных. Поскольку он одновременно изменяет как базу данных, так и SQL-входные данные, dbsqlfuzz смог обнаружить некоторые скрытые ошибки в SQLite, которые были пропущены предыдущими фреймворками, которые изменяли только входные данные SQL или только файл базы данных. Разработчики SQLite постоянно запускают dbsqlfuzz на trunk на примерно 16 ядрах. Каждая копия программы dbsqlfuzz способна обрабатывать около 400 тестовых случаев в секунду, что означает, что проверяется около 500 миллионов случаев каждый день.

Фреймворк dbsqlfuzz очень успешно повысил устойчивость кода SQLite к атакам. После добавления dbsqlfuzz в внутренний набор тестов SQLite отчеты об ошибках от внешних фреймворков, таких как OSSFuzz, практически прекратились.

Обратите внимание, что dbsqlfuzz — не основанный на Protobuf фреймворк для направленного тестирования на уязвимость SQLite, который используется Chromium и описан в статье Structure-Aware Mutator. Между этими фреймворками нет связи, кроме того, что они оба основаны на LibFuzzer. Фреймворк для Protobuf SQLite написан и поддерживается командой Chromium в Google, в то время как dbsqlfuzz написан и поддерживается первоначальными разработчиками SQLite. Наличие нескольких независимо разработанных фреймворков для SQLite хорошо, поскольку это означает, что вероятность обнаружения скрытых проблем возрастает.

В конце января 2024 года в использовании появился второй инструмент на основе LibFuzzer, названный «jfuzz». Jfuzz генерирует поврежденные JSONB фрагменты и подаёт их в JSON SQL функции для проверки того, что JSON функции могут безопасно и эффективно обрабатывать поврежденные бинарные входные данные.

4.1.4. Другие фреймворки для тестирования на уязвимость сторонних разработчиков

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

Один исследователь по тестированию на уязвимость, который особенно стоит внимания, это Manuel Rigger. Большинство фреймворков ищут только ошибки в утверждениях, сбои, неопределённое поведение (UB) или другие легко обнаруживаемые аномалии. С другой стороны, фреймворки доктора Риггера могут обнаружить случаи, когда SQLite вычисляет неправильный ответ. Риггер нашел множество таких случаев. Большинство этих находок — это сложные частные случаи, связанные с преобразованием типов и трансформацией аффинной, и немалое количество находок относится к невыпущенным функциям. Тем не менее, его находки все равно важны, поскольку они являются реальными ошибками, и разработчики SQLite признательны за возможность идентифицировать и исправить лежащие в основе проблемы.

4.1.5. Набор тестов fuzzcheck

Исторические тестовые случаи из AFL, OSS Fuzz и dbsqlfuzz собираются в наборе файлов базы данных в основном дереве исходного кода SQLite и затем повторно запускаются программой-утилитой «fuzzcheck» всякий раз, когда выполняется «make test». Fuzzcheck запускает только несколько тысяч «интересных» случаев из миллиардов случаев, проанализированных различными фьюззерами за прошедшие годы. «Интересные» случаи — это случаи, которые демонстрируют ранее невиданное поведение. Фактические ошибки, обнаруженные фьюззерами, всегда включаются в интересные тестовые случаи, но большинство случаев, запущенных fuzzcheck, никогда не были фактическими ошибками.

4.1.6. Напряжение между тестированием fuzz и 100%-ным тестированием MC/DC

Тестирование fuzz и 100%-ное тестирование MC/DC находятся в напряжении друг с другом. Это означает, что код, протестированный на 100% MC/DC, будет, как правило, более уязвим к проблемам, обнаруженным fuzzing, а код, который хорошо работает во время тестирования fuzz, как правило, имеет (намного) меньше, чем 100% MC/DC. Это связано с тем, что тестирование MC/DC препятствует написанию «защитного кода» с недостижимыми ветвями, но без защитного кода фьюзер с большей вероятностью найдет путь, который приведет к проблемам. Тестирование MC/DC, похоже, хорошо работает для создания кода, который устойчив при обычном использовании, в то время как тестирование fuzz хорошо подходит для создания кода, устойчивого к вредоносным атакам.

Конечно, пользователи предпочли бы код, который был бы устойчив как при обычном использовании, так и устойчив к вредоносным атакам. Разработчики SQLite привержены этому. Цель данного раздела — лишь указать, что одновременное выполнение обоих задач затруднено.

В течение большей части своей истории SQLite фокусировался на 100%-ном тестировании MC/DC. Сопротивление атакам fuzz стало проблемой только с появлением AFL в 2014 году. В течение некоторого времени фьюзеры находили много проблем в SQLite. В последние годы стратегия тестирования SQLite эволюционировала, уделяя больше внимания тестированию fuzz. Мы по-прежнему поддерживаем 100% MC/DC ядра SQLite, но большинство циклов процессора, используемых для тестирования, сейчас посвящены fuzzing.

Хотя тестирование fuzz и 100%-ное тестирование MC/DC находятся в напряжении, они не полностью противоречат друг другу. Тот факт, что набор тестов SQlite проходит тестирование на 100% MC/DC, означает, что когда фьюзеры находят проблемы, эти проблемы можно быстро исправить, с минимальным риском введения новых ошибок.

4.2. Некорректные файлы базы данных

Существует множество тестовых случаев, которые проверяют, что SQLite может обрабатывать некорректные файлы базы данных. Эти тесты сначала создают правильный файл базы данных, затем добавляют повреждение, изменяя один или несколько байтов в файле каким-либо способом, отличным от SQLite. Затем используется SQLite для чтения базы данных. В некоторых случаях изменения байтов находятся посередине данных. Это приводит к изменению содержимого базы данных, сохраняя при этом базу данных в правильном формате. В других случаях изменяются неиспользуемые байты файла, что не влияет на целостность базы данных. Интересные случаи возникают, когда изменяются байты файла, определяющие структуру базы данных. Тесты некорректных баз данных проверяют, что SQLite находит ошибки формата файла и сообщает об них, используя код возврата SQLITE_CORRUPT, без переполнения буферов, дереференции указателей NULL или выполнения других нежелательных действий.

Фьюзер dbsqlfuzz также отлично справляется с проверкой того, что SQLite адекватно реагирует на некорректные файлы базы данных.

4.3. Тесты граничных значений

SQLite определяет определенные пределы своей работы, такие как максимальное количество столбцов в таблице, максимальная длина оператора SQL или максимальное значение целого числа. Наборы тестов TCL и TH3 оба содержат множество тестов, которые доводят SQLite до предела его определенных пределов и проверяют, что он работает правильно для всех разрешенных значений. Дополнительные тесты выходят за пределы определенных ограничений и проверяют, что SQLite правильно возвращает ошибки. Исходный код содержит макросы тестовых случаев для проверки того, что были протестированы обе стороны каждого предела.

5. Тестирование на регрессию

Всякий раз, когда поступает сообщение об ошибке в SQLite, эта ошибка считается исправленной только после того, как новые тестовые случаи, которые бы проявили эту ошибку, были добавлены в наборы тестов TCL или TH3. Со временем это привело к тысячам и тысячам новых тестов. Эти тесты на регрессию гарантируют, что ошибки, которые были исправлены в прошлом, не будут повторно введены в будущие версии SQLite.

6. Автоматическое обнаружение утечек ресурсов

Утечка ресурсов происходит, когда системные ресурсы выделены, но никогда не освобождаются. Самые серьезные утечки ресурсов во многих приложениях — это утечки памяти — когда память выделяется с помощью malloc(), но никогда не освобождается с помощью free(). Но могут утечь и другие виды ресурсов: дескрипторы файлов, потоки, мьютексы и т. д.

Как наборы тестов TCL, так и TH3 автоматически отслеживают системные ресурсы и сообщают об утечках ресурсов при каждом запуске теста. Никакой специальной конфигурации или настройки не требуется. Наборы тестов особенно бдительны в отношении утечек памяти. Если изменение приводит к утечке памяти, наборы тестов быстро распознают это. SQLite разработан таким образом, чтобы никогда не допускать утечки памяти, даже после исключительной ситуации, такой как ошибка OOM или ошибка ввода-вывода на диск. Наборы тестов усердны в соблюдении этого.

7. Покрытие тестами

Ядро SQLite, включая unix VFS, имеет 100%-ное покрытие ветвей в TH3 в своей конфигурации по умолчанию, измеренное с помощью gcov. Расширения, такие как FTS3 и RTree, исключены из этого анализа.

7.1. Покрытие операторами против покрытия ветвями

Существует множество способов измерения покрытия тестами. Наиболее популярный показатель — «покрытие операторами». Когда кто-то говорит, что у их программы «XX% покрытия тестами», не объясняя дальше, они, как правило, подразумевают покрытие операторами. Покрытие операторами измеряет процент строк кода, выполненных хотя бы один раз набором тестов.

Покрытие ветвями более строго, чем покрытие операторами. Покрытие ветвями измеряет количество инструкций разветвления машинного кода, оцененных как минимум один раз в обоих направлениях.

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

if( a>b && c!=25 ){ d++; }

Такой оператор C-кода может сгенерировать дюжину отдельных инструкций машинного кода. Если любая из этих инструкций когда-либо оценивается, то мы говорим, что оператор был протестирован. Например, может быть так, что условное выражение всегда ложное и переменная «d» никогда не инкрементируется. Тем не менее, покрытие операторами считает эту строку кода протестированной.

Покрытие ветвями более строгое. В контексте покрытия ветвями каждый тест и каждый подблок внутри оператора рассматриваются отдельно. Для достижения 100%-ного покрытия ветвями в приведённом примере должно быть не менее трёх тестовых случаев:

• a<=b
• a>b && c==25
• a>b && c!=25

Любой из вышеперечисленных тестовых случаев обеспечит 100%-ное покрытие операторами, но все три необходимы для 100%-ного покрытия ветвями. Как правило, 100%-ное покрытие ветвями подразумевает 100%-ное покрытие операторами, но обратное неверно. Для повторного акцента, набор тестов TH3 для SQLite обеспечивает более строгую форму покрытия тестами — 100%-ное покрытие ветвями.

7.2. Тестирование покрытия защитного кода

Хорошо написанная C-программа, как правило, содержит некоторые защитные условные операторы, которые на практике всегда истинны или всегда ложны. Это приводит к проблеме программирования: нужно ли удалять защитный код, чтобы получить 100%-ное покрытие ветвями?

В SQLite ответ на предыдущий вопрос — «нет». Для целей тестирования исходный код SQLite определяет макросы ALWAYS() и NEVER(). Макрос ALWAYS() окружает условия, которые, как ожидается, всегда будут истинными, а NEVER() окружает условия, которые всегда оцениваются как ложные. Эти макросы служат комментариями, указывающими, что условия являются защитным кодом. В релизных сборках эти макросы являются пропусками:

#define ALWAYS(X)  (X)
#define NEVER(X)   (X)

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

#define ALWAYS(X)  ((X)?1:assert(0),0)
#define NEVER(X)   ((X)?assert(0),1:0)

При измерении покрытия тестами эти макросы определяются как постоянные значения истинности, так что они не генерируют инструкции ветвления языка ассемблера и, следовательно, не участвуют в расчете покрытия ветвями:

#define ALWAYS(X)  (1)
#define NEVER(X)   (0)

Набор тестов разработан для запуска три раза, по одному для каждого определения ALWAYS() и NEVER(), показанных выше. Все три прогона тестов должны давать один и тот же результат. Есть запуск-время теста с использованием интерфейса sqlite3_test_control(SQLITE_TESTCTRL_ALWAYS, ...), который может быть использован для проверки правильности установки макросов в первый вариант (вариант пропуска) для распространения.

7.3. Вынужденное покрытие граничных значений и тестов булевых векторов

Другой макрос, используемый в сочетании с измерением покрытия тестами, — это макрос testcase(). Аргументом является условие, для которого мы хотим тестовых случаев, которые оцениваются как истинные и ложные. В сборках без учета покрытия (то есть в релизных сборках) макрос testcase() является пустой операцией:

#define testcase(X)

Но в сборке, измеряющей покрытие, макрос testcase() генерирует код, который оценивает условное выражение в своём аргументе. Затем во время анализа проверяется, существуют ли тесты, которые оценивают условное выражение как истинное и ложное. Макросы Testcase() используются, например, для проверки того, что проверены граничные значения. Например:

testcase( a==b );
testcase( a==b+1 );
if( a>b && c!=25 ){ d++; }

Макросы тестовых случаев также используются, когда два или более случая оператора switch идут в один и тот же блок кода, чтобы убедиться, что код был достигнут для всех случаев:

switch( op ){
  case OP_Add:
  case OP_Subtract: {
    testcase( op==OP_Add );
    testcase( op==OP_Subtract );
    /* ... */
    break;
  }
  /* ... */
}

Для тестов с масками битов используются макросы testcase() для проверки того, что каждый бит маски влияет на результат. Например, в следующем блоке кода условие истинно, если маска содержит любой из двух битов, указывающих на то, что открывается база данных MAIN_DB или TEMP_DB. Макросы testcase() перед оператором if проверяют, что оба случая протестированы:

testcase( mask & SQLITE_OPEN_MAIN_DB );
testcase( mask & SQLITE_OPEN_TEMP_DB );
if( (mask & (SQLITE_OPEN_MAIN_DB|SQLITE_OPEN_TEMP_DB))!=0 ){ ... }

Исходный код SQLite содержит 1184 использования макроса testcase().

7.4. Покрытие ветвями против MC/DC

Выше были описаны два метода измерения покрытия тестами: «операторное» и «ветви». Есть много других метрик покрытия тестами помимо этих двух. Ещё одна популярная метрика — «Модифицированное покрытие условий/решений» или MC/DC. Wikipedia определяет MC/DC следующим образом:

• Каждое решение пытается перебрать все возможные исходы.
• Каждое условие в решении принимает каждый возможный исход.
• Каждый входной и выходной пункт вызывается.
• Каждое условие в решении демонстрирует независимое влияние на результат решения.

В языке программирования C, где && и || являются операторами "короткого замыкания", MC/DC и покрытие ветвей очень похожи. Основное различие заключается в тестах с вектором булевых значений. Можно проверить любой из нескольких битов в битовом векторе и при этом получить 100% покрытие тестов ветвей, даже если второе требование MC/DC – каждое условие в решении должно принимать каждый возможный исход – не выполняется.

SQLite использует макросы testcase() (как описано в предыдущем подразделе), чтобы убедиться, что каждое условие в решении с битовым вектором принимает каждый возможный исход. Таким образом, SQLite достигает 100% MC/DC в дополнение к 100% покрытию ветвей.

7.5. Измерение покрытия ветвей

Покрытие ветвей в SQLite в настоящее время измеряется с помощью gcov с опцией "-b". Сначала программа тестирования компилируется с опциями "-g -fprofile-arcs -ftest-coverage", затем программа тестирования запускается. Затем запускается "gcov -b" для генерации отчета о покрытии. Отчет о покрытии подробный и неудобен для чтения, поэтому сгенерированный gcov отчет обрабатывается с помощью простых скриптов для придания ему более удобного для чтения формата. Весь этот процесс, конечно, автоматизирован с помощью скриптов.

Обратите внимание, что запуск SQLite с gcov не является тестом SQLite — это тест набора тестов. Запуск gcov не тестирует SQLite, потому что опции -fprofile-args и -ftest-coverage заставляют компилятор генерировать другой код. Запуск gcov просто проверяет, что набор тестов обеспечивает 100% покрытие тестов ветвей. Запуск gcov – это тест на тест – метатест.

После того, как gcov был запущен для проверки 100% покрытия тестов ветвей, программа тестирования перекомпилируется с использованием опций компилятора поставляемой версии (без специальных опций -fprofile-arcs и -ftest-coverage) и программа тестирования повторно запускается. Этот второй запуск – это фактический тест SQLite.

Важно убедиться, что запуск gcov и второй реальный запуск дают одинаковый результат. Любые различия в выводе указывают либо на использование неопределенного или неопределенного поведения в коде SQLite (а следовательно, на ошибку), либо на ошибку в компиляторе. Обратите внимание, что за последнее десятилетие SQLite столкнулось с ошибками в GCC, Clang и MSVC. Ошибки компилятора, хотя и редки, происходят, поэтому очень важно тестировать код в конфигурации поставляемой версии.

7.6. Мутационный тест

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

SQLite стремится проверить, что каждая инструкция ветвления оказывает влияние на результат, используя мутационный тест. Скрипт сначала компилирует исходный код SQLite в язык ассемблера (например, используя опцию -S для gcc). Затем скрипт проходит по сгенерированному языку ассемблера и по одному изменяет каждую инструкцию ветвления либо на безусловный переход, либо на пустую операцию, компилирует результат и проверяет, что набор тестов обнаруживает мутацию.

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

55  static unsigned int strHash(const char *z){
56    unsigned int h = 0;
57    unsigned char c;
58    while( (c = (unsigned char)*z++)!=0 ){     /*OPTIMIZATION-IF-TRUE*/
59      h = (h<<3) ^ h ^ sqlite3UpperToLower[c];
60    }
61    return h;
62  }

Если инструкция ветвления, реализующая проверку "c!=0" на строке 58, будет изменена на пустую операцию, то цикл while будет выполняться бесконечно, и набор тестов завершится с таймаутом. Но если эта ветвь будет изменена на безусловный переход, то функция хэширования всегда будет возвращать 0. Проблема в том, что 0 – это допустимое значение хэша. Функция хэширования, которая всегда возвращает 0, все равно работает в том смысле, что SQLite все равно всегда получает правильный ответ. Таблица хэшей имен таблиц вырождается в связанный список, поэтому запросы поиска имен таблиц, которые выполняются во время анализа SQL-запросов, могут быть немного медленнее, но конечный результат будет таким же.

Для решения этой проблемы в исходный код SQLite вставляются комментарии вида "/*OPTIMIZATION-IF-TRUE*/" и "/*OPTIMIZATION-IF-FALSE*/", чтобы указать скрипту мутационного тестирования игнорировать некоторые инструкции ветвления.

7.7. Опыт работы с полным покрытием тестов

Разработчики SQLite обнаружили, что полное тестирование с полным покрытием – очень эффективный метод выявления и предотвращения ошибок. Поскольку каждый отдельный инструкцией ветвления в ядре SQLite покрывается тестовыми случаями, разработчики могут быть уверены, что изменения, внесенные в одной части кода, не имеют непредвиденных последствий в других частях кода. Многие новые функции и улучшения производительности, добавленные в SQLite в последние годы, были бы невозможны без наличия тестирования с полным покрытием.

Поддержание 100% MC/DC является трудоемким и длительным процессом. Уровень усилий, необходимый для поддержания тестирования с полным покрытием, вероятно, не является экономически эффективным для типичного приложения. Однако мы считаем, что полное тестирование с полным покрытием оправдано для широко используемой инфраструктурной библиотеки, такой как SQLite, и особенно для библиотеки баз данных, которая по своей природе «запоминает» прошлые ошибки.

8. Динамический анализ

Динамический анализ относится к внутренним и внешним проверкам кода SQLite, которые выполняются во время выполнения кода. Динамический анализ доказал свою эффективность в поддержании качества SQLite.

8.1. Assert

Ядро SQLite содержит 6754 assert() утверждения, которые проверяют предварительные и последующие условия функций и инварианты циклов. Assert() – это макрос, который является стандартной частью ANSI-C. Аргументом является булево значение, которое предполагается всегда истинным. Если утверждение ложно, программа выводит сообщение об ошибке и завершается.

Макросы Assert() отключаются при компиляции с определенным макросом NDEBUG. В большинстве систем утверждения включены по умолчанию. Но в SQLite утверждений так много, и они находятся в таких критически важных для производительности местах, что база данных работает примерно в три раза медленнее, когда утверждения включены. Поэтому в стандартной (производственной) сборке SQLite утверждения отключены. Утверждения включаются только при компиляции SQLite с предварительно определенным макросом препроцессора SQLITE_DEBUG.

Дополнительную информацию о том, как SQLite использует assert(), см. в документе Использование assert в SQLite.

8.2. Valgrind

Valgrind – пожалуй, самый удивительный и полезный инструмент для разработчиков в мире. Valgrind – это симулятор; он моделирует работу x86 под Linux. (Порты Valgrind для платформ, отличных от Linux, разрабатываются, но на момент написания этой статьи Valgrind работает надежно только под Linux, что, по мнению разработчиков SQLite, означает, что Linux должна быть предпочтительной платформой для всех разработок программного обеспечения.) При выполнении Linux-бинарника с помощью Valgrind он ищет всевозможные интересные ошибки, такие как выход за границы массива, чтение из неинициализированной памяти, переполнение стека, утечки памяти и т. д. Valgrind находит проблемы, которые легко могут пройти мимо всех остальных тестов, выполняемых для SQLite. И когда Valgrind обнаруживает ошибку, он может немедленно перевести разработчика в символьную отладку в точном месте возникновения ошибки, чтобы ускорить исправление.

Поскольку это симулятор, выполнение бинарника с помощью Valgrind медленнее, чем на базовом оборудовании. (Приблизительно, приложение, выполняемое с помощью Valgrind на рабочем станций, будет работать примерно так же, как и на смартфоне.) Поэтому непрактично запускать весь набор тестов SQLite через Valgrind. Тем не менее, очень быстрые тесты и покрытие тестов TH3 запускаются через Valgrind перед каждым выпуском.

8.3. Memsys2

SQLite содержит подключаемый подсистему выделения памяти. По умолчанию используется системная функция malloc() и free(). Однако, если SQLite скомпилирован с SQLITE_MEMDEBUG, вставляется альтернативный обёртку выделения памяти (memsys2), которая ищет ошибки выделения памяти во время выполнения. Обёртка memsys2 проверяет утечки памяти, а также выход за границы буфера, использование неинициализированной памяти и попытки использовать память после ее освобождения. Те же проверки также выполняет valgrind (и, собственно, Valgrind делает их лучше), но у memsys2 есть преимущество в том, что она намного быстрее, чем Valgrind, что означает, что проверки можно выполнять чаще и для более длительных тестов.

8.4. Утверждения для мьютексов

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

8.5. Тесты журнала

Одним из способов, которые SQLite использует для обеспечения атомарности транзакций при сбоях системы и отключении питания, является запись всех изменений в файл журнала отката перед изменением базы данных. Тестовый фреймворк TCL содержит альтернативное реализация бэкэнда ОС, которая помогает проверить, что это происходит правильно. "VFS тестирования журнала" отслеживает все операции ввода-вывода с диска между файлом базы данных и журналом отката, проверяя, чтобы ничего не было записано в файл базы данных до тех пор, пока это не будет сначала записано и синхронизировано с журналом отката. Если обнаружатся какие-либо расхождения, возникнет ошибка утверждения.

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

8.6. Проверка на неопределенное поведение

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

• Переполнение целых чисел со знаком. (Переполнение целых чисел со знаком не обязательно приводит к циклическому переходу, как ожидают большинство людей.)
• Сдвиг N-битного целого числа более чем на N бит.
• Сдвиг на отрицательное значение.
• Сдвиг отрицательного числа.
• Использование функции memcpy() с перекрывающимися буферами.
• Порядок вычисления аргументов функции.
• Являются ли переменные типа «char» со знаком или без знака.
• И так далее...

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

Для обеспечения того, чтобы SQLite не использовал неопределённое или определяемое реализацией поведение, наборы тестов повторно выполняются с помощью инструментированных сборок, которые пытаются обнаружить неопределённое поведение. Например, наборы тестов выполняются с опцией «-ftrapv» GCC. И они выполняются ещё раз с опцией «-fsanitize=undefined» в Clang. И снова с опцией «/RTC1» в MSVC. Затем наборы тестов выполняются повторно с опциями типа «-funsigned-char» и «-fsigned-char», чтобы убедиться, что различия в реализации также не имеют значения. Тесты затем повторяются на 32- и 64-битных системах и на системах с большим и малым порядком байтов, используя различные архитектуры процессоров. Кроме того, наборы тестов дополнены множеством тестовых случаев, специально разработанных для провоцирования неопределённого поведения. Например: «SELECT -1*(-9223372036854775808);».

9. Тесты с отключённой оптимизацией

Интерфейс sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS, ...) позволяет отключать выбранные оптимизации операторов SQL во время выполнения. SQLite всегда должен генерировать точно такой же ответ с включённой и выключенной оптимизацией; ответ просто приходит быстрее с включённой оптимизацией. Поэтому в производственной среде оптимизации всегда оставляют включёнными (по умолчанию).

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

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

10. Списки проверок

Разработчики SQLite используют онлайн-список проверок для координации тестирования и проверки того, что все тесты пройдены перед каждым выпуском SQLite. Прошлые списки проверок сохраняются для исторической справки. (Списки проверок доступны только для чтения анонимным пользователям интернета, но разработчики могут войти и обновить пункты списка проверок в своих браузерах.) Использование списков проверок для тестирования SQLite и других видов деятельности по разработке вдохновлено Манифестом чек-листов .

Последние списки проверок содержат приблизительно 200 пунктов, которые индивидуально проверяются для каждого выпуска. Некоторые пункты списка проверок занимают всего несколько секунд для проверки и пометки. Другие включают наборы тестов, которые выполняются много часов.

Список проверок выпуска не автоматизирован: разработчики вручную выполняют каждый пункт в списке проверок. Мы считаем важным сохранять человека в цикле. Иногда проблемы обнаруживаются при выполнении пункта списка проверок, даже если сам тест пройден. Важно, чтобы человек проверял выходные данные теста на самом высоком уровне и постоянно спрашивал: «Это действительно правильно?»

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

11. Статический анализ

Статический анализ означает анализ исходного кода во время компиляции для проверки правильности. Статический анализ включает сообщения об ошибках компилятора и более глубокие средства анализа, такие как Clang Static Analyzer. SQLite компилируется без предупреждений в GCC и Clang с флагами -Wall и -Wextra в Linux и Mac и в MSVC в Windows. Инструмент Clang Static Analyzer "scan-build" также не генерирует никаких допустимых предупреждений (хотя последние версии clang, похоже, генерируют много ложных срабатываний). Тем не менее, некоторые предупреждения могут быть сгенерированы другими средствами статического анализа. Пользователям рекомендуется не беспокоиться по поводу этих предупреждений и вместо этого утешиться интенсивным тестированием SQLite, описанным выше.

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

12. Заключение

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

Эта страница была в последний раз изменена 13 марта 2024 г. в 17:43:35 UTC