BC/NW 2011; №1 (18):2.5

ОПТИМИЗАЦИЯ И ОБФУСКАЦИЯ КОМБИНАЦИОННЫХ СХЕМ ДЛЯ СБМК И ПЛИС

Н.А. Кононов, В.А. Беспалов

Московский энергетический институт (Технический университет)

В настоящее время ПЛИС (программируемые логические интегральные схемы) и СБМК (структурированные базовые матричные кристаллы) являются широко используемыми решениями для проектирования и производства СБИС различного назначения [1, 2]. Ранее был разработан метод оптимизации УЛМ (универсального логического модуля) для ПЛИС и СБМК [3]. С помощью проведенных численных экспериментов было показано, что оптимальное количество входов LUT (Look-Up Table, или поисковой таблицы), являющейся основной частью УЛМ, равно четырем.

В настоящей работе предлагается алгоритм вычисления ПЛИ (простых логических импликаций) в комбинационной схеме, построенной на основе LUT. Полученные таким образом ПЛИ могут быть использованы для уточнения временного анализа (путем отсеивания ложных путей распространения сигнала), анализа помехоустойчивости схемы, и т.д. [4].

Как известно, n-входовая LUT может реализовать произвольную Булеву функцию n переменных (в нашем случае n=4). В предлагаемом алгоритме Булева сеть (т.е. комбинационная схема) представлена как сеть из ROBDD (Reduced Ordered Binary Decision Diagram, т.е. минимизированных диаграмм двоичных решений). Сеть ROBDD экстрагирована из исходной транзисторной схемы (одна ROBDD соответствует одному произвольному логическому вентилю). В этом случае мы можем использовать ROBDD для генерации ПЛИ непосредственно, без реальной декомпозиции на двухвходовые вентили.

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

В качестве примера применения ПЛИ, в данной работе предложен метод обфускации комбинационной схемы, построенной на основе LUT. Задача обфускации (скрытие смысла) является актуальной как для компьютерных программ, так и для схемотехнических решений [5]. Метод основан на введении в комбинационную схему некоторого числа фиктивных циклов, что делает задачу автоматического восстановления ее Булевой функции крайне сложной.

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

Литература

1. Stratix IV Device Handbook, Altera Corp., Nov 2009.

2. HardCopy III Device Handbook, Altera Corp., July 2009.

3. Н.А.Кононов «Оптимизационный подход к выбору универсальных логических модулей для СБМК и ПЛИС», тезисы докладов «Микроэлектроника и Информатика — 2010» - с.79

4. Актуальные проблемы моделирования в системах автоматизации схемотехнического проектирования / под ред. А.Л.Стемпковского. – М.: Наука, 2003. – 430 с.

5. Norman K.T. “Algorithms for white-box obfuscation using randomized subcircuit selection and replacement”, Thesis, Air Force Institute of Technology, Ohio, 2008, 99 pp.