Скобцовы Моделирование и тестирование

−удаление одного входного вектора из случайно выбранной позиции. Применение данной операции позволяет уменьшать длину генерируемой тестовой последовательности в том случае, когда удалённый вектор не ухудшает тестовые свойства последовательности;

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

−случайная замена битов в тестовой последовательности.

Выбор между тремя операторами мутации также производится случайно с вероятностями Pмут1 и Pмут2 с распределением 0<Pмут1<Pмут2<1.

Поскольку целью является получение различных выходных сигналов в исправной и неисправной схемах, то фитнесс-функция при поиске следующего тестового набора в простейшем случае определяется числом изменений сигналов в схеме. Для этого используется относительно быстрое логическое моделирование исправных ЦС. Более точными являются фитнесс-функции, учитывающие число обнаруживаемых неисправностей на выходах ЦС. Но в этом случае необходимо использовать логическое моделирование неисправных ЦС, которое требует больших вычислительных ресурсов. Общая схема ГА в данном случае остаётся неизменной. Это позволяет добиваться неплохих результатов при тестировании ЦС.

8.4 Проблемно-ориентированные фитнесс-функции для генерации тестов

Поскольку целью генерации тестов является построение последовательности, на которой максимально отличаются значения сигналов в исправной и неисправной схемах, то качество тестовой последовательности (fitness-функция) оценивается как мера отличия значений сигналов в исправной и неисправной схемах. В программных системах генерации тестов используются различные fitness–функции,

361

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

табл.8.1.

Таблица 8.1

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

В системе CRIS [109] используется техника иерархического моделирования, сокращающая затраты памяти и позволяющая обрабатывать схемы большой размерности. Здесь применяется традиционный ГА, в котором популяции эволюционируют посредством операторов мутации и кроссинговера. В качестве особи берется последовательность входных наборов. Система CRIS основывается прежде

362

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

Система GATEST [110] ориентирована на последовательностные логические схемы и основана на двухуровневом ГА: на нижнем уровне с помощью ГА строятся входные наборы, а далее ГА применяется для генерации входных последовательностей на основе полученных наборов. Соответственно, на нижнем уровне особью является входной вектор, а на верхнем – входная последовательность. В ГА применяются различные виды операторов кроссинговера: одноточечный, двухточечный, однородный. Первый уровень в свою очередь подразделяется на три фазы. Таким образом, в целом, метод образуют четыре фазы, которые определяют соответствующие различные оценочные функции:

− в фазе 1 целью алгоритма является инициализация триггеров,

оценка выполняется с помощью только исправного моделирования;

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

363

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

исправной и неисправной схемах h3 = Fd + Fdt + E . Если найден набор,

FT NF

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

− в фазе 4 выполняется построение тестовых последовательностей на основе полученного множества входных наборов с помощью ГА,

В фазах 2-4 оценка особей выполняется с помощью моделирования неисправностей, что несколько замедляет работу GATEST. Система успешно применялась к последовательностным устройствам достаточно большой размерности и строила тесты в тех случаях, где детерминированный метод HITEC [111] не мог построить тесты. К недостаткам можно также отнести то, что разработчики вручную подбирают многие параметры ГА, включая размерность алфавита, размер популяции, уровень мутации.

Интересным является подход, представленный в работе [112] системой DIGATE. Он состоит из двух фаз:

−в фазе 1 происходит выбор неисправности и ее активизация (то есть, распространения до триггеров) с помощью ГА;

−в фазе 2 ищется последовательность, которая сделала бы целевую неисправность наблюдаемой на внешних выходах схемы. Поиск выполняется с помощью ГА путем эволюции различающей последовательности, полученной заранее. Техника, применяемая во второй

364

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

неисправностей, при этом оценочные функции представляют собой взвешенные суммы. Соответственно для фазы 1 и 2 оценочные функции имеют следующий вид:

h5 = 0.2D + 0.7(W + O) + 0.1(E f + Ts + Td ) , h6 = 0.8D + 0.1(W + O) + 0.1(E f + Ts + Td ) .

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

В другой системе [108] GATTO в качестве особей также выбраны входные последовательности. Основное внимание авторы алгоритма уделяют определению эффективной оценочной функции, как меры удаленности особи от искомого оптимума. Особи оцениваются с помощью моделирования неисправностей из соображений увеличения активности неисправности в схеме (чем больше количество линий, на которых значения в исправной и неисправной схемах различны, тем больше вероятность обнаружения неисправности). Поэтому оценочная функция определяется тремя эвристическими параметрами: взвешенное количество вентилей с разными значениями в исправном и неисправном устройствах; взвешенное количество триггеров с разными значениями в исправном и неисправном устройствах; длина последовательности-особи, параметр L используется для получения компактной тестовой последовательности. В качестве весов первых двух параметров используются соответствующие

365

последовательности, h(vi ) - сумма нормализованных первых двух параметров.

Вэтом подходе, также как и в предыдущем, отсутствует ручной подбор параметров для отдельной схемы.

Всистеме АСМИД-Е [36,37], разработанной авторами и подробно описанной в разделе 9, для повышения быстродействия алгоритма построения тестов в программную реализацию интегрированы две программы параллельного моделирования с неисправностями. Первая программа реализует параллельный по неисправностям метод моделирования и используется в фазе 1 для проверки активизации произвольной неисправности случайно генерированной последовательностью.

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

оценочной функции текущего вектора по формуле: h(v) = c1Nd (v) + c2Td (v) , где v – текущий входной набор. В качестве весов используются меры наблюдаемости схемы, вычисляемые на этапе предварительной обработки схемы.

После того как для входной последовательности, моделируемой в определённом разряде, достигнута эффективная длина или произведено моделирование на последнем наборе вычисляется оценочная функция всей последовательности:

366

где s - анализируемая последовательность; vi - вектор из рассматриваемой последовательности, i – позиция вектора в последовательности, f - заданная неисправность, LH – предварительно заданная константа в диапазоне 0 < LH <= 1, благодаря которой предпочтение отдаётся более коротким последовательностям.

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

Наиболее эффективным является метод построения тестов, объединяющий преимущества структурного детерминированного и генетического алгоритмов генерации. При этом этапы внесения влияния неисправности и активизации путей до внешних выходов схемы выполняется детерминированным методом с применением многозначных алфавитов, а этап доопределения - поиска значений входов схемы, обеспечивающих требования, полученные на первых этапах, выполняется с помощью ГА. Перспективным является также использование параллельных ГА, в которых используются несколько популяций решений, которые параллельно эволюционируют, в основном, независимо друг от друга. Но время от времени между ними производится обмен лучшими решениями, который может выполняться по различным схемам. Сама природа задачи построения тестов является иерархической, поэтому в ней целесообразно использовать иерархические ГА, где на каждом уровне иерархии применяется свой ГА.

8.5Реализация генетического алгоритма генерации тестов

Вданном разделе описывается метод построения тестовых последовательностей для последовательностных схем на основании

367

генетического алгоритма. При этом для получения псевдовходов и псевдовыходов схемы необходимо разорвать линии обратной связи, как это показано в разделе 7. Моделирование работы схемы производится по тактам синхронизации, во время которых значения с псевдовыходов схемы подаются на псевдовходы. Общий подход к тестированию заключается в следующем. Процесс генерации тестов содержит три фазы. Цель первой фазы - активизация неисправности, т.е. распространение рассогласования сигнала на псевдовыходы. На начальном этапе, когда можно быстро активизировать и проверить большое число неисправностей, здесь используется псевдослучайный метод генерации тестовых последовательностей (раздел 6.1). На втором этапе для повышения эффективности процесса активизации неисправностей используется генетический алгоритм. После того, как в первой фазе активизирована какая-либо неисправность, необходимо улучшить полученную активизирующую последовательность так, чтобы она стала проверяющей. Для этого во второй фазе также используется генетический алгоритм. Фаза 2 является ядром всего алгоритма. После выполнения второй фазы в случае успешного результата – построения тестовой последовательности, необходимо произвести моделирование с неисправностями на данной последовательности (фаза три), чтобы обнаружить все неисправности, которые она проверяет. Укрупненный алгоритм в виде псевдокода представлен на рис.8.11.

Здесь переменная режим показывает, каким способом ведётся активизация неисправности: значение 0 соответствует псевдослучайному метод, 1 - генетическому алгоритму. Переменная метод показывает цель, для которой используется генетический алгоритм. При этом значение 0 соответствует активизации неисправности, а 1 - построению теста для активизированной неисправности.

368

генерация_тестов(схема)

{

режим=0; метод=0;

while(не достигнута заданная полнота)

{

счётчик++;

if( счетчик>МАХ_счётчик) break; // иначе – конец алгоритма

}

метод=1; // Фаза 2

последовательность=ГА_генерация_тестовой_ последовательности(цель); if( последовательность != НЕТ_ПОСЛЕДОВАТЕЛЬНОСТИ ) неисправное_моделирование( последовательность ); // Фаза 3

}// конец while – достигнута заданная полнота

}// конец алгоритма

Рис.8.11 Генетический алгоритм генерации тестовых наборов

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

369

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

где s – анализируемая последовательность; vi - вектор из рассматриваемой последовательности, i – позиция вектора в последовательности, f - заданная неисправность, L – предварительно заданная константа в диапазоне 0 < L ≤ 1, благодаря которой предпочтение отдаётся более коротким последовательностям. Здесь оценочная функция одного вектора из последовательности имеет вид:

h(v, f ) = f1 (v, f ) + c1 f2 (v, f ) ,

где с1 константа нормирования, равная отношению числа вентилей схемы к числу триггеров; f1(v,f) и f2(v,f) эвристические функции, определяющие:

-f1(v,f) взвешенное число вентилей с различными значениями сигналов в исправной и неисправной схемах;

-f2(v,f) взвешенное число триггеров с различными значениями сигналов в исправной и неисправной схемах.

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

370