Exile for the BBC Micro; some elegant solutions

[Prelude: sorry, this has nothing to do with security whatsoever. Feel free to bail now if you're not interested in a classic 1980's game, and rest assured that non-security posts to this blog will remain extremely rare.]

The BBC Micro game Exile, released in 1988, has a realistic claim for the best game ever. I lost months of my youth to this game. I also lost a fair few days recently re-playing the game under emulation in 2014!

What the authors were able to do with just 32KB (for everything, including video RAM) was amazing. The art of coding in this way has simply been lost. The game features:

• An enormous map featuring fairly open-ended exploration.
• A full physics engine (gravity, momentum, conservation of momentum, buoyancy, friction).
• Dozens of fiendish puzzles, characters and objects, with many interactions between entities.

There's even a great disassembly online. I was quite surprised to see that the game really is powered by real 6502 opcodes, and not unicorn tears.

The claim for "best game ever" isn't just about packing so much into such a small resource. Completing the game, even if you know what you're doing, is hours of immersive play that alternates between solving very varied puzzles and arcade-like blowing stuff up. Given how free-form the game is, there are also different solutions and orderings to to the game, so you can put your own personal spin on things.

If you want to see what all the fuss is about, the best emulator is probably B-em (part of a webring, remember those??) and the Exile game image can be readily found. And do feel free to stop reading to avoid the spoilers that now follow.

There seem to be two solutions published on the web. Unfortunately, both have triggered my OCD. Both have solutions for some of the more interesting problems that rely on abusing the limits and corner cases of the game engine, such as:

• Using the built-in viewport scrolling to sneak around with the viewport scrolled to the extreme so that an enemy or obstacle does not "see" the player.
• Abusing the fact that the physics engine "forgets" objects that are offscreen, causing corner-case and clearly unintentional behavior. (Give the poor game a break, it's trying to fit everything into 32KB!)
• Proposing solutions with low reliability.

More significantly, these problems have such beautifully elegant solutions that once you see them, it's clear that you've worked out the authors' original intent. So without further ado, here is a small collection of videos that illustrates some elegant solutions as well as an easter egg:

Getting the alien weapon

The game features a tricky-to-get alien weapon! In fact you can get it from two different places. Generally, you can feed different types of imps different "gifts" and then they might later throw you a gift in return. In this video, these cyan imps will accept a blue mushroom. Later in the game, dark blue imps accept piranhas. I had found this later exchange, but this earlier exchange was a complete surprise to me -- I only noticed it reading the disassembly referenced above.

It's a real boon to get such a powerful weapon earlier in the game. It never runs out of energy and it has good destructive power for some obstacles that are otherwise annoying. Just watch out you don't burn yourself and that you don't blow the weapon up, it's destructible.

Getting the first coronium rocks out of the alcove

There's no need to try and force the rock past the blowing bush. Speedy throwing and viewport scrolling are not necessary. There's a simple, elegant sequence that will rescue it reliably and without dubiousness.

Blowing open the rune door

The first two-thirds or so of the game are building up towards opening a very important door into the bad guy's lair. This door is blown open with a nuclear explosion between two radioactive rocks. Given the importance of the door, it's not surprising that the final puzzles towards opening it have beautiful solutions.

Both published solutions transport radioactive rocks via a route that is clearly not supposed to be an option, and the route only works on account of abusing game engine quirks. Tut tut! Here's a less hacky way of getting the required rocks, in three parts:

There's a lot going on here:

• In part #1, the use of the maggot to "wake up" the nest of green slimes is fun. Note that this doesn't always work! Game design bug? This is a very busy area of the map and the game engine often decides there's too much on-screen to spawn creatures from the nest. I lost a day stepping through 6502 assembler to understand this.
• Then, the green slimes appear attracted to sound. So we made some noise!
• The use of buoyancy to avoid the sucking bush is the first and only significant usage in a puzzle. Wonderful.
• In part #2 and #3, the presence of the big fish prevents the (very dangerous) piranhas from coming out the nest and ruining your day.
• In part #3, the piranha is actually immune to damage from acid drops -- I believe the only creature in the game that has this trait. (You can even check the disassembly :-)

Getting the mushroom immunity pill

Again, this puzzle involves blowing a door open with radioactive rocks. The published solutions suggest all sorts of hacks here, but there's a really neat solution with the "blaster" weapon that has been recently collected at this stage in the game. Previous weapons were projectile based but this one is force based and it can be used variously: at a distance to gently deviate the course of an acid drop, and then at close range to reliably launch a rock past a problem area.

Happy exploring.

Using ASAN as a protection

AddressSanitizer, or ASAN, is an excellent tool for detecting subtle memory errors at runtime in C / C++ programs. It is now a productionized option in both the clang and gcc compilers, and has assisted in uncovering literally thousands of security bugs.

ASAN works by instrumenting compiled code with careful detections for runtime errors. It is primarily a detection tool. But what if we attempted to use is as a tool for protection?

The case for using ASAN-compiled software as a protection is an interesting one. Some of the most severe vulnerabilities are memory corruptions used to completely compromise a victim's machine. This is particularly the case for a web browser. If an ASAN-compiled build can help defend against these bugs, perhaps it has value to some users? An ASAN build is slower enough that no production software is likely to ship compiled with ASAN. But the slow down is not so bad that a particularly paranoid user wouldn't be able to easily accept it on a fast machine.

With that trade-off in mind, let's explore: does ASAN actually provide protection? To answer that, let's break memory corruption down into common vulnerability classes:

1. Linear buffer overflow (heap, stack, BSS, etc.)
A linear buffer overflow is one where every byte past the end of a buffer is written in sequence, up to some end point (example). For example, a memcpy() or strcpy() based overflow is linear. Because of the way ASAN works, I believe it will always catch a linear buffer overflow. It uses a default "redzone" of at least 16 bytes, i.e. touching _any_ address within 16 bytes of a valid buffer will halt the program with an error. Under ASAN, a linear buffer overflow condition will always hit the redzone.
This is great news because linear buffer overflows are one of the more common types of security bugs, and they are quite serious, affording the attacker a lot of control in corrupting program state.

2. Non-linear buffer overflow
A non-linear buffer overflow is one where data is written at some specific (but often attacker-controlled) out-of-bounds offset relative to a buffer (example). These bugs can be extremely powerful. Unfortunately, because of their power, they are both favored by attackers and also not stopped by ASAN if the attacker knows they are targeting an ASAN build. Example C program:

int main()
{
  char* p = malloc(16);
  char* p2 = malloc(16);
  printf("p, p2: %p, %p\n", p, p2);
  p2[31] = '\0';
}

Compile it with ASAN (clang -fsanitize=address) and then run it and no error will be detected. The bad dereference "jumps over" the redzone to corrupt p2 via pointer p.

3. Use-after-free / double-free
ASAN does detect use-after-frees very reliably in the conditions that matter for current use cases: normal usage, and under fuzzing. However, if the attacker is specifically targeting an exploit against an ASAN build, they can pull tricks to still attempt the exploit. By churning the memory allocator hard (as is trivially possible with JavaScript), the condition can be hidden. Example C program:

int main()
{
   int n = 257 * 1024 * 1024;
   char* p2;
   char* p = malloc(1024);
   printf("p: %p\n", p);
   free(p);
   while (n) {
     p2 = malloc(1024);
     if (p2 == p) printf("reused!!\n");
     free(p2);
     n -= 1024;
   }
   n = 30 * 1024 * 1024;
   while (n) {
     p2 = malloc(1024);
     if (p2 == p) printf("reused!!\n");
     n -= 1024;
   }
   p[0] = 'A';
}

The bad reference is not trapped with default ASAN values. The default values can be changed such that the bad reference is trapped:

ASAN_OPTIONS=quarantine_size=4294967295 ./a.out

It's a shame that setting this value to "unlimited" may not be possible due to a probable integer truncation in parameter parsing, see how this behaves differently:

ASAN_OPTIONS=quarantine_size=4294967296 ./a.out

4. Uninitialized value
Uninitialized values are harder to categorize. The impact varies drastically depending on where the uninitialized value is a pointer or an integer. For example, for an uninitialized pointer, effects similar to "non-linear buffer overflow" might even apply. Or if the uninitialized value is a copy length then perhaps it's more similar to "linear buffer overflow".
Or, if it's an uninitialized raw function pointer, that's a bigger problem. Indirect jumps are not checked. The behavior of the following ASAN-compiled program is instructive (run it in the debugger):

void subfunc1()
{
  unsigned long long blah = 0x0000414141414141ull;
}

void subfunc2()
{
  int (*funcptr)(void);
  funcptr();
}

int main()
{
  subfunc1();
  subfunc2();
}

If the uninitialized value is a pointer to a C++ class then similar (indirect) problems apply.

5. Bad cast
The effects of a bad cast are fairly varied! Perhaps the bad cast involves mistakenly using an integer value as a pointer. In this instance, effects similar to "non-linear buffer overflow" might be achievable. Or perhaps if a pointer for a C++ object is expected, but it is mistaken with a pointer to a raw buffer, then a bad vtable gets used, leading to program flow subversion. One final C++ example to illustrate this. Run under ASAN to observe a raw crash trying to read a vtable entry from 0x0000414141414141:

class A
{
public:
  long long val;
};

class B
{
public:
  virtual void vfunc() {};
};

int main()
{
  class A a;
  a.val = 0x0000414141414141ull;
  class B* pb = (class B*) &a;
  pb->vfunc();
}


Safer ASAN?
There's certainly scope for a safer variant of ASAN, specifically designed to provide safety rather than detection. It would be based on various changes:

• Change the dereference check from "is this dereference address ok?" to "is this address in bounds for this specific pointer?". This takes care of the nasty "non-linear buffer overflow" as well as some of the worst effects of bad casts. This is not an easy change.
• Initialize more variables: pointer values on the stack and heap. (This is not as easy as it sounds, particularly for the heap case, where the casting operator may become a point of action.)
• Make the quarantine size for use-after-free unlimited. This burns a lot of memory, of course, but may be acceptable if fully unused pages are returned to the system with madvise() or even a crazy remap_file_pages() trick.

Remaining risks

Of course, even a "safer ASAN" build would not be bullet-proof. Taking the specific case of an safer-ASAN compiled Chromium, there would still be additional attacks possible:

• Plug-ins. Many plug-ins are closed source and therefore cannot be replaced with ASANified versions. The safer build of Chromium would have plug-ins disabled: --disable-plugins or even at compile time.
• Native attack surfaces called by the browser. For example, what happens when the browser encounters a web font. It'll probably get passed to a system library which parses this dangerous format using native code. In extreme cases, such as older Chromium on Windows, fonts were parsed in the kernel(!). --disable-remote-fonts, probably other flags.
• Native attack surfaces triggerable by the browser. Less obviously, there can be operating system mechanisms that kick in simply because a file is downloaded or appears on disk. Anti-virus is notoriously buggy in this regard.
• The v8 JIT engine. Any logic error in the JIT engine resulting in the emission of bad opcode sequences, or sequences with buggy bounds checks, are pretty toxic.
• Pure logic vulnerabilities. UXSS vulnerabilities will remain unmitigated. In extremely rare but spectacular cases, unsandboxed code execute has been achieved without the need for memory corruption at all.

That all said, a stock ASAN build -- and even more so a hypothetical safer-ASAN build -- provide significant mitigation potential against memory corruption vulnerabilities. One measure of how strong a mitigation is, is whether is totally closes the door on a subset of bug classes or bugs. Even for the stock ASAN case, it appears that it does (linear buffer overflows for a start).

There is certainly more room for exploration in this space.