Blocked XOR filter for blacklist filtering

Patent metadata

Field	Value
Publication number	US-11968175-B2
Application number	US-202217568370-A
Country	US
Kind code	B2
Filing date	Jan 4, 2022
Priority date	Jan 4, 2022
Publication date	Apr 23, 2024
Grant date	Apr 23, 2024

Abstract

A method of filtering a URL against a blacklist includes receiving at least a portion of a Uniform Resource Locator (URL), and determining which of a plurality of XOR filters is applicable to the received at least a portion of a URL, where each of the plurality of XOR filters represents a different portion of a URL blacklist. At least a portion of a URL is forwarded to the applicable one of the plurality of XOR filters, and the at least a portion of the URL is processed in the applicable one of the plurality of XOR filters to produce an output indicating whether the URL is likely on the blacklist.

First claim

The invention claimed is:

1. A method of filtering a URL against a blacklist, comprising:
receiving at least a portion of a Uniform Resource Locator (URL);
determining which of a plurality of XOR filters is applicable to the received at least a portion of a URL, each of the plurality of XOR filters representing a different portion of a URL blacklist;
forwarding the at least a portion of a URL to the applicable one of the plurality of XOR filters; and
processing the at least a portion of the URL in the applicable one of the plurality of XOR filters to produce an output indicating whether the URL is likely on the blacklist.

2. The method of filtering a URL against a blacklist of claim 1 , wherein the plurality of XOR filters have similar size.

3. The method of filtering a URL against a blacklist of claim 1 , wherein the plurality of XOR filters have a similar false positive detection rate.

4. The method of filtering a URL against a blacklist of claim 1 , wherein the plurality of XOR filters do not have false negative detections.

5. The method of filtering a URL against a blacklist of claim 1 , further comprising hashing the at least a portion of the URL to determine which of the plurality of XOR filters is applicable to the received at least a portion of a URL.

6. The method of filtering a URL against a blacklist of claim 1 , wherein checking at least a portion of a URL comprises check multiple compositions of the URL.

7. The method of filtering a URL against a blacklist of claim 1 , wherein the plurality of XOR filters are constructed after the inputs from the blacklist are hashed and grouped.

8. The method of filtering a URL against a blacklist of claim 7 , wherein the sizes of the plurality of XOR filters are allocated based on the number of inputs from the blacklist allocated to each XOR filter.

9. The method of filtering a URL against a blacklist of claim 8 , wherein if an XOR filter constructed using the allocated size fails to produce no false negatives, the allocated size is incrementally increased and the XOR filter is constructed again.

10. The method of filtering a URL against a blacklist of claim 1 , further comprising updating one or more of the plurality of XOR filters by selecting an XOR subfilter applicable to one or more added blacklist inputs, adding the one or more blacklist inputs to the inputs previously a part of the applicable XOR subfilter or subfilters, and reconstructing the applicable one or more XOR filters to include the one or more added blacklist inputs.

11. The method of filtering a URL against a blacklist of claim 10 , further comprising updating the one or more of the plurality of XOR filters while the filters remain operational to process the at least a portion of the URL in the applicable one of the plurality of XOR filters to produce an output indicating whether the URL is likely on the blacklist.

12. A method of updating a URL blacklist, comprising:
receiving at least a portion of a Uniform Resource Locator (URL) to be added to the blacklist;
determining which of a plurality of XOR filters is applicable to the received at least a portion of a URL to be added to the blacklist, each of the plurality of XOR filters representing a different portion of the URL blacklist; and
reformulating the XOR filter representing the determined applicable portion of the blacklist to include the received at least a portion of the URL to be added to the blacklist.

13. The method of updating a URL blacklist of claim 12 , wherein the plurality of XOR filters have similar size.

14. The method of updating a URL blacklist of claim 12 , wherein the plurality of XOR filters have a similar false positive detection rate and do not have false negative detections.

15. The method of updating a URL blacklist of claim 12 , further comprising hashing the at least a portion of the URL to determine which of the plurality of XOR filters is applicable to the received at least a portion of a URL.

16. The method of updating a URL blacklist of claim 12 , wherein the plurality of XOR filters are constructed after the inputs from the blacklist are hashed and grouped.

17. The method of updating a URL blacklist of claim 16 , wherein the sizes of the plurality of XOR filters are allocated based on the number of inputs from the blacklist allocated to each XOR filter.

18. The method of updating a URL blacklist of claim 17 , wherein if an XOR filter constructed using the allocated size fails to produce no false negatives, the allocated size is incrementally increased and the XOR filter is constructed again.

19. The method of updating a URL blacklist of claim 12 , further comprising checking at least a portion of a URL against the blacklist by checking the at least a portion of the URL against an XOR filter determined to be applicable to the URL to determine if the URL is blacklisted.

20. The method of updating a URL blacklist of claim 19 , wherein checking at least a portion of a URL comprises check multiple compositions of the URL.

Assignees

• Avast Software Sro

Inventors

• Nguyen Hai Tung
• O'Connell Christopher Joseph
• Csukas Barna
• Salomon Thomas

Classifications

• H04L63/0236 Primary

  Filtering by address, protocol, port number or service, e.g. IP-address or URL · CPC title

• H04L47/781

  Centralised allocation of resources · CPC title

• H04L63/20 Primary

  for managing network security; network security policies in general (filtering policies H04L63/0227) · CPC title

• H04L67/02

  based on web technology, e.g. hypertext transfer protocol [HTTP] · CPC title

• H04L63/101

  Access control lists [ACL] · CPC title