US6016546A — Efficient detection of computer viruses and other…

Claim 1

Independent Claim 165 words

A method of detecting the likelihood of the presence of any of a first set of known data traits in a data string, by use of a second set G of generic features and a third set S of signatures, wherein the generic features and the signatures are characteristic of said first set of data traits, said method comprising the steps of: a) loading the set G into a memory of a computer, b) locating occurrences within the data string of each generic feature in said set G, c) applying a first mapping from the occurrences located during step b) to obtain a subset S* of S, d) loading all signatures from the subset S* into a memory of said computer, e) locating occurrences within said data string of all signatures from the subset S*, and f) applying a second mapping from the occurrences located during step e) to identify a set of data traits that are likely to be present in the data string.

Claim 2

Independent Claim 165 words

A method of detecting the likelihood of the presence of any of a first set of known data traits in a data string, by use of a second set G of generic features and a third set S of signatures, wherein the generic features and the signatures are characteristic of said first set of data traits, said method comprising the steps of: a) loading the set G into a memory of a computer, b) locating occurrences within the data string of each generic feature in said set G, c) applying a first mapping from the occurrences located during step b) to obtain a subset S* of S, d) loading all signatures from the subset S* into a memory of said computer, e) locating occurrences within said data string of all signatures from the subset S*, and f) applying a second mapping from the occurrences located during step e) to identify a set of data traits that are likely to be present in the data string.

Claim 3

Dependent Claim 111 words

A method as set forth in claim 1, in which said first mapping comprises: c1) retrieving, for each generic feature occurring at least once in the data string, an associated list of signatures of said set S from a first lookup table, c2) concatenating all of the retrieved associated signature lists to form a concatenated signature list, c3) tallying the number of occurrences of each signature within the concatenated signature list, and c4) forming said subset S* from all signatures s for which the tallied number of occurrences in the concatenated signature list is not less than a threshold for s computed from a value obtained from a second lookup table.

Claim 4

Dependent Claim 141 words

A method as set forth in claim 2, in which the first lookup table is derived automatically from a collection of data strings, each data string possessing at least one of the data traits, comprising the steps of: L1a) locating all occurrences of each generic feature of set G and each signature of set S within each data string in said collection, L1b) defining an associated feature list for each signature s, consisting of all generic features that occur in every member of a defined subset of the set of said data strings in which said signature s is present, L1c) defining, for each generic feature g, an associated signature list of all signatures that include g among their associated feature lists, and L1d) forming said first lookup table by storing each generic feature g with the associated signature list thereof.

Claim 5

Dependent Claim 34 words

A method as set forth in claim 3, wherein the defined subset of the set of said data strings in which said signature s is present is the set of said data strings itself.

Claim 6

Dependent Claim 123 words

A method as set forth in claim 3, wherein the defined subset of the set of said data strings in which said signature s is present is derived from said set of data strings and a set of at most one supplied set of associated data traits for each data string, comprising the steps of: a) including each data string in said set of data strings in said subset of data strings, and b) for each data string in said set for which a set of associated data traits has been supplied, eliminating that data string from said subset if its supplied set of associated data traits and the data traits associated with s by said second mapping contain no common data traits.

Claim 7

Dependent Claim 149 words

A method as set forth in claim 2, in which the second lookup table is derived automatically from a collection of data strings, each data string possessing at least one of the data traits, comprising the steps of: L2a) locating all occurrences of each generic feature of set G and each signature of set S within each data string in the collection, L2b) for each signature s, i) defining an associated feature list for each signature s, consisting of all generic features that occur in every member of a defined subset of the set of said data strings in which said signature s is present, ii) tallying the number of distinct generic features within said associated feature list, and iii) computing a function of said tally for said signature s, and L2c) forming said second lookup table by storing each signature s with the function of said tally thereof.

Claim 8

Dependent Claim 19 words

A method as set forth in claim 6, in which the function of the tally is the tally itself.

Claim 9

Dependent Claim 31 words

A method as set forth in claim 6, in which the function of the tally is the greater of a first chosen constant or the tally minus a second chosen constant.

Claim 10

Dependent Claim 43 words

A method as set forth in claim 1, comprising the further step, in dependence upon whether any identified set of data traits is likely to be present in said data string, of signaling the identity of the data traits of said identified set.

Claim 11

Dependent Claim 38 words

A method as set forth in claim 1, comprising the further step, in dependence upon whether any signatures are loaded in to memory pursuant to step (d), of freeing said signatures from memory after carrying out step (e).

Claim 12

Dependent Claim 29 words

A method as set forth in claim 1, comprising the further step, in dependence upon whether any signatures are loaded in to memory, of caching said signatures in memory.

Claim 13

Dependent Claim 19 words

A method as set forth in claim 1, 2, 3, or 6, wherein the data traits are computer viruses.

Claim 14

Dependent Claim 27 words

A method as set forth in claim 1, 2, 3, or 6, wherein each data trait is a property of having been compiled by a specific compiler.

Claim 15

Dependent Claim 31 words

A method as set forth in claim 1, 2, 3, or 6, wherein each data trait is a computer virus identifiable by at least one signature of said third set S.

Claim 16

Dependent Claim 52 words

A method as set forth in claim 1, 2, 3, or 6, wherein each data trait is a computer virus identifiable by at least one signature of said third set S, said second set G of generic features requiring a smaller memory size for storage than said third set S of signatures.

Claim 17

Dependent Claim 189 words

A program storage device readable by a computing machine, tangibly embodying a program of instructions executable by the machine to perform method steps of a method of detecting the likelihood of the presence of any of a first set of known data traits in a data string, by use of a second set G of generic features and a third set S of signatures, wherein the generic features and the signatures are characteristic of said first set of data traits, said method comprising the steps of: a) loading the set G into a memory of a computer, b) locating occurrences within the data string of each generic feature in said set G, c) applying a first mapping from the occurrences located during step b) to a subset S* of S, d) loading all signatures from the subset S* into a memory of said computer, e) locating all occurrences within said data string of all signatures from the subset S*, and f) applying a second mapping from the occurrences located during step e) to identify a set of data traits that are likely to be present in the data string.

Claim 18

Dependent Claim 189 words

A program storage device readable by a computing machine, tangibly embodying a program of instructions executable by the machine to perform method steps of a method of detecting the likelihood of the presence of any of a first set of known data traits in a data string, by use of a second set G of generic features and a third set S of signatures, wherein the generic features and the signatures are characteristic of said first set of data traits, said method comprising the steps of: a) loading the set G into a memory of a computer, b) locating occurrences within the data string of each generic feature in said set G, c) applying a first mapping from the occurrences located during step b) to a subset S* of S, d) loading all signatures from the subset S* into a memory of said computer, e) locating all occurrences within said data string of all signatures from the subset S*, and f) applying a second mapping from the occurrences located during step e) to identify a set of data traits that are likely to be present in the data string.

Claim 19

Dependent Claim 114 words

A program storage device as set forth in claim 16, in which said first mapping comprises: c1) retrieving, for each generic feature occurring at least once in the data string, an associated list of signatures of said set S from a first lookup table, c2) concatenating all of the retrieved associated signature lists to form a concatenated signature list, c3) tallying the number of occurrences of each signature present within the concatenated signature list, and c4) forming said subset S* from all signatures s for which the tallied number of occurrences in the concatenated signature list is not less than a threshold for s computed from a value obtained from a second lookup table.

Claim 20

Dependent Claim 144 words

A program storage device as set forth in claim 17, in which the first lookup table is derived automatically from a collection of data strings, each data string possessing at least one of the data traits, comprising the steps of: L1a) locating all occurrences of each generic feature of set G and each signature of set S within each data string in said collection, L1 b) defining an associated feature list for each signature s, consisting of all generic features that occur in every member of a defined subset of the set of said data strings in which said signature s is present, L1c) defining, for each generic feature g, an associated signature list of all signatures that include g among their associated feature lists, and L1d) forming said first lookup table by storing each generic feature g with the associated signature list thereof.

Claim 21

Dependent Claim 34 words

A method as set forth in claim 18, wherein the defined subset of the set of said data strings in which said signature s is present is the set of said data strings itself.

Claim 22

Dependent Claim 123 words

A method as set forth in claim 18, wherein the defined subset of the set of said data strings in which said signature s is present is derived from said set of data strings and a set of at most one supplied set of associated data traits for each data string, comprising the steps of: a) including each data string in said set of data strings in said subset of data strings, and b) for each data string in said set for which a set of associated data traits has been supplied, eliminating that data string from said subset if its supplied set of associated data traits and the data traits associated with s by said second mapping contain no common data traits.

Claim 23

Dependent Claim 151 words

A program storage device as set forth in claim 17, in which the second lookup table is derived automatically from a collection of data strings, each data string possessing at least one of the data traits, comprising the steps of: L2a) locating all occurrences of each generic feature of set G and each signature of set S within each data string in the collection, L2b) for each signature s, i) defining an associated feature list for each signature s, consisting of all generic features that occur in every member of a defined subset of the set of said data strings in which said signature s is present, ii) tallying the number of distinct generic features within said associated feature list, and iii) computing a function of said tally for said signature s, and L2c) forming said second lookup table by storing each signature s with the function of said tally thereof.

Claim 24

Dependent Claim 21 words

A program storage device as set forth in claim 19, in which the function of the tally is the tally itself.

Claim 25

Dependent Claim 33 words

A program storage device as set forth in claim 19, in which the function of the tally is the greater of a first chosen constant or the tally minus a second chosen constant.

Claim 26

Dependent Claim 45 words

A program storage device as set forth in claim 16, comprising the further step, in dependence upon whether any identified set of data traits is likely to be present in said data string, of signaling the identity of the data traits of said identified set.

Claim 27

Dependent Claim 40 words

A program storage device as set forth in claim 16, comprising the further step, in dependence upon whether any signatures are loaded in to memory pursuant to step (d), of freeing said signatures from memory after carrying out step (e).

Claim 28

Dependent Claim 31 words

A program storage device as set forth in claim 16, comprising the further step, in dependence upon whether any signatures are loaded in to memory, of caching said signatures in memory.

Claim 29

Dependent Claim 21 words

A program storage device as set forth in claim 16, 17, 18, or 19, wherein the data traits are computer viruses.

Claim 30

Dependent Claim 29 words

A program storage device as set forth in claim 16, 17, 18, or 19, wherein each data trait is a property of having been compiled by a specific compiler.

Claim 31

Dependent Claim 33 words

A program storage device as set forth in claim 16, 17, 18, or 19, wherein each data trait is a computer virus identifiable by at least one signature of said third set S.

Claim 32

Dependent Claim 54 words

A program storage device as set forth in claim 16, 17, 18, or 19, wherein each data trait is a computer virus identifiable by at least one signature of said third set S, said second set G of generic features requiring a smaller memory size for storage than said third set S of signatures.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-01-17	2003-07-19	2004-01-18	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-01-17	2007-07-19	2008-01-18	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-01-17	2011-07-19	2012-01-18	$7700.00	Window Closed / Lapsed

Efficient detection of computer viruses and other data traits

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag