Author |
Topic: Worm Propagation (Read 9416 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
 |
Re: Worm Propagation
« Reply #1 on: Feb 3rd, 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 3rd, 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 re-wording of the problem?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Worm Propagation
« Reply #3 on: Feb 4th, 2003, 12:02am » |
Quote 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
Gender:
Posts: 1291
|
|
Re: Worm Propagation
« Reply #4 on: Feb 4th, 2003, 2:27am » |
Quote 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
|
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
|
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 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
Gender:
Posts: 1291
|
|
Re: Worm Propagation
« Reply #9 on: Mar 9th, 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 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
Gender:
Posts: 1291
|
|
Re: Worm Propagation
« Reply #10 on: May 12th, 2003, 12:21am » |
Quote 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:
Posts: 13730
|
|
Re: Worm Propagation
« Reply #11 on: May 12th, 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 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:
Posts: 1001
|
|
Re: Worm Propagation
« Reply #12 on: Nov 2nd, 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 2nd, 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: 13730
|
|
Re: Worm Propagation
« Reply #15 on: Nov 2nd, 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 2nd, 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 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:
Posts: 1
|
 |
Re: Worm Propagation
« Reply #17 on: Jul 28th, 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 non-decreasing order of their weights". 
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
Gender:
Posts: 767
|
|
Re: Worm Propagation
« Reply #18 on: Sep 2nd, 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 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:
Posts: 13730
|
|
Re: Worm Propagation
« Reply #19 on: Sep 2nd, 2004, 11:40am » |
Quote 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
 
Gender:
Posts: 2872
|
|
Re: Worm Propagation
« Reply #20 on: Oct 24th, 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: 13730
|
|
Re: Worm Propagation
« Reply #21 on: Oct 24th, 2004, 1:47pm » |
Quote 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
Gender:
Posts: 2872
|
|
Re: Worm Propagation
« Reply #22 on: Oct 25th, 2004, 6:21am » |
Quote 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:
Posts: 13730
|
|
Re: Worm Propagation
« Reply #23 on: Oct 25th, 2004, 8:23am » |
Quote 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 
|
| « Last Edit: Oct 25th, 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 25th, 2004, 6:22pm » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove