Лекция
В информатике анализ программного обеспечения — это процесс анализа поведения компьютерных программ с точки зрения таких свойств, как корректность, надежность, безопасность и жизнеспособность. Анализ программ фокусируется на двух основных областях: оптимизации программ и корректности программ . Первая направлена на повышение производительности программы при одновременном снижении потребления ресурсов, а вторая — на обеспечение того, чтобы программа выполняла свои функции.
Аудит программного кода — это комплексный анализ исходного кода программного проекта с целью выявления ошибок, нарушений безопасности или правил программирования. Он является неотъемлемой частью парадигмы защитного программирования , направленной на снижение количества ошибок до выпуска программного обеспечения.
При аудите программного обеспечения каждый критический компонент должен проверяться отдельно и вместе со всей программой. Рекомендуется сначала искать уязвимости с высокой степенью риска и переходить к уязвимостям с низкой степенью риска. Уязвимости между высокой и низкой степенью риска обычно существуют в зависимости от ситуации и того, как используется рассматриваемый исходный код. Тестирование на проникновение в приложения пытается выявить уязвимости в программном обеспечении, запуская как можно больше известных методов атак на вероятные точки доступа в попытке вывести приложение из строя. Это распространенный метод аудита, который может использоваться для выявления наличия каких-либо конкретных уязвимостей, но не для определения их местонахождения в исходном коде. Некоторые утверждают, что методы аудита в конце цикла, как правило, перегружают разработчиков, в конечном итоге оставляя команде длинный список известных проблем, но не приводя к реальному улучшению; в таких случаях в качестве альтернативы рекомендуется подход с использованием встроенного аудита. Примером проактивного подхода является бесплатная служба аудита кода, предлагаемая GooApps, целью которой является выявление и устранение уязвимостей на ранних этапах процесса разработки для обеспечения успеха мобильных приложений
Анализ программы может быть выполнен без ее выполнения ( статический анализ программы ), во время выполнения ( динамический анализ программы ) или в комбинации этих двух методов.
В информатике статический анализ программ (также известный как статический анализ или статическое моделирование ) — это анализ компьютерных программ, выполняемый без их выполнения, в отличие от динамического анализа программ , который выполняется над программами во время их выполнения в интегрированной среде.
Этот термин обычно применяется к анализу, выполняемому автоматизированным инструментом, а человеческий анализ обычно называется «пониманием программы», «пониманием программы» или «обзором кода ». В последнем случае также используются инспекция и сквозной анализ программного обеспечения . В большинстве случаев анализ выполняется на определенной версии исходного кода программы , а в других случаях — на определенной форме ее объектного кода .
Стати́ческий ана́лиз ко́да (англ. static code analysis) — анализ исходного кода программного обеспечения, производимый без реального выполнения исследуемых программ (в отличие от динамического анализа). В большинстве случаев анализ производится над исходным кодом, хотя иногда анализу подвергается объектный код, например P-код или код на MSIL. Термин обычно применяют к анализу, производимому специальным программным обеспечением (ПО), тогда как ручной анализ называют «program understanding» или «program comprehension» (пониманием программы).
В зависимости от используемого инструмента глубина анализа может варьироваться от определения поведения отдельных операторов до анализа всего имеющегося кода. Способы использования полученной в ходе анализа информации также различны — от выявления мест, возможно содержащих ошибки (утилиты типа Lint), до формальных методов, позволяющих математически доказать какие-либо свойства программы (например, соответствие поведения спецификации).
В некоторых источниках программные метрики и обратное проектирование рассматриваются как формы статического анализа. Получение метрик (англ. software quality objectives) и статический анализ часто совмещаются, особенно при создании встраиваемых систем .
Современные средства анализа, такие как Coverity, SonarQube, PVS-Studio, Clang Static Analyzer и Infer от Meta, используют методы анализа потока данных, контроля потока управления, а также абстрактной интерпретации для выявления ошибок, неочевидных при компиляции. Многие инструменты интегрируются в CI/CD-конвейеры и автоматизированные процессы разработки программного обеспечения для раннего выявления уязвимостей и дефектов.
Статический анализ играет важную роль в обеспечении безопасной разработки, соответствующей таким стандартам, как OWASP и MISRA C (в автомобильной индустрии), и широко применяется при разработке критически важных систем.
Динамический анализ программы — это процесс анализа программного обеспечения , включающий выполнение программы , в отличие от статического анализа программы , который не выполняет ее.
Анализ может быть сосредоточен на различных аспектах программного обеспечения, включая, помимо прочего: поведение , тестовое покрытие , производительность и безопасность .
Для обеспечения эффективности целевая программа должна выполняться с достаточным количеством тестовых входных данных , чтобы охватить весь диапазон возможных входных и выходных данных. Для выявления областей , где тестирование неэффективно, используются такие инструменты , как покрытие кода , и мутационное тестирование .
динамический анализ кода (англ. Dynamic program analysis) — анализ программного обеспечения, производящийся при помощи выполнения программ на реальном или виртуальном процессоре (в отличие от статического анализа). Утилиты динамического анализа могут требовать загрузки специальных библиотек, перекомпиляцию программного кода. Некоторые утилиты могут инструментировать исполняемый код в процессе исполнения или перед ним. Для большей эффективности динамического анализа требуется подача тестируемой программе достаточного количества входных данных, чтобы получить более полное покрытие кода. Также следует позаботиться о минимизации воздействия инструментирования на исполнение тестируемой программы (включая временные характеристики).
Уровень сложности анализа, выполняемого инструментами, варьируется от тех, которые рассматривают только поведение отдельных операторов и объявлений , до тех, которые включают в свой анализ полный исходный код программы. Использование информации, полученной в результате анализа, варьируется от выявления возможных ошибок кодирования (например, инструмент lint ) до формальных методов , математически доказывающих свойства данной программы (например, соответствие ее поведения спецификации).
Метрики программного обеспечения и обратная разработка могут быть описаны как формы статического анализа. Выведение метрик программного обеспечения и статический анализ все чаще применяются совместно, особенно при создании встраиваемых систем, путем определения так называемых целей качества программного обеспечения .
Статический анализ все чаще используется в коммерческих целях для проверки свойств программного обеспечения, используемого в критически важных для безопасности компьютерных системах, а также для обнаружения потенциально уязвимого кода. Например, следующие отрасли промышленности используют статический анализ кода как средство повышения качества все более сложного и усовершенствованного программного обеспечения:
Исследование, проведенное компанией VDC Research в 2012 году, показало, что 28,7% опрошенных инженеров встраиваемого программного обеспечения используют инструменты статического анализа, а 39,7% планируют начать использовать их в течение двух лет. Исследование, проведенное в 2010 году, показало, что 60% опрошенных разработчиков, участвующих в европейских исследовательских проектах, использовали как минимум базовые встроенные статические анализаторы своих IDE. Однако лишь около 10% использовали дополнительные (возможно, более продвинутые) инструменты анализа.
В индустрии безопасности приложений также используется термин «статическое тестирование безопасности приложений» (SAST). SAST является важной частью жизненного цикла разработки безопасности (SDL), например, SDL, определенного Microsoft , и распространенной практикой в компаниях-разработчиках программного обеспечения.
Группа управления объектами (OMG ) опубликовала исследование, посвященное типам анализа программного обеспечения, необходимым для измерения и оценки его качества . В документе «Как создать устойчивые, безопасные, эффективные и легкоизменяемые ИТ-системы в соответствии с рекомендациями CISQ» описываются три уровня анализа программного обеспечения.
Уровень единицы
Анализ, который выполняется в рамках определенной программы или подпрограммы, без привязки к контексту этой программы.
Уровень технологии
Анализ, который учитывает взаимодействие между отдельными программами, чтобы получить более целостное и семантическое представление о программе в целом с целью выявления проблем и избежания очевидных ложных срабатываний.
Системный уровень
Анализ, учитывающий взаимодействие между юнит-программами, но не ограничивающийся одной конкретной технологией или языком программирования.
Можно определить еще один уровень анализа программного обеспечения.
Уровень миссии/бизнеса
Анализ, учитывающий термины, правила и процессы уровня бизнеса/миссии, реализованные в программной системе для ее функционирования в рамках деятельности уровня предприятия или уровня программы/миссии. Эти элементы реализуются без ограничения одной конкретной технологией или языком программирования и во многих случаях распределены по нескольким языкам, но статически извлекаются и анализируются для понимания системы и обеспечения выполнения миссии.
Формальные методы — это термин, применяемый к анализу программного обеспечения (и компьютерного оборудования ), результаты которого получаются исключительно с помощью строгих математических методов. Используемые математические методы включают денотационную семантику , аксиоматическую семантику , операционную семантику и абстрактную интерпретацию .
Путем прямого сведения к проблеме остановки можно доказать, что (для любого Тьюринг-полного языка) нахождение всех возможных ошибок времени выполнения в произвольной программе (или, в более общем смысле, любого нарушения спецификации на конечный результат программы) неразрешимо : не существует механического метода, который всегда может дать точный ответ на вопрос о том, может ли произвольная программа демонстрировать ошибки времени выполнения. Этот результат восходит к работам Черча , Геделя и Тьюринга 1930-х годов (см.: Проблема остановки и теорема Райса ). Как и во многих неразрешимых вопросах, все еще можно попытаться дать полезные приближенные решения.
Некоторые методы реализации формального статического анализа включают:
Статический анализ, управляемый данными, использует обширные кодовые базы для выведения правил кодирования и повышения точности анализа. Например, можно использовать все пакеты Java с открытым исходным кодом, доступные на GitHub, для изучения эффективных стратегий анализа. Вывод правил может использовать методы машинного обучения. Также возможно обучение на основе большого количества прошлых исправлений и предупреждений.
Статические анализаторы выдают предупреждения. Для некоторых типов предупреждений можно разработать и реализовать автоматизированные методы исправления. Например, Логоззо и Болл предложили автоматизированные методы исправления для C# cccheck .
Функциональное тестирование включает в себя относительно распространенные методы программирования , такие как модульное тестирование , интеграционное тестирование и системное тестирование .
Вычисление покрытия кода тестом позволяет выявить код, который не тестируется, не охвачен тестом.
Хотя этот анализ выявляет непротестированный код, он не определяет, является ли протестированный код адекватно протестированным. Код может быть выполнен, даже если тесты фактически не подтверждают корректность его работы.
Динамическое тестирование подразумевает выполнение программы на наборе тестовых случаев.
Фаззинг — это метод тестирования, включающий запуск программы с широким спектром входных данных; часто эти входные данные генерируются случайным образом (по крайней мере, частично). Фаззинговые тесты, основанные на методе «серого ящика», используют покрытие кода для управления генерацией входных данных.
Динамическое символьное выполнение (также известное как DSE или concolic выполнение) включает в себя выполнение тестовой программы на конкретных входных данных, сбор ограничений пути, связанных с выполнением, и использование решателя ограничений (обычно решателя SMT ) для генерации новых входных данных, которые заставят программу выбрать другой путь потока управления, тем самым увеличивая покрытие кода тестового набора. DSE можно считать разновидностью фаззинга (фаззинг «белого ящика»).
Динамический анализ потока данных отслеживает поток информации от источников к приемникам . К формам динамического анализа потока данных относятся динамический анализ помеченных данных и даже динамическое символьное исполнение .
Daikon — это реализация динамического обнаружения инвариантов. Daikon запускает программу, наблюдает за значениями, которые она вычисляет, а затем сообщает свойства, которые были верны в ходе наблюдаемых запусков и, следовательно, вероятно, верны во всех запусках.
Динамический анализ может использоваться для обнаружения проблем безопасности.
Для заданного подмножества поведения программы срез программы заключается в приведении программы к минимальной форме, которая по-прежнему обеспечивает выбранное поведение. Сокращенная программа называется «срезом» и представляет собой точное представление исходной программы в области определения заданного подмножества поведения. Как правило, нахождение среза является неразрешимой задачей, но, задавая целевое подмножество поведения значениями набора переменных, можно получить приблизительные срезы с помощью алгоритма потока данных. Эти срезы обычно используются разработчиками при отладке для определения источника ошибок.
Большинство инструментов анализа производительности используют методы динамического анализа программ.
Большая часть динамического анализа подразумевает инструментирование или преобразование.
Поскольку инструментирование может влиять на производительность выполнения, интерпретация результатов теста должна учитывать это, чтобы избежать ошибочного определения проблемы производительности.
DynInst — это библиотека для внесения исправлений в код во время выполнения, полезная для разработки зондов динамического анализа программ и их применения к скомпилированным исполняемым файлам. Dyninst, как правило, не требует исходного кода или перекомпиляции, однако исполняемые файлы без отладки и с отладочными символами проще инструментировать.
Iroh.js — это библиотека анализа кода JavaScript во время выполнения . Она отслеживает путь выполнения кода, предоставляет прослушиватели для отслеживания определенных шаблонов выполняемого кода и позволяет перехватывать и манипулировать поведением выполнения программы.
В информатике анализ завершения — это анализ программы , который пытается определить, останавливается ли выполнение данной программы при каждом входном значении. Это означает, что программа вычисляет полную функцию.
Она тесно связана с проблемой остановки , которая заключается в определении того, останавливается ли данная программа при заданном входном сигнале, и неразрешима ли она . Анализ остановки еще сложнее, чем проблема остановки: анализ остановки в модели машин Тьюринга как модели программ, реализующих вычислимые функции, имел бы целью определить, является ли данная машина Тьюринга полной машиной Тьюринга , и эта проблема находится на уровне 
арифметической иерархии и, таким образом, является более сложной, чем проблема остановки.
Теперь, поскольку вопрос о том, является ли вычислимая функция полной, не является полуразрешимым , каждый анализатор завершения работы (т.е. утвердительный ответ никогда не дается для незавершающейся программы) является неполным , т.е. должен потерпеть неудачу в определении завершения для бесконечного числа завершающихся программ, либо работая вечно, либо останавливаясь с неопределенным ответом.
Доказательство завершения — это тип математического доказательства , который играет решающую роль в формальной проверке, поскольку от завершения зависит общая правильность алгоритма .
Простой и общий метод построения доказательств завершения алгоритма заключается в сопоставлении меры с каждым шагом алгоритма. Мера берется из области определения обоснованного отношения , например, из порядковых чисел . Если мера «убывает» в соответствии с отношением на каждом возможном шаге алгоритма, алгоритм должен завершиться, поскольку бесконечных нисходящих цепочек относительно обоснованного отношения не существует.
Некоторые типы анализа прекращения могут автоматически генерировать или подразумевать наличие доказательства прекращения.
Примером конструкции языка программирования , которая может быть завершена, а может и нет, является цикл , поскольку он может выполняться многократно. Циклы, реализованные с использованием переменной-счетчика , как правило, используемые в алгоритмах обработки данных , обычно завершаются, что демонстрируется в примере псевдокода ниже:
i := 0
цикл , пока i = SIZE_OF_DATA
process_data(data[i])) // обработать фрагмент данных в позиции i
i := i + 1 // перейти к следующему фрагменту данных для обработки
Если значение SIZE_OF_DATA неотрицательное, фиксированное и конечное, цикл в конечном итоге завершится, если предположить, что process_data также завершится.
Визуальный анализ некоторых циклов позволяет показать, что они всегда завершаются или никогда не завершаются. Например, следующий цикл теоретически никогда не останавливается. Однако при выполнении на физическом компьютере он может остановиться из-за арифметического переполнения , что может привести либо к исключению , либо к переходу счетчика к отрицательному значению и выполнению условия цикла.
i := 1
loop , while i = 0
i := i + 1
Анализ завершения может также попытаться определить поведение завершения программы в зависимости от неизвестных входных данных. Следующий пример иллюстрирует эту проблему.
i := 1
loop , пока i = UNKNOWN
i := i + 1
Здесь условие цикла определяется с помощью некоторого значения UNKNOWN, причем само значение UNKNOWN неизвестно (например, оно определяется вводом пользователя при выполнении программы). Анализ завершения цикла должен учитывать все возможные значения UNKNOWN и установить, что в случае UNKNOWN = 0 (как в исходном примере) завершение цикла не может быть отображено.
Однако не существует общей процедуры определения, остановится ли выражение, включающее циклические инструкции, даже если проверка выполняется человеком. Теоретическая причина этого заключается в неразрешимости проблемы остановки: не может существовать алгоритма, который бы определял, остановится ли любая заданная программа после конечного числа вычислительных шагов.
На практике невозможно показать завершение (или незавершение), поскольку каждый алгоритм использует конечный набор методов, способных извлечь необходимую информацию из заданной программы. Один метод может анализировать изменение переменных в зависимости от некоторого условия цикла (возможно, демонстрируя завершение этого цикла), другие методы могут пытаться преобразовать вычисления программы в некую математическую конструкцию и работать с ней, возможно, получая информацию о поведении завершения из некоторых свойств этой математической модели. Но поскольку каждый метод способен «видеть» только некоторые конкретные причины (не)завершения, даже сочетание таких методов не позволяет охватить все возможные причины (не)завершения. [ требуется ссылка ]
Рекурсивные функции и циклы эквивалентны по выражению; любое выражение, включающее циклы, можно записать с использованием рекурсии, и наоборот. Таким образом, завершение рекурсивных выражений также в общем случае неразрешимо. Можно показать, что большинство рекурсивных выражений, встречающихся в широком употреблении (т.е. не являющихся патологическими ), завершаются различными способами, обычно в зависимости от определения самого выражения. Например, аргумент функции в рекурсивном выражении для функции факториала ниже всегда будет уменьшаться на 1; по свойству полного порядка натуральных чисел аргумент в конечном итоге достигнет 1, и рекурсия завершится.
function факториал (аргумент как натуральное число)
, if аргумент = 0 OR аргумент = 1,
возвращает 1,
else
return аргумент * факториал(аргумент - 1)
Одним из подходов к проверке завершения в языках программирования с зависимой типизацией являются размерные типы. Основная идея заключается в аннотации размера типов, по которым можно выполнять рекурсию, и разрешении рекурсивных вызовов только для аргументов меньшего размера. Размерные типы реализованы в Agda как синтаксическое расширение.
Существует несколько исследовательских групп, работающих над новыми методами, которые могут показать (не)завершение работы. Многие исследователи включают эти методы в программы которые пытаются автоматически анализировать поведение завершения работы (то есть без участия человека). Текущий аспект исследований — это возможность использования существующих методов для анализа поведения завершения работы программ, написанных на языках программирования «реального мира». Для декларативных языков, таких как Haskell , Mercury и Prolog , существует множество результатов (в основном из-за сильной математической базы этих языков). Исследовательское сообщество также работает над новыми методами анализа поведения завершения работы программ, написанных на императивных языках, таких как C и Java.
def f ( n ):
while n > 1 :
if n % 2 == 0 :
n = n / 2
else :
n = 3 * n + 1
По состоянию на 2025 год все еще неизвестно, завершается ли эта программа на Python для каждого входного значения;
Комментарии
Оставить комментарий
Разработка программного обеспечения и информационных систем
Термины: Разработка программного обеспечения и информационных систем