Skip to end of metadata
Go to start of metadata

Table of contents

Description

Kotlin code anomaly detection – исследовательский проект, направленный на поиск аномалий методами машинного обучения в исходном коде программ на Kotlin в разных представлениях и в компиляторе Kotlin.

На данный момент мы ищем аномалии на конкретном синтаксическом дереве и на байт-коде, порожденном компилятором Kotlin.

Purposes

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

Мы считаем, что таким кодом могут являться аномалии, найденные с помощью ML-методов обнаружения аномалий.

На данный момент мы заинтересованы в поиске:

  1. Кода, соответствующего медленной работе программы во время исполнения (аномальный байт-код);
  2. Кода, при обработке которого компилятором могут возникнуть проблемы с его производительностью или корректностью (вывода типов, data flow/control flow анализа, кодогенерации и т. д.)
    1. Такой код может являться хорошим тестом компилятора на текущую функциональность, а также использоваться для тестирования компиляторных рефакторингов или новых фич.
    2. Как правило, это код, предполагающий нетривиальный вывод типов, сложный control flow и data flow анализ и т. д. – другим словом, в терминах кода компилятора, большой code pass.
  3. Проблем в оптимальности кодогенерации и эффективности оптимизаций компилятора
    1. Для детектирования таких проблем одного представления исходного кода недостаточно: на данный момент мы, например, анализируем аномалии на конкретном синтаксическом дереве в связке с байт-кодом.
  4. Проблем инлайнинга
    1. Под такими проблемами подразумеваются случаи, когда эффективность проинлайненного кода меньше, чем при использовании invocation инструкций в байт-коде.
    2. Здесь также предполагается совместный анализ нескольких представлений кода.
  5. Language design проблем
    1. Таким проблемам соответствует код, в котором присутствуют не очень удачные решения в дизайне языка, либо есть повод для введения новых конструкций, позволяющих записать более элегантно найдённый аномальней код.
    2. Эти аномалии должны быть проанализированы разработчиками компилятора, поскольку language design – область, по большей части постижимая только человеком.

Experiments

На данный момент мы умеем анализировать конкретные синтаксические деревья и байт-код, как по отдельности, так и вместе (условные аномалии).

В качестве датасета был использован собранный с Гитхаба набор исходного кода на Kotlin (который далее парсился с помощью соответствующего модуля компилятора) и собранный из релизных файлов репозиториев (готовые сборки) набор байт-кода.

Мы проводили эксперименты с использованием разных методов векторизации синтаксического дерева и байт-кода и с разными методами детектирования аномалий.

Использованные способы векторизации:

  • Human-written metrics: составленные человеком метрики и посчитанные по ним значения для каждого исходного кода и его дерева разбора (например, кол-во строк кода, максимального глубина в дереве разбора и пр.)
  • N-grams extraction: автоматическое извлечение n-грамм из деревьев разбора и байт-кода.

Использованные методы anomaly detection:

  • Local outlier factor,
  • Isolation forest,
  • Elliptic envelope,
  • Autoencoder,
  • One class SVM.

Anomalies on the parse trees

По поиску аномалий на дереве разбора были проведены следующие эксперименты:

  • Векторизация с human-written metrics, детектирование аномалий с помощью Local outlier factor, Isolation forest и Elliptic envelope и объединение результатов.
  • Векторизация путем извлечение n-грамм (с n=1,2,3) и детектирование аномалий автоэнкодером.
  • Векторизация с human-written metrics (другой набор метрик), детектирование аномалий с помощью One class SVM.

Anomalies on the bytecode

Эксперименты по детектированию аномалий в байт-коде:

  • Векторизация путем извлечение n-грамм (с n=1,2,3) и детектирование аномалий автоэнкодером.

Conditional anomalies

Эксперименты по детектированию условных аномалий (аномалий на байт-коде и не аномалия на синтаксическом дереве и наоборот):

  • Векторизация путем извлечение n-грамм (с n=1,2,3) и детектирование аномалий автоэнкодером.

Results

По результатам всех экспериментов было получено несколько сотен аномалий, они были вручную сгруппированы в классы и оценены экспертами. Результаты можно найти на Я.Диске (см. раздел Links).

Tools

  • Сбор исходного кода на Kotlin и байт-кода с Гитхаба (для репозиториев с main language Kotlin): https://github.com/PetukhovVictor/github-kotlin-repo-collector
    • Туториал:
      Она принимает на вход путь к папке с json-ками со сборниками ссылок на репо и путь к папке, куда будут качаться репо.
      Тула использует JGit для общения с гитхабом, он осуществляет авторизацию, используя oauth-токен из файлика `.github` в домашней директории, поэтому перед запуском тулы его нужно создать (содержимое такое: `oauth=<token>`).
      Из репо тулы, из Releases нужно скачать jar-ник и запустить его:
      `java -jar github-kotlin-repo-collector-0.1.jar -i <path to repo list folder> -o <path to repos folder>`
      Рекомендую сперва её запускать на маленьких порциях ссылок на репо, чтобы убедиться, что всё идет как надо.
      Что она делает:
      1) Клонирует поочередно репо;
      2) Фильтрует файлы, оставляя только сорсы Котлина;
      3) Если в репо есть созданные релизы с бинарниками, то качает последний из них и дергает API вот этой тулы — https://github.com/PetukhovVictor/github-kotlin-jar-collector:
      3.1) Если релиз - zip, то распаковывает его;
      3.2) Если jar, то извлекает из него class-файлы с байт-кодом (тоже самое делается с полученными jar-никами из архива);
      3.3) Если apk, то декомпилирует его и достает class-файлы.
      4) Если были собраны бинарники: из сорсов по регулярке достается список всех используемых пакетов, по котором фильтруются собранные class-файлы (для удаления нерелевантного байт-кода — сторонних либ в частности);
      5) Если были собраны бинарники: парсит class-файлы и записывает байт-код в json-ки.
      Т. о. в результате в каждой папке репо будет папка sources и, если были бинарники, папка classes, в которой рядом с каждым class файлом лежит соответствующая json-ка с байт-кодом.
  • Ветка в репо компилятора Kotlin с модулем для удобного извлечения конкретных синтаксических деревьев по исходному коду: https://github.com/PetukhovVictor/kotlin/tree/cad-sandbox
    • Туториал:
      1) Склонить мой форк репо компилятора: `git clone https://github.com/PetukhovVictor/kotlin.git` ;
      2) Зачекаутиться на ветку с модулем: `cd kotlin && git checkout cad-sandbox`;
      3) Сделать всё, как написано здесь: https://github.com/JetBrains/kotlin#build-environment-requirements (`Build environment requirements`);
      4) Запустить соответствующую грэдловую таску: `./gradlew :compiler:cad-sandbox:cleanTest :compiler:cad-sandbox:test --tests "org.jetbrains.kotlin.parsing.PsiExtractor.testRun" -i` (сопровождается скромным логом)
      Он будет брать сорсы из папки `kotlin/compiler/cad-sandbox/sources` и создавать рядом json-ку с PSI. Т. е. рекомендую предыдущей тулзе сразу указывать эту папку в качестве той, куда будут качаться репо.

Tasks and research areas

  1. Автоматическая классификация и кластеризация найденных аномалий
    • Кластеризация — для обнаружения новых классов и для альтернативной группировки.
    • Классификация — для отсечения не интересующих классов.
    • Label Propagation и прочий Active/Semi-supervised Learning.
  2. Концентрация на ML-алгоритмах, их настройка, сравнительный анализ, проба других методов anomaly detection.
  3. Эксперименты с векторизацией:
    • Явные признаки: увеличение кол-ва явных признаков, эксперименты со снижением размерности;
    • Неявные признаки:
      • Более разумный feature selection для n-грамм
      • Настройка алгоритма генерации: эксперименты с разными типами связей (ребенок-родитель, “горазонтальные” связи, “диагональные” и пр.)
      • Проба других методов автокодирования синтаксических деревьев и списков (через дочерние узлы, ML)
  4. Более прицельный поиск аномалий с ориентацией на конкретные компоненты компилятора:
    • Поиск аномалий в constraint solver: аномальные системы уровней относительно типовых переменных и аномальные их решения.
    • Поиск аномалий вокруг data flow и control flow анализа: обнаружение сложных и запутанных, явных и неявных (смарткасты) приведений типов; сложных графов потока управления.
    • Аномалии вокруг overload resolution: детектирование больших и сложных наборов методов-кандидатов для вызова.
  5. Поиск простых и условных аномалий с использованием представлений других таргетов Котлина: Javascript (AST) и LLVM биткод.
  6. Поиск аномалий, направленных на конкретные фичи языка и их взаимодействия
    • Главная задача здесь – понять, как можно описывать фичи языка и их комбинацию (например, на уровне конкретного синтаксического дерева).
  7. Поиск аномалий с использованием других представлений: токены, compiler front-end IR and back-end IRs.
    • Первоочередная задача здесь – поискать аномалии на токенах, поскольку в этом случае появляются новые данные для анализа: identifiers (названия переменных, классов и пр.) и values (числа, строки и прочие литералы).
  8. Автоматизация сборок гитхабовых проектов – важная инженерная задача, необходимая для возможности анализа кода на произвольных внутрикомпиляторных представлениях исходного кода.
    • Здесь нужно научиться билдить произвольный проект, скачанный с гитхаба, и подсовывать сборочной системе пропатченный компилятор, который дампит нужные нам представления исходного кода.

 

  • No labels