Arbitrary Code Execution in Doom?

In the realm of TASing there is this concept called "arbitrary code execution". It means using the player's input in a way that re-programs the game from the inside out. It is often achieved in games via severe glitches. When a glitch causes a game to read instructions from an unexpected memory address, the player has an opportunity to arrange it so that those instructions have a specific effect instead of a random crash. In many console games this has allowed TASers to perform an instant jump to the ending credits. In the most extreme case, the player can re-program the whole game into anything he likes just by using the player input.

Here is an example of a TAS that executes arbitrary code. Only the game controller input is required to achieve this: https://www.youtube.com/watch?v=JxgEXDnXD6M

(More examples here: http://tasvideos.org/Movies-C3050Y.html)

The question is: Can this be done in Doom?

I know that there are many different ways to crash Doom, but I don't know how Doom behaves in those situations. Maybe the game state can be arranged in a peculiar way, so that the game doesn't crash, but causes an unexpected code execution instead?

To give a more specific idea, here is a completely hypothetical example: Play some map of Doom and arrange some overflow glitches or other potential data corrupting errors. Then press the exit switch. If the game data is corrupted in a specific way, the level number might be something else than it should be. The player might warp into a wrong level. Or maybe due to overflows and other errors some level data is unexpectedly read from a wrong memory address that has monster data: monster coordinates, monster hit points, etc. In an Einsteinian whim of clever autism, the player has damaged three imps by 10, 5 and 5 hit points respectively and killed two demons at coordinates {56, 22} and {56, 23} thus constructing the game memory so that when level data is glitchedly read from those monsters' addresses and some meaningful string of code is executed. Another hypothetical method is to void glide out of bounds and use the player coordinates to cause overflows and errors that reconstruct the game memory so that arbitrary code execution becomes possible. Actually, any unexpected glitch would be a funny thing to achieve. Maybe just overflow the memory so that something mildly interesting happens? This is highly hypothetical and I have very little experience on stuff like this, so it would be interesting to hear any insights from people who know something about how doom code behaves.

Given how the Doom engine is practically free of any sort of bounds checking, I'm almost positive that you could do arbitrary code execution with a PWAD. With player inputs in the standard IWAD, though? I'm not so sure.

Offhand, seems like the best bet would be exploiting the http://doomwiki.org/wiki/External_control_driver probably.

Most of the exploits described sound "just" like clever/deliberate data corruption, not like what is commonly accepted as arbitrary code execution (which would need to be platform-specific, and somehow cause the engine to execute valid but "noncanon" code).

The "easiest" way to inject executable code in the Doom's engine, intended as a sequence of meaningful machine code instructions, would be to have a solid data structure like e.g. an unmasked texture, flat or patch consist of x86 code, and then try to trick the engine into actually executing it (kinda like how buffer overflow attacks are carried out).

Now, with certain kinds of bad data it's possible to have e.g. runaway patch drawing, but it's much harder to alter the PC (program counter) or the actual functions' code, due to how data is arranged in memory (first executable code, then data). Maybe by causing a write to a precise code address...and then, the exploit would be not only platform-specific, but also machine-specific, and even then it wouldn't always be repeatable (e.g. let's say that you manage to cause a flat drawing to overwrite part of the flat drawing function itself, and from then on the sky is the limit. It might only work if you can find the function's address exactly, and know exactly which instructions to change).

An easier approach (perhaps) would be to "attack" the various codepointer attributes of the mobj_t or even the player_t objects: again, if you manage to overwrite even a single of those pointers with a "catch all" function that gives you control, then you might have something on your hands.

I mentioned drawing functions because they are the only kind of data that can be interpreted as a kind of primitive imperative language (essentially it's a sequence of "draw pixel" or "skip N pixels" instructions, terminated by an "end patch/texture column" instruction. However the "skip N pixels instruction" is very limited, having a "range" of 8 bits, not nearly enough to access the executable code's position in memory. But maybe there are more exploitable attacks.

A known way to induce runaway patch drawing is drawing masked textures on a 1-sided linedef (it "ignores" patch offset/skipinstructions, drawing literally everything it finds in memory), the Medusa effect (that one can actually run away), etc.

Somewhat unrelated, but isn't it true that it's possible to introduce computer viruses via PWADs? I seem to recall reading that certain source ports went out of their way to alter engine behavior that allowed viral WADs to be booted into vanilla Doom.

^ Never heard of anything like that before.

The closest would be that some ports check map structures more thorougly and apply some "sanitation" rather than mindlessly loading them to memory -especially advanced ports which are less tolerant of badly constructed blockmaps, reject tables, stray linedefs etc., going even as far as rebuilding the nodes. But it has nothing to do with computer viruses.

That beind said, you can certainly store any kind of data as a PWAD lump, is you're so inclined, but by itself, it won't be a threat to the game (though it might trigger antivirus software, e.g. if I use the code of a virus as texture data because I find it pretty. Fairly innocuous if just displayed, but anti-virus software will not like it anyway).

A far more believable threat would be using social engineering to "convince" a gullible user to use an editor to save a lump from the PWAD to disk, rename it to "imstupid.exe" and click on it ;-)

Megamur said:

Somewhat unrelated, but isn't it true that it's possible to introduce computer viruses via PWADs? I seem to recall reading that certain source ports went out of their way to alter engine behavior that allowed viral WADs to be booted into vanilla Doom.

Sounds like bullshit. Since each source port's code is laid out differently, an attack on one would probably do nothing on the others, or crash at worst.

In particular, you wouldn't have much luck with a DOS virus on a modern Windows system.

Now I recall reading some Doom creepypasta about a "PWAD which could delete files" or do other nasty stuff to a user's computer, like "reducing it to DOS" or "making it run faster". It was so potent, that even opening the ZIP file it came in could do stuff like e.g. turning the screen red and writing a file to the C:\ folder against the user's will.

All of that of course before the unlucky Doomed (pun intended) user met his (real-life) demise....

Yup, that sounds more like creepypasta ;-)

Aqfaq said:

I know that there are many different ways to crash Doom, but I don't know how Doom behaves in those situations.

Surprisingly for a DOS game, Doom has relatively good "exception handling", in the sense that in most cases it will shut itself off and exit (relatively) gracefully if it encounter certain errors (e.g. visplane overflow is actually a handled exception, not a crash!). There are more controlled exits than crashes. In fact, uncontrolled crashes are quite rare, and many of them are also easy to attribute to a cause, e.g. division by zero.

Well, now I'm going to be wondering where I read that....

Megamur said:

Well, now I'm going to be wondering where I read that....

Probably where you read that if you don't stop doing certain shameful things, your palms will grow hairy and/or you'll go blind ;-)

Graf Zahl said:

Sounds like bullshit. Since each source port's code is laid out differently, an attack on one would probably do nothing on the others, or crash at worst.

Well, this practice may work to detect and report security issues in source ports.

By the way, here is a detailed explanation of ACE (Arbitrary Code Execution) in Super Mario World: https://www.youtube.com/watch?v=vAHXK2wut_I

If ACE is ever achieved in Doom, somebody should code a functioning Asteroids game into the map screen just by playing Doom.

Well, in theory you can already execute arbitrary code in Boom. If you have the patience to fucking code it.

Megamur said:

Somewhat unrelated, but isn't it true that it's possible to introduce computer viruses via PWADs?

It would have been possible if certain plans had not been changed early. In the Doom alpha they used a data lump to contain x86 code for how to draw the HUD view...

But maybe it's still possible, if this arbitrary execution thing can work. I eagerly await for someone to make it work and then for everybody to clamor for source ports to support this severe security risk because it's a vanilla feature. :p

Maes said:

Well, in theory you can already execute arbitrary code in Boom. If you have the patience to fucking code it.

I have unfinished wadc library to make large boom conveyor logic manageable. I've been inspired to pick that back up after seeing "going down".

Maes said:

It was so potent, that even opening the ZIP file it came in could do stuff like e.g. turning the screen red and writing a file to the C:\ folder against the user's will.

Sounds like an ANSI bomb to me. It is possible to include such a thing in the ZIP's comment tag, too. The PWAD itself is not capable of printing ANSI codes, I think.

LogicDeLuxe said:

Sounds like an ANSI bomb to me. It is possible to include such a thing in the ZIP's comment tag, too. The PWAD itself is not capable of printing ANSI codes, I think.

Only that the creepypasta was about a ZDoom PWAD, and by the age and context the OS was likely Windows XP.

I'm surprised hackers haven't thought, at the very least, of a t****prank caused by arbitrary code execution. Something like launching your Calendar app or going to an arbitrary web URL.

Well, at this point, I guess we can just sit back as Linguica comes up with something also for that. Linguihacks/LinguicACE on the way?

EDIT: Now that I think about it, there was a potential for such attacks in the DOS era: mods that came with their own pre-modified doom.exe were not uncommon. How much did you trust the author to have just used DEHackED to alter it?

More rarely, sometimes there are mods that come with their own source port executables even today (plain or modified ZDoom, usually). Again, how much would you trust the executable to really be just a clean copy of ZDoom or the modifications to be benign?

What happens, if you activate 20 shootable switches simultaneously with the SSG?

With 4 players, this can be increased to 80 switches.

Then have some hitscan monsters shoot additional switches on the same frame to activate more than 100 switches simultaneously. Heck, there are probably clever map designs that could trigger any number of switches imaginable.

How many switches can Doom handle? Does it depend on what the switch does?

In fact, a shootable switch is activated even if the hitscan passes through the linedef, it doesn't need to land on it - so that a theoretically infinite number of switches can be activated by a single hitscan!

In practice, vanilla triggers a Spechits overflow already at 8 simultaneously triggered linedef actions (I see no reason why shootable switches wouldn't count to this), and an Intercept overflow whenever a hitscan simply passes through more than 128 linedefs. Both result in undefined behaviour.

TimeOfDeath's intercepts overflow exploits this to create an all-ghost bug and then uses it deliberately in the map's gimmicky gameplay.

Any port with the BOOM DeHackEd/BEX parser is likely to be highly vulnerable via provision of malformed DEHACKED lumps, because it uses a large number of insecure ANSI C library functions on fixed-length buffers without sufficient defensive programming practices.

Just an idea for an attack vector against modern ports. Platforms with DEP provide an extra challenge, however.

Malformed ACS may get you places on some ports, especially earlier versions of them that are using the original Hexen interpreter code. It has a near-tragedy-level lacking of bounds/sanity checking and provides access to a large number of opcode commands that could be manipulated to write or read unintended locations.

Aqfaq said:

How many switches can Doom handle? Does it depend on what the switch does?

If you have more than 16* repeatable switches pressed down simultaneously, the game will exit with

P_StartButton: no button slots left!

This is pretty hard to do with players but quite easily achieved with lots of type 46 GR open door specials, and chaingunners. However it's not really exploitable because the game bothers to range-check for it (hence the specific error message).
____
* 4 switches by 4 players, according to some comment somewhere

Doom's codebase is certainly riddled with errors and overflows, the vast majority of them, however, is asymptomatic (e.g. I discovered a tan table overflow into the sin/cos tables only with Mocha, and was forced to emulate it).

All those years, nobody has demonstrated a successful ACE attack on the engine. I guess that an important reason for that is that most overflows occur in the "data region" of memory, which is well isolated from the code. Doom has relatively little static data which could get overwritten during an overflow condiion. Even overflowing spechits, sprites, visplanes etc. at most results in a read of bogus data, which however never results in it being interpreted as x86 machine code, at most in graphical glitches or engine misbehavior.

The only weak point I can recall on the top of my head, is when starting a map or loading a savegame: in P_SpawnMapThing, it's possible, if a thing is marked with a zero or negative number, to cause a write below the global playerstarts array because of the lack of bound checking.

In theory, since a short is used for the mthing->type variable (playerstarts[mthing->type-1]), this gives a "range" of up to -32K bytes. I don't know if that's enough to overwrite actual executable code in vanilla, but it's possible to use this mechanism with a maliciously crafted PWAD or altered savegame. Whether it's usable to write actual executable code in a reliable way, that's another matter.

If we can restrict the discussion to DOS, it should be a lot simpler to achieve there. It wouldn't object to being asked to execute code out of the data segment, for one thing, if you found a way to trigger that.

Also I should note there is at least one overflow that can overwrite almost the entire BSS segment of the program, and that's the spanstart[] overflow that can be triggered by being very close to a too-tall dropoff. Unfortunately it competes with several other possible errors caused under the same conditions and it would take a monsterous analysis of the precise behavior of the renderer to find the exact condition where the loop in R_MakeSpans will break w/o a prior R_DrawColumn error triggering.

Quasar said:

If we can restrict the discussion to DOS, it should be a lot simpler to achieve there. It wouldn't object to being asked to execute code out of the data segment, for one thing, if you found a way to trigger that.

It would somehow require to inject a JMP or similar instruction inside a subroutine that gets called often, or even right inside the body of the caller (e.g. in the P_SpawnMapThing example, it should be able to point inside P_SpawnMapThing itself, and in a place that will be executed as soon as possible after the write is performed).

It might also be difficult to write more than one byte or short at a time exactly where you want it or without having to write a lot of useless garbage data along with the executable payload (even if just that one single JMP instruction). This jump should then be used to execute a more "solid" virus-like code lump, disguised e.g. as a flat or texture, which are large enough and contiguous. Essentially, I believe that only a two-stage attack is possible, if at all.

Maes said:

It would somehow require to inject a JMP or similar instruction inside a subroutine that gets called often, or even right inside the body of the caller (e.g. in the P_SpawnMapThing example, it should be able to point inside P_SpawnMapThing itself, and in a place that will be executed as soon as possible after the write is performed).

I should mention that we recently accidentally discovered that subsequent intercepts overflows that occur after the first one happens can corrupt the thinker list, by treating the mobj_t pointers that it trashed the data segment with on previous runs as line_t * type. There was a demo of it, which displayed this strange behavior - after the first intercepts overflow, everything is all-ghosts as you'd normally expect. However, the player then fires another tracer shot over the large pile of objects which triggered the intercepts overflow originally and some serious magic can be seen to happen right before the game crashes - some of the mobj_t's that were shot change positions and, most importantly for our discussion here, they change *states* and start to display other things' sprites (one changes into an imp for example).

Keep in mind that A. every thinker contains a think_t function pointer to the function to call for its next thinking turn, and in addition, B., every state contains an action function. If you can corrupt thinkers and mobj_t's, then it *might* be possible to carefully manipulate consecutive intercepts overflows to hook your own routine into the thinker list.

Hmm...that does seem to have some logic.

OK, so the intercepts_t struct looks like this:

typedef struct
{
    fixed_t	frac;		// along trace line
    boolean	isaline;
    union {
	mobj_t*	thing;
	line_t*	line;
    }			d;
} intercept_t;

typedef struct mobj_s
{

    thinker_t           thinker;
    fixed_t             x;
    fixed_t             y;
    fixed_t             z;
...
    [omissis]
...
}

typedef struct thinker_s
{
	struct		thinker_s	*prev, *next;
	think_t		function;
} thinker_t;

//
// P_InterceptVector
// Returns the fractional intercept point
// along the first divline.
// This is only called by the addthings
// and addlines traversers.
//
fixed_t
P_InterceptVector
( divline_t*	v2,
  divline_t*	v1 )
{
#if 1
    fixed_t	frac;
    fixed_t	num;
    fixed_t	den;
	
    den = FixedMul (v1->dy>>8,v2->dx) - FixedMul(v1->dx>>8,v2->dy);

    if (den == 0)
	return 0;
    //	I_Error ("P_InterceptVector: parallel");
    
    num =
	FixedMul ( (v1->x - v2->x)>>8 ,v1->dy )
	+FixedMul ( (v2->y - v1->y)>>8, v1->dx );

    frac = FixedDiv (num , den);

    return frac;
}

Maes said:

However, if I was a hacker motivated to make Doomers' lives more miserable by such means, I sure would wish for an easier method ;-)

Well, the bad guys back then opted for including some malicious com files in their install.bat
There are probably some examples preserved on shovelware CDs.

There's also the infamous Taipan.666 virus, which I have once seen on a very crappy shovelware CD with mostly broken zip files. The virus included some Doom related scare message.

All of the structures as generated by Watcom have no padding; "0-byte alignment" if you will. So there's no chance that in->frac with overlap with thinker_t::think, in other words - the offset in both structures is 8 bytes in. PS: "boolean" is an enum and all enums are 32-bit under Watcom, just to remove that from the equation. None of this however explains the magic behaviors in that demo, so perhaps something else goes on that we're not immediately considering.

Quasar said:

All of the structures as generated by Watcom have no padding; "0-byte alignment" if you will.

Well, that's what I assumed too when guessing the struct sizes in memory. And yes, I also assumed that boolean has the same size as integer (32-bit), hence why I said that the intersect_t struct has a sizeof() 12 (fixed_t (4 bytes), boolean (4 bytes), union of pointers (4 bytes), no padding), same as the thinker_t struct (3 pointers x 4 bytes.

Quasar said:

So there's no chance that in->frac with overlap with thinker_t::think, in other words - the offset in both structures is 8 bytes in.

Exactly which fields will overlap depends on the difference between addresses. E.g. if the intercepts list begins at address 120 (decimal, chosen so that it evenly divides with 12) and contains let's say just 5 elements, tops, and thus will be 60 bytes long, so it ends at address 179.

Let's say that the very first mobj_t happens to be at address 180, immediately after. 180-120 = 60 and 60%12 =0 so the two objects are in a "0 modulo 12 mutual alignment". If there was some other data between them (e.g. an integer, 4 bytes) then they would be at a "4 modulo 12" alignment, and so on.

Now, depending on how many intercepts overflow one gets, and how far away the very first mobj_t is from the end of the list, one may get no overwrite at all, only a partial overwrite (which may not even include all of the first 12 bytes of the mobj_t), or a complete overlap of that particular mobj_t. However, since mobj_t's are allocated by using Z_Malloc, there's no guarantee that the next mobj_t will be continuous with the first (and I don't know what their size_t is, either), so let's just assume that all hacking must work with that one first encountered mobj_t, and none else.

For an intercept_t.frac field to overlap with thinker, there must be an overflow of at least two intercepts (or more, depends on how far away the first mobj_t is), and the first mobj_t must be positioned so that the second intercept begins where the thinker_t pointer should be. But yeah, if they are really contiguous in memory, then the first intercept cannot overwrite the first mobj_t's thinker_t function with its frac field. I don't know how viable it would be to overflow/overwrite a second, a third etc. mobj_t, and whether (sizeof(mobj_t)%12==0).

If it IS, and all mobj_t's are contiguous in memory, then yeah, a frac -> thinker overwrite can never happen. However, if their sizeof(mobj_t)%12==8, it might be possible at the second mobj_t, and periodically every three after that one. With sizeof(mobj_t)%12==4, it will be at the third one, and also every three after that one.

Of course, with that much overwriting, many bad things may happen that will break the engine or bomb out doom.exe way before a hacker manages to get any sort of useful control over it (assuming that the intention of ACE was to help the player cheat, or to do something within the engine not normally possible with standard commands and rules). Getting control of an engine in a borked up state which cannot even be restarted/reset, would not be very useful :-/