Incremental anti-spam lookup and update service

• US 7,664,819 B2
• Filed: 06/29/2004
• Issued: 02/16/2010
• Est. Priority Date: 06/29/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hulten, Geoffrey J, Rounthwaite, Robert L, Hazeur, Derek M, Goodman, Joshua T, Murphy, Elissa E.
• Primary Examiner(s): Bruckart; Benjamin R
• Application Number:
  US10/879,626
• Publication Number:
  US 20060015561A1
• Time in Patent Office: 2,058 Days
• Field of Search: 709204-207, 709217-219, 707 1- 10, 726/45, 726/22, 726/23
• US Class Current: 709/206
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

The present invention provides a unique system and method that facilitates incrementally updating spam filters in near real time or real time. Incremental updates can be generated in part by difference learning. Difference learning involves training a new spam filter based on new data and then looking for the differences between the new spam filter and the existing spam filter. Differences can be determined at least in part by comparing the absolute values of parameter changes (weight changes of a feature between the two filters). Other factors such as frequency of parameters can be employed as well. In addition, available updates with respect to particular features or messages can be looked up using one or more lookup tables or databases. When incremental and/or feature-specific updates are available, they can be downloaded such as by a client for example. Incremental updates can be automatically provided or can be provided by request according to client or server preferences.

Claims

1. A computer-implemented anti-spam update system comprising following components stored in a computer memory:

a spam filter trained to distinguish between spam and good messages;

an update component that incrementally augments or replaces at least a portion of the spam filter with updated information to facilitate spam prevention, the update component is built at least in part by using a machine learning component; and

the machine learning component trains a first new filter using data extracted from one or more newly received messages, determines differences between the first new filter and the spam filter that satisfy a threshold value, trains a second new filter constrained to maintain weights of features of the spam filter corresponding to differences between the first new filter and the spam filter that did not satisfy the threshold value, and determines differences between the spam filter and the second new filter which satisfy one or more thresholds for augmenting or replacing at least a portion of the spam filter, wherein the updated information utilized by the update component is based at least in part on the determined differences between the spam filter and the second new filter.

2. The system of claim 1, the update component updates at least a data portion of the spam filter.

3. The system of claim 1 runs on at least one of a client or a server.

4. The system of claim 1, the update component is trained using match- or hash-based data.

5. The system of claim 1, further comprising a payment verification component that determines whether a client or server has paid to receive updates before one or more updates are provided to the spam filter.

6. The system of claim 1, the update component provides the updated information to the spam filter via a plurality of IP addresses to mitigate denial-of-service attacks.

7. The system of claim 1, the updated information comprises one or more incremental update files corresponding to one or more parameter changes.

8. The system of claim 1, the at least a portion of the spam filter comprises data specific to at least one feature.

9. The system of claim 8, the at least one feature comprises at least one of an IP address and a URL.

10. The system of claim 1, further comprising a component that builds machine learning spam filters to lessen a number of parameter changes between an existing spam filter and a new filter to facilitate minimizing incremental update sizes.

11. The system of claim 1, the update component sequentially applies a plurality of different updates to the spam filter.

12. The system of claim 1, the update component merges at least a subset of a plurality of updates to improve download efficiency of the updated information.

13. The system of claim 1, the update component selectively provides feature-specific updates in an independent manner such that at least one feature is updated independently of at least one other feature.

14. The system of claim 1, the spam filter comprises a plurality of sub-filters that are trained or updated independently of each other and is decomposable as a result.

15. The system of claim 1, further comprising a quarantining component that delays classification of at least a subset of messages until the spam filter receives the updated information from the update component.

16. A computer-implemented anti-spam query system comprising following components stored in a computer memory:

a machine learning spam filter trained to distinguish between spam and good messages;

a lookup component that receives queries for feature-related information as a message arrives to facilitate updating the spam filter, the lookup component is built at least in part by using a lookup database; and

the lookup database trains a first new filter using one or more features extracted from one or more recently received messages, determines differences between the first new filter and the spam filter that satisfy a threshold value, trains a second new filter constrained to maintain weights of features of the spam filter that did not satisfy the threshold value, and determines differences between the spam filter and the second new filter which satisfy one or more thresholds for augmenting or replacing at least a portion of the spam filter, wherein the lookup component updates the spam filter based at least in part on the determined differences between the spam filter and the second new filter.

17. The system of claim 16, the feature-related information comprises positive and negative data for a plurality of features or messages.

18. The system of claim 16, the feature-related information comprises feature scores and reputation scores for a plurality of features including at least one of IP addresses, URLs, hostnames, character strings, and words.

19. The system of claim 16, the spam filter is discriminatively trained.

20. The system of claim 16, the spam filter is updated at least partially incrementally.

21. The system of claim 16, the spam filter is updated at least partially by the lookup component.

22. The system of claim 16, the lookup component writes incremental lookup queries to file or stores them on disk and combines them in memory.

23. The system of claim 16, the lookup component comprises:

a back-end database that comprises a set of features and associated weights and one or more models or filters that are generated during training;

a middle-ware layer that passes communication between the database and a spam filter; and

the spam filter which calls the middle-ware layer at predefined or automatic frequency to obtain the most recent updated model and merges an online model with a locally stored model file.

24. The system of claim 16, the queries comprise requests for incremental updates of information for the spam filter from at least one of a client or a server.

25. The system of claim 16, further comprising an updated spam filter that is propagated from a service provider to an end user in at least two stages, wherein at least one of the stages is automatic such that there is an option for human intervention between the two stages.

26. The system of claim 16, further comprising a component that propagates filter code automatically from the service provider to the end user.

27. The system of claim 16, queries are sent to the lookup component at specified intervals according to an end user or administrator preferences.

28. The system of claim 16, updates to the spam filter take effect without restarting a messaging program.

29. A computer-implemented anti-spam update method comprising the following operations to build filters which minimize a number of differences:

providing an existing trained spam filter stored in a computer memory;

discriminatively training a first new spam filter using machine learning and data from one or more new messages;

determining a first set of differences between the existing spam filter and the first new spam filter that satisfy a threshold or heuristic;

training a second new spam filter using the new message data subject to a constraint that parameter changes between the first new spam filter and the existing spam filter that did not satisfy the threshold or heuristic have same value in the second new filter and the existing filter;

determining a second set of differences between the second new spam filter and the existing spam filter; and

incrementally updating the existing spam filter with at least a subset of the second set of the differences.

30. The update service of claim 29, the existing spam filter is trained using machine learning.

31. The update service of claim 29, the existing spam filter is currently in use by a messaging program to classify messages as spam or good.

32. The update service of claim 29, the new spam filter is trained on more recent or new data.

33. The update service of claim 29, the differences comprise one or more parameter changes between the existing spam filter and the new spam filter.

34. The update service of claim 29 is a web-based service.

35. The update service of claim 29, further comprising requesting feature-specific updates to the existing spam filter at least in part by searching at least one of lookup tables and databases.

36. The update service of claim 35, the lookup tables and databases comprising a plurality of incremental updates corresponding to a plurality of features.

37. The update service of claim 29, wherein incrementally updating the existing spam filter is based at least in part by the distribution of messages that any one of a client, server, or user receives.

38. The update service of claim 29, wherein one or more incremental updates to the existing spam filter are feature-specific such that at least one feature is updated independently of another feature.

39. A computer-implemented anti-spam update system comprising following components stored in a computer memory:

means for providing an existing trained spam filter;

means for discriminatively training a first new spam filter using machine learning and new data;

means for determining a first set of differences between the existing spam filter and the first new spam filter that satisfy a threshold or heuristic;

means for training a second new spam filter using the new data subject to a constraint that parameter changes between the first new spam filter and the existing spam filter that did not satisfy the threshold or heuristic have same values in the second filter as they do in the existing filter;

means for determining a second set of differences between the second new spam filter and the existing spam filter; and

means for incrementally updating the existing spam filter with at least a subset of the second set of the differences.

40. The update system of claim 39, further comprising a means for requesting feature-specific updates to the existing spam filter at least in part by searching at least one of lookup tables and databases.

41. A computer readable medium having stored thereon computer-executable code for facilitating incremental updates to spam filters comprising:

code for obtaining information associated with a first set of differences resulting from comparing an existing spam filter to a first newly trained spam filter;

code for comparing absolute values of the first set of differences to one or more threshold values;

code for training a second newly trained spam filter such that elements of the second newly trained spam filter respectively corresponding to differences in the first set of differences having absolute values less than the threshold values are unchanged from the existing filter;

code for obtaining information regarding a second set of differences associated with comparing the existing filter and the second newly trained filter; and

code for updating the existing filter based on the second set of differences.