Теория и практика защиты программ


Анализ характеристик программных модулей с помощью управляющего графа


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

Количественная оценка сложности программы при помощи управляющего графа вычисляется [Лип0] как сумма V=e-n+2p, где e

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

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

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

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




- Начало -  - Назад -  - Вперед -