US5675711A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Adaptive statistical regression and classification of data strings, with application to the generic detection of computer viruses
Assignee: Trend Micro Inc
•
Filing: 1994-05-13
•
Granted: 1997-10-07
•
Expires: 2014-05-13
Abstract
Abstract A data string is a sequence of atomic units of data that represent information. In the context of computer data, examples of data strings include executable programs, data files, and boot records consisting of sequences of bytes, or text files consisting of sequences of bytes or characters. The invention solves the problem of automatically constructing a classifier of data strings, i.e., constructing a classifier which, given a string, determines which of two or more class labels should be assigned to it. From a set of (string, class-label) pairs, this invention provides an automated technique for extracting features of data strings that are relevant to the classification decision, and an automated technique for developing a classifier which uses those features to classify correctly the data strings in the original examples and, with high accuracy, classify correctly novel data strings not contained in the example set. The classifier is developed using "adaptive" or "learning" techniques from the domain of statistical regression and classification, such as, e.g., multi-layer neural networks. As an example, the technique can be applied to the task of distinguishing files or boot records that are infected by computer viruses from files or boot records that are not infected.
Inventors
- 👤 Jeffrey Owen Kephart
- 👤 Gregory Bret Sorkin
- 👤 Gerald James Tesauro
- 👤 Steven Richard White
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 04:30
CPC Classifications
G; G06; G06F; G06F21/00; G06F21/50; G06F21/55; G06F21/56; G06F21/562; G06F21/564
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
93 words
A method of constructing a classifier of data strings, comprising: defining a set of classes, wherein one of the classes is a default class; providing a labelled set of exemplars from a plurality of the classes; defining a set of features, based on the examplars, that are statistically likely to be relevant to the classification; developing a classifier that uses the occurrence frequency of the features in an input string to classify that string, augmenting the number of exemplars in the default class with additional exemplars chosen from outside the plurality of classes.
Claim 2
Independent Claim
93 words
A method of constructing a classifier of data strings, comprising: defining a set of classes, wherein one of the classes is a default class; providing a labelled set of exemplars from a plurality of the classes; defining a set of features, based on the examplars, that are statistically likely to be relevant to the classification; developing a classifier that uses the occurrence frequency of the features in an input string to classify that string, augmenting the number of exemplars in the default class with additional exemplars chosen from outside the plurality of classes.
Claim 3
Dependent Claim
45 words
The method of claim 1, wherein developing the classifier comprises training the classifier on the exemplars to take as input a transformed function of the occurrence frequency of each of the features in a given data string, and to produce as output a class label.
Claim 4
Dependent Claim
27 words
The method of claim 2, wherein the transformed function of the occurrence frequency of each feature is zero if the occurrence frequency is zero, and one otherwise.
Claim 5
Dependent Claim
18 words
The method of claim 1, wherein the features are contiguous data sequences possessing lengths within a specified range.
Claim 6
Dependent Claim
20 words
The method of claim 1, wherein each of the features is common in one class and uncommon in other classes.
Claim 7
Dependent Claim
13 words
The method of claim 1, wherein the additional exemplars resemble the default exemplars.
Claim 8
Independent Claim
300 words
A method of constructing a classifier of data strings, comprising: providing a labelled set of exemplars from a plurality of classes; augmenting the number of exemplars in the default class with additional exemplars chosen from outside the plurality of classes, wherein the additional exemplars resemble the default exemplars; defining a set of features, based on the exemplars, that are statistically likely to be relevant to the classification, the features being contiguous data sequences possessing lengths within a specified range, and which are common in one class and uncommon in other classes, wherein defining a set of features comprises: for each class: forming a minimal list of all features which appear among the exemplars of that class with a relative frequency greater than a specified threshold; and eliminating from the list every feature for which the value of a specified monotonically non-decreasing multi-variate function of the relative frequencies of that feature within each of the other classes is greater than a specified threshold; selecting from the remaining features in the list for each class a set of one or more features such that each exemplar in the class contains at least a number n cover of the features in the set; selecting from the remaining features in the list for each class a set of one or more features having orthogonal patterns of occurrence among the exemplars of that class, such that each exemplar in that class contains at least n cover of the features in the set; developing a classifier that uses the occurrence frequency of the features in an input string to classify that string, wherein developing the classifier comprises training the classifier on the exemplars to take as input a function of the occurrence frequency of each of the features, and to produce as output a class label.
Claim 9
Independent Claim
300 words
A method of constructing a classifier of data strings, comprising: providing a labelled set of exemplars from a plurality of classes; augmenting the number of exemplars in the default class with additional exemplars chosen from outside the plurality of classes, wherein the additional exemplars resemble the default exemplars; defining a set of features, based on the exemplars, that are statistically likely to be relevant to the classification, the features being contiguous data sequences possessing lengths within a specified range, and which are common in one class and uncommon in other classes, wherein defining a set of features comprises: for each class: forming a minimal list of all features which appear among the exemplars of that class with a relative frequency greater than a specified threshold; and eliminating from the list every feature for which the value of a specified monotonically non-decreasing multi-variate function of the relative frequencies of that feature within each of the other classes is greater than a specified threshold; selecting from the remaining features in the list for each class a set of one or more features such that each exemplar in the class contains at least a number n cover of the features in the set; selecting from the remaining features in the list for each class a set of one or more features having orthogonal patterns of occurrence among the exemplars of that class, such that each exemplar in that class contains at least n cover of the features in the set; developing a classifier that uses the occurrence frequency of the features in an input string to classify that string, wherein developing the classifier comprises training the classifier on the exemplars to take as input a function of the occurrence frequency of each of the features, and to produce as output a class label.
Claim 10
Independent Claim
171 words
A method of constructing a classifier of data strings, comprising: providing a labelled set of exemplars from a plurality of classes; defining a set of features, based on the exemplars, that are statistically likely to be relevant to the classification, comprising: for each class: forming a list of each feature for which the average of a transformed frequency, defined as a specified transforming function of the occurrence frequency of that feature, among the exemplars of that class exceeds a predetermined threshold; eliminating from the list every feature for which the value of a specified monotonically non-decreasing multi-variate function of the average of the transformed frequency of that feature in each of the other classes exceeds a predetermined threshold; developing a classifier that uses the occurrence frequency of the features in an input string to classify that string, wherein developing the classifier comprises training the classifier on the exemplars to take as input a function of the occurrence frequency of each of the features, and to produce as output a class label.
Claim 11
Independent Claim
171 words
A method of constructing a classifier of data strings, comprising: providing a labelled set of exemplars from a plurality of classes; defining a set of features, based on the exemplars, that are statistically likely to be relevant to the classification, comprising: for each class: forming a list of each feature for which the average of a transformed frequency, defined as a specified transforming function of the occurrence frequency of that feature, among the exemplars of that class exceeds a predetermined threshold; eliminating from the list every feature for which the value of a specified monotonically non-decreasing multi-variate function of the average of the transformed frequency of that feature in each of the other classes exceeds a predetermined threshold; developing a classifier that uses the occurrence frequency of the features in an input string to classify that string, wherein developing the classifier comprises training the classifier on the exemplars to take as input a function of the occurrence frequency of each of the features, and to produce as output a class label.
Claim 12
Dependent Claim
41 words
The method of claim 8, wherein the monotonically non-decreasing multi-variate function is the occurrence frequency of the given feature among all exemplars except those in the given class, divided by the total number of units of data contained in those exemplars.
Claim 13
Dependent Claim
43 words
The method of claim 8, wherein the monotonically non-decreasing multi-variate function is the number of exemplars not in the given class that contain one or more instances of the given feature, divided by the total number of exemplars not in the given class.
Claim 14
Dependent Claim
45 words
The method of claim 8, further comprising: selecting from the remaining features in the list a cover comprising a set of one or more features such that each exemplar in the class contains at least a number n cover of the features in that class.
Claim 15
Dependent Claim
21 words
The method of claim 11, wherein the number of features in the list for each class is minimal, or nearly minimal.
Claim 16
Dependent Claim
52 words
The method of claim 8, further comprising: selecting from the remaining features in the list an incomplete cover comprising a set of one or more features such that the number of exemplars in the class containing at least a number n cover of the features in the set exceeds a specified threshold.
Claim 17
Dependent Claim
36 words
The method of claim 8, further comprising: selecting features from the remaining features in the list for each class such that the selected features have maximally orthogonal patterns of occurrence among the exemplars of that class.
Claim 18
Dependent Claim
18 words
The method of claim 14, wherein the orthogonal patterns of occurrence are determined using a Gram-Schmidt orthogonalization procedure.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-10-06 | 2001-04-07 | 2001-10-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-10-06 | 2005-04-07 | 2005-10-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-10-06 | 2009-04-07 | 2009-10-07 | $7700.00 | Window Closed / Lapsed |