RESOURCE ACCESS FILTERING SYSTEM AND DATABASE STRUCTURE FOR USE THEREWITH

• US 20100217771A1
• Filed: 01/18/2008
• Published: 08/26/2010
• Est. Priority Date: 01/22/2007
• Status: Active Grant

• Current Assignee: Forcepoint LLC
• Original Assignee: Websense UK Ltd. (Forcepoint LLC)
• Inventors: Nash, Alastair
• Granted Patent: US 8,250,081 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing

Abstract

A database structure (400) stores data representing a plurality of resource identifiers (200) such as URLs in a computing system. The URLs (200) are each associated with a respective category code (310). Each of resource identifiers (200) is hashed to provide a hash value (300) which is divided into at least first and second hash portions (301, 302). The first hash portions (301) index a main hash array (410) to select a main data block (421) in a main data section (420) holding a set of the second hash portions (302) and the respective category codes (310). For security and compactness, optionally the hash value (300) is further divided to provide a third hash portion (303) which is discarded and is not used to access the database (400). A database generation apparatus, a database search apparatus and a filtering apparatus, a method of creating a database structure and a method of retrieving data from a database structure, and to a computer readable storage medium having a database structure recorded thereon are each described.

Claims

1. A resource access filtering system, comprising:

a generator unit (50) arranged to create a database structure (400), wherein the generator unit (50) comprises;

a categorization unit (51) arranged to provide a plurality of resource identifiers (200) each associated with a respective category code (310);

a hashing unit (52) arranged to hash each of the plurality of resource identifiers (200) to provide a hash value (300), and to divide the hash value (300) into at least first and second hash portions (301, 302); and

a storing unit (53) arranged to output the database structure (400) including at least a hash array (410) and a main data section (420), wherein the main data section (420) comprises the second hash portions (302) and the respective category codes (310) divided amongst a plurality of main data blocks (421), and the hash array (410) comprises the first hash portions (301) each associated with a pointer (412) to a respective one of the main data blocks (421) in the main data section (420);

a client unit (10) arranged to request access to a resource (32) with reference to a demanded resource identifier (200); and

a filter unit (40) arranged to control access to the resource (32) with reference to a category code (310) obtained from the database structure (400) according to the demanded resource identifier (200), wherein the filtering unit (40) comprises;

a communication unit (41) arranged to obtain the demanded resource identifier (200) in relation to a resource access request made by the client device (10);

a database access unit (42) arranged to return a category code (310) appropriate to the demanded resource identifier (200) from the database structure (400), by generating a search hash value (300) based on the resource identifier (200) and dividing the search hash value (300) into at least first and second hash portions (301, 302), identifying a respective main data block (421) in the main data section (420) of the database structure (400) by consulting the hash array (410) using the first hash portion (301), and retrieving the category code (310) from the respective main data block (421) according to the second hash portion (302); and

a control unit (43) arranged to determine a control action in relation to the resource access request made by the client device (10) with reference to the category code (310) obtained by the database access unit (42),

wherein the hashing unit (52) is arranged to divide each of the hash values (300) into at least the first and second hash portions (301, 302) and a third hash portion (303), and the storing unit (53) is arranged to discard each of the third hash portions (303); and

the database access unit (42) is arranged to divide the search hash value (300) derived from the demanded resource identifier (200) into corresponding at least the first and second hash portions (301, 302) and a third hash portion (303).

3. The resource access filtering system of claim 1, wherein the storing unit (53) is arranged to provide the hash array (410) as an index comprising a set of hash index entries (411) based on the first hash portions (301), wherein each of the hash index entries (411) comprises the pointer (412) identifying a respective one of the main data blocks (421) in the main data section (420).

4. The resource access filtering system of claim 3, wherein each of the hash index entries (411) further comprises a length value (413) of the respective main data block (421) in the main data section (420), whereby the pointer (412) and the length value (413) together select the respective main data block (421) from the main data section (420).

5. The resource access filtering system of claim 1, wherein the main data section (420) comprises a plurality of records (422), wherein each record (422) comprises a respective one of the second hash portions (302) and the associated category code (310) for a given one of the plurality of resource identifiers (200).

6. The resource access filtering system of claim 5, wherein:

the storing unit (53) is further arranged to provide a page data section (440), and wherein each record (422) in the main data section (420) further comprises a page index (426) which indexes a page data block (444) in the page data section (440) comprising one or more page data strings (441) and one or more associated page category codes (311);

the communication unit (41) is arranged to obtain the demanded resource identifier (200) including a demanded page (204); and

the database access unit (42) is arranged to receive the demanded page (204) and to compare the demanded page (204) against the page data strings (441) in the respective page data block (444) and return the associated page category code (311).

7. The resource access filtering system of claim 6, wherein at least one entry in the page index (426) comprises a default value which indicates that there are no page data strings (441) in the page data section (440) for a particular one of the records (422).

8. The resource access filtering system of claim 1, wherein:

the storing unit (53) is further arranged to provide a conflict data section (430) comprising the category code (310) and an undivided hash value (300) of at least one of a first resource identifier (200) and a second resource identifier (200) for which the first and second hash portions (301,302) thereof conflict, and wherein at least one of the records (422) in the main data section (420) for the first and second resource identifiers (200) indicates that the conflict data section (430) contains the undivided hash value (300); and

the database access unit (42) consults the conflict data section (430) when the respective record (422) in the main data section (420) for the demanded resource identifier (200) so indicates.

9. The resource access filtering system of claim 1, wherein:

the filter unit (40) comprises at least a faster-access primary storage device (44) and a slower-access secondary storage device (45); and

in a first memory-based mode, the entire database structure (400) is loaded into the faster-access primary storage device (44) and is initialized by converting each of the pointers (412) in the main hash array (410) into memory location references which directly or indirectly reference memory address locations where the main data blocks (421) of the main data section (420) are loaded, and is accessed in the faster-access primary storage device (44); and

in a second shared-access mode, the main hash array (410) is loaded into the faster-access primary storage device (44), whilst at least the main data section (420) is retained on the secondary storage device (45) and is initialized by converting each of the pointers (412) in the main hash array (410) into offsets from a start of a file of the database structure (400) as stored on the secondary storage (45), and is accessed by obtaining the converted offset (412) from the main hash array (410) in the primary storage device (44) and loading only the required data block (421) from the main data section (420) into the primary storage device (44).

10. The resource access filtering system of claim 9, wherein the filter unit (40) is selectively operated in either the first memory-based mode or in the second shared-access mode.

11. The resource access filtering system of claim 1, wherein:

the generator unit (50) further comprises an updater unit (54) arranged to produce an update structure (500); and

the filter unit (40) is arranged to apply the update structure (500) to a current copy of the database structure (400a) to produce an updated new database structure (400b) incorporating a plurality of desired updates;

wherein the update structure (500) comprises at least a main update section (520) comprising a list of update commands (521) each followed by one or more parameters (522) to insert, modify or delete a respective record (422) in the main data section (420) and the update commands (521) are sorted such that the order of the commands (521) corresponds to the order of the records (422) in the main data section (420).

12. The resource access filtering system of claim 11, wherein the update structure (500) includes at least:

an INSERT command which instructs the filter unit (40) to insert a new record (422) in the main data section (420) at a location identified by a position parameter (522) giving an offset position where the instructed command is to be performed, and also provides parameters (522) for the second hash portion (302) and the category code (310) of the new record (422) and the first hash portion (301) such that the main hash array (410) is recalculated by the filter unit (40) to allow for the new record (422);

a MODIFY command which instructs the filter unit (40) to modify an existing record (422) in the main data section (420) wherein the parameters (522) provide new data to be written into the database structure (400) to replace the current data of the relevant record (422); and

a DELETE command which instructs the filter unit (40) to delete a record (422) from the main data section (420) of database structure (400) at a location identified by a position parameter (522) giving an offset position where the instructed command is to be performed, and a parameter (522) comprising the respective first hash portion (301), such that the filter unit (40) recalculates the main hash array (410) to account for the now deleted record (422).

13. The resource access filtering system of claim 12, wherein the position parameter (522) gives a relative position which is relative to a position of a previous command or, if no previous commands have been given, is relative to a default starting position.

14. The resource access filtering system of claim 11, wherein the storing unit (53) is further arranged to provide a page data section (440), and the updater unit (54) is arranged to provide the update structure (500) including a page update section (540) having a list of page update commands (541) each followed by one or more page update parameters (542) to insert, modify or delete a respective page string (441), and the page update commands (541) are sorted by the first hash portion (301) and then by the page string (441).

15. The resource access filtering system of claim 11, wherein the storing unit (53) is further arranged to provide a conflict data section (430), and the updater unit (54) is arranged to provide the update structure (500) including a conflict update section (530) having a list of conflict update commands (531) each followed by one or more conflict update parameters (532) to insert, modify or delete a respective undivided hash value (300), and the conflict update commands (531) are sorted by the undivided hash values (300).

16. The resource access filtering system of claim 11, wherein the filter unit (40) is arranged to update the database structure (400) by copying a current live copy of the database structure (400a) in a plurality of chunks whilst applying the update commands (521) separately in turn to each of the copied chunks to produce the updated new database structure (400b).

17. The resource access filtering system of claim 1, wherein the resource identifiers (200) identify resources in a computing network.

18. The resource access filtering system of claim 1, wherein the resource identifiers (200) comprise Uniform Resource Locators.

19. The resource access filtering system of claim 1, wherein the resource identifiers (200) comprise at least a host portion (202) and the hash unit (52) hashes the host portion (202) to provide the hash value (300).

2. (canceled)

20. A generator apparatus (50) to create a database structure (400), comprising:

a processor configured to;

provide a plurality of resource identifiers (200) each associated with a respective category code (310);

hash each of the plurality of resource identifiers (200) to provide a hash value (300), and to divide the hash value (300) into at least first and second hash portions (301, 302); and

output the database structure (400) to a memory, said output data structure including at least a hash array (410) and a main data section (420), wherein the main data section (420) comprises the second hash portions (302) and the respective category codes (310) divided amongst a plurality of main data blocks (421), and the hash array (410) comprises the first hash portions (301) each associated with a pointer (412) to a respective one of the main data blocks (421) in the main data section (420).

21. A filter apparatus (40) to control access to resources (32) in a computing system, comprising:

a filter unit (40) arranged to control access by a client device (10) to a resource (32) with reference to a category code (310) obtained from a database structure (400) according to a demanded resource identifier (200); and

a database access unit (42) arranged to obtain the category code (310) appropriate to the demanded resource identifier (200) from the database structure (400), by generating a search hash value (300) based on the demanded resource identifier (200) and dividing the search hash value (300) into at least first and second hash portions (301, 302), identifying a respective main data block (421) in a main data section (420) of the database structure (400) by consulting the hash array (410) using the first hash portion (301), and retrieving the category code (310) from the respective main data block (421) according to the second hash portion (302).

22. A computer readable storage medium having recorded thereon a database structure (400) storing data representing a plurality of resource identifiers (200) each associated with a respective category code (310), comprising:

a main data section (420) having a plurality of main data blocks (421), wherein each of the plurality of main data blocks (421) comprises a plurality of second hash portions (302) and each of the plurality of second hash portions (302) is associated with a respective category code (310); and

a main hash array (410) comprising a plurality of first hash portions (301), wherein each of the first hash portions (301) is associated with a reference pointer (412) to a respective one of the plurality of main data blocks (421) in the main data section (420);

wherein each of the first hash portions (301) and the second hash portions (302) is divided from a hash value (300) derived a respective one of the plurality of resource identifiers (200).

23. A method of creating a database structure (400), comprising the computer-implemented steps of:

providing a plurality of resource identifiers (200) each associated with a respective category code (310);

hashing each of the plurality of resource identifiers (200) to provide a respective hash value (300) and dividing the respective hash value (300) into at least a first hash portion (301) and a second hash portion (302); and

storing at least a main hash array (410) and a main data section (420) in the database structure (400), wherein the main data section (420) comprises a plurality of main data blocks (421) each comprising a set of the second hash portions (302) associated with the respective category codes (310), and the main hash array (410) comprises the first hash portions (301) each associated with a reference (412) to a respective one of the plurality of main data blocks (421) in the main data section (420).

24. A method of retrieving data from a database structure (400), comprising the computer-implemented steps of:

receiving a demanded resource identifier (200) which identifies a resource (32) in a computing system;

creating a hash value (300) based on the resource identifier (200) and dividing the hash value (300) into at least first and second hash portions (301, 302);

identifying a main data block (421) in a main data section (420) of the database structure (400) by consulting a hash array (410) using the first hash portion (301); and

retrieving a category code (310) from the identified main data block (421) according to the second hash portion (302).

25-30. -30. (canceled)