http://www.viniti.ru

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

ВВЕДЕНИЕ

Каждый знает, что криптография – это способ сокрытия от противника смысла передаваемого сообщения. Факт шифровки сообщения при этом не скрывается, но лишь посвященный знает способ дешифровки. Стеганография, в отличие от криптографии, призвана скрыть от противника сам факт передачи чего-то секретного. Это как писать молоком между строк обычного рукописного сообщения. Посвященному, чтобы прочитать сокрытое, достаточно подержать письмо над огнем, а непосвященный даже не поймет, что у него в руках. Скрытое сообщение может даваться в стеганографии прямым текстом или быть подвергнуто предварительной криптографической обработке, это не имеет значения.

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

Безобидным будем считать текст, не привлекающий внимание внешней стороной – форматом, шрифтом, орфографией, морфологией, синтаксисом или лексикой. Все эти черты должны соотноситься с темой текста и только с ней. Осмысленный текст последовательно излагает что-то отличное от спрятанного сообщения. Естественно,что если при скрытом кодировании семантическая связность несущего текста теряется, то утрачивается и его безобидность. Он становится "подозрительным" именно в стеганографическом плане. Лучше всего, чтобы несущий текст сохранял исходный смысл, не важно какой – глубокий или тривиальный.

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

Более практичные идеи выдвигает собственно лингвистическая стеганография (ЛС). Под ней мы понимаем скрытое кодирование произвольной информации в произвольном несущем тексте с опорой на нетривиальные лингвистические идеи и ресурсы. ЛС молода, но улсе хорошо представлена на международных конференциях по сокрытию информации (Information Hiding) и ее безопасности (Information Security).

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

В пионерных работах [2, 3] выдвинута идея использования для целей Л С словарей (ква-зи)синонимов. Вся лексика данного языка разбивается на множество групп разного объема. Внутри групп слова сходны как грамматически (они принадлежат одной части речи), так и семантически, вплоть до настоящей синонимии. Если очередное слово несущего текста принадлежит группе с т > 1 синонимами, оно может нести скрытую информацию примерно в Iog2(m) бит. Для простоты будем считать, что все группы имеют объемы, равные степеням двойки, т. е. содержат 2" членов, где п = 1, 2, 3..., а слова внутри группы заранее упорядочены номерами г = 0,..., 2n – 1. При стеганографии очередной слог длиной в п бит кодируемого сообщения рассматривается как внутригрупповой номер г-го синонима, который должен заменить в тексте исходное слово. После этого в тексте ищется очередное слово, с синонимами и производится аналогичная его замена и так вплоть до исчерпания кодируемого сообщения или несущего текста.

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

Иногда при кодировании номер, задаваемый скрытой информацией, совпадает с внутригрупповым номером слова в исходном тексте, и тогда никакой замены не происходит. Но при крупных группах квазисинрнимов такое происходит редко и тогда ничем не ограниченные внутригрупповые замены не только изменяют смысл, текста, но и делают его семантически несвязным и тем "подозрительным", что заметно в приводимых в [3] примерах. Настоящая работа предлагает стеганографиче-ский алгоритм, который тоже заменяет текстовые слова их синонимами. Однако он тестирует-производимые замены относительно контекста заменяемого слова. Контекстом считается набор словосочетаний, в которые входит заменяемое слово.

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

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

Приведенное выше понимание словосочетаний находится в русле русской лингвистической традиции с ее синтаксическими зависимостями непосредственно между словами. Эта традиция получила современное развитие в теории "Смысл <->Текст" И. А. Мельчука [4]. Что же до описания языка методом составляющих, получившего на Западе развитие в теории Н. Хомского и его последователей, оно для описания словосочетаний практически не годится: компоненты словосочетания близки в дереве зависимостей, но линейно могут располагаться в предложении далеко друг от друга. Поэтому мы полностью отмежевываемся от подхода, при котором словосочетаниями называют просто совокупности слов, часто встречающиеся рядом в узком окне, продвигающемся вдоль текста.

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

Более конкретно, целями данной работы являются:

– Пояснить, что синонимы бывают как абсолютные, так и относительные; как однословные, так. и многословные. В отличие от относительных синонимов, абсолютные синонимы и относимые к ним (в первую очередь, аббревиатуры), применяются для синонимических замен независимо от контекста. Многословные синонимы, например, электрический ток = электроток в обычные синонимические словари, как правило, не включаются, но для нас они принципиально важны.

– Объяснить, какие словосочетания наиболее важны для синонимического перифразирования- и в чём должен согласоваться с базой словосочетаний синонимический словарь.

– Кратко описать алгоритм лингвистической стеганографии, основанный на идее синонимических замен, проверяемых по словосочетаниям в контексте.

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

АБСОЛЮТНЫЕ И ОТНОСИТЕЛЬНЫЕ СИНОНИМЫ

Феномен синонимии очень важен в лингвистике. В частности; теория "Смысл<->Текст" считает себя исчислением синонимических дерифра-' зов [4]. В ней предложена сложная совокупность правил перифразирования; сохраняющих смысл исходного предложения и дискурса в целом. В.. зависимости от того, на каком уровне языка ведется перефразирование, в его процессе меняется лексика, синтаксическая структура и морфологические характеристики. слов. Вместо одрого слова могут появиться несколько, или наоборот (например, помочь О оказать помощь) могут изменяться части речи (понять Значит помочь <–> понимание означает помощь) и порядок слов. Однако программное воплощение указанных концепций пока достигнуто лишь для ограниченного набора языковых выражений [5].

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

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

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

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

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

К сожалению, в любом языке абсолютных синонимов очень мало. Но существуют эквиваленты другого типа – различные сокращения и аббревиатуры, равно используемые в рамках единого текста. Вот пример группы эквивалентов: {Соединенные Штаты Америки, Соединенные Штаты, США}. Будем далее все такие эквиваленты относить к абсолютным синонимам.

Фактически допущение многословных синонимов привносит очень большое число абсолютных синонимов, например {экс-президент, бывший президент} или {замминистра, заместитель министра}.

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

Еще одну, пусть немногочисленную, группу эквивалентов представляют так называемые морфологические варианты, например {нуль, ноль}, {туннель, тоннель}, {мучить, мучать}.

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

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

Итак, мы предполагаем наличие обширного синонимического словаря со следующими особенностями:

– Каждая группа имеет доминанту.

– Эквиваленты доминанты, если они есть, специально помечены.

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

– Любой член группы, включая доминанту, может повторяться в иной группе и/или быть омонимом члена другой группы. Например, у омонимичного существительного сила есть две группы: {силах, магнитуда, мощность, мощь} и {сила2, действенность}.

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

БАЗА СЛОВОСОЧЕТАНИЙ И ДОПОЛНЕНИЯ К НЕЙ

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

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

В русском языке словосочетания в указанном их понимании давно фигурировали в соответствующих пособиях, есть также словарь среднего объема [9]. В рамках теории "Смысл <–> Текст" (ТСТ) словосочетания получили адекватное описание и классификацию [10]. С точки зрения семантики они были разделены на полные идиомы – фраземы (их смысл не содержит прямого смысла отдельных компонентов); полуфраземы или лексические функции (их смысл содержит прямой смысл только одного компонента из двух главных) и свободные сочетания (их смысл непосредственно составлен из смыслов компонентов).

В 1990-2003 гг. нами была разработана интерактивная система КроссЛексика, в базе которой содержится ныне более 1,2 млн русских словосочетаний разной частотности и разной идиоматично-сти – фразем, полуфразем и свободных словосочетаний [11-14]. Статистический анализ результатов показал, что свободные словосочетания не столь уж свободны: они возможны только между словами фиксированных семантических полей, так что их суммарное количество превышает число фразем и полуфразем вместе взятых лишь в разы (по нынешней нашей оценке – раз в пять), но не на порядки [13].

Дополнительно выяснилось [13, 15], что только при включении в подобные базы свободных словосочетаний эти базы могут найти широкое применение: для создания гибкого и идиоматичного текста; для формирования расширенных поисковых предписаний при поиске информации в текстовых корпусах или Интернете; для автоматического синтаксического анализа открытых текстов; для разрешения омонимии; для обнаружения и исправления семантических ошибок типа малапропизмов; для синонимического перефразирования текстов с целью их канонизации или приближения к возможностям лиц с ограниченным знанием языка; для выявления смысловой связности текста и автоматической сегментации текста на параграфы и т. п.

Идеологически КроссЛексика базируется на ТСТ, но не маркирует и не описывает полуфраземы лексическими функциями, а синтаксические типы словосочетаний здесь не столь дробны, как поверхностно-синтаксические отношения в ТСТ. При этом 94% словосочетаний русского языка оказались относящимися к следующим четырем типам: существительное/глагол/прилагательное/наречие – его модификатор в виде прилагательного или наречия (запутанный сюжет, правильно выразить, практически незаметный, очень хорошо); глагол – его подлежащее (резолюция одобрена, существует противоречие); глагол – его дополнение или предложное обстоятельство (дать воды, передать по радио); существительное – его дополнение (глава государства, борьба за мир).

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

Уже давно было обнаружено и количественно оценено [16], что русское существительное в единственном и множественном числе может иметь разные наборы словосочетаний. Это очевидно для прилагательных, тяготеющих к множественному числу (многие, многочисленные, разнообразные,...) в сравнении с прилагательными, тяготеющими к единственному числу (единственный, одиночный,...), но имеет место и во многих иных случаях. Поэтому единственное и множественное числа существительного берутся как две разные единицы словаря.

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

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

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

Но кроме словосочетаний КроссЛексика содержит и семантические связи ВордНетовского типа, из которых здесь интересны синонимы и гиперонимы. Включенный в КроссЛексику синонимический словарь оперирует теми же граммемами, что и база словосочетаний. Для более эффективного использования синонимов при контроле словосочетаний целесообразно подключать синонимы, являющиеся таковыми в очень ограниченном числе контекстов. Например, исчисление и начисление не считаются синонимами в привычных словарях, но они примерно эквивалентны в словосочетаниях исчисление дивидентов и начисление дивидендов и поэтому сочтены синонимами в Кросс-Лексике. Заметим, что разбиение на граммемы позволяет иметь синонимические группы разные по объему для разных чисел: {клиент, пользователь, потребитель} Vs. {клиенты, клиентура, пользователи, потребители}. Точно так же могут различаться количественно группы для глаголов разного вида.

Из числа словосочетаний, в базе КроссЛексики все лее не представленных, многие могут быть "выведены" в процессе обращения к базе и тут же использоваться для стеганографии, если опираться на родовые понятия. Например, в базе представлены словосочетания о цветах вообще {купить цветов, нарвать цветов, украсить цветами,...} и дополнительно системе известно, что калы являются видом цветов. В итоге при запросе о калах имеется возможность сформировать словосочетания {купить кал, нарвать кал, украсить калами,. } Формально процедура эвристического вывода выглядит так [17]: если компонент Словаря C1 имеет родовое слово (гипероним) H, а H формирует словосочетание с компонентом C2, то С1 формирует словосочетание того же типа с С2. Если у гиперонима H нет словосочетаний релевантного типа, то проверяется гипероним от гиперонима и т. д.

Итак предполагается пользоваться при необходимости иерархией родо-видовых связей между отдельными компонентами словаря.

СТЕГАНОГРАФИЧЕСКИЙ АЛГОРИТМ

Предлагаемый алгоритм имеет два входа.

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

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

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

Наш алгоритм включает следующие шаги.

Поиск синонимичных слов. Текст сканируется и в нем выделяются те отдельные слова и слитые многословные выражения, которые являются статьями системного словаря и имеют синонимы. Если данным условиям отвечают одновременно некая последовательность слов и ее входящая в нее подпоследовательность, предпочтение отдается объемлющей последовательности. Оставшиеся служебные слова помечаются как нерелевантные: они не участвуют в поисках главных компонентов словосочетаний, хотя и могут быть их служебными частями.

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

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

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

Транзитивное замыкание необходимо, поскольку обеспечивает одинаковый состав объединенной группы, с какого бы ее члена эта операция не начиналась, а это важно при декодировании, поскольку в тексте может произойти замена слова. Но иногда эта операция чрезмерно расширяет результирующую группу и чревата привлечением недопустимых замен. Возьмем, например, объединенную группу {освещение1 (например, по телевидению), освещение2 = свет1, свет2 = мир1, мир2 = перемирие}, полученную из любого представленного в тексте слова – освещение, свет, мир или перемирие. Контекст требовать или обеспечить возможен при текстовых словах как освещение, так и мир/перемирие, и потому допускает неверные взаимозамены крайних указанных групп синонимов. Но дополнительный контекст в газете возможен только для освещение\, контекст на кухне – только для группы освещение2 = свет1, a контекст в Либерии – только для группы мир2 = перемирие. Тем самым, ограничительные контексты могут исключить из групп все ненужное, что и будет.продемонстрировано ниже на примере.

Проверка объединенных групп на словосочетания. Если данная группа содержит только абсолютные синонимы, она не проверяется на контекст, а для проверки на сочетаемость с ней иных слов может быть взят любой из синонимов. Если же данная группа содержит относительные синонимы Sj, они подлежат проверке на совместимость с внешними полнозначными словами Wj слева и справа от проверяемой группы. Если внешнее слово Wj не синонимично или имеет только абсолютные синонимы, то проверяется, с какими из s» оно образует однотипные словосочетания. Те Si, которые не формируют словосочетаний с ш,-, отбрасываются. Если внешнее слово Wj само принадлежит объединенной группе с элементами Wjk, то проверяются все однотипные словосочетания пар {Wjk, Si} при всех ink. Отсутствие словосочетания хотя бы с одним внешним элементом ведет к отбрасыванию проверяемого элемента. При этом может не остаться иных пар, кроме как у исходного слова текста, и тогда соответствующая группа в стеганографическом процессе далее не участвует. Элементы, оставшиеся в группе, нумеруются заранее фиксированным образом (например, по алфавиту) от 0 до m=1, где m – число оставшихся элементов.

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

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

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

ТРАССИРОВАННЫЙ ВРУЧНУЮ СТЕГАНОГРАФИЧЕСКИЙ ПРИМЕР

Возьмем типичный текстовой фрагмент из потока новостей Газета.Ру (декабрь 2003):

(1) Пять подземных толчков зарегистрировано за сутки на юге Республики Алтай. Сила землетрясений составляла от 2,2 до 3,1 балла по шпале Рихтера, сообщили на Акташской сейсмической станции сегодня после

Здесь одиночные слова или группы слов, имеющие синонимы, подчеркнуты, а абсолютные синонимы выделены еще и полужирным шрифтом.

Ниже даются группы абсолютных синонимов, зафиксированных в системном словаре КроссЛек-сики. Синонимы упорядочим по алфавиту и двоично пронумеруем:

0. землетрясения 1. подземные толчки

0. за 24 часа 1 за сутки (+за день)

0. сейсмическая станция 1 сейсмостанстанция

Согласно принятому в примере упрощенному варианту алгоритма неабсолютный синоним за день во второй из приведенных групп отбрасывается.

При транзитивном замыкании текстового синонима зарегистрированный были найдены следующие синонимические группы (доминанты вынесены вперед):

зарегистрированный, зафиксированный, отмеченный;

закрепленный, зафиксированный, прикрепленный;

помеченный, замеченный, отмеченный, подмеченный, примеченный;

отпразднованный, отмеченный.

Тем самым полная группа без повторов имеет вид:

(2) закрепленный, замеченный, зафиксированный, зарегистрированный, отмеченный, отпразднованный, подмеченный, помеченный, прикрепленный, примеченный.

Ниже даны те группы относительных синонимов в тексте, которые транзитивное замыкание не меняет:

0. Алтай 1. Республика Алтай

0. равняться 1. составлять

0. проинформироватъ 1. сообщить (+поведать)

0. во вторую половину дня 1. после полудня

Вариант поведать из третьей группы отброшен как имеющий помету устарелое.

Наконец, существительное сила имеет два омонима каждый со своим набором синонимов:

00. магнитуда 01. мощность 10. мощь 11. сила\ 0. действенность 1. силаз

Отфильтруем теперь относительные синонимы и омонимы, которые не удовлетворяют контексту.

Абсолютный синоним землетрясения образует зафиксированные в базе словосочетания с замеченный, зарегистрированный, зафиксированный и отмеченный, но не с остальными членами группы (2), которые поэтому отбрасываются. Все оставшиеся варианты образуют словосочетания с имеющим абсолютный синоним выражением за сутки, а также с несинонимичным словом юг: замеченный/зарегистрированный/зафиксированный/отмеченный за сутки/на юге. Тем самым в группе (2) оставляются только четыре синонима

00. замеченный 01. зарегистрированный 10. зафиксированный 11. отмеченный

Из двух омонимических групп для сила только синонимы силах удовлетворяют контексту: магни-туда/мощность/мощь/сила землетрясения.

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

(сейсмостанция IS -А станция) -> (сообщить на станцию) -> (сообщить на сейсмостанцию)

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

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

подземные толчки 1 землетрясения 1

зарегистрированный 2 составлять 1

за сутки 1 сообщить 1

Республика Алтай 1 сейсмическая станция 1

силах 2 после полудня 1

В целом это дает 12 бит, т. е. в данном фрагменте текста можно спрятать, например, две латинские буквы с кодами в виде правых 6-битовых слогов таблицы ASCII. Так, биграмма si (исп. 'да') соответствует следующему варианту текста (отличия от оригинала выделены):

(3) Пять подземных толчков зафиксировано за 24 часа на юге Республики Алтай. Сила землетрясений составляла от 2,2 до 3,1 балла по шкале Рихтера, проинформировали ио Акташской сейсмической станции сегодня после полудня.

Смысл полностью сохранен, но третье отличие внесло небольшую стилистическую шероховатость.

Спрятанная биграмма по (исп. или англ. 'нет') соответствует иному варианту, безупречному во всех отношениях:

(4) Пять подземных толчков зарегистрировано за сутки на юге Республики Алтай. Мощность землетрясений составляла от 2,2 до 3,1 балла по шкале Рихтера, сообщили на Акташской сейсмостанции сегодня после полудня.

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

Поскольку объем оригинального фрагмента равен 206 байт, а скрытой информации 1,5 байт. последняя составляет 0,73% от несущего текста. Эта величина, которую назовем стеганографиче-ской плотностью, как видим, невелика, и из-за типичности примера едва ли можно ожидать заметно большей величины. Но в достаточно протяженном тексте можно скрыть вполне содержательные послания, они должны лишь быть раз в 200 короче несущего текста.

ВЫВОДЫ

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

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

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

У алгоритма уже сейчас обнаружились следующие недостатки.

• Не должны использоваться для стеганографии отрезки текста, в которых сочинены два синонима, например, отдельные подземные толчки, а также мощные землетрясения. Иначе могут возникнуть повторы (отдельные землетрясения, а также мощные землетрясения), литературному русскому языку не свойственные.

• Неосторожно использовать синонимы, при подстановке которых возникают два однокоренных

слова рядом: гуманный человек хорошо, но человечный человек – это уже из сферы художественной литературы.

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

Все подобные недостатки требуют дальнейших исследований.

СПИСОК ЛИТЕРАТУРЫ

1. Shingo Inoue,et al. A Proposal on Information Hiding Methods using XML. http://takizawa.gr.jp/lab.nlp-xml.pdf.

2. Chapman M., Davida G. Hiding the hidden:A software system for concealing ciphertext as innocuoustext / Eds. Han Yongfei, Okamoto Tatsuaki, Qing Sihan //Proc. 1st Intern. Conf. on Information and Communication Security K'lCS 97. lecture N't«» in Computer Science No. 1334. Springer, 1997. P. 335-345.

3. Chapman M., Davida G., Rennhard M.A Practical «ind Effective Approach to Largo-Scab" Automated Linguistic Stenography / Eds. G. I. Davida, "V". Frank»'! // Information security. Proc, of Intern.Conf. Information and Communication Security ICS 2001,Lecture Notes iw Computer Science No. 2200 -Springer2001,– P. 156-165.

4. Мельчук И. А. Опыт теории лингвистических моделей "Смысл <->Текст Семантика, синтаксис. М.: Наука. 1974.- 314 с.

5. Apresian Ju. D., et al. ETAP-3 Linguistic Processor a Full-Fledged NPL Implementation of the Meaning-Text Theory" // Proc. First Intern. Of Meaning-Text Theory MTT 2003,– Paris: Ecole Normals Superior*, June 2003.P. 279-288.

6. Fellbaum Ch. (ed.) WordNet: An Electronic Lexical Database.– MIT Press, 1998.

7.Vosscn P. (ed.) EuroWordNet General Document.Vers. 3 final, ww.hurnuva.nl/~ewn.

8. Oxford Collocations Dictionary for Students of English.– Oxford University Press, 20O3.

9. Словарь сочетаемости слов русского «зыка. Ок.2500 слов – статей / Под ред." П. Н. Денисова, В. В. Морковкина.– М.: Русский язык, 1983.– 688 с.

10.Mel’chuk I. Phrasemes in Language and Phraseology in Linguistics / Eds. Everaert et al. // Idioms:Structural and Psychological Perspectives. Hillsctate.– NJHove, UK: Lawrence Erlbaum Associates Pubt, 1995. ~P. 169-252.

11. Большаков И. А. Тезаурус в системах подготовки текстов: каким ему быть? // Междукар. форум по информ. и джум.– 1991.– Т. 16, № 2.– С. 3-Ю"

12. Bolshafcov I. A. Maltifanctkm thesaurus for Russian word processing // Proceedings of 4th Conference

on Applied Natural language Processing.– Stuttgart, Germany, October 1994,– P. 200-202.

13. Bolshakov I, A. Getting One's First Million.,. Collocations /Ed. A. Gelbtikh. Computational Linguisticsand Intelligent Text Processing //Proc. 5th Intern. Conf.CICILmg-2004, February 2004, Seoul, Korea. Lecture Notes in Computer Science No. 2745.– Springer, 2004.–P. 229-242.

14. Bolshakov I. A., Gelbttkh A. F. A. Very Large Database of Collocations aad Semantic Links / Eds. M. Bouzegboub et al. // Natural Language Processing and Information Systems. Proc. Intern. Conf. on Applications of Natural Language to Information Systems NLDB-2000. Lecture Notes in Computer Science JSfe 1959.– Springer,– 2001.– P. 103-114.

15. Bolshakov I. A., Gelbukh A. F. Word Combinations as an Important Part of Modern Electronic

Dictionaries // SEPLN (Sociedad Espanol para el Procesamiento del Lenguaje Natural) Revista.– 2002.–No. 29,– P. 47-54.

16. Большаков И. А., Гельбух А. Ф. Раздельное представление словосочетаний ддж существительных единственного ж множественного числа // Тр.Межяунар. Семинара по вычиелвтеяьиой лингвистикеи ее приложениям. Диалог W.-– Пупогао, 1996.– С. 42-44.

17. Bolshakov I. A., Gelbakh A. F. Heuristics-Based Replenishment of Collocation Databases / Eds.E. Ranchhold, N. J. Mamede // Advances in NaturalLanguage Processing. Proc. Intern. Conf. PorTAL 2002,Faro. Portugal. Lecture Notes in Artificial IntelligenceNo. 2389.-- Springer, 2002.– P. 25-32.

Материал поступил в редакцию 16.03.04

ISSN 0548-002? . НТИ . СЕР. 2 . ИНФОРМ, ПРОЦЕССЫ И СИСТЕМЫ . 2004 . № 8