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


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


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

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

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

 

Алгоритм А

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

А2. В графе программы ищется структурированная конструкция. Если такой нет, то выполняется переход к шагу А4.

А3. В дереве образуется вершина структурированной конструкции. Эта конструкция сворачивается в вершину, тип которой указывается. Выполняется переход к шагу А2.

А4. Если в графе осталась только одна вершина, то работа алгоритма заканчивается.

А5. В графе выделяется неструктурируемая конструкция и в структурном дереве образуется вершина соответствующего  типа. Конструкция в графе сворачивается, после чего выполняется переход к шагу А2.

 

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

S(V(i)-1), где NS - множество вершин неструктурируемого типа в структурном дереве; V(i) - топологическая сложность конструкции, соответствующей i-й вершине дерева.

Вычисление V(i) производится на шаге А5 алгоритма по формуле V(i)=e(i)-n(i)+2, где e(i) - количество дуг, а n(i) - количество вершин рассматриваемой конструкции.

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




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