Что такое статический разбор
Значение слова «статический»
1. Относящийся к статике (в 1 знач.); связанный с состоянием покоя, равновесия, неподвижности. Статическая теория. Статический уровень воды. Статическое давление. Статическая нагрузка на рельсы (нагрузка, производимая вагоном на стоянке).
2. То же, что статичный. Статический художественный образ. □ Вы вносите в это дело сюжет, динамическое начало, тогда как натюрморт — вещь статическая. Андроников, Письмо к Юрию Пименову.
Источник (печатная версия): Словарь русского языка: В 4-х т. / РАН, Ин-т лингвистич. исследований; Под ред. А. П. Евгеньевой. — 4-е изд., стер. — М.: Рус. яз.; Полиграфресурсы, 1999; (электронная версия): Фундаментальная электронная библиотека
СТАТИ’ЧЕСКИЙ, ая, ое; в качестве кратк. форм употр. стати́чен, чна, чно. 1. только полн. формы. Прил. к статика в 1 знач.; основанный на законах статики (мех.). С. расчет. Статически (нареч.) неопределимая система. 2. перен. Прил. к статика во 2 знач.; рассматривающий внутреннее соотношение явлений независимо от развития (книжн.). Статическое описание, изучение. 3. только полн. формы. Прил., по знач. связанное со свойствами электрического заряда, находящегося в равновесии (физ.). Статическое электричество. Статическая индукция. Статическая емкость. ◊
Источник: «Толковый словарь русского языка» под редакцией Д. Н. Ушакова (1935-1940); (электронная версия): Фундаментальная электронная библиотека
стати́ческий
1. связанный, соотносящийся по значению с существительным статика; свойственный, характерный для него
2. то же, что статичный ◆ Флокены резко снижают статическую и особенно усталостную прочность изделий, поэтому наличие их в готовых изделиях недопустимо. Б. С. Натапов, Н. А. Благовещенский, «Термическая обработка металлов», 1955 г.
3. информ. вычисленный, созданный, записанный или выделенный до запуска программы и, как правило, неизменяемый на стадии исполнения программы ◆ По времени способы назначения разделяются на две категории: статические ― распределение выполняется на этапе написания, компиляции или старта программы (до реального начала вычислений); динамические ― распределение осуществляется в процессе исполнения. Владимир Карпов, Алексей Лобанов, «Кризисы программного жанра», 2011 г. // «За науку» (цитата из НКРЯ)
Делаем Карту слов лучше вместе
Привет! Меня зовут Лампобот, я компьютерная программа, которая помогает делать Карту слов. Я отлично умею считать, но пока плохо понимаю, как устроен ваш мир. Помоги мне разобраться!
Спасибо! Я обязательно научусь отличать широко распространённые слова от узкоспециальных.
Насколько понятно значение слова сосняк (существительное):
Всем привет. На одном из код-ревью я столкнулся с мыслью, что многие, а чего скрывать и я сам, не то чтобы хорошо понимаем когда нужно использовать ключевое слова static. В данной статье я хотел бы поделиться своими знаниями и информацией по поводу ключевого слова static. Статья будет полезна как начинающим программистам, так и людям, работающим с языком С++. Для понимания статьи у вас должны быть знания о процессе сборки проектов и владение языком С/С++ на базовом уровне. Кстати, static используется не только в С++, но и в С. В этой статье я буду говорить о С++, но имейте в виду, что всё то, что не связано с объектами и классами, в основном применимо и к языку С.
Что такое static?
Где используется?
Ниже приведена схема, как и где используется static в программе.
А теперь я постараюсь детально описать все то, что изображено на схеме. Поехали!
Статические переменные внутри функции
Если не использовать static в строке 4, выделение памяти и инициализация переменной count происходит при каждом вызове функции counter(), и уничтожается каждый раз, когда функция завершается. Но если мы сделаем переменную статической, после инициализации (при первом вызове функции counter()) область видимости count будет до конца функции main(), и переменная будет хранить свое значение между вызовами функции counter().
Статические объекты класса
В строке 3 мы создаем класс Base с конструктором (строка 5) и деструктором (строка 8). При вызове конструктора либо деструктора мы выводим название метода класса в консоль. В строке 14 мы создаем статический объект obj класса Base. Создание этого статического объекта будет происходить только при первом вызове функции foo() в строке 18.
Из-за того, что объект статический, деструктор вызывается не при выходе из функции foo() в строке 15, а только при завершении программы, т.к. статический объект разрушается при завершении программы. Ниже приведен пример той же программы, за исключением того, что наш объект нестатический.
Если мы уберем static при создании переменной в функции foo(), то разрушение объекта будет происходить в строке 15 при каждом вызове функции. В таком случае вывод программы будет вполне ожидаемый для локальной переменной с выделенной памятью на стеке:
Статические члены класса
В сравнении с предыдущими вариантами использования, статические члены класса немного сложнее для понимания. Давайте разберемся, почему. Предположим, у нас есть следующая программа:
В нашем примере мы создали класс А (строка 3) и класс В (строка 9) со статическими членами класса (строка 15). Мы предполагаем, что при создании объекта b в строке 19 будет создан объект a в строке 15. Так бы и произошло, если бы мы использовали нестатические члены класса. Но вывод программы будет следующим:
Причиной такого поведения является то, что статические члены класса не инициализируются с помощью конструктора, поскольку они не зависят от инициализации объекта. Т.е. в строке 15 мы только объявляем объект, а не определяем его, так как определение должно происходить вне класса с помощью оператора разрешения области видимости (::). Давайте определим члены класса B.
Теперь, после того как мы определили наш статический член класса в строке 18, мы можем увидеть следующий результат программы:
Constructor A
Constructor B
Destructor B
Destructor A
Нужно помнить, что член класса будет один для всех экземпляров класса B, т.е. если мы создали три объекта класса B, то конструктор статического члена класса будет вызван только один раз. Вот пример того, о чем я говорю:
Constructor A
Constructor B1
Constructor B2
Constructor B3
Destructor B3
Destructor B2
Destructor B1
Destructor A
Статические функции
Для того чтобы исправить данную проблему, одну из функций мы объявим статической. Например эту:
В этом случае вы говорите компилятору, что доступ к статическим функциям ограничен файлом, в котором они объявлены. И он имеет доступ только к функции sum() из math.cpp файла. Таким образом, используя static для функции, мы можем ограничить область видимости этой функции, и данная функция не будет видна в других файлах, если, конечно, это не заголовочный файл (.h).
Статические функции-члены класса (методы)
Статическую функцию-член вы можете использовать без создания объекта класса. Доступ к статическим функциям осуществляется с использованием имени класса и оператора разрешения области видимости (::). При использовании статической функции-члена есть ограничения, такие как:
В классе A в строке 8 у нас есть статическая функция-член foo(). В строке 14, мы вызываем функцию используя имя класса и оператор разрешения области видимости и получаем следующий результат программы:
Из вывода видно, что никакого создания объекта нет и конструктор/деструктор не вызывается.
Если бы метод foo() был бы нестатическим, то компилятор выдал бы ошибку на выражение в строке 14, т.к. нужно создать объект для того, чтобы получить доступ к его нестатическим методам.
Заключение
В одной статье в интернете я нашел совет от автора – «Используйте static везде, где только можно». Я хотел бы написать, почему так делать не стоит, а стоит использовать только в случае необходимости.
Статический анализ – от знакомства до интеграции
Устав от нескончаемого code review или отладки, временами задумываешься, как бы упростить себе жизнь. И немного поискав, ну или случайно наткнувшись, можно увидеть волшебное словосочетание: «Статический анализ». Давайте посмотрим, что это такое и как он может взаимодействовать с вашим проектом.
Собственно говоря, если вы пишете на каком-либо современном языке, тогда, даже не догадываясь об этом, вы пропускали его через статический анализатор. Дело в том, что любой современный компилятор предоставляет пусть и крохотный, но набор предупреждений о потенциальных проблемах в коде. Например, компилируя C++ код в Visual Studio вы можете увидеть следующее:
В этом выводе мы видим, что переменная var так и не была использована нигде в функции. Так что на самом деле вы почти всегда пользовались простеньким статическим анализатором кода. Однако, в отличие от профессиональных анализаторов, таких как Coverity, Klocwork или PVS-Studio, предоставляемые компилятором предупреждения могут указывать только на небольшой спектр проблем.
Если вы не знаете наверняка, что такое статический анализ и как его внедрять, прочтите эту статью, чтобы более подробно ознакомиться с этой методологией.
Зачем нужен статический анализ?
В двух словах: ускорение и упрощение.
Статический анализ позволяет найти уйму различных проблем в коде: начиная от неправильного использования конструкций языка, заканчивая опечатками. Например, вместо
Вы написали следующий код:
Как видите, в последней строке появилась опечатка. Например, PVS-Studio выдаёт следующее предупреждение:
V537 Consider reviewing the correctness of ‘y’ item’s usage.
Если хотите потыкать в эту ошибку руками, то попробуйте готовый пример на Compiler Explorer: *клик*.
И как вы понимаете, не всегда можно обратить внимания на подобные участки кода сразу и из-за этого можно засесть за отладку на добрый час, недоумевая, почему всё работает так странно.
Однако это явная ошибка. А если разработчик написал неоптимальный код из-за того, что позабыл какую-либо тонкость языка? Или же вовсе допустил в коде undefined behavior? К сожалению, подобные случаи совершенно обыденны и львиная часть времени тратится на то, чтобы отладить специфично работающий код, который содержит опечатки, типичные ошибки или undefined behavior.
Именно для этих ситуаций и появился статический анализ. Это помощник для разработчика, который укажет ему на различные проблемы в коде и объяснит в документации почему так писать не нужно, к чему это может привести и как это исправить. Вот пример как это может выглядеть: *клик*.
Больше интересных ошибок, которые может обнаружить анализатор, вы можете найти в статьях:
Примечание. Статический анализ не заменяет и не отменяет такую полезную вещь, как обзоры кода. Он дополняет этот процесс, помогая заранее заметить и исправить опечатки, неточности, опасные конструкции. Намного продуктивнее сосредоточиться при обзорах кода на алгоритмах и понятности кода, а не над высматриванием не там поставленной скобки или читать скучные функции сравнения.
0. Знакомство с инструментом
Всё начинается с пробной версии. Действительно, сложно решиться внедрять что-либо в процесс разработки, если никогда до этого не видел инструмента вживую. Поэтому первым делом стоит скачать пробную версию.
Что вы узнаете на этом этапе:
Дело в том, что обычно на проекты с большой кодовой базой статические анализаторы выдают огромное количество предупреждений. Нет необходимости исправлять их все, так как ваш проект уже работает, а значит эти проблемы не являются критичными. Однако вы можете посмотреть на самые интересные предупреждения и исправить их при необходимости. Для этого нужно отфильтровать вывод и оставить только наиболее достоверные сообщения. В плагине PVS-Studio для Visual Studio это делается фильтрацией по уровням и категориям ошибок. Для наиболее точного вывода оставьте включёнными только High и General:
Действительно, 178 предупреждений просмотреть значительно проще, чем несколько тысяч…
Во вкладках Medium и Low часто попадаются хорошие предупреждения, однако в эти категории занесены те диагностики, которые имеют меньшую точность (достоверность). Подробнее про уровни предупреждений и варианты работы под Windows можно посмотреть тут: *клик*.
Успешно просмотрев самые интересные ошибки (и успешно исправив их) стоит подавить оставшиеся предупреждения. Это нужно для того, чтобы новые предупреждения не терялись среди старых. К тому же статический анализатор – это помощник для программиста, а не список для багов. 🙂
1. Автоматизация
После знакомства наступает время настройки плагинов и интеграции в CI. Это необходимо сделать до того, как программисты начнут использовать статический анализатор. Дело в том, что программист может забыть включить анализ или вовсе не захотеть. Для этого нужно сделать некоторую финальную проверку всего, чтобы непроверенный код не мог попасть в общую ветку разработки.
Что вы узнаете на данном этапе:
А теперь приступим к сервисам непрерывной интеграции (CI). Любой анализатор можно внедрить в них без каких-либо серьезных проблем. Для этого нужно создать отдельный этап в pipeline, который обычно находится после сборки и юнит-тестов. Делается это при помощи различных консольных утилит. Например, PVS-Studio предоставляет следующие утилиты:
В системах под управлением Windows отсутствует возможность установить анализатор из пакетного менеджера, однако есть возможность развернуть анализатор из командной строки:
Подробнее о развёртывании PVS-Studio в системах под управлением Windows можно почитать *тут*.
После установки нужно запустить непосредственно анализ. Однако делать это рекомендуется только после того, как прошла компиляция и тесты. Это связано с тем, что для статического анализа обычно требуется в два раза больше времени, чем для компиляции.
Так как способ запуска зависит от платформы и особенностей проекта, я покажу вариант для C++ (Linux) в качестве примера:
Первая команда выполнит анализ, а вторая конвертирует отчёт в текстовый формат, выведет его на экран и вернёт отличный от 0 код возврата в случае наличия предупреждений. Подобный механизм удобно использовать для блокировки сборки при наличии сообщений об ошибках. Однако, вы всегда можете убрать флаг -w и не блокировать сборку, содержащую предупреждения.
Примечание. Текстовый формат — это неудобно. Он приводится просто для примера. Обратите внимание на более интересный формат отчёта — FullHtml. Он позволяет осуществлять навигацию по коду.
Подробнее про настройку анализа на CI можно прочитать в статье «PVS-Studio и Continuous Integration» (Windows) или «Как настроить PVS-Studio в Travis CI» (Linux).
Хорошо, вы настроили работу анализатора на сборочном сервере. Теперь, если кто-то залил непроверенный код, будет падать этап проверки, и вы сможете обнаружить проблему, однако это не совсем удобно, так как эффективнее проверять проект не после того, как произошло слияние веток, а до него, на этапе pull request’а.
В целом настройка анализа pull request’а не сильно отличается от обычного запуска анализа на CI. За исключением необходимости получить список изменённых файлов. Обычно их можно получить, запросив разницу между ветками при помощи git:
Теперь нужно передать анализатору на вход этот список файлов. Например, в PVS-Studio это реализовано при помощи флага -S:
Подробнее про анализ pull request’ов можно узнать *тут*. Даже если вашего CI нет в списке указанных в статье сервисов, вам будет полезен общий раздел, посвященный теории этого типа анализа.
Настроив анализ pull request’ов вы сможете блокировать содержащие предупреждения коммиты, тем самым создав границу, которую непроверенный код не сможет пересечь.
Это всё безусловно хорошо, однако хотелось бы иметь возможность посмотреть все предупреждения в одном месте. Не только от статического анализатора, но и от юнит-тестов или от динамического анализатора. Для это существуют различные сервисы и плагины. PVS-Studio, например, имеет плагин для интеграции в SonarQube.
2. Интеграция на машины разработчиков
Теперь пришло время установки и настройки анализатора для повседневного использования при разработке. К этому моменту вы уже познакомились с большей частью способов работы, поэтому это можно назвать самой лёгкой частью.
Как самый простой вариант – разработчики сами могут установить необходимый анализатор. Однако это займёт много времени и отвлечёт их от разработки, поэтому вы можете автоматизировать этот процесс, используя установщик и нужные флаги. Для PVS-Studio есть различные флаги для автоматизированной установки. Впрочем, всегда есть пакетные менеджеры, например, Chocolatey (Windows), Homebrew (macOS) или десятки вариантов для Linux.
Затем нужно будет установить необходимые плагины, например, для Visual Studio, IDEA, Rider etc.
3. Ежедневное использование
На этом этапе пора сказать пару слов о способах ускорения работы анализатора при ежедневном использовании. Полный анализ всего проекта занимает очень много времени, однако часто ли мы меняем код разом во всём проекте? Едва ли существует настолько масштабный рефакторинг, что сразу затронет всю кодовую базу. Количество изменяемых файлов за раз редко превышает десяток, поэтому их и есть смысл анализировать. Для подобной ситуации существует режим инкрементального анализа. Только не пугайтесь, это не ещё один инструмент. Это специальный режим, который позволяет анализировать только изменённые файлы и их зависимости, причём это происходит автоматически после сборки, если вы работаете в IDE c установленным плагином.
В случае, если анализатор обнаружит в недавно измененном коде проблемы, то сообщит об этом самостоятельно. Например, PVS-Studio скажет вам об этом при помощи оповещения:
Само собой недостаточно сказать разработчикам использовать инструмент. Нужно как-то им рассказать, что это вообще и как это есть. Вот, например, статьи про быстрый старт для PVS-Studio, однако подобные туториалы вы сможете найти для любого предпочитаемого вами инструмента:
Ещё на этапе знакомства с инструментом мы подавили очень много предупреждений во время одного из первых запусков. Увы, но статические анализаторы не идеальны, поэтому время от времени выдают ложные срабатывания. Подавить их обычно легко, например в плагине PVS-Studio для Visual Studio достаточно нажать на одну кнопку:
Однако вы можете не только подавлять их. Например, вы можете сообщить в поддержку о наличии проблемы. Если ложное срабатывание возможно исправить, то в будущих обновлениях вы можете обратить внимание на то, что с каждым разом становится всё меньше и меньше специфичных для вашей кодовой базы ложных срабатываний.
После интеграции
Вот мы и прошли все этапы по интеграции статического анализа в процесс разработки. Несмотря на важность настройки подобных инструментов на CI, самым главным местом запуска является именно компьютер разработчика. Ведь статический анализатор – это не судья, который говорит где-то далеко от вас, что код никуда не годится. Напротив, это помощник, который подсказывает, если вы устали и напоминает, если вы о чём-либо забыли.
Правда без регулярного использования статический анализ вряд ли значительно упростит разработку. Ведь самая его главная польза для разработчика заключается не столько в поиске сложных и спорных участков кода, сколько в раннем их обнаружении. Согласитесь, что обнаружить проблему, когда правки ушли на тестирование, не только неприятно, но и очень долго. Статический анализ же при регулярном использовании просматривает каждое изменение прямо на вашем компьютере и сообщает о подозрительных местах во время работы над кодом.
А если вы или ваши коллеги всё ещё не уверены, стоит ли внедрять анализатор, то предлагаю сейчас перейти к чтению статьи «Причины внедрить в процесс разработки статический анализатор кода PVS-Studio». В ней разобраны типовые опасения разработчиков о том, что статический анализ будет отнимать их время и так далее.
Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Maxim Zvyagintsev. Static Analysis: From Getting Started to Integration.
О статическом анализе начистоту
Последнее время все чаще говорят о статическом анализе как одном из важных средств обеспечения качества разрабатываемых программных продуктов, особенно с точки зрения безопасности. Статический анализ позволяет находить уязвимости и другие ошибки, его можно использовать в процессе разработки, интегрируя в настроенные процессы. Однако в связи с его применением возникает много вопросов. Чем отличаются платные и бесплатные инструменты? Почему недостаточно использовать линтер? В конце концов, при чем тут статистика? Попробуем разобраться.
Сразу ответим на последний вопрос – статистика ни при чем, хотя статический анализ часто по ошибке называют статистическим. Анализ статический, так как при сканировании не происходит запуск приложения.
Для начала разберемся, что мы хотим искать в программном коде. Статический анализ чаще всего применяют для поиска уязвимостей – участков кода, наличие которых может привести к нарушению конфиденциальности, целостности или доступности информационной системы. Однако те же технологии можно применять для поиска и других ошибок или особенностей кода.
Оговоримся, что в общем виде задача статического анализа алгоритмически неразрешима (например, по теореме Райса). Поэтому приходится либо ограничивать условия задачи, либо допускать неточность в результатах (пропускать уязвимости, давать ложные срабатывания). Оказывается, что на реальных программах рабочим оказывается второй вариант.
Существует множество платных и бесплатных инструментов, которые заявляют поиск уязвимостей в приложениях, написанных на разных языках программирования. Рассмотрим, как обычно устроен статический анализатор. Дальше речь пойдет именно о ядре анализатора, об алгоритмах. Конечно, инструменты могут отличаться по дружелюбности интерфейса, по набору функциональности, по набору плагинов к разным системам и удобству использования API. Наверное, это тема для отдельной статьи.
Промежуточное представление
В схеме работы статического анализатора можно выделить три основных шага.
Аналогично компиляторам, лексический и синтаксический анализ применяются для построения внутреннего представления, чаще всего — дерева разбора (AST, Abstract Syntax Tree). Лексический анализ разбивает текст программы на минимальные смысловые элементы, на выходе получая поток лексем. Синтаксический анализ проверяет, что поток лексем соответствует грамматике языка программирования, то есть полученный поток лексем является верным с точки зрения языка. В результате синтаксического анализа происходит построение дерева разбора – структуры, которая моделирует исходный текст программы. Далее применяется семантический анализ, он проверяет выполнение более сложных условий, например, соответствие типов данных в инструкциях присваивания.
Дерево разбора можно использовать как внутреннее представление. Также из дерева разбора можно получить другие модели. Например, можно перевести его в трехадресный код, по которому, в свою очередь, строится граф потока управления (CFG). Обычно CFG является основной моделью для алгоритмов статического анализа.
При бинарном анализе (статическом анализе двоичного или исполняемого кода) также строится модель, но здесь уже используются практики обратной разработки: декомпиляции, деобфускации, обратной трансляции. В результате можно получить те же модели, что и из исходного кода, в том числе и исходный код (с помощью полной декомпиляции). Иногда сам бинарный код может служить промежуточным представлением.
Теоретически, чем ближе модель к исходному коду, тем хуже будет качество анализа. На самом исходном коде можно делать разве что поиск по регулярным выражениям, что не позволит найти хоть сколько-нибудь сложную уязвимость.
Анализ потока данных
Одним из основных алгоритмов статического анализа является анализ потока данных. Задача такого анализа — определить в каждой точке программы некоторую информацию о данных, которыми оперирует код. Информация может быть разная, например, тип данных или значение. В зависимости от того, какую информацию нужно определить, можно сформулировать задачу анализа потока данных.
Например, если необходимо определить, является ли выражение константой, а также значение этой константы, то решается задача распространения констант (constant propagation). Если необходимо определить тип переменной, то можно говорить о задаче распространения типов (type propagation). Если необходимо понять, какие переменные могут указывать на определенную область памяти (хранить одни и те же данные), то речь идет о задаче анализа синонимов (alias analysis). Существует множество других задач анализа потока данных, которые могут использоваться в статическом анализаторе. Как и этапы построения модели кода, данные задачи также используются в компиляторах.
В теории построения компиляторов описаны решения задачи внутрипроцедурного анализа потока данных (отследить данные необходимо в рамках одной процедуры/функции/метода). Решения опираются на теорию алгебраических решеток и другие элементы математических теорий. Решить задачу анализа потока данных можно за полиномиальное время, то есть за приемлемое для вычислительных машин время, если условия задачи удовлетворяют условиям теоремы о разрешимости, что на практике происходит далеко не всегда.
Расскажем подробнее про решение задачи внутрипроцедурного анализа потока данных. Для постановки конкретной задачи, помимо определения искомой информации, нужно определить правила изменения этой информации при прохождении данных по инструкциям в CFG. Напомним, что узлами в CFG являются базовые блоки – наборы инструкций, выполнение которых происходит всегда последовательно, а дугами обозначается возможная передача управления между базовыми блоками.
Для каждой инструкции 
определяются множества:
Второе соотношение формулирует правила, по которым информация «объединяется» в точках слияния дуг CFG ( 
– предшественники в CFG). Может использоваться операция объединения, пересечения и некоторые другие.
Искомая информация (множество значений введенных выше функций) формализуется как алгебраическая решетка. Функции 
и 
рассматриваются как монотонные отображения на решётках (функции потока). Для уравнений потока данных решением является неподвижная точка этих отображений.
Алгоритмы решения задач анализа потока данных ищут максимальные неподвижные точки. Существует несколько подходов к решению: итеративные алгоритмы, анализ сильно связных компонент, T1-T2 анализ, интервальный анализ, структурный анализ и так далее. Существуют теоремы о корректности указанных алгоритмов, они определяют область их применимости на реальных задачах. Повторюсь, условия теорем могут не выполняться, что приводит к усложнению алгоритмов и неточности результатов.
Межпроцедурный анализ
На практике необходимо решать задачи межпроцедурного анализа потока данных, так как редко уязвимость будет полностью локализовываться в одной функции. Существует несколько общих алгоритмов.
Построение общего графа потока управления программы, в котором вызовы функций заменены на переходы по адресу начала вызываемой функции, а инструкции возврата заменены на переходы на все инструкции, следующие после всех инструкций вызова данной функции. Такой подход добавляет большое количество нереализуемых путей выполнения, что сильно уменьшает точность анализа.
Алгоритм, аналогичный предыдущему, но при переходе на функцию происходит сохранение контекста – например, стекового фрейма. Таким образом решается проблема создания нереализуемых путей. Однако алгоритм применим при ограниченной глубине вызовов.
Построение информации о функциях (function summary). Наиболее применимый алгоритм межпроцедурного анализа. Он основан на построении summary для каждой функции: правил, по которым преобразуется информация о данных при применении данной функции в зависимости от различных значений входных аргументов. Готовые summary используются при внутрипроцедурном анализе функций. Отдельной сложностью здесь является определение порядка обхода функций, так как при внутрипроцедурном анализе для всех вызываемых функций уже должны быть построены summary. Обычно создаются специальные итеративные алгоритмы обхода графа вызовов (call graph).
Межпроцедурный анализ потока данных является экспоненциальной по сложности задачей, из-за чего анализатору необходимо проводить ряд оптимизаций и допущений (невозможно найти точное решение за адекватное для вычислительных мощностей время). Обычно при разработке анализатора необходимо искать компромисс между объемом потребляемых ресурсов, временем анализа, количеством ложных срабатываний и найденных уязвимостей. Поэтому статический анализатор может долго работать, потреблять много ресурсов и давать ложные срабатывания. Однако без этого невозможно находить важнейшие уязвимости.
Именно в этом моменте серьезные статические анализаторы отличаются от множества открытых инструментов, которые, в том числе, могут себя позиционировать в поиске уязвимостей. Быстрые проверки за линейное время хороши, когда результат нужно получить оперативно, например, в процессе компиляции. Однако таким подходом нельзя найти наиболее критичные уязвимости – например, связанные с внедрением данных.
Taint-анализ
Отдельно стоит остановиться на одной из задач анализа потока данных — taint-анализе. Taint-анализ позволяет распространить по программе флаги. Данная задача является ключевой для информационной безопасности, так как именно с помощью нее обнаруживаются уязвимости, связанные с внедрением данных (внедрения в SQL, межсайтовый скриптинг, открытые перенаправления, подделка файлового пути и так далее), а также с утечкой конфиденциальных данных (запись пароля в журналы событий, небезопасная передача данных).
Попробуем смоделировать задачу. Пусть мы хотим отследить n флагов – 
. Множеством информации здесь будет множество подмножеств 
, так как для каждой переменной в каждой точке программы мы хотим определить ее флаги.
Далее мы должны определить функции потока. В данном случае функции потока могут определяться следующими соображениями.
Наконец, нужно определить правила слияния информации в точках соединения дуг CFG. Слияние определяется по правилу объединения, то есть если из разных базовых блоков пришли разные наборы флагов для одной переменной, то при слиянии они объединяются. В том числе отсюда появляются ложные срабатывания: алгоритм не гарантирует, что путь в CFG, на котором появился флаг, может быть исполнен.
Например, необходимо обнаруживать уязвимости типа «Внедрение в SQL» (SQL Injection). Такая уязвимость возникает, когда непроверенные данные от пользователя попадают в методы работы с базой данных. Необходимо определить, что данные поступили от пользователя, и добавить таким данным флаг taint. Обычно в базе правил анализатора задаются правила постановки флага taint. Например, поставить флаг возвращаемому значению метода getParameter() класса Request.
Далее необходимо распространить флаг по всей анализируемой программе с помощью taint-анализа, учитывая, что данные могут быть валидированы и флаг может исчезнуть на одном из путей исполнения. В анализаторе задается множество функций, которые снимают флаги. Например, функция валидации данных от html-тегов может снимать флаг для уязвимости типа «Межсайтовый скриптинг» (XSS). Или функция привязки переменной к SQL-выражению снимает флаг о внедрении в SQL.
Правила поиска уязвимостей
В результате применения указанных выше алгоритмов промежуточное представление дополняется информацией, необходимой для поиска уязвимостей. Например, в модели кода появляется информация о том, каким переменным принадлежат определенные флаги, какие данные являются константными. Правила поиска уязвимостей формулируются в терминах модели кода. Правила описывают, какие признаки в итоговом промежуточном представлении могут говорить о наличии уязвимости.
Например, можно применить правило поиска уязвимости, которое будет определять вызов метода с параметром, у которого есть флаг taint. Возвращаясь к примеру SQL-инъекции, мы проверим, что переменные с флагом taint не попадают в функции запроса к базе данных.
Получается, важной частью статического анализатора, помимо качества алгоритмов, является конфигурация и база правил: описание, какие конструкции в коде порождают флаги или другую информацию, какие конструкции валидируют такие данные, и для каких конструкций критично использование таких данных.
Другие подходы
Помимо анализа потока данных существуют и другие подходы. Одним из известных является символьное выполнение или абстрактная интерпретация. В этих подходах происходит выполнение программы на абстрактных доменах, вычисление и распространение ограничений по данным в программе. С помощью такого подхода можно не просто находить уязвимость, но и вычислить условия на входные данные, при которых уязвимость является эксплуатируемой. Однако у такого подхода есть и серьезные минусы – при стандартных решениях на реальных программах алгоритмы экспоненциально взрываются, а оптимизации приводят к серьезным потерям в качестве анализа.
Выводы
Под конец, думаю, стоит подвести итог, сказав о плюсах и минусах статического анализа. Логично, что сравнивать будем с динамическим анализом, в котором поиск уязвимостей происходит при выполнении программы.
Минусами статического анализа является неизбежное наличие ложных срабатываний, потребление ресурсов и длительное время сканирований на больших объемах кода. Однако, эти минусы неизбежны, исходя из специфики алгоритмов. Как мы увидели, быстрый анализатор никогда не найдет реальную уязвимость типа SQL-инъекции и подобных.
Об остальных сложностях использования инструментов статического анализа, которые, как оказывается, вполне можно преодолевать, мы писали в другой статье.