Открыть список
Как стать автором
Обновить
208,77
Рейтинг
PVS-Studio
Статический анализ кода для C, C++, C# и Java

Зачем PVS-Studio использует анализ потока данных: по мотивам интересной ошибки в Open Asset Import Library

Блог компании PVS-StudioOpen sourceC++Алгоритмы

PVS-Studio - Анализ потока данных
Анализ потока данных является неотъемлемой частью любого современного статического анализатора кода. Однако, со стороны, не очень понятно, что это и главное – зачем нужно. До сих пор некоторые ассоциируют статический анализ с поиском чего-то в коде по определённому шаблону. Поэтому время от времени мы пишем заметки, в которых демонстрируем, как та или иная технология, используемая в анализаторе PVS-Studio, помогает выявить очередную интересную ошибку. Сегодня как раз такая статья, в которой мы рассмотрим баг в одной из реализаций стандарта кодирования двоичных данных Base64.


Всё началось с проверки свежей версии библиотеки Qt 6. Про это была отдельная классическая статья, где я описал 77 найденных ошибок. Так получилось, что вначале я решил бегло полистать отчёт, ещё не пряча предупреждения, относящиеся к сторонним библиотекам. Другими словами, я не отключил в настройках предупреждения, относящиеся к \src\3rdparty. И так вышло, что я сразу наткнулся на интересный пример ошибки в библиотеке Open Asset Import Library, про которую я решил сделать эту отдельную маленькую заметку.


Найденный дефект демонстрирует, зачем в инструментах, таких как PVS-Studio, полезно анализировать поток данных. Без этого поиск многих ошибок просто невозможен. Кстати, если вам интересно подробнее узнать про анализ потока данных и про другие аспекты устройства инструмента, предлагаю вашему вниманию статью "Технологии, используемые в анализаторе кода PVS-Studio для поиска ошибок и потенциальных уязвимостей".


Теперь перейдём, собственно, к ошибке, обнаруженной в Open Asset Import Library (assimp). Файл: \src\3rdparty\assimp\src\code\FBX\FBXUtil.cpp.


std::string EncodeBase64(const char* data, size_t length)
{
    // calculate extra bytes needed to get a multiple of 3
    size_t extraBytes = 3 - length % 3;

    // number of base64 bytes
    size_t encodedBytes = 4 * (length + extraBytes) / 3;

    std::string encoded_string(encodedBytes, '=');

    // read blocks of 3 bytes
    for (size_t ib3 = 0; ib3 < length / 3; ib3++)
    {
        const size_t iByte = ib3 * 3;
        const size_t iEncodedByte = ib3 * 4;
        const char* currData = &data[iByte];

        EncodeByteBlock(currData, encoded_string, iEncodedByte);
    }

    // if size of data is not a multiple of 3,
    // also encode the final bytes (and add zeros where needed)
    if (extraBytes > 0)
    {
        char finalBytes[4] = { 0,0,0,0 };
        memcpy(&finalBytes[0], &data[length - length % 3], length % 3);

        const size_t iEncodedByte = encodedBytes - 4;
        EncodeByteBlock(&finalBytes[0], encoded_string, iEncodedByte);

        // add '=' at the end
        for (size_t i = 0; i < 4 * extraBytes / 3; i++)
            encoded_string[encodedBytes - i - 1] = '=';
    }
    return encoded_string;
}

Если хотите, то для начала можете попробовать обнаружить ошибку самостоятельно. А чтобы вы случайно сразу не прочитали ответ, приведу пока список некоторых других интересных статей и кратко расскажу, что такое Base64 :). Список дополнительных статей на близкую тематику:


  1. 31 февраля;
  2. Использование машинного обучения в статическом анализе исходного кода программ;
  3. Как внедрить статический анализатор кода в legacy проект и не демотивировать команду.

Ok, продолжим. Перед нами реализация алгоритма кодирования строки байт в кодировку Base64. Это стандарт кодирования двоичных данных при помощи только 64 символов. Алфавит кодирования содержит текстово-цифровые латинские символы A-Z, a-z и 0-9 (62 знака) и 2 дополнительных символа, зависящих от системы реализации. Каждые 3 исходных байта кодируются 4 символами.


Если осталось закодировать только один или два байта, то в результате получаются только первые два или три символа строки, а выходная строка дополняется двумя или одним символами "=". Это предотвращает добавление дополнительных битов к восстановленным данным. Вот этот момент как раз реализован в рассматриваемой функции неправильно.


Если вы нашли ошибку, вы молодец. Если нет, то это тоже нормально. Нужно вникать в код, чтобы заметить, что что-то идёт не так. Анализатор про это "что-то не то" сообщает предупреждением: V547 [CWE-571] Expression 'extraBytes > 0' is always true. FBXUtil.cpp 224


Чтобы понять причину беспокойства анализатора, давайте посмотрим, как инициализируется переменная extraBytes:


// calculate extra bytes needed to get a multiple of 3
size_t extraBytes = 3 - length % 3;

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


size_t extraBytes = length % 3;

Тогда, если обрабатывается, например, 5 байт, то получаем 5 % 3 = 2, и нужно дополнительно обработать 2 байта. Если на вход поступило 6 байт, то ничего отдельно обрабатывать не нужно, так как 6 % 3 = 0.


Хотя, возможно имелось в виду, сколько байт не хватает для кратности трём. Тогда правильный код должен быть таким:


size_t extraBytes = (3 - length % 3) % 3;

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


size_t extraBytes = 3 - length % 3;

И как раз при анализе этого кода анализатору и понадобился механизм анализа потока данных. Какое бы значение не находилось в переменной length, после деления по модулю будет получено значение в диапазоне [0..2]. Анализатор PVS-Studio умеет работать с диапазонами, точными значениями и множествами. Т. е. речь идёт про Value Range Analysis. В данном случае будет использован именно диапазон значений.


Продолжим вычисления:


size_t extraBytes = 3 - [0..2];

Получается, что переменная extraBytes никогда не будет равна нулю. Анализатор вычислит следующий возможный диапазон её значений: [1..3].


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


if (extraBytes > 0)

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


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


// calculate extra bytes needed to get a multiple of 3
size_t extraBytes = 3 - length % 3; // 3-6%3 = 3

// number of base64 bytes
size_t encodedBytes = 4 * (length + extraBytes) / 3; // 4*(6+3)/3 = 12

std::string encoded_string(encodedBytes, '=');

Уже получилось, что выходная строка будет содержать 12 символов, а не 8. Дальше тоже всё будет работать неправильно – даже нет смысла вдаваться в подробности.


Вот так легко и просто статический анализ нашёл ошибку в коде. А представьте, ведь кто-то будет мучиться и отлаживаться, чтобы понять, почему неправильно происходит кодирование символов в кодировку Base64. Здесь мы, кстати, подходим к вопросу качества используемых сторонних библиотек, который я рассматривал в публикации "Почему важно проводить статический анализ открытых библиотек, которые вы добавляете в свой проект".


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


Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Andrey Karpov. Why PVS-Studio Uses Data Flow Analysis: Based on Gripping Error in Open Asset Import Library.

Теги:си++c++программированиебагстатический анализ кодаOpen Asset Import Libraryassimpоткрытый исходный кодpvs-studio
Хабы: Блог компании PVS-Studio Open source C++ Алгоритмы
Всего голосов 16: ↑12 и ↓4 +8
Просмотры1.2K

Комментарии 5

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Похожие публикации

Лучшие публикации за сутки