wu :: forums
« wu :: forums - Worm Propagation »

Welcome, Guest. Please Login or Register.
Mar 29th, 2024, 7:26am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, Icarus, towr, ThudnBlunder, SMQ, Grimbal, william wu)
   Worm Propagation
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Worm Propagation  (Read 9412 times)
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Worm Propagation  
« Reply #25 on: Oct 26th, 2004, 7:56pm »
Quote Quote Modify 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 NP-Complete.
IP Logged
Sjoerd Job Postmus
Full Member
***





   


Posts: 228
Re: Worm Propagation  
« Reply #26 on: Mar 10th, 2005, 2:56pm »
Quote Quote Modify 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 Sad!
IP Logged
DewiMorgan
Guest

Email

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

Although it's NP-hard, the fun comes from constructing an effective, nearoptimal algorithm for a blind virus to spread most economically.
 
Longest-path and center-of-mass and most-grandchildren 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=Hub-target-A-B-C-D-E-...-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 already-infected 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 non-infected 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:
 
x-x-infected-y
 
...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 known-infected hosts on that tree.
IP Logged
Shiladie
Newbie
*





   


Posts: 2
Re: Worm Propagation  
« Reply #28 on: Nov 26th, 2006, 6:10pm »
Quote Quote Modify 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^s-1 = 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 26th, 2006, 6:12pm by Shiladie » IP Logged
balakrishnan
Junior Member
**





   


Gender: male
Posts: 92
Re: Worm Propagation  
« Reply #29 on: Jan 10th, 2007, 8:04pm »
Quote Quote Modify Modify

Is this solved yet?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Worm Propagation  
« Reply #30 on: Jan 11th, 2007, 1:51am »
Quote Quote Modify Modify

on Jan 10th, 2007, 8:04pm, balakrishnan wrote:
Is this solved yet?
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: male
Posts: 175
Re: Worm Propagation  
« Reply #31 on: Feb 12th, 2007, 9:19am »
Quote Quote Modify 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 21st, 2007, 10:02am »
Quote Quote Modify Modify

can sumone please add more smileys plz  Undecided
IP Logged
Hippo
Uberpuzzler
*****





   


Gender: male
Posts: 919
Re: Worm Propagation  
« Reply #33 on: Apr 30th, 2007, 4:26am »
Quote Quote Modify 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 xi,neg xi creates triangle.  
 
Let vertex i is connected to both xi and neg xi.  
 
And let us create path of length k-i-2 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 xi or neg xi is blotted in time i.
 
Furthermore for i-th literal vertex (xi or neg xi 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 k-2 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 l-th clause create and connect vertices cl,dl and for each literal y connect cl to l-th leave of the y tree.
 
Vertex cl must be blotable in time k-1 to  
be able to blot dl before time k.  
 
...
WQD
IP Logged
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board