Программирование средства внедрения и анализа водяных знаков в исходные тексты программ

      Кроме математических подходов к защите ПО существует еще множество технических подходов, усложняющих взломщику задачу. Так, широко распространенным является применение защиты от отладки – комплекса мер, направленных на обнаружение факта запуска программы «внутри» отладчика, и аварийное завершение ее работы в случае, если отладчик будет обнаружен. [3] 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2. Методы  внедрения водяных  знаков
1. Исследование статистических свойств исполняемого кода

      Практически любое ПО (далее для простоты "программа") состоит из двух основных составляющих — внутренних данных (расположенных  в сегментах данных) и исполняемого кода. Природа внутренних данных программы  и их статистические свойства сильно зависят от функций программы  и реализованных в ней алгоритмов. Для исполняемого кода программы  проявляется ряд закономерностей, сохраняющихся от программы к  программе. Эти закономер-ности обусловлены  тем, что исполняемый код приложения представляет собой последовательность из определенного ограниченного  множества машинных инструкций. Причем порядок следования большинства  из них, а так же частоты использования  как отдельных машинных команд, так  и определенных конструкций, образованных двумя и более командами, определяется такими параметрами, как архитектура  среды выполнения, синтаксическая корректность, требования к эффективности. По этой причине сегмент кода каждого  приложения обладает рядом статистических характеристик, сохраняющихся от программы  к программе и практически  не зависящих от реализованной в  ней функциональности. К ним можно  отнести такие пара-метры, как  вероятность появления той или  иной инструкции, вероятность появления  определенной инструкции в указанной  точке программы, вероятность следования рассматриваемой инструкции за некоторой  другой, среднее расстояние между  повторяющимися инструкциями в программе  и др. Например, как видно на рисунке 7, среднее значение номера команды, использованной в программе (M(x)), практически не зависит от самой программы и ее длины. [4]

     Измерения проводились для более чем 20 программных  модулей (.exe, .dll) прикладного и системного назначения. Исследуемая закономерность наблюдается и при осуществлении  вы-числения величины M(x) не для всех команд модуля (N), а для некоторого выбранного случайно их подмножества из L команд. На рисунке 8 приведены аналогичные зависимости для L=N, L=N/10 и L=N/100. Из полученных результатов можно сделать вывод о том, что и при осуществлении выборки подмножества команд из программы величина параметра M(х) не выходит за пределы определенного интервала значений, и, как показали эксперименты, для L=N/100 M(х) находится в интервале (55, 95).

     Рисунок 7 – Зависимость М(х) от числа команд в модуле 

     Рисунок 8 – Зависимость M(x) от количества команд в модуле при выборках 100, 10 и 1% 

     Еще одной статистической характеристикой  исполняемого кода является среднее  расстояние между одинаковыми командами. Данный параметр характеризуется функцией S(k), значения которой равняются количеству совпавших команд в оригинальной программе P и программе P’, являющейся циклически сдвинутой на k позиций P. Под совпавшими командами понимаются стоящие на одной и той же позиции в P и P’ одинаковые команды. На рисунке 8 показана полученная экспериментально зависимость числа совпадений команд S(k) от величины сдвига k для значений k в интервале 1–100. 
 

     

     Рисунок 8 – Экспериментальная зависимость S(k) 

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

     Значение  рассмотренного параметра может  служить одной из статистических характеристик программы, которая  не зависит от ее содержания, поскольку, как показали результаты экспериментов, начиная с некоторого значения k (порядка 2000 и выше) значение величины S(k) не выходит за пределы определенного интервала, на границы которого оказывают лишь незначительное влияние реализованные в программе алгоритмы. 

2. Предлагаемые  методы внедрения  водяных знаков

 

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

      Изменение значения среднего номера встреченной команды. Аналогичным образом можно воздействовать не только на частоту встречаемости одной команды, но и нескольких команд, и в этом случае параметром, резкое отклонение в значении которого от стандартного будет говорить о наличии в программе водяного знака, будет средний номер выбранной из программы ассемблерной команды М_х. Для того чтобы программа не только обладала рассматриваемым признаком, но и его наличие нельзя было обнаружить, не располагая некоторыми секретными данными, например, ключом, можно поступить следующим образом. Известно, что значение такого параметра, как М_х, располагается в некотором интервале, границы которого фиксированы, что было подтверждено экспериментально (рисунок 7). Таким образом, изменение величины данного параметра в пределах этого интервала не окажет существенного влияния на частотные характеристики кода. Пусть программа P состоит из N ассемблерных команд. Исходя из результатов проведенных экспериментов, можно сделать предположение о том, что для любой программы для любых случайно выбранных из нее L (L<N) команд величина такого параметра M_x также будет заключена в определенном интервале (см. рисунок 8). Можно подобрать такой вид воздействия теперь уже не на всю программу, а на выбранные из нее L команд, кото-рый приведет к отклонению рассматриваемого параметра далеко за пределы интервала его возможных значений в большую или меньшую сторону, не приводящих, однако, к выходу аналогичного параметра для всей программы за границы экспериментально определенного интервала.

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

Сдвиг распределения разностей  номеров двух последовательно  выбранных команд. Рассмотрим еще одно свойство исполняемого кода, которое может быть использовано для внедрения в программу скрытого признака. Если некоторая случайная величина (СВ) x распределена равномерно, то в соответствии с центральной предельной теоремой величина

                                                         (1)

где x_i — равномерно распределенная случайная величина, n — количество суммируемых значений, обладает нормальным распределением. В случае если СВ x распределена равномерно в интервале от –D до D, то математическое ожидание (MO) СВ у будет равным 0.

      Если  же равномерно распределенная СВ распределена в интервале от 0 до B, то после-довательность значений

,                                                   (2)

будет также обладать нормальным распределением с МО M()=0.

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

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

Рисунок 9 - Распределение частот встречаемости групп содержащих переменное число команд

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

      Пусть S={S₁, S₂, ..., S_m} - двоичная последовательность, которой представлен водяной знак.

      Необходимо  разместить последовательность S в теле программы P таким образом, что бы:

      а) модифицированная программа P', содержащая S, имела такое же наблюдаемое пове-дение, что и P;

      б) последовательность S невозможно было извлечь, не располагая некоторым секрет-ным ключем A₀;

      в) способ размещения S в Р определяется значением ключа A₀ и использует некоторое его свойство, исключающее возможность случайного появления S в теле программы.

      Внедрение признака авторства  путем внесения изменений  в автокорреляционную характеристику. Как уже отмечалось выше, автокорреляционная зависимость программы обладает свойством, заключающимся в том, что процент совпадений в оригинальной P и циклически сдвинутой программе P’ начиная с некоторого значения сдвига становится постоянным, очень несущественно меняющимся от программы к программе. Эксперименты показали, что для всего множества исследованных программ значения параметра S(k) (количество совпадений при сдвиге на k позиций) не выходили за пределы интервала от 12 до 22% для сдвигов на число позиций, равное 100 и более. Отклонения в виде данной автокорреляционной функции от ее стандартного вида могут быть использованы в качестве средства, подтверждающего наличие водяного знака. Например, можно преобразовать программу таким образом, что для некоторых значений величины сдвига k количество совпадающих команд будет существенно ниже либо выше стандартного. Идея использования данной характеристики исполняемого кода может быть применена для внедрения водяного знака.

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

3. Оценка  эффективности подстановок

 

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

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

Для каждого  модуля проводилась оценка следующих величин:

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

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

Общее число команд в программе (Ntotal) может быть определено по формуле

Ntotal = Nrepl + Nconst ,

где Nconst – количество инструкций, которые не могут быть заменены на эквивалентные. В свою очередь,

Nrepl = Nsym + Ndissym ,

где Ndissym – количество инструкций, допускающих эквивалентную замену, однако только с использованием так называемых «несимметричных» правил подстановки.

Для более  наглядного представления полученных результатов (рис. 1) рассматриваются следующие величины:

Sym – процент инструкций, допускающих применение к ним симметричных правил подстановки, определяемый как Nsym / Ntotal ⋅ 100%;

     Repl – процент всех заменяемых инструкций, определяемый как Nrepl / Ntotal ⋅ 100%.