Способ поиска пути по дереву

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

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

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

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

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

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

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

Заявки US 8880507 и US 7603346 описывают способ поиска длиннейшего соответствия префикса (англ. LPM, Longest Prefix Match) с использованием бинарных деревьев.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг. 3 отображает способ поиска пути по дереву масок путей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тип дерева поиска - не бинарное, имеет более двух потомков. Дерево поиска начинается с корневого узла 210, по своим связям представляет дерево имен файлов, где информация об элементах пути располагается в узлах (вершинах) дерева 220. Элемент пути - это строка, содержащая имя отдельного файла, каталога, домена какого-либо уровня. Путь в общем случае состоит из нескольких элементов, соединенных метасимволами -разделителями. Например, путь «C:\Windows\readme.txt» содержит 3 элемента «C:», «Windows», «readme.txt». Метасимволом разделителя элементов пути может выступать «\» или «/» и их комбинации, например, "\\".

В частном варианте реализации дерево путей - это двумерное хранилище данных, которое описывается двухсвязным списком по высоте 230 и односвязными на подуровнях 240.

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

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

Метасимволами маски элемента пути могут являться, например, «*» и «?». При этом «*» обозначает группу любых символов, не совпадающих со входным именем при поиске. Метасимвол «?» обозначает один символ, не совпадающий с входным именем при поиске.

В частном варианте реализации дерево может содержать следующие маски:

- «обычные», не рекурсивные, которые описывают элементы пути только на данном уровне дерева 250 (например, маска, описывающая имена файлов, при этом вершина, содержащая данную маску, не будет иметь потомков);

- «рекурсивные», которые описывают элементы пути на данном и дочернем уровнях дерева 260 (например, маска, описывающая имена каталогов, при этом вершина, содержащая данную маску, может иметь потомков).

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

То есть, один и тот же путь может быть описан разными масками. Например, путь «C:\Windows\System32\file.txt» может быть описан как с помощью маски «C:\Windows\System32\*.txt», так и с помощью «C:\Windows\System*\file.*».

Указанные маски не взаимоисключающие, однако могут охватывать один и тот же набор файлов. В случае если в дереве существует маска, которая охватывает набор файлов, описываемый добавляемой маской, и добавляемая маска описывает более широкий набор путей, существующая маска удаляется из дерева. Например, если в дереве была описана маска «C:\Windows\System??\*.txt», а добавляется «C:\Windows\System*\*.*», то существующая описанная маска удаляется, а новая добавляется в дерево. То есть, существующая последовательность вершин и листьев, соответствующая описанной маске, удаляется из дерева, а новая последовательность, соответствующая новой маске, добавляется в дерево. С другой стороны, если добавляется более узкая маска по сравнению с существующей в дереве, то структура дерева не меняется.

Фиг. 3 отображает способ поиска пути к файлу по дереву масок путей.

Поиск совпадения искомого пути (путь, который нужно найти в дереве) осуществляется поэлементным сравнением пути от корневого узла дерева. На этапе 310 выделяют элемент искомого пути через поиск до символа разделителя пути (например, символа «\» или «/»). Далее на этапе 320 сравнивают выделенный элемент по длине и точному содержимому с узлами текущего уровня дерева (все дочерние узлы). Далее на этапе 330, если найдено совпадение, но искомый путь больше не содержит компонентов на этапе сравнения 340, совпадение считается полным, и поиск прекращается 350. Иначе текущий дочерний узел становится узлом начала поиска, и происходит переход к шагу 310. Если на этапе 330 точное совпадение не найдено, на этапе 360 элемент искомого пути сравнивается по маске с узлами текущего уровня дерева. Если совпадение по маске не найдено на этапе 370, происходит возврат к этапу 340, если элемент пути последний, то поиск прекращается на этапе 350. Если на этапе 370 найдено совпадение по маске, и существуют дочерние вершины 380, начинается поиск остатка входного пути по дочерним вершинам дерева 390. Начинается такой поиск с выделения нового элемента остатка искомого пути 310. Если на этапе 370 найдено совпадение по маске и отсутствуют дополнительные вершины, а выделенный элемент пути -последний, поиск прекращается на этапе 350. При этом, если элемент искомого пути конечный, а вершина, с которой совпал конечный элемент точно или по маске не имеет дочерних вершин, считается, что совпадение найдено. Если элемент пути не совпал ни точно, ни по маске с вершинами текущего дерева, считается, что совпадение не найдено.

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

Среднее время прямого поиска в дереве описывается так:

Т=М*f*D/2, где:

f - среднее время сравнения одного компонента;

М - среднее количество дочерних масок для данной вершины дерева;

D - количество компонентов входного пути.

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

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

Фиг. 4 представляет пример компьютерной системы общего назначения, персональный компьютер или сервер 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, представленного на Фиг. 4. В вычислительной сети могут присутствовать также и другие устройства, например, маршрутизаторы, сетевые станции, пиринговые устройства или иные сетевые узлы.

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

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