Posted: 5/25/2017 8:46 PM
Post subject: History of Arbitrary Code Execution
Quote
DeathInABottle
He/Him
Joined: 5/25/2017
Posts: 2
Location: Canada
I'm an academic working on a book about the relationship between the design, play, and political philosophy of videogames. One of the chapters is a semi-historical account of practices related to tool-assisted speedrunning, and I'd like to get my facts straight. I'm working on a section on arbitrary code execution right now, and I'd like to identify a rough origin of the practice; from what I can tell, Masterjun popularized it with the credits warp for SMW (http://tasvideos.org/1945M.html), though it sounds like he didn't originally discover it - or at least that it involved あんた (anta) and p4plus2. And I'm not at all sure about the existence of other forms of ACE that predated the SMW credits warp. If you can point me to any other, earlier instances of ACE in TASVideos or elsewhere, I'd be very grateful. Thanks!
Posted: 5/25/2017 9:37 PM
Quote
feos
Site Admin, Skilled player (1254)
Joined: 4/17/2010
Posts: 11475
Location: Lake Char­gogg­a­gogg­man­chaugg­a­gogg­chau­bun­a­gung­a­maugg
NES TAS of 2011
Complete timeline: http://tasvideos.org/Movies-C3050Y-RatingV-Obs.html Some of the ACE setups were replicated real-time, but I don't have the links. Seth Bling performed one for SNES for example.
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Posted: 5/25/2017 9:48 PM
Quote
Amaraticando
It/Its
Editor, Player (159)
Joined: 1/10/2012
Posts: 673
Location: Brazil
TAS of 2015 SNES TAS of 2015
This is the timeline of the credits warp for SMW. Not 100% complete, but covers almost everything important. This text was originally written by nathanisbored and SethBling. - [Jan 2009] Let's Player raocow accidentally does null sprite glitch ( https://www.youtube.com/watch?v=xOOT2XIm5o0&t=7m20s ) - [June 2009] ISM finds item swap ( https://www.youtube.com/watch?v=0jvZ_u2Q9Ls ) - [Sep 2010] Mister discovers item swap with powerups instead of overloading sprite table ( http://tasvideos.org/forum/viewtopic.php?p=247535#247535 ) - [Oct 2010] nathanisbored recreates null sprite with double-tongue glitch ( https://www.youtube.com/watch?v=g25UHjarSCY ) - [Oct 2010] bahamete discovers side effects of null sprite on brown revolving platforms ( https://www.youtube.com/watch?v=zQFseooBPl0 ) - [Oct 2010] WillDaBeast innovates item swap with fire/coin instead of powerup ( https://www.youtube.com/watch?v=ZB0iXcD6WCc ) - [Oct 2010] Mister debugs null sprite's properties ( http://tasvideos.org/forum/viewtopic.php?p=250970#250970 ) - [Oct 2011] nathanisbored accidentally discovers eating chuck gives powerup effects ( http://tasvideos.org/forum/viewtopic.php?p=292639#292639 ) - [Nov 2011] Antaasas exploits null sprite on brown platform to credits warp from YI3; p4plus2 reverse-engineers Antaasas's movie and documents code in English ( http://tasvideos.org/forum/viewtopic.php?p=294959#294959 ) - [Dec 2011] Masterjun submits first credits warp TAS to TASVideos ( http://tasvideos.org/1945M.html ) - [Dec 2011] nathanisbored discovers stun bug using double-tongue glitch ( https://www.youtube.com/watch?v=Dd5t6Vsucqs ) - [Mar 2012] Antaasas discovers credits warp in YI2 with stun bug; turns out to be due to emulation error and not possible on console ( https://www.youtube.com/watch?v=nHK_lOk9dic ) - [Apr 2013] Masterjun improves the run without emulator bug and creates first ACE TAS ( http://tasvideos.org/2380M.html ) - [Jan 2014] Following Antaasas's suggestion, Masterjun debugs chuck-eat crash and manipulates open bus code to controller ports for the current ACE TAS ( http://tasvideos.org/4315S.html ) - [July 2014] jeffw356 reverse-engineers Masterjun's run to find RTA-viable setup ( http://pastebin.com/pEKutJZQ ) - [July 2014] jeffw356 completes successful credits warp RTA ( http://www.twitch.tv/jeffw356/c/4762957 ) - [Jan 2015] SethBling completes first successful credits warp RTA on console ( https://www.youtube.com/watch?v=14wqBA5Q1yc ) - [Jan 2015] DotsAreCool and nathanisbored improve route using berries; SethBling writes new code to reach earlier credits ( https://www.youtube.com/watch?v=c1d2ujQO7J0 ) - [Jan 2015] Dram55 and SethBling improve route by breaking block at end of level ( https://www.youtube.com/watch?v=vLACETAAbV4 ) - [Jan 2015] CarlSagan42 improves the route using turn block particle ( http://www.twitch.tv/carlsagan42/c/6022246 ) - [Feb 2015] Thanks to Carl's improvement, p4plus2, nathanisbored, and DotsAreCool improve route by eating 2nd chuck ( https://www.youtube.com/watch?v=-IFj3rqY3G4 ) - [Feb 2015] p4plus2 writes more condensed code and makes warp more consistent. nathanisbored, DotsAreCool, and CarlSagan42 improve route around it ( https://www.youtube.com/watch?v=RzwDB_gnie4 ) - [Feb 2015] MrCheeze finds powerup incrementation+multitap route that's nearly 100% reliable and safe ( https://pastebin.com/Wy6XKYmS ) - [Mar 2015] DotsAreCool creates TAS for marathon safe credits warp ( https://www.youtube.com/watch?v=6nBzTeXFfmE ) - [Mar 2015] PangaeaPanga improves route by using coin sparkles to replace turn block particles. ( https://www.twitch.tv/videos/40800223 ) - [Feb 2016] SethBling improves on marathon safe credits warp with a second multitap ( https://www.twitch.tv/videos/43025721 ) - [Mar 2016] SethBling finds frame-perfect LR cloud strategy using controller inputs to control open bus execution ( https://pastebin.com/uCCE3TND ) - [Apr 2016] SethBling and DotsAreCool find RLX strategy for easy scroll-less cloud ( https://pastebin.com/3a8ysX9r, https://www.youtube.com/watch?v=ZhB4VpPE1SU ) - [Apr 2016] SethBling finds RLX credits warp route requiring multitap ( https://www.youtube.com/watch?v=v2CDVFK40hs ) - [Apr 2016] SethBling finds non-multitap RLX credits warp route ( https://www.twitch.tv/videos/61486103 ) - [Jul 2016] FURiOUS finds better route and early item swap for non-multitap RLX credits warp ( https://www.twitch.tv/videos/80938561 )
Posted: 5/26/2017 12:44 AM
Quote
Patashu
He/Him
Joined: 10/2/2005
Posts: 4043
For pokemon RBY and GSC, the pokemon glitch forum 'Glitch City Laboratories' ( https://forums.glitchcity.info/ ) and youtubers like TheZZAZZGlitch ( https://www.youtube.com/user/TheZZAZZGlitch ) have extensive documentation of pokemon glitches and arbitrary code execution methods. Pokemon RBY is probably the biggest hotbed for ACE. Besides having a ridiculous number of ways to reach ACE in general, it has one of the easiest ACE methods to perform in real time on real hardware, with the '8F' item - using input like taking steps on the overworld, arranging items in boxes, etc. code can easily be written and executed. I don't have a timeline of ACE history in Pokemon RBY, but these are the places you'll want to start looking.
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu My twitch. I stream mostly shmups & rhythm games http://twitch.tv/patashu My youtube, again shmups and rhythm games and misc stuff: http://youtube.com/user/patashu
Posted: 5/26/2017 5:29 PM
Quote
BigBoct
He/Him
Editor, Former player
Joined: 8/9/2007
Posts: 1692
Location: Tiffin/Republic, OH
[2187] GBC Pokémon: Yellow Version "arbitrary code execution" by bortreb in 12:51.87 was the first ACE submission here.
Previous Name: boct1584
Posted: 5/26/2017 6:20 PM
Quote
feos
Site Admin, Skilled player (1254)
Joined: 4/17/2010
Posts: 11475
Location: Lake Char­gogg­a­gogg­man­chaugg­a­gogg­chau­bun­a­gung­a­maugg
NES TAS of 2011
boct1584 wrote:
[2187] GBC Pokémon: Yellow Version "arbitrary code execution" by bortreb in 12:51.87 was the first ACE submission here.
It wasn't. See my post.
Warning: When making decisions, I try to collect as much data as possible before actually deciding. I try to abstract away and see the principles behind real world events and people's opinions. I try to generalize them and turn into something clear and reusable. I hate depending on unpredictable and having to make lottery guesses. Any problem can be solved by systems thinking and acting.
Posted: 5/26/2017 7:43 PM
Quote
BigBoct
He/Him
Editor, Former player
Joined: 8/9/2007
Posts: 1692
Location: Tiffin/Republic, OH
feos wrote:
boct1584 wrote:
[2187] GBC Pokémon: Yellow Version "arbitrary code execution" by bortreb in 12:51.87 was the first ACE submission here.
It wasn't. See my post.
Let me rephrase, then. I think bortreb's movie was the one to really introduce the concept of ACE to the community.
Previous Name: boct1584
Posted: 5/26/2017 9:04 PM
Quote
p4wn3r
Player (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Lucky TAS of 2011 Gameboy TAS of 2011
I can only speak about Pokémon RBY code execution, I am not familiar with how it is done in SMW. Although RBY is considered a very buggy game today, it was not so many years ago. Just for example, the glitch that allows you to catch Mew was only publicly disclosed in 2003, when people were already playing the Gen 3 games. Today things happen much faster because of the Internet. Anyway, for a long time, glitches related to RBY were pretty minor, and completely useless to speedrunning, so people did not bother to look for ACE. One person who was really important in reversing the game's internals was hanzou. He found a lot of gameshark codes for the game and documented pretty much every glitch found at the time, he was probably the person who understood the game best in the pre-TAS era (in the west, at least, I don't know about players in Japan). The discovery that really made Pokemon RBY an interesting TAS was the Lvl 1-100. Having an overleveled Pokemon just after the first gym pretty much destroyed the game, and improved glitchless runs by a large margin. It was from that point on that people started fuzzing with the game to look for glitches with speedrunning in mind. It was when the Safari Zone walk-through-walls was discovered, the Brock badge skip, etc. Things started to go out of control with the ZZAZZ glitch, which was the first to corrupt the terminator of the inventory list, which is the classic way to get ACE in RBY. If I recall correctly, it was also hanzou, that found out how to warp to the Hall of Fame using ZZAZZ, most probably from his knowledge of creating gameshark codes. This was the first instance where people used a corrupted inventory to edit the memory of the game and I remembered it blew my mind when I first saw it. Then, came the save corruption glitch and the extremely short RBY runs (it was also the time when people started whining about glitchy TASes). From that point all that mattered was to understand how the data in the game was stored and try to find the fastest way to overwrite it. Eventually it was found out how to trick the game into calling any function, and because the game boy is a primitive device, with no security at all, it was pretty obvious that arbitrary code execution was possible.
Posted: 5/27/2017 2:29 AM
Quote
jlun2
Skilled player (1741)
Joined: 9/17/2009
Posts: 4981
Location: ̶C̶a̶n̶a̶d̶a̶ "Kanatah"
GBA TASer of 2010
Well, there's a (most likely incomplete) list of games here that can do that. And rather obscure, but since the wii exploits were technically arbitrary code execution, someone also tried submitting that for April Fools in 2012: #3515: RachelB's Wii The Legend of Zelda: Twilight Princess "glitched" in 00:22.65 Not sure if that counted.
LLCoolDave wrote:
This seems to be competing for the "Worst looking TAS of 2011" Award.
Posted: 5/27/2017 7:32 AM
Quote
thatguy
Editor
Joined: 11/3/2013
Posts: 506
To clarify: Masterjun's SMW movie was the first to use arbitrary code execution to complete a game, although before that there were a great many TASes that completed games very quickly through wrong-warping to the end and similar techniques, (eg the original Pokemon Yellow save corruption movie). Bobtreb's Pokemon Yellow movie was the first to go one stage further, to use arbitrary code execution to do something the game couldn't otherwise do by itself. Masterjun's movie had mastered the technical detail of how to hijack a video game; Bobrteb's was the first to establish the broader implications that ACE could be used to do literally anything the hardware could handle.
Posted: 5/31/2017 11:18 AM
Quote
DeathInABottle
He/Him
Joined: 5/25/2017
Posts: 2
Location: Canada
Thanks a lot! I'd found some of this already, but other bits are new. Really helpful.
Posted: 5/31/2017 11:33 AM
Quote
Mitjitsu
He/Him
Banned User
Joined: 4/24/2006
Posts: 2997
TAS of 2007 N64 TAS of 2007
Donkey Kong Country is probably the earliest example of Arbitrary Code Execution. In terms of wrong warping between levels 1 and 2. A of people including me accidentally stumbled across it back then.