Методы контроля, реализующие раскраску команд

Суть данной группы методов заключается в следующем. Каждой ко­манде ГСА ставится в соответствие признак, называемый цветом команды, который для разных методов реализуется по-разному. ГСА преобразуется так, чтобы соблюдалась определенная последовательность чередования цветов, которая задается с помощью дополнительного элемента, обычно – счетчика цветов. Этот процесс называется раскраской программы. Преоб­разование ГСА достигается за счет введения диагностических вершин (D). Диагностическая вершина – это команда, обладающая требуемым цветом и не влияющая на результат выполнения программы. Возможность выбора команды в качестве диагностической вершины зависит от метода кон­троля.

Метод контроля, использующий раскраску без учета     структуры команд

Данный метод изложен в работе [3]. Модели дефекта выбраны сле­дующие:

– переход команды в команду K_i/K_j, т.е. соответствующий дефект механизма хранения в нашей модели;

– пропадание команды, определяемое нулями по всем разрядам ко­манды, т.е. дефект механизма дешифрации K_i/0 в нашей модели;

– искажение команды, определяемое как одиночная неисправность в двоичном представлении команды, т.е. дефект механизма хранения.

Каждая программа представляется, как указывалось выше, граф-схе­мой алгоритма.

На первом этапе производится раскраска ГСА. Выбирается m – ко­личество цветов – в зависимости от требуемой вероятности обнаружения дефектов перехода. Каждой команде присваивается цвет так, чтобы по лю­бому пути ГСА соблюдалась правильная последовательность цветов от 0 до m–1. Если последовательность нарушается, то в ГСА вводятся диагно­стические вершины. В данном методе в качестве диагностической вер­шины может выступать любая команда, не нарушающая выполнения про­граммы (типа NOP – пустой команды, СМР – команды сравнения и т.д.).

Пример 4.4. На рис. 4.31 представлена раскрашенная ГСА рис. 4.30 при m = 5, цвета записаны сверху у обозначения команды. Буквой D обо­значены введенные диагностические вершины.

Рис. 4.31. Пример раскрашенной ГСА

Преобразованная программа приведена ниже:

CLR AX M1: MOV CX,2

MOV BX,1 M5: CMP C,4

CMP C,2 ADD C,4

JNE M1 M3: CMP C,10

CMP C,5 JNE M6

JNE M3 CMP C,2

CLR DX ; D4 CMP C,4

NOP ; D0 JMP M5

MOV BX,1 M4: CMP AX,1 ; D1

CMP C,2 M6: CMP C,2

CLR CX ; D3 RET

CMP C,4

JNE M2

INC BX

JMP M4

DEC BX

JMP M4

Команды, соответствующие введенным диагностическим вершинам, помечены комментарием. В качестве диагностических вершин введены команды NOP, CMP AX,1 INC DX, CLR CX, не влияющие на ход выпол­нения программы. На втором этапе в каждую команду дополнительно вво­дится еще один избыточный разряд, дополняющий ее двоичное представ­ление до четности.

Пример 4.5. Ниже представлена двоичная запись команд раскра­шенной ГСА, представленной на рис 4.30, с избыточными разрядами, включающими цвет от 0 до 4 и дополнение до четности: