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



Если статический анализатор умеет вычислить, чему равно выражение, это позволяет осуществлять более глубокий анализ кода и выявлять больше ошибок. Речь конечно идёт не только о точных значениях выражений, таких как 1+2, но и о вычислении диапазона значений, которые может принимать переменная в определённом месте программы. В анализаторе PVS-Studio мы называем алгоритмы, отвечающие за вычисление диапазонов — механизмом виртуальных значений. Такой механизм есть как в ядре анализатора C/C++ кода, так и в ядре C#-анализатора. В этой статье мы рассмотрим механизм виртуальных значений на примере C#-анализатора.

В своём анализаторе PVS-Studio для поиска ошибок в C# проектах мы используем Roslyn для получения всей необходимой информации об исходном коде. Roslyn предоставляет нам синтаксическое дерево, информацию о типах, поиск зависимостей и так далее. В процессе анализа PVS-Studio выполняет обход синтаксического дерева и применяет диагностики к его узлам. Помимо этого, в процессе обхода собирается информация, которая может быть использована анализатором позже. Примером такой дополнительной информации являются виртуальные значения.

Создание виртуальных значений

Виртуальные значения сохраняются для полей, свойств, переменных и параметров при первом упоминании в коде. Если первое упоминание — это объявление переменной или присваивание, то мы попробуем вычислить виртуальное значение путём анализа выражения справа от знака равенства. В противном случае мы как правило ничего не знаем о свойстве/поле/параметре и считаем, что оно может принимать любое допустимое значение. Рассмотрим пример:

public class MyClass
{
    private bool hasElements = false;
    public void Func(byte x, List<int> list)
    {
        int y = x;
        hasElements = (list.Count >= 0);
        if (hasElements && y >= 0) //V3022
        {
        }
    }
}

Когда в процессе обхода дерева анализатор дойдёт до тела функции Func, он начнёт вычислять виртуальные значения переменных. В первой строке объявляется переменная y, которая инициализируется значением х. Так как про x мы знаем только то что он имеет тип byte, то значит он может принимать любое значение от 0 до 255. Этот диапазон значений и будет присвоен в качестве виртуального значения переменной y. Аналогично будет сделано и для поля hasElements: анализатор знает про то что свойство Count у списка не может принимать отрицательные значения, поэтому в качестве виртуального значения переменной hasElements будет присвоено true. Теперь при анализе условия hasElements && y >= 0 мы знаем что левая и правая части истинны и значит всё условие тоже всегда истинно — здесь и срабатывает диагностика V3022.

Рассмотрим подробнее как вычисляется виртуальное значение выражения.

Вычисление виртуального значения выражения

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

public void Func(int x)
{
    if (x >= -10 && x <= 10 && x != 0)
    {
        int y = x + 5;
    }
}

В начале функции про переменную x ничего не известно и её диапазон — все допустимые значения типа int: [int.MinValue, int.MaxValue]. При входе в блок if мы можем уточнить виртуальное значение на основании условия. Таким образом внутри блока if переменная x будет иметь диапазон [-10, -1], [1, 10]. Если теперь x будет использоваться при вычислении выражения, то анализатор учтёт её виртуальное значение. В нашем примере y получит виртуальное значение [-5, 4], [6, 15].

Для выражений типа bool виртуальное значение вычисляется по-другому. Здесь у нас только три варианта: ложь, истина или неизвестное значение. Поэтому мы просто переберём достаточное количество вариантов для всех переменных выражения, и проверим во всех ли случаях выражение будет принимать одно и то же значение. Например:

public void Func(uint x)
{
    bool b = (x >= 0); //V3022
}

Какие бы значения для параметра x мы ни взяли, выражение x >= 0 всегда истинно. Поэтому подставив несколько значений вместо x, мы убедимся в этом и присвоим true в качестве виртуального значения для b.

Ещё пример из проекта umbraco:

private object Aggregate(object[] args, string name)
{
    ....
    if (name != "Min" || name != "Max") //V3022
    {
        throw new ArgumentException("Can only use min or max...");
    }
    ....
}

Чтобы убедиться в том что условие в примере всегда истинно анализатор подставляет вместо name значения «Min», «Max», "", null. В каждом из этих случаев либо левая, либо правая часть выражения будет истинна, значит выражение в условии всегда истинно.

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

Уточнение виртуальных значений в блоке if/else

Рассмотрим для примера как ведут себя виртуальные значения при обработке блока if/else.

public void Func(int x)
{
    if (x >= 0)
    {                    //x:[0, int.MaxValue]
        if (x <= 10)
        {                //x:[0, 10]
        ....
        }
        else
        {                //x:[11, int.MaxValue]
        ....
        }
    }
}

Проанализировав условие x >= 0, PVS-Studio ограничит диапазон переменной x для первого блока if значениями [0, int.MaxValue]. После обработки второго условия x <= 10 анализатор создаст ещё две копии виртуальных значений переменной x — одну для блока if, другую для блока else. Причём на эти копии будут наложены ограничения с учётом виртуального значения этой же переменной из родительского блока и виртуального значения выражения в условии. То есть для вложенного блока if виртуальное значение переменной x будет [0, 10], а для блока else — все остальные значения — [11, int.MaxValue].

После обхода блока if/else нам нужно объединить виртуальные значения из блоков if и else для каждой переменной. Тут также следует учесть, что если в конце if или else был оператор перехода, например, return, то объединять значения из этого блока не нужно. Примеры:

public void Func1(int x)
{
    bool b1 = false;
    bool b2 = false;
    if (x >= 0)
    {
        ....
        b1 = true;
        b2 = true;
    }
    else
    {
        ....
        b1 = true;
    }
    //Здесь мы знаем, что b1 всегда true
    //А вот b2 может принять любое значение
}

public void Func2(int x)
{
    if (x < 0)
        return;
    //Здесь мы знаем, что x всегда неотрицательный
}

Обработка циклов

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

public void Func()
{
    int i = 0;
    while (i < 10)
    {
        if (i == 5)
        {
        ....
        }
        i++;
    }
}

Если просто скопировать виртуальные значения из родительского блока в блок while, то при анализе условия i == 5 мы получили бы ложное срабатывание V3022, так как мы знаем, что до цикла переменная i была равна нулю. Поэтому перед тем как анализировать тело цикла, нужно вычислить какие значения переменные могут принимать в конце итерации, а также во всех блоках, содержащих оператор continue, и объединить все эти значения вместе со значениями переменных до входа в цикл. Кроме того, если мы анализируем цикл for, нужно учесть блоки инициализации и изменения счётчика. После того как значения всех возможных точек входа в цикл объединены к ним необходимо применить условие цикла точно так же как это сделано для блока if. Так мы получим правильные виртуальные значения для переменных и можно выполнять второй обход цикла, на котором будут применяться диагностики.

После обхода цикла нам нужно объединить виртуальные значения переменных со всех точек, из которых мы может попасть на следующий после цикла оператор. Это значения до начала цикла (если не будет выполнено ни одной итерации), значения переменных в конце тела цикла, значения переменных в блоках, содержащих операторы break или continue. Все эти значения мы уже вычислили и запомнили в момент первого обхода цикла. Теперь все их нужно также объединить и применить условие, противоположное условию цикла.

Это было сложное объяснение, поэтому давайте рассмотрим пример:

public void Func(bool condition1, bool condition2, bool condition3)
{
    int x = 0;
    while (condition1)
    {
        //x:[0, 1], [3]
        if (condition2)
        {
            x = 2;
            break;
        }
        if (condition3)
        {
            x = 3;
            continue;
        }
        x = 1;
    }
    //x:[0, 3]
}

В этом примере переменная x до входа в цикл равна нулю. Выполнив первый проход по циклу, анализатор вычислит что переменная x также может принять значения 1, 2 в блоке с break и 3 в блоке с continue. Так как у нас три точки перехода к очередной итерации цикла, то в начале цикла переменная x может принимать значения 0, 1 или 3. А в следующий за циклом оператор мы можем попасть из четырёх точек. Поэтому здесь x может быть равен 0, 1, 2 или 3.

Также анализатор вычисляет какие значения могут принимать переменные внутри блоков case оператора switch, внутри try/catch/finally и для других конструкций языка.

Деление на ноль

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

public int GetBlockCount(int dataLength, int blockSize)
{
    return dataLength / blockSize;
}

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

public string GetDownloadAvgRateString() {
    if (SecondsDownloading >= 0) {
        return GetSpeed(Downloaded / SecondsDownloading);
    } else {
        return "";
    }
}

или такие:

public void Func(int x, int y)
{
    for (int i = -10; i <= 10; i++)
    {
        y = x / i;
    }
}

В качестве решения мы разделяем диапазоны виртуальных значений на точные и неточные. По умолчанию диапазон считается неточным пока его не уточнили путём явного присваивания константы или переменной с точным диапазоном, или путём ограничения в условии оператора if или цикла. Если ноль попадает внутрь или на границу точного диапазона, то в этом случае диагностика деление на ноль срабатывает.

Примеры

Рассмотрим теперь несколько примеров из реальных проектов, найденных PVS-Studio с помощью виртуальных значений.

Пример N1 (RavenDB).

internal static void UrlPathEncodeChar (char c, Stream result)
{
    if (c < 33 || c > 126) {
        byte [] bIn = Encoding.UTF8.GetBytes (c.ToString ());
        for (int i = 0; i < bIn.Length; i++) {
            ....
        }
    }
    else if (c == ' ') { //V3022
        result.WriteByte ((byte) '%');
        result.WriteByte ((byte) '2');
        result.WriteByte ((byte) '0');
    }
    else
        result.WriteByte ((byte) c);
}

Первое условие функции UrlPathEncodeChar обрабатывает специальные символы, второе условие — специальная оптимизация для пробела. Но так как ASCII код пробела равен 32, то пробел будет обработан первым блоком. PVS-Studio находит эту ошибку следующим образом: внутри блока if виртуальное значение переменной c будет равно [0, 32], [127, char.MaxValue], а внутри первого блока else — все остальные значения: [33, 126]. Так как код пробела не попадает в этот диапазон, то анализатор сообщает об ошибке V3022 — выражение c == ' ' всегда ложно.

Пример N2 (ServiceStack).

protected override sealed void Initialize()
{
    if (RootDirInfo == null)
        RootDirInfo = new DirectoryInfo(WebHostPhysicalPath);

    if (RootDirInfo == null || !RootDirInfo.Exists) //V3063
        throw new ApplicationException("...");
    ....
}

В начале функции Initialize про свойство RootDirInfo нам ничего не известно. После анализа условия RootDirInfo == null создаются ещё 2 копии виртуальных значений: одна для блока if в котором RootDirInfo равен null, и вторая для блока else, в котором RootDirInfo не равен null. Хотя блока else в нашем примере нет, виртуальные значения для него всё равно создаются. Дальше внутри блока if в свойство RootDirInfo присваивается новое значение, полученное в результате вызова конструктора. Так как конструктор никогда не возвращает null, то значение RootDirInfo в блоке if теперь не равно null. Так как RootDirInfo для блока else тоже не равен null, то при объединении этих двух веток мы получаем что RootDirInfo после обработки первого условия никогда не будет равен null. В итоге при анализе второго условия PVS-Studio сообщает об ошибке V3063 — часть условия всегда ложна.

Пример N3 (ServiceStack).

public static TextNode ParseTypeIntoNodes(this string typeDef)
{
    ....
    var lastBlockPos = typeDef.IndexOf('<');
    if (lastBlockPos >= 0)
    {
        ....
        //V3022
        while (lastBlockPos != -1 || blockStartingPos.Count == 0)
        {
            var nextPos = typeDef.IndexOfAny(blockChars,
                lastBlockPos + 1);
            if (nextPos == -1)
                break;
            ....
            lastBlockPos = nextPos;
        }
    }
}

Рассмотрим, что происходит в этом примере с переменной lastBlockPos. Сначала в неё присваивается результат вызова функции IndexOf. Анализатор знает, что функции IndexOf, IndexOfAny, LastIndexOf, LastIndexOfAny возвращают неотрицательное значение или -1. Следовательно диапазон переменной lastBlockPos будет [-1, int.MaxValue]. После входа в блок if диапазон будет ограничен только неотрицательными значениями [0, int.MaxValue]. Дальше анализатор выполнит проход по телу цикла while. Переменная nextPos при объявлении получает диапазон [-1, int.MaxValue]. После анализа условия if (nextPos == -1) создаются две копии виртуальных значений переменной nextPost: [-1] для ветки if и [0, int.MaxValue] для ветки else. Так как ветка if содержит оператор break, то в остальном теле цикла для переменной nextPost используются только виртуальные значения ветки else: [0, int.MaxValue], которые и присваиваются в конце переменной lastBlockPos.

Таким образом у нас есть две точки перехода к телу цикла: одна при входе в цикл, в которой lastBlockPos имеет значение [0, int.MaxValue] и вторая при переходе к очередной итерации, в которой lastBlockPos тоже имеет значение [0, int.MaxValue]. Следовательно, lastBlockPos никогда не принимает отрицательные значения в условии цикла, а значит условие цикла всегда истинно, о чём и сообщает диагностика V3022.

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

Пример N4 (TransmissionRemoteDotnet).

// Converts an IPv4 address into a long, for reading from geo database
long AddressToLong(IPAddress ip)
{
    long num = 0;
    byte[] bytes = ip.GetAddressBytes();
    for (int i = 0; i < 4; ++i)
    {
        long y = bytes[i];
        if (y < 0) //V3022
            y += 256;
        num += y << ((3 - i) * 8);
    }

    return num;
}

Здесь в переменную y типа long присваивается значение типа byte. Так как тип byte беззнаковый, то проверка y < 0 бессмысленна.

Пример N5 (MSBuild).

private bool ValidateTaskNode()
{
    bool foundInvalidNode = false;
    foreach (XmlNode childNode in _taskNode.ChildNodes)
    {
        switch (childNode.NodeType)
        {
            case XmlNodeType.Comment:
            case XmlNodeType.Whitespace:
            case XmlNodeType.Text:
                // These are legal, and ignored
                continue;
            case XmlNodeType.Element:
                if (childNode.Name.Equals("Code") ||
                    childNode.Name.Equals("Reference") ||
                    childNode.Name.Equals("Using"))
                {
                    continue;
                }
                else
                {
                     foundInvalidNode = true;
                }
                break;
            default:
                foundInvalidNode = true;
                break;
        }

        if (foundInvalidNode) //V3022
        {
            ....
            return false;
        }
    }

    return true;
}

В этом примере тело цикла содержит два оператора — switch и if. Рассмотрим блок switch. Первая секция с тремя case содержит только оператор continue, поэтому отсюда не может быть перехода к проверке условия foundInvalidNode. Вторая секция case либо выполняет переход к следующей итерации цикла, либо устанавливает foundInvalidNode в true и выходит из switch. И, наконец, секция default тоже устанавливает foundInvalidNode в true и выходит из switch. Таким образом после выхода из switch переменная foundInvalidNode будет всегда истинна, а значит следующий if лишний. Анализатор принял во внимание что в этом блоке switch есть ветка default, а значит управление не может перейти сразу к проверке условия — одна из switch-секций будет обязательно выполнена.

Нужно заметить, что внутри этого оператора switch continue имеет отношение к циклу, а break осуществляет выход из switch, а не из цикла!

Заключение

Вычисление значений переменных на этапе статического анализа — это мощный инструмент для поиска ошибок. Код может содержать сложные ветвления, вложенные условия и циклы, блоки размером в сотни строк. Проследить вручную как меняется переменная и найти ошибку может быть очень сложно и статический анализатор PVS-Studio является хорошим помощником в поисках многих ошибок.

Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Ilya Ivanov. Searching for errors by means of virtual values evaluation.