Child pages
  • Kotlin compiler fuzzing to detect performance degradation
Skip to end of metadata
Go to start of metadata

Background

Тестировать компиляторы руками – крайне сложно, количество возможных программ для них крайне велико, как велико и количество возможных code passes в коде компилятора. Тем не менее тестирование руками также остаётся очень полезным – тестировщик может обладать знаниями о существующих проблемах в компиляторе, и будет уделять внимание более проблемным областям, но большинство багов и других проблем после ручного тестирования по-прежнему остаются незамеченными.

Таким образом, появляется задача – тестировать компилятор путём автоматической генерации программ. 

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

Описание

Предлагается генерировать программы методами машинного обучения для тестирования компилятора Kotlin с целью поиска перформанс-проблем. Поиск перформанс-проблем предполагает прежде всего попутную оптимизацию величины, например, времени анализа программа, размера памяти, используемой JVM и пр. То есть необходимо генерировать программы с заданным численным критерием подходимости.

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

Направления исследования

Genetic programming

В качестве отправной точки предлагается решить задачу в терминах генетического программирования: определить операторы кроссовера и мутации и фитнесс-функцию.

  1. Датасет – компиляторные тесты (около 10 тыс. фрагментов кода)

  2. Кодирование: прямое древовидное кодирование: синтаксическое дерево PSI, порождаемое компилятором

  3. Кроссовер: предлагается ввести понятие блока и входных и выходных ограничений для него. Эти ограничения представляют из себя набор типов, который требуется для:

    1. комбинирования этого блока с другим

    2. комбинирования другого блока с данным

  4. Мутации: removeNode(), generateNode(), changeNodeValueToGenerated()

    1. Генерация по грамматике/генерация по написанному ограниченному генератору

    2. Нужны эвристические проверки applicability сгенерированного блока к месту, куда он вставляется

    3. Для removeNode нужно доказательство того, что такое удаление не сломает код

  5. Fitness function. Эксперименты с разными величинами: время анализа, кодогенерации, занимаемая память JVM и пр.

GANы

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

Публикации по теме

Предлагается подход DeepSmith, который предполагает построение генеративных моделей для входных данных компилятора. Обучение на большом количестве кода реального мира. Т. е. попытка обучения семантике языка. Совместно с дифференциальным тестированием. Применяют всё это на языке OpenCL, хвастаются, что фаззер работает без их значительных усилий, и находит много ошибок – больше, чем фаззеры без ML, которые требуют много инженерных усилий. Также говорят о небольших тестовых примерах (можно будет подглянуть в их reducing).

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

Это статья ребят из Политеха, которые занимаются фаззингом нашего компилятора с целью нахождения падений и разницы поведений между разными back-end-ами. Для генерации кода используются разные мутации типа переподвешивания поддеревьев PSI, удаление узлов, перестановка строк и пр. Seed files – также компиляторные тесты. Насколько я знаю, не используется какого-то дополнительного анализа валидности сделанных мутаций (находится довольно много ошибок за счет большого числа попыток и относительно быстрой компиляции).

Тут рассказывается о генерации кода без каких-либо ограничений словарного запаса или структуры. Обычно существующие тулы генерируют код в определенном контексте (то есть в некоторой части языка программирования), что является очень сильным ограничением. Предлагается подход, в котором оцениваются вероятности путей AST.

Статья больше сбоку: предлагается методология оценивания эффективности фаззеров. Есть много попутных хороший классификаций (типы фаззеров: black-box, gray-box, и т. д.), как долго должен работать фаззер, оценивание по code coverage. В общем довольно много всего полезного, но сбоку. Вполне может пригодиться.

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

Можно будет использовать в описательной части / использовать предложенную там методологию по оценке влияния фаззерных ошибок на wild world.


  • No labels