SYSTEM AND METHOD FOR IDENTIFYING A FILE PATH USING TREE DATA STRUCTURE

• US 20160292416A1
• Filed: 06/19/2015
• Published: 10/06/2016
• Est. Priority Date: 03/31/2015
• Status: Active Grant

• Current Assignee: Kaspersky Lab ZAO
• Original Assignee: Kaspersky Lab ZAO
• Inventors: Levchenko, Vyacheslav I.
• Granted Patent: US 9,875,248 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 21/566 Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules

Abstract

Disclosed is a system and method for identifying a path in a tree data structure having a plurality of levels. An example method includes receiving a request from a software application to access a resource in a computer file system using a requested path; identifying a first element in the requested path; comparing the first element with nodes in a first level of the tree data structure to identify an exact match; if the first element does not have an exact match, comparing the first element with at least one mask node in the first level of the tree data structure to identify a match by mask; and if the first element does not match one of mask nodes in the first level of the tree data structure, determining that the requested path is not in the tree data structure.

Claims

1. A method for identifying a path in a tree data structure having a plurality of levels, the method comprising:

receiving a request from a software application to access a resource in a computer file system using a requested path;

identifying, by a hardware processor, a first element in the requested path;

comparing, by the hardware processor, the first element with a plurality of nodes in a first level of the tree data structure to identify an exact match;

if the hardware processor does not identify an exact match between the first element and one of the plurality of nodes in the first level of the tree data structure, comparing the first element with at least one mask node in the first level of the tree data structure to identify a match by mask; and

if the hardware processor does not identify a match by mask between the first element and one of the at least one mask nodes in the first level of the tree data structure, determining that the requested path is not in the tree data structure.

2. The method of claim 1, further comprising:

if the hardware processor identifies a match between the identified first element and one of the plurality of nodes or one of the at least one mask nodes in the first level of the tree data structure, determining whether the requested path contains an additional element; and

if the requested path contains an additional element, comparing, by the hardware processor, the additional element with a plurality of nodes in a second level of the tree data structure to identify an exact match for the additional element.

3. The method of claim 2, further comprising:

if the hardware processor does not identify an exact match between the additional element and one of the plurality of nodes in the second level of the tree data structure, comparing the additional element with at least one mask node in the second level of the tree data structure to identify a match by mask; and

if the hardware processor does not identify a match by mask between the second element and one of the at least one mask nodes in the second level of the tree data structure, determining that the requested path is not in the tree data structure.

4. The method of claim 1, further comprising:

if the hardware processor does identifies a match by mask between the first element and one of the at least one mask nodes in the first level of the tree data structure, determining if there are child vertices; and

performing a search of first element of the requested path in the tree data structure if there are child vertices and determining whether the requested path contains an additional element if there are no child vertices.

5. The method of claim 1,

wherein the first element of the requested path is assigned as an initial element of the requested path and the plurality of nodes in the first level of the tree data structure are assigned as children nodes of a root node of the tree data structure, and

wherein if the hardware processor identifies a match between the initial element of the requested path and one of the plurality of nodes or one of the at least one mask nodes of the children nodes of the tree data structure, assigning the matched node as a current node and comparing a subsequent node of the requested path with children nodes of the current node to determine an exact match or a match by mask.

6. The method of claim 1, further comprising:

if the hardware processor identifies a match between the identified first element and one of the plurality of nodes or one of the at least one mask nodes in the first level of the tree data structure, identifying each additional element in the requested path; and

comparing each additional element with at least one of an exact node and a mask node in a respective additional level of the tree data structure to determine whether each additional element matches one of an exact node or a mask node.

7. The method of claim 6, further comprising granting to the software application, by the hardware processor, access to the resource in the computer file system if each additional element in the requested path matches one of an exact node or a mask node.

8. A system for identifying a path in a tree data structure having a plurality of levels, the system comprising:

a hardware processor configured to;

receive a request from a software application to access a resource in a computer file system using a requested path;

identify a first element in the requested path;

compare the first element with a plurality of nodes in a first level of the tree data structure to identify an exact match,

wherein, if the hardware processor does not identify an exact match between the first element and one of the plurality of nodes in the first level of the tree data structure, the hardware processor is further configured to compare the first element with at least one mask node in the first level of the tree data structure to identify a match by mask, and

wherein, if the hardware processor does not identify a match by mask between the first element and one of the at least one mask nodes in the first level of the tree data structure, the hardware processor is further configured to determine that the requested path is not in the tree data structure.

9. The system of claim 8,

wherein, if the hardware processor identifies a match between the identified first element and one of the plurality of nodes or one of the at least one mask nodes in the first level of the tree data structure, the hardware processor is further configured to determine whether the requested path contains an additional element, and

wherein, if the requested path contains an additional element, the hardware processor is further configured to compare the additional element with a plurality of nodes in a second level of the tree data structure to identify an exact match for the additional element.

10. The system of claim 9,

wherein, if the hardware processor does not identify an exact match between the additional element and one of the plurality of nodes in the second level of the tree data structure, the hardware processor is further configured to compare the additional element with at least one mask node in the second level of the tree data structure to identify a match by mask, and

wherein, if the hardware processor does not identify a match by mask between the second element and one of the at least one mask nodes in the second level of the tree data structure, the hardware processor is further configured to determine that the requested path is not in the tree data structure.

11. The system of claim 8,

wherein, if the hardware processor does identify a match by mask between the first element and one of the at least one mask nodes in the first level of the tree data structure, the hardware processor is further configured to:

determine if there are child vertices,

perform a search of first element of the requested path in the tree data structure if there are child vertices, and

determine whether the requested path contains an additional element if there are no child vertices.

12. The system of claim 8,

wherein the first element of the requested path is assigned as an initial element of the requested path and the plurality of nodes in the first level of the tree data structure are assigned as children nodes of a root node of the tree data structure, and

wherein if the hardware processor identifies a match between the initial element of the requested path and one of the plurality of nodes or one of the at least one mask nodes of the children nodes of the tree data structure, the hardware processor is further configured to assign the matched node as a current node and compare a subsequent node of the requested path with children nodes of the current node to determine an exact match or a match by mask.

13. The system of claim 8,

wherein, if the hardware processor identifies a match between the identified first element and one of the plurality of nodes or one of the at least one mask nodes in the first level of the tree data structure, the hardware processor is further configured to:

identify each additional element in the requested path, and

compare each additional element with at least one of an exact node and a mask node in a respective additional level of the tree data structure to determine whether each additional element matches one of an exact node or a mask node.

14. The system of claim 13, wherein the hardware processor is further configured to grant to the software application access to the resource in the computer file system if each additional element in the requested path matches one of an exact node or a mask node.

15. A non-transitory computer readable medium storing computer executable instructions for identifying a path in a tree data structure having a plurality of levels, including instructions for:

receiving a request from a software application to access a resource in a computer file system using a requested path;

identifying, by a hardware processor, a first element in the requested path;

comparing, by the hardware processor, the first element with a plurality of nodes in a first level of the tree data structure to identify an exact match;

if the hardware processor does not identify an exact match between the first element and one of the plurality of nodes in the first level of the tree data structure, comparing the first element with at least one mask node in the first level of the tree data structure to identify a match by mask; and

if the hardware processor does not identify a match by mask between the first element and one of the at least one mask nodes in the first level of the tree data structure, determining that the requested path is not in the tree data structure.

16. The non-transitory computer readable medium of claim 15, further comprising:

if the hardware processor identifies a match between the identified first element and one of the plurality of nodes or one of the at least one mask nodes in the first level of the tree data structure, determining whether the requested path contains an additional element; and

if the requested path contains an additional element, comparing, by the hardware processor, the additional element with a plurality of nodes in a second level of the tree data structure to identify an exact match for the additional element.

17. The non-transitory computer readable medium of claim 16, further comprising:

if the hardware processor does not identify an exact match between the additional element and one of the plurality of nodes in the second level of the tree data structure, comparing the additional element with at least one mask node in the second level of the tree data structure to identify a match by mask; and

if the hardware processor does not identify a match by mask between the second element and one of the at least one mask nodes in the second level of the tree data structure, determining that the requested path is not in the tree data structure.

18. The non-transitory computer readable medium of claim 15, further comprising:

if the hardware processor does identifies a match by mask between the first element and one of the at least one mask nodes in the first level of the tree data structure, determining if there are child vertices; and

performing a search of first element of the requested path in the tree data structure if there are child vertices and determining whether the requested path contains an additional element if there are no child vertices.

19. The non-transitory computer readable medium of claim 15,

wherein the first element of the requested path is assigned as an initial element of the requested path and the plurality of nodes in the first level of the tree data structure are assigned as children nodes of a root node of the tree data structure, and

wherein if the hardware processor identifies a match between the initial element of the requested path and one of the plurality of nodes or one of the at least one mask nodes of the children nodes of the tree data structure, assigning the matched node as a current node and comparing a subsequent node of the requested path with children nodes of the current node to determine an exact match or a match by mask.

20. The non-transitory computer readable medium of claim 15, further comprising:

if the hardware processor identifies a match between the identified first element and one of the plurality of nodes or one of the at least one mask nodes in the first level of the tree data structure, identifying each additional element in the requested path; and

comparing each additional element with at least one of an exact node and a mask node in a respective additional level of the tree data structure to determine whether each additional element matches one of an exact node or a mask node.

21. The non-transitory computer readable medium of claim 20, further comprising granting to the software application, by the hardware processor, access to the resource in the computer file system if each additional element in the requested path matches one of an exact node or a mask node.