Как сделать статический логический анализ кода с помощью дерева AST или другого инструмента?

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

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

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

Есть второй подход. Он основан на автоматических аннотациях функций. Дело в том, что при анализе функций просматривается информация о том, как используются их аргументы и какие значения они не могут принимать. Рассмотрим простой пример, который я приводил в статье «Технологии, используемые в коде PVS-Studio анализатор для поиска ошибок и потенциальных уязвимостей'.

int Div(int X)
{
  return 10 / X;
}
void Foo()
{
  for (int i = 0; i < 5; ++i)
    Div(i);
}

Анализатор распознает, что переменная X используется в функции Div в качестве делителя. На его основе автоматически создается специальная аннотация функции Div. Затем учитывается тот факт, что диапазон значений [0..4] передается функции в качестве аргумента X. Анализатор делает вывод, что должно появиться деление на ноль.

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

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

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

Рассмотрим следующий код:

// control flow block 1
int i = 1;
if (some_condition()) {
    // control flow block 2
    i = 2;
}
// control flow block 3
int j = i;

С графом потока управления

[1]
 | \     <- if (some_condition())
 |  [2]
 | /     <- join of control flow after the if block ends
[3]

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

[1] entry: nothing; exit: i
[2] entry: nothing; exit: i
[3] entry: i; exit: i, j (I assume i, j are re-used after the end of this example)

Обратите внимание, что [2] entry пусто, так как i никогда не читается и всегда записывается в блоке [2]. Проблема с этим представлением заключается в том, что i находится в списке выхода всех блоков, но имеет разные возможные значения для каждого блока.

Итак, давайте введем неизменяемые символы в псевдокоде:

// control flow block 1
i = 1;
if (some_condition()) {
    // control flow block 2
    i_1 = 2;
}
// control flow block 3
// join-logic of predecessor [1] and [2]
i_2 = one_of(i, i_1);
j = i_2;

Теперь каждая переменная связана точно со своим первым (и единственным) присвоением. Это означает, что граф зависимости может быть построен путем анализа символов, которые участвуют в назначении.

i   -> i_2
i_1 -> i_2
i_2 -> j

Теперь, если существует какое-либо ограничение на допустимое значение j, средство статической проверки может потребовать, чтобы все предшественники j (а именно i_2, в свою очередь, исходящие из i и i_1) , удовлетворить этому требованию.

В случае вызовов функций граф зависимостей будет содержать ребро от каждого вызывающего аргумента до соответствующего параметра в определении функции.

Применить это к вашему примеру просто, если мы сосредоточимся только на переменной массива и проигнорируем изменения в содержимом массива (я не совсем уверен, в какой степени статическая проверка будет отслеживать содержимое отдельных элементов массива, чтобы найти опасность вниз дорога):

Пример 1:

void f1(char *s)
{
    s[20] = 0;
}

void f2()
{
    char a[10];
    if (x + y == 2) {
        f1(a);
    }
}

Превращается в

f1(s)
{
    s[20] = 0;
}

f2()
{
    a = char[10];
    if (x + y == 2) {
        call f1(a);
    }
}

С графом зависимостей, включая переданные аргументы через вызов функции

a -> s

Таким образом, сразу становится ясно, что a необходимо учитывать при статическом анализе безопасности s[20].

Пример 2:

void f1(char *s)
{
    char str_arry[30];
    s= str_arry;
    s[20] = 0;
}

Превращается в

f1(s)
{
    // control flow block 1
    str_arry = char[30];
    s_1 = str_arry;
    s_1[20] = 0;
}

С графиком зависимости

str_arry -> s_1

Таким образом, сразу становится ясно, что единственным значением, которое следует учитывать при статическом анализе безопасности s_1[20], является str_arry.

Как Cppcheck мог получить связь между «a» в f2 и «s» в f1?

Они определенно не одинаковы. Может произойти одно из следующего:

Вы передаете a функции, и CPPcheck продолжает запоминать размер a, даже если вы обращаетесь к нему с формальным параметром s.

Вы должны иметь в виду, что инструменты статического анализа и компиляторы работают по-разному, с разными целями. Инструменты статического анализа были созданы ТОЧНО для того, чтобы выявлять такие вещи, как вы представили в своем вопросе.

Во втором примере у вас есть:

s= str_arry;

который удаляет связь между s и a.