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

       

Построение критических путей, подлежащих обязательному тестированию


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

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

Алгоритм Б

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


Б2. Отмечаются все входы и выходы управляющего графа и фиксируется первый вход.

Б3.  Если все входы рассмотрены, то выполняется переход к шагу Б9, иначе выполняется переход к шагу Б4.

Б4. Строится очередной путь, причем первой вершиной пути  назначается зафиксированный вход.

Б5. Если текущая вершина пути не выходная, то необходимо перейти к шагу Б6, в противном случае - к шагу Б4 (путь построен).

Б6. Если у последней вершины пути выходят необработанные дуги, то выполняется переход к шагу Б7, в противном случае - к шагу Б8.

Б7. В текущий путь включается необработанная дуга с началом в последней (текущей) вершине пути. Если таких дуг несколько, то выполняется переход к шагу Б5.

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

Б9. Участкам пути, входящим в макровершины, присваиваются весовые коэффициенты в соответствии с весами макровершин. Для каждого полного пути определяется весовой коэффициент пути, равный сумме весов входящих в него участков.



Б10. Вычисляется среднее значение весовых коэффициентов путей тестирования, после чего составляется множество критических путей, весовые коэффициенты которых выше среднего. Алгоритм заканчивается.

Необходимо сделать некоторые пояснения к алгоритму Б:

·          при построении кратчайшего пути до ближайшей вершины из допустимого множества используется модификация известного алгоритма Дейкстры (достаточно сравнивать вершину с минимальной временной пометкой на принадлежность допустимому множеству) [Кн];



·          при выполнении шага Б8 ограничения на допустимое множество накладываются в соответствии с двумя соображениями: во-первых, желательно получить не слишком длинные пути, так как весьма вероятно, что они окажутся нереализуемыми, а во-вторых, желательно получить как можно больше путей, однако при этом необходимо контролировать выполнение условия, чтобы число путей не превысило топологическую сложность рассматриваемого участка программы (топологическая сложность определяется при построении структурного дерева программы по алгоритму Б);

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

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

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

www.kiev-security.org.ua

BEST rus DOC FOR FULL SECURITY


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