Arbitrary Code Execution in Doom?

Maes said:

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 :-/

Gotcha, most of that makes sense to me. Mobjs are not contiguous, however. They are at effectively random locations on the heap.

On your final point, you should watch some of the Pokemon ACE TASes before dismissing what you can do with a game engine that's in the process of dying a slow death from memory corruption - granted DOOM's architecture and programming don't quite permit that level of insanity, but, just for an example, some interrupts may keep running when DOOM hangs. If you could use your brief window for code execution to hook one, then you could bootstrap up something else and do regular work every time that interrupt fires from then on. Gotta get creative and remember you have the full architecture of a DOS machine - with virtually no memory protection - available.

Still, I have to admit that successful use of the intercepts overflow is a really big longshot. It's just an idea, a mental experiment if you will. Due to its potential for a range of undefined behaviors, it at least deserves to be eliminated as a candidate thoroughly ;)

Quasar said:

Gotcha, most of that makes sense to me. Mobjs are not contiguous, however. They are at effectively random locations on the heap.

Yup, that's what I think too is the general case, especially when a map is in "steady state", so to speak (aka normal gameplay), with objects being spawned and dying all the time, and especially with the lump caching mechanism reclaiming and reassigning memory every now and then.

I'm not sure if only when a level is freshly loaded from disk or from a savegame, the P_SpawnMapThing function can generate contiguous objects -if nothing else uses the allocator between calls-. The very first of those objects, BTW, would be the player. Hmm....

Now that I think of it, exactly what guarantees us that any mobj_t will be the very first object allocated on the heap (or the Z-allocator's mega chunk, anyway) and always be located right after the intercepts list? On a freshly started engine maybe....but after several load/reload/end game cycles?

Edit: NM, I now re-read your original post carefully and realized you were talking about the thinker's list, which in itself is simply a thinker_t structure (thinkercap) so it can be overwritten with the same rules we already mentioned. However it's preceded by:

int leveltime;

in p_tick.c, so even if the intercepts list is right before it in memory, they will be in a 4 % 12 alignment, at least. Is there some way to see exactly where intercepts is relative to thinkercap?

Now, even if thinkercap.thinker is overwritten by a ::frac field, will it ever be executed in the same way as other thinkers? Also, any thinkers beyond thinkercap will be interspersed in memory by the allocator, and thus unreachable. However, if the alignment if 0%12 or 4%12, it may be possible to overwrite the prev or next (preferably) pointers of the thinkercap list, and thus point anywhere we want. Maybe it's not so impossible after all? O_o

Maes said:

However it's preceded by:

int leveltime;

Possible fallacy here to watch out for: global variables are not emitted in strict source code definition order by Watcom, and *do* sometimes have padding between them. You'd need to check a disassembly to verify the layout of any part of the data segment. In the case of the region near intercepts and intercept_p, this has already been done however for the sake of overflow emulation.

Maes said:

in p_tick.c, so even if the intercepts list is right before it in memory, they will be in a 4 % 12 alignment, at least. Is there some way to see exactly where intercepts is relative to thinkercap?

Now, even if thinkercap.thinker is overwritten by a ::frac field, will it ever be executed in the same way as other thinkers? Also, any thinkers beyond thinkercap will be interspersed in memory by the allocator, and thus unreachable. I really am not sure if a repeatable, reliable ACE is possible now :-/

I am not sure if we're on the same page with respect to the mechanism that's at work here. When intercepts are written during the first overflow, they spray the data segment nearby with mobj_t * and line_t * values. I would suggest that some of these being written into other nearby global pointer variables (intercept_p in particular) are the mechanism for corruption.

You seem to be assuming that intercepts[] is anywhere close to the heap. That's false. intercepts[] is a static array and intercept_t structures are never dynamically allocated. The intercept_p pointer is a static global which is supposed to range from &intercepts[0] to &intercepts[MAXINTERCEPTS-1] - but there is no range checking on it so it will walk past the end of intercepts[] and stomp unrelated memory. However the game engine later depends on intercept_p to be pointing inside the intercepts[] array when deciding what to do with intercepts that were collected. Since it itself can be overwritten by an intercepts overflow, it may contain a pointer to a line_t or mobj_t instead of a pointer to an intercept_t.

I believe this is when the corruption occurs.

Quasar said:

You seem to be assuming that intercepts[] is anywhere close to the heap. That's false. intercepts[] is a static array and intercept_t structures are never dynamically allocated. The intercept_p pointer is a static global which is supposed to range from &intercepts[0] to &intercepts[MAXINTERCEPTS-1]

Well, if the pointer can go beyond the range of the intercepts[] array, eventually it will venture into the heap, if the overflow is large enough, but I thought that it was somewhat close.

Well, if it's not the heap that will be overwritten first, it will be other static data structures first, then. What's RIGHT AFTER intercepts[MAXINTERCEPTS-1]?

Quasar said:

Since it itself [intercept_p] can be overwritten by an intercepts overflow, it may contain a pointer to a line_t or mobj_t instead of a pointer to an intercept_t.

Ah OK, now I got it. So, the intercept_p pointer is right after the intercept[] array? If so, overwriting it with an intercepts_t struct will result in the intercept_t::frac value replacing it.

So in order for the hack to work:

• The player must cause an intercepts overflow so that the frac value generated is a valid pointer to some specially crafted data.
  
• This data will then be interpreted as an array of intercepts_t structs by the engine.
  
• The "intercepts::thing" field of at least one of these strucs must point to some specially crafted mobj_t (which, by definition, cannot belong to the "official" thinker list...yet), whose ::thinker::thinker field contains our ACE payload.
  
• Somehow, that thinker's code must be executed for our ACE hack to work.
  

However, any intercepted/interceptable line or thing is used in the various Traverse functions. In order for arbitrary code to function, that thinker must be somehow linked into the thinker list or the thinker function must be otherwise invoked.

I dunno, seems like all the planets must line up for this chain of events to result in controlled ACE, and the corrupted intercept_p pointer could be pointing anywhere in memory, really, due to it being overwritten by the intercept_t::frac value. O_o

This array from choco doom is the layout of memory after the intercepts[] array in the particular version of Doom that entryway reverse-engineered for emulation purposes in PrBoom-Plus. Comments are mine.

static intercepts_overrun_t intercepts_overrun[] =
{
    {4,   NULL,                          false}, // This is compiler padding 
    {4,   NULL, /* &earlyout, */         false},
    {4,   NULL, /* &intercept_p, */      false},
    {4,   &lowfloor,                     false},
    {4,   &openbottom,                   false},
    {4,   &opentop,                      false},
    {4,   &openrange,                    false},
    {4,   NULL,                          false}, // unknown, or padding?
    {120, NULL, /* &activeplats, */      false},
    {8,   NULL,                          false}, // ditto
    {4,   &bulletslope,                  false},
    {4,   NULL, /* &swingx, */           false},
    {4,   NULL, /* &swingy, */           false},
    {4,   NULL,                          false}, // ditto
    {40,  &playerstarts,                 true},
    {4,   NULL, /* &blocklinks, */       false},
    {4,   &bmapwidth,                    false},
    {4,   NULL, /* &blockmap, */         false},
    {4,   &bmaporgx,                     false},
    {4,   &bmaporgy,                     false},
    {4,   NULL, /* &blockmaplump, */     false},
    {4,   &bmapheight,                   false},// layout not considered from here on
    {0,   NULL,                          false}, 
};

Is that blockmap stuff near the bottom where the all ghosts bug comes from?

Linguica said:

Is that blockmap stuff near the bottom where the all ghosts bug comes from?

Would make sense. That requires a pretty significant overflow to reach, however, given the 120 byte activeplats array that's in the way.

If the blockmap origins are borked, it's probable.

In any case, none of these variables would easily lead to the kind of controlled ACE we're looking.

Perhaps the "cleanest" way would be, during the very first intercepts overflow which overwrites the intercept_p pointer, to set up the interception so that the frac field contains a pointer into the body of a commonly called function, where it's safe to inject a JMP instruction.

This way, the next intercept will be written inside that function. That next intercept, must contain a frac value such that it is a valid x86 instruction, but it must be able to jump directly to our code payload. I don't know if that's possible with a single 32-bit instruction, certainly not to an absolute 32-bit address. Maybe if the parameter of an existing JMP instruction is altered...