System, method and apparatus for use in monitoring or controlling internet access

• US 8,135,831 B2
• Filed: 09/14/2009
• Issued: 03/13/2012
• Est. Priority Date: 09/09/2004
• Status: Active Grant

• Current Assignee: Forcepoint LLC
• Original Assignee: Websense UK Ltd. (Forcepoint LLC)
• Inventors: Pettener, Ian James, Nash, Alistair H., Sinclair, John W.
• Primary Examiner(s): LAZARO, DAVID R
• Application Number:
  US12/558,961
• Publication Number:
  US 20100005165A1
• Time in Patent Office: 911 Days
• Field of Search: 709/224, 709/203, 709/217, 726 11- 13, 707/736, 707/741, 707/747
• US Class Current: 709/224
• CPC Class Codes: G11B 20/00847 wherein the usage restriction is defined by a licence file
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/30 Managing network names, e.g. use of aliases or nicknames name-to-address mapping H04L61/45
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 63/102 Entity profiles
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An apparatus method and system are described for categorizing Uniform Resource Locators (URLs) when accessing the Internet 20 from a client 12. A request message 500 is generated to request categorization of a specified URL, and a category is provided in a reply message 600. The specified URL and the category are added to a category cache. In a second or subsequent instance of a URL request referring to the specified URL, the category is determined from the category cache. This reduces communication traffic in a network such as the Internet 20.

Claims

1. A cache data structure implemented on a non-transitory, computer-readable medium, comprising:

a hash array comprising one or more index elements, each index element comprising a host tree pointer and a hash key derived from a stored URL, wherein hashed host portions of at least two different URLs correspond to the same index element, wherein the same index element comprises a pointer to a combined host tree and age list; and

wherein the combined host tree and age list comprises one or more tree nodes, wherein each tree node comprises URL data representing a specified URL and a category code corresponding to the URL data, and wherein each tree node comprises a next node pointer referring to a previous node, the next node comprising an age older than the previous node; and

one or more host trees depending from said host tree pointers of the index elements of the hash array, each host tree comprising one or more tree nodes each holding URL data representing stored URLs and associated category codes.

2. The cache data structure of claim 1, wherein each tree node comprises a host string holding a host portion of a stored URL and an associated category code, and a page array of zero or more page strings each page string holding a page portion and an associated category code.

3. The cache data structure of claim 2, wherein each page string comprises a children flag denoting whether category codes are available for children of a stored URL path portion.

4. The cache data structure of claim 3, wherein the tree list is a balanced red-black tree and each tree node further comprises a red-black flag.

5. The cache data structure of claim 1, wherein each tree node further comprises a parent node pointer, a left node pointer, and a right node pointer.

6. A non-transitory computer readable medium having a data structure stored thereon defining a cache structure comprising:

a hash array comprising one or more index elements, each index element comprising a host tree pointer and a hash key derived from a stored URL; and

one or more host trees depending from said host tree pointers of the index elements of the hash array, each host tree comprising one or more tree nodes each holding URL data representing stored URLs and associated category codes, wherein hashed host portions of at least two different URLs correspond to the same index element, wherein the same index element comprises a pointer to a combined host tree and age list; and

an age list to list each of the tree nodes by age, wherein the age list comprises, within each tree node, a next pointer and a previous pointer which refer to a next older tree node and a previous newer tree node, respectively.

7. The cache data structure of claim 6, wherein each tree node comprises a host string holding a host portion of a stored URL and an associated category code, and a page array of zero or more page strings each page string holding a page portion and an associated category code.

8. The cache data structure of claim 7, wherein each page string comprises a children flag denoting whether category codes are available for children of a stored URL path portion.

9. The cache data structure of claim 8, wherein the tree list is a balanced red-black tree and each tree node further comprises a red-black flag.

10. The cache data structure of claim 6, wherein each tree node further comprises a parent node pointer, a left node pointer, and a right node pointer.

11. A non-transitory computer readable medium having a data structure stored thereon defining a cache structure comprising:

a hash array wherein a host portion of a specified URL is hashed to identify a corresponding index element in the hash array; and

a combined host tree and age list stored at the identified corresponding index element in the hash array associated with the host portion of the specified URL,

wherein each tree node of the host tree comprises URL data representing a specified URL and a corresponding category, and each tree node further comprises a next pointer and a previous pointer which refer to a next older tree node and a previous newer tree node, respectively, to form an age list, and

wherein the hashed host portions of at least two different URLs correspond to the same index element, wherein the same index element comprises a pointer to a combined host tree and age list.

12. The cache data structure of claim 11 wherein the hash array has a predetermined length.

13. The cache data structure of claim 12, wherein the predetermined length of the hash array is set by a variable which is input from a control panel during use of the computer readable medium.

14. The cache data structure of claim 11, wherein each specified URL comprises a host portion and a path portion, and each tree node comprises a host string holding the host portion, and an array of one or more strings each representing a path portion depending from the host portion.

15. The cache data structure of claim 14 further comprising, within each tree node, a children flag which identifies whether category codes are available for children of a specified URL host or URL path.

16. The cache data structure of claim 11 further comprising a custom cache, wherein the custom cache records a customized list of stored URLs and associated category codes.

17. The cache data structure of claim 16, wherein the custom cache comprises:

a hash array wherein the host portion of a specified URL is hashed to produce an index element in the hash array; and

a host tree wherein each tree node of the host tree comprises URL data representing a specified URL and a corresponding category code.

18. The cache data structure of claim 11, wherein each tree node comprises a host string holding a host portion of a URL and an associated category code, and a page array of zero or more page strings each page string holding a page portion and an associated category code.

19. The cache data structure of claim 18, wherein each page string further comprises a children flag identifying whether category codes are available for children of a stored path portion.

20. A non-transitory computer readable medium having a data structure stored thereon defining a cache structure comprising:

a category cache module storing a plurality of URLs and associated category codes, such that matching a specified URL against one of the stored URLs provides the category code,

wherein the category cache module is configured to store the specified URL and the category code to a category cache, the category cache comprising

a hash array wherein a host portion of the specified URL is hashed to identify a corresponding index element in the hash array; and

a combined host tree and age list stored at the identified corresponding index element in the hash array associated with the host portion of the specified URL,

wherein the hashed host portions of at least two different URLs correspond to the same index element, wherein the same index element comprises a pointer to a combined host tree and age list, and

wherein each tree node of the host tree comprises URL data representing a specified URL and a corresponding category, and each tree node further comprises a next pointer and a previous pointer which refer to a next older tree node and a previous newer tree node, respectively, to form an age list.

21. The cache data structure of claim 20, wherein to store the specified URL and the category, the category cache module is configured to:

identify the corresponding index element in the hash array;

store the URL data at the head of the age list; and

remove an oldest tree node from a tail of the age list when the category cache has reached a predetermined maximum size,

wherein, in response to receiving a second or subsequent instance of a URL request by the interface module with respect to the specified URL, the category cache module is configured to

determine the category of the specified URL from the category cache; and

move the URL data representing the specified URL to the head of the age list.

22. The cache data structure of claim 20, further comprising a custom cache which holds a customized list of stored URLs and associated category codes, such that the custom cache is searchable.

23. A cache data structure implemented on a non-transitory, computer-readable medium, comprising:

a hash array comprising one or more index elements, each index element comprising a host tree pointer and a hash key derived from a stored URL, wherein the hashed host portions of at least two different URLs correspond to the same index element;

one or more host trees depending from said host tree pointers of the index elements of the hash array, each host tree comprising one or more tree nodes each holding URL data representing stored URLs and associated category codes; and

an age list to list each of the tree nodes by age, wherein the age list comprises, within each tree node, a next pointer and a previous pointer which refer to a next older tree node and a previous newer tree node, respectively,

wherein each tree node comprises a host string holding a host portion of a stored URL and an associated category code, and a page array of zero or more page strings each page string holding a page portion and an associated category code, and

wherein each page string comprises a children flag denoting whether category codes are available for children of a stored URL path portion.