ЛАБОРАТОРНАЯ РАБОТА N8

 

ИДЕНТИФИКАЦИЯ ПРОГРАММ

 

ЦЕЛЬ:изучить способы идентификации программ.

 

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

 

Цель процедур идентификации программ и программных модулей -выявить явные признаки нарушения авторского права.

Ниже описаны четыре способа идентификации программ:

-анализ характеристик программы;

-анализ стиля программирования;

-анализ идентификационных меток;

-анализ программных процедур.

 

1. АНАЛИЗ ХАРАКТЕРИСТИК ПРОГРАММЫ.

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

Хорошо известны следующие характеристики и способы анализа последовательности данных: 1) контрольная сумма, 2) продольный контроль и 3) контроль по четности. Для установления подлинности можно рассмотреть и более сложные характеристики, которые позволяют выявить изменения данных, вызванные, например, ошибками передачи по линии связи. Сами по себе эти характеристики мало пригодны для идентификации данных, которые были искажены преднамеренно и для которых характерны отклонения, существенно превышающие погрешности, возникающие из-за случайных возмущений. Фактически для идентификации программ необходимо выявлять те следы подобия, которые остаются после преднамеренных искажений. Представляют интерес способы сравнения различных программ для выявления степени заимствования (плагиата), достаточной, чтобы сделать вывод о нарушении авторского права или по крайней мере целесообразности проведения более детальных исследований. Существует много таких подходов. Ценность программы заключается в действиях, которые могут быть выполнены с ее помощью. Наиболее характерные параметры программы могут быть легко изменены или модифицированы осторожным злоумышленником без изменения функций, выполняемых программой, и для этого не требуется большого умения программировать. В любом случае все эти изменения будут либо проигнорированы, либо преобразованы в иную форму при компиляции программы. Программный модуль при компиляции размещается в памяти по адресам, которые являются функцией местоположения модуля в программе, так что машинный код будет иметь существенно различную меру прямой корреляции.

При установлении степени подобия программ можно выбрать различные критерии.

 

1.1. Гистограммы появления операторов в программе.

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

Визуальное восприятие гистограммы можно выразить математически, используя понятие корреляции. Простую меру оценки подобия можно получить, подсчитывая для каждого оператора с номером n среднее значение частоты его появления S[n]/2 в обеих программах и вычитая разность частот его появления D[n] в каждой программе. Математически эта мера подобия adeq[n] для одного оператора записывается в виде

adeq[n]=S[n]/2-D[n]=(f1[n]+f2[n])/2-¦f1[n]-f2[n]¦,

где f1[n],f2[n]-частоты появления оператора с номером n соответственно в программах 1 и 2;

S[n]-средняя сумма частот появления оператора с номером n в обеих программах;

D[n]-разность между частотами появления оператора с номером n в программах 1 и 2.

Мера по всей последовательности операторов получается путем суммирования по всем операторам и нормировки (чтобы снять зависимость от длины программы, сумму делят на полное число операторов в обеих программах).Такая мера подобия adeq(1,2) для программ 1,2 имеет вид

adeq(1,2)=E(S[n]-2D[n])/ES[n],

где N-число операторов в языке.

Если частота появления операторов в обеих программах одинакова, мера адекватности adeq(1,2)=1; если операторы, присутствующие в программах, образуют пересекающиеся множества, adeq(1,2)=-1.

Статистическая формула для корреляции имеет вид

corr(1,2)=E(f1[n]-f1)(f2[n]-f2)/[E(f1[n]-f1)^2E(f2[n]-f2)^2]^1/2^

где f1,f2- средние значения частот появления всех команд в программах 1 и 2 соответственно.

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

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

 

1.2. Простая взаимная корреляция.

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

Пусть последовательность операторов seq1 имеет длину L1, а последовательность seq2-длину L2, причем L1>L2.Допустим, что последовательность seq2 сдвинута на n элементов по отношению к последовательности seq1, так что k-й элемент последовательности seq2 сравнивается с (n+k)=м элементом последовательности seq1. Если n+k>L1, то k:=k-L1.

Обозначим через S[n] число совпадений элементов при заданном n, тогда для подсчета этой суммы можно использовать следующий рекуррентный алгоритм:

sum(n):=0

for n=1 to L1

sum(n):=sum(n)+1

next n

Sn:=sum(n)

Соответствующая сумма S[n] отображается на графике. Затем одна из последовательностей смещается на один элемент, и процедура продолжается по всей длине последовательности наибольшей длины. Ожидается, что две программы, имеющие общий модуль, будут иметь число совпадений, равное длине модуля, когда модули совместятся.

 

1.3. Взвешенная взаимная корреляция.

Прямая корреляция между элементами множества не является оптимальной мерой, поскольку фоновая корреляция, обусловленная случайностью, может оказаться очень высокой, и поэтому необходимо переходить от анализа отдельных элементов к группам элементов. Улучшенную корреляцию можно получить, если рассматривать группы. Поэтому при поиске в некоторой последовательности операторов совпадающих элементов следует проверять, является ли следующий элемент совпадающим, и если это так, то совпадение фиксируется и этот процесс продолжается до окончания сравниваемой последовательности. Если последовательность имеет длину n, объем выборки, отнесенный к первому элементу, увеличивается с 1 до n. Расчет корреляции продолжается путем перехода к следующему элементу последовательности. В этом случае соответствующая выборка увеличивается с 2 до n-1. Таким образом, общий объем выборки, используемый для расчета корреляции и порожденный данной последовательностью, становится равным

V[n]=Ei=n(n+1)/2, i=(1,...,n)

в то время как начальный объем был равен всего лишь n.

Коэффициент значимости длины последовательности по отношению к фоновому значению случайной корреляции определяется отношением

k[n]=V[n]/n=(n+1)/2.

Коэффициент значимости может возрасти, если кроме поэлементных совпадений учитывать попарные, и тогда коэффициент значимости k[n] станет больше. Поскольку попарное совпадение, хотя и в меньшей степени, может также быть случайным, можно перейти к анализу групп из трех и более элементов.

 

1.4. Автокорреляция.

Автокорреляционная функция является результатом анализа корреляции внутри самой программы. Для такого анализа достаточно воспользоваться подпрограммами для определения взаимных корреляций, если в качестве двух тестовых использовать одну и ту же последовательность. Автокорреляция представляет значительный интерес, поскольку дает числовую характеристику программы. Автокорреляционная функция представлена в виде гистограммы (см.стр.153 книги 1).

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

 

2.ДОСТОВЕРНОСТЬ ИДЕНТИФИКАЦИИ.

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

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

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

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

 

3.АНАЛИЗ СТИЛЯ ПРОГРАММИРОВАНИЯ.

Рассматривая стиль программирования с позиций защиты, часто употребляется термин "родимые пятна".

Воспроизведение ошибки рассматривается как доказательство несанкционированного копирования. Однако следует отметить, что некоторые логические ошибки могут быть присущи разным людям. Если ошибка очевидна, то невероятно, чтобы другие могли повторить ее.

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

 

4.АНАЛИЗ ИДЕНТИФИКАЦИОННЫХ МЕТОК.

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

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

 

4.1.Кодирование идентификационных меток.

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

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

 

4.2.Встроенные метки.

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

 

5.АНАЛИЗ ПРОГРАММНЫХ ПРОЦЕДУР.

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

 

ПРИМЕР РЕАЛИЗАЦИИ

 

В качестве примера применения идентификационных меток рассмотрим программу, где слово carder закодировано 10 различными спо собами.

1 REM Программа позволяет ввести,сформировать,откорректировать и

2 REM отсортировать произвольный массив строк

'3 format "b"

'2400:open #5 "b":format "t"

'2400:Open #3;"t":dim a$(90,45)

4 DATA 10,30,35,40,45,50,55,60,65,70,75,80,85,95,100,105,110

9 DATA 15,5,90,20,25,90,67,65,82,68,69,82,71,82,79,86,69,82

11 READ b,f,g,h,j,k,l,m,n,o,p,q,r,s,t,u,v,c,a,r,d,e,r:GOTO 300

25 CLS : na = na + 1

PRINT na: a$(na, 3) = "0"

30 INPUT "Укажите номер строки:"; b$: IF c < 3 THEN d = 67

35 IF b$ = "" THEN GOTO 50

45 GOTO 55: DIM f$(3, 1)

50 a$(na, 2) = a$(na - 1, 2)

55 INPUT " и позицию символа:"; b$: IF b$ = " " THEN GOTO 65

60 a$(na, 1) = b$: GOTO 70

65 a$(na, 1) = a$(na - 1, 1): IF a < 1 THEN j = 65

70 INPUT "укажите данные для записи"; b$

75 IF b$ = "" THEN a$(na, 5) = a$(na - 1, 5): ln = 1: GOTO 85

80 ln = LEN(b$): 'a$(na,5 to 4+ln)=b$

85 IF ln = 1 THEN GOTO 139

90 a$(na, 4) = CHR$(ln + 64)

95 PRINT at; 20, 1; a$(na, 4): IF r < 18 THEN g = 82

100 INPUT "продолжить-enter"; b$

101 INPUT " ошибка-w"; b$

102 INPUT "повторить-stop"; b$:

IF b$ = "stop" THEN RETURN

104 IF b$ = "w" THEN na = na - 1

114 na = na + 1: GOTO 25

'REDIM f$(18, 14)

121 RETURN

139 INPUT "укажите последнюю строку:"; y$: IF d < 4 THEN d = 68

154 IF y$ = "" THEN a$(na, 4) = a$(na - 1, 4): GOTO 95

176 a$(na, 4) = CHR$(64 + VAL(y$)): GOTO 95

181 DIM p$(6)

FOR z = 1 TO 6

READ w: p$(z) = CHR$(w)

NEXT z: PRINT p$: RETURN

199 w = 0: IF e < 5 THEN j = 69

200 FOR z = 1 TO na - 1

203 a1 = VAL(a$(z + 1, 1)) + 100 * (VAL(a$(z + 1, 2)) + VAL(a$(z + 1, 3)))

204 a2 = VAL(a$(z, 1)) + 100 * (VAL(a$(z, 2)) + VAL(a$(z, 3)))

222 IF a1 >= a2 THEN GOTO 226

225 z$ = a$(z, w): a$(z, w) = a$(z + 1, w): a$(z + 1, w) = z$: w = 1

226 NEXT z: IF w = 1 THEN GOTO 199

231 RETURN

249 IF r < 18 THEN g = 82

300 INPUT "для чтения меню нажми любую клавишу"; y$: CLS

303 PRINT : PRINT "char print out-enter c"

327 PRINT : PRINT "add data-enter a"

344 PRINT : PRINT "replace data-enter r "

356 PRINT : PRINT "to define data-enter d"

357 PRINT : PRINT "if error-enter er "

370 PRINT : PRINT "to stop-enter stop"

375 PRINT : PRINT "to list data on screen-enter l"

385 PRINT : PRINT "set parameters-enter p"

390 PRINT : PRINT "to sort-enter s"

395 PRINT : PRINT "to save data-enter sa"

400 INPUT "Выберите опцию"; y$

401 IF y$ = "c" THEN GOSUB 400

402 IF y$ = "a" THEN GOSUB 400

403 IF y$ = "r" THEN INPUT "номер данных?"; na: GOSUB 25

404 IF y$ = "d" THEN na = na + 1: GOSUB 25

405 IF y$ = "er" THEN GOSUB 25

406 IF y$ = "stop" THEN STOP

407 IF y$ = "l" THEN GOSUB 400

408 IF y$ = "p" THEN GOSUB 460

425 IF y$ = "fp" THEN GOSUB 181

435 IF y$ = "s" THEN GOSUB 200

455 GOTO 300:

'DIM f$(5, 18)

460 INPUT "x1,default 3"; y$: x1 = 3: IF y$ <> " " THEN x1 = VAL(y$)

465 INPUT "na,default 1"; y$: na = 1: IF y$ <> " " THEN na = VAL(y$)

470 INPUT "ly,default 18"; y$: ly = 18: IF y$ <> " " THEN ly = VAL(y$)

475 INPUT "y2,default 4"; y$: y2 = 4: IF y$ <> " " THEN y2 = VAL(y$)

480 INPUT "xl,default 5"; y$: xl = 5: IF y$ <> " " THEN xl = VAL(y$)

485 INPUT "lx,default 18"; y$: lx = 18: IF y$ <> " " THEN lx = VAL(y$)

490 RETURN

 

Работу данной программы можно посмотреть, запустив файл

lab8.exe.

 

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1.Изучить теоретический материал.

2.Разобрать контрольный пример.

3.Разработать программу согласно индивидуальному заданию.

 

ТРЕБОВАНИЯ К ОТЧЕТУ

Отчет должен содержать краткие теоретические сведения в виде от-

ветов на контрольные вопросы,текст программы,результаты рабо-

ты,выводы о проделанной работе.

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.Способы идентификации программ.

2.Анализ характеристик программы.

3.Гистограммы появления операторов в программе.

4.Простая взаимная корреляция.

5.Взвешенная взаимная корреляция.

6.Автокорреляция.

7.Достоверность идентификации.

8.Анализ стиля программирования.

9.Анализ идентификационных меток.

10.Кодирование идентификационных меток.

11.Защита форматов выходных данных.

12.Встроенные метки.

13.Анализ программных процедур.

 

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ

1.Распечатка результатов программы с текстовым сопровождением

об авторе.

2.Распечатка идентификационных меток, введенных в программу.

3.Создание идентификационной метки, расшифровка и распечатка

результата идентификации.

4.Распечатка контрольной суммы программного блока.

5.Анализ частотных характеристик программы

-взаимной корреляции,

-автокорреляции.

 

ЛИТЕРАТУРА

1.Защита программного обеспечения: Пер. с англ./Д.Гроувер, Р.Сатер, Дж.Фипс и др./Под редакцией Д.Гроувера.-М.:Мир,1992.-286 с ил.

2. Защита информации в вычислительных системах. /Сборник.- М.:Знание,1982.

3. Хофман Л.Дж. Современные методы защиты информации.- М.:Советское радио, 1980.

4. Дружинин Г.В.,Сергеева И.В. Качество информации.-М.:Радио и связь, 1990.

5. Зарубежная радиоэлектроника. /ежемесячный н-т журнал/ N12,1989.

6. Безруков Н.Н. Компьютерная вирусология / Справочное руководство/.- К.: УРЕ, 1991.