МЕТОД ОБНАРУЖЕНИЯ НЕДЕКЛАРИРОВАННЫХ ВОЗМОЖНОСТЕЙ И ЗНАЧЕНИЙ DON’T CARE ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА
32 О. Ф. Немолочнов, А. Г. Зыков, В. С. Кулагин и др.
УДК 004.056.53
О. Ф. НЕМОЛОЧНОВ, А. Г. ЗЫКОВ, В. С. КУЛАГИН, Л. Г. ОСОВЕЦКИЙ, В. И. ПОЛЯКОВ, А. В. СУХАНОВ
МЕТОД ОБНАРУЖЕНИЯ НЕДЕКЛАРИРОВАННЫХ ВОЗМОЖНОСТЕЙ И ЗНАЧЕНИЙ DON’T CARE
ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА
Рассматриваются вопросы верификации вычислительных процессов по графоаналитическим моделям, управляемых частично-определенными булевыми функциями. Исследуются задачи поиска по булеву графу управления и кубическим покрытиям недекларированных возможностей и мертвого кода как следствия значения don’t care. Приведены примеры построения покрытий для булева графа и верификации значений don’t care в виде покрытия конъюнкции отношений-неравенств, тождественно равных нулю.
Ключевые слова: вычислительный процесс, недекларированные возможности, мертвый код, графоаналитическая модель.
Введение. Определим вычислительный процесс как процесс преобразования информации по формулам и алгоритмам, позволяющим вычислять значения некоторого множества переменных. Вычисление значений переменных по разным формулам и алгоритмам осуществляется в соответствии с множеством отношений-неравенств, которыми задаются условия-предикаты. Каждое отношение может либо выполняться, либо не выполняться, т.е. принимать два значения: true и false (верное и ложное), и, следовательно, образует предикат на множестве значений переменных, входящих в левую и правую части неравенств. Для описания вычислительного процесса, порождаемого логической схемой или программой, необходимо построить модель, которая позволит формализовать его описание и упростить решение различных задач синтеза и анализа с применением аппарата теории множеств и алгебры логики. В качестве такой модели удобно использовать графоаналитическое представление вычислительного процесса [1]. В вершинах графа располагаются итеративные и рекуррентные формулы и условия-предикаты (отношения). Связи между вершинами задаются дугами. В общем случае в вершине может размещаться любой алгоритм преобразования информации. Дуги управления образуют конъюнкции условий-предикатов, их дизъюнкции образуют булевы функции. Основная задача исследования вычислительного процесса (ВП) — его верификация в соответствии с декларацией — заключается в верификации декларированных и недекларированных возможностей ВП и в поиске несуществующих значений don’t care (от англ. — букв.: „все равно“, „не заботит“).
Таким образом, задача верификации вычислительного процесса может быть сведена к поиску недекларированных возможностей (НДВ) и конъюнкций условий-предикатов, тождественно равных нулю, для которых системы неравенств не имеют решений. НДВ на графе вычислительного процесса образуют множество вершин и дуг, недостижимых через последовательности входных наборов, построенных в соответствии с декларацией и значением don’t care, которые порождают частично-определенные булевы функции. Эти функции при их отображении на n-мерный двоичный куб Еn2 могут быть заданы покрытиями комплексов K1( f ) , где f=1, K 0 ( f ) , где f=0, и K d ( f ) , где f=d (don’t care). Поиск и верификация вершин комплекса K ( f ) и составляет основную задачу анализа вычислительных процессов.
Графоаналитическая модель вычислительного процесса. Информационные потоки в вычислительных процессах управляются некоторым множеством условий-предикатов в виде отношений-неравенств. Неравенства могут выполняться, порождая предикат P, равный T, или
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
Метод обнаружения недекларированных возможностей и значений don’t care ВП
33
не выполняться, порождая предикат F. Формула понимается как конечная последовательность переменных и знаков математических операций между ними, т.е. как линейная формула FR. Значение, вычисленное по формуле FR, будем обозначать как |FR|. Алгоритм понимается как некоторая конечная последовательность элементарных действий, приводящих к однозначному результату — значению переменной. Обобщением формулы или алгоритма является некоторый оператор S, имеющий одну точку входа (Тin) и одну точку выхода (Tout).
Представление и описание вычислительного процесса в виде графа — это некоторая не зависящая от конкретной реализации метамодель, например, в виде логической схемы или программы на алгоритмическом языке.
Для описания вычислительного процесса введем три типа вершин [2]: 1) линейные — для формул и операторов; 2) условные — для отношений-неравенств; 3) объединения связей между линейными и условными вершинами. Связи между вершинами являются однонаправленными, т.е. всегда имеется источник и приемник передачи управления: таким образом, информационные потоки в виде последовательности вершин и дуг являются направленными и детерминированными. Аналитическое описание вершин может быть задано как в виде логико-алгебраических выражений, сочетающих в себе логику условий-предикатов и алгебраические формулы вычисления переменных, так и в виде кубических покрытий [3].
Далее вычислительный процесс может быть фрагментирован на замкнутые параллельные структуры (SR), реализующие альтернативные вычисления переменных r или разных переменных по различным формулам в зависимости от заданного множества условий-предикатов. Условияпредикаты могут задаваться либо непосредственно булевыми переменными, либо косвенно через отношения-неравенства. Некоторое множество вершин и дуг графа вычислительного процесса образует параллельную структуру, если оно содержит одну точку Тin и одну точку Tout. Для каждой структуры SR все разветвления по условиям должны сходиться в одной точке Tout. На алгоритмическом языке высокого уровня им соответствуют условные операторы.
Любая булева функция f, входящая в параллельную структуру SR, является полностью заданной, т.е. образует комплекс K(f)=K1(f)∪Kd(f)∪K0(f). Другими словами, если в структуре SR содержится n условий, то любая булева функция f из SR может быть отображена на кубе
Еn2 множествами вершин K, таких что K1 ∪ K 0 ∪ K d = Еn2 . Здесь d (don’t care) — такие вер-
шины куба Еn2 , в которых значение функции не определено вследствие того, что конъюнкции
условий-предикатов дают пустые пересечения множеств значений переменных, входящих в отношения-неравенства, т.е. система неравенств не имеет решения.
Параллельные структуры SR могут находиться между собой в следующих отношениях: — включение, когда некоторая структура SRj содержит в себе некоторую структуру SRi (SRj ⊃ SRi); — конъюнкция — SRj&SRi, т.е. последовательная композиция; — дизъюнкция — SRj ∨SRi, т.е. параллельная композиция. Вследствие того, что любая структура SR является замкнутой, покрытия входящих в нее булевых функций можно (и нужно) строить независимо друг от друга, полагая, что условияпредикаты локализованы в ней, чем и достигается компактность покрытий. Таким образом, при построении покрытий для некоторой структуры SR другие структуры графа вычислительного процесса могут рассматриваться как некоторые нераскрываемые операторы S, что соответствует реализации вычислительного процесса, описанного на языке высокого уровня, в виде блоков и модулей. На рис. 1 показан пример параллельной структуры, реализующей итеративную формулу
(при k1 < k2 ):
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
34 О. Ф. Немолочнов, А. Г. Зыков, В. С. Кулагин и др.
⎧IFR1 при x < k1; r = ⎨⎪IFR2 при k1 ≤ x ≤ k2 ,
⎪⎩IFR3 при x > k2. На рис. 1 обозначение а соответствует отношению xk2, тогда a : x ≥ k1 и b : x ≤ k2 . Остальные использованные на рис. 1 обозначения соответствуют принятым в работе [2].
zin
a: CV1 x < k1
z′1Т= z1Т
LV3 r := z′3
z′1F= z1F
b: CV2 x < k2
z′2F= z2F
LV4
D3 UD6
z′2Т= z2Т
r := D4 z′4 D5
D6=D3∪D4∪D5
LV5
r := z′5
z′out
Рис. 1
Выражение для r на языке высокого уровня может быть записано условным оператором присваивания:
r:= если (xk2), то ,
иначе . Вычисления покрытия для переменной r сведены в табл. 1, где приведены исходные покрытия для всех вершин графа в соответствии с типовыми покрытиями и принятыми в работе [2] обозначениями.
Таблица 1
zin а b r r′ z1′T z1′F z2′T z2′F z3′ z4′ z5′ zo′ut Примечание
100 010
001
1 С1 ⎫
1 1
С2 С3
⎪⎪ ⎬ ⎪
С
(U D 6
)
0 0 0 0 С 4 ⎭⎪
× 1
××
0
1 0
× ××
1 0
1 0
1 0
× ××
11 00
1 0
0 101 1 110
× 000
10 11
01 10
0×
00
С5 С6
⎫ ⎬ ⎭
С
( LV3
)
С7 С8
⎫ ⎬ ⎭
С ( LV5
)
С9 С10
⎫ ⎬ ⎭
С ( LV4
)
С11 С12
⎫ ⎪ ⎬
С
(CV2
)
C13 ⎪⎭
С14 С15
⎫ ⎪ ⎬
С (CV1
)
C16 ⎭⎪
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
Метод обнаружения недекларированных возможностей и значений don’t care ВП
35
В табл. 2 приведены пересечения кубов, имеющих непустое значение. Вычисления про-
изводились от выхода z′out ко входу zin и свелись фактически к перебору четырех кубов из по-
крытия C(UD6).
Таблица 2
zin а b r r′ z1′T z1′F z2′T z2′F z3′ z4′ z5′ zo′ut
Примечание
1 1 × × 1
0
0
0 100
1 C1∩ C5∩ C15∩ C8∩ C10
1 0 0 × 0
1
0
1 010
1 C3∩ C7∩ C11∩ C6∩ C10
1 0 1 × 0
1
1
0 001
1 C2∩ C9∩ C12∩ C6∩ C8
0 × ××
×
0 0 0 0 000 0
C4∩ C6∩ C8∩ C10
Удалив из покрытия промежуточные значения z′, получим покрытие C(r) в формате zin a b r r′ z′out:
⎧
C(r)=
⎪⎪ ⎨
⎪
⎪⎩
zin a b r
r′ z′out
1 1 × × 1 ⎫
1 0 0 × 1 1 0 1 × 1
⎪⎪ ⎬
.
⎪
0×××
×
0 ⎭⎪
Структура этого покрытия соответствует структуре покрытий для типовых вершин и описывает режим вычисления переменной r по различным итеративным формулам и режим хранения: r=×.
Поиск и верификация недекларированных возможностей. Недекларированные возможности — функциональные возможности программного обеспечения (ПО), не описанные или не соответствующие описанным в документации. Реализацией недекларированных возможностей являются, в частности, программные закладки.
Программные закладки — преднамеренно внесенные в ПО функциональные объекты, которые при определенных условиях (входных данных) инициируют выполнение не описанных в документации функций ПО, приводящих к нарушению конфиденциальности, доступности или целостности обрабатываемой информации [4].
Определим недекларированные возможности в общем виде как все не описанные в декларации особенности и возможности вычислительного процесса, порождаемого программой в ходе ее исполнения. Природа НДВ носит как объективный, так и субъективный характер в силу сложности и размерности самого программного продукта. Однако для НДВ можно выделить в общих чертах следующие основные источники и составляющие:
— наличие в программном продукте специально предусмотренных закладок для наблюдения и отладки ВП в ходе его проектирования и эксплуатации;
— „замалчивание“ излишне мелких подробностей ВП при составлении декларации вследствие стремления к ее компактности;
— наличие в частично определенных булевых функциях f управления ВП неопределенных значений d в виде комплекса Kd(f), который объективно существует, но, как правило, не используется и не описывается.
Поиск и верификацию НДВ ВП можно осуществить путем моделирования процесса либо в виде исполнения программы, либо — на более высоком уровне — по графоаналитической модели.
Моделирование ВП проводится на испытательных наборах входных переменных, построенных по его декларации путем прямого исполнения программы в ходе тестовых экспериментов. При этом необходимо фиксировать вершины и дуги графа, которые достижимы из точки Tin, вычисляются и наблюдаются в точке Tout исследуемой программы.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
36 О. Ф. Немолочнов, А. Г. Зыков, В. С. Кулагин и др.
О п р е д е л е н и е . Если множество вершин и дуг графоаналитической модели вычислительного процесса недостижимы в результате тестовых экспериментов, построенных по декларации, то они образуют множество НДВ.
Множество задействованных вершин и дуг графа образуют декларированные возможности (ДВ) ВП и соответственно программы, его реализующей. Таким образом, все множество вершин и дуг M(V, D) распадается на два подмножества MДВ и MНДВ: M(V, D)=MДВ∪ MНДВ. Указанные подмножества можно построить путем моделирования константных „неисправностей“ для условий-предикатов (m1≡ 1(T) и m0≡ 0(F)) непосредственным внесением их либо в программу [5], либо в условные вершины графоаналитической модели ВП при условии, что такая модель построена. С этой целью в ходе тестовых экспериментов производится сравнение результатов вычислений без „неисправностей“ и с заданной „неисправностью“ m p∈ N, где N — все множество условий-предикатов. Условие-предикат может быть полностью не проверено или проверено только в одном из значений T или F. В этом смысле множество непроверяемых „неисправностей“ и образует множество вершин и дуг НДВ.
Поиск и верификация значений don’t care. Для любой булевой функции f от n переменных область определения состоит из 2n их значений, задающих канонические формы f. Это множество значений может быть сопоставлено с вершинами n-мерного двоичного куба Еn2 , для упрощения логических выражений можно применять исчисление кубических комплексов путем построения неизбыточных покрытий в виде дизъюнктивных нормальных форм (простых импликант) или в виде скобочных форм (полученных методом функциональной декомпозиции). Первый способ применяется при реализации ВП в виде логических схем, а второй — в виде программного продукта.
В случае частично-определенных булевых функций область определения из 2n значений разбивается на два подмножества M1 и M d: M1 ∪ M d= Еn2 и M1 ∩ M d= ∅ . Множество M1 состоит из конъюнкций аргументов, на которых функция принимает значение, равное единице, а множество M d состоит из конъюнкций, тождественно равных нулю. Значения функции f на конъюнкциях из множества M d принято обозначать как d — don’t care: т.е. все равно какое значение имеет функция f, оно может быть произвольно присоединено к любой функции управления z, построенной на множестве M1.
В случае если булевы переменные задаются в виде отношений-неравенств, то значениям d соответствуют системы неравенств, для которых отсутствуют решения, и, следовательно, множество отношений между переменными, входящими в левую и правую части неравенств, дают пустое пересечение.
Итак, определим множество конъюнкций don’t care как множество конъюнкций, тождественно равных нулю. Поиск таких конъюнкций может быть осуществлен либо путем непосредственного решения систем неравенств в аналитической форме, либо методом моделирования отношений на числовой оси в виде линий Ламберта или непосредственным заданием множеств на плоскости в виде диаграмм Эйлера — Венна [6].
Верификация значения don’t care состоит в построении покрытий С1 для M1 и Сd для M d, которые позволяют производить поиск значения don’t care в сокращенной форме для подмножеств из M d и, следовательно, сократить перебор вариантов при решении систем отношений-неравенств.
Рассмотрим описанные выше положения на примере. Пусть на числовых осях x и y заданы четыре отношения:
α: x < 4, β: x > 5, γ: y < 3, ζ: y > 6 .
Здесь отношения α и β не зависят от значений γ и ζ, поэтому поиск значения don’t care можно произвести раздельно.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
Метод обнаружения недекларированных возможностей и значений don’t care ВП
37
Итак, если x5, то эта система неравенств не имеет решения: на числовой оси х
невозможно найти значения х, удовлетворяющие конъюнкции α=β=1, т.е. αβ ≡ 0, что и является значением don’t care. Аналогично конъюнкция γ=ζ=1 также не имеет решения, и тождество γζ ≡ 0 образует значение don’t care для y6.
Покрытие множества Md относительно множества отношений {α,β,γ,ζ} компактно можно записать в виде двух кубов:
αβ γ ζ
Сd
=
⎧ ⎨
⎩
11 ×× ×× 11
⎫ ⎬
.
⎭
Аналогично можно для верификации значения don’t care построить покрытие множест-
ва M1 в виде четырех кубов:
С1
=
⎧ ⎨
⎩
αβγ ζ
×0×0 0 ×0× ×00× 0 ××0
⎫⎬. ⎭
Заметим, что С1 ∪ Сd= Еn2 и С1 ∩ Сd= ∅ : это и свидетельствует о рассмотрении всех
конъюнкций для отношений {α,β,γ,ζ}. Рассмотренные решения проиллюстрированы на рис. 2. На рис. 2, а показаны отноше-
ния {α,β,γ,ζ} в системе координат x y: видно, что число существующих решений для системы неравенств равно 9, а 7 отношений решений не имеют. На рис. 2, б показана развертка куба
Еn2 в виде карты Карно: 1 — вершины множества M1, d — множества Md.
а) б)
у αβ γζ 00 01 11 10
345 6
00 1 1 d 1
296
3
187
01 1 1 d 1 11 d d d d
45
х
10 1 1 d 1
(x5)
и (y6)
С1 ∪ Сd= Еn2 и С1 ∩ Сd= ∅
Рис. 2
Как следует из рассмотренного примера, задача поиска и верификации значения don’t
care заключается в переборе всех вариантов решений, этот перебор может быть сокращен,
если решения искать сразу в кубической форме.
Мертвый код как следствие значения don’t care. Определим понятие мертвого кода (МК) как множества команд программы, которые не могут быть исполнены ни при каких значениях конъюнкций условий-предикатов. Это может быть только в том случае, если данные конъюнкции тождественно равны нулю. Такие конъюнкции и образуют множества значений don’t care и порождают частично-определенные булевы функции. Если функции запрограм-
мированы в явном виде, то операторы, заданные в программе только через них, никогда не будут исполняться. Иными словами, мертвый код всегда есть следствие значения don’t care.
Такие конъюнкции могут быть заданы на уровне булевых переменных в виде явных
тавтологий, например, a ∨ a , aa или в виде избыточных выражений, например, a∨ab, a∨ ab
и т.п. Указанная избыточность может быть следствием ошибок при программировании
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
38 О. Ф. Немолочнов, А. Г. Зыков, В. С. Кулагин и др.
условий, например при настройке стандартных шаблонов, и если это ошибка, а не умысел, то она должна быть устранена путем минимизации логических выражений. Заметим, что для настраиваемых шаблонов значение don’t care может быть только вычислено и указано, в противном случае теряется сам смысл шаблонов как стандартного и апробированного решения.
Если же значение don’t care запрограммировано сознательно в виде артефакта, то порождаемые операторы образуют закладки. Эти закладки не могут быть обнаружены в ходе тестовых экспериментов по полной декларации, содержащей декларированные и недекларированные возможности программы. В этом и состоит принципиальное различие между мертвым кодом и НДВ.
Мертвый код может быть в неявном виде задан при программировании отношенийнеравенств, в этом случае необходимо осуществлять поиск значения don’t care через решение систем неравенств. Для простоты рассмотрения приведем примеры мертвого кода в виде условных выражений над булевыми переменными. Пусть заданы условные выражения, реализующие операторы S1 и S2, которые могут быть операторами присваивания, перехода, обращения к процедурам либо в общем случае любыми составными операторами, модулями или блоками. Итак, пусть заданы два условных выражения:
если ( aa ), то S1, иначе S2, если ( a ∨ a ), то S1, иначе S2.
В первом выражении оператор S1 никогда не будет исполняться, а во втором не будет исполняться оператор S2. Операторы S1 и S2 в данном контексте могут рассматриваться как специально сделанные закладки. Конъюнкции, тождественно равные нулю, показаны на
рис. 3, а, б в виде функций управления zi на булевых графах, реализующих приведенные выше условные выражения соответственно.
a) zi
б) zi
CV1 a:
T
CV1 a: F
T z1 S1
F z1
CV2 a: F z2
T
z3≡0 S1
CV2 a: F z3≡0
T z2
S2 S2
f=aa f=a∨a
Рис. 3
Заключение. Наличие в вычислительном процессе, порождаемом программой при ин-
терпретации ее команд процессором, недекларированных возможностей или мертвого кода
несет в себе явную (НДВ) или неявную (МК) угрозу безопасности программному продукту.
Эта угроза может быть реализована, например, в виде компьютерного вируса. Поэтому поиск
и верификация НДВ и МК является основной задачей в области защиты информации. Реше-
ние этой задачи конструктивно может быть найдено путем построения графоаналитической
модели или, в частном случае, построением булева графа для функции управления вычисли-
тельным процессом. Для сокращения размерности задачи поиска НДВ и МК вычислительный
процесс на графоаналитической модели следует разбивать на параллельные структуры. Такое
разбиение позволяет локализовать поиск и верификацию НДВ и МК в рамках отдельно взя-
той параллельной структуры и не рассматривать все множество реализованных в программе
условий-предикатов совместно.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
Метод обнаружения недекларированных возможностей и значений don’t care ВП
39
СПИСОК ЛИТЕРАТУРЫ
1. Немолочнов О. Ф., Зыков А. Г., Поляков В. И. Комплексные кубические покрытия и графоаналитические модели как средство описания вычислительных процессов программ // Тр. Междунар. науч.-техн. конф. „Интеллектуальные системы“ (AIS’06) и „Интеллектуальные САПР“ (CAD-2006). М.: Физматлит, 2006. Т. 2. С. 3—7.
2. Модель и примитивы вершин циклических вычислительных процессов / О. Ф. Немолочнов, А. Г. Зыков, Л. Г. Осовецкий, В. И. Поляков // Изв. вузов. Приборостроение. 2007. Т. 50, № 8. С. 18—23.
3. Немолочнов О. Ф., Зыков А. Г., Поляков В. И. Кубические покрытия логических условий вычислительных процессов и программ // Науч.-техн. вестн. СПбГУ ИТМО. Информационные технологии, вычислительные и управляющие системы. СПб.: СПбГУ ИТМО, 2004. Вып. 14. С. 225—233.
4. Руководящий документ Гостехкомиссии России „Защита от несанкционированного доступа к информации. Ч. 1. Программное обеспечение средств защиты информации. Классификация по уровню контроля отсутствия недекларированных возможностей“. Введ. 04.06.1999 г.
5. Тестирование логических неисправностей вычислительных процессов в программах / О. Ф. Немолочнов, А. Г. Зыков, Л. Г. Осовецкий и др. // Информ. технологии. 2007. № 12. С. 2—5.
6. Кондаков Н. И. Логический словарь. М.: Наука, 1971.
Олег Фомич Немолочнов Анатолий Геннадьевич Зыков
Вячеслав Сергеевич Кулагин Леонид Георгиевич Осовецкий Владимир Иванович Поляков
Андрей Вячеславович Суханов
Сведения об авторах — д-р техн. наук, профессор; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, кафедра информатики и прикладной математики — канд. техн. наук, доцент; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра информатики и прикладной математики; E-mail: zykov_a_g@mail.ru — канд. техн. наук, доцент; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра электроники — д-р техн. наук, профессор; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра безопасных информационных технологий — канд. техн. наук, доцент; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра вычислительной техники; E-mail: v_i_polyakov@mail.ru — канд. техн. наук, доцент; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра безопасных информационных технологий
Рекомендована кафедрой информатики и прикладной математики
Поступила в редакцию 06.06.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
УДК 004.056.53
О. Ф. НЕМОЛОЧНОВ, А. Г. ЗЫКОВ, В. С. КУЛАГИН, Л. Г. ОСОВЕЦКИЙ, В. И. ПОЛЯКОВ, А. В. СУХАНОВ
МЕТОД ОБНАРУЖЕНИЯ НЕДЕКЛАРИРОВАННЫХ ВОЗМОЖНОСТЕЙ И ЗНАЧЕНИЙ DON’T CARE
ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА
Рассматриваются вопросы верификации вычислительных процессов по графоаналитическим моделям, управляемых частично-определенными булевыми функциями. Исследуются задачи поиска по булеву графу управления и кубическим покрытиям недекларированных возможностей и мертвого кода как следствия значения don’t care. Приведены примеры построения покрытий для булева графа и верификации значений don’t care в виде покрытия конъюнкции отношений-неравенств, тождественно равных нулю.
Ключевые слова: вычислительный процесс, недекларированные возможности, мертвый код, графоаналитическая модель.
Введение. Определим вычислительный процесс как процесс преобразования информации по формулам и алгоритмам, позволяющим вычислять значения некоторого множества переменных. Вычисление значений переменных по разным формулам и алгоритмам осуществляется в соответствии с множеством отношений-неравенств, которыми задаются условия-предикаты. Каждое отношение может либо выполняться, либо не выполняться, т.е. принимать два значения: true и false (верное и ложное), и, следовательно, образует предикат на множестве значений переменных, входящих в левую и правую части неравенств. Для описания вычислительного процесса, порождаемого логической схемой или программой, необходимо построить модель, которая позволит формализовать его описание и упростить решение различных задач синтеза и анализа с применением аппарата теории множеств и алгебры логики. В качестве такой модели удобно использовать графоаналитическое представление вычислительного процесса [1]. В вершинах графа располагаются итеративные и рекуррентные формулы и условия-предикаты (отношения). Связи между вершинами задаются дугами. В общем случае в вершине может размещаться любой алгоритм преобразования информации. Дуги управления образуют конъюнкции условий-предикатов, их дизъюнкции образуют булевы функции. Основная задача исследования вычислительного процесса (ВП) — его верификация в соответствии с декларацией — заключается в верификации декларированных и недекларированных возможностей ВП и в поиске несуществующих значений don’t care (от англ. — букв.: „все равно“, „не заботит“).
Таким образом, задача верификации вычислительного процесса может быть сведена к поиску недекларированных возможностей (НДВ) и конъюнкций условий-предикатов, тождественно равных нулю, для которых системы неравенств не имеют решений. НДВ на графе вычислительного процесса образуют множество вершин и дуг, недостижимых через последовательности входных наборов, построенных в соответствии с декларацией и значением don’t care, которые порождают частично-определенные булевы функции. Эти функции при их отображении на n-мерный двоичный куб Еn2 могут быть заданы покрытиями комплексов K1( f ) , где f=1, K 0 ( f ) , где f=0, и K d ( f ) , где f=d (don’t care). Поиск и верификация вершин комплекса K ( f ) и составляет основную задачу анализа вычислительных процессов.
Графоаналитическая модель вычислительного процесса. Информационные потоки в вычислительных процессах управляются некоторым множеством условий-предикатов в виде отношений-неравенств. Неравенства могут выполняться, порождая предикат P, равный T, или
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
Метод обнаружения недекларированных возможностей и значений don’t care ВП
33
не выполняться, порождая предикат F. Формула понимается как конечная последовательность переменных и знаков математических операций между ними, т.е. как линейная формула FR. Значение, вычисленное по формуле FR, будем обозначать как |FR|. Алгоритм понимается как некоторая конечная последовательность элементарных действий, приводящих к однозначному результату — значению переменной. Обобщением формулы или алгоритма является некоторый оператор S, имеющий одну точку входа (Тin) и одну точку выхода (Tout).
Представление и описание вычислительного процесса в виде графа — это некоторая не зависящая от конкретной реализации метамодель, например, в виде логической схемы или программы на алгоритмическом языке.
Для описания вычислительного процесса введем три типа вершин [2]: 1) линейные — для формул и операторов; 2) условные — для отношений-неравенств; 3) объединения связей между линейными и условными вершинами. Связи между вершинами являются однонаправленными, т.е. всегда имеется источник и приемник передачи управления: таким образом, информационные потоки в виде последовательности вершин и дуг являются направленными и детерминированными. Аналитическое описание вершин может быть задано как в виде логико-алгебраических выражений, сочетающих в себе логику условий-предикатов и алгебраические формулы вычисления переменных, так и в виде кубических покрытий [3].
Далее вычислительный процесс может быть фрагментирован на замкнутые параллельные структуры (SR), реализующие альтернативные вычисления переменных r или разных переменных по различным формулам в зависимости от заданного множества условий-предикатов. Условияпредикаты могут задаваться либо непосредственно булевыми переменными, либо косвенно через отношения-неравенства. Некоторое множество вершин и дуг графа вычислительного процесса образует параллельную структуру, если оно содержит одну точку Тin и одну точку Tout. Для каждой структуры SR все разветвления по условиям должны сходиться в одной точке Tout. На алгоритмическом языке высокого уровня им соответствуют условные операторы.
Любая булева функция f, входящая в параллельную структуру SR, является полностью заданной, т.е. образует комплекс K(f)=K1(f)∪Kd(f)∪K0(f). Другими словами, если в структуре SR содержится n условий, то любая булева функция f из SR может быть отображена на кубе
Еn2 множествами вершин K, таких что K1 ∪ K 0 ∪ K d = Еn2 . Здесь d (don’t care) — такие вер-
шины куба Еn2 , в которых значение функции не определено вследствие того, что конъюнкции
условий-предикатов дают пустые пересечения множеств значений переменных, входящих в отношения-неравенства, т.е. система неравенств не имеет решения.
Параллельные структуры SR могут находиться между собой в следующих отношениях: — включение, когда некоторая структура SRj содержит в себе некоторую структуру SRi (SRj ⊃ SRi); — конъюнкция — SRj&SRi, т.е. последовательная композиция; — дизъюнкция — SRj ∨SRi, т.е. параллельная композиция. Вследствие того, что любая структура SR является замкнутой, покрытия входящих в нее булевых функций можно (и нужно) строить независимо друг от друга, полагая, что условияпредикаты локализованы в ней, чем и достигается компактность покрытий. Таким образом, при построении покрытий для некоторой структуры SR другие структуры графа вычислительного процесса могут рассматриваться как некоторые нераскрываемые операторы S, что соответствует реализации вычислительного процесса, описанного на языке высокого уровня, в виде блоков и модулей. На рис. 1 показан пример параллельной структуры, реализующей итеративную формулу
(при k1 < k2 ):
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
34 О. Ф. Немолочнов, А. Г. Зыков, В. С. Кулагин и др.
⎧IFR1 при x < k1; r = ⎨⎪IFR2 при k1 ≤ x ≤ k2 ,
⎪⎩IFR3 при x > k2. На рис. 1 обозначение а соответствует отношению xk2, тогда a : x ≥ k1 и b : x ≤ k2 . Остальные использованные на рис. 1 обозначения соответствуют принятым в работе [2].
zin
a: CV1 x < k1
z′1Т= z1Т
LV3 r := z′3
z′1F= z1F
b: CV2 x < k2
z′2F= z2F
LV4
D3 UD6
z′2Т= z2Т
r := D4 z′4 D5
D6=D3∪D4∪D5
LV5
r := z′5
z′out
Рис. 1
Выражение для r на языке высокого уровня может быть записано условным оператором присваивания:
r:= если (xk2), то ,
иначе . Вычисления покрытия для переменной r сведены в табл. 1, где приведены исходные покрытия для всех вершин графа в соответствии с типовыми покрытиями и принятыми в работе [2] обозначениями.
Таблица 1
zin а b r r′ z1′T z1′F z2′T z2′F z3′ z4′ z5′ zo′ut Примечание
100 010
001
1 С1 ⎫
1 1
С2 С3
⎪⎪ ⎬ ⎪
С
(U D 6
)
0 0 0 0 С 4 ⎭⎪
× 1
××
0
1 0
× ××
1 0
1 0
1 0
× ××
11 00
1 0
0 101 1 110
× 000
10 11
01 10
0×
00
С5 С6
⎫ ⎬ ⎭
С
( LV3
)
С7 С8
⎫ ⎬ ⎭
С ( LV5
)
С9 С10
⎫ ⎬ ⎭
С ( LV4
)
С11 С12
⎫ ⎪ ⎬
С
(CV2
)
C13 ⎪⎭
С14 С15
⎫ ⎪ ⎬
С (CV1
)
C16 ⎭⎪
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
Метод обнаружения недекларированных возможностей и значений don’t care ВП
35
В табл. 2 приведены пересечения кубов, имеющих непустое значение. Вычисления про-
изводились от выхода z′out ко входу zin и свелись фактически к перебору четырех кубов из по-
крытия C(UD6).
Таблица 2
zin а b r r′ z1′T z1′F z2′T z2′F z3′ z4′ z5′ zo′ut
Примечание
1 1 × × 1
0
0
0 100
1 C1∩ C5∩ C15∩ C8∩ C10
1 0 0 × 0
1
0
1 010
1 C3∩ C7∩ C11∩ C6∩ C10
1 0 1 × 0
1
1
0 001
1 C2∩ C9∩ C12∩ C6∩ C8
0 × ××
×
0 0 0 0 000 0
C4∩ C6∩ C8∩ C10
Удалив из покрытия промежуточные значения z′, получим покрытие C(r) в формате zin a b r r′ z′out:
⎧
C(r)=
⎪⎪ ⎨
⎪
⎪⎩
zin a b r
r′ z′out
1 1 × × 1 ⎫
1 0 0 × 1 1 0 1 × 1
⎪⎪ ⎬
.
⎪
0×××
×
0 ⎭⎪
Структура этого покрытия соответствует структуре покрытий для типовых вершин и описывает режим вычисления переменной r по различным итеративным формулам и режим хранения: r=×.
Поиск и верификация недекларированных возможностей. Недекларированные возможности — функциональные возможности программного обеспечения (ПО), не описанные или не соответствующие описанным в документации. Реализацией недекларированных возможностей являются, в частности, программные закладки.
Программные закладки — преднамеренно внесенные в ПО функциональные объекты, которые при определенных условиях (входных данных) инициируют выполнение не описанных в документации функций ПО, приводящих к нарушению конфиденциальности, доступности или целостности обрабатываемой информации [4].
Определим недекларированные возможности в общем виде как все не описанные в декларации особенности и возможности вычислительного процесса, порождаемого программой в ходе ее исполнения. Природа НДВ носит как объективный, так и субъективный характер в силу сложности и размерности самого программного продукта. Однако для НДВ можно выделить в общих чертах следующие основные источники и составляющие:
— наличие в программном продукте специально предусмотренных закладок для наблюдения и отладки ВП в ходе его проектирования и эксплуатации;
— „замалчивание“ излишне мелких подробностей ВП при составлении декларации вследствие стремления к ее компактности;
— наличие в частично определенных булевых функциях f управления ВП неопределенных значений d в виде комплекса Kd(f), который объективно существует, но, как правило, не используется и не описывается.
Поиск и верификацию НДВ ВП можно осуществить путем моделирования процесса либо в виде исполнения программы, либо — на более высоком уровне — по графоаналитической модели.
Моделирование ВП проводится на испытательных наборах входных переменных, построенных по его декларации путем прямого исполнения программы в ходе тестовых экспериментов. При этом необходимо фиксировать вершины и дуги графа, которые достижимы из точки Tin, вычисляются и наблюдаются в точке Tout исследуемой программы.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
36 О. Ф. Немолочнов, А. Г. Зыков, В. С. Кулагин и др.
О п р е д е л е н и е . Если множество вершин и дуг графоаналитической модели вычислительного процесса недостижимы в результате тестовых экспериментов, построенных по декларации, то они образуют множество НДВ.
Множество задействованных вершин и дуг графа образуют декларированные возможности (ДВ) ВП и соответственно программы, его реализующей. Таким образом, все множество вершин и дуг M(V, D) распадается на два подмножества MДВ и MНДВ: M(V, D)=MДВ∪ MНДВ. Указанные подмножества можно построить путем моделирования константных „неисправностей“ для условий-предикатов (m1≡ 1(T) и m0≡ 0(F)) непосредственным внесением их либо в программу [5], либо в условные вершины графоаналитической модели ВП при условии, что такая модель построена. С этой целью в ходе тестовых экспериментов производится сравнение результатов вычислений без „неисправностей“ и с заданной „неисправностью“ m p∈ N, где N — все множество условий-предикатов. Условие-предикат может быть полностью не проверено или проверено только в одном из значений T или F. В этом смысле множество непроверяемых „неисправностей“ и образует множество вершин и дуг НДВ.
Поиск и верификация значений don’t care. Для любой булевой функции f от n переменных область определения состоит из 2n их значений, задающих канонические формы f. Это множество значений может быть сопоставлено с вершинами n-мерного двоичного куба Еn2 , для упрощения логических выражений можно применять исчисление кубических комплексов путем построения неизбыточных покрытий в виде дизъюнктивных нормальных форм (простых импликант) или в виде скобочных форм (полученных методом функциональной декомпозиции). Первый способ применяется при реализации ВП в виде логических схем, а второй — в виде программного продукта.
В случае частично-определенных булевых функций область определения из 2n значений разбивается на два подмножества M1 и M d: M1 ∪ M d= Еn2 и M1 ∩ M d= ∅ . Множество M1 состоит из конъюнкций аргументов, на которых функция принимает значение, равное единице, а множество M d состоит из конъюнкций, тождественно равных нулю. Значения функции f на конъюнкциях из множества M d принято обозначать как d — don’t care: т.е. все равно какое значение имеет функция f, оно может быть произвольно присоединено к любой функции управления z, построенной на множестве M1.
В случае если булевы переменные задаются в виде отношений-неравенств, то значениям d соответствуют системы неравенств, для которых отсутствуют решения, и, следовательно, множество отношений между переменными, входящими в левую и правую части неравенств, дают пустое пересечение.
Итак, определим множество конъюнкций don’t care как множество конъюнкций, тождественно равных нулю. Поиск таких конъюнкций может быть осуществлен либо путем непосредственного решения систем неравенств в аналитической форме, либо методом моделирования отношений на числовой оси в виде линий Ламберта или непосредственным заданием множеств на плоскости в виде диаграмм Эйлера — Венна [6].
Верификация значения don’t care состоит в построении покрытий С1 для M1 и Сd для M d, которые позволяют производить поиск значения don’t care в сокращенной форме для подмножеств из M d и, следовательно, сократить перебор вариантов при решении систем отношений-неравенств.
Рассмотрим описанные выше положения на примере. Пусть на числовых осях x и y заданы четыре отношения:
α: x < 4, β: x > 5, γ: y < 3, ζ: y > 6 .
Здесь отношения α и β не зависят от значений γ и ζ, поэтому поиск значения don’t care можно произвести раздельно.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
Метод обнаружения недекларированных возможностей и значений don’t care ВП
37
Итак, если x5, то эта система неравенств не имеет решения: на числовой оси х
невозможно найти значения х, удовлетворяющие конъюнкции α=β=1, т.е. αβ ≡ 0, что и является значением don’t care. Аналогично конъюнкция γ=ζ=1 также не имеет решения, и тождество γζ ≡ 0 образует значение don’t care для y6.
Покрытие множества Md относительно множества отношений {α,β,γ,ζ} компактно можно записать в виде двух кубов:
αβ γ ζ
Сd
=
⎧ ⎨
⎩
11 ×× ×× 11
⎫ ⎬
.
⎭
Аналогично можно для верификации значения don’t care построить покрытие множест-
ва M1 в виде четырех кубов:
С1
=
⎧ ⎨
⎩
αβγ ζ
×0×0 0 ×0× ×00× 0 ××0
⎫⎬. ⎭
Заметим, что С1 ∪ Сd= Еn2 и С1 ∩ Сd= ∅ : это и свидетельствует о рассмотрении всех
конъюнкций для отношений {α,β,γ,ζ}. Рассмотренные решения проиллюстрированы на рис. 2. На рис. 2, а показаны отноше-
ния {α,β,γ,ζ} в системе координат x y: видно, что число существующих решений для системы неравенств равно 9, а 7 отношений решений не имеют. На рис. 2, б показана развертка куба
Еn2 в виде карты Карно: 1 — вершины множества M1, d — множества Md.
а) б)
у αβ γζ 00 01 11 10
345 6
00 1 1 d 1
296
3
187
01 1 1 d 1 11 d d d d
45
х
10 1 1 d 1
(x5)
и (y6)
С1 ∪ Сd= Еn2 и С1 ∩ Сd= ∅
Рис. 2
Как следует из рассмотренного примера, задача поиска и верификации значения don’t
care заключается в переборе всех вариантов решений, этот перебор может быть сокращен,
если решения искать сразу в кубической форме.
Мертвый код как следствие значения don’t care. Определим понятие мертвого кода (МК) как множества команд программы, которые не могут быть исполнены ни при каких значениях конъюнкций условий-предикатов. Это может быть только в том случае, если данные конъюнкции тождественно равны нулю. Такие конъюнкции и образуют множества значений don’t care и порождают частично-определенные булевы функции. Если функции запрограм-
мированы в явном виде, то операторы, заданные в программе только через них, никогда не будут исполняться. Иными словами, мертвый код всегда есть следствие значения don’t care.
Такие конъюнкции могут быть заданы на уровне булевых переменных в виде явных
тавтологий, например, a ∨ a , aa или в виде избыточных выражений, например, a∨ab, a∨ ab
и т.п. Указанная избыточность может быть следствием ошибок при программировании
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
38 О. Ф. Немолочнов, А. Г. Зыков, В. С. Кулагин и др.
условий, например при настройке стандартных шаблонов, и если это ошибка, а не умысел, то она должна быть устранена путем минимизации логических выражений. Заметим, что для настраиваемых шаблонов значение don’t care может быть только вычислено и указано, в противном случае теряется сам смысл шаблонов как стандартного и апробированного решения.
Если же значение don’t care запрограммировано сознательно в виде артефакта, то порождаемые операторы образуют закладки. Эти закладки не могут быть обнаружены в ходе тестовых экспериментов по полной декларации, содержащей декларированные и недекларированные возможности программы. В этом и состоит принципиальное различие между мертвым кодом и НДВ.
Мертвый код может быть в неявном виде задан при программировании отношенийнеравенств, в этом случае необходимо осуществлять поиск значения don’t care через решение систем неравенств. Для простоты рассмотрения приведем примеры мертвого кода в виде условных выражений над булевыми переменными. Пусть заданы условные выражения, реализующие операторы S1 и S2, которые могут быть операторами присваивания, перехода, обращения к процедурам либо в общем случае любыми составными операторами, модулями или блоками. Итак, пусть заданы два условных выражения:
если ( aa ), то S1, иначе S2, если ( a ∨ a ), то S1, иначе S2.
В первом выражении оператор S1 никогда не будет исполняться, а во втором не будет исполняться оператор S2. Операторы S1 и S2 в данном контексте могут рассматриваться как специально сделанные закладки. Конъюнкции, тождественно равные нулю, показаны на
рис. 3, а, б в виде функций управления zi на булевых графах, реализующих приведенные выше условные выражения соответственно.
a) zi
б) zi
CV1 a:
T
CV1 a: F
T z1 S1
F z1
CV2 a: F z2
T
z3≡0 S1
CV2 a: F z3≡0
T z2
S2 S2
f=aa f=a∨a
Рис. 3
Заключение. Наличие в вычислительном процессе, порождаемом программой при ин-
терпретации ее команд процессором, недекларированных возможностей или мертвого кода
несет в себе явную (НДВ) или неявную (МК) угрозу безопасности программному продукту.
Эта угроза может быть реализована, например, в виде компьютерного вируса. Поэтому поиск
и верификация НДВ и МК является основной задачей в области защиты информации. Реше-
ние этой задачи конструктивно может быть найдено путем построения графоаналитической
модели или, в частном случае, построением булева графа для функции управления вычисли-
тельным процессом. Для сокращения размерности задачи поиска НДВ и МК вычислительный
процесс на графоаналитической модели следует разбивать на параллельные структуры. Такое
разбиение позволяет локализовать поиск и верификацию НДВ и МК в рамках отдельно взя-
той параллельной структуры и не рассматривать все множество реализованных в программе
условий-предикатов совместно.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12
Метод обнаружения недекларированных возможностей и значений don’t care ВП
39
СПИСОК ЛИТЕРАТУРЫ
1. Немолочнов О. Ф., Зыков А. Г., Поляков В. И. Комплексные кубические покрытия и графоаналитические модели как средство описания вычислительных процессов программ // Тр. Междунар. науч.-техн. конф. „Интеллектуальные системы“ (AIS’06) и „Интеллектуальные САПР“ (CAD-2006). М.: Физматлит, 2006. Т. 2. С. 3—7.
2. Модель и примитивы вершин циклических вычислительных процессов / О. Ф. Немолочнов, А. Г. Зыков, Л. Г. Осовецкий, В. И. Поляков // Изв. вузов. Приборостроение. 2007. Т. 50, № 8. С. 18—23.
3. Немолочнов О. Ф., Зыков А. Г., Поляков В. И. Кубические покрытия логических условий вычислительных процессов и программ // Науч.-техн. вестн. СПбГУ ИТМО. Информационные технологии, вычислительные и управляющие системы. СПб.: СПбГУ ИТМО, 2004. Вып. 14. С. 225—233.
4. Руководящий документ Гостехкомиссии России „Защита от несанкционированного доступа к информации. Ч. 1. Программное обеспечение средств защиты информации. Классификация по уровню контроля отсутствия недекларированных возможностей“. Введ. 04.06.1999 г.
5. Тестирование логических неисправностей вычислительных процессов в программах / О. Ф. Немолочнов, А. Г. Зыков, Л. Г. Осовецкий и др. // Информ. технологии. 2007. № 12. С. 2—5.
6. Кондаков Н. И. Логический словарь. М.: Наука, 1971.
Олег Фомич Немолочнов Анатолий Геннадьевич Зыков
Вячеслав Сергеевич Кулагин Леонид Георгиевич Осовецкий Владимир Иванович Поляков
Андрей Вячеславович Суханов
Сведения об авторах — д-р техн. наук, профессор; Санкт-Петербургский государственный
университет информационных технологий, механики и оптики, кафедра информатики и прикладной математики — канд. техн. наук, доцент; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра информатики и прикладной математики; E-mail: zykov_a_g@mail.ru — канд. техн. наук, доцент; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра электроники — д-р техн. наук, профессор; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра безопасных информационных технологий — канд. техн. наук, доцент; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра вычислительной техники; E-mail: v_i_polyakov@mail.ru — канд. техн. наук, доцент; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра безопасных информационных технологий
Рекомендована кафедрой информатики и прикладной математики
Поступила в редакцию 06.06.09 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 12