Systems and methods for classification of messaging entities

[0001] This application claims priority under 35 U.S.C. §119(e) to U.S. Provisional Application Ser. No. 61/334,819 titled “Systems And Methods For Classification Of Messaging Entities” filed May 14, 2010, the disclosure of which is incorporated herein by reference in its entirety.

[0002] This disclosure relates to classifying messaging entities and filtering communications.

[0003] In the anti-spam industry, spammers use various creative means for evading detection by spam filters. Accordingly, spam filter designers adopt a strategy of combining various detection techniques in their filters.

[0004] Current tools for message sender analysis include IP blacklists (e.g., real-time blacklists (RBLs)) and IP whitelists (e.g., real-time whitelists (RWLs)). Whitelists and blacklists add value to the spam classification process; however, whitelists and blacklists are inherently limited to providing a binary-type (YES/NO) response to each query. In contrast, a reputation system has the ability to express an opinion of a sender in terms of a scalar number in some defined range. Thus, where blacklists and whitelists are limited to “binary” responses, a reputation system can express “shades of gray” in its response.

[0005] In general, one aspect of the subject matter described in this specification can be embodied in methods that include receiving a communication at the one or more data processor comprising data that identifies a plurality of biasing characteristics related to a messaging entity associated with the communication; analyzing the identified plurality of biasing characteristics related to the messaging entity associated with the communication based upon a plurality of criteria; biasing a reputation score associated with the messaging entity based upon the analysis of the identified plurality of biasing characteristics related to the messaging entity associated with the communication; and determining an action to be taken with respect to a communication associated with the messaging entity based upon the reputation score. Other embodiments of this aspect include corresponding systems, apparatus, and computer program products.

[0006] The details of one or more embodiments of the subject matter described in this specification are set forth in the accompanying drawings and the description below. Other features, aspects, and advantages of the subject matter will become apparent from the description, the drawings, and the claims.

[0015] FIG. 1 depicts at 30 a system for handling transmissions received over a network 40. The transmissions can be many different types of communications, such as electronic mail (e-mail) messages sent from one or more messaging entities 50. The system 30 assigns a classification to a messaging entity (e.g., messaging entity 52), and based upon the classification assigned to the messaging entity, an action is taken with respect to the messaging entity's communication.

[0016] The system 30 uses a filtering system 60 and a reputation system 70 to help process communications from the messaging entities 50. The filtering system 60 uses the reputation system 70 to help determine what filtering action (if any) should be taken upon the messaging entities' communications. For example, the communication may be determined to be from a reputable source and thus the communication should not be filtered.

[0017] The filtering system 60 identifies at 62 one or more message characteristics associated with a received communication and provides that identification information to the reputation system 70. The reputation system 70 evaluates the reputation by calculating probabilities that the identified message characteristic(s) exhibit certain qualities. An overall reputation score is determined based upon the calculated probabilities and is provided to the filtering system 60.

[0018] The filtering system 60 examines at 64 the reputation score in order to determine what action should be taken for the sender's communication (such as whether the communication transmission should be delivered to the communication's designated recipient located within a message receiving system 80). The filtering system 60 could decide that a communication should be handled differently based in whole or in part upon the reputation scored that was provided by the reputation system 70. As an illustration, a communication may be determined to be from a non-reputable sender and thus the communication should be handled as Spam (e.g., deleted, quarantined, etc.).

[0019] Reputation systems may be configured in many different ways in order to assist a filtering system. For example, a reputation system 70 can be located externally or internally relative to the filtering system 60 depending upon the situation at hand. As another example, FIG. 2 depicts a reputation system 70 that has been configured to calculate reputation scores based upon such message characteristic identification information as sender identity as shown at 82. It should be understood that other message characteristics can be used instead of or in addition to sender identity. Moreover, transmissions may be from many different types of messaging entities, such as a domain name, IP address, phone number, or individual electronic address or username representing an organization, computer, or individual user that transmits electronic messages. For example, generated classifications of reputable and non-reputable can be based upon a tendency for an IP address to send unwanted transmissions or legitimate communication.

[0020] The system's configuration 90 could also, as shown in FIG. 2, be established by identifying a set of binary, testable criteria 92 which appear to be strong discriminators between good and bad senders. P (NR|C_i) can be defined as the probability that a sender is non-reputable, given that it conforms to quality/criterion C, and P (R|C_i) can be defined as the probability that a sender is reputable, given that it conforms to quality/criterion C_i.

[0021] For each quality/criterion C, periodic (e.g., daily, weekly, monthly, etc.) sampling exercises can be performed to recalculate P (NR|C_i). A sampling exercise may include selecting a random sample set S of N senders for which quality/criterion C_i is known to be true. The senders in the sample are then sorted into one of the following sets: reputable (R), non-reputable (NR) or unknown (U). N_R is the number of senders in the sample that are reputable senders, N_NR is the number of senders that are non-reputable senders, etc. Then, P (NR|C_i) and P (R|C_i) are estimated using the formulas:

[0022] $P\left(\mathrm{NR}|C_i\right)=\frac{N_{\mathrm{NR}}}{N}$ $P\left(R|C_i\right)=\frac{N_R}{N}$
For this purpose, N=30 was determined to be a large enough sample size to achieve an accurate estimate of P (NR|C_i) and P (R|C_i) for each quality/criterion C_i.

[0023] After calculating P (NR|C_i) and P (R|C_i) for all criteria, the computed probabilities are used to calculate an aggregate non-reputable probability 94, P_NR, and an aggregate reputable sender probability 96, P_R, for each sender in the reputation space. These probabilities can be calculated using the formulas:

[0024] $P_{\mathrm{NR}}=(1-\prod _{i=1}^N{\left\{\begin{array}{cc}1-P\left(\mathrm{NR}|C_i\right)& \mathrm{if}\mathrm{criterion}i\mathrm{applies}\\ 1& \mathrm{otherwise}\end{array}\right)}^{\left(\#\mathrm{of}\mathrm{criteria}\mathrm{that}\mathrm{apply}\right)}{P}_R=(1-\prod _{i=1}^N{\left\{\begin{array}{cc}1-P\left(R|C_i\right)& \mathrm{if}\mathrm{criterion}i\mathrm{applies}\\ 1& \mathrm{otherwise}\end{array}\right)}^{\left(\#\mathrm{of}\mathrm{criteria}\mathrm{that}\mathrm{apply}\right)}$
In experimentation, the above formulas appeared to behave very well for a wide range of input criteria combinations, and in practice their behavior appears to be similar to the behavior of the formula for correctly computing naïve joint conditional probabilities of “non-reputable” and “reputable” behavior for the input criteria.

[0025] After calculating P_NR and P_R for each sender, a reputation score is calculated for that sender using the following reputation function:
f(P_NR,P_R)=(c₁+c₂P_NR+c₂P_R+c₃P_NR²+c₃P_R²+c₄P_NRP_R+c₅P_NR³+c₅P_R³+c₆P_NRP_R²+c₆P_NR²P_R)((P_NR−P_R)³±c₇(P_NR−P_R))

• • [0026] where
    • [0027] c₁=86.50
    • [0028] c₂=−193.45
    • [0029] c₃=−35.19
    • [0030] c₄=581.09
    • [0031] C₅=234.81
    • [0032] c₆=−233.18
    • [0033] C₇=0.51
      It should be understood that different functions can act as a reputation score determinator 98 and can be expressed in many different forms in addition to a functional expression. As an illustration, FIG. 3 depicts at 100 a tabular form for determining reputation scores. The table shows reputation scores produced by the above function, based on values of P_NR and P_R as they each vary between 0.0 and 1.0. For example as shown at 110, a reputation score of 53 is obtained for the combination of P_NR=0.9 and P_R=0.2. This reputation score is a relatively high indicator that the sender should not be considered reputable. A reputation score of 0 is obtained if P_NR and P_R are the same (e.g., the reputation score is 0 if P_NR=0.7 and P_R=0.7 as shown at 120). A reputation score can have a negative value to indicate that a sender is relatively reputable as determined when P_R is greater than P_NR. For example, if P_NR=0.5 and P_R=0.8 as shown at 130, then the reputation score is −12.

[0034] Reputation scores can be shown graphically as depicted in FIG. 4 at 150. Graph 150 was produced by the above function, based on values of P_NR and P_R. FIG. 4 illustrates reputation score determinations in the context of Spam in that the terms P_NR and P_R are used respectively as probability of hamminess and probability of spamminess as the probabilities each vary between 0.0 and 1.0.

[0035] As shown in these examples, reputation scores can be numeric reputations that are assigned to messaging entities based on characteristics of a communication (e.g., messaging entity characteristic(s)) and/or a messaging entity's behavior. Numeric reputations can fluctuate between a continuous spectrum of reputable and non-reputable classifications. However, reputations may be non-numeric, such as by having textual, or multiple level textual categories.

[0036] FIG. 5 depicts an operational scenario wherein a reputation system is used by a filtering system to generate reputation scores. In this operational scenario, a reputation score is computed for a particular sender (e.g., IP address, domain name, phone number, address, name, etc), from a set of input data. With reference to FIG. 5, data is gathered at step 200 that is needed to calculate non-reputable and reputable probabilities for a sender. The data is then aggregated at step 210 and used in probability calculations at step 220. This includes determining, for a sender, non-reputable probabilities and reputable probabilities for various selected criteria. An aggregate non-reputable probability and an aggregate reputable probability are then calculated for each sender.

[0037] After calculating an aggregate non-reputable probability and an aggregate reputable probability for each sender, a reputation score is calculated at 230 for that sender using a reputation function. At step 240, the sender's reputation score is distributed locally and/or to one or more systems to evaluate a communication associated with the sender. As an illustration, reputation scores can be distributed to a filtering system. With the reputation score, the filtering system can choose to take an action on the transmission based on the range the sender reputation score falls into. For unreputable senders, a filtering system can choose to drop the transmission (e.g., silently), save it in a quarantine area, or flag the transmission as suspicious. In addition, a filter system can choose to apply such actions to all future transmissions from this sender for a specified period of time, without requiring new lookup queries to be made to the reputation system. For reputable senders, a filtering system can similarly apply actions to the transmissions to allow them to bypass all or certain filtering techniques that cause significant processing, network, or storage overhead for the filtering system.

[0038] It should be understood that similar to the other processing flows described herein, the processing and the order of the processing may be altered, modified and/or augmented and still achieve the desired outcome. For example, an optional addition to the step of extracting unique identifying information about the sender of the transmission would be to use sender authentication techniques to authenticate certain parts of the transmission, such as the purported sending domain name in the header of the message, to unforgeable information about the sender, such as the IP address the transmission originated from. This process can allow the filtering system to perform lookups on the reputation system by querying for information that can potentially be forged, had it not been authenticated, such as a domain name or email address. If such domain or address has a positive reputation, the transmission can be delivered directly to the recipient system bypassing all or some filtering techniques. If it has a negative reputation, the filtering system can choose to drop the transmission, save it in a quarantine area, or flag it as suspicious.

[0039] Many different types of sender authentication techniques can be used, such as the Sender Policy Framework (SPF) technique. SPF is a protocol by which domain owners publish DNS records that indicate which IP addresses are allowed to send mail on behalf of a given domain. As other non-limiting examples, SenderID or DomainKeys can be used as sender authentication techniques.

[0040] As another example, many different types of criteria may be used in processing a sender's communication. FIG. 6 depicts the use of non-reputable criteria 300 and reputable criteria 310 for use in determining reputation scores.

[0041] The non-reputable criteria 300 and reputable criteria 310 help to distinguish non-reputable senders and reputable senders. A set of criteria can change often without significantly affecting the reputation scores produced using this scoring technique. As an illustration within the context of SPAM identification, the following is a list of spamminess criteria that could be used in the reputation scoring of a message sender. The list is not intended to be exhaustive, and can be adapted to include other criteria or remove criteria based upon observed behavior.

• • [0042] 1. Mean Spam Score: A sender is declared “non-reputable” if a mean spam profiler score of transmissions that it sends exceeds some threshold, W.
  • [0043] 2. RDNS Lookup Failure: A sender is declared “non-reputable” if reverse domain name system (RDNS) queries for its IP addresses fail.
  • [0044] 3. RBL Membership: A sender is declared “non-reputable” if it is included in a real-time blackhole list (RBL). (Note: multiple RBLs may be used. Each RBL can constitute a separate testing criterion.)
  • [0045] 4. Mail Volume: A sender is declared “non-reputable” if its average (mean or median) transmission volume exceeds a threshold, X, where X is measured in transmissions over a period of time (such as, e.g., a day, week, or month). (Note: multiple average volumes over multiple time periods may be used, and each average volume can constitute a separate testing criterion.)
  • [0046] 5. Mail Burstiness/Sending History: A sender is declared “non-reputable” if its average (mean or median) transmission traffic pattern burstiness (defined by the number of active sending sub-periods within a larger time period, e.g., number of active sending hours in a day or number of active sending days in a month) is less than some threshold, Y, where Y is measured in sub-periods per period. (Note: multiple average burstiness measures over multiple time periods may be used, and each average burstiness measure can constitute a separate testing criterion.)
  • [0047] 6. Mail Breadth: A sender is declared “non-reputable” if its average (mean or median) transmission traffic breadth (as defined by the percentage of systems that receive transmissions from the same sender during a period of time (such as, e.g., a day, week, or month)) exceeds some threshold, Z. (Note: multiple average breadths over multiple time periods may be used, and each average breadth measure can constitute a separate testing criterion.)
  • [0048] 7. Malware Activity: A sender is declared “non-reputable” if it is known to have delivered one or more malware codes (such as, e.g., viruses, spyware, intrusion code, etc) during a measurement period (e.g., a day, week, or month).
  • [0049] 8. Type of Address: A sender is declared “non-reputable” if it is known to be dynamically assigned to dial-up or broadband dynamic host control protocol (DHCP) clients by an internet service provider (ISP).
  • [0050] 9. CIDR Block Spamminess: A sender is declared “non-reputable” if its IP addresses are known to exist within classless inter-domain routing (CIDR) blocks that contain predominantly “non-reputable” IP addresses.
  • [0051] 10. Human Feedback: A sender is declared “non-reputable” if it is reported to have sent undesirable transmissions by people analyzing the content and other characteristics of those transmissions.
  • [0052] 11. SpamTrap Feedback: A sender is declared “non-reputable” if it is sending transmissions to accounts that have been declared as spamtraps and as such are not supposed to receive any legitimate transmissions.
  • [0053] 12. Bounceback Feedback: A sender is declared “non-reputable” if it is sending bounceback transmissions or transmissions to accounts that do not exist on the destination system.
  • [0054] 13. Legislation/Standards Conformance: A sender is declared “non-reputable” if it is not conforming to laws, regulations, and well-established standards of transmission behavior in the countries of operation of either the sender and/or the recipient of the transmissions.
  • [0055] 14. Continuity of Operation: A sender is declared “non-reputable” if it has not operated at that sending location longer than some threshold Z.
  • [0056] 15. Responsiveness to Recipient Demands: A sender is declared “non-reputable” if it is not responding in a reasonable timeframe to legitimate demands of the recipients to terminate their relationship with the sender to not receive any more transmissions from them.
  • [0057] 16. Frequently Changing Domain Name Records to Bias Reputation: A reputation score of a sender having a corresponding IP address/Domain name mapping that changes frequently can be biased to toward being non-reputable. Botnets—a collection of software robots, or bots, that run autonomously and automatically on a collection of compromised computers (e.g., Zombie computers). Botnets often associated with registered domain names and direct thousands of infected machines to serve as web servers or DNS servers for a domain name. The botnet can frequently change the DNS address record for a domain name, e.g., change the DNS address every few seconds, directing the traffic to another infected machine. In some implementations DNS servers can be continuously queried to identify domain names address records that change frequently and IP addresses that correspond to the identified frequently changing domain name address records. The reputation server can reduce the reputation of devices corresponding to the IP addresses associated with the identified domain names based upon determining that the IP address is associated with the frequently changing IP address/domain name mapping, thereby biasing the reputation of the device towards being non-reputable.

[0058] As used herein, biasing the reputation towards non-reputable or reputable results in a continuous spectrum of reputable and non-reputable classifications. The bias can be a linear function or a non-linear function, depending on the signal(s) from which the biasing is determined. Additional signals on which to bias a reputation score and biasing techniques are described below.

[0059] The following is a list of “reputable” criteria that could be used in determining the “reputability” of a sender. The list is not intended to be exhaustive, and can be adapted to include other criteria or remove criteria based upon observed behavior.

• • [0060] 1. Mean Spam Score: A sender is declared “reputable” if the mean spam profiler score of transmissions that it sends falls below some threshold, W.
  • [0061] 2. Human Feedback: A sender is declared “reputable” if it is reported to have sent only legitimate transmissions by people analyzing transmission flows from that sender, in conjunction with the reputation of the organization that owns those sending stations.
  • [0062] 3. Using Bounce Address Tag Verification (BATV) to Bias Reputation: A sender having message that includes a BATV token associated with a message originator can have a reputation score that is biased toward reputable. The BATV token can be used to identify legitimate messages that have been bounced from a receiving server (e.g., based upon being unable to resolve the e-mail address). If a bounced message includes a BATV token appended to the original message by the mail server associated with the message originator, then the message is identified as authentic and the mail server notifies the user that the message was bounced. However, if the message was spoofed, the bounced message will not include the BATV token, and the mail server can discard the message or notify an administrator. In some implementations, the presence of the BATV token in a bounced message can be used to increase the reputability of the IP address associated with the originator of the message.
    • [0063] In some implementations, when a first party sends a message to a second party, the mail server can rewrite the from address as, e.g., <first-party>-<token>@example.com. When the second party responds to the message, the second party will respond to the address <first-party>-<token>@example.com. The mail server associated with the first party can resolve the address to <first-party>@example.com. The mail server can authenticate the message based upon the token information in the username. In further implementations, the mail server associated with the first party can match the “from” field of the message from the second party to the token included in the message to authenticate the message. Moreover, the reputation associated with the IP address of the second party can be biased toward being reputable based upon the presence of the token in the message to the first party.

[0064] The following is a list of biasing criteria that can be used in biasing a reputation score toward being “reputable” or “non-reputable”. The biasing is dependent on the characteristics of the entity and/or message. The list is not intended to be exhaustive, and can be adapted to include other criteria or remove criteria based upon observed behavior.

• • [0065] 1. Zone File Characteristics: In some implementations, domain registration data can be examined to identify zone files for all registered domains. The zone files can be analyzed to identify malicious domains. In some implementations, textual analysis of the domain name itself can be used to identify the randomness of the domain name based upon, for example, using n-gram language models or Markov-chain analysis to determine the randomness of a registered domain name. In this example, the more random a domain name appears to be based upon a language model, the more likely the domain name is not reputable. Thus, the randomness of a domain name can be used to reduce the reputation associated with the domain name or IP address(es) associated with the domain name. In further implementations, the non-randomness of a domain name can be used to increase the reputation associated with a domain name.
    • [0066] In further implementations, frequent name server changes can be used to adjust the reputation of a device or domain. For example, legitimate domains are more likely to have name server records that are relatively constant without change. However, non-reputable domains are more likely to change providers more frequently, and thereby are more likely to have multiple changes in the name servers that map the domain. Thus, if the zone file for a domain has many name server changes frequently over a period of time, it is more likely that the entity associated with the domain name is malicious. In such implementations, the reputation of the domain name can be biased to account for the increased likelihood that the domain name is associated with a malicious entity.
    • [0067] It has also been observed that domain names that have been registered for a longer period of time are more likely to be legitimate servers. However, domain names that have been registered recently have a higher likelihood of be non-reputable. Thus, in some implementations, the reputation associated with a domain name can be biased based upon the age of the domain name. The bias can be a linearly increasing function of time, an exponentially increasing function of time, or a logarithmically increasing function of time.
  • [0068] 2. Traffic Pattern Characteristics: In some implementations, the reputation server can analyze the mail sending patterns of IP addresses. For example, reputable mail servers typically originate regular volumes of mail during the week, and low volumes of mail on the weekends, while non-reputable mail servers typically generate a more random mail origination pattern with a burst of traffic, followed by a period of very low volume of traffic. Thus, addresses or entities that do not have a regular mail sending pattern typically associated with a reputable mail server can be biased toward non-reputable. Moreover, addresses or entities that have a regular mail sending pattern associated with the sending patterns of reputable mail servers can be biased towards reputable.
  • [0069] 3. Real Time Zombie Detector: In some implementations, the reputation system can flag IP addresses that have been persistent senders of messages. The reputation server can use these special flags to indicate that an IP address is not subject to analysis by the real-time tests, while IP addresses that have not been previously flagged can be analyzed using real-time tests. In some implementations, the reputation system can analyze information identifying how many devices asked for this IP address during a period of time (e.g., a ten minute window) and how often those devices asked for the IP address during that period of time. This information can be used to assign a breadth rating to the IP address. The breadth rating can be compared to breadth rating profiles of reputable and non-reputable IP addresses to determine how to bias the reputation of the address or device. For example, an IP address assigned a breadth rating which is similar to non-reputable IP addresses can be biased towards non-reputable, while an IP address assigned a breadth rating which is similar to reputable IP addresses can be biased towards reputable.
  • [0070] 4. Persistent Communication Characteristics: In some implementations, the communication patterns of an entity with an established working set of recipients can be analyzed to identify a likelihood that the sender is reputable or non-reputable. A reputable sender might exchange e-mail with a certain set of recipients on a regular basis, while a non-reputable sender is more likely not to have any particular set of users with whom the non-reputable sender exchanges e-mail on a regular basis. For example, a spammer is more likely to send a single communication to thousands of recipients, while a legitimate user is more likely to send multiple communications to an established group of friends, coworkers, or clients. Thus, senders with an established set of recipients and/or sending patterns can be biased towards reputable (e.g., increasing the likelihood that the sender is identified as reputable), while senders without any established set of recipients and/or sending patterns can be biased toward non-reputable (e.g., increasing the likelihood that the sender is identified as non-reputable).
  • [0071] 5. Subject Classification: In some implementations, information on subject fields and originating IP addresses can be collected from communications. The collected information can be aggregated, and a classification algorithm can be executed using the terms in the subject. Based upon data collected from a training data set, terms can be identified as associated with malicious messages (or associated with reputable messages). In some implementations, when a term appears with a given frequency in known non-reputable messages, the term can be identified as associated with non-reputable communications. For example, the term “Free financial offer”, if it occurs with a statistically significant frequency in the subject line of messages, may be highly correlated with spam messages. The reputation of devices or addresses associated with communications that include subject field terms that are highly correlated with spam messages can be biased towards being non-reputable. Similarly, some terms can be identified as correlated with reputable messages if they appear within known reputable messages with a threshold frequency. Such terms can be used to bias the reputation of an associated device or address towards being identified as a reputable device or address.
    • [0072] In some implementations, all terms associated with subject fields of messages originating from an IP address can be concatenated and compared to the subject field profiles of known reputable and known non-reputable IP addresses. Devices or addresses that display a correlation to subject field profiles of known reputable IP addresses can be biased towards being classified as reputable, while devices or addresses that display a correlation to subject field profiles of known non-reputable IP addresses can be biased towards being classified as non-reputable.
  • [0073] 6. Hash Vault Profiling: In some implementations, messages can be analyzed to extract hash values from messages using a winnowing algorithm. The winnowing algorithm is applied such that similar messages are most likely to produce similar or identical hash values. The winnowing algorithm can extract many fingerprints from a message and selects a number of fingerprints from different parts of the message, such that the selected fingerprints are most likely to be the same for messages that are similar.
    • [0074] In some implementations, the hashes can be stored along with the IP address to a hash vault. The hash vault can store millions of hashes and can be organized based upon a least recently used (LRU) algorithm, such that the least recently used hash can be removed when a new hash is encountered. The stored hashes in the hash vault can be flagged as reputable or non-reputable. In some implementations, the flag can include information on how many times the hash has been encountered. Hashes that have been encountered more than a threshold number of times can be identified as being associated with spam messages. If an entity sends messages that include non-reputable hashes, the reputation of the entity can be biased towards having a non-reputable reputation based upon the origination of non-reputable messages from the entity.
  • [0075] 7. Performance Optimized Image Spam Correlation: Image spam can be difficult to identify. Simple techniques (i.e., techniques that do not require significant processing resources) are prone to false negatives, while more sophisticated techniques (i.e., techniques that require significant processing resources and are more accurate) can result is system performance degradation. In some implementations, a two tiered approach can be used to identify image spam. In the first step, a small set of key attributes can be identified from an image in a message. Based upon these attributes, a support vector machine can be used on the attributes as a first pass to determine which images are more likely to be spam. If the image is cleared by the first pass, it can be forwarded to the recipient. Otherwise the image is identified as potential spam and can be analyzed in more detail. Example key features can be extracted from the image header, including image size, image width, image height, number of bytes, how much the image can be compressed, etc.
    • [0076] In the more detailed analysis, additional features are identified from the image, including for example, noise levels, gradients, and number of edges, among many others. These more detailed features can be compared to the detailed features of known image spam, for example, using SVM algorithms. Detailed image spam analysis is described in U.S. patent application Ser. No. 11/626,568, entitled “Detecting Image Spam,” filed on Jan. 24, 2007, which is hereby incorporated by reference in its entirety. An SVM classification algorithm is described in U.S. patent application Ser. No. 12/020,253, entitled “Granular Support Vector Machine with Random Granulation,” filed on Jan. 25, 2008, which is hereby incorporated by reference in its entirety. The reputation of entities associated with image spam can be decreased or biased towards having a non-reputable reputation, while the reputation of entities associated with non-spam images can be increased or biased towards having a reputable reputation.
  • [0077] 8. Reputation Intelligence Combined with From Domains to ID Spam: Spammers often try to spoof legitimate senders. In some implementations, the owner of IP addresses that send communications on behalf of domains can be identified. If the owner of the IP address and the domain differ, it is likely that the IP address is a non-reputable entity. For example, assume “examplemail.com” is a reputable mail site owned by Example Company, an established and reputable company. If an IP address that sends mail from examplemail.com does not belong to Example Company, owner of the examplemail.com domain, that IP address can be identified as a non-reputable entity. Additionally, the reputability score associated with IP addresses originating communications that do not match the domain identified by the communication can be reduced or biased towards being non-reputable. Similarly, the reputability score associated with IP addresses originating primarily communications that match the domain identified by the communication can be increased or biased towards being reputable.

[0078] The example list of biasing criteria is not limiting. Other biasing criteria can include reverse domain name server lookup failure; membership on one or more real-time blacklists (RBLs); mail volume; mail burstiness; mail breadth; geographic location; malware activity; classless inter-domain routing (CIDR) block comprising a number of internet protocol addresses identified to send spam; rate of honeypot detections; rate of undeliverable transmissions; continuity of operation; responsiveness to recipient requests; and the like.

[0079] After computing a reputation grade for each sender in the universe of senders, a reputation classification can be made available via a communication protocol that can be interpreted by the queriers that make use of the reputation system (e.g., DNS, HTTP, etc). As shown in FIG. 7, when a query 350 is issued for a sender, the reputation system can respond with a return value 360 that includes the reputation score of that sender, as well as any other relevant additional information that can be used by the querier to make the final judgment on the acceptability of the sender's transmission (e.g., age of the reputation score, input data that determined the score, etc).

[0080] An example of a communication protocol that can be used is a domain name system (DNS) server which can respond with a return value in the form of an IP address: 172.x.y.z. The IP address can be encoded using the formula:

[0081] $\mathrm{IP}=172·\left(\frac{\mathrm{rep}-\mathrm{rep}}{2\times \mathrm{rep}}\right)·\left(\mathrm{rep}\mathrm{div}256\right)·\left(\mathrm{rep}\mathrm{mod}256\right)$

[0082] The reputation of the queried sender can be deciphered from the return value as follows:
rep=(−1)^2-x×(256y+z)

[0083] Therefore, when x=0, the returned reputation is a positive number, and when x=1, the returned reputation is a negative number. The absolute value of the reputation is determined by the values of y and z. This encoding scheme enables the server to return via the DNS protocol reputation values within the range [−65535, 65535]. It also leaves seven (7) unused bits, namely the seven high-order bits of x. These bits can be reserved for extensions to the reputation system. (For example, the age of a reputation score may be communicated back to the querier.)

[0084] The systems and methods disclosed herein may be implemented on various types of computer architectures, such as for example on different types of networked environments. As an illustration, FIG. 8 depicts a server access architecture within which the disclosed systems and methods may be used (e.g., as shown at 30 in FIG. 8). The architecture in this example includes a corporation's local network 490 and a variety of computer systems residing within the local network 490. These systems can include application servers 420 such as Web servers and e-mail servers, user workstations running local clients 430 such as e-mail readers and Web browsers, and data storage devices 410 such as databases and network connected disks. These systems communicate with each other via a local communication network such as Ethernet 450. Firewall system 440 resides between the local communication network and Internet 460. Connected to the Internet 460 are a host of external servers 470 and external clients 480.

[0085] Local clients 430 can access application servers 420 and shared data storage 410 via the local communication network. External clients 480 can access external application servers 470 via the Internet 460. In instances where a local server 420 or a local client 430 requires access to an external server 470 or where an external client 480 or an external server 470 requires access to a local server 420, electronic communications in the appropriate protocol for a given application server flow through “always open” ports of firewall system 440.

[0086] A system 30 as disclosed herein may be located in a hardware device or on one or more servers connected to the local communication network such as Ethernet 480 and logically interposed between the firewall system 440 and the local servers 420 and clients 430. Application-related electronic communications attempting to enter or leave the local communications network through the firewall system 440 are routed to the system 30.

[0087] In the example of FIG. 8, system 30 could be configured to store and process reputation data about many millions of senders as part of a threat management system. This would allow the threat management system to make better informed decisions about allowing or blocking electronic mail (e-mail).

[0088] System 30 could be used to handle many different types of e-mail and its variety of protocols that are used for e-mail transmission, delivery and processing including SMTP and POP3. These protocols refer, respectively, to standards for communicating e-mail messages between servers and for server-client communication related to e-mail messages. These protocols are defined respectively in particular RFC's (Request for Comments) promulgated by the IETF (Internet Engineering Task Force). The SMTP protocol is defined in RFC 821, and the POP3 protocol is defined in RFC 1939.

[0089] Since the inception of these standards, various needs have evolved in the field of e-mail leading to the development of further standards including enhancements or additional protocols. For instance, various enhancements have evolved to the SMTP standards leading to the evolution of extended SMTP. Examples of extensions may be seen in (1) RFC 1869 that defines a framework for extending the SMTP service by defining a means whereby a server SMTP can inform a client SMTP as to the service extensions it supports and in (2) RFC 1891 that defines an extension to the SMTP service, which allows an SMTP client to specify (a) that delivery status notifications (DSNs) should be generated under certain conditions, (b) whether such notifications should return the contents of the message, and (c) additional information, to be returned with a DSN, that allows the sender to identify both the recipient(s) for which the DSN was issued, and the transaction in which the original message was sent. In addition, the IMAP protocol has evolved as an alternative to POP3 that supports more advanced interactions between e-mail servers and clients. This protocol is described in RFC 2060.

[0090] Other communication mechanisms are also widely used over networks. These communication mechanisms include, but are not limited to, Voice Over IP (VoIP) and Instant Messaging. VoIP is used in IP telephony to provide a set of facilities for managing the delivery of voice information using the Internet Protocol (IP). Instant Messaging is a type of communication involving a client which hooks up to an instant messaging service that delivers communications (e.g., conversations) in realtime.

[0091] As the Internet has become more widely used, it has also created new troubles for users. In particular, the amount of spam received by individual users has increased dramatically in the recent past. Spam, as used in this specification, refers to any communication receipt of which is either unsolicited or not desired by its recipient. A system and method can be configured as disclosed herein to address these types of unsolicited or undesired communications. This can be helpful in that e-mail spamming consumes corporate resources and impacts productivity.

[0092] The systems and methods disclosed herein are presented only by way of example and are not meant to limit the scope of the invention. Other variations of the systems and methods described above will be apparent to those skilled in the art and as such are considered to be within the scope of the invention. For example, using the systems and methods of sender classification described herein, a reputation system can be configured for use in training and tuning of external filtering techniques. Such techniques may include Bayesian, Support Vector Machine (SVM) and other statistical content filtering techniques, as well as signature-based techniques such as distributed bulk message identification and message clustering-type techniques. The training strategies for such techniques can require sets of classified legitimate and unwanted transmissions, which can be provided to the trainer by classifying streams of transmissions based on the reputation scores of their senders. Transmissions from senders classified as un-reputable can be provided to the filtering system trainer as unwanted, and the wanted transmissions can be taken from the stream sent by the legitimate senders.

[0093] As an illustration, methods and systems can be configured to perform tuning and training of filtering systems utilizing reputation scores of senders of transmissions in sets of trainable transmissions. At least one characteristic is identified about transmissions from senders. The identifying of at least one characteristic can include extracting unique identifying information about the transmissions (e.g., information about the senders of the transmissions), or authenticating unique identifying information about the transmissions, or combinations thereof. Queries are sent to a reputation system and scores are received representing reputations of the senders. Transmissions are classified into multiple categories based on a range a sender's reputation score falls into. Transmissions and their classification categories are passed on to a trainer of another filtering system to be used for optimization of the filtering system.

[0094] As another example, methods and systems can be configured to perform filtering of groups of transmissions utilizing reputation scores of senders of transmissions. Multiple transmissions can be grouped together based on content similarities or similarities in transmission sender behavior. At least one characteristic can be identified about each transmission in the groupings. The identifying of at least one characteristic can include extracting unique identifying information about the transmission (e.g., information about the sender of a transmission), or authenticating unique identifying information about the transmission, or combinations thereof. A query can be sent to the reputation system and receive a score representing reputation of each sender. Groups of transmissions can be classified based on the percentage of reputable and non-reputable senders in the group.

[0095] As another example of the wide variations of the disclosed systems and methods, different techniques can be used for computation of joint conditional probabilities. More specifically, different mathematical techniques can be used for computing the aggregate non-reputable sender probability, P_NR, and the aggregate reputable sender probability, P_R, for each sender in the reputation space. As an illustration, two techniques are described. Both techniques use P (NR|C_i) and P (R|C_i), the conditional probabilities of non-reputable and reputable behavior, for each testing criterion C_i. The first technique makes the assumption that all testing criteria are independent. The second technique incorporates the assumption that the testing criteria are not independent. Therefore, the second technique is more difficult to carry out, but produces more accurate results.

[0096] 1. Technique for Independent Testing Criteria

[0097] In the independent case, it is assumed that each criterion C_i is independent of all other criteria. The probability that the sender is non-reputable, P_NR, is calculated using the following formula:

[0098] $P_{\mathrm{NR}}=\frac{\prod P\left(\mathrm{NR}|C_j\right)}{\prod P\left(\mathrm{NR}|C_j\right)+\prod \left(1-P\left(\mathrm{NR}|C_j\right)\right)}$
where j ranges over all criteria that apply to the sender in question. Similarly, the probability that the sender is a reputable sender, P_R, is calculated using the following formula:

[0099] $P_R=\frac{\prod P\left(R|C_j\right)}{\prod P\left(R|C_j\right)+\prod \left(1-P\left(R|C_j\right)\right)}$
where j ranges over all criteria that apply to the sender in question.

[0100] 2. Technique for Non-Independent Testing Criteria

[0101] In the dependent case, it is assumed that each criterion C_i is not independent of all other criteria, so the analysis must take into account “non-linear” interactions between criteria within their joint probability distribution. To find the correct values for P_NR and P_R for a given sender, a table is constructed to represent the entire joint probability distribution. Below is a sample table for a joint distribution of four qualities/criteria.

[0102]

Case	C1	C2	C3	C4	PNR	PR
1	N	N	N	N	N/A	N/A
2	N	N	N	Y	P(NR|C4)	P(R|C4)
3	N	N	Y	N	P(NR|C3)	P(R|C3)
4	N	N	Y	Y	P(NR|C3, C4)	P(R|C3, C4)
5	N	Y	N	N	P(NR|C2)	P(R|C2)
6	N	Y	N	Y	P(NR|C2, C4)	P(R|C2, C4)
7	N	Y	Y	N	P(NR|C2, C3)	P(R|C2, C3)
8	N	Y	Y	Y	P(NR|C2, C3, C4)	P(R|C2, C3, C4)
9	Y	N	N	N	P(NR|C1)	P(R|C1)
10	Y	N	N	Y	P(NR|C1, C4)	P(R|C1, C4)
11	Y	N	Y	N	P(NR|C1, C3)	P(R|C1, C3)
12	Y	N	Y	Y	P(NR|C1, C3, C4)	P(R|C1, C3, C4)
13	Y	Y	N	N	P(NRC1, C2)	P(R|C1, C2)
14	Y	Y	N	Y	P(NR|C1, C2, C4)	P(R|C1, C2, C4)
15	Y	Y	Y	N	P(NR|C1, C2, C3)	P(R|C1, C2, C3)
16	Y	Y	Y	Y	P(NR|C1, C2, C3, C4)	P(R|C1, C2, C3, C4)

For a joint distribution of M criteria, there exist (2^M−1) distinct cases within the joint probability distribution. Each case constitutes a particular combination of characteristics. The probability that the sender is non-reputable, P_NR, is estimated for each case using the following technique. For each one of the (2^M−1) cases, a random sample of N senders is gathered that exhibit the combination of characteristics described by that case. (For this purposes, N=30 is a large enough sample). Each sender is sorted into one of the following sets: reputable (R), non-reputable (NR) or unknown (U). N_R is the number of sender in the sample that are reputable senders, N_NR is the number of senders that are non-reputable senders, etc. Then, P_NR and P_R is estimated using the formulas:

[0103] $P_{\mathrm{NR}}=\frac{N_{\mathrm{NR}}}{N}$ $P_R=\frac{N_R}{N}$
The sampling of the IP addresses is repeated periodically (e.g., daily, weekly, monthly) to update the joint probability distribution.

[0104] Embodiments of the subject matter and the functional operations described in this specification can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the subject matter described in this specification can be implemented as one or more computer program products, i.e., one or more modules of computer program instructions encoded on a tangible program carrier for execution by, or to control the operation of, data processing apparatus. The tangible program carrier can be computer readable medium, such as a machine-readable storage device, a machine-readable storage substrate, a memory device, or a combination of one or more of them.

[0105] The terms “computer” or “server” encompasses all apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them.

[0106] A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, or declarative or procedural languages, and it can be deployed in any form, including as a stand alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network.

[0107] The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit).

[0108] Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices.

[0109] Computer readable media suitable for storing computer program instructions and data include all forms of non volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

[0110] To provide for interaction with a user, embodiments of the subject matter described in this specification can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input.

[0111] Embodiments of the subject matter described in this specification can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or one that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the subject matter described is this specification, or any combination of one or more such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet.

[0112] The computing system can include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

[0113] While this specification contains many specific implementation details, these should not be construed as limitations on the scope of any invention or of what may be claimed, but rather as descriptions of features that may be specific to particular embodiments of particular inventions. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination.

[0114] Similarly, while operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products.

[0115] Particular embodiments of the subject matter described in this specification have been described. Other embodiments are within the scope of the following claims. For example, the actions recited in the claims can be performed in a different order and still achieve desirable results. As one example, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In certain implementations, multitasking and parallel processing may be advantageous.