Анализ программы - Program analysis

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

Анализ программы может выполняться без выполнения программы ( статический анализ программы ), во время выполнения ( динамический анализ программы ) или в сочетании того и другого.

Статический анализ программы

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

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

Неправильная оптимизация крайне нежелательна. Итак, в контексте оптимизации программы есть две основные стратегии обработки неразрешимого с вычислительной точки зрения анализа:

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

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

Поток управления

Целью анализа потока управления является получение информации о том, какие функции могут быть вызваны в различных точках во время выполнения программы. Собранная информация представлена графом потока управления (CFG), где узлы представляют собой инструкции программы, а края представляют собой поток управления. Идентифицируя блоки кода и циклы, CFG становится отправной точкой для оптимизаций, выполненных компилятором.

Анализ потока данных

Анализ потока данных - это метод, предназначенный для сбора информации о значениях в каждой точке программы и о том, как они меняются с течением времени. Этот метод часто используется компиляторами для оптимизации кода. Одним из наиболее известных примеров анализа потока данных является проверка на зараженность, которая заключается в рассмотрении всех переменных, содержащих данные, предоставленные пользователем, которые считаются «испорченными», то есть небезопасными, и предотвращении использования этих переменных до тех пор, пока они не будут очищены. Этот метод часто используется для предотвращения атак с использованием SQL-инъекций . Проверка на заражение может выполняться статически или динамически.

Абстрактная интерпретация

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

Системы типов

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

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

Информация о статическом типе ( предполагаемая или явно предоставленная аннотациями типов в исходном коде) также может использоваться для оптимизации, например, для замены упакованных массивов на неупакованные массивы.

Системы эффектов

Системы эффектов - это формальные системы, предназначенные для представления эффектов, которые может иметь выполнение функции или метода. Эффект кодифицирует то, что делается, и то, что это делается - обычно это называется типом эффекта и областью соответственно.

Проверка модели

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

Динамический анализ программы

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

Тестирование

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

Мониторинг

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

Программа нарезки

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

Смотрите также

использованная литература

дальнейшее чтение

  • Агравал, Хиралал; Хорган, Джозеф Р. Динамическая нарезка программ (PDF) .
  • Чунлей, Ван; Банда, Чжао; Ики, Дай (2009). «Эффективный подход к анализу безопасности потока управления для двоичных исполняемых файлов». 2009 2-я Международная конференция IEEE по компьютерным наукам и информационным технологиям . С. 272–276. DOI : 10.1109 / ICCSIT.2009.5234950 . ISBN 978-1-4244-4519-6.
  • Нильсон, Флемминг; Нильсон, Ханне Риис; Ханкин, Крис (2005). Принципы анализа программ . Springer Science + Business Media .

внешние ссылки