Способ поиска входной строки в дереве поиска с индексацией используемых при построении дерева строк

Область техники

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

Уровень техники

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

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

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

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

Публикация US 8880507 описывает систему поиска IP-адресов, использующую дерево, в узлах которого содержатся подстроки.

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

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

Сущность изобретения

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

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

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

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

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

Краткое описание чертежей

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

Фиг. 1 изображает пример работы программного обеспечения на компьютере.

Фиг. 2А изображает способ поиска входной строки в дереве поиска, содержащем маски.

Фиг. 2Б отображает структуру дерева поиска.

Фиг. 2В отображает структуру дерева поиска после индексации.

Фиг. 3 представляет пример компьютерной системы общего назначения, на которой может быть реализовано настоящее изобретение.

Описание вариантов осуществления изобретения

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

Фиг. 1 изображает пример работы приложений на вычислительном устройстве.

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

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

- локальные пути к файлам и каталогам 130 (в зависимости от типа устройства и операционной системы формат путей может отличаться);

- пути к веткам реестра 140;

- пути в локальной сети 150;

- адреса ресурсов в сети интернет 155;

- пути к определенным сервисам и серверам (например, строка связи с базой данных 165 на SQL-сервере);

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

Пути, разрешенные или запрещенные для приложения, могут быть описаны в базе данных, которую использует приложение безопасности 180. Зачастую множество путей содержит пути из одного каталога, которые могут быть описаны с помощью масок. В общем случае маска - это строка, с помощью которой может быть описано множество похожих строк. В общем случае маски описываются с помощью специальных символов (спецсимволов), например, «?» (маска произвольного одиночного символа) и «*» (маска произвольного числа произвольных символов). Описание с помощью масок сокращает общее количество путей, контролируемых приложением безопасности 160, например, пути «C:\Windows\System\Drivers» и «D:\Windows\System32\Drivers» могут быть описаны с помощью маски «?:\Windows\System*\Drivers». Однако количество контролируемых (разрешенных или запрещенных) путей даже в случае использования масок может быть значительным. При линейном последовательном поиске сравнение пути, к которому обращается приложение, со всеми разрешенными (запрещенными) путями занимает значительное время, так как является последовательным сравнением строк друг с другом. При этом возможно замедление работы как отдельного приложения 120, так и приложения безопасности 160 или операционной системы 110 в целом. При выполнении ресурсоемких задач, например, при математических расчетах или обработке запросов к базе данных, на вычислительном устройстве (например, компьютере или сервере) замедление недопустимо, необходимо решение для быстрого поиска пути, по которому обращается приложение, во множестве разрешенных путей.

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

Фиг. 2А изображает способ поиска пути по дереву поиска, содержащему маски путей.

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

На начальном этапе 201 средство создания дерева 291 создает словарь символов. Словарь символов содержит символы и спецсимволы, которые могут быть использованы средством создания дерева 291 при создании дерева. Например, в качестве символов используются только английские символы в верхнем регистре. Кроме того, в качестве спецсимволов могут использоваться упомянутые символы «?» и «*». Расположение спецсимволов в строке адреса произвольное, количество спецсимволов не ограничено. В общем случае запрещается использовать комбинации из рядом расположенных спецсимволов (то есть нельзя указать «*?», «?*» или «**»).

В одном из вариантов реализации для каждого символа в словаре средство создания дерева 291 добавляет индекс - числовое значение. Например, элементы словаря, состоящего из английских символов в верхнем регистре, цифр и спецсимволов, имеют индексы от «0» до «36» (26 индексов добавляются для букв алфавита, 10 индексов для цифр, индекс «36» добавляется для спецсимволов).

Пример дерева поиска 220, построенного на этапе 202 средством создания дерева 291 для набора путей:

отображен на Фиг. 2Б.

При построении дерева поиска 220 средство создания дерева 291 сохраняет (помещает) в узлы дерева поиска 220 подстроки (англ. substring), состоящие из символов словаря, при этом каждая строка из набора путей разделяется на подстроки. В общем случае реализации настоящего изобретения из каждой строки из набора путей выделяется и помещается в отдельный узел дерева поиска 220 подстрока, являющаяся префиксом строки из набора путей, содержащая символы до спецсимвола («?» или «*»). В одном из вариантов реализации спецсимвол «?» также помещается в отдельный узел дерева поиска 220. Оставшаяся подстрока (оставшаяся часть строки из набора путей) также (по вышеуказанным правилам) разделяется на подстроки, если содержит другие спецсимволы, в ином случае помещается в отдельный узел дерева поиска 220. В случае, если строка из набора путей содержит подстроку, которая содержится в подстроке одного из узлов дерева поиска 220, подстрока этого узла разделяется на две подстроки, при этом первая подстрока сохраняется в этом узле дерева поиска 220, а вторая - в дочернем. Узел дерева поиска 220, в который помещается последняя подстрока входящей в набор путей строки, является конечным, но может содержать потомков. Конечные узлы дерева поиска 222 отмечены на Фиг. 2Б с помощью утолщенных контурных линий.

При построении дерева поиска средство построения дерева 291 сохраняет в узле дерева индекс пути из набора путей, подстрока которого хранится в этом узле. При этом индекс пути - это в общем случае номер строки в наборе путей, по которому строится дерево поиска. В одном узле может храниться более одного индекса пути. Индексы путей, хранящиеся в узлах дерева поиска 220, указаны на Фиг. 2Б в квадратных скобках. Так, например, узел «\REGISTRY\MACHINE\S» хранит индексы путей с [1] по [9], так как указанная подстрока содержится в каждом пути из набора путей.

На этапе 203 средство построения дерева 291 выполняет индексацию дерева поиска 222, которое после индексации имеет структуру, отображенную на Фиг. 2В. Средство построения дерева с использованием словаря символов строит таблицу индексации. В каждом конечном узле средство построения дерева 291 выбирает последний символ подстроки узла, и в таблице индексации сохраняет индексы путей, которые содержат подстроку, хранящуюся в данном конечном узле.

В результате таблица индексации в одном из вариантов реализации выглядит так (сам символ, набор индексов путей):

На этапе 204 средство поиска 292 определяет множество индексов узлов, которые будут использованы при поиске входной строки по дереву поиска 222. Для этого по таблице индексации для последнего символа строки, которую надо найти, определяется набор индексов путей, по которым необходимо выполнить поиск. Так, например, в строке «REGISTRY\MACHINE\SYSTEM\CONTROLSET001NUM\ROOT\LEGACY_KLP» последним символом является «Р», поэтому согласно таблице индексации при поиске необходимо использовать пути [2], [5] дерева поиска 222. Кроме того, так как дерево поиска 222 содержит произвольный символ в конечном узле, индексы путей, ведущие к нему, тоже учитываются средством поиска 292, то есть при поиске необходимо также использовать пути [3], [4]. Средство поиска 292 объединяет наборы индексов путей во множество индексов путей, в результате чего определяет, что при поиске упомянутой строки выполнять сравнение нужно только в узлах, содержащих подстроки путей [2], [5], [3], [4].

На этапе 205 средство поиска 292 выполняет поиск входной строки в дереве поиска 222. Происходит сравнение входной строки с подстроками, хранящимися в узлах дерева поиска 222, при этом сначала определяется, содержит ли узел индекс пути, входящий во множество индексов путей, определенное на этапе 204, затем подстрока узла ищется во входной строке. В настоящее время существует множество способов быстрого поиска подстроки в строке, существуют также способы, которые выполняют упомянутый поиск с использованием масок. Рассмотрение этих способов выходит за рамки настоящего изобретения. Если подстрока из узла дерева поиска 222 содержится во входной строке и находится в начале входной строки (является префиксом входной строки), то часть входной строки, эквивалентная подстроке из узла дерева поиска 222, удаляется из входной строки, и поиск продолжается. Оставшаяся часть входной строки (подстрока) сравнивается с дочерними узлами упомянутого узла дерева, подстрока которого содержалась во входной строке. Как и ранее, сначала определяется, содержит ли узел индекс пути, входящий во множество индексов путей, определенное на этапе 204, затем подстрока узла ищется в оставшейся части входной строки. Таким образом, ветвления дерева, которые образованы узлами, содержащими индексы путей, не указанные в таблице индексации, не используются для поиска средством поиска 292.

Так, в примере, рассмотренном выше, поиск упомянутой входной строки «REGISTRY\MACHINE\SYSTEM\CONTROLSET001\ENUM\ROOT\LEGACY_KLP» выполняется с использованием узлов дерева поиска 222, хранящих индексы путей [2], [5], [3], [4]. Самый верхний узел дерева поиска 222 хранит индексы путей с [1] по [9], подстрока «\REGISTRY\MACHINE\S», содержащаяся в нем, является частью упомянутой входной строки. Эта часть строки удаляется из входной строки, поиск продолжается для строки «YSTEM\CONTROLSET001\ENUM\ROOT\LEGACY_KLP», с которой сравнивается подстрока «OFTWARE\» узла дерева поиска 222, хранящего индексы пути [4], [5], [6], [7], [8]. Индексы пути [4], [5] включены в таблицу индексации, это означает, что в дочерних узлах ветвлений дерева поиска 222 существует подстрока, заканчивающаяся на символ «Р» или содержащая маску. Однако подстрока узла «OFTWARE\» не является частью строки, для которой продолжается поиск. Поиск не продолжается с использованием дочерних узлов данного узла, а продолжается с использованием узла «YSTEM\CONTROLSET», который хранит индексы путей [0], [1], [2], [3], при этом путь [2] также входит в определенное ранее множество индексов путей. Так как строка «YSTEM\CONTROLSET» является частью строки поиска, строка поиска принимает вид «001\ENUM\ROOT\LEGACY_KLP», и поиск продолжается с использованием дочерних узлов данного узла. Дочерний узел только один, содержит среди индексов индексы пути [2], [3], которые включены в таблицу индексации. Так как подстрока этого узла имеет вид «*\» (то есть содержит маску), используются упомянутые способы поиска подстроки с использованием масок. Так, в результате такого поиска подстрока «001\» эквивалентна подстроке «*\». Входная строка принимает вид «ENUM\ROOT\LEGACY_KLP», и поиск продолжается. Узел «SERVICES\KL» не содержит индекс пути, входящий в определенное ранее множество индексов путей, поэтому поиск с использованием данного узла не производится. Узел с индексом «ENUM\ROOT\LEGACY_KL» содержит индексы путей [2], [3], входящие в определенное ранее множество индексов путей, подстрока «ENUM\ROOT\LEGACY_KL» узла является частью строки для поиска. В результате строка для поиска принимает вид «Р». В определенное ранее множество индексов путей узлов не входит узел «IF», но входят узлы «ОР» и «?», поэтому происходит поиск подстроки узла «ОР» в строке поиска. Поиск не успешен, далее происходит поиск подстроки узла «?» в строке поиска. Так как подстрока этого узла имеет вид «?» (то есть содержит маску), используются упомянутые способы поиска подстроки с использованием масок. Так, в результате такого поиска подстрока «Р» эквивалентна подстроке «?». Таким образом, упомянутая входная строка найдена средством поиска 292 в дереве поиска 222, то есть описана подстроками и масками, хранящимися в узлах дерева поиска 222.

Функциональность средства построения дерева 291 и средства поиска 292 может быть реализована исключительно аппаратными средствами, а также в виде комбинации, где часть функциональности реализована программными средствами, а часть - аппаратными. В некоторых вариантах реализации программная часть функциональности упомянутых средств может быть исполнена на процессоре компьютера общего назначения (пример изображен на Фиг. 3).

Фиг. 3 представляет пример компьютерной системы общего назначения, персональный компьютер или сервер 20, содержащий центральный процессор 21, системную память 22 и системную шину 23, которая содержит разные системные компоненты, в том числе память, связанную с центральным процессором 21. Системная шина 23 реализована, как любая известная из уровня техники шинная структура, содержащая в свою очередь память шины или контроллер памяти шины, периферийную шину и локальную шину, которая способна взаимодействовать с любой другой шинной архитектурой. Системная память содержит постоянное запоминающее устройство (ПЗУ) 24, память с произвольным доступом (ОЗУ) 25. Основная система ввода/вывода (BIOS) 26 содержит основные процедуры, которые обеспечивают передачу информации между элементами персонального компьютера 20, например, в момент загрузки операционной системы с использованием ПЗУ 24.

Персональный компьютер 20 в свою очередь содержит жесткий диск 27 для чтения и записи данных, привод магнитных дисков 28 для чтения и записи на сменные магнитные диски 29 и оптический привод 30 для чтения и записи на сменные оптические диски 31, такие как CD-ROM, DVD-ROM и иные оптические носители информации. Жесткий диск 27, привод магнитных дисков 28, оптический привод 30 соединены с системной шиной 23 через интерфейс жесткого диска 32, интерфейс магнитных дисков 33 и интерфейс оптического привода 34 соответственно. Приводы и соответствующие компьютерные носители информации представляют собой энергонезависимые средства хранения компьютерных инструкций, структур данных, программных модулей и прочих данных персонального компьютера 20.

Настоящее описание раскрывает реализацию системы, которая использует жесткий диск 27, сменный магнитный диск 29 и сменный оптический диск 31, но следует понимать, что возможно применение иных типов компьютерных носителей информации 56, которые способны хранить данные в доступной для чтения компьютером форме (твердотельные накопители, флеш карты памяти, цифровые диски, память с произвольным доступом (ОЗУ) и т.п.), которые подключены к системной шине 23 через контроллер 55.

Компьютер 20 имеет файловую систему 36, где хранится записанная операционная система 35, а также дополнительные программные приложения 37, другие программные модули 38 и данные программ 39. Пользователь имеет возможность вводить команды и информацию в персональный компьютер 20 посредством устройств ввода (клавиатуры 40, манипулятора «мышь» 42). Могут использоваться другие устройства ввода (не отображены): микрофон, джойстик, игровая консоль, сканнер и т.п. Подобные устройства ввода по своему обычаю подключают к компьютерной системе 20 через последовательный порт 46, который в свою очередь подсоединен к системной шине, но могут быть подключены иным способом, например, при помощи параллельного порта, игрового порта или универсальной последовательной шины (USB). Монитор 47 или иной тип устройства отображения также подсоединен к системной шине 23 через интерфейс, такой как видеоадаптер 48. В дополнение к монитору 47, персональный компьютер может быть оснащен другими периферийными устройствами вывода (не отображены), например колонками, принтером и т.п.

Персональный компьютер 20 способен работать в сетевом окружении, при этом используется сетевое соединение с другим или несколькими удаленными компьютерами 49. Удаленный компьютер (или компьютеры) 49 являются такими же персональными компьютерами или серверами, которые имеют большинство или все упомянутые элементы, отмеченные ранее при описании существа персонального компьютера 20, представленного на Фиг. 3. В вычислительной сети могут присутствовать также и другие устройства, например маршрутизаторы, сетевые станции, пиринговые устройства или иные сетевые узлы.

Сетевые соединения могут образовывать локальную вычислительную сеть (LAN) 50 и глобальную вычислительную сеть (WAN). Такие сети применяются в корпоративных компьютерных сетях, внутренних сетях компаний и, как правило, имеют доступ к сети Интернет. В LAN- или WAN-сетях персональный компьютер 20 подключен к локальной сети 50 через сетевой адаптер или сетевой интерфейс 51. При использовании сетей персональный компьютер 20 может использовать модем 54 или иные средства обеспечения связи с глобальной вычислительной сетью, такой как Интернет. Модем 54, который является внутренним или внешним устройством, подключен к системной шине 23 посредством последовательного порта 46. Следует уточнить, что сетевые соединения являются лишь примерными и не обязаны отображать точную конфигурацию сети, т.е. в действительности существуют иные способы установления соединения техническими средствами связи одного компьютера с другим.

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