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


         

Если все входы рассмотрены, то


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

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

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

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

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

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

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

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

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

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

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


Содержание  Назад  Вперед