Графовые модели программ

Взаимосвязь статического и динамического анализа программ

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

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

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

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

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

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

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

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

Управляющим графом программы (УГП) называется ориентированный граф G(N,E), где N – множество вершин графа, а E – множество дуг, вершины которого соответствуют последовательным (линейным) участкам программы, а дуги – возможным передачам управления между ними. Вершинам УГП чаще всего соответствуют либо минимальные (отдельные операторы), либо максимальные (базовые блоки) линейные участки программы. Поскольку УГП обладает свойствами графа потока, его вершины часто называют узлами.

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

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