This is a great example of Bratus et al refer to as a "weird machine" [1], in which an attacker uses crafted input to create a new and unexpected computational environment. That is, by using special input, the attacker manipulates pieces of the target program to act like a CPU that processes "weird commands" (ie more special inputs are used as assembly instructions that run on the weird machine).
Anyway, there is a rising field ("language-theoretic security") that studies this phenomenon. If this Pokemon example interests you, then you should give it a look.
Wow - excellent link. I've been thinking about this lately. I'm not alone in thinking that languages are going to be important here. This is a great resource for further study! Thanks!
Not really. As I understand, the different layers are:
1. In-game, he can write non-arbitrary but sufficiently powerful machine code to be executed directly. He uses this to write layer two.
2. He can write arbitrary machine code using A, B, start, select. He uses this to write layer three.
3. He can write arbitrary machine code using all the buttons (including d-pad combinations that I assume are physically impossible). He uses this to write the balloons.
All the code that actually gets run is precompiled machine code being executed by the processor. (There's nothing to stop him writing a shell, he just didn't.) He's not exploiting a system which happens to be turing-complete, he's gaining access to a system which was designed to be turing-complete but locked down.
Fascinating. I always wondered if this sort of thing was possible when I noticed as a child that pressing multiple buttons at the same time on my parents calculator made the screen show stuff that wasn't actually real numbers (things like a 2 with a part missing, etc.). Likewise seeing which buttons on the VCR have precedence (e.g. if I hold down "play" and press "stop" then what happens? And vice versa?). I always assumed the device wouldn't be designed comprehensively to handle all possible inputs like that, so there was a chance some of them would allow you to do funky unintended stuff.
Given the complexity and freedom of access that a videogame has, I'm not surprised that this hack is technically possible, but it is very impressive that someone's managed to do it!
There's this kind of unintended effects all over the place in tech.
A particularly interesting one for programmers might be the M6502 CPU.
All opcodes on the M6502 are 8 bits. Due to the way it was implemented in order to keep transistor count low, various patterns will trigger specific functionality at specific stages of execution (you can find a javascript emulation of it that displays the execution in excruciating detail as the result of creating a transistor exact clone of the design by decapping an actual 6502 CPU and scanning it...).
These were arranged so that the documented instructions present a suitably useful instruction set. But all of the remaining opcodes still does something that was simply deemed pointless by the designers.
Some have been found useful by demo writers in particular as a way of saving cycles. Some are just totally bizarre and/or unstable. Some does fun stuff like putting more than one value on the memory bus at the same time. Some even locks the CPU up so solid it needs to be power cycled to recover...
Here's an overview of the nitty gritty details from someone who actually knows what they're talking about: http://www.pagetable.com/?p=39
Ha! When I was a kid we had Pong. You know, the hard-wired kind that plugged into your television, and get off my lawn, but this one had three variant games: Pong, basketball, and ... racketball I think. There was a hard three-position switch to switch between games - and if you positioned it just right between positions, you could coax the game into a hybrid game that mixed up the court layouts.
"This script walks from the Viridian City pokemon store to Oak's Lab in the most efficient way possible. The walk-thru-grass function guarantees that no wild battles will happen by manipulating the game's random number generator."
Most tool-assisted speedruns (TASes) for old-school video games, usually RPGs like Pokemon, include a "manipulates luck" clause. The emulator uses save-states, and if there's a random encounter, the player reverts to an earlier state. Repeat until successful.
Some games have naturally exploitable RNGs too. The GBA RPG Golden Sun and its sequel, for example, had a RNG that was completely reverse-engineered for players to get the top items that normally only randomly drop extremely rarely.
In one of my least favorite games of all time, Final Fantasy II, it was possible to reset the "steps remaining until random battle" number by entering the menu and healing a character without full HP.
The number was actually stored in the save file, so you could just count steps until you entered a random battle, reload the system, and take n-1 before healing to completely avoid encounters. I expect this was purposeful because the battle system was so tedious and the encounter rate was obnoxiously high.
> 10) We think we've figured out how to hack into the computer our universe is running on.
It seems Software Engineering still has a long ways to go as a discipline: games like this fall to exploits by a small community after only a few years, while somehow the universe we live in has survived our civilization (and maybe others) banging on it for billions without any noticeable hiccups. ;)
I think the issue is most software is not designed with security as a primary concern, so a determined users can produce a convoluted input that breaks a system. Having said that, if you take out buffer overflow exploits, how many games would still be hacked?
For anyone that don't get the reference: This is from Hitchikers guide to the galaxy, which goes on to spend a few paragraphs describing how to fly by throwing yourself at the ground and missing it. As it says, "clearly, it is the second part, the missing, which presents the difficulties".
By the way, it's also exactly how orbiting works. The Moon and all the satellites are trying to fall down on us constantly, but they go so fast they actually keep on missing :).
Note that a key part of the hack requires the hardware to reset while a save game write is in progress. This causes the file to have invalid data -- an inventory list count is set to an "impossible" value.
Then, within the game, the invalid-length-list is used to overwrite other arbitrary locations, including a function pointer to an update procedure. Once that's overwritten he can jump to his own code and it's "game over" as in, he completely controls the hardware.
But from what I can see, it wouldn't be possible without the initial hardware resetting during a write. Not that it diminishes the awesomeness, it'd just be a bit purer if it was a software-only hack.
If you're really into this, spend some more time on tasvideos.org
The guys that do these tool-assisted speed runs are incredible. One fellow plays 4 Mega Mans all at once with a single controller doing input for all 4 games at the same time.
This Pokemon hack is insane, but was inspired by a guy who uses it to beat the game in around 2 minutes. That particular speed run abuses the fact that everything in the game has a simple identifier. So, what he does is inserts a warp point into his inventory, drops it in front of himself, and walks through it to the end of the game.
I built a layer of clojure code on top of the JNI bindings to get
an entirely functional interface to vba-rerecording. This
interface treats state of the emulator as an immutable object, and
allows me to do everything I could do with the lower level C
interface in a functional manner. Using this functional code, I
wrote search programs that take a particular game-state and try
out different combinations of button presses to get any desired
effect. By combining different styles of search with different
initial conditions
Just like the amazing amount of StarCraft glitches, ranging from making ground units fly to completely insine stuff like turning a unit into a trap that crashes the game for every player who looks at it (and after some time crashes the game for everybody). All by legal in-game actions. I can't find a link, but one comprehensive summary back in the old days suggested that at least some of those glitches may be intentional, given how improbable, weird and useful they were.
If you're interested in seeing what happens when you really want to hack the game though glitching/RAM abuse via cheat codes, check out this Let's Play of Pokemon Blue.
Probably not many. He used a buffer overflow exploit (found by someone else) to achieve arbitrary code execution (in a program not designed for security). That is not a trivial task (given the limited number of op-codes he was able to use), but not something that deserves job offers.
I think you underestimate how easy it is to exploit buffer overflows on systems with no exploit mitigations. Come back when you have ASLR and DEP running on the gameboy.
For those that are wondering if something like this is possible outside of computers/video games, I would recommend a study of Lucid Dreaming. If brain hacking is possible, this has to be the best method of entry into the system.
So am I correct in my understanding that this sort of hack is made possible only because the Gameboy uses an 8080 derived chip with Von Neumann architecture? ie. if it used a Z8 (or any other Harvard Arch chip) it wouldn't be possible to "bootstrap" like this?
Anyway, there is a rising field ("language-theoretic security") that studies this phenomenon. If this Pokemon example interests you, then you should give it a look.
[1]http://www.cs.dartmouth.edu/~sergey/langsec/