Author 
Topic: Worm Propagation (Read 8819 times) 

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


Re: Worm Propagation
« Reply #1 on: Feb 3^{rd}, 2003, 1:30am » 
Quote 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
Gender:
Posts: 288


Re: Worm Propagation
« Reply #2 on: Feb 3^{rd}, 2003, 5:58pm » 
Quote 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 rewording of the problem?


IP Logged 



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


Re: Worm Propagation
« Reply #3 on: Feb 4^{th}, 2003, 12:02am » 
Quote Modify

on Feb 3^{rd}, 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 rewording 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.. Bruteforce is usually my first solution, smart solutions follow when it's apparant bruteforce 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
Gender:
Posts: 1291


Re: Worm Propagation
« Reply #4 on: Feb 4^{th}, 2003, 2:27am » 
Quote Modify

Breadthfirst 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

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 offline 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 offline or protected.


IP Logged 



wolfgang
Guest

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 doubleredundancy 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 4^{th}, 2003, 8:53am » 
Quote 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 treecreating 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 topdown weight sorting algorithm won't work as the way we figure out C's importance.

« Last Edit: Feb 4^{th}, 2003, 10:00am by wolfgang » 
IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Worm Propagation
« Reply #9 on: Mar 9^{th}, 2003, 2:13am » 
Quote 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 NPhard because of the tradeoff between depth and bushiness.

« Last Edit: Mar 9^{th}, 2003, 2:14am by william wu » 
IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Worm Propagation
« Reply #10 on: May 12^{th}, 2003, 12:21am » 
Quote Modify

An interesting email 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 12^{th}, 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:
Posts: 13614


Re: Worm Propagation
« Reply #11 on: May 12^{th}, 2003, 1:06am » 
Quote 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 12^{th}, 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:
Posts: 1001


Re: Worm Propagation
« Reply #12 on: Nov 2^{nd}, 2003, 8:57am » 
Quote 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 2^{nd}, 2003, 8:59am by TenaliRaman » 
IP Logged 
Self discovery comes when a man measures himself against an obstacle  Antoine de Saint Exupery



TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001

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:
Posts: 13614


Re: Worm Propagation
« Reply #15 on: Nov 2^{nd}, 2003, 12:19pm » 
Quote 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:
Posts: 1001


Re: Worm Propagation
« Reply #16 on: Nov 2^{nd}, 2003, 12:32pm » 
Quote 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 nlevel 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:
Posts: 1


Re: Worm Propagation
« Reply #17 on: Jul 28^{th}, 2004, 10:28am » 
Quote 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 nondecreasing order of their weights".


IP Logged 



John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767


Re: Worm Propagation
« Reply #18 on: Sep 2^{nd}, 2004, 10:49am » 
Quote 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 NPhard. 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:
Posts: 13614


Re: Worm Propagation
« Reply #19 on: Sep 2^{nd}, 2004, 11:40am » 
Quote Modify

on Sep 2^{nd}, 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
Gender:
Posts: 2814


Re: Worm Propagation
« Reply #20 on: Oct 24^{th}, 2004, 10:03am » 
Quote 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:
Posts: 13614


Re: Worm Propagation
« Reply #21 on: Oct 24^{th}, 2004, 1:47pm » 
Quote Modify

I'm pretty sure it has to be NP. Because as it isn't polynomial, it's nonpolynomial.. There's only two classes. You might be thinking of NPcomplete (a subclass of NPproblem)


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2814


Re: Worm Propagation
« Reply #22 on: Oct 25^{th}, 2004, 6:21am » 
Quote Modify

I was taught that NP was Nondeterministic Polynomial  in other words solvable by a nondeterministic device in polynomial time, unlike P which are solvable by deterministic devices in polynomial time, L which are solvable using logarithmic space, PSPACE, NPSPACE which are solvable using polynomial space by deterministic and nondeterministic devices respectively. The simplest type of NP algorithm is one which nondeterministically generates a possible solution, and then tests it in polynomial time  the basic idea of a nondeterministic 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 nondeterministically generated (in time O(n^{2})) 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(n^{3}), 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:
Posts: 13614


Re: Worm Propagation
« Reply #23 on: Oct 25^{th}, 2004, 8:23am » 
Quote Modify

on Oct 25^{th}, 2004, 6:21am, rmsgrey wrote:I was taught that NP was Nondeterministic 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

« Last Edit: Oct 25^{th}, 2004, 8:47am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Worm Propagation
« Reply #24 on: Oct 25^{th}, 2004, 6:22pm » 
Quote Modify

This problem seems to be the same as the Minimum Broadcast Time problem, which is claimed to be NPComplete (no proof, but a reference) in the first few pages of the following paper . Now that we 'know' that it is NPComplete, it would be interesting to come up with a proof of that.

« Last Edit: Oct 25^{th}, 2004, 6:31pm by Aryabhatta » 
IP Logged 



