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

Welcome, Guest. Please Login or Register.
Sep 25th, 2018, 11:45am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: Eigenray, Grimbal, ThudnBlunder, Icarus, SMQ, towr, 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 8853 times)
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Worm Propagation  
« on: Feb 3rd, 2003, 12:04am »
Quote Quote Modify Modify

WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION WORM PROPAGATION



A hacker is attacking a computer network. Each computer on the network is connected to various other computers. The hacker releases a worm on a source computer. When a worm infects a computer, that computer can propagate a copy of the worm to a connected computer at a rate of once per second. Suppose the hacker knows the layout of the network; i.e., he knows which computers are connected to which. How should the worm proceed to infect the whole network as quickly as possible?  
 
Also, if possible, describe an algorithm for computing the minimum time till total network infection. (Admittedly a computer science background will help here, but it is not absolutely necessary.)
 


Note: Writing credits to Yosen Lin. Inspiration was the Sapphire worm that hit the Net last week.
« Last Edit: Feb 3rd, 2003, 12:05am by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Worm Propagation  
« Reply #1 on: Feb 3rd, 2003, 1:30am »
Quote Quote Modify Modify

...
Order all connected computers as a tree, with the source computer as the root, and make sure the tree is as shallow as possible. Model it so an infected computer 'reinfects' itself, and another computer, making a binary tree, where each level is one second further in time.
And of course al connection in the tree have to be there 'irl' between the computers.
...
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Chronos
Full Member
***





   
WWW Email

Gender: male
Posts: 288
Re: Worm Propagation  
« Reply #2 on: Feb 3rd, 2003, 5:58pm »
Quote Quote Modify Modify

towr:  Where you have and make sure the tree is as shallow as possible., isn't that sort of begging the question?  Does there exist a standard algorithm for doing that, which any computer scientist would know already?  Or did you just intend it as a re-wording of the problem?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Worm Propagation  
« Reply #3 on: Feb 4th, 2003, 12:02am »
Quote Quote Modify Modify

on Feb 3rd, 2003, 5:58pm, Chronos wrote:
Does there exist a standard algorithm for doing that, which any computer scientist would know already?  Or did you just intend it as a re-wording of the problem?
I'm not sure if there is a standard solutuion for doing it in a smart way, since some links just aren't possible and other have to be there..
There is however the way of making every possible tree, and choosing the one that befits the criterium.. Brute-force is usually my first solution, smart solutions follow when it's apparant brute-force would take too long.
 
There has to be a better way, but I'm not really sure yet what it is..
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Worm Propagation  
« Reply #4 on: Feb 4th, 2003, 2:27am »
Quote Quote Modify Modify

Breadth-first search (BFS) can give you the shallowest possible tree. This basically organizes the vertices according to how many steps away they are from the source vertex.
 
Yes, there's a cheaper way to do this than expand all possibilities ... Somewhere you need to describe how to choose the next vertex the worm should infect in order to minimize total infection time. This next vertex should satisfy some metric. Drawing some simple example networks should help.
 
 
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
wolfgang
Guest

Email

Re: Worm Propagation  
« Reply #5 on: Feb 4th, 2003, 8:21am »
Quote Quote Modify Modify Remove Remove

Coming from a very amateur programmer:
Create the tree by starting with the host computer and assigning an ID to every computer it's attached to. Move to those computers and assign an ID to each one they're attached to that doesn't already have an ID. Make it a 2 part number such as 2.3 or 2'3 to identify both parent and child. Continue till all computers have an ID. (towards the end I suppose it would speed things up to start with the computers that haven't been IDed and work backwards).
Now to infect. Instruct each computer to search for the longest ID that starts with its own ID, to reach the most distant computers quickly. Continue until all computers it's been assigned have been infected.
Then move to other computers it wasn't assigned, on the assumption that some computers will be off-line or virus protected and they'll break the chain. If you make each infected computer start by sending a message to its parent to let it know the infection was successful, then the next step would be to either retry those that didn't respond or start infecting their children. Those that reach the end of the tree should start by trying to infect their cousins or uncles. If they ever find one that wasn't infected, then move up to its parent and grandparent...
The total time to total infection will be one second for each step to the longest branch, or a couple seconds longer if there are computers off-line or protected.
IP Logged
wolfgang
Guest

Email

Re: Worm Propagation  
« Reply #6 on: Feb 4th, 2003, 8:32am »
Quote Quote Modify Modify Remove Remove

Obviously, I made one very silly mistake. I really should register so I can undo those mistakes before anybody else sees them, but I keep thinking this will be my very last mistake. Anyway Please ignore the suggestion that a computer infect its grandchildren in the event the computer it tried to infect doesn't respond. Obviously it has no direct connection to its grandchildren or they wouldn't be grandchildren. Maybe the tree should have double-redundancy or it should start sending out lists of the computers it missed so other computers can see whether they can make the bypass,
IP Logged
wolfgang
Newbie
*





   


Posts: 12
Re: Worm Propagation  
« Reply #7 on: Feb 4th, 2003, 8:53am »
Quote Quote Modify Modify

Wrong again, but at least I'm registered, so this will be my last post.
The total time will be the maximum sum of all the address parts for one of the computers at the top of the tree. If a tree is very broad, the worm will spread sideways much more slowly than it spreads up. So the fastest algorithm would be to weigh each branch. Start with the branches that will take the longest, not just the tallest branch. And those branches will have to be sorted in reverse order, sorting the top of the tree first and working your way down.
 
I should have known this would be more complicated than it looked. It's too hard for me so I'll shut up after one more comment. My tree-creating algorithm is no where near optimal. As soon as A infects B, A and B should be equally regarded to decide which will infect C if it's connected to both. And that decision will be based both on equalizing A's and B's workloads (If A connects 100 computers and B connects 10, then you don't want A wasting time infecting computers that B could handle), as well as the importance or weight of C's vertex. But that means the whole tree's shape may change, so a top-down weight sorting algorithm won't work as the way we figure out C's importance.
« Last Edit: Feb 4th, 2003, 10:00am by wolfgang » IP Logged
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Worm Propagation  
« Reply #8 on: Feb 25th, 2003, 12:31am »
Quote Quote Modify Modify

on Feb 4th, 2003, 8:53am, wolfgang wrote:
I should have known this would be more complicated than it looked. [/hide]

 
You're not alone; it turns out our solution was flawed. We're stuck too.
IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Worm Propagation  
« Reply #9 on: Mar 9th, 2003, 2:13am »
Quote Quote Modify Modify

I eventually resorted to googling. We have rediscovered what is typically known as the gossip problem. However, my searches were unsuccessful toward finding a general algorithm for minimal gossip times on a graph. One paper I saw found minimal gossip times only for particular graph structures, such as cliques, trees, and lines; however, I only gave it a cursory survey. Anyways, this problem seems far harder than I expected, and is probably NP-hard because of the tradeoff between depth and bushiness.
« Last Edit: Mar 9th, 2003, 2:14am by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: Worm Propagation  
« Reply #10 on: May 12th, 2003, 12:21am »
Quote Quote Modify Modify

An interesting e-mail I got from an Edward Rustin regarding this problem. Intuitively it seems right to head for the center of mass, but of course that's not a proof.  
 
 

Hi,
 
This isn't exactly a conventional method for solving the network
propagation problem but it does work. Unfortunatly I doubt that an
algorithm or a strictly formal proof can be derived from this. All you
need is a lot of string and a bit of time.
 
Since our hacker knows the layout of the network already then he can do
this. Bascily we create a network diagram using string. Every computer is
represented by a knot in our string. Whenever two parts of the network
come togeather (say at a router or a gateway machine) we tie two pieces of
string togeather. Make sure that the knots that represent hubs or other
'transparent' pieces of hardware are easy to tell apart from the knots
that represent computers. The only tricky part is to ensure that the
spaceing between knots is consistent.
 
Once we have our 'string map' of the network its easy to find the 'center'
of the network. pick up the string at any of its loose ends (the loose
ends being computers on the edge of the network) and let the string hang
naturally. The lowest point is the computer 'furthest' away from the
computer that you are holding in your fingers. If you then hold that
lowest knot and pull the two so that the string becomes tight then we've
just mapped out the shortest path between those two computers. Its a
trivial exercise to count the number of computers between these two points
(and, should we wish, map it onto our network diagram). From this we can
work out which computer is centered between those two points.
 
We now need to perform a sort of 'string recursion' algorithm. Still
holding our bottom knot let go of the top one. This will now show us the
point furthest away from our previous bottom. Take hold of this point and
drop the top one. This, once again, gives us the furthest point away from
that previous point. Repeat untill we oscillate between two points, each
point being the furthest point away from each other. This is the longest
path on our network.
 
An easier way to visualise this is as follows:
 
Pick a point on the network - P1
Let the network hang from that point, lowest point is P2
While (Pn != Pn+2) AND (Pn+1 != Pn+3)
        Hang network from Pn
        Lowpoint is Pn+1
 
        Repeat with Pn+1
 
Pn, Pn+1 is now the longest path.
 
This makes it trivial to determine where the network's 'center' is, being
the computer that is in the middle of these two points. This is therefore
the best computer to infect first. The propagation time is thus the
ceiling of Distance(P1, P2)/2.
 
 
This makes it trivial to determin where the network's 'center' is, being
the computer that is in the middle of these two points. This is therefore
the best computer to infect first. The propagation time is thus the
ceiling of Distance(P1, P2)/2.
 
The best propagation tactic for the worm is for each computer to propagate
first to the computers on this line between the two points and then on
subsequent ticks to propagate to any other uninffected computer that it is
connected to. I think that's so at least.
 
Even if that isn't true, my string computer should go someway to solving
this problem.
 
Edward Rustin

 
 
 
« Last Edit: May 12th, 2003, 12:22am by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Worm Propagation  
« Reply #11 on: May 12th, 2003, 1:06am »
Quote Quote Modify Modify

I'm not sure it will work, because the 'distance' (time) between two computers depends on the previous steps taken by the worm.  
From one computer the worm can only infect one other computer per second, so all computers connected to that computer are at a different distance which you can't determine before you determine the order in which you infect them.
« Last Edit: May 12th, 2003, 1:07am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Worm Propagation  
« Reply #12 on: Nov 2nd, 2003, 8:57am »
Quote Quote Modify Modify

::
Why not simply apply Djikstra Algorithm (from source node to every node) and then construct a tree whose root node is the source node.
::
« Last Edit: Nov 2nd, 2003, 8:59am by TenaliRaman » IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Worm Propagation  
« Reply #13 on: Nov 2nd, 2003, 9:48am »
Quote Quote Modify Modify

Could you elaborate on how that would work?
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Worm Propagation   wormprop.bmp
« Reply #14 on: Nov 2nd, 2003, 11:50am »
Quote Quote Modify Modify

Pretty simple (i think!)
 
Construct the graph of the network. Assign each edge of the graph with weight 1 (we simply are interested in minimising the hopcounts here). Now apply Djikstra algorithm from source node to every other node and build a tree.
 
Consider this example as an illustration,
IP Logged


Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Worm Propagation  
« Reply #15 on: Nov 2nd, 2003, 12:19pm »
Quote Quote Modify Modify

Ah..
So basicly it won't work here, imo.. The distance between nodes depends on the order childnodes are chosen.. (because the worm can only be send to one node every second)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
TenaliRaman
Uberpuzzler
*****



I am no special. I am only passionately curious.

   


Gender: male
Posts: 1001
Re: Worm Propagation  
« Reply #16 on: Nov 2nd, 2003, 12:32pm »
Quote Quote Modify Modify

In the simple graph i proposed above, the time taken for worm propagation is not much significant.
 
However if my idea is to produce a n-level tree with m childnodes for each node on an average then it can achieve significant time minimisation.
IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
mindcrime
Newbie
*





   


Gender: male
Posts: 1
Re: Worm Propagation  
« Reply #17 on: Jul 28th, 2004, 10:28am »
Quote Quote Modify Modify

Well guys, I am new to this field but let me exercise my feeble mind over this topic.
 
The hacker could create a minimal spanning tree from the network and start the attack from the root. The minimal spanning tree could be the traditional one as we all know, but it should also be "minimal" in another sense wherever possible. The other sense is that as far as possible , the weights of the edges should be nondecreasing. Clearly, by choosing the appropriate vertex which satisfies this property in any spanning tree as the root, this is possible. So the solution can be very crisply stated as follows...
 
"Find the minimal spanning tree and start from the vertex from which every edge is ordered to the leaves in non-decreasing order of their weights".  Roll Eyes
IP Logged
John_Gaughan
Uberpuzzler
*****



Behold, the power of cheese!

5187759 5187759   john23874   SnowmanJTG
WWW Email

Gender: male
Posts: 767
Re: Worm Propagation  
« Reply #18 on: Sep 2nd, 2004, 10:49am »
Quote Quote Modify Modify

Minimal spanning tree may be a good start but will not, by itself, yield a solution. Keep in mind that time is a factor, not just location on the network. If a node has ten children, it will infect them, one a second, until it is done. This introduces complexity to the algorithm that, as William said, probably makes it NP-hard. That and the fact that we do not know the network layout ahead of time, so we have to generalize it enough to work in all cases.
 
All of my CS education pertaining to trees makes assumptions that go against this program. I believe the answer lies not in traditional tree/graph theory but in some new angle, a new way of approaching the problem that flies in the face of conventional thought.
 
One parameter not described in the original problem is whether a copy of the worm has knowledge about which nodes are already infected. Does a worm infect its children until done, then quit? Does it know about nodes not connected to itself? E.g. if the root infects a node, which infects another node, does that node know about its "cousin" nodes? Does the algorithm take that into account? Is infection random? How much a priori knowledge do we have?
IP Logged

x = (0x2B | ~0x2B)
x == the_question
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Worm Propagation  
« Reply #19 on: Sep 2nd, 2004, 11:40am »
Quote Quote Modify Modify

on Sep 2nd, 2004, 10:49am, John_Gaughan wrote:
That and the fact that we do not know the network layout ahead of time, so we have to generalize it enough to work in all cases.
The puzzle states we do know the layout of the network (not necessarily a tree) ahead of time.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Worm Propagation  
« Reply #20 on: Oct 24th, 2004, 10:03am »
Quote Quote Modify Modify

Looking back over some of the old problems...
 
I'm curious as to whether this problem can even be shown to be in NP - I'm a little rusty on the theory, but don't NP problems have to be able to evaluate prospective solutions in polynomial time? How would you go about recognising a genuine minimum time infection route? Certainly a naive brute force method requires comparison of all possible attacks to determine the optimum one.
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Worm Propagation  
« Reply #21 on: Oct 24th, 2004, 1:47pm »
Quote Quote Modify Modify

I'm pretty sure it has to be NP. Because as it isn't polynomial, it's non-polynomial.. There's only two classes.
You might be thinking of NP-complete (a subclass of NP-problem)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2818
Re: Worm Propagation  
« Reply #22 on: Oct 25th, 2004, 6:21am »
Quote Quote Modify Modify

I was taught that NP was Non-deterministic Polynomial - in other words solvable by a non-deterministic device in polynomial time, unlike P which are solvable by deterministic devices in polynomial time, L which are solvable using logarithmic space, P-SPACE, NP-SPACE which are solvable using polynomial space by deterministic and non-deterministic devices respectively.
 
The simplest type of NP algorithm is one which non-deterministically generates a possible solution, and then tests it in polynomial time - the basic idea of a non-deterministic machine is that, whenever it hits a "choose" instruction, it makes all possible choices simultaneously, and then evaluates the outcome of each choice in parallel. The machine fails if all choices fail, and succeeds if any parallel version succeeds.
 
I guess you could create a machine that, for a given infection time, checks the non-deterministically generated (in time O(n2)) infection scheme in time O(n) to see if it takes the appropriate amount of time to infect the network. Having that machine, you could then create another machine that called it repeatedly with times 1 to n until a success gets returned. Assuming I haven't made any egregious errors, the total running time would be O(n3), putting the problem in NP.
 
I guess I've managed to answer my own question then...
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13640
Re: Worm Propagation  
« Reply #23 on: Oct 25th, 2004, 8:23am »
Quote Quote Modify Modify

on Oct 25th, 2004, 6:21am, rmsgrey wrote:
I was taught that NP was Non-deterministic Polynomial
hmm.. you're right
 I must be more affected by my cold than I reallize.. At least I got the 'non' and 'polynomial' parts right Wink
« Last Edit: Oct 25th, 2004, 8:47am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Worm Propagation  
« Reply #24 on: Oct 25th, 2004, 6:22pm »
Quote Quote Modify Modify

This problem seems to be the same as the Minimum Broadcast Time problem, which is claimed to be NP-Complete (no proof, but a reference) in the first few pages of the following paper .
 
Now that we 'know' that it is NP-Complete, it would be interesting to come up with a proof of that.
 
« Last Edit: Oct 25th, 2004, 6:31pm by Aryabhatta » 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