[Open source, C++, Алгоритмы] Зачем PVS-Studio использует анализ потока данных: по мотивам интересной ошибки в Open Asset Import Library
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Анализ потока данных является неотъемлемой частью любого современного статического анализатора кода. Однако, со стороны, не очень понятно, что это и главное – зачем нужно. До сих пор некоторые ассоциируют статический анализ с поиском чего-то в коде по определённому шаблону. Поэтому время от времени мы пишем заметки, в которых демонстрируем, как та или иная технология, используемая в анализаторе 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 :). Список дополнительных статей на близкую тематику:
- 31 февраля;
- Использование машинного обучения в статическом анализе исходного кода программ;
- Как внедрить статический анализатор кода в 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;
И как раз при анализе этого кода анализатору и понадобился механизм анализа потока данных. Какое бы значение не находилось в переменной 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.
===========
Источник:
habr.com
===========
Похожие новости:
- [Open source, C++, Алгоритмы] Why PVS-Studio Uses Data Flow Analysis: Based on Gripping Error in Open Asset Import Library
- [C++] CRTP: Пример на паттерне «Мост»
- [Open source, Виртуализация, Разработка под Linux, Openshift] 14 лучших практик разработки приложений на OpenShift
- [Анализ и проектирование систем, Управление разработкой, Научно-популярное] Почему чтобы переместить кнопку, нужно две недели (перевод)
- [Информационная безопасность, Программирование, .NET, C#, Разработка под Windows] Как следить (наблюдать) за компьютером. Часть 1 — делаем скриншоты пользователей
- [C++, Разработка игр] Сборка Open Source GTA VC и GTA III в Linux
- [Мессенджеры, Open source, Системное администрирование, PHP, Программирование] Рефакторинг пет проекта: докеризация, метрики, тесты
- [Программирование, C++, Тестирование веб-сервисов, Конференции] Как достичь полной автоматизации в Automotive тестировании и особенности Move конструктора: узнаем 25 февраля
- [Программирование, C++, Работа с 3D-графикой, Разработка игр, CGI (графика)] Vulkan. Руководство разработчика. Swap chain (перевод)
- [C++, Учебный процесс в IT, Карьера в IT-индустрии] Вебинар «Стандарт С++20»: обзор новых возможностей C++, введённых Стандартом C++20
Теги для поиска: #_open_source, #_c++, #_algoritmy (Алгоритмы), #_si++ (си++), #_c++, #_programmirovanie (программирование), #_bag (баг), #_staticheskij_analiz_koda (статический анализ кода), #_open_asset_import_library, #_assimp, #_otkrytyj_ishodnyj_kod (открытый исходный код), #_pvsstudio, #_blog_kompanii_pvsstudio (
Блог компании PVS-Studio
), #_open_source, #_c++, #_algoritmy (
Алгоритмы
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 09:04
Часовой пояс: UTC + 5
Автор | Сообщение |
---|---|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
Анализ потока данных является неотъемлемой частью любого современного статического анализатора кода. Однако, со стороны, не очень понятно, что это и главное – зачем нужно. До сих пор некоторые ассоциируют статический анализ с поиском чего-то в коде по определённому шаблону. Поэтому время от времени мы пишем заметки, в которых демонстрируем, как та или иная технология, используемая в анализаторе 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 :). Список дополнительных статей на близкую тематику:
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;
И как раз при анализе этого кода анализатору и понадобился механизм анализа потока данных. Какое бы значение не находилось в переменной 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. =========== Источник: habr.com =========== Похожие новости:
Блог компании PVS-Studio ), #_open_source, #_c++, #_algoritmy ( Алгоритмы ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 09:04
Часовой пояс: UTC + 5