Probabilistic Set Membership Using Bloom Filters

Abstract

A method for determining whether data is included in a database is described. In one embodiment, the method may include receiving, from a remote computing device, a search request that includes a portion of a signature, comparing the portion of the signature with a plurality of signatures stored at the database, determining whether at least one match exists between the portion of the signature and the plurality of signatures, upon determining at least one match exists, identifying each match and identifying a bloom filter that includes each match, and transmitting the bloom filter to the remote computing device.

What is claimed is: 
     
         1 . A method for determining whether data is included in a database, at least a portion of the method being performed by one or more computing devices, each comprising at least one processor, the method comprising:
 receiving, from a remote computing device, a search request that includes a portion of a signature truncated to a predefined length;   comparing the portion of the signature with a plurality of signatures stored at the database;   determining whether at least one match exists between the portion of the signature and the plurality of signatures;   upon determining at least one match exists, identifying each match and generating a bloom filter that includes each match, and   taking a security action based at least in part on determining the data matches one or more malware signatures in the bloom filter.   
     
     
         2 . The method of  claim 1 , further comprising:
 generating the bloom filter based at least in part on a default false positive rate or a custom false positive rate indicated in the request.   
     
     
         3 . The method of  claim 1 , wherein the bloom filter is generated before receiving the search request based at least in part on (a) identifying a segment from the plurality of signatures stored at the database, (b) generating the bloom filter using the identified segment, and (c) determining at least a part of the segment matches the portion received in the request or determining at least a part of the portion received in the request matches the segment. 
     
     
         4 . The method of  claim 1 , further comprising transmitting the bloom filter to the remote computing device. 
     
     
         5 . The method of  claim 1 , further comprising:
 adding a new signature to the plurality of signatures in the database; and   updating the bloom filter generated before receiving the search request based at least in part on the adding of the new signature to the database.   
     
     
         6 . The method of  claim 1 , further comprising:
 including a first reference and a second reference with the bloom filter, the first reference comprising a number of matches in the bloom filter, and the second reference comprising a number of hash functions used to build the bloom filter.   
     
     
         7 . The method of  claim 1 , further comprising:
 upon determining no match is found between the portion of the signature and the plurality of signatures, sending a notification to the remote computing device indicating no match exists in the database.   
     
     
         8 . The method of  claim 1 , further comprising:
 receiving an additional portion of the signature to reduce a number of matches in the bloom filter; and   comparing the combination of the additional portion and the portion of the signature with the plurality of signatures stored at the database.   
     
     
         9 . The method of  claim 1 , wherein the predefined length is associated with a predetermined number of bits of the signature. 
     
     
         10 . The method of  claim 9 , wherein a number of bits in each of the plurality of signatures stored at the database are greater than the predetermined number of bits of the signature. 
     
     
         11 . The method of  claim 1 , wherein the portion includes at least one of a beginning portion of the signature, one or more middle portions of the signature, or an end portion of the signature, or any combination thereof. 
     
     
         12 . The method of  claim 1 , wherein the data comprises at least one of a user name, a password, an IP address, a malware signature, a threat risk score associated with a machine or user, threat activities associated with the machine or the user, suspicious behaviors associated with the machine or the user, identity information associated with the user, or a combination thereof. 
     
     
         13 . The method of  claim 12 , wherein the security action is further based at least in part on at least one of determining the threat risk score satisfies a risk score threshold, determining the threat activities satisfy a threat threshold, determining the suspicious behaviors satisfy a suspicious behaviors threshold, determining the identity information of the user has been potentially stolen, or any combination thereof. 
     
     
         14 . The method of  claim 1 , wherein the signature and each of the plurality of signatures comprise a hash within a range of 32 bits and 32,768 bits. 
     
     
         15 . The method of  claim 1 , wherein the signature comprises a hash, a cryptographic hash, or a bloom filter. 
     
     
         16 . A computing device configured for determining whether data is included in a database, comprising:
 a processor;   memory in electronic communication with the processor, wherein the memory stores computer executable instructions that when executed by the processor cause the processor to perform the steps of:
 receive, from a remote computing device, a search request that includes a portion of a signature truncated to a predefined length; 
 compare the portion of the signature with a plurality of signatures stored at the database; 
 determine whether at least one match exists between the portion of the signature and the plurality of signatures; 
 upon determining at least one match exists, identify each match and generating a bloom filter that includes each match; 
 taking a security action based at least in part on determining the data matches one or more malware signatures in the bloom filter. 
   
     
     
         17 . The computing device of  claim 16 , wherein the instructions are executable by the processor to generate the bloom filter based at least in part on a default false positive rate or a custom false positive rate indicated in the request. 
     
     
         18 . The computing device of  claim 16 , wherein the bloom filter is generated before receiving the search request based at least in part on (a) identifying a segment from the plurality of signatures stored at the database, (b) generating the bloom filter using the identified segment, and (c) determining at least a part of the segment matches the portion received in the request or determining at least a part of the portion received in the request matches the segment. 
     
     
         19 . The computing device of  claim 16 , further comprising transmitting the bloom filter to the remote computing device. 
     
     
         20 . A non-transitory computer-readable storage medium storing computer executable instructions that when executed by a processor cause the processor to perform the steps of:
 receiving, from a remote computing device, a search request that includes a portion of a signature truncated to a predefined length;   comparing the portion of the signature with a plurality of signatures stored at the database;   determining whether at least one match exists between the portion of the signature and the plurality of signatures;   upon determining at least one match exists, identifying each match and generating a bloom filter that includes each match, and   taking a security action based at least in part on determining the data matches one or more malware signatures in the bloom filter.