Построение аппроксимирующих схем в режиме троирования | Известия вузов. Физика. 2022. № 4. DOI: 10.17223/00213411/65/4/150

Построение аппроксимирующих схем в режиме троирования

Троирование является одним из широко используемых на практике подходов к обеспечению надежности функционирования логических схем. Однако появившиеся в последние годы возможности одновременного внесения в каждую копию и соответствующие линии вредоносных подсхем (Trojan Circuits) делают метод троирования уязвимым. Возникает необходимость противостоять таким угрозам. Одним из выходов в этой ситуации является использование вместо идентичных трех схем двух аппроксимирующих схем и одной рабочей схемы, выполняющей предписанное разработчиком функционирование. Этот подход приводит к появлению незащищенной области, в которой неисправность одной из трех схем может быть не обнаружена. Предлагается строить аппроксимирующие схемы, начиная с построения аппроксимирующих систем булевых функций, являющихся заданием на их синтез. Показано, что этот подход дает больше возможностей для сокращения незащищенной области, чем известные ранее методы. Приведены алгоритмы получения аппроксимирующих систем булевых функций из безызбыточной системы ДНФ рабочей схемы и алгоритм оценки величины незащищенной области.

Deriving Approximate logic circuits for triple-modular redundancy (TMR) schemes.pdf Введение Надежность сложных физических систем зависит от надежности составляющих их компонент, в частности, от надежности управляющих компонент, которые, как правило, являются логическими схемами высокой производительности. Схемы троирования являются одним из широко распространенных подходов к обеспечению надежности функционирования логических схем. Предполагается, что одна из трех схем может быть неисправной. В этом случае в условиях подключения к одноименным выходам трех схем схемы голосования значение выхода определяется значением большинства одноименных выходов. Схемы голосования предполагаются исправными. Однако в современных условиях производство логической схемы может выполняться различными фирмами, в том числе, и в разных частях света. В связи с этим появляется возможность включения вредоносной подсхемы в каждую из идентичных схем, например, в соответствующую линию каждой из трех схем. Вредоносная подсхема (Trojan Circuit) может изменить в нужный момент значение сигнала на этих линиях на противоположное значение с целью искажения работы схемы или с целью извлечения конфиденциальной информации из устройства, содержащего рассматриваемую схему. Это значит, что технология троирования оказывается уязвимой в условиях возможности включения вредоносных подсхем. Одним из известных подходов к защите схемы троирования является использование аппроксимирующих схем, которые строятся из рабочей схемы, реализующей нужное разработчику поведение [1-3]. Аппроксимирующие схемы используются также при синтезе самопроверяемых логических схем [4-6]. В работе [1] аппроксимирующие схемы используются с целью сокращения аппаратурных затрат в условиях, когда функционирование самопроверяемой схемы может незначительно отклоняться от функционирования рабочей схемы, что менее важно, чем сокращение аппаратурных затрат. При использовании аппроксимирующих схем в схемах троирования отклонение от корректного функционирования возможно в присутствии неисправности в одной из трех схем в так называемой незащищенной области. В данной работе при построении аппроксимирующих схем основное внимание уделяется проблеме сокращения незащищенной области. С этой целью предлагается строить аппроксимирующие схемы из аппроксимирующих систем булевых функций. Это значит, что предлагается еще на этапе создания рабочей схемы учесть необходимость ее защиты от внедрения вредоносных подсхем при использовании троирования. Этот подход дает большие возможности для сокращения незащищенной области. Предлагается вычисление оценки незащищенной области, основанное на поиске всех тестовых наборов для константных неисправностей подмножества литер системы булевых функций и их компактном представлении в виде ROBDD-графов. 1. Возможные подходы к защите схем троирования от внедрения вредоносных подсхем Одним из возможных подходов борьбы с внедрением вредоносных подсхем в системы троирования может быть использование различных методов получения безызбыточной системы ДНФ (различных эвристик в рамках одного метода) в качестве задания на синтез каждой из схем троирования. Далее к полученным системам можно применить различные методы синтеза, возможно, различные эвристики при применении одного и того же метода синтеза. В результате получаем три различные схемы, реализующие одну и ту же систему булевых функций (три схемы, реализующие одну и ту же систему частичных булевых функций, когда речь идет о комбинационных составляющих схем с памятью). Включение в различающиеся схемы одинаковых вредоносных подсхем оказывается затруднительным. Такой подход гарантирует обнаружение любого искажения одной из систем булевых функций, как и при обычном троировании, и затрудняет внедрение вредоносных подсхем (Trojan Circuits). Этот подход приводит к получению различных по сложности схем, одноименные выходы которых поступают на схему голосования. Он может быть применен в рамках конкретных АРМов, используемых разработчиком. Другим подходом к защите от введения в систему троирования вредоносных подсхем является применение аппроксимирующих схем, которые в большей степени, чем в рамках предыдущего подхода, затрудняют введение вредоносных подсхем в три схемы одновременно. Речь идет о том, что одна схема реализует интересующую нас систему булевых функций, а две другие системы булевых функций отличаются от заданной системы, по возможности, незначительно. В дальнейшем будем называть первую схему рабочей схемой. Две другие схемы принято называть аппроксимирующими схемами, а реализуемые ими системы - аппроксимирующими системами булевых функций. В работах [1-3] предлагается строить аппроксимирующие функции на основе анализа и последующей модификации структуры рабочей схемы. В рабочую схему (в ее внутренние полюсы) с целью получения аппроксимирующих схем вводятся константные неисправности: либо константа 0 в каждый из выбранных полюсов, либо константа 1. Затем в полученные схемы добавляются элементы для обеспечения необходимых свойств систем булевых функций, реализуемых искаженными схемами. При замене выбранных полюсов константой 0 получается система булевых функций, поглощаемая системой, реализуемой рабочей схемой. При замене выбранных полюсов константой 1 получается система, поглощающая систему, реализуемую рабочей схемой. Выбор полюсов ориентирован на возможно меньшие отличия систем булевых функций аппроксимирующих схем от системы рабочей схемы. Эти отличия находятся, как правило, в результате моделирования и, следовательно, оценка выбираемых полюсов является приближенной. При использовании созданных аппроксимирующих схем возникает незащищенная область, в рамках которой неисправности одной из схем могут оказаться не обнаружимыми при их первом проявлении, а возможно, и во всей рабочей области функционирования этой схемы. Чем меньше отличаются аппроксимирующие системы от системы рабочей схемы, тем меньше незащищенная область. В рассматриваемом в данной работе подходе построение аппроксимирующих схем предлагается начать с построения систем аппроксимирующих функций, которые затем используются в качестве задания на синтез аппроксимирующих схем. Такой подход, во-первых, позволяет получать аппроксимирующие системы, существенно более близкие к системе рабочей схемы, а, во вторых, не требует введения в рабочую схему дополнительных элементов для обеспечения на выходах аппроксимирующей схемы, полученной введением в полюсы рабочей схемы константных неисправностей, их монотонного проявления. Предлагаемый нами подход ориентирован на этапы автоматизированного синтеза логических схем, используемые в современных САПР. В частности, предполагается, что задание на синтез рабочей схемы представляется безызбыточной системой ДНФ (БДНФ). Неисправности константа 0 сводятся к исключению некоторых конъюнкций отдельных ДНФ, т.е. к a-неисправностям нескольких конъюнкций из БДНФ [7, 8]. Неисправности константа 1 сводятся к снижению на единицу ранга конъюнкций отдельных ДНФ из БДНФ, т.е. к b-неисправностям некоторых конъюнкций [7, 8]. Объединив ROBDD-графы, представляющие все тестовые наборы для каждой из введенных в рабочую систему БДНФ константных неисправностей, получаем ROBDD-граф R, представляющий незащищенную область при использовании метода троирования. Предлагаемый подход не требует моделирования на всем множестве входных наборов схемы, однако позволяет получить точные оценки качества выбираемых литер при замене их константами. Это значит, что он может быть применен при синтезе схем, зависящих от нескольких десятков и более входных полюсов в условиях, что ROBDD-графы, построенные для БДНФ, не зависят экспоненциально от числа входных полюсов схемы. Для последних схем нужны методы, ориентированные на SAT-технологии. Рассматриваемые в данной работе схемы составляют широкий класс используемых на практике логических схем, а предлагаемые в работе алгоритмы, основанные на операциях над ROBDD-графами, характеризуются полиномиальной сложностью от числа входов схемы. К сформированным системам булевых функций можно применять различные методы синтеза логических схем или различные модификации одного и того же метода в рамках возможностей АРМа, используемого разработчиком схемы троирования. Это позволит еще больше затруднить введение вредоносных подсхем в схемы троирования. Как известно, константные неисправности внутренних полюсов схемы приводят к значительному искажению поведения схемы, т.е. в среднем произвольные константные неисправности могут на 1/3 исказить рабочую область функционирования схемы. Из этого следует, что очень важно находить внутренние полюсы схемы с небольшим множеством тестовых наборов для их константных неисправностей. Такие полюсы обычно отыскиваются путем моделирования и, следовательно, оценки их качества для сложных схем могут быть только приближенными. Неисправности внутренних полюсов схемы порождают в общем случае более существенные искажения БДНФ рабочей схемы по сравнению с предлагаемым в данной работе подходом. Мы имеем в виду, в частности, использование метода синтеза, основанного на делении ДНФ, сохраняющего исходную БДНФ при синтезе рабочей схемы [9]. Фиксирование константой 0 некоторого внутреннего полюса рабочей схемы в общем случае приводит к исчезновению нескольких конъюнкций БДНФ рабочей схемы, как правило, более одной конъюнкции. Фиксирование константой 0 конъюнкции БДНФ приводит к исчезновению одной конъюнкции одной функции системы. При фиксировании внутреннего полюса рабочей схемы константой 1 происходит исчезновение, как правило, нескольких букв в нескольких конъюнкциях БДНФ рабочей схемы. Фиксирование константой 1 конъюнкции БДНФ приводит к исчезновению буквы в одной конъюнкции одной из функций системы. Из сказанного следует, что предлагаемый нами подход позволяет получать аппроксимирующие системы, более близкие к БДНФ рабочей схемы. При фиксировании константой 0 некоторых литер в конъюнкциях БДНФ рабочей схемы сложность аппроксимирующей схемы может уменьшиться. При фиксировании константой 1 некоторых литер в конъюнкциях БДНФ рабочей схемы возможно усложнение аппроксимирующей схемы. Выбор конъюнкций в БДНФ рабочей схемы для внесения в них неисправностей с целью построения аппроксимирующих систем функций ориентирован, в первую очередь, на достижение возможно меньшего отличия аппроксимирующих систем от БДНФ рабочей схемы, т.е. на возможно большее сокращение незащищенной области. Предлагаются алгоритмы выбора литер БДНФ для внесения в них неисправностей. Эти алгоритмы основаны на получении всех тестовых наборов для каждой из неисправностей и компактного их представления в виде ROBDD-графа. Такие ROBDD-графы позволяют оценивать долю тестовых наборов в пространстве переменных БДНФ. Используемый подход дает возможность по соответствующим ROBDD-графам получать вероятностные оценки доли незащищенной области. Это, в свою очередь, позволяет находить компромисс между вычисленной долей и сложностью получаемых с помощью выбранных методов синтеза аппроксимирующих схем. 2. Построение аппроксимирующих систем булевых функций Введем ряд определений. Пусть F(x1, …, xn) = f1(x1, …, xn),…, fm(x1, …, xn) - система из m булевых функций от n переменных. Будем говорить, что система G(x1, …, xn) = = g1(x1, …, xn),…, gm(x1, …, xn) поглощает систему F(x1, …, xn) = f(x1, …, xn), …, fm(x1, …, xn), если для любого набора α = α1, …, αn F(α1, …, αn) < G(α1, …, αn), т.е. для одноименных функций системы выполняется условие fi(α1, …, αn) < = gi(α1, …, αn). Обозначим символом G(x1, …, xn) систему, реализуемую рабочей схемой, а через F1(x1, …, xn)(F0(x1, …, xn)) - поглощающую (поглощаемую) аппроксимирующие системы. Для трех систем выполняется соотношение F0(x1, …, xn) < G(x1, …, xn) < (F1(x1, …, xn). (1) Это соотношение представлено на рис. 1, здесь незащищенная область не заштрихована. Рис. 1. Графическое представление связи между системой, реализуемой рабочей схемой, и аппроксимирующими системами Пусть описание поведения рабочей схемы представлено в виде БДНФ. Это значит, что БДНФ состоит из простых импликант системы булевых функций. В общем случае предполагается, что БДНФ построена по системе частичных булевых функций. Каждая конъюнкция БДНФ снабжается характеристикой, в ней перечислены функции, для которых эта конъюнкция является допустимой. Конъюнкция допустима, если ее пересечение с областью нулевых наборов значений переменных частичной функции системы пусто, а с областью единичных наборов значений переменных частичной функции не пусто. Поскольку конъюнкция БДНФ является простой импликантой системы булевых функций, то из нее нельзя исключить ни одной (любой) литеры в условиях сохранения характеристики этой конъюнкции. Кроме того, так как список конъюнкций с соответствующими характеристиками представляет безызбыточную систему ДНФ, то из характеристики конъюнкции этой системы нельзя исключить ни одной функции. Пусть в БДНФ G(x1, …, xn) рабочей схемы в некоторых конъюнкциях одна из переменных заменяется константой 1, в каждом случае в конъюнкции одной из функций системы. В результате получена система F1(x1, …, xn). Утверждение 1. G(x1, …, xn) < F1(x1, …, xn). Утверждение очевидно, поскольку исключение переменной в конъюнкции некоторой функции системы приводит к расширению области единичных значений этой функции и, следовательно, к расширению области единичных значений системы в целом. Пусть система ДНФ F0(x1, …, xn) получается из БДНФ G(x1, …, xn) рабочей схемы исключением конъюнкций из некоторых функций БДНФ G(x1, …, xn), не обязательно из каждой функции. Это означает, что в характеристиках некоторых конъюнкций системы исключено по одной из функций. Полученную таким образом систему обозначаем F0(x1, …, xn). Утверждение 2. F0(x1, …, xn) < G(x1, …, xn). Утверждение очевидно, поскольку исключение одной функции из характеристики конъюнкции означает сокращение области единичных значений этой функции и, следовательно, сокращение области единичных значений системы в целом. Из сказанного следует, что предлагаемые способы получения систем F0(x1, …, xn) и F1(x1, …, xn) гарантируют выполнение соотношения (1). Получение системы F0(x1, …, xn) Опишем основные шаги алгоритма. Предварительно упорядочим конъюнкции БДНФ G(x1, …, xn) по неубыванию рангов. Можно ограничиться рассмотрением не всех конъюнкций, а лишь их части из начала списка. 1. Извлекаем из системы каждую конъюнкцию по очереди. 2. Для каждой функции из характеристики выбранной конъюнкции строим ROBDD-граф, представляющий множество тестовых наборов, обнаруживающих исчезновение этой конъюнкции из ДНФ функции, которая сопоставлена удаленной функции из характеристики рассматриваемой конъюнкции. Это множество характеризует отличие рассматриваемой ДНФ от той, которая представляется БДНФ G(x1, …, xn). 3. Просмотрев все функции в характеристике конъюнкции, выбираем ту функцию, которая характеризуется множеством тестовых наборов наименьшей мощности. Таких функций может быть несколько. Запоминаем эти функции вместе с соответствующей конъюнкцией. Переходим к следующей конъюнкции БДНФ G(x1, …, xn). 4. Если все конъюнкции в БДНФ G(x1, …, xn) (некоторое заданное их подмножество) просмотрены, выбираем по невозрастанию мощностей соответствующих тестовых наборов L различных конъюнкций с соответствующими функциями. Желательно, чтобы исказилась каждая из функций системы, тогда значение L должно быть не меньше числа m функций системы. 5. Исключаем в характеристиках выбранных конъюнкций выбранные функции, получаем систему F0(x1, …, xn). 6. Объединяем ROBDD-графы, представляющие множества тестовых наборов, обнаруживающих удаление конъюнкций, и получаем ROBDD-граф R0, представляющий множество наборов, отличающее систему F0(x1, …, xn) от БДНФ G(x1, …, xn). 7. Вычисляем по R0 долю наборов, составляющих незащищенную область за счет использования аппроксимирующей системы F0(x1, …, xn). Получение системы F1(x1, …, xn) Опишем основные шаги алгоритма. Предварительно упорядочим конъюнкции БДНФ G(x1, …, xn) по неубыванию рангов. Можно ограничиться рассмотрением не всех конъюнкций, а лишь их частью из начала списка. Будем иметь в виду, что выбрасывание переменной из конъюнкции искажает не каждую функцию из характеристики этой конъюнкции, а только некоторые из них. Последние функции будем называть нерасширяемыми по рассматриваемой переменной исследуемой конъюнкции. 1. Извлекаем из системы каждую конъюнкцию по очереди. 2. Для каждой переменной рассматриваемой конъюнкции находим множество функций из характеристики конъюнкции, для которых конъюнкция не расширяема по этой переменной. 3. Для каждой функции выбранного подмножества и выбранной переменной строим множество тестовых наборов, обнаруживающих исключение переменной в рассматриваемой конъюнкции. Представляем это множество соответствующим ROBDD-графом. Выбираем ту функцию, в которой множество тестовых наборов наименьшее. Таких функций может быть несколько. Запоминаем эти функции вместе с соответствующей конъюнкцией и переменной. 4. Просматриваем все переменные выбранной конъюнкции, выполняя для каждой п. 2, 3. Переходим к следующей конъюнкции БДНФ G(x1, …, xn). 5. Если все конъюнкции БДНФ G(x1, …, xn) (некоторое заданное их подмножество в начале списка, представляющего БДНФ G(x1, …, xn)) просмотрены, выбираем по невозрастанию мощностей соответствующих тестовых наборов L конъюнкций с соответствующими функциями и переменными. Желательно, чтобы исказилась каждая из функций системы, тогда значение L должно быть не меньше числа m функций системы. 6. Исключаем в характеристиках выбранных конъюнкций выбранные функции и добавляем в систему конъюнкции, в которой некоторые переменные удалены. В добавленных конъюнкциях характеристики в общем случае являются подмножеством характеристик соответствующей конъюнкции БДНФ G(x1, …, xn). Получаем систему F1(x1, …, xn). 7. Объединяем ROBDD-графы выбранных переменных из соответствующих конъюнкций и функций. Получаем ROBDD-граф R1, представляющий множество наборов, отличающее систему F1(x1, …, xn) от БДНФ G(x1, …, xn). Вычисляем по R1 долю наборов, составляющих незащищенную область за счет использования поглощающей аппроксимирующей системы. Сложив доли, вычисленные по графам R0, R1, получим долю незащищенных наборов при использовании аппроксимирующих функций. Заметим, что чем выше ранги конъюнкций БДНФ G(x1, …, xn) рабочей схемы, тем меньше в среднем доля незащищенной области при фиксированном L. Далее приведем алгоритмы вычисления всех тестовых наборов для а- и b-неисправностей БДНФ. 3. Получение множества всех тестовых наборов для a-неисправности системы ДНФ Итак, имеем систему ДНФ D = D1, …, Dm, являющуюся БДНФ. Система задана списком конъюнкций с соответствующими характеристиками. (Начинаем с БДНФ рабочей схемы.) В одной из ДНФ, представляющей функцию fj системы удалена конъюнкция ki. Это обеспечивается удалением из характеристики конъюнкции в системе D функции fj. Требуется найти множество тестовых наборов, обнаруживающих рассматриваемую неисправность, компактно представив его ROBDD-графом. Речь идет об a-неисправности в ДНФ, представляющей функцию fj в заданной системе. Поскольку рассматриваемая система порождена БДНФ, то удаление любой конъюнкции из множества конъюнкций отдельной функции сокращает множество единичных наборов этой функции. Тестовые наборы для такой неисправности есть наборы, на которых функция fj обращается в единицу только за счет конъюнкции ki. В общем случае это часть наборов, обращающих конъюнкцию ki в единицу. Алгоритм 1. Формируем список конъюнкций функции fj после удаления конъюнкции ki. Конъюнкции в этом списке не имеют характеристик, они представляют фрагмент ДНФ Dj (Dj/ki) функции fj в системе D. По этому списку строим ROBDD-граф (Dj/ki). 2. Представляем конъюнкцию ki ROBDD-графом R(ki). 3. Находим пересечение полученных графов, обозначаем его графом , = (Dj/ki) & R(ki). Полученный граф представляет наборы, на которых конъюнкция ki обращается в единицу совместно с некоторыми другими конъюнкциями рассматриваемой ДНФ. 4. Получаем инверсию графа , переименовав его терминальные вершины. Полученный граф обозначим . 5. Граф Ra(ki) = & R(ki) представляет множество всех тестовых наборов для рассматриваемой a-неисправности. 4. Получение множества всех тестовых наборов для b-неисправности системы ДНФ Формируем список конъюнкций функции fj из системы D. Конъюнкции в этом списке не имеют характеристик, они представляют ДНФ Dj функции fj в системе D. Удаляем из конъюнкции ki этой ДНФ литеру xs, по которой эта конъюнкция является нерасширяемой. Необходимо найти множество тестовых наборов, обнаруживающих эту неисправность, компактно представив его ROBDD-графом. Речь идет о b-неисправности в ДНФ, представляющей функцию fj в заданной системе D. Поскольку рассматриваемая конъюнкция является нерасширяемой по переменной xs, то удаление этой переменной из рассматриваемой конъюнкции расширяет множество единичных наборов функции fj. Тестовые наборы для такой неисправности есть наборы, на которых функция fj принимает единичное значение за счет b-неисправности конъюнкции ki вместо предписанного ей нулевого значения. Алгоритм 1. Формируем список конъюнкций функции fj из системы D. Конъюнкции в этом списке не имеют характеристик, они представляют ДНФ Dj функции fj в системе D. По этому списку строим ROBDD-граф R(Dj). 2. Формируем дополнение конъюнкции ki, заменив в ki литеру xs на инверсную. Обозначаем дополнение символом ki*. Представляем конъюнкцию ki* ROBDD-графом R(ki*). 3. Находим инверсию графа R(Dj), переименовав его терминальные вершины. Обозначаем полученный граф . Граф Rb(ki) = & R(ki*) представляет множество всех тестовых наборов для рассматриваемой b-неисправности. 5. Определение по ROBDD-графу доли единичных наборов представляемой им функции Напомним известную процедуру решения этой задачи. Итак, задан ROBDD-граф, представляющий некоторую функцию. Требуется определить долю единичных наборов этой функции. Сведем задачу к определению вероятности единичного значения этой функции в условиях, когда вероятность единичного значения каждой переменной функции равна 1/2. Воспользуемся формулой разложения Шеннона для каждой функции, сопоставляемой внутреннему полюсу ROBDD-графа. Вероятность единичного значения функции , представляемой вершиной ROBDD-графа, вычисляется с использованием вероятностей , единичных значений функций и , сопоставляемых дочерним вершинам вершины , следующим образом (вершина отмечена переменной ): . Двигаясь от 1 терминальной вершины к корню графа и используя приведенную выше формулу, достигаем корня ROBDD-графа и, следовательно, вычисляем вероятность единичного значения функции, представленной графом. Проиллюстрируем процедуру построения аппроксимирующих функций на примере, используя матрицы в коде Грея [10]. Такое представление функций системы является более наглядным, чем ROBDD-графы. 6. Построение системы аппроксимирующих функций с использованием матричного представления функций Имеем систему булевых функций, заданную перечнем конъюнкций системы, причем, конъюнкции представлены соответствующими троичными векторами, в характеристиках конъюнкций перечислены функции системы: - 1 - 1 0 / 1, 3 1 1 - - - / 1 1 - - - 0 / 1, 3 0 - - 0 0 / 2, 3 - 0 - 1 - / 2 - - 1 1 1 / 3. Выделим из системы отдельные функции, представив их в виде ДНФ: , , . Далее представим функции этой системы матрицами в коде Грея на рис. 2. a б в Рис. 2. Представление системы на матрицах Пусть для получения аппроксимирующих функций в качестве возможных изменений выбраны две конъюнкции системы: / 1, 3 и / 2, 3. Сокращаем область единичных значений за счет одной из выбранных конъюнкций в каждой функции системы, рассматривая соответствующие a-неисправности. В ДНФ первой функции исключаем конъюнкцию . В результате получаем функцию, представленную на рис. 3. Область сокращения единичных значений заштрихована. Рис. 3. Исчезла конъюнкция из f1 В ДНФ второй функции исключаем конъюнкцию . В результате получаем функцию, представленную на рис. 4. Область сокращения единичных значений заштрихована. Рис. 4. Исчезла конъюнкция из f2 В ДНФ третьей функции исключаем конъюнкцию . В результате получаем функцию, представленную на рис. 5. Область сокращения единичных значений заштрихована. Рис. 5. Исчезла конъюнкция из f3 Представляем аппроксимирующую систему F0 в виде: 1 1 - - - / 1 1 - - - 0 / 1, 3 0 - - 0 0 / 3 - 0 - 1 - / 2 - - 1 1 1 / 3 Далее находим аппроксимирующую систему F1. Рассматриваем конъюнкцию . Она является нерасширяемой по каждой из своих переменных для функции f1. Обеспечиваем для каждой из переменных этой конъюнкции искажения функции за счет удаления одной из переменных. Результаты представлены на рис. 6. Области искажений заштрихованы, они одинаковы по мощности для каждой из удаляемых переменных. a б в Рис. 6. Расширение области единичных значений f1 за счет конъюнкции Конъюнкция для функции f3 не расширяема по переменной x4. Искажения функции за счет исключения остальных переменных рассматриваемой конъюнкции представлены на рис. 7. Области искажений заштрихованы, они одинаковы по мощности. a б Рис. 7. Расширение области единичных значений f3 за счет конъюнкции по переменным x2, x5 Конъюнкция для функции f2 не расширяема по каждой переменной. За счет исключения по одной из переменных получаем искажения этой функции, представленные на рис. 8. Наименьшие искажения обеспечиваются исключением из рассматриваемой конъюнкции переменной x4. a б в Рис. 8. Расширение области единичных значений f2 за счет конъюнкции по каждой из переменных Конъюнкция для функции f3 не расширяема по переменным x4, x5. Результаты исключения каждой из этих переменных представлены на рис. 9. Наименьшие искажения обеспечиваются исключением из рассматриваемой конъюнкции переменной x4. a б Рис. 9. Расширение области единичных значений f3 за счет конъюнкции по переменным x4, x5 В результате из конъюнкции в функциях f1, f3 исключаем переменную x5, а в функции f2 из конъюнкции ͞ исключаем переменную x4. Получаем систему F1 в виде - 1 - 1 - / 1, 3 1 1 - - - / 1 1 - - - 0 / 1, 3 0 - - 0 0 / 3 - 0 - 1 - / 2 - - 1 1 1 / 3 0 - - - 0 / 2. Итак, область единичных значений функции f1 сокращается на 2 набора и расширяется на 2 набора, т.е. на 4 наборах из 32 искажения функции f1 могут быть не обнаружены при троировании. Область единичных значений функции f2 сокращается на 4 набора и расширяется на 2 набора, т.е. на 6 наборах из 32 искажения функции f2 могут быть не обнаружены при троировании. Область единичных значений функции f3 сокращается на 2 набора и расширяется на 2 набора, т.е. на 4 наборах из 32 искажения функции f3 могут быть не обнаружены при троировании. В примере доля незащищенных наборов довольно высока, поскольку рассматривается система от малого числа переменных. Однако, чем больше число переменных системы, тем в среднем выше ранги конъюнкций системы, а чем выше ранги конъюнкций БДНФ G(x1, …, xn) рабочей схемы, тем меньше в среднем доля незащищенной области при фиксированном L. Заключение Предложен подход к построению аппроксимирующих схем, основанный на предварительном построении аппроксимирующих функций и последующем синтезе по ним комбинационных схем. Аппроксимирующие схемы ориентированы на защиту схемы троирования от внедрения вредоносных подсхем (Trojan Circuits). Этот подход позволяет получать меньшие незащищенные области, чем известные ранее методы синтеза аппроксимирующих схем. Алгоритмы получения аппроксимирующих систем и оценки порожденной ими незащищенной области основаны на использовании операций над ROBDD-графами.

Ключевые слова

комбинационные схемы, безызбыточные системы ДНФ, аппроксимирующие схемы, троирование, константные неисправности, тестовые наборы, обнаруживающие константные неисправности

Авторы

ФИООрганизацияДополнительноE-mail
Матросова Анжела ЮрьевнаНациональный исследовательский Томский государственный университетд.т.н., профессор, профессор кафедры компьютерной безопасности ИПМКН НИ ТГУmau11@yandex.ru
Останин Сергей АлександровичНациональный исследовательский Томский государственный университетк.т.н., доцент, зав. кафедрой компьютерной безопасности ИПМКН НИ ТГУsergeiostanin@yandex.ru
Гошин Геннадий ГеоргиевичТомский государственный университет систем управления и радиоэлектроникид.ф.-м.н., профессор, профессор кафедры сверхвысокочастотной и квантовой радиотехники ТУСУРаgoshingg@svch.tusur.ru
Всего: 3

Ссылки

Chaudhury M.R., Mohandram K. // Proc. DATE. - 2008. - P. 902-908.
Sanchez Clemente A., Entrena L., Garsea Valderas, Lopez-Ongil C. // Proc. of 18-th IOLTS. - 2012. - P. 176-18.
Antonio Jose Sanchez Clemente. Transient Error Mitigation by Means of Approximate Logic Circuits: Tesis Doctoral. - Universidad Carlos III de Madrid, 2017.
Touba N.A., McCluskey E.J. // IEEE Trans.Computer-aided Design. - 1997. - V. 16. - P. 783-789.
Saposhnikov V.V. et al. // Proc. Asian Test Symposium. - 1998. - P. 296-300.
Das D., Touba N. //j. Electron. Testing: Theory and Applications. - 1999. - V. 15. - P. 145-155.
Kohavi I., Kohavi Z. // IEEE Trans.Comput. - 1972. - V. C-21. - No. 6. - P. 556-558.
Матросова А.Ю. // Автоматика и вычислительная техника. - 1978. - № 5. - С. 42-45.
Матросова А.Ю., Кудин Д.В., Николаева Е.А. // Вестник Томского государственного университета. Управление. Вычислительная техника и информатика. - 2011. - № 2. - С. 99-107.
Karnaugh M. // Trans. Am. Institute of Electrical Engineers. Part I: Communication and Electronics. - 1953. - V. 72 (5). - P. 593-599.
 Построение аппроксимирующих схем в режиме троирования | Известия вузов. Физика. 2022. № 4. DOI: 10.17223/00213411/65/4/150

Построение аппроксимирующих схем в режиме троирования | Известия вузов. Физика. 2022. № 4. DOI: 10.17223/00213411/65/4/150