Resource access filtering system and database structure for use therewith

• US 8,250,081 B2
• Filed: 01/18/2008
• Issued: 08/21/2012
• Est. Priority Date: 01/22/2007
• Status: Active Grant

• Current Assignee: Forcepoint LLC
• Original Assignee: Websense UK Ltd. (Forcepoint LLC)
• Inventors: Nash, Alistair
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US12/523,987
• Publication Number:
  US 20100217771A1
• Time in Patent Office: 1,677 Days
• Field of Search: 707/754, 707/747, 707/698, 707/999.009, 711/216, 709/201, 713/175, 726/2, 726/22, 726/26, 370/395.32
• US Class Current: 707/754
• 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:

one or more server devices, in combination, comprising;

a generator unit arranged to create a database structure, wherein the generator unit comprises

a categorization unit arranged to provide a plurality of resource identifiers each associated with a respective category code,

a hashing unit arranged to hash each of the plurality of resource identifiers to provide a hash value, and to divide the hash value into at least first and second hash portions, and

a storing unit arranged to output the database structure including at least a hash array and a main data section, wherein the main data section comprises the second hash portions and the respective category codes divided amongst a plurality of main data blocks, and the hash array comprises the first hash portions each associated with a pointer to a respective one of the main data blocks in the main data section; and

a filter unit arranged to control access to a resource with reference to a category code obtained from the database structure according to a demanded resource identifier, wherein the filtering unit comprises

a communication unit arranged to obtain the demanded resource identifier in relation to a resource access request made by the client device,

a database access unit arranged to return a category code appropriate to the demanded resource identifier from the database structure, by generating a search hash value based on the resource identifier and dividing the search hash value into at least first and second hash portions, identifying a respective main data block in the main data section of the database structure by consulting the hash array using the first hash portion and retrieving the category code from the respective main data block according to the second hash portion, and

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

wherein the hashing unit is arranged to divide each of the hash values into at least the first and second hash portions and a third hash portion, and the storing unit is arranged to discard each of the third hash portions; and

the database access unit is arranged to divide the search hash value derived from the demanded resource identifier into corresponding at least the first and second hash portions and a third hash portion.

2. The resource access filtering system of claim 1, wherein the storing unit is arranged to provide the hash array as an index comprising a set of hash index entries based on the first hash portions, wherein each of the hash index entries comprises the pointer identifying a respective one of the main data blocks in the main data section.

3. The resource access filtering system of claim 2, wherein each of the hash index entries further comprises a length value of the respective main data block in the main data section, whereby the pointer and the length value together select the respective main data block from the main data section.

4. The resource access filtering system of claim 1, wherein the main data section comprises a plurality of records, wherein each record comprises a respective one of the second hash portions and the associated category code for a given one of the plurality of resource identifiers.

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

the storing unit is further arranged to provide a page data section and wherein each record in the main data section further comprises a page index which indexes a page data block in the page data section comprising one or more page data strings and one or more associated page category codes;

the communication unit is arranged to obtain the demanded resource identifier including a demanded page; and

the database access unit is arranged to receive the demanded page and to compare the demanded page against the page data strings in the respective page data block and return the associated page category code.

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

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

the storing unit is further arranged to provide a conflict data section comprising the category code and an undivided hash value of at least one of a first resource identifier and a second resource identifier for which the first and second hash portions thereof conflict, and wherein at least one of the records in the main data section for the first and second resource identifiers indicates that the conflict data section contains the undivided hash value; and

the database access unit consults the conflict data section when the respective record in the main data section for the demanded resource identifier so indicates.

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

the filter unit comprises at least a faster-access primary storage device and a slower-access secondary storage device; and

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

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

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

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

the generator unit further comprises an updater unit arranged to produce an update structure; and

the filter unit is arranged to apply the update structure to a current copy of the database structure to produce an updated new database structure incorporating a plurality of desired updates;

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

11. The resource access filtering system of claim 10, wherein the update structure includes at least:

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

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

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

12. The resource access filtering system of claim 11, wherein the position parameter 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.

13. The resource access filtering system of claim 10, wherein the storing unit is further arranged to provide a page data section, and the updater unit is arranged to provide the update structure including a page update section having a list of page update commands each followed by one or more page update parameters to insert, modify or delete a respective page string, and the page update commands are sorted by the first hash portion and then by the page string.

14. The resource access filtering system of claim 10, wherein the storing unit is further arranged to provide a conflict data section, and the updater unit is arranged to provide the update structure including a conflict update section having a list of conflict update commands each followed by one or more conflict update parameters to insert, modify or delete a respective undivided hash value, and the conflict update commands are sorted by the undivided hash values.

15. The resource access filtering system of claim 10, wherein the filter unit is arranged to update the database structure by copying a current live copy of the database structure in a plurality of chunks whilst applying the update commands separately in turn to each of the copied chunks to produce the updated new database structure.

16. The resource access filtering system of claim 1, wherein the resource identifiers identify resources in a computing network.

17. The resource access filtering system of claim 1, wherein the resource identifiers comprise Uniform Resource Locators.

18. The resource access filtering system of claim 1, wherein the resource identifiers comprise at least a host portion and the hash unit hashes the host portion to provide the hash value.

21. The system of claim 1, further comprising:

a client computer, comprising;

client unit arranged to request access to the resource with reference to the demanded resource identifier.

19. A filter apparatus to control access to resources in a computing system, comprising:

a processor configured to;

provide a plurality of resource identifiers, each associated with a respective category code;

hash each of the plurality of resource identifiers to provide a hash value, and to divide the hash value into at least first and second hash portions; and

output the database structure to a memory, said output data structure including at least a hash array and a main data section, wherein the main data section comprises the second hash portions and the respective category codes divided amongst a plurality of main data blocks, and the hash array comprises the first hash portions each associated with a pointer to a respective one of the main data blocks in the main data section,

control access by a client device to a resource with reference to a category code obtained from the database structure according to a demanded resource identifier; and

obtain the category code appropriate to the demanded resource identifier from the database structure, by generating a search hash value based on the demanded resource identifier and dividing the search hash value into at least first and second hash portions, identifying a respective main data block in a main data section of the database structure by consulting the hash array using the first hash portion, and retrieving the category code from the respective main data block according to the second hash portion.

22. The apparatus of claim 19, wherein the hash array does not comprise the second hash portions.

23. The filter apparatus of claim 19, wherein the main data block is identified by consulting the hash array using only the first hash portion.

20. A computer implemented method of controlling access by a client device to a demanded resource identifier:

providing a plurality of resource identifiers each associated with a respective category code;

hashing each of the plurality of resource identifiers to provide a respective hash value and dividing the respective hash value into at least a first hash portion and a second hash portion; and

storing at least a main hash array and a main data section in the database structure, wherein the main data section comprises a plurality of main data blocks each comprising a set of the second hash portions associated with the respective category codes, and the main hash array comprises the first hash portions each associated with a reference to a respective one of the plurality of main data blocks in the main data section,

receiving the demanded resource identifier from the client device which identifies a resource in a computing system;

creating a hash value based on the resource identifier and dividing the hash value into at least first and second hash portions;

identifying a main data block in a main data section of the database structure by consulting a hash array using the first hash portion; and

retrieving a category code from the identified main data block according to the second hash portion

controlling access by the client device to the demanded resource identifier based, at least in part, on the category code.

24. The method of claim 20, wherein the main hash array does not comprise the second hash portions.

25. The method of claim 20, wherein the main data block is identified without using the second hash portion.