System and method for matching pattern

• US 9,392,005 B2
• Filed: 05/26/2011
• Issued: 07/12/2016
• Est. Priority Date: 05/27/2010
• Status: Active Grant

• Current Assignee: Samsung SDS (China) Co., Ltd. (Samsung Group)
• Original Assignee: Samsung SDS (China) Co., Ltd. (Samsung Group)
• Inventors: Yoo, InSeon
• Primary Examiner(s): Reyes, Mariela
• Assistant Examiner(s): Black, Linh
• Application Number:
  US13/116,419
• Publication Number:
  US 20110295894A1
• Time in Patent Office: 1,874 Days
• Field of Search: 707/698, 707/747, 382/159, 382/170, 382/181, 704/221, 706/48
• US Class Current: 1/1
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

System and method for matching a pattern are provided. The pattern matching method includes performing a sub pattern matching operation to match at least one sub data of a plurality of sub data of a target data with a pre-stored pattern data, and performing a full pattern matching operation to determine whether the target data is identical to at least the pre-stored pattern data by referring to a result of the sub pattern matching operation, and wherein the full pattern matching operation is performed or not performed according to a type of the pre-stored pattern data. Accordingly, an accurate matching operation is performed with respect to the target data of various patterns.

Claims

1. A malware pattern matching method comprising:

generating a hash matcher table comprising a hash value item displaying a hash value and an item displaying a pre-stored malware pattern data, or comprising the hash value item displaying the hash value and an item displaying whether a hash value of the pre-stored malware pattern data is identical to the hash value displayed on the hash value item;

dividing a target data into a plurality of sub data;

for at least one sub data of the plurality of sub data, generating a hash value of the sub data and comparing the generated hash value of the sub data and the hash matcher table;

generating a sub matcher table which comprises the hash value item displaying the hash value and a malware pattern data item displaying a malware pattern data corresponding to the hash value displayed on the hash value item;

only in response to the hash value of at least one sub data of the plurality of sub data existing in the hash matcher table, performing a sub pattern matching operation to match the at least one sub data of the plurality of sub data with the corresponding pre-stored malware pattern data by using the sub matcher table;

determining a type of the pre-stored malware pattern data;

in response to a determination that the type of the pre-stored malware pattern data is a grammatically complex malware pattern, performing a full pattern matching operation to determine whether the target data is identical to at least the pre-stored malware pattern data by referring to a result of the sub pattern matching operation; and

in response to a determination that the type of the pre-stored malware pattern data is a grammatically simple malware pattern, not performing the full pattern matching operation,

wherein performing the sub pattern matching operation comprises;

performing a light pattern matching operation to match a part of the one sub data with the pre-stored malware pattern data by using the sub matcher table; and

if the part of the one sub data is identical to or included in the pre-stored malware pattern data, performing an exact pattern matching operation to match a whole of the one sub data with a whole of the pre-stored malware pattern data.

2. The malware pattern matching method as claimed in claim 1, wherein, in response to the determination that the type of the pre-stored malware pattern data matched with the one sub data is part of the grammatically complex malware pattern, the result of the sub pattern matching operation is recorded on a sub pattern matrix.

3. The malware pattern matching method as claimed in claim 2, wherein the performing the full pattern matching operation comprises checking whether the sub pattern matching operation matches all malware sub patterns included in the sub pattern matrix.

4. The malware pattern matching method as claimed in claim 1, further comprising recording the result of the sub pattern matching operation on a sub pattern matrix,

wherein the performing the full pattern matching operation comprises checking whether the sub pattern matching operation matches all malware sub patterns included in the sub pattern matrix.

5. The malware pattern matching method as claimed in claim 1, wherein the part of the one sub data is at least one of a head value, a middle value, and a tail value of the one sub data.

6. The malware pattern matching method as claimed in claim 1, wherein the sub matcher table further comprises a middle value item displaying a middle value of the pre-stored malware pattern data and a tail value item displaying a tail value of the pre-stored malware pattern data.

7. The malware pattern matching method as claimed in claim 1, wherein the pattern data item displays an address where the pre-stored malware pattern data is stored or displays the pre-stored malware pattern data.

8. The malware pattern matching method as claimed in claim 1, wherein the sub matcher table further comprises a collision pattern offset item displaying a collision pattern offset value indicating whether one of the hash values of the pre-stored malware pattern data collides with another of the hash values of the pre-stored malware pattern data.

9. The malware pattern matching method as claimed in claim 8, wherein, if the one of the hash values of the pre-stored malware pattern data collides with the other of the hash values of the pre-stored malware pattern data, the collision pattern offset item displays the one of the hash values.

10. The malware pattern matching method as claimed in claim 1, wherein the performing the sub pattern matching operation comprises:

searching for a hash value identical to the hash value of the one sub data among the hash values displayed on the hash value item of the sub matcher table; and

comparing a malware pattern data corresponding to the searched for hash value and the one sub data.

11. The malware pattern matching method as claimed in claim 10, wherein the comparing comprises:

performing a light pattern matching operation to match a part of the one sub data with the pre-stored malware pattern data; and

only if the part of the one sub data is identical to or included in the pre-stored malware pattern data, performing an exact pattern matching operation to match a whole of the one sub data with the pre-stored malware pattern data.

12. The malware pattern matching method as claimed in claim 10, wherein the sub matcher table further comprises a collision pattern offset item displaying an collision pattern offset value indicating whether one of the hash values of the pre-stored malware pattern data collides with another of the hash values of the pre-stored malware pattern data,

wherein the pattern matching method further comprises, if an offset value exists in the collision pattern offset item, comparing a malware pattern data indicated by the offset value and the one sub data.

18. The malware pattern matching method as claimed in claim 1, wherein the target data is data to be checked to determine whether or not malware exists therein.

13. A malware pattern matching method comprising:

generating a hash matcher table comprising a hash value item displaying a hash value and an item displaying a malware pattern data of a pre-stored malware pattern database or comprising the hash value item displaying the hash value and an item indicating whether hash values of the malware pattern data of the pre-stored pattern database are identical to the hash values displayed on the hash value item;

dividing a target data into a plurality of sub data;

for at least one sub data of the plurality of sub data, generating a hash value of the sub data and comparing the generated hash value of the sub data and the hash matcher table;

generating a sub matcher table which comprises the hash value item displaying the hash value and a malware pattern data item displaying a malware pattern data corresponding to the hash value displayed on the hash value item;

only in response to the hash value of at least one sub data of the plurality of sub data existing in the hash matcher table, performing a light pattern matching operation to match a part of the at least one sub data of the plurality of sub data with a malware pattern data of a pre-stored malware pattern database by using the sub matcher table; and

performing an exact pattern matching operation to match a whole of the one sub data with the malware pattern data only if the part of the one sub data is identical to or included in the malware pattern data.

14. The malware pattern matching method as claimed in claim 13, wherein the sub matcher table further comprises a collision pattern offset item displaying a collision pattern offset value indicating whether one of the hash values of the malware pattern data collides with another of the has values of the malware pattern data.

15. A malware pattern matching system, comprising:

a target data dividing unit which, using a processor, divides a target data into a plurality of sub data;

a storage unit which stores a hash matcher table comprising a hash value item displaying a hash value and an item displaying a pre-stored malware pattern data, or comprising the hash value item displaying the hash value and an item displaying whether a hash value of the pre-stored malware pattern data is identical to the hash value displayed on the hash value item;

a hash value matching unit which matches a hash value of at least one sub data of the plurality of sub data with the hash matcher table;

a sub pattern matching unit which, only in response to the hash value of at least one sub data of the plurality of sub data existing in the hash matcher table, matches the at least one sub data of the plurality of sub data with the corresponding pre-stored malware pattern data;

a full pattern matching unit that, in response to the one sub data not being identical to the malware pattern data matched with the hash value of the one sub data after the matching operation of the sub pattern matching unit, matches the target data with the malware pattern data by referring to a matching result of the sub pattern matching unit; and

a determination unit that, in response to the one sub data being identical to the malware pattern data matched with the hash value of the one sub data after the matching operation of the sub pattern matching unit, does not operate the full pattern matching unit and determines that the malware pattern data is included in the target data,

wherein the sub pattern matching unit comprises;

a light pattern matching unit which is operable to match a part of the one sub data with a sub matcher table; and

an exact pattern matching unit which matches a whole of the one sub data with the pattern data, if the part of the one sub data is identical to those of the sub matcher table,

wherein the sub matcher table comprises the hash value item displaying the hash value and a malware pattern data item displaying a malware pattern data corresponding to the hash value displayed on the hash value item.

16. The malware pattern matching system as claimed in claim 15, further comprising a pattern hash value generator which generates a hash value included in the hash matcher table.

17. A malware pattern matching system, comprising:

a target data dividing unit which, using a processor, divides a target data into a plurality of sub data;

a storage unit which stores a hash matcher table comprising a hash value item displaying a hash value and an item displaying a pre-stored malware pattern data, or comprising the hash value item displaying the hash value and an item displaying whether a hash value of the pre-stored malware pattern data is identical to the hash value displayed on the hash value item;

a hash value matching unit which matches a hash value of at least one sub data of the plurality of sub data with the hash matcher table;

a sub pattern matching unit which, only in response to the hash value of at least one sub data of the plurality of sub data existing in the hash matcher table, matches the at least one sub data of the plurality of sub data with the corresponding pre-stored malware pattern data;

a full pattern matching unit which is operable to match the target data with a whole of the pre-stored malware pattern data; and

a determination unit which determines whether to operate the full pattern matching unit according to a type of the pre-stored malware pattern data,

wherein the type of the pre-stored malware pattern data is a grammatically defined complex malware pattern or a grammatically defined simple malware pattern,

wherein the malware pattern matching system further comprises a determination unit that, in response to the type of the pre-stored malware pattern data being the grammatically defined simple malware pattern, does not operate the full pattern matching unit, and

wherein, in response to the type of the pre-stored malware pattern data being the grammatically defined complex malware pattern, the determination unit controls the full pattern matching unit to be operated after the matching operation of the sub pattern matching unit,

wherein the sub pattern matching unit comprises;

a light pattern matching unit which is operable to match a part of the one sub data with a sub matcher table; and

an exact pattern matching unit which matches a whole of the one sub data with the pattern data, if the part of the one sub data is identical to those of the sub matcher table,

wherein the sub matcher table comprises the hash value item displaying the hash value and a malware pattern data item displaying a malware pattern data corresponding to the hash value displayed on the hash value item.