Содержание к диссертации
Введение
1. Анализ существующих технологий блокирования вредоносного поведения программ 12
1.1. Основные понятия и определения 12
1.2. Актуальность систем блокирования поведения 13
1.3. Цели и задачи систем блокирования поведения 16
1.4- Анализ типовых стадий компьютерной атаки 18
1.5, Классификация технологий блокирования поведения 21
1.5 Л. Технологии на основе политик безопасности 23
1.5.1, Технологии на основе сигнатур 25
1,5.1 Технологии на основе статистических данных ,„. 28
1.6, Преимущества и недостатки технологий блокирования поведения 30
1.7, Выводы 31
2. Исследование систем блокирования вредоносного поведения программ и выявление общих путей их развития 33
2.1, Теория решения изобретательских задач как инструмент исследования 33
2.1.1- Этапы формулировки задачи и ее решения 35
2.1.2- Методика перехода от изобретательской ситуации к комплексу задач 36
2.2, Изобретательская ситуация в исследуемой проблеме 37
2-3- Постановка задачи блокирования вредоносного поведения в виде системы противоречий 40
2,4- Решение поставленной задачи 43
2.4Л, Разделение противоречивых свойств в структуре путем изоляции поведения программ 2.4.2. Разделение противоречивых свойств в структуре путем изоляции ресурсов 47
2.4.3. Разделение противоречивых свойств во времени путем разделения работы 49
2.4.4. Разделение противоречивых свойств во времени путем оптимизации работы 51
2.5. Общие пути развития систем блокирования вредоносного поведения 52
2.6, Выводы 53
3, Разработка методологической и алгоритмической основы метатехнологии защиты от вредоносного поведения программ 54
3.1. Метод логической изоляции поведения программ 54
3.2. Внутреннее представление механизма логической изоляции 56
3.3. Разработка алгоритмов логической изоляции
3.3.1. Способы обработки запросов к ресурсам 57
3.3.2. Способы выделения памяти для изолируемых ресурсов 61
3.3.3. Алгоритмы изоляции логических объектов 64
3-3.4. Алгоритмы изоляции физических объектов 66
3.4. Разработка концепции метатехнологии защиты 71
3.4.1. Реализация доступности системы в условиях неопределенности 73
3.4.2. Интеграция механизма логической изоляции с существующими системами защиты 76
3.5. Выводы 80
4. Оценка эффективности метатехнологии защиты в статистических системах 82
4Л. Методика оценки эффективности механизма логической изоляции...82
4,2, Моделирование логической изоляции в системе обнаружения вторжений на основе динамики системных вызовов 85
4.2.1. Построение классификатора на основе вероятностных суффиксных деревьев 89
4.2.2. Получение обучающего и тестового набора для классификатора 98
4.2.3. Построение экспертной системы для оценки классификатора.,„104
4.2.4. Получение и сравнение характеристик качества классификатора 107
4,3« Выводы ПО
5. Программная реализация и практическая оценка основных механизмов предлагаемой метатехнологии 112
5.1. Подходы к реализации метода логической изоляции 112
5.1.1. Реализация на уровне фильтра системных сервисов 112
5.1.2, Реализация на уровне фильтра файловых операций 118
5.1.3- Реализация на уровне фильтра дисковых операций 123
5.2. Сравнительный анализ рассмотренных подходов реализации 126
5.3. Разработка механизма логической изоляции 129
5 А Практическая оценка механизма логической изоляции 132
5.5, Выводы 135
Заключение 136
Список литературы
- Анализ типовых стадий компьютерной атаки
- Изобретательская ситуация в исследуемой проблеме
- Способы обработки запросов к ресурсам
- Моделирование логической изоляции в системе обнаружения вторжений на основе динамики системных вызовов
Введение к работе
В настоящее время в сфере информационных технологий отчетливо просматривается тенденция быстрого усложнения и обновления информационных систем, что является причиной появления все новых и новых угроз безопасности. Системам защиты, в свою очередь, необходимо учитывать больше аспектов безопасности, что также приводит к их усложнению. Они становятся громоздкими и сложными в эксплуатации и настройке.
Кроме того, данные статистики говорят о том, что существующие средства защиты от вредоносного поведения программ, к которым традиционно относят системы контроля доступа, обнаружения вторжений и антивирусные сканеры не способны в полной мерс защитить компьютеры пользователей от новых и неизвестных вредоносных программ.
Современная система защиты должна обеспечивать адекватное противодействие новым и неизвестным вредоносным программам. Актуальной становится проблема разработки контрмер по отношению к вредоносным воздействиям. Система защиты должна предполагать, что часть атак со стороны вредоносных программ все же достигнет успеха и необходимо иметь заранее подготовленный арсенал контрмер.
Суть проблемы заключается в том, что наиболее разработанные и доминирующие технологии защиты, такие, как контроль доступа, обнаружение вторжений и антивирусное сканирование, работают в рамках парадигмы блокирования действий или предотвращения вторжений, которая утрачивает свою адекватность реальным условиям. Возникает необходимость переосмысления существующих технологий в свете сегодняшних тенденций и качественного их усовершенствования.
Актуальность темы
Диссертация посвящена исследованию методологических аспектов актуальной проблемы защиты информационных ресурсов от вредоносного поведения программ. Теоретические исследования ряда авторов показали с математической строгостью принципиальную ограниченность техник обнаружения и блокирования вредоносного программного кода, В этой связи на передний план выходит задача разработки не абсолютной, но адекватной системы защиты, что вызывает необходимость обобщения и систематизации концепций и подходов, имеющих отношение к обозначенной проблеме.
Принимая во внимание сегодняшнюю тенденцию быстрого усложнения и увеличения объемов информационных потоков, важно отметить, что помимо задачи обнаружения и блокирования новых и неизвестных угроз безопасности особое значение приобретает задача оперативного поиска и ликвидации последствий вредоносных воздействий. Не смотря на то, что данные задачи направлены на решение одной проблемы, попытки их комплексного рассмотрения до сих пор не предпринимались.
В диссертации предлагается восполнить данный пробел рассмотрением задач блокирования вредоносных воздействий и восстановления системы после сбоев в рамках принципа изоляции поведения программ. Учитывая успехи и продолжающееся развитие теории метапознания в таких науках как математика (металогика), физика (метафизика), информатика (метапоиск), представляется целесообразным раскрытие методологического значения принципа изоляции посредством понятия «метатехнология защиты». Роль идеи метатехнологии заключается в том, что она фиксирует общие моменты и особенности технологий, по отношению к которым она применяется и указывает на конкретные способы их модернизации.
Цели и задачи работы
Целью работы является разработка метатехнологии защиты, позволяющей качественно модернизировать существующие технологии защиты информационных ресурсов от вредоносного поведения программ в части принятия решений о допустимости и недопустимости информационных воздействий.
Для достижения указанной цели были поставлены следующие задачи:
1. Исследовать существующие системы защиты от вредоносного
поведения программ и выявить общие пути их развития.
2, Разработать алгоритмическую и методологическую основу
метатехнологии защиты,
3. Разработать методику оценки эффективности метатехнологии защиты,
4, Провести экспериментальное исследование метатехнологии защиты с
помощью программной реализации ее основных механизмов.
Методы исследованя
Для решения перечисленных задач использовались методы решения изобретательских задач, теории вероятностей, теории функциональных и экспертных систем, теории графов и алгоритмов.
Объект и предмет исследования
Объектом исследования являются технологии защиты от вредоносного поведения программ. Предметом исследования являются аспекты развития и модернизации существующих технологий защиты.
Результаты, выносимые на защиту
1, Разработанные метод и алгоритмы логической изоляции поведения программ позволяют реализовать эффективную защиту различных типов информационных ресурсов.
2. Разработанная концепция метатехнологии защиты определяет способы модернизации существующих технологий защиты на основе метода логической изоляции и механизма отложенного принятия решений.
3 - Разработанная методика оценки эффективности метатехнологии защиты позволяет моделировать применение механизма логической изоляции к различным реализациям статистических систем защиты.
4, Результаты экспериментального исследования предлагаемой метатехнологии подтверждают ее работоспособность и возможность применения в реальных условиях.
Научная новизна работы
Научная новизна работы заключается в следующем:
1, С помощью методов решения изобретательских задач осуществлено
исследование систем защиты от вредоносного поведения программ и
выявлены общие пути их развития.
2. Разработаны новые метод и алгоритмы логической изоляции поведения
программ, основанные на модификации логики выполнения операций с
ресурсами, предполагающей возможность отмены изменений и
возврата к исходному состоянию в случае обнаружения неисправности.
3, Разработана концепция метатехнологии защиты, в рамках которой
предложены новые способы модернизации существующих технологий
защиты, на основе метода логической изоляции и механизма
отложенного принятия решений.
4. Разработана методика оценки эффективности предлагаемой
метатехнологии на базе экспертной системы, позволяющая оценивать
целесообразность применения механизма логической изоляции к
статистическим системам защиты.
Карта работы
Основные этапы диссертационной работы можно представить с помощью визуальной карты, как показано на рисунке 1,
Технологии контроля доступа
Технологии
обнаружения
вторжений
Технологии антивирусного сканирования
ТРИЗ исследование
Концепция
метатехнологии
защиты
Метод логической изоляции
Развитие
прежних
концепций
Развитие
идеи изоляции
Описание
Оценка
Алгоритмы
Реализация
Рис 1. Визуальная карта работы.
Данный рисунок показывает, каким образом выполняется переход от объекта исследования, представленного технологиями контроля доступа, обнаружения вторжений и антивирусного сканирования, к предмету исследования, выраженного концепцией метатехнологии защиты.
Практическая ценность работы
В практическом плане ценность представляют разработанные метод и алгоритмы логической изоляции поведения программ, которые могут использоваться разработчиками для создания новых средств защиты различных типов информационных ресурсов.
Кроме того, разработанный метод логической изоляции позволяет модернизировать бинарный механизм принятия решений, используемый в существующих системах защиты, решающих задачи противодействия вирусам, контроля доступа и обнаружения вторжений, таким образом, чтобы была возможность отложенного принятия решений, когда ни пользователь, ни система не могут дать однозначного ответа по поводу блокирования поведения- Применение логической изоляции позволяет принимать правильные решения при появлении достаточной информации без риска для безопасности системы.
Ценность также представляет разработанная методика оценки целесообразности применения логической изоляции в различных реализациях статистических систем защиты.
Использование результатов
Результаты, полученные в ходе работы над диссертацией, были использованы на кафедре Безопасности информационных технологий ТРТУ при проведении научно-исследовательских работ «Создание программных и программно-аппаратных средств обнаружения и выявления сетевых атак в информационно-телекоммуникационных системах» и «Разработка материалов по вопросам обнаружения сетевых атак в ЛВС АС ВН и создания программного макета системы тестирования системы обнаружения атак», а также при проведении научных исследований, поддержанных грантом РФФИ № 04-07-90137 «Исследование и разработка моделей, методов и средств обнаружения атак».
Достоверность полученных результатов подтверждается полнотой и корректностью теоретических обоснований и результатами экспериментов, проведенных с помощью разработанных в диссертации программ.
Апробация работы
По теме диссертации опубликовано 11 научных статей и тезисов докладов, из них одна статья опубликована в журнале «Проблемы информационной безопасности. Компьютерные системы» из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных работ. Основные результаты, полученные в ходе работы над диссертацией, были представлены на:
Международных научно-практических конференциях «Информационная безопасность», г. Таганрог, 2003, 2004,2005 годов.
Всероссийских научных конференциях «Проблемы информационной безопасности в системе высшей школы», г, Москва, 2003 и 2006 годов,
3- Всероссийском смотр-конкурсе научно-технического творчества студентов высших учебных заведений «Эврика - 2005», г. Новочеркасск, 2005 г.
4. Международной научно-практической конференции «Комплексная
защита информации», г. Суздаль, 2006 г.
5, Международном конкурсе по информационной безопасности
«Securitatea informationala - 2006», г. Кишинев, 2006 г.
Анализ типовых стадий компьютерной атаки
Не смотря на то» что существует огромное множество самых разнообразных вирусов, троянских программ и компьютерных червей, все атаки на компьютерные системы имеют очень много общих свойств, что позволяет свести весь процесс заражения к определенной последовательности действий, как показано на рисунке 1 .4,
Получить доступ к удаленному компьютеру можно лишь в том случае, если он имеет одну или несколько уязвимостей. Поэтому первой фазой компьютерной атаки является фаза "Изучения", На данном этапе злоумышленник получает полный список уязвимостей и брешей в защите пользовательского компьютера.
Код, использующий уязвимость передается па целевой компьютер в фазе "Внедрения", Цель этой фазы - запустить на уязвимом компьютере вредоносный код с помощью доступных методов. Например., через гшреполпеїдая буфера После того как вредоносный код был удачно запушен, ом пытается остаться ва целевом компьютере. Цель фазы "Сохранения" заключается в том, чтооы вредоносный код запускался всякий раз, когда система перезапускается.
После того как вредоносный код внедрился в систему и расчистил себе плацдарм, он пытается распространить себя на другие, уязвимые компьютеры. В фазе "Распространения" вредоносный код ищет компьютеры, на которые он может себя переписать и запустить.
Только в фазе "Парализации" выполняется реальное нанесения ущерба. Вредоносная программа может удалить файлы, разрушить систему, произвести атаку типа "распределенный отказ в обслуживании" (DDoS).
Первые две стратегии сильно подвержены изменениям (сигнатуры атак постоянно изменяются). Также существуют специальные методы сокрытия нападения с помощью "техники уклонения". Например, кодирование строк передаваемых Web серверам в Unicode формат, или перекрывающаяся фрагментация пакетов. Также продукты, которые обнаруживают атаки на этапе "Внедрения" могут иметь несколько интерпретаций (рассуждение на базе догадок о том, как целевой компьютер будет обрабатывать сетевой пакет). Это приводит к большому количеству ложных тревог.
Последние три стратегии, напротив, очень стабильны во времени. Они ограничены количеством злонамеренных действий, которые злоумышленник, хочет произвести на целевой машине. Например, модификация операционной системы, добавление нового пользовательского аккаунта, открытие выходящих сетевых соединений, удаление файла и другие- Таких действий можно насчитать всего несколько десятков. Причем этот список остается неизменным: например вирус Морриса в 1988 году производил те же повреждения системы, что и NIMDA Worm в 2001 году. Поскольку в большинстве случаев такие действия, как модификация программных файлов и настроек операционной системы можно рассматривать как необычные действия, то идентифицировать атаку на этих этапах гораздо легче.
Таким образом, можно отметить, что на начальных стадиях каждая атака выглядит по-разному и может быть реализована множеством различных способов. Кроме того, одна и та же атака может быть выполнена в различных модификациях. На более поздних стадиях атаки не отличаются вариативностью и, как правило, используют схожие схемы. Благодаря этому обнаружение и блокирование новых атак целесообразно выполнять именно на последних стадиях вторжения,
Общей особенностью всех технологий блокирования поведения является их способность идентифицировать и блокировать вредоносные действия программ в режиме реального времени [4-7]. В рамках данных технологий решаются следующие основные задачи: перехват обращений процессов к ресурсам; проверка легитимности каждой выполняемой операции; блокирование выполнения вредоносных операций.
В случае успешной работы системы блокирования поведения вредоносное действие предотвращается до его непосредственного выполнения, В соответствии с внутренними настройками система защиты сообщает пользователю, какое именно приложение выполнило несанкционированные действия, и по какой причине оно было заблокировано.
Исходя из решаемых задач, внутреннюю структуру любой системы блокирования поведения можно представить в виде управляющего и исполнительного компонентов. Взаимодействие данных компонентов носит двухсторонний характер
Изобретательская ситуация в исследуемой проблеме
Все системы блокирования поведения на основе правил безопасности состоят из трех основных компонентов: БД правил безопасности, механизма принятия решений и монитора безопасности. Все эти компоненты являются неотъемлемой частью любой существующей системы данного типа. Они составляют ядро механизма безопасности.
На рисунке также изображена внешняя среда, в которую входит пользователь, работающий с системой. Изображение пользователя обусловлено тем, что конфликт может возникнуть не только внутри системы между ее компонентами, но и между исследуемой системой и надсистемой, или внешней средой,
В рассматриваемой схеме система контроля доступа накладывает ограничения на выполняющиеся приложения, достаточные для того» чтобы при их исполнении гарантировать конфиденциальность информации пользователя. БД правил безопасности определяет разрешенные и запрещенные действия для всех приложений, выполняющихся в системе. Действие или поведение приложения может представлять собой чтение, запись или удаление какого-либо файла, ключа реестра или другого объекта системы. Механизм принятия решений производит анализ каждого действия приложения по определенному алгоритму, используя БД правил безопасности. Если устанавливается, что рассматриваемое действие является вредоносным, то оно немедленно блокируется, в противном случае, выполнение действия разрешается. Возможна также и ситуация когда механизм принятия решений не может определить является ли данное действие вредоносным или нет, В этом случае система спрашивает пользователя, и получив ответ, выполняет нужную команду. Непосредственный контроль поведения приложений выполняет монитор безопасности, который одновременно является и сенсором, перехватывающим выполняемые приложением действия, и исполнительным органом, выполняющим команды механизма принятия решений.
Перед началом работы систему защиты необходимо настроить в соответствии с принятыми для данной среды требованиями или политикой безопасности. Для корректной настройки системы пользователю необходимо иметь информацию об установленных приложениях и ресурсах, с которыми они могут работать. Данный факт является существенной проблемой системы контроля доступа, так как, с одной стороны, на компьютерах пользователей установлено множество приложений разного назначения, выполняющих разные функции и, с другой стороны, приложения не имеют спецификации по своей работе, что не исключает наличия скрытых возможностей. По этим причинам составление правил безопасности является сложной задачей для пользователя и, кроме того, нет никаких гарантий, что приложение не выполнит какую-либо скрытую и непредусмотренную системой защиты операцию.
Другой важной проблемой систем защиты, основанных на правилах безопасности, являются ложные тревоги. Появление ложных тревог обусловлено тем, что, в принципе, невозможно создать абсолютно исчерпывающий набор правил безопасности для каждого установленного в системе приложения- В большинстве случаев, для удобства и быстроты настройки, система защиты предлагает использовать шаблонные правила для конкретных типов приложений- Это может привести к тому, что выполнение легальных операций будет блокироваться и пользователю придется многократно корректировать правила безопасности. Работа пользователя может быть прервана в любой момент, если механизм принятия решений не сможет самостоятельно определить является ли выполняемая операция вредоносной или нет. Все это может привести к ослаблению правил безопасности, что естественно не является наилучшим решением.
Перед нами изобретательская ситуация с четко видными поверхностными противоречиями- Нужно как-то упростить или облегчить создание правил безопасности, но как — неизвестно. Появление ложных тревог должгто быть мшшмщзытм шли вообще отсутствовать, что таюке
В таблице можно рассматривать или верхнюю или нижнюю половину (относительно диагонали), так как прямое и обратное взаимодействие для выявления конфликтующей пары одинаковы. Из шести пар элементов конфликт имеется в трех: 1. пользователь - БД правил; 2. пользователь - механизм принятия решений; 3. БД правил — механизм принятия решений. Две конфликтующие пары - это две различные изобретательские ситуации со своими углубленными противоречиями. Следует отметить, что исследовательская задача в ТРИЗ всегда формулируется в виде цепочки противоречий. Сформулируем цепочку противоречий для первой конфликтующей пары:
ПШ: Система блокирования поведения должна обеспечивать защиту не только от известных вредоносных программ, но и от неизвестных, которые могут появиться в будущем- Для этого необходимо реализовать правила безопасности для всех типов программ (пользовательские приложения, сервисы, скрипты, драйверы и т.д.) и ресурсов (файлы, ключи реестра» устройства внешней памяти и др.), а сами правила должны учитывать не только одиночные операции, но также и последовательности взаимосвязанных операций. Таким образом, можно добиться высокой вероятности обнаружения и блокирования вредоносных программ.
Способы обработки запросов к ресурсам
В данной работе рассматриваются способы изоляции следующих типов ресурсов в рамках операционной системы Microsoft Windows: Файлы, Ключи системного реестра, Объекты ядра. Секторы жесткого диска.
Изоляция файловой системы заключается в перехвате и - перенаправлении функций для работы с файлами, которые имеют в качестве входного параметра имя файла. К таким функциям можно отнести функции создания и открытия файлов. Перед тем как выполнить функцию открытия файла па запись, механизм логической изоляции копирует файл, к которому происходит обращение в выделенный кэш, затем меняет оригинальное имя файла, переданное в функцию, на новое имя и после этого разрешает функции продолжить свое выполнение- В результате успешного завершения функции создается описатель, связанный с кэшированным файлом, в то время как оригинальный файл остается неоткрытым. Поскольку остальные файловые функции, такие как чтение или запись файла работают непосредственно с описателем кэшированного файла, то нет необходимости перехватывать и отслеживать их работу. Однако функции удаления файла, чтения атрибутов файлов и перечисления файлов в директории нуждаются в обработке. При удалении файла необходимо выполнить извлечение имени файла по описателю и записать его в список удаленных файлов. При попытке извлечения имени файла по его описателю необходимо возвращать оригинальное имя файла» соответствующее реальной среде. При перечислении файлов в определенной директории необходимо возвращать адекватный список файлов с учетом содержимого этой директории в изолированной области.
Системный реестр представляет собой хранилище общесистемных и пользовательских параметров. Структура реестра аналогична структуре логического диска. Он содержит разделы (keys), напоминающие дисковые каталоги, и параметры (values), которые можно сравнить с файлами на диске. Поэтому для изоляции реестра можно использовать такой же способ, как и для изоляции файловых ресурсов. Необходимо перехватывать только те функции, которые получают на вход имя ключа, и перенаправлять их в выделенный кэш таким образом, как это делается для файловых ресурсов, В зависимости от того, какой тип доступа запрашивается при обращении к ключу реестра, приложение получает доступ либо к оригинальному ключу, либо к его новой копии в кэше.
Операционная система поддерживает различные типы объектов ядра, среди которых можно выделить мьютексы (mutex objects), разделяемую память (section objects), события (event objects), каналы (pipe objects), почтовые ящики (mailslot objects), порты (port objects) и другие. На физическом уровне каждый объект ядра представляет собой просто блок памяти, выделенный ядром и доступный только ему. Этот блок представляет собой структуру данных, в элементах которой содержится информация об объекте. Объекты ядра могут использоваться приложениями для синхронизации работы, а также для межпроцессного взаимодействия. Поскольку все объекты ядра находятся в едином пространстве имен, то запуск нового экземпляра приложения в режиме изоляции может быть остановлен ранее запущенным экземпляром в обычном режиме. Кроме того, изолированное приложение может взаимодействовать с внешней средой с помощью механизмов межпроцессного взаимодействия, основанных на объектах ядра. Для предотвращения подобных ситуаций объекты ядра также необходимо изолировать, как и другие ресурсы. Поскольку операционная система поддерживает иерархию объектов ядра подобную файлам и реестру, изоляцию можно организовать аналогичным способом, за счет перехвата операций создания и открытия объектов и перенаправления их в изолированную область.
Таким образом, мы видим, что все рассмотренные логические объекты изоляции - файлы, ключи реестра и объекты ядра имеют иерархическую структуру. Кроме того, функции для работы с данными объектами очень схожи и могут быть разделены на две группы. Первая группа включает в себя функции, принимающие на вход текстовые имена в качестве параметров. Как правило, это функции создания или открытия объектов.
Моделирование логической изоляции в системе обнаружения вторжений на основе динамики системных вызовов
Для построения модели описанной системы защиты предлагается использовать алгоритм классификации по расстоянию на основе вероятностных суффиксных деревьев (probabilistic suffix tree, PST), который был эффективно использован рядом авторов для решения задачи распознавания музыкальных стилей [49].
Вероятностное суффиксное дерево, описанное в [52], это п-арное дерево, в котором узлы организованы так, что корневой узел представляет безусловную вероятность каждого символа в алфавите, в то время как, узлы на следующих уровнях представляют вероятности возникновения следующего символа при условии, что уже наблюдалась комбинация одного или большего числа символов (т.е. при наличии истории). Вероятности - это относительные оценки, вычисляющие частоту возникновения символа В обучающем примере или примерах. PST также имеют свойство порядка, соответствующее глубине дерева, так что PST порядка к содержит к+1 уровень. Для иллюстрации, рисунок 4,6 показывает PST третьего порядка, порожденное из образца «2113131334», где символы «2» и «4» используются как начало и конец строки.
Начиная с корневого узла, который представляет пустую строку, каждый узел является суффиксом всех своих потомков, поэтому модель получила название суффиксного дерева- Корень, представляющий пустую строку, является непосредственным суффиксом всех единичных СИМВОЛОВ
Числа в круглых скобках расположенные рядом с узлами являются условными вероятностями следующих символов, за исключением того, что распределение вероятностей следующих символов для корневого узла имеет вероятность равную нулю для конечного символа «4», поскольку этот символ сам не имеет следующих символов в обучающем примере. Необходимо также отметить, что переходы к следующему символу осуществляются от одной ветки к другой, а не от родительского узла к потомку, вследствие формата суффикса узла.
Ниже представлен рекурсивный алгоритм для построения дерева-Пример для построения сканируется для определения вероятности каждого символа. Каждый символ с ненулевой вероятностью становится потомком корневого символа, и для каждого такого узла пример пересканируется для определения распределения вероятностей следующих символов. Это может создать новые листья и добавить новый уровень к PST. Построение рекурсивно добавляет дополнительные уровни путем проверки каждого текущего листа для определения, могут ли быть созданы новые листья среди потомков данного узла. Информация о символах, предшествующих данному символу сохраняется, поскольку эти символы могут встречаться в суффиксной информации потомков данного узла. Узел добавляется только если подстрока символов, которая соответствует метке узла, есть в обучающем примере и для него существует ненулевое распределение вероятности следующего символа. Многие ветви отмирают прежде, чем распространяются до максимума глубины. Глубина (т.е. порядок) дерева может быть установлена в максимальное допустимое значение, или по умолчанию, это длина входной последовательности. Для каждого узла дерева память должна выделяться динамически.
Далее рекурсивный восходящий процесс усечения должен удалить ветви, которые предоставляют ту же информацию, что и родительские узлы. Удаление этих узлов «аналогичных родительским» снижает избыточность в структуре дерева и таким образом, создает экономичную модель. Пунктирные линии и фигуры на рисунке 4.6 показывают отсеченные узлы и соответствующие ветви, Отсечение базируется на вероятностной информации.
Главная роль PST в нашем случае — это стохастическое представление обучающих данных в древовидной структуре. Несколько PST, потенциально представляющих разные или подобные обучающие примеры могут быть слиты в одно дерево, которое может быть получено другим путем при использовании всех индивидуальных обучающих последовательностей. Эта операция позволяет проводить прямые манипуляции с самими PST без потери дополнительных вычислительных мощностей для разборки большого дерева PST. В отношении реконструкции, как упомянуто выше, определенные узлы убираются из PST, если они предоставляют ту же стохастическую информацию, как и их предки. Существует алгоритм для реконструкции вероятностной информации следующих символов для удаленных узлов и, таким образом, реконструкции или заполнения узлов в PST- Эта техника может использоваться для выполнения аналитических операций с PST, таких как сравнение двух деревьев. Есть несколько вариантов алгоритмов нахождения расстояния между двумя PST для нахождения степени похожести или непохожести между PST
