Abstract:
One embodiment relates to an apparatus for in-the-cloud identification of spam and/or malware. The apparatus includes computer-readable code configured to be executed by the processor so as to receive queries, the queries including hash values embedded therein. The apparatus further includes computer-readable code configured to be executed by the processor so as to detect a group of hash codes which are similar and to identify the group as corresponding to an undesirable network outbreak. Another embodiment relates to an apparatus for in-the-cloud detection of spam and/or malware. The apparatus includes computer-readable code configured to be executed by the processor so as to receive an electronic message, calculate a locality-sensitive hash based on the message, embed the locality-sensitive hash into a query, and send the query to a central analysis system via a network interface. Other embodiments, aspects and features are also disclosed.

Description:
BACKGROUND 
     1. Field of the Invention 
     The present invention relates generally to communication networks, and more particularly, but not exclusively, to techniques for identifying spam and/or malware. 
     2. Description of the Background Art 
     Problems associated with unsolicited messages in electronic mail systems and malware in computer systems are well documented. Unsolicited messages, also referred to as “spam,” are mass mailed by spammers to e-mail accounts over the Internet. Malware includes computer viruses, worms, phishing messages, and malicious scripts. 
     Various anti-spam and anti-malware techniques have been developed to combat spam and malware. For example, anti-spam software has been deployed in host computers to detect and block spam, and anti-virus software is commonly deployed in personal computers. 
     The domain name system (DNS) is a hierarchical naming system for resources on the Internet. A DNS blacklist (DNSBL) is a published list of known untrustworthy IP addresses (for example, those IP addresses linked to spamming) which may be checked to determine if an electronic mail (email) message is from an address known for sending out spam. Conversely, a DNS whitelist is a published list of known trustworthy IP addresses which may be used to avoid unnecessary false positive identifications of spam. 
     SUMMARY 
     One embodiment relates to an apparatus for in-the-cloud identification of spam and/or malware. The apparatus includes computer-readable code configured to be executed by the processor so as to receive queries, said queries including hash codes embedded therein. The apparatus further includes computer-readable code configured to be executed by the processor so as to detect a group of hash codes which are considered similar and to identify said group as corresponding to spam or malware. 
     Another embodiment relates to a method performed by executing computer-readable code on an apparatus. The apparatus receives queries that include hash codes embedded therein. The apparatus also detects a group of hash codes which are considered similar and identifies said group as corresponding to spam or malware. 
     Another embodiment relates to an apparatus for in-the-cloud detection of spam and/or malware. The apparatus includes computer-readable code configured to be executed by the processor so as to receive an electronic message, calculate a locality-sensitive hash based on the message, embed the locality-sensitive hash into a query, and send the query to an analysis system via a network interface. 
     In accordance with another embodiment of the invention, tangible computer-readable media may store computer-readable code described herein for use at a host and/or server. 
     These and other features of the present invention will be readily apparent to persons of ordinary skill in the art upon reading the entirety of this disclosure, which includes the accompanying drawings and claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a schematic diagram depicting a data communication system in which an embodiment of the invention may be utilized. 
         FIG. 2  is a schematic diagram depicting a computer apparatus which may be configured as a component in the implementation of in-the-cloud identification of spam and/or malware in accordance with an embodiment of the invention. 
         FIG. 3  is a flow chart depicting a method performed by a host engine at a host computer in accordance with an embodiment of the invention. 
         FIG. 4A  shows html tags of a first example of an image-based spam. 
         FIG. 4B  shows html tags of a second example of an image-based spam. 
         FIG. 5A  shows a locality-sensitive hash of the html tags from the first example of an image-based spam (shown in  FIG. 4A ). 
         FIG. 5B  shows a locality-sensitive hash of the html tags from the second example of an image-based spam (shown in  FIG. 4B ). 
         FIG. 6  is a flow chart depicting a method performed by an analysis system at a server to identify a group of messages as spam or malware in accordance with an embodiment of the invention. 
         FIG. 7  is a table showing an example group of messages identified as spam by an analysis system at a server in accordance with an embodiment of the invention. 
         FIG. 8  is a flow chart depicting a method performed by an analysis system to check whether or not a message is considered to be spam or malware in accordance with an embodiment of the invention. 
     
    
    
     The use of the same reference label in different drawings indicates the same or like components. 
     DETAILED DESCRIPTION 
     Applicants have determined that prior technologies to identify unsolicited messages or spam have certain disadvantages and inefficiencies. The present application discloses apparatus and methods for in-the-cloud identification of spam and/or malware, such as computer viruses, worms, phishing messages, or malicious scripts. In the present application, such spam and/or malware may be referred to jointly as undesirable network outbreaks. Advantageously, these apparatus and methods provide for the centralized monitoring of outbreaks of spam and/or malware and enable central control over the level of variants (of spam and/or malware) to be identified. 
     Referring to  FIG. 1 , a data communication system  10  according to an embodiment of the invention is shown generally. The system includes a Wide Area Network (WAN)  12 , such as an intranet or Internet, multiple Local Area Networks (LANs) (wired or wireless)  14 , and gateways  16  connecting the LANs to the WAN. Two LANs are shown interconnected via the WAN, but the WAN may interconnect any number of LANs. 
     A plurality of personal computers (PCs) or other computer hosts  20  may be connected to each LAN  14 . In accordance with an embodiment of the invention, one or more of the hosts  20  may be configured with a host engine (HE)  21 . 
     A domain name system (DNS) server  30  may be connected to the WAN  12 . The domain name system or DNS is a hierarchical naming system for resources on the Internet. In accordance with an embodiment of the invention, the DNS server  30  may be configured with an analysis system  31  and an undesirable ID data structure  32 . 
     Referring now to  FIG. 2 , there is shown a schematic diagram of a computer apparatus  200  which may be configured as a component in the implementation of in-the-cloud identification of spam in accordance with an embodiment of the invention. The computer apparatus  200  may be employed as a host computer  20 , a gateway  16 , or a DNS server  30 , for example. The computer  200  may have fewer or more components to meet the needs of a particular application. The computer  200  may include a processor  201 , such as those from the Intel Corporation of Santa Clara, Calif., or Advanced Micro Devices of Sunnyvale, Calif., for example. The computer  200  may have one or more buses  203  coupling its various components. The computer  200  may include one or more user input devices  202  (e.g., keyboard, mouse), one or more data storage devices  206  (e.g., hard drive, optical disk, USB memory), a display monitor  204  (e.g., LCD, flat panel monitor, CRT), a computer network interface  205  (e.g., network adapter, modem), and a main memory  208  (e.g., RAM). The data storage system of the computer apparatus includes the data storage devices  206  and the main memory  208 . The computer network interface  205  may be coupled to one or more data communication networks  209 , which in this example may be a LAN  14  and/or a WAN  12 . 
     In the example of  FIG. 2 , the main memory  208  includes software modules  210 . The software modules  210  may comprise computer-readable program code (i.e., software) components of a host computer  20 , a gateway  16 , or a DNS server  30 , for example. 
     The software modules  210  may be loaded from the data storage device  206  to the main memory  208  for execution by the processor  201 . In accordance with an embodiment of the invention, the software modules  210  on a host computer  20  may include a host engine (HE)  21 , and the software modules  210  on a DNS server  30  may include an analysis system  31 . In addition, the data storage device  206  on the DNS server  30  may include an undesirable ID data structure  32 . 
       FIG. 3  is a flow chart depicting a method performed by a host engine (HE)  21  at a host computer  20  in accordance with an embodiment of the invention. For example, the host computer  20  may be a personal computer (desktop or laptop) connected via a LAN  14  to the Internet. As another example, the host computer may be a cellular phone configured to communicate over a telecommunication network to the Internet. 
     As seen in  FIG. 3 , an electronic message arrives  302  at the host computer. For example, the message may be an electronic mail (email) message. Alternatively, the message may be a text message. 
     The HE (which may be configured as a software module running on the host computer) may then process  304  the message that was received. For example, if the message is an email in hypertext markup language (HTML) format, then the HE may be configured to process the message by removing the plain text and leaving the HTML tags, or, alternatively, by removing the HTML tags and leaving the plain text. Such processing may be done before the hashing algorithm to be applied. 
     The HE then calculates  306  a locality-sensitive hash by applying an appropriate hashing algorithm to the message (after post processing, if any). In accordance with an embodiment of the invention, the hashing algorithm may comprise a Nilsimsa code generator. The Nilsimsa code generator may be configured to generate Nilsimsa codes which have a fixed length of 256 bits. Nilsimsa codes are locality sensitive in that a relatively small change in the message results in a relatively small change in the corresponding Nilsimsa code. 
     The locality-sensitive hash may then be embedded  308  in a query, and the query may be sent  310  to an analysis system. For example, a domain name system (DNS) query may be embedded with the locality-sensitive hash, and the DNS query sent out by the host computer to be received by a DNS server configured with the analysis system. Subsequently, an answer to the query may be received  312  by the HE from the analysis system. 
       FIG. 4A  shows html code of a first example of an image-based spam. This first spam is an unsolicited electronic mail message which may be received by a user and which displays an unsolicited advertisement in an image. Similarly,  FIG. 4B  shows html code of a second example of an image-based spam. This second spam is an unsolicited electronic mail message which may be received by another user and may actually display the same image as the first spam. 
       FIG. 5A  shows a locality-sensitive hash of the html code from the first example of an image-based spam (shown in  FIG. 4A ). Similarly,  FIG. 5B  shows a locality-sensitive hash of the html tags from the second example of an image-based spam (given in  FIG. 4B ). Each locality-sensitive hash is shown as 64 hexadecimal digits which represents 256 bits. In this example, the locality-sensitive hashes comprise Nilsimsa codes (which are 256 bits in length). Performing a difference function over the two locality-sensitive hashes indicates that the two hashes agree in 235 out of 256 bits, which is a high level of agreement. This characteristic of the locality-sensitive hashes (that similar content results in similar hash codes) allows similar spam to be grouped and identified in accordance with an embodiment of the invention. 
       FIG. 6  is a flow chart depicting a method performed by an analysis system  31  to identify a group of messages as spam or malware in accordance with an embodiment of the invention. For example, the analysis system  31  may be an in-the-cloud system which may be accessed by communicating with a server which is connected to the Internet. In one embodiment, the server may be a DNS server  30 . 
     As seen in  FIG. 6 , the server configured with the analysis system  31  receives  602  queries which include locality-sensitive hashes. These queries may be received from host engines  21  at multiple hosts. For example, the hosts may comprise computers or electronic devices that are configured to receive emails or text messages from the Internet. 
     The analysis system  31  (which may be configured as a software module running on the server) may then determine or detect  604  a group of hash codes which are considered similar. For example, if the locally sensitive hash algorithm being used in  602  is a Nilsimsa hash, then determining that two hash codes are similar would be done by determining whether two hash codes have a number of common bits greater than a configurable threshold. The similarity measure may be configured so that less or more similarity is needed before multiple hash codes are identified as being members of a common group. 
     A lower similarity threshold (for example, fewer common bits in the case of using a Nilsimsa hash as the locality sensitive hash) would detect more spam messages and/or malware but may lead to more false positive identifications. On the other hand, a higher similarity threshold would lead to fewer false positive identifications but may leave more spam messages and/or malware as undetected. 
     The analysis system  31  may then identify  606  the group of similar locality-sensitive hashes (with a similarity measure sufficient to pass a threshold) as corresponding to spam or malware. This identification of the group of hashes as corresponding to spam may rely on other characteristics beyond the cluster of hash codes. Examples of approaches for associating this as a spam cluster may be to (i) have a spam sample from a spam trap which belongs to this group, or (ii) to look at the distribution of IP numbers which were the sources of the spam. 
     Once a group of similar locality-sensitive hashes is identified as spam, the analysis system  31  may determine  608  a signature for the spam or malware. One approach would be to identify a central representative hash code for the cluster. The representative samples could be in a data structure such as a KD tree for fast identification of similar hash codes. A kd (k-dimensional) tree is a space-partitioning data structure for organizing points in a k-dimensional space. A kd tree is a type of binary search tree. Another approach would involve calculation of an associated bitmask for the spam or malware cluster. Such a bitmask may be configured such that the bits which are not common are not compared against the signature, while the bits which are common are compared against the signature. An example of this approach is discussed below in relation to  FIG. 7 . 
     The analysis system  31  may then add  610  the signature (and possibly the associated bitmask) to an undesirable ID data structure  32 . For example, the undesirable ID data structure  32  may be configured as a binary search tree, such as a KD tree, or other efficiently searchable data structure. Such an undesirable ID data structure  32  may be searched to determine if a newly received locality-sensitive hash value matches a signature/mask for a spam. The analysis system  31  may also forward  612  the update (new addition) to the undesirable ID data structure  32  to other servers configured with the analysis system  31 . 
       FIG. 7  is a table showing an example group of messages identified as spam by an analysis system at a server in accordance with an embodiment of the invention which uses a bitmask in association with the spam signature. The table shows a sample series of bits of a locality-sensitive hash for ten variants of an example spam. The actual hash codes would generally be longer, but only seventeen bits are shown for purposes of illustration. 
     Below the ten variants of the example spam are shown bits for a signature and corresponding mask for the spam. As seen, the bits with common values amongst the spam variants are made part of the signature, and the bits that do not have common values amongst the spam variants are masked off so that they are not part of the signature. 
       FIG. 8  is a flow chart depicting a method performed by an analysis system  31  to check whether or not a message or file is considered to be spam or malware in accordance with an embodiment of the invention. For example, the analysis system  31  may be at a server which is connected to the Internet. In one embodiment, the server may be a DNS server  30 . 
     As seen in  FIG. 8 , the server configured with the analysis system  31  receives  802  a query which includes a locality-sensitive hash code. The query may be received from a computer or other electronic device that is configured with a host engine  21 . 
     The analysis system  31  (which may be configured as a software module running on the server) may then search  804  the undesirable ID data structure  32  to determine  806  whether or not the locality-sensitive hash matches any signature/mask entry in the data structure. The analysis system  31  may then respond  808  to the query by returning an answer to the inquiring HE  21 . The answer may indicate whether or not the hash code indicates that the corresponding message or file is spam or malware. 
     Improved apparatus and methods for identification of spam have been disclosed herein. While specific embodiments of the present invention have been provided, it is to be understood that these embodiments are for illustration purposes and not limiting. Many additional embodiments will be apparent to persons of ordinary skill in the art reading this disclosure.