Lab 1620 - Ackermann Function

Description

In a cracker's world, the next-best thing to breaking in to your computer is locking you out of it. Attacks that prevent someone from using their machine are called denial-of-service attacks.

There are many ways to render a computer useless. Attacks may involve consuming all available CPU cycles, allocating all memory to starve out other programs, including the operating system or causing a system to hang while it waits for something impossible to happen. The result is the same: the user being attacked is effectively locked out of the machine.

One way to make a computer slow down is to give it a task that easily consumes all available processing cycles. Movie goers may remember a 1983 movie, War Games, that tells the story of David, a high-school hacker, who manages to tap into WOPR, the Pentagon's top defense computer. Thinking he's discovered a great new video game, "Global Thermonuclear War," David innocently brings the US and the Soviet Union to the brink of total war. Convinced that the Soviets have launched an assault, the computer prepares for a retaliatory strike with real nuclear missles. David was able to engage WOPR in a game that cleverly used all the computer's machine processing, effectively stalling the retaliation before the missles were launched.

The trick is to have a process that consumes all processing power of the machine it is on. The basic sequence might be something like this:

  1. Create a program that starts a thread with its priority set to maximum so it will take processing cycles away from other tasks, even system crital ones.
  2. Redefine the stop() method such that the thread cannot be stopped.
  3. Have the program sleep for a while before starting to trash the system. It will be hard to figure out who is draining all resources if it starts apparently at a random time.
  4. When it starts, if there is a user-visible part of the program, have it appear to be harmless, such as displaying a picture.
  5. The real work of the program is to begin calculating some CPU-intensive activity that eats cycles. One particularly worthy function for major processing overload is the Ackermann function, which is the subject of this project.
Description of the Function

The Ackermann function looks very simple, yet it (and more importantly, is inverse) plays a major role in computer science and computational complexity theory. It is a function that grows faster than probably any one you've seen before. It's a strange numerical function on natural numbers, with this definition:

m = 0 A(0, n) = n+1
m > 0, n = 0 A(m, 0) = A(m-1, 1)
m > 0, n > 0 A(m, n) = A(m-1, A(m, n-1))

Looks harmless, doesn't it? If you calculate the first three lines (where 'line' means that m is fixed, and n varies), you get the following table:

  n
m 0 1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11 12
2 3 5 7 9 11 13 15 17 19 21 23
3 5 13 29 61 125 253 509 1021 2045 4093 8189

This is the table that you find in many books on programming or recursions. In fact, this so-called function hardly counts as one, since it doesn't do any real calculations (except for one '+'). It is more like an array, whose values are used to access other parts of the array. This is easy to see when you write the function slightly differently, with square brackets instead of parentheses:

m = 0 A[0, n] = n+1
m > 0, n = 0 A[m, 0] = A[m-1, 1]
m > 0, n > 0 A[m, n] = A[m-1, A[m, n-1]]

If you think of the first function as the initialization for line 0 of the array, you may notice that this function doesn't contain any calculations of the actual values, only of their indices.

Assignment

Use a recursive solution to calculate A(m,n) and to generate the table of values for rows representing m from 0 to 3 and columns representing n from 0 to 10 as shown above. Be careful: the function grows very quickly. Do not create a denial of service scenario on your own computer by trying to calculate an Ackermann number that you think might be just a little bit bigger. It might be a lot bigger. For example, A(4,1) is a five digit number. A(4,2) is a 19,729 digit number that is larger than the number of particles in the known universe. Clearly, even my Pentium-4 running Linux will take a while to calculate A(4,2).


Copyright © 2010 by Asylum Computer Services LLC Return to CS Labs