Short Codes, Big Effects

The set of short codes in all programming languages that have significant, and perhaps unexpected effects is a particularly fascinating one, because often the most seemingly innocent codes can cause a variety of problems. Some of the most clever lines of code ever written (like the one-liners in Python) rely on hugely compact writing, approaching “Kolmogorov complexity”-like optimizations.

After the System.exit(); command in Java and its translations into other programming languages, the most well known of such codes is rm -r ./ on Linux machines. It’s so effective at destroying your computer that you cannot execute this code in “vanilla mode”. Trying to execute it on my virtual Linux Mint, caused it to remove all of my files, but stopped short from deleting system necessary ones:

• rm is the utility with which one can remove files
• The -r flag denotes the “recursive” option, which is used for deleting folders and its contents
• ./ denotes the root folder which holds all of the contents of the Linux operating system.

On Windows machines, the corresponding command is del -r *. These two commands permanently not only damage your computer, but actively destroy it, hence why they are essentially banned from use.

When programming, protections against infinite loops ought to be implemented to not cause a total crash of a server. But while (true) {} and its translations are useless in practice, and serve no purpose other than to block the event loop from executing anything else. Hence why they used sparingly.

The sleep()function however, a glorified while (true) {}, has plenty of eclectic use-cases, from creating a more user-friendly UI, to reducing the power-consumption of an application, along with the joke use of “increasing performance by removing strategically placed sleep functions”. The key to abusing it however, is that sleep is used on the millisecond level: if the time to sleep is large, some processes can seem like they won’t ever end, hence why a quick way to crash an API call or execution thread would be to sneak this function in with a very high time limit.

Next to infinite loops, and such sleeping creatures, you also have algorithmically complex functions, that, may not be infinite, but can take long enough for big enough input, that they quickly become unacceptable forms of programming (somewhere around n³), mirroring sleep and while(true) {}. NP problems are also part of these programs, because they are, as far as we know, only solvable in exponential time. The Hamiltonian Path problem for instance, can take a very very long time to run, such that it seems like the algorithm might never halt.

But these algorithms usually take more than a few lines of code to write, and are easily identified in code review as ones that need to be deconstructed. Enter the elegant Ackermann function. It looks like an innocent enough recursive function that can be expressed in 5 simple Python lines. Watch however, as a few toy inputs result in unexpected maximum recursion limit errors:

def A(m, n):
   if m == 0:
      return n+1
   if n == 0:
      return A(m-1,n)
   return A(m-1, A(m,n-1))
print(A(2,2)) # 7
print(A(2,3)) # 9
print(A(3,2)) # 29
print(A(3,3)) # 61
print(A(4,2)) # maximum recursion depth exceeded
print(A(4,1)) # maximum recursion depth exceeded

As it turns out, the value that A(4,2) would spit out (if we had infinite computing resources) a number that contains over 19’000 digits! Not only this, but it would compute it by adding the number 1 manually, until it gets there. The function is not just a crazy exponential function, but one whose complexity O(mA(m, n)). In other words, the complexity of the function increases with the value that it results in, which is a very unintuitive notion. Written in other programming languages, one can get it down to 3 lines, such as in C.

int A(int m, int n) {
    if (m == 0) { return n+1; }
    if (n == 0) { return A(m-1,1); }
    return A(m-1, A(m,n-1));
}

While these nasty monster functions rely on a “recursion overflow”, there is a short shell code that relies on a “thread overflow”: The forkbomb, a well known red team exploit, which I have copied from RTFM: Red Team Field Manual by Ben Clark, is written in shell and looks like this: :(){:|:&};:

This very short code defines a function that creates two threads, which in turn, execute the same function, thus creating another two threads, such that within only 10 recursion steps, there are 1024 threads all executing more thread-creating madness. This slows your computer down pretty quickly, regardless of your hardware, to the point where you need to restart your computer to clear the threads.

With these things in mind, when people work together on a software project, there are also rules in place, so that everyone can manage their code in harmony. On the software engineering side of things, the quintessential devastating command (or should I say, “option”?) is the memeified git push ––force, which is unfortunate knowledge to have, given that one can accidentally use it in one’s work:

• git specifies the git utility for version control
• push tells the utility to place the changes you’ve made on your local machine, to the remote repository
• The ––force flag tells it to overwrite any changes on the remote repository, thus risking the loss of changes from other team members.

Given that this command can erase previously completed work, it is implicitly understood not to ever use this option, as it can easily waste people’s time rewriting code.

Of course, there are plenty more little snippets that can cause real havoc (kill, shutdown, or while(true) { malloc(10) }), and the few presented here are only a small part of the whole set. But they’re good to know, always a nice reminder of how dangerous a few characters can be and how mediocre code review can make or break supercomputers.