Author 
Topic: Worm Propagation (Read 9295 times) 

Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Worm Propagation
« Reply #25 on: Oct 26^{th}, 2004, 7:56pm » 
Quote Modify

Supposedly, 3 dimensional matching is reducible in a straight forward way to the minimum broadcast problem. 3 Dimensional Matching: Given a set S of 3n elements and a family F of subsets of S, such that each element of F is of cardinality 3, does there exist a subset H of F of cardinality n such that the union of elements of H is S. (basically given some m > n, triples from S, can you find n triples which cover S. Since S is of size 3n, those n triples must be mutually disjoint, it is also known as the Exact Three Cover.) 3 Dimensional Matching is known to be NPComplete.


IP Logged 



Sjoerd Job Postmus
Full Member
Posts: 228


Re: Worm Propagation
« Reply #26 on: Mar 10^{th}, 2005, 2:56pm » 
Quote Modify

I'm an infected computer, I will take these steps: 1. Enumerate the computers I can infect. 2. Choose uninfected computer that only I can infect, with the largest amount of links. 3. If that fails  all computers are somehow attached to other infects  choose one with as many links as possible, with the least amount of infected links, with the largest total of infect busyness. 4. If that fails, I can no longer infect anything, so I'm done !


IP Logged 



DewiMorgan
Newbie
Posts: 29


Re: Worm Propagation
« Reply #27 on: Jun 2^{nd}, 2006, 7:38pm » 
Quote Modify

Although it's NPhard, the fun comes from constructing an effective, nearoptimal algorithm for a blind virus to spread most economically. Longestpath and centerofmass and mostgrandchildren solutions all provide good general answers, but fail in some situations. Consider a situation where you are attacking "target", which lies between a hub, connected in parallel to X machines, none of which are interconnected, and to a chain of Y machines. X=HubtargetABCDE...Y Clearly, if X>Y, then it's better to infect the hub machine first, so it can start infecting its children as soon as possible. This is despite the fact that it's not the "center" of the network, and it's not the longest path. If X<Y, then it's best to infect the chain first, even though the first link only has a single outside connection, because that link leads to the majority of the network, which we want to infect. It rapidly becomes more complicated when you start linking the leaves together, of course. Any solution should be recursive (that is, each infected child should be able to run it too). And unless the infected machines broadcast which others they infect, and the machines can deliberate amongst eachother about who should infect whom, I's assume all machines are working blind. As much as possible, though, each machine needs to mark alreadyinfected machines in its internal map, remove the links between them, remove any subsequently isolated machines, and repeat the process each second (after it had connected to all its own children, it would consider itself an isolated node, and remove itself from the network, stopping its own action). But guessing which others (other than its parent and the ones it infected itself) were infected, could be tricky. This is because I think randomness may need to come into play. The chance of it selecting a target node could be divided by the number of available nodes, and multiplied by the suspected number of noninfected links from that node, for instance. Also want to include a factor to compensate for the probability of another known infected node selecting that item. Possibly subtract 1/(number of nodes available to infected node) from the probability of selecting that item, for each infected node that shares it, capping at just over zero, but not marking it as actually infected unless the probability was 1/1. Then scale all probabilities so the total probability of selecting SOME node is 1. This algorithm would mean that nodes right in the center of a mass of infected machines might not get infected until one of the infected machines had exhausted all other probabilities, but that's probably not a bad thing. I think the above is pretty close to optimal, though it would be suboptimal for the first node in the Y>X state above. It would also fail sometimes for: xxinfectedy ...since it would sometimes choose y first. Probably the choices should only be random where there are conflicts with other infected hosts, and should be deterministic for unshared nodes. which brings us back to how to best choose deterministically. THe weighting should include a measure of the netsork distance from other infected notes (other than passing through the current host), too. And probably a measure of the size of the tree behind it divided by the number of knowninfected hosts on that tree.


IP Logged 



Shiladie
Newbie
Posts: 2


Re: Worm Propagation
« Reply #28 on: Nov 26^{th}, 2006, 6:10pm » 
Quote Modify

Very simple, most probably flawed logic while looking at this after confusing ever myself with bad math here is an example for 7 seconds with infinit computers available infecting the maximum computers 0: x 1: x, 1x1 2: x, 2x1,1x2 3: x, 3x1,3x2,1x3 4: x, 4x1 6x2,4x3,1x4 5: x, 5x1,10x2,10x3,5x4,1x5 6: x, 6x1,15x2,20x3,15x4,6x5,1x6 7: x, 7x1,21x2,35x3,35x4,21x5,7x6,1x7 after 7 seconds you infect 127 computers and now its so obvious, the equation for what i am now sure is probably the completely wrong problem is: s = seconds assumeing you start at 0 x = number of computers infected 2^s1 = x this is assumeing perfect network layout and that the virus is smart enough to not infect the same computer more then once. which bwe have to assume to get any sort of real answer for this riddle without more information about how the network is layed out the rest is theorycraft about 'weighting the larger branches of the network more heavily' and such and now im ready for the flame about how i'm wrong and missed some big note, which is probably true because this just is too simply to have so many people thinking...

« Last Edit: Nov 26^{th}, 2006, 6:12pm by Shiladie » 
IP Logged 



balakrishnan
Junior Member
Gender:
Posts: 92


Re: Worm Propagation
« Reply #29 on: Jan 10^{th}, 2007, 8:04pm » 
Quote Modify

Is this solved yet?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Worm Propagation
« Reply #30 on: Jan 11^{th}, 2007, 1:51am » 
Quote Modify

on Jan 10^{th}, 2007, 8:04pm, balakrishnan wrote:Depends on what you consider solved. To do it perfectly is NP hard, and the brute force approach to do that was posted early on. However a near optimal solution may be better in practice (especially if you don't know the entire layout beforehand). And there's nearly always room for improvement at that end.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



CowsRUs
Full Member
Why is it that cats are better then cows? Why not?
Gender:
Posts: 175


Re: Worm Propagation
« Reply #31 on: Feb 12^{th}, 2007, 9:19am » 
Quote Modify

I would infect other computers then infect more then infect more than start spamming emails and hope some idiot clicks on the spam with the virus


IP Logged 
"It is very good to have a brother who has a cow. It is also good to have a brother who has two cows. In fact, a brother with a cow is great, except when he has exactly 135 cows and is one of thecow himself."Unknown



bosssssss3
Newbie
Posts: 4


Re: Worm Propagation
« Reply #32 on: Mar 21^{st}, 2007, 10:02am » 
Quote Modify

can sumone please add more smileys plz


IP Logged 



Hippo
Uberpuzzler
Gender:
Posts: 919


Re: Worm Propagation
« Reply #33 on: Apr 30^{th}, 2007, 4:26am » 
Quote Modify

Sorry I had loooked for on all pages missing the title one ... this belongs here... I will show that minimal gosip problem (worm propagation) is NP hard. I will show that deciding whether mingosip=k providing you know mingosip in k,k+1 is NP complete. I will show a reduction from the SAT CNF problem. You have m clauses using n different variables alltogether. Let k be chosen later. I will construct graph with mingosip in k,k+1 having mingosip = k iff given formula is satisfable: Construction will be started from starting vertex 0 for the gosip problem. Let vertex 0 and newly created vertices x_{i},neg x_{i} creates triangle. Let vertex i is connected to both x_{i} and neg x_{i}. And let us create path of length ki2 edges starting in vertex i. Last vertex of the path being blotted before time k+1 forces that vertex i is blotted at time i+1. In that case either x_{i} or neg x_{i} is blotted in time i. Furthermore for ith literal vertex (x_{i} or neg x_{i} vertex) we create hypercube sceletton connected to it such that under each literal there is at least m leaves in the last level. This is the only bound for k (and it is lower bound). And the last level is blottable in time k2 iff the literal vertex is selected and in time k iff it is not selected and the last vertex of path under vertex i is reachable in time k. For lth clause create and connect vertices c_{l},d_{l} and for each literal y connect c_{l} to lth leave of the y tree. Vertex c_{l} must be blotable in time k1 to be able to blot d_{l} before time k. ... WQD


IP Logged 



