Pull to refresh
281.77
PVS-Studio
Static Code Analysis for C, C++, C# and Java

Сортировка предупреждений статических анализаторов по приоритету при поиске и исправлении программных ошибок

Reading time 16 min
Views 3.2K
Original author: Lori Flynn
За 2015 год в Национальной базе данных уязвимостей США (National Vulnerability Database, NVD) было зарегистрировано 6,488 новых программных уязвимостей, всего же в ней насчитывается 74,885 уязвимостей, найденных за период 1988-2016 гг. Инструменты статического анализа проверяют исходный код программ на наличие дефектов, в том числе потенциальных уязвимостей защиты, и выдают диагностические сообщения (предупреждения), в которых указывается местоположение предполагаемого дефекта, его характер, и, как правило, дополнительная контекстуальная информация. Достоверность таких предупреждений затем оценивается пользователем. Трудозатраты на проверку всех предупреждений и исправление всех подтвержденных ошибок вручную зачастую значительно превосходят бюджет и сроки проекта. По этой причине пользователи нуждаются в инструментах, которые позволили бы сортировать предупреждения по степени важности, тем самым определяя порядок их проверки. Настоящая статья посвящена проводимому нами исследованию данного вопроса с использованием классификационных моделей, призванных помочь специалистам по анализу и программистам в классификации предупреждений по приоритету и определении оптимального порядка исправления соответствующих ошибок.

Предупреждения статических анализаторов: проблемы и основная задача


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

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

Допустимые соотношения между скоростью и точностью анализа были согласованы в ходе обсуждений между разработчиками статических анализаторов (как закрытых, так и открытых), по итогам которых было определено оптимальное количество выдаваемых предупреждений, которое позволило бы выявлять реальные ошибки, не порождая при этом слишком много ложных срабатываний. На тему того, с каким трудом проходили эти обсуждения, есть примечательная статья Эла Бесси из Coverity: A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World .

Предыдущее исследование выявило уменьшение совпадения по типам дефектов, выявляемых наиболее популярными инструментами. С одной стороны, это объясняется тем, что разработка статического анализатора с нуля — это трудоемкая задача, и производители просто не могут включить все виды анализа сразу. С другой стороны, диагностики для некоторых видов ошибок требуют большого количества памяти, времени для анализа или дискового пространства. Такие диагностики не включаются в инструмент, если они пользуются малым спросом среди пользователей.

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

Согласно эмпирическим данным, полученным Кременеком и др., у анализаторов, которые способны эффективно выявлять программные ошибки, ложные срабатывания составляют 30% и выше от общего количества выдаваемых ими предупреждений. Наша задача, таким образом, состоит в том, чтобы добиться максимально возможной автоматизации процесса установления истинности/ложности предупреждений. Мы также определяем степень достоверности у тех предупреждений, которые требуют проверки пользователем, для того, чтобы облегчить процесс сортировки предупреждений по приоритету.

Наш подход


Исследования других авторов, посвященные проблеме объединения предупреждений от разных инструментов и их оценки — [Meng 2008], [Kong 2007], [Kremenek 2004a] и [Plakosh 2014], — опираются на статистические методы, которые не учитывают сложные потенциальные корреляции между различными факторами (например, принимают во внимание меньшее число признаков классификации и/или используют более простые математические модели) либо не дают подробного описания для предупреждений от нескольких инструментов. В то же время имеется множество работ, которые исследуют вопрос классификации предупреждений какого-либо одного инструмента и используют методы их сортировки по приоритету на основе тех же признаков, что учитываются и в наших классификационных моделях. Примеры таких статей: [Heckman 2011], [Ruthruff 2008], [Kremenek 2004b] и [Heckman 2007].

Авторам предыдущих исследований удалось точно установить степень достоверности предупреждений отдельных анализаторов и на основе этого показателя и ряда других факторов классифицировать их по приоритету. Так, авторы исследования Predicting Accurate and Actionable Static Analysis Warnings: An Experimental Approach разработали модели, которые правильно определили ложные срабатывания среди предупреждений статического анализатора FindBugs более чем в 85% случаев. Предупреждения, подлежащие оценке, сортировались по приоритету на основании динамически обновляемых данных о том, исправлялись ли подтвержденные ошибки того или иного типа в прошлом. В предыдущих исследованиях при решении проблемы дифференциации между ложными и реальными ошибками использовались такие методы, как сбор контекстуальной информации о коде, выбор типов предупреждений, слияние данных, машинное обучение, а также математические и статистические модели. Все эти методы и механизмы используются и в нашем исследовании. Кроме того, мы применяем технологию динамического обнаружения дефектов, теорию графов и механизм верификации моделей. Опираясь на работу других исследователей, мы объединили множество признаков классификации, соответствующих параметрам предупреждений и самого кода.

Наш подход также учитывает опыт исследования, проведенного Институтом программной инженерии Карнеги-Меллон (Software Engineering Institute, SEI), Improving the Automated Detection and Analysis of Secure Coding Violations [Plakosh 2014], итогом которого стала разработка трех бинарных логистических регрессионных моделей для классификации предупреждений (за основу были взяты предупреждения, для которых имеются соответствия в базе Стандартов безопасного программирования SEI CERT) — эти модели учитывают, в каких анализаторах срабатывала та или иная диагностика. Другими словами, для трех правил из Стандартов безопасного программирования SEI CERT авторы исследования разработали классификаторы, которые затем были «обучены» на наборе уже проверенных предупреждений от нескольких инструментов. Далее эти классификаторы были протестированы на другом наборе предупреждений, при этом каждый классификатор должен был оценить их как истинные или ложные, после чего точность предсказаний сравнивалась с реальными данными ручной оценки. В этой работе впервые были предложены продвинутые методы статистического анализа набора предупреждений от разных статических анализаторов, позволяющих максимально точно предсказать истинность/ложность того или иного предупреждения.

В нашем исследовании мы дополняем работу SEI за счет внедрения механизма оценки дополнительных классификационных методов и использования намного большего числа признаков классификации. Кроме того, анализируемый нами набор данных отличается большим объемом и разнородностью. Мы разработали классификаторы для правил, а также начальный классификатор, который использует формат идентификатора правил SEI CERT (он включает в себя 3-буквенный префикс, обозначающий тип правила, номер, дефис и название языка программирования, например: «INT33-C») в качестве еще одного признака классификации. Мы продолжаем совершенствовать наши классификационные модели, пробуя разные параметры классификаторов, добавляя новые данные в наборы предупреждений, на которых «обучаются» и тестируются модели, а также экспериментируя с наборами входных данных при разработке классификаторов. Как только классификатор готов, мы применяем его к соответствующим предупреждениям в тестовом наборе для того, чтобы оценить точность предсказания наших моделей. Новизна нашего подхода заключается в том, что мы используем несколько анализаторов, учитываем больше признаков и применяем ряд продвинутых методов классификации, из которых отбираются наиболее производительные.

В команду исследователей из SEI, которая помогает мне в работе над настоящим проектом, входят Дэвид Свобода, Уилл Снейвли, Роберт Стодард, Дэвид Зуброу, Дженнифер Бёрнс, Гильермо Марсе-Сантурьо, Эли Канал, Кристин Бек и Ричард Чин. Наша команда сотрудничает со старшим преподавателем Школы информатики Университета Карнеги — Меллон (CMU's School of Computer Science ) Клэр Ле Гу, которая выступает в роли консультанта. Ее опыт чрезвычайно полезен для нашего проекта, поскольку она занимается исследованиями в области программной инженерии и языков программирования, а именно специализируется на проблемах разработки, отладки и обеспечения качества программных систем. Наше исследование также отвечает задачам, поставленным Министерством обороны в связи с потребностью в технологии оперативного, сопровождаемого и автоматизированного анализа и верификации приложений. Кроме того, наше исследование соответствует одной из двух задач стратегического плана SEI: обеспечение безопасности программно-зависимых систем на протяжении всего их жизненного цикла.

Наш подход позволит специалистам по анализу и программистам сортировать предупреждения по степени важности за счет автоматизации следующих процессов:
  • Определение степени достоверности предупреждения (т.е. вероятности, что то или иное предупреждение является истинным или ложным).
  • Распределение предупреждений по трем категориям: предполагаемые истинные предупреждения (e-TP), предполагаемые ложные срабатывания (e-FP) и промежуточные (I). При этом предупреждения первой группы (e-TP) после обнаружения сразу направляются отладчикам, минуя ручную проверку.
  • Сортировка промежуточных предупреждений на основании их степени достоверности. При этом также могут учитываться дополнительные факторы, имеющие отношение к данному предупреждению, например, риски и расходы, связанные с его обработкой.

При разработке классификатора для некоторого правила из Стандартов безопасного программирования SEI CERT мы используем архивные данные по всем проверенным предупреждениям, относящимся к данному правилу, а также новые данные, собранные в рамках настоящего проекта. Аналогично учитываются архивные и новые данные при создании классификатора для всего набора предупреждений.

Опираясь на опыт упомянутых выше исследований (как внутри SEI, так и за его пределами), мы выделили следующие признаки классификации для включения в наши модели (неполный список):
  • глубина предупреждения (глубина нахождения предполагаемого дефекта в файле)
  • количество значимых строк кода (SLOC) в функции/методе, файле, программе
  • общее количество строк кода (LOC) в функции/методе, файле, программе
  • цикломатическая сложность
  • связность (модулей программы)
  • сцепление ("«элементов модуля)
  • язык
  • совпадающие предупреждения (одинаковые строки кода, файл и правило), выданные всеми анализаторами
  • частота изменений кода
  • число предупреждений (на файл, функцию и т.д.)
  • число токенов в функции/методе
  • число функций/методов в файле
  • число параметров в функции/методе
  • среднее количество токенов
  • среднее количество SLOC
  • частично совпадающие пути к файлам
  • имя класса (где применимо)
  • имя метода/функции
  • имя пакета (где применимо)
  • множество других показателей, специфических для конкретного инструмента, которые могут варьировать для разных предупреждений

Обработка архивных данных по проверенным предупреждениям и соответствующих признаков из приведенного списка происходит с применением четырех методов классификации:
Один из наборов данных, используемых в нашем исследовании, включает в себя результаты оценки предупреждений для 20 баз исходного кода общим объемом 19,237 KLOC (тысяч строк кода)и содержит 3,147 подтвержденных реальных предупреждений и 11,772 подтвержденных ложных срабатывания.

Для проверки этих баз использовался инструмент Source Code Analysis Laboratory (SCALe) CERT -программная платформа, объединяющая в себе средства анализа целого ряда коммерческих, открытых и экспериментальных инструментов. Благодаря тому, что SCALe пользуется возможностями нескольких статических анализаторов, он обнаруживает больше дефектов, чем любой отдельно взятый инструмент. Однако такой подход подразумевает большой объем выходных данных и, соответственно, требует больших трудозатрат для их обработки. Всего с помощью SCALe было проанализировано более 16 миллионов строк кода, включая базы исходных кодов Министерства обороны, систем энергоснабжения, медицинского оборудования и т.п.

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

Приложение также можно использовать для изучения предупреждений. Интерфейс на основе веб-браузера позволяет фильтровать предупреждения и сортировать их по приоритету, просматривать соответствующий участок исходного кода и помечать предупреждения как истинные или ложные. База данных динамически обновляется при внесении изменений.

Мы усовершенствовали SCALe для нашего проекта, так что теперь он может собирать дополнительную информацию по каждому предупреждению и выполнять ряд вспомогательных задач, например, обеспечивать анонимность данных. Дополнительная информация извлекается из нескольких источников. Метрики исходного кода (такие как цикломатическая сложность и количество значащих строк кода) вычисляются с помощью модифицированной версии инструмента Lizard. Поля для дополнительных параметров извлекаются из отчетов анализаторов.

Кроме того, мы разработали скрипт, который объединяет и анализирует предупреждения, подготавливая данные к обработке приложениями статистического анализа. Этот скрипт конвертирует многотабличную базу данных модифицированной версии SCALe в линейный файл .csv, в котором записи разделены запятой — такой формат удобен для инструментов, осуществляющих классификацию. Наш скрипт также объединяет предупреждения, совпадающие по параметрам [правило, номер строки, файл]. Наконец, скрипт проводит дополнительный анализ и добавляет к записям такие сведения как число предупреждений на файл, число предупреждений на функцию и глубину вложенности файла в проекте, а также разбивает пути к файлам таким образом, чтобы частично совпадающие пути могли использоваться в качестве признаков классификации.

Наш метод разработки классификаторов может быть легко расширен для работы с другими стандартами и платформами, способными хранить данные проверок. Например, правила программирования CERT могут быть заменены другими схожими стандартами, а инструмент SCALe — другими платформами. Хранящиеся в SCALe ассоциации предупреждений с правилами могут быть заменены на ассоциации с другими правилами и нумерованными списками ошибок, например, Единый каталог программных уязвимостей (Common Weakness Enumeration ), Стандарт подтверждения безопасности приложений OWASP (OWASP Application Security Verification Standard Project ) и Стандарт разработки программного обеспечения на языке C MISRA. Аналогично данные оценки предупреждений из других платформ, работающих с несколькими анализаторами, могут быть конвертированы в другие форматы, поддерживаемые нашими классификаторами и инструментами их разработки.

Испытания нашего подхода с партнерами из Министерства обороны


Помимо 20 кодовых баз, проверенных CERT, мы используем данные трех подразделений Министерства обороны (об этом виде сотрудничества мы поговорим в отдельной статье), два из которых заявили о необходимости проверки защищенности их кода объемом более 100 MSLOC (миллионов значащих строк кода). Экстраполируя результаты, собранные на архивных данных предыдущих проверок CERT (при коэффициенте 3.31 предупреждения на 1,000 строк кода), мы ожидаем, что для кодовых баз обоих подразделений удастся идентифицировать примерно 662,000 предупреждений. Наша задача состоит в том, чтобы автоматически установить истинность/ложность помеченных дефектов с точностью 95%. В случае успеха наш метод (и созданные на его основе анализаторы) поможет значительно снизить трудозатраты по оценке результатов анализа и сортировке найденных дефектов по приоритету.

При использовании нашей системы автоматической классификации специалисты в упомянутых подразделениях могли бы обрабатывать предупреждения по следующей схеме:
  • e-TP (предполагаемые истинные ошибки) направляются непосредственно команде отладчиков.
  • I (промежуточные предупреждения) направляются для оценки команде аналитиков.
  • e-FP (предполагаемые ложные срабатывания) игнорируются.

Дальнейшая экстраполяция архивных данных CERT дает соотношение истинных/ложных предупреждений 1:3.74. Таким образом, с учетом нашей амбициозной задачи по обработке 90% предупреждений и корректном распределении их по группам e-TP и e-FP, ожидаются следующие результаты для 200 MSLOC: 126,000 e-TP, которые будут сразу направлены команде отладчиков, 470,000 e-FP, которые будут проигнорированы, и 66,000 I, которые будут оценены вручную. Эти цифры предполагают сокращение времени на ручную оценку предупреждений на 90%, при этом будут учитываться все предупреждения, так что уровень защищенности кода не будет снижаться (другими словами, 90% автоматически идентифицированных e-TP — или e-FP-предупреждений соответствуют сокращению времени на их оценку вручную на 90%). Степень достоверности промежуточных предупреждений поможет определить порядок их проверки. На практике те из них, которые имеют наименьший приоритет, могут вовсе игнорироваться.

На рисунке ниже показано, как наш метод поможет усовершенствовать процесс проверки приложений. Кодовые базы проверяются несколькими статическими анализаторами, и каждый из них выдает свой набор предупреждений. Стрелки под надписью „Today“ (»сегодня"), ведущие от блока «Alerts» («предупреждения») к диаграмме с красной рамкой, указывают на привычную стратегию обработки предупреждений, при которой каждое из предупреждений и соответствующий ему код должны проверяться вручную для установления его истинности или ложности. Данный процесс, как правило, отнимает слишком много времени, учитывая ограниченный бюджет проектов. Желтым кружком на данной диаграмме показано количество предупреждений, которые можно оценить за 12,939 часов работы (исходя из того, что на каждое предупреждение обычно уходит 5 минут, согласно результатам исследования [Hayward, 2008]), а красным эллипсом — оставшиеся 506,733 непроверенных предупреждения. С другой стороны, наша стратегия показана верхним рядом стрелок: 90% предупреждений будут автоматически и корректно распределены по группам e-TP или e-FP, в результате чего пользователю останется проверить лишь 66,000 промежуточных предупреждений. На это уйдет всего лишь 5,500 часов, что составляет меньше половины времени для первого сценария. Более того, наш метод гарантирует, что все предупреждения, требующие ручной проверки, обязательно ее пройдут.



Рис. 1: Задача нашего исследования состоит в том, чтобы значительно сократить время на ручную оценку непроверенных предупреждений и их количество. Изображение женщины и ноутбука («Woman And Laptop») взято из следующего источника: www.publicdomainpictures.net/view-image.php?image=47526&picture=woman-and-laptop.

Дальнейшая работа


В недавно опубликованном исследовании Automatically Learning Semantic Features for Defect Prediction было показано, что анализ семантических признаков программ может значительно улучшить точность обнаружения программных дефектов. В связи с этим мы планируем впоследствии добавить такой анализ в наши классификационные модели. Более того, мы рассчитываем применять семантические признаки из хранящихся в репозиториях отчетов при разработке классификаторов. Мы также собираемся использовать механизм автоматической оптимизации параметров для классификационных методов, что, согласно результатам недавнего исследования Automated Parameter Optimization of Classification Techniques for Defect Prediction Models , поможет значительно улучшить наши классификаторы.

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

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

Возможно также, что в будущем результаты нашего исследования будут объединены с решениями в области автоматического исправления кода, работа над которыми в настоящее время ведется в SEI. В этом случае наши модели будут применяться после автоматического рефакторинга кода, который поможет устранить лишь незначительное количество предупреждений о потенциальных ошибках. Наш метод может быть использован для сортировки по приоритету (при экспертном анализе) потенциальных полуавтоматических исправлений, корректность которых не гарантирована и которые требуют ручной оценки (например, специалист должен определить, будет ли некоторое автоматическое исправление корректным с учетом желаемого поведения кода). Все остальные предупреждения, для которых нет автоматических исправлений, могут быть классифицированы обычным способом с помощью нашего метода, как описано выше (т.е. с распределением по категориям e-TP, e-FP и I).

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

Мы будем рады вашим отзывам о данной работе — оставляйте их в разделе комментариев под текстом.

Дополнительные ресурсы


Читайте и комментируйте наши статьи и помогайте нам совершенствовать Стандарты программирования SEI CERT, разработка которых ведется на основе общедоступных вики-сайтов.

Также мы приглашаем вас посетить сайт Лаборатории анализа исходного кода CERT.

Далее приводятся источники цитат в данной статье:

[Heckman 2011] Heckman, Sarah, and Laurie Williams. A systematic literature review of actionable alert identification techniques for automated static code analysis. Information and Software Technology 53.4 (2011): 363-387.

[Heckman 2007] Heckman, Sarah. Adaptively ranking alerts generated from automated static analysis, Crossroads 14.1, 2007.

[Kong 2007] Kong, Deguang, et al. ISA: a source code static vulnerability detection system based on data fusion. Proceedings of the 2nd international conference on Scalable information systems. ICST, 2007.

[Kremenek 2004] Kremenek, Ted, et al. Correlation exploitation in error ranking. ACM SIGSOFT Software Engineering Notes. Том 29. N6. ACM, 2004.

[Meng 2008] N. Meng, Q. Wang, Q. Wu, H. Mei, An approach to merge results of multiple static analysis tools, Proceedings of the Eight International Conference on Quality Software, Oxford, UK, August 12-13, 2008.

[Plakosh, 2014] Plakosh, Daniel, Robert Seacord, Robert W. Stoddard, David Svoboda, and David Zubrow. Improving the Automated Detection and Analysis of Secure Coding Violations. (2014).

[Ruthruff 2008] Ruthruff, Joseph R., et al. Predicting accurate and actionable static analysis warnings: an experimental approach. Proceedings of the 30th international conference on Software engineering. ACM, 2008.

Translation Acknowledgements
  • This non-SEI-sanctioned translation of the blog post “Prioritizing Alerts from Static Analysis to Find and Fix Code Flaws” by Lori Flynn 2016 Carnegie Mellon University, was prepared by Andrey Karpov with special permission from the Software Engineering Institute.
  • Neither Carnegie Mellon University nor its Software Engineering Institute participated in the creation of this translation, and accordingly, they do not directly or indirectly endorse it. Accuracy and interpretation of this translation are the responsibility of Andrey Karpov.
  • ANY MATERIAL OF CARNEGIE MELLON UNIVERSITY AND/OR ITS SOFTWARE ENGINEERING INSTITUTE CONTAINED HEREIN IS FURNISHED ON AN «AS-IS» BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER EXPRESSED OR IMPLIED, AS TO ANY MATTER INCLUDING, BUT NOT LIMITED TO, WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY, OR RESULTS OBTAINED FROM USE OF THE MATERIAL. CARNEGIE MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT.

Tags:
Hubs:
+8
Comments 1
Comments Comments 1

Articles

Information

Website
pvs-studio.com
Registered
Founded
2008
Employees
31–50 employees