Теория и практика защиты программ
Если все входы рассмотрены, то
Б2. Отмечаются все входы и выходы управляющего графа и фиксируется первый вход.
Б3. Если все входы рассмотрены, то выполняется переход к шагу Б9, иначе выполняется переход к шагу Б4.
Б4. Строится очередной путь, причем первой вершиной пути назначается зафиксированный вход.
Б5. Если текущая вершина пути не выходная, то необходимо перейти к шагу Б6, в противном случае - к шагу Б4 (путь построен).
Б6. Если у последней вершины пути выходят необработанные дуги, то выполняется переход к шагу Б7, в противном случае - к шагу Б8.
Б7. В текущий путь включается необработанная дуга с началом в последней (текущей) вершине пути. Если таких дуг несколько, то выполняется переход к шагу Б5.
Б8. Строится кратчайший путь из последней (текущей) вершины до ближайшей вершины допустимого множества, в которое включаются выходные вершины графа, если в текущем пути уже есть хотя бы одна дуга, а также все вершины, из которых выходят некоторые дуги, если ни одна из вершин не пройдена дважды. Если такой кратчайший путь существует, то он присоединяется к текущему пути, после чего делается переход к шагу Б5. В противном случае фиксируется следующий вход, если это возможно, и делается переход к шагу Б3.
Б9. Участкам пути, входящим в макровершины, присваиваются весовые коэффициенты в соответствии с весами макровершин. Для каждого полного пути определяется весовой коэффициент пути, равный сумме весов входящих в него участков.
Б10. Вычисляется среднее значение весовых коэффициентов путей тестирования, после чего составляется множество критических путей, весовые коэффициенты которых выше среднего. Алгоритм заканчивается.
Необходимо сделать некоторые пояснения к алгоритму Б:
· при построении кратчайшего пути до ближайшей вершины из допустимого множества используется модификация известного алгоритма Дейкстры (достаточно сравнивать вершину с минимальной временной пометкой на принадлежность допустимому множеству) [Кн];
