Source: Daniel Wellman (with illustrations!)
One of my favorite movies as a kid was Tron, the early 1980's film about a computer programmer who gets “digitized” and sucked into a computer world inhabited by personified computer programs. In the film, the protagonist joins a group of resistant programs in an effort to take down the oppressive Master Control Program (MCP), a rogue piece of software which had evolved, acquired a thirst for power, and was attempting to take over the Pentagon's computer systems.
In one of the most exciting scenes in the film, the hero programs race in light cycles, which were two-wheeled motorcycle-like vehicles that left walls in their wake. One of the protagonists forced an enemy cycle to crash into the arena's wall, leaving a gaping hole. The heroes dispatched their opponents and escaped through the hole to freedom – the first step on their way to take down the MCP.
When I watched that movie, I had no idea that I would unwittingly recreate the Tron world years later, rogue programs and all, with an Apple IIgs computer.
Here's how it happened: When I first learned to program, I decided to create a version of the Tron light cycles game. My friend Marco Busse and I programmed it on an Apple IIgs using ORCA/Pascal and 65816 assembly language. During play, the screen background was solid black with a white border, with one color line representing each player. We displayed the game score in a horizontal strip at the bottom of the screen. It wasn't the most graphically advanced program, but it was simple and fun. It looked something like this:
Sample Game Screen
The game supported up to four players – that is, if they scrunched up close together on the same keyboard. It was clumsy, but it worked. We rarely had enough people in the same place to play as all four cycles, so Marco eventually added computer-controlled players that could put up a reasonable fight.
The Arms Race
At this point, the game was a lot of fun already, but we wanted to experiment. We added missiles in order to give players a second chance to blow their way out of an impending crash. As Marco described it years later, “Both the AI and the humans had three missiles they could use during the course of the game. When a missile hit a wall, it would create a mini 'explosion' that would erase the color on the background back to black as it faded out – thereby eliminating sections of the trail left by previous cycles.”
Soon we had players and computers firing missiles to shoot their way out of tight situations. Nonetheless, Tron purists may scoff, since the movie programs didn't have such luxuries as missiles to get them out of a bind.
The Escape
Like all accidents of a bizarre and unusual nature, this one was unexpected.
One day, when Marco and I were playing against two computer opponents, we forced one of the AI cycles to trap itself between its own walls and the bottom game border. Sensing an impending crash, it fired a missile, just like it always did whenever it was trapped. But this time was different – instead of firing at another trail, it fired at the game border, which looked like any other light cycle trail as far as the computer was concerned. The missile impacted with the border, leaving a cycle-sized hole, and the computer promptly took the exit and left the main playing field. Puzzled, we watched as the cycle drove through the scoring display at the bottom of the screen. It easily avoided the score digits and then drove off the screen altogether.
Shortly after, the system crashed.
Our minds reeled as we tried to understand what we had just seen. The computer had found a way to get out of the game. When a cycle left the game screen, it escaped into computer memory – just like in the movie.
Our jaws dropped when we realized what had happened.
So what did we do after discovering a defect in our program that could methodically crash the entire system? Crashed Apple II Screen from Mike's Hobby Home We did it again. First we tried to blow our own way out of the game screen. Then we forced the computer to escape – repeatedly. Each time we were rewarded with fantastic crashes. Sometimes the disk drive light would twitch as the drive groaned into unending service. Other times, the screen would change to nonsensical text, or the speaker emitted a shriek or a low drone. Sometimes all of these things happened at once, leaving the computer in a state of total meltdown.
So why did this happen? To understand the answer, let's peek into the architecture of the Apple IIgs computer.
(Un)Protected Memory
The Apple IIgs operating system didn't have protected memory, a feature present in most modern operating systems that assigns programs memory space and restricts them from accessing memory outside that space. The upshot was that an Apple IIgs program could read or write anywhere it wanted (except it couldn't write to ROM – Read-Only Memory). The IIgs used memory-mapped I/O to access devices like the disk drive, which meant that you could activate the disk drive by reading from a certain memory location. Graphics programs took advantage of this design by reading and writing directly to the screen memory.
The game used one of the IIgs's Super Hi-Res modes; it ran at a glorious 320x200 pixels with a palette of 16 colors. To choose the palette colors, the programmer mapped sixteen entries (numbered 0 – 15 or $0 – F in hexadecimal) to 12-bit color values. You could read and write colors directly to the video RAM to paint the screen, just like you could read and write in program data memory.
Crash-detection algorithm
The game took advantage of this fact and implemented crash detection by reading directly from video RAM. For each light cycle, the game computed its next position based upon its current heading and read that pixel from video memory. If the position was empty, represented by a black pixel (palette entry $0), the player was safe and the game continued. But if the position wasn't empty, then the player had collided with a either a light cycle wall or the white game border (palette entry 15 or $F). Here's an example:
Sample video RAM
This example shows the upper-left corner of the screen, with color $F representing the white game border and color entry $1 representing player one's green cycle. Here the player is moving left as indicated by the arrow, which means the next space is empty, or color $0. If the player continued in this direction for one more move, they would collide with the wall (color $F) and crash.
Going off the grid
The algorithm to determine which pixel to check next used some fast assembler math to calculate a memory address – either one pixel above, below, to the left, or to the right of the current pixel. But since any given pixel on the screen was really just a memory address, the algorithm simply calculated a new memory location to read. So when the light cycle left the screen, the game happily calculated the next location in system memory to check for a wall crash. This meant that the cycle was now cruising through system RAM, wantonly turning on bits and “crashing” into memory.
Writing to random locations in system memory isn't generally a wise design practice. Unsurprisingly, the game would generate spectacular crashes as a result. A human player would be driving blind and usually crash right away, limiting the scope of system casualties. The AI opponents had no such weakness. The computer would scan immediately in front, to the left, and to the right of its position to determine if it was about to hit a wall and change directions accordingly. So as far as the computer was concerned, system memory looked no different than screen memory. As Marco described it,
We can only speculate what it started doing once it left screen memory, since it obviously would look to find a way to continue going in a direction that was occupied by 0’s. If it became blocked and ran into a “wall” of numbers, it would die. In those spectacular crashes though, it would sometimes be running around very much “alive” until at some point it either overwrote some code being executed with a trail that didn’t make sense, or it would access some memory mapped device that would then cause a crash. But it wasn’t immediate – the AI ran around for a little while out there before it crashed the system.
In the end, we had not only recreated the light cycle game from the movie, but recreated the escape as well. And just like in the movie, the escape had great consequences.
Nowadays, with operating systems that have protected memory, this sort of thing wouldn't happen so easily. Still, it makes me wonder if there are Tron-like programs out there trying to break free from their “protected spaces” — all in an effort to stop rogue AI code from taking over the Pentagon.
I guess we'll have to wait for that digitizer to get invented in order to find out.