EFFICIENT DETECTION OF RELAY NODE

• US 20090154375A1
• Filed: 11/10/2008
• Published: 06/18/2009
• Est. Priority Date: 11/09/2007
• Status: Active Grant

• Current Assignee: Polytechnic Institute Of New York University (New York University)
• Original Assignee: Polytechnic Institute Of New York University (New York University)
• Inventors: Memon, Nasir, Coskun, Baris
• Granted Patent: US 7,986,636 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/12 Network monitoring probes

Abstract

Whether or not a node is a relay node may be determined by, for each of a plurality of active flows, assigning a random number to the flow, wherein each of the random numbers is drawn from a distribution. Then, for each of a plurality of time slots, any incoming flows to the node and any outgoing flows from the node may be determined, random numbers assigned to any active flow of the incoming flows may be summed to generate a first sum, random numbers assigned to any active outgoing flows may be summed to generating a second sum, and the first sum may be multiplied with the second sum to generate a product associated with the time slot. The products over the plurality of time slots may then be summed to obtain a summed product. This may be repeated, reassigning random values to each of the plurality of flows, thereby obtaining a plurality of summed products. A variance of the plurality of summed products may be determined and compared with a threshold to obtain a comparison result. Whether or not the node is a relay node may then be determined using the comparison result. Execution of a relay node protection policy may be controlled using the determination of whether or not the node is a relay node.

Claims

1. A computer implemented method for determining whether or not a node in a network is a relay node, the computer-implemented method comprising:

a) for each of a plurality of flows, assigning a random number to an active flow, wherein each of the random numbers is drawn from a known distribution;

b) for each of a plurality of time slots,

1) determining any incoming flows to the node,

2) determining any outgoing flows from the node,

3) summing random numbers assigned to any of the incoming flows to generate a first sum,

5) summing random numbers assigned to any of the outgoing flows to generating a second sum,

6) multiplying the first sum with the second sum to generate a product associated with the time slot,

c) summing the products over the plurality of time slots to obtain a summed product;

d) repeating (a)-(c) reassigning random values to each of the plurality of flows, thereby obtaining a plurality of summed products;

e) determining a variance of the plurality of summed products;

f) comparing the determined variance with a threshold to obtain a comparison result;

g) determining whether or not the node is a relay node using the comparison result; and

h) controlling, using the computer system, the execution of a relay node protection policy using the determination of whether or not the node is a relay node.

2. The computer implemented method according to claim 1, further comprising:

removing a random number associated with a particular flow from the act of summing if a random number has already been accumulated for another flow, the another flow having an exact reverse direction of the particular flow.

3. The computer implemented method according to claim 1, wherein the incoming flow associated with a particular time slot is measured at a time interval differently aligned from the particular time slot of the corresponding outgoing flow to achieve a higher true positive rate of evaluating a node as a relay node.

4. The computer implemented method according to claim 1, wherein the known distribution has a zero mean.

5. The computer implemented method according to claim 1, wherein the repeating (a)-(c) reassigning random values to each of the plurality of flows, thereby obtaining a plurality of summed products is performed at least 100 times.

6. Apparatus for facilitating host malware detection, the apparatus comprising:

one or more processors;

at least one input device; and

one or more storage devices storing processor-executable instructions which,

when executed by one or more processors, perform a method of;

a) for each of a plurality of flows, assigning a random number to the flow, wherein each of the random numbers is drawn from a known distribution;

b) for each of a plurality of time slots,

1) determining any incoming flows to the node,

2) determining any outgoing flows from the node,

3) summing random numbers assigned to any active flow of the incoming flows to generate a first sum,

5) summing random numbers assigned to any active flow of the outgoing flows to generating a second sum,

6) multiplying the first sum with the second sum to generate a product associated with the time slot,

c) summing the products over the plurality of time slots to obtain a summed product;

d) repeating (a)-(c) reassigning random values to each of the plurality of flows, thereby obtaining a plurality of summed products;

e) determining a variance of the plurality of summed products;

f) comparing the determined variance with a threshold to obtain a comparison result;

g) determining whether or not the node is a relay node using the comparison result; and

h) controlling, using the computer system, the execution of a relay node protection policy using the determination of whether or not the node is a relay node.