Информационная безопасность

Методы динамического и статистического анализа


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

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

Статистическое построение графа потока управления строит граф потока управления на основании информации о порядке следования базовых блоков на одном наборе или на множестве наборов входных данных.

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

Динамическое выделение мёртвого кода позволяет выявить инструкции программы, которые выполнялись при данном запуске программы, но не оказали никакого влияния на результат работы программы. Если анализируется совокупность запусков программы на множестве наборов входных данных, можно говорить о статистическом выделении мёртвого кода.

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

Заметим, что о точности динамических методов анализа можно говорить, только если известно полное тестовое покрытие программы (построение полного тестового покрытия - алгоритмически неразрешимая задача). В противном случае статистическое выявление свойств программы не позволяет нам утверждать, что данное свойство справедливо на всех допустимых наборах входных данных. Например, условие if (leap_year(current_data)) всегда будет равно значению "истина", если текущий год високосный, и значению "ложь" в противном случае, однако удаление этого ператора из программы приведёт к её неправильной работе.


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

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


Содержание раздела