Тестирование компиляторов

Первой прочитанной книгой в этом году у меня была “Редкая профессия” Евгения Зуева. Автор рассказывает о первом в мире C++ компиляторе, который они делали небольшой командой по заказу бельгийцев. Стиль книги на любителя - технические детали проектов перемешаны с лирическими отступлениями, но мне понравились две главы, где автор рассказывает как они тестировали компилятор. Так как тираж книжки небольшой и вам вряд ли доведётся её читать, то я приведу текст обеих глав здесь:

Программирование «наизнанку»

Решающим фактором в том, что сегодня мы имеем нечто, что можно с уверенностью назвать компилятором Си++, стало тестирование. Нам трудно судить о том, как следует тестировать, скажем, текстовый редактор или (упаси, Господи!) операционную систему, но наш опыт тестирования и отладки компилятора говорит о том, что это едва ли не самое главное во всём проекте.

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

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

Надо понять специфику этой работы, чтобы оценить её невероятную сложность. Есть стандарт языка (который и не стандарт вовсе, а «рабочие материалы по предварительному стандарту рабочих групп ANSI и ISO», и почти каждый квартал выходит новая версия этих «рабочих материалов»). Это кирпич в три килограмма. Каждый абзац стандарта содержит одно утверждение (а чаще несколько) относительно того или иного свойства языка. Тестовый пакет должен проверять каждое такое свойство, то есть содержать соответствующий тест на каждое утверждение стандарта. Каждое утверждение тестируется в предположении, что другие языковые свойства компилятор реализует корректно, - протестировать все сочетания свойств физически невозможно. Предварительный стандарт, как уже говорилось, постоянно изменяется, значит, каждый новый талмуд нужно просмотреть и увидеть, что изменилось, по сравнению с прежним (перечень изменений рабочие группы тогда не вели), и внести в тесты соответствующие изменения и добавления.

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

Наконец, предварительный стандарт - это текущий результат живых дискуссий, обсуждений, голосований рабочих групп; там сидят очень грамотные специалисты, но и они, бывает, ошибаются и не всё сразу видят. Поэтому в каждой версии есть (и в окончательном варианте останутся) ошибки, неясности, двусмысленности, недоговорённости. Все это присутствует, наверное, в любом стандарте, но Си++ в этом отношении чемпион - слишком это сложный язык, и слишком хаотически и спонтанно он проектируется. Так что, читая стандарт, следовало чётко осознавать, почему та или иная фраза кажется тебе абракадаброй: то ли ты плохо знаешь английский, то ли недостаточно глубоко понимаешь Си++, то ли ребята из ANSI/ISO что-то напутали (а часто и то, и другое, и третье). И не с кем посоветоваться - все учебники по Си++ излагают в лучшем случае версию «Зелёной книги» 1990 г., - и нельзя проверить свое понимание на компьютере: нет компилятора, который реализовывал бы свойство, за которое комитет проголосовал на прошлой неделе. Еще не отлита та пуля…

В таких условиях и был написан тестовый набор, который в итоге содержал более 6500 тестов. (Можно понять, почему подобные пакеты стоят на Западе до 20 тыс. долл.!) Важно то, что до определённого момента две наши команды работали полностью независимо, никак не влияя друг на друга. В результате тесты не подгонялись под компилятор, а алгоритмы компилятора проектировались строго по семантике языка, без ориентации на то, чтобы протолкнуть его сквозь конкретные тесты. Взаимные консультации касались только обсуждения собственно текста стандарта - отправной точки для обеих групп. Только когда компилятор в основном был сделан, мы начали использовать тесты из тестового набора. Вообще, создание тестового пакета - отдельная история, не менее интересная и драматичная, чем наша. На самом деле далеко не всё было так гладко и последовательно, как описано выше. Наш шеф В. А. Сухомлин потратил очень много усилий на формирование коллектива тестовиков. Можно понять сложность задачи - непросто найти программистов, которые хотели и могли бы заниматься «программированием наизнанку» - использовать язык не для решения какой-либо задачи, а для проверки того или иного свойства самого языка! Авторы методики тестирования довольно быстро выполнили свою задачу и, не будучи знатоками Си++, отошли от проекта. Руководить той адовой работой по написанию тестов, о которой мы писали выше, пытались разные люди, но только с приходом Дениса Давыдова, аспиранта мехмата, процесс приобрел систематический и продуктивный характер. У этого одарённого и трудолюбивого парня была масса очень интересных и действительно перспективных находок и идей, связанных с тестированием ПО, и если бы не его совершенно необъяснимая и неожиданная кончина, вся эта работа сейчас наверняка выглядела бы ещё сильнее и солиднее. Талантливые люди всегда уходят слишком рано…

С тех пор отладка тестов почти полностью легла на наши плечи, и мы вложили в пакет очень много своего труда. Тестовой команды как таковой уже нет - трудно рассчитывать, что студенты будут, практически ничего не получая, в течение долгого времени тянуть эту тяжелую лямку (тем более что студенты ВМК сейчас могут с лёгкостью получить пусть не слишком интересную, но гораздо менее тяжёлую и неплохо оплачиваемую работу). Таким образом, мы с достаточным основанием можем говорить о том, что этот тестовый набор в значительной степени наш (я имею в виду только авторство - с формальной точки зрения он принадлежит заказавшей его фирме). Сейчас это прекрасный, всесторонне выверенный и протестированный набор из почти семи тысяч небольших, но строго специфицированных и единообразно составленных программ, охватывающий весь язык Си++ в полном соответствии со стандартом. Не знаю, что делают с ним бельгийцы, продают ли они его и за сколько, но для нас ценность его исключительно велика, мы любим его не меньше, чем компилятор. В какой-то статье было сказано, что нормальное соотношение разработчиков и тестировщиков на Западе - один к двум. У нас пропорция была даже выше.

Настоящая работа

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

Все было по-другому. Вечером мы запускали тестовый прогон, утром (если наш жалкий SparcClassic или монструозный диск Махtоr на 300 Мбайт за ночь не дал сбой) получали протоколы тестирования, разбирали «по принадлежности» непрошедшие тесты, и начиналась настоящая программистская работа - поиск и исправление ошибок.

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

Первые тестовые прогоны были кошмарны: на половине тестов компилятор выдавал вереницы жутких диагностических сообщений, которые, казалось, никогда не должны появляться, другие аварийно заканчивались знаменитой диагностикой «core dumped», те тесты, которым все-таки удалось прорваться сквозь компилятор, при исполнении выдавали неверные результаты, и лишь единицы завершались скромной фразой «test passed». Казалось, не в силах человеческих разобраться в этой каше. Однако капля камень точит.

Поначалу-то как раз было легче - в первую очередь находились и исправлялись очевидные ляпы. Как правило, одно исправление приводило к проталкиванию десятка, а то и больше ранее неудачных тестов. Были, конечно, и «наведённые» ошибки, которые в один прекрасный день магическим образом бесследно исчезали, оставляя после себя смутное беспокойство (а вдруг как исчезли, так и вновь появятся?). Но чем дальше двигалась отладка, тем дороже давался каждый тест. Ошибки становились все тоньше, специфичнее и тяжелее в поиске, а чтобы исправить найденную ошибку, иногда приходилось перетрясти десяток функций в разных модулях. Исправление одной ошибки не раз приводило к появлению целой серии «экранированных» ею ошибок, которые не могли проявиться до ликвидации первой ошибки. Компилятор, казалось, сопротивлялся лечению, словно строптивый ребенок.

А тут ещё в самый разгар работы, когда ошибки щелкаются одна за другой, компилятор на глазах выздоравливает, словно от тяжелой болезни, - приходит новая версия стандарта. Значит, надо опять смотреть, что изменилось. Ладно, если вводится новая языковая возможность, это может быть несложно в реализации и даже приятно: когда ни у Borland, ни у gcc еще не был реализован описатель mutable или булевский тип, у нас уже всё работало. Хуже, если уточняются детали семантики хорошо известных конструкций, что, как правило, влечёт за собой переделку базовых алгоритмов. Так, общий алгоритм сравнения типов, алгоритм обработки совместно используемых функций (одноимённых функций, различающихся числом и типами параметров) и в особенности алгоритмы, реализующие правила вызова деструкторов и обработки исключений, переделывались после почти каждой новой версии предварительного стандарта. Понятно, что каждая такая переделка работающей программы вызывает поток новых ошибок, и мы откатываемся на месяц назад…

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

А интересно, как тестирует свои компиляторы Watcom?

Если интересны подходы в тестировании компиляторов, то этот набор ссылок может быть неплохим стартом для погружения в тему.

10.01.2019

Мутационное тестирование 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