Matching engine with signature generation

• US 7,516,130 B2
• Filed: 02/24/2006
• Issued: 04/07/2009
• Est. Priority Date: 05/09/2005
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: Trend Micro Inc.
• Inventors: Huang, Shu, Ren, Liwei, Huang, Fei, Dong, Aiguo, Tan, Dehua
• Primary Examiner(s): Wassum; Luke S
• Application Number:
  US11/361,340
• Publication Number:
  US 20060253438A1
• Time in Patent Office: 1,138 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A system and a method generates at least one signature associated with document. In one embodiment, a document comprised of text is received and parsed to generate a token set. The token set includes a plurality of tokens. Each token corresponds to the text in the document that is separated by a predefined character characteristic. A score is calculated for each token in the token set based on a frequency and distribution of the text in the document. Each token is then ranked based on the calculated score. A subset of the ranked tokes is selected and a signature is generated for each occurrence of the selected tokens. The selected list of signatures is then output.

Claims

1. A method for generating a plurality of signatures associated with a document, the method comprising:

receiving a document comprising text;

parsing the document to generate a token set comprising a plurality of tokens, each token corresponding to the text in the document separated by a predefined character characteristic;

calculating a score for each token in the token set based on a frequency and distribution of occurrences of the text in the document;

ranking each token in the token set based on the calculated score;

selecting, from the ranked tokens, a predetermined number of top ranked tokens to limit a number of signatures generated for said document; and

generating a signature for each occurrence of the selected tokens,

wherein said score calculation is such that a more even distribution of the occurrences of the text in the document results in a higher score, and

wherein said score for each token is proportional to a first quantity divided by a second quantity, further wherein the first quantity comprises a position of a last occurrence of the text in the document minus a position of a first occurrence of the text in the document, and further wherein the second quantity comprises a square root of a sum of squares of differences in positions between adjacent occurrences of the text in the document.

2. The method of claim 1, wherein the predefined character characteristic comprises a delimiter.

3. The method of claim 1, further comprising outputting the predetermined number of top signatures in a list.

4. The method of claim 1, wherein the document is an ASCII document.

5. The method of claim 1, further comprising outputting a list of the generated signatures.

6. A computer readable storage medium storing instructions executable by a processor, the instructions when executed causing a processor to:

receive a document comprising text;

parse the document to generate a token set comprising a plurality of tokens, each token corresponding to the text in the document separated by a predefined character characteristic;

calculate a score for each token in the token set based on a frequency and distribution of the text in the document;

rank each token in the token set based on the calculated score;

select, from the ranked tokens a predetermined number of top ranked tokens to limit a number of signatures generated for said document; and

generate a signature for each occurrence of the selected tokens,

wherein said score calculation is such that a more even distribution of the occurrences of the text in the document results in a higher score, and

wherein said score for each token is proportional to a first quantity divided by a second quantity, further wherein the first quantity comprises a position of a last occurrence of the text in the document minus a position of a first occurrence of the text in the document, and further wherein the second quantity comprises a square root of a sum of squares of differences in positions between adjacent occurrences of the text in the document.

7. The computer readable storage medium of claim 6, wherein the predefined character characteristic comprises a delimiter.

8. The computer readable storage medium of claim 6, further comprising instructions to cause the processor to output a predetermined number of top signatures in a list.

9. The computer readable storage medium of claim 6, wherein the document is an ASCII document.

10. The computer readable storage medium of claim 6, wherein the instructions when executed by the processor further cause the processor to output a list of the generated signatures.