MDL compress system and method for signature inference and masquerade intrusion detection

1. An intrusion masquerade detection method, comprising:

applying a compression algorithm to one or more sets of user input content data to build a set of user grammars;

forming at least one model for the set of user grammars using characteristics of the set of user grammars, the characteristics including a first estimated algorithmic minimum sufficient statistic for the set of user grammars;

storing the at least one model for the set of user grammars in a database;

calculating a second estimated algorithmic minimum sufficient statistic for at least one target block of other input content data by applying the compression algorithm to the at least one target block of the other input content data;

determining a distance between the at least one target block of the other input content data and the at least model for the set of user grammars by comparing the first estimated algorithmic minimum sufficient statistic and the second estimated algorithmic minimum sufficient statistic;

determining an intrusion masquerade based on the determined distance; and

outputting an indication of the determined intrusion masquerade.

2. The intrusion masquerade detection method of claim 1 , the at least one model for the set of user grammars comprising a healthy session model and a masquerade model.

3. The intrusion masquerade detection method of claim 1 , the determining an intrusion masquerade including:

calculating an inverse compression ratio over a time period for the at least one target block of the other input content data;

comparing the calculated inverse compression ratio for the at least one target block of the other input content data to at least one inverse compression ratio associated with a compressed data set of the at least one model for the set of user grammars; and

determining an intrusion masquerade event based on a difference between the calculated inverse compression ratio for the at least one target block of the other input content data and the at least one inverse compression ratio associated with the compressed data set of the at least one model for the set of user grammars exceeding a threshold.

4. The intrusion masquerade detection method of claim 1 , the compression algorithm being an algorithm that estimates Kolmogorov complexity.

5. The intrusion masquerade detection method of claim 4 , the compression algorithm being a grammar-based compression algorithm that forms compressive grammar based on Minimum Description Length (MDL) principles.

6. The intrusion masquerade detection method of claim 1 , the compression algorithm being applied to the at least one target block of the other input content data in linear time.

7. The intrusion masquerade detection method of claim 1 , a separate set of user grammars being associated with each individual user.

8. The intrusion masquerade detection method of claim 1 , the calculating the second estimated algorithmic minimum sufficient statistic for the at least one target block of other input content data, the determining the distance between the at least one target block of the other input content data and the at least one model for the set of user grammars, the determining the intrusion masquerade based on the distance, and the outputting the indication of the determined intrusion masquerade, being performed in real-time.

9. The intrusion masquerade detection method of claim 1 , the calculating the second estimated algorithmic minimum sufficient statistic by applying the compression algorithm to at least one target block of the other input content data, further comprising:

searching, in real-time, a string of the other input content data for MDL compression phrases from the at least one model for the set of user grammars;

substituting with Huffman code for found phrases;

sorting the set of user grammars so that longest phrases are applied first to an unclassified string of the other input content data and

attributing a cost for phrases that are not found in the at least one model for the set of user grammars by quantifying a cost of explicitly representing symbols associated with the phrases.

10. A machine-implemented grammar inference engine for intrusion masquerade detection, comprising:

a pre-processing device that receives one or more sets of user input content data and outputs filtered data;

a grammar generating device that is coupled to the pre-processing device and that is configured (1) to generate a set of user grammars by applying a compression algorithm to the filtered data and (2) to form at least one model for the set of user grammars using characteristics of the set of user grammars the characteristics including a first estimated algorithmic minimum sufficient statistic for the set of user grammars; and

a grammar applying device that is coupled to a classifier that compares the first algorithmic minimum sufficient statistic for the set of user grammars generated by the grammar generating device to a second estimated algorithmic sufficient statistic for at least one target block of other input content data, calculated using the compression algorithm, and that determines a distance between the at least one target block of the other input content data and the at least model for the set of user grammars,

the classifier being coupled to the grammar applying device and to a post-processor, the classifier receiving (1) distance values representing determined distances from the grammar applying device and (2) decision criteria from the post-processor, the classifier being configured to calculate a likelihood of fit between the at least one target block of the other input content data and the at least one model for the set of user grammars based on the comparison provided by the grammar applying device as an indication of an intrusion masquerade.

11. The machine-implemented grammar inference engine of claim 10 , further comprising a grammar database coupled to the grammar applying device and to the grammar generating device that stores the at least one model for the set of user grammars.

12. The machine-implemented grammar inference engine of claim 10 , the compression algorithm being an algorithm that estimates Kolmogorov complexity.

13. The machine-implemented grammar inference engine of claim 12 , the compression algorithm being a grammar-based compression algorithm which forms compressive grammar based on MDL principles.

14. The machine-implemented grammar inference engine of claim 10 , the pre-processing device applying a sliding window protocol to segment portions of the one or more sets of input content data.

15. The machine-implemented grammar inference engine of claim 10 , the grammar applying device and the grammar generating device executing the compression algorithm in linear time.

16. A non-transitory computer-readable medium upon which is embodied a sequence of programmable instructions which, when executed by a processor, cause the processor to perform an intrusion masquerade detection method comprising:

applying a compression algorithm to one or more sets of user input content data to build a set of user grammars;

forming at least one model for the set of user grammars using characteristics of the set of user grammars, the characteristics including a first estimated algorithmic minimum sufficient statistic for the set of user grammars;

storing the at least one model for the set of user grammars in a database;

calculating a second estimated algorithmic minimum sufficient statistic for at least one target block of other input content data by applying the compression algorithm to the at least one target block of the other input content data;

determining a distance between the at least one target block of the other input content data and the at least model for the set of user grammars by comparing the first estimated algorithmic minimum sufficient statistic and the second estimated algorithmic minimum sufficient statistic;

determining an intrusion masquerade based on the determined distance; and

outputting an indication of the determined intrusion masquerade.

17. The non-transitory computer-readable medium of claim 16 , the calculating the second estimated algorithmic minimum sufficient statistic for the at least one target block of the other input content data, the determining the distance between the at least one target block of the other input content data and the at least one model for the set of user grammars, the determining the intrusion masquerade based on the distance, and the outputting the indication of the intrusion masquerade, are performed in real-time.

18. The non-transitory computer-readable medium of claim 16 , the calculating the second estimated algorithmic minimum sufficient statistic by applying the compression algorithm to at least one target block of the other input content data, further comprising:

searching, in real-time, a string of the other input content data for MDL compression phrases from the at least one model for the set of user grammars;

substituting with Huffman code for found phrases;

sorting the set of user grammars so that longest phrases are applied first to an unclassified string of the other input content data and

attributing a cost for phrases that are not found in the at least one model for the set of user grammars by quantifying a cost of explicitly representing symbols associated with the phrases.