Мутационное тестирование c Mull

Давно хотел попробовать мутационное тестирование (далее MT) в деле и всё никак не получалось.

Здесь я не буду описывать, что такое мутационное тестирование. Если интересно, то воспользуйтесь списком ссылок внизу статьи. Отмечу только два факта: количество публикаций о MT и количество программ, которые тестировали с помощью MT, показывают, что интерес к MT неуклонно растёт с 1988 года. В разных научных статьях фигурирует цифра в 70-90% реальных дефектов, найденных с помощью MT. Мне этого достаточно, чтобы заинтересоваться MT и попробовать на одном из реальных проектов.

В прошлом году предоставилась возможность это сделать. Знакомые ребята активно работали над инструментом для MT - Mull и у них уже была рабочая версия. Mull использует LLVM для получения IR любого исходного кода, который поддерживается в LLVM. Потом мутирует получившийся код, компилирует, запускает юнит-тесты и анализирует результаты. На тот момент для использования Mull нужна была поддержка последней версии clang в проекте, тесты на Google Test и свободное время. Я тогда работал над коммерческим проектом, который написан на C++, имел хорошее покрытие юнит-тестами на Google Test - около 80% и для сборки использовалась одна из последних версий clang. Проект как нельзя лучше подходил для эксперимента с Mull.

Разработчики Mull не поленились написать инструкции по использованию для CentOS и Ubuntu и установка прошла без особых проблем. А дальше начались проблемы.

Для использования Mull нужна версия LLVM c поддержкой LTO (>=3.9). Мы в проекте использовали не общесистемный компилятор, а из своего тулчейна. И версия LLVM там была не самая последняя. Эксперимент пришлось поставить на паузу до тех пор, пока не обновили тулчейн. Дождавшись планового обновления тулчейна я начал разбираться в сборочной инфраструктуре проекта, чтобы понять как добавить опции для сборки всего проекта с поддержкой LTO. После добавления опций после сборки стали появляться файлы с LLVM Bitcode вместо объектных файлов ELF. Теперь всё было готово для первого запуска Mull.

Для конфигурационного файла я взял за основу тестовый конфиг и немного отредактировал:

bitcode_file_list: MULL_BITCODE_FILES
project_name: PROJECT
max_distance: 1
fork: true
exclude_locations:
- XXX
  • bitcode_file_list - файл со списком всех bc файлов (find . -name "*.bc")
  • max_distance - по-моему это расстояние между мутациями в одном файле. Оптимизация, чтобы не делать слишком много мутаций.
  • fork - запуск мутантов происходит в дочерних процессах (на случай крэша или таймаута), лучше выставить в true.

Запуск: /opt/mull-driver/bin/mull-driver config.yml

После непродолжительной работы OOM-киллер отстреливает процесс Mull.

[1122049.396117] Out of memory: Kill process 16802 (mull-driver) score 483 or sacrifice child
[1122049.396123] Killed process 16802 (mull-driver) total-vm:1999272kB, anon-rss:816808kB, file-rss:36kB, shmem-rss:0kB

В ходе переписки с авторами Mull выясняю, что мутации пока выполняются последовательно и распараллеливание пока только в планах (сейчас уже исправлено и запуск тестов происходит параллельно):

alexdenisov [4:48 PM]
это так из-за мутантов, над этим тоже работаем есть более грамотный способ, но
на данный момент это tradeoff между памятью и скоростью сейчас каждый мутант
создает копию модуля в котором он находится, и эта копия висит в памяти
(ограничение LLVM такое) более грамотный способ это выкусывать только те
функции которые требуют выполнения, это должно разительно снизить и потребление
памяти и увеличить саму скорость выполнения, вот я как раз над этим работаю
сейчас, но там не очень тривиальное решение, требует времени

Я попробовал ограничить количество тестов одной группой тестов, с которыми работает Mull в конфиге и указать явно какие мутации мне интересны:

tests:
  - gtest_active_component_controller

add_mutation_operator
negate_mutation_operator
remove_void_function_mutation_operator

В этот раз тестирование завершается с другой ошибкой:

LLVM ERROR: Cannot select: 0x23e592060: i64 = X86ISD::WrapperRIP TargetGlobalTLSAddress:i64<i8** @_ZSt15__once_callable> 0 [TF=10]
 0x23e5192e0: i64 = TargetGlobalTLSAddress<i8** @_ZSt15__once_callable> 0 [TF=10]
In function: _ZSt9call_onceIMNSt13__future_base13_State_baseV2EFvPSt8functionIFSt10unique_ptrINS0_12_Result_baseENS4_8_DeleterEEvEEPbEJPS1_S9_SA_EEvRSt9once_flagOT_DpOT0_

Но после этого выяснилось, что ошибка эта известная, LLVM JIT не поддерживает thread local storage (TLS).

На этом я прекратил свои эксперименты с Mull, но желание внедрить мутационное тестирование в какой-то реальный проект всё ещё оставалось.

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

Дополнительные ссылки по теме:

24.11.2018

Обзор UPS для слаботочной электроники

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

Когда я делал дома ремонт, то сделал около входной двери слаботочный щиток и все слаботочные провода из квартиры заведены туда: витая пара, телефонный и телевизионный кабеля. Поэтому все роутеры, коммутаторы и базовая станция DECT стоят внутри щитка. Для всего этого оборудования места в щитке хватает, но так как там помимо самих устройств еще DIN-рейка с розетками и адаптеры питания, то для аккумулятора места остаётся немного. Я решил вернуться к вопросу поиска UPS для своих сетевых железок и выбрать подходящий вариант.

(Полу)Готовые решения

Первая мысль - почему бы не использовать обычные переносные USB-аккумуляторы для телефонов? На Хабре нашел такой ответ на этот вопрос:

Свинцовые аккумы для ИБП рассчитаны на долгий марафонский постепенный разряд; а литиевые АКБ — это «спринтеры». Ну и к тому же держать литиевую батарейку постоянно заряжающейся — стрёмно, а ну как полыхнёт? Свинцовая максимум вспухнет и протечёт. Это неприятно, но несравнимо с пожаром.

Поэтому вариант с такими аккумуляторами я не рассматривал.

Для питания пожарной сигнализации и промышленных систем видеонаблюдения используют ИБП наподобие СКАТ и ШТИЛЬ. У нас в подъезде как раз такая коробка стоит около блока пожарной сигнализации. Для моих требований такие ИБП слишком большие, но можно рассмотреть вариант ИБП Скат с креплением на DIN-рейку и внешним свинцовым аккумулятором и такой вариант был уже интереснее. Отзыв о таком ИБП на Хабре:

Я себе купил Скат на DIN-рейку (SKAT-12-3.0-DIN) + подключил к нему аккумулятор на 17 А/ч — хватить должно на доооолго (10 часов думаю точно вытянет), если учесть что ток роутера + подключенного к нему HDD чуть более 1 ампера… Одно плохо — у линейки SKAT-12-XXX-DIN нет защиты от глубокого разряда, она есть либо в обычных моделях, где аккумулятор ставится в корпус, либо в двухамперной модели на DIN, а мне двух ампер в перспективе может не хватить…

Для CarPC проектов продают программируемые контроллеры питания MINI-BOX OpenUPS. Есть примеры использования таких контроллеров для питания роутера. Но в моём случае с ним приходится платить за фичи, которые мне не нужны (контроль и управление по USB).

Ещё один вариант это использование специального источника питания с функцией UPS и внешними аккумуляторными батареями. Как пример - MeanWell DR-UPS40 + батарея и понижающий блок питания от MeanWell. Большой плюс такого варианта в креплении на DIN-рейку и небольшом форм-факторе, но цена выглядит запределеной. Получается дороже, чем обычный UPS. Вариант блока питания попроще описал, там использовали MeanWell ADD-55A.

ИБП от отечественного производителя - DC Guard 10W. Отзывов про него я не нашёл.

DIY

С ИБП для слаботочной электроники множество схем для самостоятельной сборки. Если есть время и навыки пайки, то можете рассмотреть DYI решения:

Mini UPS System For Router/Mobile Charger – DIY Project

DIY: Mini UPS for DSL Modem and WiFi Routers

“Слаботочка” для домашней сети - дешёвый вариант, но обратите внимание на минусы такого решения.

How to build a cheap UPS for PC Engines ALIX - ИБП на базе батареи типа “Крона”.

Ссылки:

24.11.2018

Разобраться в новом коде

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

После непродолжительного поиска я нашел несколько скриптов, которые рисуют такой граф. На вопрос в твиттере мне подсказали ещё несколько вариантов: doxygen и скрипт graph-llvm-ir для LLVM IR.

Все найденные варианты работают примерно одинаково: строят синтаксическое дерево и на его основе рисуют картинку с графом. При ближайшем рассмотрении выяснилось, что код pycflow2dot давно не обновлялся и не работает с последними версиями питоновских модулей. codeviz тоже давно не обновлялся и у меня не получилось его попробовать. А вот Doxygen оказался очень простым в использовании. Нужно выполнить команду doxygen -g, которая создаст шаблон конфига, потом включить в этом конфиге опции HAVE_DOT, EXTRACT_ALL, EXTRACT_PRIVATE, EXTRACT_STATIC, CALL_GRAPH и запустить doxygen Doxyfile в директории с исходниками. После успешного выполнения программа создаст две директории: latex и html. В первой будут исходники для сборки pdf документа, а во второй документация для просмотра в браузере. Для теста я запускал doxygen в репозитории проекта CRIU (~67 KLOC) и создание документации заняло 4 минуты. Для каждого исходного файла создается отдельный раздел с документации и там можно посмотреть и описания функций, если они аннотированы в коде, и графы взаимосвязей функций. Пользоваться удобно.

01.06.2018

Практикум для изучения ОС

Я решил систематизировать свои знания об устройстве операционных систем и читаю всякие книжки по этой теме. На отсутствие теории не могу жаловаться. А вот с практической стороной у меня сложилось не сразу. Чаще всего советуют для изучения ОС взять исходники Minix или одну из первых версий. Но у Minix очень большая кодовая база, а ядро Линукс это всё-таки еще не операционная система.

Для меня более подходящим полигоном для изучения и экспериментирования стал проект учебной ОС xv6. Это Unix-подобная ОС, которую используют в учебных целях в MIT и других университетах. Запустить её просто - нужно собрать загрузочный образ и загрузить с ним виртуальную машину:

$ make
$ make qemu

Набор пользовательских утилит сильно ограничен, но, например, можно посмотреть список файлов и запустить регресионные тесты:

Помимо исходного кода для xv6 доступен учебник с описанием её устройства.

Ещё один проект, который мне был полезен, это юнит-тесты для KVM. Каждый юнит-тест это простая программа на ассемблере, проверяет “железо”: наличие ACPI таблиц, возможность выделить память, порты ввода-вывода и т.д.

23.02.2018

Карточки Людвига

Когда Студия Артемия Лебедева занялась картой Московского метро, то я читал рассказы арт-директора этого проекта о том, как они делают эту карту. Людвиг пишет интересно и мне нравилось его читать. Недавно зашел на его сайт, который он постоянно переделывает, и мне понравились его Карточки. Я подписался на них по РСС и rss2email прислал мне в почту все девяносто семь записей. Пришлось читать.

Карточки состоят из понравившихся в книгах цитат, а часть - его собственные размышления и наблюдения. Ссылки на самые интересные карточки я привел ниже.

Рецензия на книгу Прохорова “Русская модель управления” - Факторы успеха русской модели управления.

Об экспериментальном подходе Пастера

Два поста про Любищева и его систему: Любищев о своей системе, Краткая справка о системе А.А. Любищева. Если коротко, то Любищев был советским учёным, который научился очень точно планировать своё время и за счёт этого многое успел сделать за свою карьеру. Я про него читал книгу “Эта странная жизнь”, но книжка показалась скучной. Если интересно узнать подробнее, то эти два поста могут быть хорошим введением.

Про ошибки внимания в Атомная подводная лодка против траулера, или Как работает иллюзия внимания. В Японии для борьбы с халатностью и невнимательностью была разработана система “pointing and calling”. Главная идея этой системы заключается в том, что человек в укрепляет умственное действие физическим жестом и голосовым сигналом. Например, машинисту мало посмотреть на зелёный свет, перед тем, как тронуть состав. Он должен указать на светофор, и громко сказать “Зелёный свет, можно ехать”. Таким образом не только он сам более внимательно относится к своим действиям, но и все окружающие видят, что он не забыл проверить важный индикатор, или выполнить пункт техники безопасности.

Кратко о сути психоанализа Фрейда

Токсоплазма — бесстрашный кошачий пассажир. Так я узнал что такое токсоплазма и чем она опасна.

Описание способа организации поездок, который позволит беречь “мыслетопливо” - Спокоен, как авиапассажир.

О смысле жизни невыдающегося математика

Если вы хотя бы раз в жизни пытались завести у себя какую-то привычку, то знаете насколько это иногда бывает сложно сделать. В тяжелых случаях Людвиг советует капнуть маслица.

Об ограниченной эффективности советов

„Буря в пустыне“. Неожиданная стратегия из учебника.

21.12.2017

Универсальный фаззер для грамматик

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

Пожалуй самый известный пример это csmith. Фаззер генерирует синтаксически правильную программу на языке Си и с помощью тестируемого компилятора пытаются эту программу скомпилировать. С помощью csmith нашли семь десятков багов в gcc и пару сотен в LLVM.

Второй пример это sqlsmith. Принцип точно такой же как и у csmith, список багов тоже не маленький - семь десятков.

sqlsmith и csmith имеют одну общую черту - генератор для каждого из них писали отдельно. Писать свой генератор для синтаксиса каждого из демонов OpenBSD мне совсем не хотелось. К тому же синтаксис мог со временем меняться и генератор пришлось бы исправлять.

Ещё один пример это фаззер для CockroachDB. Эта СУБД имеет нестандартную реализацию SQL, поэтому sqlsmith им не подошёл. Грамматика SQL для CockroachDB описывается в формате YACC и они на основе этой грамматики сделали генератор SQL запросов и нашли с ним 82 бага. Из-за того, что генератор использует YACC формат он опять же не является универсальным для разных грамматик.

В OpenBSD для описания грамматики конфигов тоже используется YACC, на основе которого с помощью утилиты yacc генерируется парсер. Пример описания для yacc выглядит так:

%{
#include <stdio.h>
#include <string.h>
 
void yyerror(const char *str)
{
        fprintf(stderr,"error: %s\n",str);
}
 
int yywrap()
{
        return 1;
} 
  
main()
{
        yyparse();
} 

%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE

Мне нужно было YACC-описание преобразовать в более стандартный и читаемый формат, желательно независимый от языков программирования. Таким форматом является BNF - форма Бэкуса-Наура. BNF используется для описания синтаксиса языков программирования, протоколов и т.д. Вот так, например, выглядит описание небольшой части синтаксиса конфига пакетного фильтра в OpenBSD:

line    = ( option | pf-rule | 
          antispoof-rule | queue-rule | anchor-rule | 
          anchor-close | load-anchor | table-rule | include ) 
 
option  = "set" ( [ "timeout" ( timeout | "{" timeout-list "}" ) ] | 
          [ "ruleset-optimization" [ "none" | "basic" | 
          "profile" ] ] | 
          [ "optimization" [ "default" | "normal" | "high-latency" | 
          "satellite" | "aggressive" | "conservative" ] ] 
          [ "limit" ( limit-item | "{" limit-list "}" ) ] | 
          [ "loginterface" ( interface-name | "none" ) ] | 
          [ "block-policy" ( "drop" | "return" ) ] | 
          [ "state-policy" ( "if-bound" | "floating" ) ] 
          [ "state-defaults" state-opts ] 
          [ "fingerprints" filename ] | 
          [ "skip on" ifspec ] | 
          [ "debug" ( "emerg" | "alert" | "crit" | "err" | 
          "warning" | "notice" | "info" | "debug" ) ] | 
          [ "reassemble" ( "yes" | "no" ) [ "no-df" ] ] ) 

yacc не может преобразовать YACC-описание напрямую в BNF форму, но с ключом -v можно преобразовать в описание, удобное для чтения, а потом сделав небольшие преобразования получить описание в EBNF, расширенной BNF форме. EBNF это как раз то, что мне и было нужно. Для чтения EBNF во многих языках есть модули и сделать генератор не будет большой проблемой.

Приятный бонус использования EBNF это возможность нарисовать railroad диаграммы для грамматики:



Насколько эффективным получился мой генератор напишу в одном из следующих постов.

Если тема показалась интересной, то вот список статей на подобную тематику:

18.12.2017

Наблюдение о блоггинге

За время ведения этого блога у меня появилось одно наблюдение.

Когда есть идея для нового поста, то это ещё недостаточное условие для его написания. Потому что вдобавок к идее нужно найти материал, придумать как подать текст, продумать структуру и т.д. Если такую подготовительную работу не сделать, то написание может превратиться в мучение - вроде хочется написать, но текст не идёт. Если же всё предварительно продумать, то написание текста пройдет легко. Я для себя взял за правило основательно готовиться перед тем как сесть писать новый текст и назвал его Правило Толстого. Потому что он это сформулировал задолго до меня:

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

14.12.2017

Чтение PDF

Многие из книг по тестированию и верификации ПО доступны бесплатно в формате PDF. Но PDF читать неудобно: экран смартфона слишком маленький для него, на компьютере экран нормальный, но я не готов портить зрение чтением на нём сотен страниц текста. Авторы этих книг продают эти книги в бумажном варианте и я был бы готов их купить, если бы не сумасшедшие цены - от $100 USD и выше.

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

10.12.2017