Introduction#

Logical Stones is a freeware puzzle game made by Tibor Neszt and his team back in 2006. The game is similar to Sokoban in many ways, but with a twist, it utilizes gravity and some additional rules. The goal of the game is to push all the stones to the exit points as fast as you can.

Problem#

Logical Stones used to work just fine in Windows 98 and Windows XP. However, it crashes upon startup in newer versions of Windows even if compatibility mode is being used. A virtual machine could have been used to workaround this issue, but I wanted to fix the root cause.

Investigation#

LgStones.exe#

First, I started to gather some information about the main game executable by using PEiD, which is a tool capable of detecting most common packers and compilers used in executable files.

It seems to be that the executable is compressed using the open source Ultimate Packer for Executables (UPX) tool which makes debugging nearly impossible. Fortunately, the tool is capable of unpacking executables as well.

PS X:\Logical_Stones> upx -d LgStones.exe
                       Ultimate Packer for eXecutables
                          Copyright (C) 1996 - 2018
UPX 3.95w       Markus Oberhumer, Laszlo Molnar & John Reiser   Aug 26th 2018

        File size         Ratio      Format      Name
   --------------------   ------   -----------   -----------
    315904 <-    147968   46.84%    win32/pe     LgStones.exe

Unpacked 1 file.

Debugging#

I started debugging the unpacked LgStones.exe with IDA Debugger. The execution immediately stopped with a common symptom of a heap corruption:

The exception happened at the end of the function located at 0x407714 while the variable v7 was being deallocated. Can you spot the mistake in the following pseudocode?

{
[...]
  v7 = (char *)malloc(v6);
  sub_403AC0(v4, v7);
  for ( i = 0; i < a3; ++i )
  {
    sscanf(v7, "%d", &v11);
    for ( ; *v7 != 32; ++v7 )
      ;
    ++v7;
    if ( v11 > 0 )
    {
      glGenTextures(1, &v10);
      v9 = v10;
      *(_DWORD *)(a2 + 4 * i) = v10;
      if ( sub_401AB8(&v12, v7, v9, 0, 0) != 1 )
      {
        free(v7);
        return 0;
      }
      v7 += v11;
    }
  }
  free(v4);
  free(v7);
  return 1;
}

TIP

The behavior is undefined if the value of ptr does not equal a value returned earlier by malloc(), calloc() or realloc().

cppreference.com

Explanation#

As you can see the variable v7 is being modified in the body of the loop which causes undefined behavior if it is not pointing to the beginning of the allocated memory block by the time the execution reaches the corresponding free statement.

Solution#

The trivial solution would have been to replace the free call with NOP instructions and just forget about the memory leak, but there was a reason I avoided using virtual machines in the first place.

Custom memory allocator#

What if we could create a custom implementation of malloc and free which is aware of this kind of misuse?

LgStonesAllocator.dll to the rescue#

Let us create an extension which can be loaded upon startup. The purpose of this dynamic library is to create proxy functions for malloc and free which can handle the mistake of the developers. The library should also redirect the original calls to malloc and free automatically.

WARNING

The following code snippet exploits the circumstances of this very specific scenario mentioned above and is by no means a generic solution.

void* block = nullptr;

void* on_misused_malloc(size_t size) {
    return block = malloc(size);
}

void on_misused_free(void* /*faulty_block*/) {
    free(block);
}

Since the game only allocates and deallocates the variable v7 once, the easiest solution is to store a pointer to the beginning of the allocated memory block and call free on this pointer instead of the one provided by the game thus preventing the undefined behavior.

The only remaining task is to redirect the original calls to the proxy functions by overwriting the memory address of the CALL instructions in question.

The following instructions need to be changed - their operands should point to the proxy functions defined in our DLL.

 Address    Code             Instruction
 --------   -----------      -------------------------
 0040778F   E8 3C3C0100      CALL <JMP.&msvcrt.malloc>  // v7 = (char *)malloc(v6);
 00407769   E8 523C0100      CALL <JMP.&msvcrt.free>    // free(v7);
 0040782B   E8 903B0100      CALL <JMP.&msvcrt.free>    // free(v7);

Inside the DLL’s entry point the above-mentioned instructions are dynamically modified:

void redirect_call_instruction(intptr_t instruction_address, intptr_t proxy_address) {
    LPVOID operand_address = reinterpret_cast<LPVOID>(instruction_address + sizeof(uint8_t));

    DWORD old_protect;
    VirtualProtect(operand_address, sizeof(intptr_t), PAGE_EXECUTE_READWRITE, &old_protect);

    intptr_t relative_offset = proxy_address - instruction_address - 5;
    memcpy(operand_address, &relative_offset, sizeof(LPVOID));

    VirtualProtect(operand_address, sizeof(intptr_t), old_protect, nullptr);

    FlushInstructionCache(GetCurrentProcess(), operand_address, sizeof(intptr_t));
}

BOOL WINAPI DllMain(HINSTANCE hinstDLL, DWORD fdwReason, LPVOID lpReserved) {
    if (fdwReason == DLL_PROCESS_ATTACH) {
        redirect_call_instruction(0x0040778F, reinterpret_cast<intptr_t>(on_misused_malloc));
        redirect_call_instruction(0x00407769, reinterpret_cast<intptr_t>(on_misused_free));
        redirect_call_instruction(0x0040782B, reinterpret_cast<intptr_t>(on_misused_free));
    }

    return TRUE;
}

The relative addresses of the faulty malloc and free calls are overridden by the relative addresses of our proxy functions. Explaining the whole concept is beyond the scope of this article, but if you would like to learn more about x86 hooking in general, I would recommend the following article: http://jbremer.org/x86-api-hooking-demystified/

Link LgStonesAllocator.dll to LgStones.exe#

The final step is to associate our DLL somehow with the main game executable. Since the faulty free is called right after launching the game, traditional run-time DLL injection methods would not be sufficient. By using petools I added the LgStonesAllocator.dll to LgStones.exe’s import table which loads the library automatically when it is executed.

Results#

The game successfully starts without a crash, but there seems to be another problem - its user interface supports only the 4:3 aspect ratio and is completely unusable at today’s common resolutions. The window of the game becomes full screen by default and it enforces the current resolution of your display.

In the next article, I am expanding the game with configurable resolution handling.

Downloads#

You may download and play the game, including all the fixes for free.

• LgStones.zip
  • SHA-256 ef3f082abaa20069cfd12e9869609a31333272a055b2c65a70942f8f3586b6b7

The source code for LgStonesAllocator is also available.

• LgStonesAllocator.zip
  • SHA-256 211990aaa721d6f037c436e757f4e1d029bd5f3e871a3ac583c11d01134b0933