View source for Arbitrary code execution

{{Incomplete|needs=needs loads of links to documented examples of exploits, images, much more explanation of what's going on, possible links to TASvideos, etc.}}
'''Arbitrary code execution''' (often shortened to '''ACE''') is a type of [[glitch]] exploit or security flaw that allows a user to run custom code, including code not contained in the software's original source code. Glitch exploits capable of enabling arbitrary code execution are present in several Pokémon games.

Because arbitrary code execution allows a user to run almost any code that the hardware is capable of executing, arbitrary code execution is often used during [[speedrun]]ning (in formats in which it is permitted).

==Cause==
Data storage on any standard computational device consists of two fundamental types, ROM ({{wp|read-only memory}}) and RAM ({{wp|random-access memory}}). In the context of a game console, ROM consists of the game code which cannot be modified (short of physically tampering with the cartridge), while RAM consists of any data that may change on a continuous basis, such as the contents of the save file (SRAM), the contents of the screen/video display (VRAM), and other variables (such as whether or not the player is currently in a battle, or the current sound(s) that are playing, or anything that needs to be temporarily stored such as numbers in the middle of a formula calculation or routine<!-- registers -->). (Notably, all data stored in RAM, except for SRAM, is deleted whenever power to the machine is cut.)

One temporary value that exists in any standard machine is the processor's {{wp|program counter}}, which points to the memory location where the next line of code is to be read and executed. Normally, the program counter automatically increments by 1 each time a line of code is read, such that individual lines of code are read sequentially; however there are many cases where a line of code will tell the program counter itself to jump forward or back (such as when some lines of code must only be executed under certain conditions and must be skipped otherwise, or when the game must wait for a certain condition to be true before progressing, and must continuously check that condition until it is true). Commands that cause the program counter to do this are known as ''jump instructions''<!-- or "branch instructions", but I'm 70% sure that GB assembly instead calls them "jump if zero" and "jump if not zero"; regardless, not quite relevant to the article -->. Naturally, as all game code exists in ROM, all proper jump instructions must point to a location in ROM. The program counter just blindly reads in and executes code at whatever memory location it is pointing to (and then increments itself by 1); thus faulty jump instructions may cause the program counter to start reading in garbage values from an unexpected place and attempt to interpret them as code, making this one possible source of glitches.

Arbitrary code execution is fundamentally caused whenever faulty code contains a jump instruction that causes the program counter to jump to a RAM location instead of ROM. From here, as RAM values can be controlled by the player unlike ROM values, it becomes possible for the player to modify these values, and values stored just after it, in order to spell out specific lines of code that are desirable or exploitable.

Sources of arbitrary code execution can include various [[Glitch#Glitch characteristics|glitch items, moves, etc.]], whose effects are never intended by the developers and are thus faulty code by definition. For example, a normal item would likely instruct the program counter to jump to some predetermined location that contains code for the correct behavior of that item, while a glitch item may instruct the program counter to jump to an unexpected location, thus running faulty code.

As arbitrary code execution literally enables the player to do anything the console's hardware is capable of, it has enormous potential and can be thought of as "jailbreaking" the console; extremely elaborate setups have been performed and documented where players have coded new graphics, music, or even entire new games onto the platform.

==Methods==
After discovering a glitch that causes the program counter to jump to RAM, it is often the case that the initial location jumped to is hard for the player to control (such as sound bank data). Thus, it is common for most arbitrary code execution setups to first spell out only a small amount of code there, forming another jump instruction that will lead to a second location in memory that is easy for the player to modify. Examples of such locations can include [[party]] or [[PC]] data, [[Bag]] contents, [[Pokémon Storage System|Box]] names, and Pokémon [[nickname]]s. Once this has been done, the player may readily fill the second memory area with arbitrary code for the console to execute, and then perform the initial jump (by using the glitch item, glitch move, etc.), which will perform the second jump to the filled code and cause it to be run.

For more complex exploits, the above "two-stage" jump setup may not be enough as the game will eventually run out of space in the easily modifiable second location (the Bag/Box/etc.) to continue spelling out code. It is possible to extend the setup to three stages by writing code in the second location whose effect is to write more code to a third location that contains more space but is hard for the player to modify directly<!-- such as what? couldn't find a direct example; does someone with more experience know what location is being written to in the linked video? -->. Once enough code has been written to the third location, the player may substitute the second location's code for code that jumps to the third location, then perform the glitch which will execute three jumps and run the desired code.<ref>https://www.youtube.com/watch?v=D3EvpRHL_vk</ref><!-- This multi-stage setup is specifically *NOT* TAS-exclusive; in fact it's the most viable substitute for jumping to controller input when the goal is to show off a demonstration unassisted rather than speed. -->

Even more advanced setups may jump the program counter to controller input<ref>http://tasvideos.org/2187M.html</ref><!-- linking to the older and now obsolete run as it demonstrates this better -->, allowing a theoretically unlimited amount of code to be entered and run on the fly without having to store it all beforehand. Current demonstrations of this type of setup have so far been TAS-exclusive (as controller input is polled on and can change every frame, 60 times per second, as well as due to the very large amount of code that must be desired for such a setup to be worthwhile unassisted<!-- clarification: even if realtime is involved, if the desired exploit (e.g. programming Pong/Snake) is small enough, no one's going to spend the time to craft an unlimited input buffer when the storage space within the game's RAM is enough. A desired exploit has to be really huge to no longer fit inside all of the game's RAM and require jumping to controller input for more space. Code this large would take on the order of hours to input at realtime speed, which makes it unlikely. This sentence is NOT saying that programming the controller input loop itself is a large amount of code; it's saying that there's no point in programming such a realtime controller input loop in the first place unless the desired exploit (which is programmed in AFTER the input loop) is large enough to require it. -->); however as the setup code can be arbitrary, it is no doubt possible to program an input loop that is slow enough to be performed in real time.

Performing an arbitrary code execution glitch (i.e. using a particular glitch item, etc.) without any setup beforehand can be highly dangerous, as the program counter will jump to RAM and then begin to execute potentially numerous lines of completely unpredictable code (depending on whatever changing values happen to be there in RAM at the time) before a stop command happens to be reached. Such lines of unpredictable garbage code may happen to include, for example, code whose effect is to fail the save file's verification check, destroying it.<!-- This is significantly worse than, say, glitch items that crash the game, because at least they run predetermined garbage code and thus have predictable effects. --><!-- So for example, never use the 8F item unless you already have a setup in place inside your party, items, etc.. Whatever unpredictable stuff (e.g. crash) that happens afterward, soft-resetting the game in an attempt to undo that may just be the worst thing to do. --><!-- Link to glitchcity.info forums where this happened to someone -->

===[[Generation I]]===
Using the glitch item 8F{{sup/1|RB}} or 5かい{{sup/1|RG}} causes the program counter to jump to the RAM location that stores the number of Pokémon in the player's [[party]]. This value (as well as values stored just after it, such as the contents of the player's party and their [[Bag]]) is particularly easy to modify right off the bat, and as such this may be considered one of the easiest arbitrary code execution setups to perform once the item has been obtained.<ref>http://forums.glitchcity.info/index.php/topic,6638.0.html</ref><ref>http://forums.glitchcity.info/index.php/topic,6573.0.html</ref>

To have maximum possible control over the values in memory corresponding to the Bag, heavy use of the [[item duplication glitch]] is common.

The current simplest known way to obtain the 8F item is through the [[item underflow]] glitch. A possible alternate method, though much more time-consuming, involves the glitch Pokémon [[94]] and [[94 h]] whose invalid Pokédex number of #213 corrupts the fourth item in the player's Bag, increasing its index number by 16 upon encountering it (similar to how encountering any Pokémon with a Pokédex number of #000 [[item duplication glitch|increases]] the quantity of the sixth item by 128). This allows transforming a [[Good Rod]] into 8F. An even older method which uses the heavy corruption effects of [[Super Glitch]] also exists.

Outside of 8F and 5かい, numerous other arbitrary code execution exploits also exist in these games, such as situational use of the glitch move {{m|--}} or turning [[Pallet Town]] into [[Twinleaf Town]]<!-- link to TASvideos submission exploiting this-->.

===={{game|Yellow}}====
Similarly, to 8F and 5かい, the glitch item ws# #m# causes the program counter to jump to the RAM location which stores the list of Pokémon in the current [[Pokémon Storage System|PC box]] upon use, enabling easy arbitrary code execution<ref>http://glitchcity.info/wiki/index.php/Arbitrary_code_execution#Using_.22ws_m.22_.28Yellow.29</ref>. Like 8F and 5かい, ws# #m# can be obtained using the [[item underflow]] glitch or with [[pPkMnp' ']].

Additionally, a separate arbitrary code execution method exists exclusive to Yellow, which can be started by any event that causes the player's [[walking Pokémon|following]] Pikachu to stand off-screen (such as the {{m|sing}}ing {{p|Jigglypuff}} in [[Pewter City]]'s [[Pokémon Center]], the {{p|Clefairy}} in the [[Pokémon Fan Club]], or a number of [[Glitch City|Glitch Cities]]). Walking while Pikachu is off-screen will in fact slowly cause memory corruption to the current map and nearby areas in memory (such as the current save file's gameplay timer as well as Pikachu's [[happiness]] value)<ref>http://forums.glitchcity.info/index.php?topic=7130.0</ref> as the game runs buggy code that attempts to keep track of Pikachu's off-screen position; it is possible to walk around in specific patterns to eventually create an arbitrary code execution setup by corrupting the map to place an invalid [[signpost]] on the map whose routine points to RAM rather than ROM<ref>http://wiki.pokemonspeedruns.com/index.php/User:Stump/Yellow_NSC_Pikachu_Offscreen_Stat_XP_ACE_Route#Pikachu_Offscreen</ref>.

==={{game|Gold and Silver|s}}===
{{Incomplete|section|needs=grammatical cleanup/organization/paragraph breakup, more explanation, maybe transfer some stuff from one article into the other (either direction) or even merge the two articles together}}
In English releases of Pokémon Gold and Silver, the [[Coin Case glitches]] are a subset of arbitrary code execution glitches.

In the Japanese versions, the Coin Case executes code at a certain place (which tells the player how many coins they have) and terminates that with a hex:57 terminator, this causes the code to stop. However, in English releases that terminator is not valid and causes the code to jump to echo RAM at E112 and run code at that spot. The reason this was not caught in the testing of the game is because this section is typically made up of mostly 00, so nothing visible occurs. But if the player has listened to a certain cry, the address executes code that actually has a visible effect, such as 'which move?he PP of' or a glitch dimension. When the cry is of a {{p|Bellsprout}}, {{p|Machop}}, {{p|Machoke}}, or {{p|Omanyte}}, this effect makes the code jump again, to address EB12. This address can be modified by using specific [[party]] Pokémon, such as a level 23 {{p|Quagsire}} holding an [[HP Up]] with {{m|Sleep Talk}} as its first move in the fourth party slot, to send the code to the PC items. The Quagsire can be given a [[Protein]] instead to jump to the [[Pokémon Storage System|Box]] names. That data is then modified along with certain movement patterns to achieve an effect, such as obtaining {{p|Celebi}} or [[Five question marks#Hex FF|????? (FF)]], going to [[Mt. Silver]] with no Pokémon (causing the player to win automatically), or coding an entire new game onto the console.

==={{game|Crystal}}===
{{Incomplete|section|needs=Look up more detailed explanation from PokemonSpeedruns.com, Pokemon Crystal any% category}}

A variant of the [[Celebi Egg glitch]] allows the player to control the [[held item]] in addition to the {{OBP|Pokémon|species|species}} of the Pokémon obtained. This can be manipulated to cause the held item to be a [[Key Item]], something that is not normally possible.

Removing a held Key Item from its holder while another copy of the item is already in the [[Bag]] will cause the duplicate copies to appear as two separate, identical stacks. The two stacks must then be placed next to each other and a third normal Key Item placed below them. At this point, swapping the two identical stacks (with the Select button), behavior unaccounted for by the developers, will corrupt the second stack and either corrupt or destroy the third stack.<ref>https://www.youtube.com/watch?v=FZrFMi6B0jQ</ref> From here, as the number of stacks in the inventory has now unexpectedly decreased, it is possible to achieve a similar effect to the dry [[item underflow]] glitch in [[Generation I]], giving the player access to 255 items in the Key Items Pocket; the underflow effect can then be spread to other pockets via item swapping.

As with [[Generation I]], precise out-of-bounds item manipulation can be used to either place a certain [[TM]] outside of the TM/HM Pocket, or corrupt the player's current Pokédex sort mode, depending on the language version of the game. Either way, attempting to use the TM in an invalid way or open the Pokédex in its glitched state will execute faulty code and cause the game to jump to RAM, enabling arbitrary code execution.

==={{game|Emerald}}===
Viewing the summary of at least one [[??????????]] glitch Pokémon is known to cause the program counter to jump to the location in RAM where [[nickname]]s of Pokémon in the [[PC]] are stored. The only currently known method to obtain this glitch Pokémon is through [[Glitzer Popping]], a sub-glitch of the [[Pomeg glitch]]. Due to the limited set of data values that nicknames can hold, applications of arbitrary code execution using this method are limited.<ref>https://www.youtube.com/watch?v=m9pvNYdhldo</ref>

At least one glitch move's animation script is also known to point to SRAM, specifically address $0E0F14C0 which can be manipulated to redirect the animation pointer to the 11th pc item and then the 15th item. Again, Glitzer Popping is the only currently known method to obtain a Pokémon with this glitch move (Move 27a2 (E! E! ho!)). Arbitrary glitch items and quantities can be obtained through another subglitch of the Pomeg glitch currently undocumented on Bulbapedia, making this method much more viable to spell out code compared to using nicknames, however, because of the nature of save data, the file always shifts 2 nibbles and therefore, if your save file has an odd number at address 0E0F14C0 at the beginning, the save file can not be properly manipulated and that save file is not viable for this method of arbitrary code execution
<ref>https://www.youtube.com/watch?v=1pb-6hMDQBs</ref>

==={{game|Diamond and Pearl|s}}===
{{incomplete|section|needs=https://www.youtube.com/watch?v=tmPzFAuKMA8}}
Arbitrary code execution is possible in {{game|Diamond and Pearl|s}}.

==History==
{{Incomplete|section|needs=discuss history of how ACE was discovered; iirc it was first done in Super Mario World with the Yoshi's Island 3 spinning platform stack overflow credits warp, and then the full extent of its arbitrariness demonstrated rather spectacularly in Pokémon Yellow; link to TASvideos; maybe even link to AGDQ demonstrations}}

==References==
<references />

==External links==
* [http://glitchcity.info/wiki/index.php/Arbitrary_code_execution Article on Glitch City Wiki]
* [https://en.wikipedia.org/wiki/Arbitrary_code_execution Article on Wikipedia]

{{Glitches}}<br/>
{{Project Glitchdex notice|no}}

[[Category:Glitches]]

[[fr:Exécution de code arbitraire#Dans Pokémon Rouge et Bleu]]
[[zh:任意代码注入（漏洞）]]