Methods for categorizing input data

• US 20070116267A1
• Filed: 11/28/2005
• Published: 05/24/2007
• Est. Priority Date: 04/01/2003
• Status: Active Grant

• Current Assignee: Sytex, Inc. (Leidos Holdings, Inc.)
• Original Assignee: Sytex, Inc. (Leidos Holdings, Inc.)
• Inventors: Speirs, William, Cole, Eric
• Granted Patent: US 7,748,036 B2
• Time in Patent Office: Days
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/26 Testing cryptographic entity, e.g. testing integrity of encryption key or encryption algorithm
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 9/06 the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators

Abstract

Methods are provided for categorizing input data into a selected data type category. Exemplary embodiments are directed to the categorization of binary input data, for example random input data, as either compressed or encrypted based on statistical analysis. To this end, at least a portion of the input data is analyzed to derive a statistical test result for the portion that is indicative of a degree of randomness of the data. The data is then categorized as either compressed or encrypted based on the statistical test result.

Claims

1. A method of categorizing random input data, comprising:

a. analyzing at least a portion of the input data to derive a statistical test result for said portion which is indicative of a degree of randomness of the input data; and

b. categorizing said input data as either compressed or encrypted based on said statistical test result.

2. A method according to claim 1 wherein said input data comprises a series of bits, each of which is analyzed to derive said statistical test result.

3. A method according to claim 1 whereby said statistical test result produces a χ

² value relating to the input data'"'"'s degree of randomness.

4. A method according to claim 3 whereby the input data is categorized as compressed if said χ

² value is within a pre-determined threshold range.

5. A method according to claim 1 wherein said input data comprises a series of bits and whereby said statistical test result is obtained by conducting a statistical test against the input data that is selected from a group of tests consisting of:

a frequency test, a serial (two-bit) test, a poker test, a runs test, an autocorrelation test, Maurer'"'"'s universal statistical test, a monotonically increasing test, and a monotonically decreasing test.

6. A method according to claim 5 further comprising:

c. conducting a plurality of statistical tests against the input data to derive a plurality of preliminary test results each being indicative of a degree of randomness of one or more distinct characteristics of the input data;

d. assigning a weighting value to each preliminary test result to generate a plurality of weighted test results;

e. summing the weighted test results to produce a weighted sum which corresponds to said statistical test result; and

f. categorizing the input data as compressed if said weighted sum is within a selected threshold range, or encrypted if said weighted sum is outside of the selected threshold range.

7. A method according to claim 6 whereby each weighting value is determined by an optimization algorithm.

8. A method according to claim 7 wherein said optimization algorithm is a genetic algorithm.

9. A method according to claim 1 wherein said random input data is one of a data file and a contiguous data stream.

10. A method according to claim 9 wherein the random input data is a data file, which includes a file header and a data portion, and whereby said statistical result is derived by analyzing only said data portion.

11. A data categorization method, comprising:

a. establishing a data categorization schema;

b. receiving binary input data of an unknown data type;

c. conducting a plurality of different statistical tests on the input data, each of which analyzes one or more distinct characteristics thereof to derive an associated statistical test result which is indicative of a degree of randomness for the input data; and

d. categorizing the input data into a selected data type category based on said statistical test results and said data categorization schema.

12. A data categorization method according to claim 11 wherein said input data comprises a series of bits, each of which is analyzed to derive each statistical test result.

13. A data categorization method according to claim 11 whereby said data categorization schema is established by:

a. selecting a plurality of data files, each of a known data type;

b. compressing at least a portion of each data file to produce a corresponding compressed file;

c. encrypting at least a portion of each data file to produce a corresponding encrypted file;

d. conducting a plurality of said statistical tests against each compressed file thereby to derive a distribution of compression test results for each statistical test;

e. conducting said statistical tests against each encrypted file thereby to derive a distribution of encryption test results for each statistical test;

f. deriving a first set of mathematical expressions which conform to the distributions of compression test results;

g. deriving a second set of mathematical expressions which conform to the distributions of encryption test results;

h. solving, with respect to each statistical test, for an intersection of the corresponding first and second mathematical expressions, thereby defining an associated threshold range within which a given test result is indicative of data compression, and outside of which a given test result is indicative of data encryption; and

i. deriving a decision-making rule based on said threshold ranges such that the binary input data can be categorized as either;

(1) compressed if said statistical test results satisfy said decision-making rule, or

(2) encrypted if said statistical test results fail to satisfy said decision-making rule.

14. A data categorization method according to claim 13 whereby said binary input data is categorized as compressed if a majority of said statistical tests are indicative of data compression, otherwise said binary input data is categorized as encrypted.

15. A data categorization method according to claim 13 wherein each data file includes a file header and a data portion, and whereby only said data portion is compressed and encrypted.

16. A data categorization method according to claim 15 whereby said file header is removed prior to creation of the corresponding compressed file and the corresponding encrypted file.

17. A data categorization method according to claim 11 whereby each of said statistical tests is selected from a group of tests consisting of:

a frequency test, a serial (two-bit) test, a poker test, a runs test, an autocorrelation test, Maurer'"'"'s universal statistical test, a monotonically increasing test, and a monotonically decreasing test.

18. A data categorization method according to claim 11 wherein said binary input data is one of a data file and a contiguous data stream.

19. A data categorization method according to claim 11 whereby the selected data type category is selected from a group of categories consisting of:

random data, plaintext data, encrypted data, compressed data and unknown data.

20. A data categorization method according to claim 11 wherein the selected data type category is one of encrypted data and compressed data.

21. A method of categorizing binary input data as either compressed or encrypted, comprising:

a. predetermining an associated χ

² threshold range for each of a plurality of statistical tests which may be employed to analyze test data, such that, for each statistical test a given χ

² test result is;

(1) indicative of data compression if it falls within the test'"'"'s associated χ

² threshold range, or

(2) indicative of data encryption if it falls outside the associated χ

² threshold range; and

b. pre-establishing a schema for categorizing test data as either compressed or encrypted based on said threshold ranges and on statistical test results to be obtained when conducted against test data;

c. receiving input data for testing, wherein said input data is one of;

(1) a data file; and

(2) a contiguous data stream;

d. conducting each said statistical test on an associated portion of the input data to derive a set of actual χ

² test results; and

e. categorizing said input data as either compressed or encrypted based on whether said actual χ

² test results satisfy or fail to satisfy said schema.

22. A method according to claim 21 whereby each statistical test is selected from a group of tests consisting of:

a frequency test, a serial (two-bit) test, a poker test, a runs test, an autocorrelation test, Maurer'"'"'s universal statistical test, a monotonically increasing test, and a monotonically decreasing test.

23. A method according to claim 22 whereby said input data is categorized as compressed if a majority of the actual χ

² test results are indicative of data compression, otherwise said binary input data is categorized as encrypted.

24. A method according to claim 21 whereby said input data is categorized as compressed if a majority of the actual χ

² test results are indicative of data compression, otherwise said binary input data is categorized as encrypted.

25. A method according to claim 21 whereby said χ

² threshold ranges are predetermined by;

a. selecting a plurality of data files, each of a known data type;

b. compressing at least a portion of each data file to produce a corresponding compressed file;

c. encrypting at least a portion of each data file to produce a corresponding encrypted file;

d. conducting a plurality of said statistical tests against each compressed file thereby to derive a distribution of compression test results for each statistical test;

e. conducting said statistical tests against each encrypted file thereby to derive a distribution of encryption test results for each statistical test;

f. deriving a first set of mathematical expressions which conform to the distributions of compression test results;

g. deriving a second set of mathematical expressions which conform to the distributions of encryption test results; and

h. solving, with respect to each statistical test, for an intersection of the corresponding first and second mathematical expressions, thereby defining an associated χ

² threshold range within which a given test result is indicative of data compression, and outside of which a given test result is indicative of data encryption.