Как мы научили JavaScript анализатор понимать поток управления

• Граф потока управления?
• Как мы это сделали?
  • Обобщённый CFG
  • Подход к тестированию
• Что уже ищем?
  • Линейный код
  • Условия
  • Циклы
  • Обработка исключений
• Что дальше?
• Итоги

Недавно в статический анализатор PVS-Studio была добавлена поддержка JavaScript/TypeScript, и он на старте умеет искать ошибки, связанные с потоком управления. Причём тут граф потока управления, как мы его добавили и чем это полезно — читайте в этой статье.

Граф потока управления?

Я уже затрагивал эту тему, в частности, в моей серии про taint-анализ в Java, но кратко напомню. Исходный код, попадая в статический анализатор, преобразуется в абстрактное синтаксическое дерево (AST). Оно почти полностью отображает структуру кода, как он написан в редакторе. Для задач анализа потока управления, таких как поиск недостижимого кода, оно подходит плохо. На AST можно написать проверку, которая его ищет, но:

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

Для решения этих задач и существует граф потока управления (Control Flow Graph, CFG), который отвечает за отображение всех возможных путей в программе.

Состоит он из трёх составляющих:

• Узлы входа и выхода.
• Узлы базовых блоков, внутри которых расположены линейные инструкции.
  • Базовые блоки заканчиваются терминаторами (либо ничем). Терминаторы — особые инструкции, выражающие определённую семантику потока выполнения: ветвления, break/continue и т.п.
• Рёбра между узлами графа, отображающие возможные переходы потока управления.

Как мы это сделали?

Обобщённый CFG

В статье про разработку JavaScript/TypeScript анализатора мы уже упоминали, что инструмент включает в себя не только синтаксическое дерево для конкретного языка, но и обобщённое для мультиязыкового анализа. Мы назвали его CAT (Common Abstract Tree).

И хоть пока к JavaScript/TypeScript другие языки не присоединились, уже сейчас мы заложили возможность для расширения CFG: основной движок работает агностично от конкретного языка. Для этого мы описываем набор разных семантик и собираем их как конструктор под нужный нам язык. Таким образом, мы экономим себе время на поддержке других языков в будущем.

Примера таких специальных семантик для JavaScript/TypeScript два:

• try блоки, в которых исключения не типизированные, и больше одного catch быть не может.
• Метки вешаются на конкретную инструкцию, и к ней можно перейти только из вложенного в неё break. Также можно перейти по метке через continue, если она стоит на цикле.

Подход к тестированию

Проверка CFG на корректность — отдельное приключение. Первое, что приходит в голову: сериализовать граф в Graphviz либо иным способом, проверить глазами и зафиксировать эталон. Спойлер: это грабли, и мы на них наступили. Вот почему это не работает:

• Граф постоянно меняется при разработке. Придётся переписывать падающие тесты руками либо сжигать токены ИИ-агентов.
• Пропустить баг в эталоне очень легко. Если бы люди не делали ошибок, то индустрия статического анализа бы не существовала.
• Красивая топология не гарантирует, что граф реально передает всю семантику потока управления.

В итоге мы сменили подход и написали мини-интерпретатор нашего CAT на базе CFG. Идея простая: если наш интерпретатор, обойдя граф, даст тот же результат, что и интерпретатор JavaScript, то граф построен верно. Проверяется это простым Assertion API такого вида:

@Test
void branching() {
    EvaluationAssert.evaluate("branching")
                    .withParam("param", true)
                    .expect("a", 2);

    EvaluationAssert.evaluate("branching")
                    .withParam("param", false)
                    .expect("a", 0);
}

Этот тест запускает интерпретатор и сверяет результаты выполнения с эталоном, который можно получить, предварительно выполнив TypeScript код:

function branching(param: boolean) {
    let a = 1;
    if (param) {
        a++;
    } else {
        a--;
    }
}

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

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

По итогу имеем работающий строитель графов для JavaScript/TypeScript, строящийся за один проход по AST, что довольно шустро — для React все графы строится за четверть секунды.

Что уже ищем?

Линейный код

Самые рядовые опечатки, которые можно было бы искать и через AST, конечно, идут первыми:

if ( curveLengths[ i ] >= d ) {
    diff = curveLengths[ i ] - d;
    curve = this.curves[ i ];
    var u = 1 - diff / curve.getLength();
    return curve.getPointAt( u );
    break;
}

Предупреждение PVS-Studio: V7039 Unreachable code detected. Control flow never reaches this statement. three.js 29417.

Граф, который строит анализатор:

На нём отлично видно, что в break нет ни одного пути, поэтому он помечается как недостижимый.

Маловероятно, что эта ошибка на что-то влияет, и, скорее всего, недостижимый break просто является лишним. Но что занятно: этот файл — библиотека Three.js, скопированная внутрь Juice Shop, и такой же ошибки внутри актуального репозитория Three.js мы не нашли.

Кстати, классический баг с Automatic Semicolon Insertion вида:

function foo() {
    return // asi happens here
        this.bar
}

Будет ловиться точно таким же образом, ведь вставленная ; создаст терминатор в блоке с return и вынесет this.bar в следующий блок:

Условия

Занятный случай "защитного программирования" произошёл в Phaser:

if (!childA.parentContainer && !childB.parentContainer)
{
    return this.displayList.getIndex(childB)
      - this.displayList.getIndex(childA);
}
else if (childA.parentContainer === childB.parentContainer) {
// more branches ending with return statements here
} else
{
    var listA = childA.getIndexList();
    var listB = childB.getIndexList();
    var len = Math.min(listA.length, listB.length);

    for (var i = 0; i < len; i++)
    {
        var indexA = listA[i];
        var indexB = listB[i];

        if (indexA === indexB)
        {
            continue;
        }
        else
        {
            return indexB - indexA;
        }
    }
    return listB.length - listA.length;
}
//  Technically this shouldn't happen, but ...
// eslint-disable-next-line no-unreachable
return 0;

Предупреждение PVS-Studio: V7039 Unreachable code detected. Control flow never reaches this statement. InputPlugin.js 2981

Веток else-if было больше, но я их убрал для краткости и чтобы уменьшить граф:

Если вчитаться в комментарий и посмотреть на код, то опасение программиста должно стать понятным: выше сложная логика с 5+ ветками, каждая из которых завершает поток выполнения, поэтому он решил перестраховаться, не доверившись даже ESLint. Мы же вслед за ним по топологии графа увидели, что пути в return 0 просто нет.

Циклы

"Бесплатно" мы получаем и нахождение циклов, которые выполняются бесконечно или, наоборот, всего один раз. Такой случай попался в уже упомянутом Three.js:

loop:
for (var pos = 0; pos < limit; pos++) {
    for (; pos < limit; pos++) {                 // <=
        for (var k = 0; k < needleLength; k++) {
            if (haystack[pos + k] !== needle[k]) {
                continue loop;
            }
        }

        return pos;
    }
}

Предупреждение PVS-Studio: V7039 Unreachable code detected. Control flow never reaches this statement. opentype.module.js 6109.

Граф потока управления:

Диагностика обнаружила, что на графе инкремент переменной pos в цикле недостижим. Посмотрев на код, легко заметить, что все ветки действительно прерывают второй for, и у него будет лишь одна итерация. А на графе это подтверждается — пути в инкремент нет.

Попал этот код в проект из OpenType, но ныне скопированная зависимость уже удалена.

Обработка исключений

Случаи с вложенными try и прерыванием потока выполнения из finally не только экзотические, но часто и считаются code smell, так что сходу найти срабатывания в Open Source не вышло.

Однако это был один из самых нетривиальных случаев для обработки из-за запутанности семантики try-catch-finally. Нужно учитывать:

• Есть ли в try секции catch, finally или обе.
• Следить не только за явными throw, но и обрабатывать, куда тебя приведут неявные исключения.
• Перезаписывать прерывание потока управления своим внутри finally, когда оно произошло в try или catch.
• Каскадно пробрасывать прерывание потока управления сквозь try, если оно произошло в finally.
• И ещё множество других граничных кейсов, а также их комбинаторные сочетания.

Так что покуда этот случай показать хочется, приведу синтетический пример:

function tryCatchFinallyCase() {
    try {
        try {
            throw new Error("Whoops");
        } finally {
            console.log("inner")
        }
        return true // V7039
    } finally {
        console.log("outer")
    }
    return false; // V7039
}

Для такой функции анализатор построит следующий граф:

На графе можно чётко увидеть, что сами рёбра несут в себе информацию о том, какую операцию они "запомнили" до выхода из функции. В то же время недостижимые return узлы идентифицируются анализатором.

Что дальше?

Мы рассмотрели ошибки, которые анализатор способен находить при помощи нового механизма. И действительно, он уже показал свою эффективность, позволив достаточно тривиально реализовать диагностики V7039 (недостижимый код) и V7040 (бесконечная рекурсия) к релизу PVS-Studio 8.00. Но помимо диагностик, перед нами открываются и новые перспективы:

• Углубить построение CFG, распространив его на short-circuit выражения.
• Научиться находить не только недостижимый, но и мёртвый код за счёт условного проброса констант.
• Сделав основу для движка анализа потока данных, можно будет начать с taint-анализа (анализ помеченных данных).
• А углубив этот же движок, можно будет перейти к расчёту других видов анализа потока данных, таких как поиск разыменования нулевой ссылки, деления на ноль и прочего.

В общем, если CAT дал нам возможность расширения вширь, то CFG позволяет расширяться вглубь, так что теперь почва для развития нового анализатора стала ещё более плодотворной.

Итоги

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

• блоге PVS-Studio в X;
• нашем ежемесячном дайджесте статей;
• моём личном блоге.