System and method for identifying a file path using tree data structure

• US 9,875,248 B2
• Filed: 06/19/2015
• Issued: 01/23/2018
• Est. Priority Date: 03/31/2015
• Status: Active Grant

• Current Assignee: Kaspersky Lab ZAO
• Original Assignee: Lab A.O. Kaspersky
• Inventors: Levchenko, Vyacheslav I.
• Primary Examiner(s): Parsons, Theodore C.
• Assistant Examiner(s): DE JESUS LASSALA, CARLOS MANUEL
• Application Number:
  US14/744,270
• Publication Number:
  US 20160292416A1
• Time in Patent Office: 949 Days
• 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 to the resource;

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

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, wherein the tree data structure comprises a nested listing of paths in the computer file system, the listing corresponding to paths permissible to access by the software application;

when 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 wherein during comparing, narrower masks are compared with the first element before broader and recursive masks;

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;

granting the software application access to the resource in the computer file system using the requested path only when the requested path is 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 1, further comprising:

prior to forming the tree data structure, calculating and preserving a number of significant characters in each mask node; and

prior to comparing an element path with at least one mask node, disregarding a mask node for comparison when the number of significant characters in the mask node are greater than the number of significant characters in the requested path.

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 to the resource;

identify a first element in the requested path to the resource;

compare the first element with a plurality of nodes in a first level of the tree data structure to identify an exact match, wherein the tree data structure comprises a nested listing of paths in the computer file system, the listing corresponding to paths permissible to access by the software application, wherein, when 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 during comparing, narrower masks are compared with the first element before broader and recursive masks, wherein, when 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; and

wherein the hardware processor is further configured to grant the software application access to the resource in the computer file system using the requested path only when the requested path is 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 8, wherein the hardware processor is further configured to:

prior to forming the tree data structure, calculate and preserve a number of significant characters in each mask node; and

prior to comparing an element path with at least one mask node, disregard a mask node for comparison when the number of significant characters in the mask node are greater than the number of significant characters in the requested path.

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 to the resource;

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

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, wherein the tree data structure comprises a nested listing of paths in the computer file system, the listing corresponding to paths permissible to access by the software application;

when 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 wherein during comparing, narrower masks are compared with the first element before broader and recursive masks;

when 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; and

granting the software application access to the resource in the computer file system using the requested path only when the requested path is 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 15, wherein the instructions further comprise:

prior to forming the tree data structure, calculating and preserving a number of significant characters in each mask node; and

prior to comparing an element path with at least one mask node, disregarding a mask node for comparison when the number of significant characters in the mask node are greater than the number of significant characters in the requested path.