Document fingerprinting with asymmetric selection of anchor points

• US 8,359,472 B1
• Filed: 03/25/2010
• Issued: 01/22/2013
• Est. Priority Date: 03/25/2010
• Status: Active Grant

• Current Assignee: Trend Micro Inc.
• Original Assignee: Trend Micro Inc.
• Inventors: Ren, Liwei, Xu, Qiuer
• Primary Examiner(s): ZECHER, CORDELIA P K
• Application Number:
  US12/731,874
• Time in Patent Office: 1,034 Days
• Field of Search: None
• US Class Current: 713/176
• CPC Class Codes: G06F 16/325 Hash tables
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 21/556 involving covert channels, i.e. data leakage between processes inhibiting the analysis of circuitry or operation with measures against power attack G06F21/755

Abstract

One embodiment relates to a computer-implemented process for generating document fingerprints. A document is normalized to create a normalized text string. A first hash function with a sliding hash window is applied to the normalized text string to generate an array of hash values. Candidate anchoring points are selected by applying a first filter to the array of hash values. The anchoring points are chosen by applying a second filter to the candidate anchoring points. Finally, a second hash function is applied to substrings located at the chosen anchoring points to generate hash values for use as fingerprints for the document. Other embodiments and aspects are also disclosed.

Claims

1. A computer-implemented process for generating document fingerprints, the method being performed using a computer including at least a processor, data storage, and computer-readable instructions, and the method comprising:

normalizing a document to create a normalized text string;

applying a first hash function with a sliding hash window to the normalized text string to generate an array of hash values;

applying a first filter to the array of hash values to select candidate anchoring points;

applying a second filter to the candidate anchoring points to select anchoring points; and

applying a second hash function to substrings located at the selected anchoring points to generate hash values for use as fingerprints of the document.

2. The process of claim 1, wherein the first hash function and the second hash functions are different functions.

3. The process of claim 1, wherein the first hash function comprises a Karp-Rabin function.

4. The process of claim 3, wherein the second hash function comprises a string hash function which is different from a Karp-Rabin function.

5. The process of claim 1, wherein the first filter selects those hash values h which satisfy h=0 mod p, where p is a prime number.

6. The process of claim 1, wherein the second filter divides the normalized text into a plurality of pieces and selects one anchoring point per piece.

7. The process of claim 6, wherein the pieces are of equal size, except for a last piece.

8. The process of claim 6, wherein if there are multiple candidate anchoring points in a single piece, then the candidate anchoring point closest to the centre of that piece is chosen to be the anchoring point for that piece.

9. The process of claim 1, wherein the fingerprints generated for a repository of sensitive documents along with corresponding document identifiers are indexed to create a fingerprint database.

10. A computer-implemented method for document leakage prevention, the method comprising:

applying a first procedure to sensitive documents to be protected, the first procedure using a first filter and a second filter to choose anchoring points and generating fingerprints based on the chosen anchoring points; and

applying a second procedure to a target document to be inspected for sensitive text, the second procedure using the first filter, but not the second filter, to select anchoring points and generating target fingerprints based on the selected anchoring points.

11. The method of claim 10, wherein the first procedure is applied at a server and is used to generate a fingerprint database.

12. The method of claim 11, wherein the second procedure is applied at a client computer and is used to detect sensitive text within the target document by matching the target fingerprints against the fingerprint database.

13. A computer apparatus configured to generate document fingerprints, the apparatus comprising:

data storage configured to store computer-readable instruction code and data;

a processor configured to access the data storage and to execute said computer-readable instruction code;

computer-readable instruction code configured to normalize a computer-readable document to create a normalized text string;

computer-readable instruction code configured to apply a first hash function with a sliding hash window to the normalized test string to generate an array of hash values;

computer-readable instruction code configured to apply a first filter to the array of hash values to select candidate anchoring points;

computer-readable instruction code configured to apply a second filter to the candidate anchoring points to select anchoring points; and

computer-readable instruction code configured to apply a second hash function to substrings located at the selected anchoring points to generate hash values for use as fingerprints of the document.

14. The computer apparatus of claim 13, wherein the first hash function comprises a Karp-Rabin function.

15. The computer apparatus of claim 14, wherein the second hash function comprises a string hash function which is different from a Karp-Rabin function.

16. The computer apparatus of claim 13, wherein the first filter selects those hash values h which satisfy h=0 mod p, where p is a prime number.

17. The computer apparatus of claim 13, wherein the second filter divides the text into a plurality of pieces and selects one anchoring point per piece.

18. The computer apparatus of claim 17, wherein if there are multiple candidate anchoring points in a single piece, then the candidate anchoring point closest to the centre of that piece is chosen to be the anchoring point for that piece.

19. The computer apparatus of claim 13, wherein the fingerprints generated for a repository of sensitive documents along with corresponding document identifiers are indexed to create a fingerprint database.

20. A data leakage prevention apparatus implemented on a distributed network of computer apparatus, the data leakage prevention apparatus comprising:

a server computer configured to apply a first procedure to sensitive documents to be protected, the first procedure using a first filter and a second filter to choose anchoring points and generating fingerprints based on the chosen anchoring points; and

a plurality of end-point computers configured to each apply a second procedure to a target document to be inspected for sensitive text, the second procedure using the first filter, but not the second filter, to select anchoring points and generating target fingerprints based on the selected anchoring points.

21. The data leakage prevention apparatus of claim 20, wherein the first procedure is used to generate a fingerprint database, and wherein the second procedure is used to detect sensitive text within the target document by matching the target fingerprints against the fingerprint database.