Correlating packets
View Patent ↗A system/method searches a traffic stream for a sequence of “matching” packets that exhibit a high degree of correlation or similarity to a sequence of “reference” packets. The correlation between matching and reference packets is based on a degree of correspondence between individual packets, as well as the sequence-order of the corresponding packets. A variation of the Needleman-Wunsch algorithm is preferably used to select corresponding packets in the traffic stream that provide a sequence-order that best matches the sequence-order of the reference packets, based on a measure of the correspondence for each match, and a penalty associated with each non-match. The algorithm is further modified to reduce the required search-space for finding corresponding packets in the traffic stream.
1. A method comprising:
identifying, by a traffic analysis system, a plurality of predefined reference transmissions,
determining, by the traffic analysis system, correspondence factors between traffic transmissions of a plurality of traffic transmissions and reference transmissions of the plurality of reference transmissions to provide a plurality of correspondence factors for each of the reference transmissions, each correspondence factor being a measure of correspondence between a traffic transmission and a reference transmission, and
selecting, by the traffic analysis system, a set of matching transmissions to the reference transmissions from the plurality of traffic transmissions, based on the plurality of correspondence factors, and based on a sequence order of the plurality of reference transmissions.
2. The method of claim 1 , wherein selecting the set of matching transmissions is further based on a first penalty factor associated with each failure to match one of the reference transmissions to one of the traffic transmissions.
3. The method of claim 2 , wherein selecting the set of matching transmissions is further based on a second penalty factor associated with each failure to match one of the traffic transmissions to one of the reference transmissions.
4. The method of claim 1 , wherein selecting the set of matching transmissions is further based on a penalty factor associated with each failure to match one of the traffic transmissions to one of the reference transmissions.
5. The method of claim 1 , wherein selecting the set of matching transmissions includes applying a Needleman-Wunsch algorithm to the pluralities of reference and traffic transmissions.
6. The method of claim 1 , wherein selecting the set of matching transmissions includes determining an assignment score that is based on:
the correspondence factor of each matching transmission and corresponding reference transmission, and
a first penalty factor that is associated with each reference transmission that is not matched to a corresponding traffic transmission.
7. The method of claim 6 , wherein determining the assignment score is further based on a second penalty factor that is associated with each traffic transmission that is not matched to a corresponding reference transmission.
8. The method of claim 7 , wherein the first penalty factor is substantially equal to the second penalty factor.
9. The method of claim 6 , wherein selecting the set of matching transmissions includes:
determining a plurality of assignment scores for a plurality of possible assignments of matching transmissions and reference transmissions,
identifying a maximum assignment score within the plurality of assignment scores, and
selecting the set of matching transmissions corresponding to an assignment of the plurality of possible assignments having the maximum assignment score.
10. The method of claim 9 , further including determining the plurality of possible assignments.
11. The method of claim 10 , wherein determining the plurality of possible assignments is based on a maximum penalty score within the assignment score.
12. The method of claim 11 , wherein the maximum penalty score includes an accumulation of the first penalty factor for each reference transmission that is not matched to one of the traffic transmissions.
13. The method of claim 12 , further including maintaining a running accumulation of the first penalty factor for each reference transmission that is not matched to one of the traffic transmissions while determining each possible assignment of the plurality of possible assignments, and wherein determining each possible assignment is based on the running accumulation.
14. The method of claim 6 , wherein the assignment score is based on a sum of:
the correspondence factor for each production transmission having a matching transmission, and
the first penalty factor for each production transmissions having no matching traffic transmission.
15. The method of claim 14 , wherein the sum further includes a second penalty factor for each traffic transmission having no matching reference transmission.
16. The method of claim 1 , wherein the reference transmissions and traffic transmissions conform to a packet-based protocol, such that each reference transmission corresponds to a reference packet and each traffic transmission corresponds to a traffic packet.
17. The method of claim 16 , wherein selecting the set of matching transmissions includes determining an assignment score that is based on:
the correspondence factor of each matching packet and corresponding reference packet, and
a first penalty factor that is associated with each reference packet that is not matched to a corresponding traffic packet.
18. The method of claim 17 , wherein selecting the set of matching transmissions includes:
determining a plurality of assignment scores for a plurality of possible assignments of corresponding traffic packets and reference packets,
identifying a maximum assignment score within the plurality of assignment scores, and
selecting the set of matching packets corresponding to an assignment of the plurality of possible assignments having the maximum assignment score.
19. The method of claim 18 , further including determining the plurality of possible assignments.
20. The method of claim 19 , wherein determining the plurality of possible assignments is based on a maximum penalty score within the assignment score.
21. The method of claim 20 , further including maintaining a running accumulation of penalties for each non-match of a reference packet and a traffic packet while determining each possible assignment, and wherein determining the possible assignment is based on the running accumulation.
22. The method of claim 20 , wherein the maximum penalty score includes an accumulation of the first penalty factor for each reference packet that is not matched to one of the traffic packets.
23. The method of claim 22 , further including maintaining a running accumulation of the first penalty factor for each reference packet that is not matched to one of the traffic packets, and determining the plurality of possible assignments is based on the running accumulation.
24. The method of claim 18 , wherein the assignment score is based on a sum of:
the correspondence factor for each production packet having a corresponding matching traffic packet, and
the first penalty factor for each production packet having no matching traffic packet.
25. The method of claim 24 , wherein the sum includes a second penalty factor for each traffic packet having no matching reference packet.
26. The method of claim 1 , wherein the correspondence factor is based on one or more of:
a direction of the traffic transmission,
a size of the traffic transmission, and
content of the traffic transmission.
27. The method of claim 1 , wherein determining the correspondence factor includes identifying strings within the traffic transmission that correspond to strings within the reference transmission.
28. The method of claim 27 , wherein determining the correspondence factor is based on a maximum continuous length of the strings within the traffic transmission that correspond to strings within the reference transmission.
29. The method of claim 27 , wherein identifying the strings within the traffic transmission that correspond to strings within the reference transmission includes application of a Needleman-Wunsch algorithm.
30. The method of claim 1 , wherein determining the correspondence factor includes identifying occurrences of key words or phrases within some or all of the traffic transmissions.
31. A system comprising hardware and software components that includes:
a correspondence determinator that is configured to determine correspondence factors between a plurality of reference transmissions and a plurality of traffic transmissions to provide a plurality of correspondence factors for each of the plurality of reference transmissions, each correspondence factor being a measure of correspondence between a traffic transmission and a reference transmission,
an assignment generator that is configured to generate a plurality of possible assignments of matching traffic transmissions to the plurality of reference transmissions from the plurality of reference transmissions, and
an assignment selector that is configured to select a preferred assignment from the plurality of possible assignments, based on a score associated with each assignment of the plurality of possible assignments that is based on the plurality of correspondence factors.
32. The system of claim 31 , wherein the correspondence determinator is configured to determine the correspondence factors based on one or more of:
a direction of each traffic transmission relative to a direction of each reference transmission,
a size of each traffic transmission relative to a size of each reference transmission, and
content of each traffic transmission relative to content of each reference transmission.
33. The system of claim 31 , wherein the correspondence determinator is configured to determine one or more of the correspondence factors based on occurrences of key words or phrases in one or more of the traffic transmissions.
34. The system of claim 31 , wherein the correspondence determinator is configured to determine one or more of the correspondence factors based on occurrences of strings within the traffic transmissions that correspond to strings within the reference transmissions.
35. The system of claim 34 , wherein the correspondence factors are based on a maximum length of the strings within the traffic transmissions that correspond to strings within the reference transmissions.
36. The system of claim 34 , wherein the correspondence determinator is configured to apply a Needleman-Wunsch algorithm to determine the one or more of the correspondence factors.
37. The system of claim 31 , wherein the assignment generator is configured to generate the possible assignments such that each assignment substantially maintains a sequence order associated with the reference transmissions.
38. The system of claim 37 , wherein the assignment generator is configured to determine the score of each assignment.
39. The system of claim 38 , wherein the score is also dependent upon a penalty factor that is associated with each traffic transmission that is not matched to one of the reference transmissions.
40. The system of claim 38 , wherein the score is also dependent upon a first penalty factor that is associated with each reference transmission that is not matched to one of the traffic transmissions.
41. The system of claim 40 , wherein the score is also dependent upon a second penalty factor that is associated with each traffic transmission that is not matched to one of the reference transmissions.
42. The system of claim 41 , wherein the assignment generator applies a Needleman-Wunsch algorithm to generate and score each possible assignment.
43. The system of claim 38 , wherein the assignment generator is configured to generate each possible assignment based on a maximum allowable accumulation of penalties associated with non-matched pairs of reference and traffic transmissions.
44. The system of claim 43 , wherein the assignment generator is configured to:
maintain a running accumulation of the penalties while each possible assignment is being generated, and
avoiding the generation of one or more other possible assignments based on the running accumulation relative to the maximum allowable accumulation.
45. The system of claim 44 , wherein the running accumulation is based on an accumulation of penalties associated with reference transmissions that are not matched to one of the traffic transmissions.
46. The system of claim 43 , wherein the maximum allowable accumulation is based on an accumulation of penalties associated with reference transmissions that are not matched to one of the traffic transmissions.
47. The system of claim 31 , wherein the reference transmissions and traffic transmissions conform to a packet-based protocol.
48. A system comprising hardware and software components that includes:
a correspondence determinator that is configured to determine correspondence factors between a plurality of reference packets and a plurality of traffic packets to provide a plurality of correspondence factors for each of the plurality of reference packets, each correspondence factor being a measure of correspondence between a traffic transmission and a reference transmission,
an assignment generator that is configured to generate a plurality of assignments that each provide a mapping between the plurality of reference packets and the plurality of traffic packets, based on the plurality of correspondence factors and based on a sequence order of the plurality of reference packets, and
an assignment selector that is configured to select a preferred assignment from the plurality of assignments, based on a score that is associated with each assignment of the plurality of assignments.
49. The system of claim 48 , wherein each correspondence factor is based on one or more of:
a direction of each traffic packet relative to a direction of a corresponding reference packet,
a size of each traffic packet relative to a size of a corresponding reference packet, and
content of each traffic packet relative to content of a corresponding reference packet.
50. The system of claim 49 , wherein each assignment includes one or more matching pairs of reference and traffic packets, and the assignment generator is configured to determine the score of each assignment, based on the correspondence factor of each matching pair of reference and traffic packets, and based on a first penalty factor associated with each reference packet that is not paired to a matching traffic packet.
51. The system of claim 50 , wherein the score of each assignment is further based on a second penalty factor associated with each traffic packet that is not paired to a matching reference packet.
52. The system of claim 51 , wherein the assignment generator is configured to apply a Needleman-Wunsch algorithm to generate and score the plurality of assignments.