How can I find the data structure that represents mine layout of Minesweeper in memory?
Asked Answered
L

10

94

I'm trying to learn about reverse engineering, using Minesweeper as a sample application. I've found this MSDN article on a simple WinDbg command that reveals all the mines but it is old, is not explained in any detail and really isn't what I'm looking for.

I have IDA Pro disassembler and the WinDbg debugger and I've loaded winmine.exe into both of them. Can someone provide some practical tips for either of these programs in terms of finding the location of the data structure that represents the mine field?

In WinDbg I can set breakpoints, but it is difficult for me to imagine at what point to set a breakpoint and at what memory location. Similarly, when I view the static code in IDA Pro, I'm not sure where to even begin to find the function or data structure that represents the mine field.

Are there any Reverse Engineers on Stackoverflow that can point me in the right direction?

Leopold answered 31/5, 2009 at 4:24 Comment(7)
What a great idea for an assignment for students. Its kind of like anatomy lab with minesweeper as the cat.Darlinedarling
for our international readers that might be confused, minesweeper is the american version of the happy flower finding game that ships with windows vista. microsoft.blognewschannel.com/index.php/archives/2006/09/28/…Jollenta
Happy flower finding game? O_o Political correctness have gone too far.Impurity
Well, the minesweeper version is the default at least in the Swedish version of Vista. I suppose they default to the happy-flowers version in places where mines actually to tend to blow children to pieces.Monzon
So ... just clicking on some random squares to see if they are mines isn't helpful for this, huh?Superstructure
@Smandoli: that would translate to writing bits to random places in memory to see if you activate a mine in the game. OS security model allowing, this seems like a definite way to lose a leg.Margarine
Wow! Playing minesweeper through the code, using back-door handles instead of the UI ... I wonder if hackers play their games that way ever.Superstructure
K
125

Part 1 of 3


If you are serious into reverse engineering - forget about trainers and cheat engines.

Good reverse engineer should first get to know OS, core API functions, program general structure (what is run loop, windows structures, event handling routines), file format (PE). Petzold's classics "Programming Windows" can help (www.amazon.com/exec/obidos/ISBN=157231995X) as well as online MSDN.

First you should think about where minefield initialization routine can be called. I thought of following:

  • When you launch the game
  • When you click happy face
  • When you click Game->New or press F2
  • When you change level difficulty

I decided to check out F2 accelerator command.

To find accelerator handling code you are to find window message handling procedure (WndProc). It can be traced down by CreateWindowEx and RegisterClass calls.

To read:

Open up IDA, Imports window, find "CreateWindow*", jump to it and use "Jump xref to operand (X)" command to see where it is called. There should be just one call.

Now look above for RegisterClass function and it's parameter WndClass.lpfnWndProc. I already named function mainWndProc in my case.

.text:0100225D                 mov     [ebp+WndClass.lpfnWndProc], offset mainWndProc
.text:01002264                 mov     [ebp+WndClass.cbClsExtra], edi
.text:01002267                 mov     [ebp+WndClass.cbWndExtra], edi
.text:0100226A                 mov     [ebp+WndClass.hInstance], ecx
.text:0100226D                 mov     [ebp+WndClass.hIcon], eax

.text:01002292                 call    ds:RegisterClassW

Hit Enter on function name (use 'N' to rename it to something better)

Now take a look at

.text:01001BCF                 mov     edx, [ebp+Msg]

This is message id, which in case of F2 button press should contain WM_COMMAND value. You are to find where it is compared to 111h. It can be done either by tracing down edx in IDA or by setting conditional breakpoint in WinDbg and pressing F2 in the game.

Either way leads to something like

.text:01001D5B                 sub     eax, 111h
.text:01001D60                 jz      short loc_1001DBC

Right click on 111h and use "Symbolic constant" -> "Use standard symbolic constant", type WM_ and Enter. You should now have

.text:01001D5B                 sub     eax, WM_COMMAND
.text:01001D60                 jz      short loc_1001DBC

It is an easy way to find out message id values.

To understand accelerator handling check out:

It's quite a lot of text for a single answer. If you are interested I can write another couple of posts. Long story short minefield stored as an array of bytes [24x36], 0x0F shows that byte is not used (playing smaller field), 0x10 - empty field, 0x80 - mine.

Part 2 of 3


Ok, let's go on with F2 button.

According to Using Keyboard Accelerators when F2 button is pressed wndProc function

... receives a WM_COMMAND or WM_SYSCOMMAND message. The low-order word of the wParam parameter contains the identifier of the accelerator.

Ok, we already found where WM_COMMAND is processed, but how to determine corresponding wParam parameter value? This is where Resource hacker comes into play. Feed it with binary and it shows you everything. Like accelerators table for me.

alt text http://files.getdropbox.com/u/1478671/2009-07-29_161532.jpg

You can see here, that F2 button corresponds to 510 in wParam.

Now let's get back to code, that handles WM_COMMAND. It compares wParam with different constants.

.text:01001DBC HandleWM_COMMAND:                       ; CODE XREF: mainWndProc+197j
.text:01001DBC                 movzx   eax, word ptr [ebp+wParam]
.text:01001DC0                 mov     ecx, 210h
.text:01001DC5                 cmp     eax, ecx
.text:01001DC7                 jg      loc_1001EDC
.text:01001DC7
.text:01001DCD                 jz      loc_1001ED2
.text:01001DCD
.text:01001DD3                 cmp     eax, 1FEh
.text:01001DD8                 jz      loc_1001EC8

Use context menu or 'H' keyboard shortcut to display decimal values and you can see our jump

.text:01001DBC HandleWM_COMMAND:                       ; CODE XREF: mainWndProc+197j
.text:01001DBC                 movzx   eax, word ptr [ebp+wParam]
.text:01001DC0                 mov     ecx, 528
.text:01001DC5                 cmp     eax, ecx
.text:01001DC7                 jg      loc_1001EDC
.text:01001DC7
.text:01001DCD                 jz      loc_1001ED2
.text:01001DCD
.text:01001DD3                 cmp     eax, 510
.text:01001DD8                 jz      loc_1001EC8 ; here is our jump

It leads to code chunk that calls some proc and exits wndProc.

.text:01001EC8 loc_1001EC8:                            ; CODE XREF: mainWndProc+20Fj
.text:01001EC8                 call    sub_100367A     ; startNewGame ?
.text:01001EC8
.text:01001ECD                 jmp     callDefAndExit  ; default

Is that the function that initiates new game? Find that out in the last part! Stay tuned.

Part 3 of 3

Let's take a look at the first part of that function

.text:0100367A sub_100367A     proc near               ; CODE XREF: sub_100140C+CAp
.text:0100367A                                         ; sub_1001B49+33j ...
.text:0100367A                 mov     eax, dword_10056AC
.text:0100367F                 mov     ecx, uValue
.text:01003685                 push    ebx
.text:01003686                 push    esi
.text:01003687                 push    edi
.text:01003688                 xor     edi, edi
.text:0100368A                 cmp     eax, dword_1005334
.text:01003690                 mov     dword_1005164, edi
.text:01003696                 jnz     short loc_10036A4
.text:01003696
.text:01003698                 cmp     ecx, dword_1005338
.text:0100369E                 jnz     short loc_10036A4

There are two values (dword_10056AC, uValue) read into registers eax and ecx and compared to another two values (dword_1005164, dword_1005338).

Take a look at actual values using WinDBG ('bp 01003696'; on break 'p eax; p ecx') - they seemed like minefield dimensions for me. Playing with custom minefield size showed that first pair are new dimensions and second - current dimensions. Let's set new names.

.text:0100367A startNewGame    proc near               ; CODE XREF: handleButtonPress+CAp
.text:0100367A                                         ; sub_1001B49+33j ...
.text:0100367A                 mov     eax, newMineFieldWidth
.text:0100367F                 mov     ecx, newMineFieldHeight
.text:01003685                 push    ebx
.text:01003686                 push    esi
.text:01003687                 push    edi
.text:01003688                 xor     edi, edi
.text:0100368A                 cmp     eax, currentMineFieldWidth
.text:01003690                 mov     dword_1005164, edi
.text:01003696                 jnz     short loc_10036A4
.text:01003696
.text:01003698                 cmp     ecx, currentMineFieldHeight
.text:0100369E                 jnz     short loc_10036A4

A little bit later new values overwrite current and subroutine is called

.text:010036A7                 mov     currentMineFieldWidth, eax
.text:010036AC                 mov     currentMineFieldHeight, ecx
.text:010036B2                 call    sub_1002ED5

And when I saw it

.text:01002ED5 sub_1002ED5     proc near               ; CODE XREF: sub_1002B14:loc_1002B1Ep
.text:01002ED5                                         ; sub_100367A+38p
.text:01002ED5                 mov     eax, 360h
.text:01002ED5
.text:01002EDA
.text:01002EDA loc_1002EDA:                            ; CODE XREF: sub_1002ED5+Dj
.text:01002EDA                 dec     eax
.text:01002EDB                 mov     byte ptr dword_1005340[eax], 0Fh
.text:01002EE2                 jnz     short loc_1002EDA

I was completely sure that I found minefield array. Cause of cycle which inits 360h bytes length array (dword_1005340 ) with 0xF.

Why 360h = 864? There are some cues below that row takes 32 bytes and 864 can be divided by 32, so array can hold 27*32 cells (although UI allows max 24*30 field, there is one byte padding around array for borders).

Following code generates minefield top and bottom borders (0x10 byte). I hope you can see loop iteration in that mess ;) I had to use paper and pen

.text:01002EE4                 mov     ecx, currentMineFieldWidth
.text:01002EEA                 mov     edx, currentMineFieldHeight
.text:01002EF0                 lea     eax, [ecx+2]
.text:01002EF3                 test    eax, eax
.text:01002EF5                 push    esi
.text:01002EF6                 jz      short loc_1002F11    ; 
.text:01002EF6
.text:01002EF8                 mov     esi, edx
.text:01002EFA                 shl     esi, 5
.text:01002EFD                 lea     esi, dword_1005360[esi]
.text:01002EFD
.text:01002F03 draws top and bottom borders
.text:01002F03 
.text:01002F03 loc_1002F03:                            ; CODE XREF: sub_1002ED5+3Aj
.text:01002F03                 dec     eax
.text:01002F04                 mov     byte ptr MineField?[eax], 10h ; top border
.text:01002F0B                 mov     byte ptr [esi+eax], 10h       ; bottom border
.text:01002F0F                 jnz     short loc_1002F03
.text:01002F0F
.text:01002F11
.text:01002F11 loc_1002F11:                            ; CODE XREF: sub_1002ED5+21j
.text:01002F11                 lea     esi, [edx+2]
.text:01002F14                 test    esi, esi
.text:01002F16                 jz      short loc_1002F39

And the rest of subroutine draws left and right borders

.text:01002F18                 mov     eax, esi
.text:01002F1A                 shl     eax, 5
.text:01002F1D                 lea     edx, MineField?[eax]
.text:01002F23                 lea     eax, (MineField?+1)[eax+ecx]
.text:01002F23
.text:01002F2A
.text:01002F2A loc_1002F2A:                            ; CODE XREF: sub_1002ED5+62j
.text:01002F2A                 sub     edx, 20h
.text:01002F2D                 sub     eax, 20h
.text:01002F30                 dec     esi
.text:01002F31                 mov     byte ptr [edx], 10h
.text:01002F34                 mov     byte ptr [eax], 10h
.text:01002F37                 jnz     short loc_1002F2A
.text:01002F37
.text:01002F39
.text:01002F39 loc_1002F39:                            ; CODE XREF: sub_1002ED5+41j
.text:01002F39                 pop     esi
.text:01002F3A                 retn

Smart usage of WinDBG commands can provide you cool minefield dump (custom size 9x9). Check out the borders!

0:000> db /c 20 01005340 L360
01005340  10 10 10 10 10 10 10 10-10 10 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
01005360  10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
01005380  10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
010053a0  10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
010053c0  10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
010053e0  10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
01005400  10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
01005420  10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
01005440  10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
01005460  10 0f 0f 0f 0f 0f 0f 0f-0f 0f 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
01005480  10 10 10 10 10 10 10 10-10 10 10 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
010054a0  0f 0f 0f 0f 0f 0f 0f 0f-0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
010054c0  0f 0f 0f 0f 0f 0f 0f 0f-0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................
010054e0  0f 0f 0f 0f 0f 0f 0f 0f-0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f 0f  ................................

Hmm, looks like I'll need another post to close the topic

Kilauea answered 24/7, 2009 at 12:39 Comment(4)
@Stanislav, good answer Stanislav. If you can elaborate on it at all, please do so. These long, informative answers are the best. Perhaps a bit more on how you zeroed in on the minefield data structure?Leopold
@Stanislav, I've accepted your answer because the 250 rep bounty was ending. Congratulations!Leopold
@Stanislav, I've edited your mult-part answer into a single answer. You haven't approached the size limit of your single answer and I think it is typically preferred to have one answer rather than post several. Feel free to edit your original answer (this one) and add on to it as you see fit.Equitation
Also, epic answer Stanislav. Thanks a lot for your hardwork!Equitation
G
15

It seems like you are trying to disassemble the source but what you need to do is look at the memory space of the running program. The hex editor HxD has a feature that lets you just that.

https://static.mcmap.net/file/mcmap/ZG-Ab5ovK1c1cw2mbmylZV0hXRyoa1MAZV2nKm2lcz/uploads/fcc1991162.png

Once you're in the memory space, it is a matter of taking snapshots of the memory while you mess around with the board. Isolate what changes versus what doesn't. When you think you have a handle on where the data structure lies in hex memory, try editing it while it is in memory and see if the board changes as a result.

The process you want is not unlike building a 'trainer' for a video game. Those are usually based on finding where values like health and ammo live in memory and changing them on the fly. You may be able to find some good tutorials on how to build game trainers.

Gregoor answered 21/7, 2009 at 16:27 Comment(2)
Well, you ~can~ locate the memory location via static disassembly. You can follow through the assembly instructions looking for things like rand() functions being called to generate the mine field and then trace through from there to see at what location the field is stored at in memory (and how).Equitation
Both approaches are challenging. I've tried to disassemble applications in the past and I've found it to be very painful. How exactly do you spot a rand() function?Gregoor
E
12

Check out this code project article, it's a little more in depth than the blog post you mentioned.

http://www.codeproject.com/KB/trace/minememoryreader.aspx

Edit

And this article, although not about minesweeper directly, gives you a good step by step guide on hunting through memory using WinDbg:

http://www.codingthewheel.com/archives/extracting-hidden-text-with-windbg

Edit 2

Again, this isn't about minesweeper, but it has definitely given me some food for thought for my memory debugging, there's a wealth of tutorials here:

http://memoryhacking.com/forums/index.php

Also, download CheatEngine (mentioned by Nick D.) and work through the tutorial it comes with.

Edaphic answered 7/7, 2009 at 11:2 Comment(0)
O
9

"In WinDbg I can set breakpoints, but it is difficult for me to imagine at what point to set a breakpoint and at what memory location. Similarly, when I view the static code in IDA Pro, I'm not sure where to even begin to find the function or datastructure that represents the mine field."

Exactly!

Well, you can look for routines like random() that will be called during the construction of the mines table. This book helped me a lot when I was experimenting with reverse engineering. :)

In general, good places for setting break points are calls to message boxes, calls to play a sound, timers and other win32 API routines.

BTW, I am scanning minesweeper right now with OllyDbg.

Update: nemo reminded me a great tool, Cheat Engine by Eric "Dark Byte" Heijnen.

Cheat Engine (CE) is a great tool for watching and modifying other processes memory space. Beyond that basic facility, CE has more special features like viewing the disassembled memory of a process and injecting code into other processes.

(the real value of that project is that you can download the source code -Delphi- and see how those mechanisms were implemented - I did that many years ago :o)

Oakland answered 31/5, 2009 at 6:9 Comment(0)
B
5

A pretty good article on this very topic can be found at Uninformed. It covers reversing Minesweeper (as an introduction to reverse engineering Win32 apps) in pretty great detail and is all around a pretty great resource.

Baylor answered 22/7, 2009 at 2:51 Comment(0)
D
4

This website might be more helpful:

http://www.subversity.net/reversing/hacking-minesweeper

The general way to go about doing this is:

  1. Somehow get source code.
  2. Disassemble and hope leftover symbols can help you.
  3. Guess the data type and try to manipulate it and use a memory scanner to limit the possibilities.

In response to Bounty

Well, on a second reading, it appears as though you wanted a guide on how to use a debugger like WinDBG rather than the usual question of how to reverse engineer. I've already shown you the website that tells you the values you need to search for, so the question is, how do you search for it?

I am using Notepad in this example because I do not have Minesweeper installed. But the idea is the same.

alt text

You type

s <options> <memory start> <memory end> <pattern>

Press "? " and then "s " to see the help.

Once you've found the memory pattern you want, you can then press alt+5 to bring up the memory viewer for a nice display.

alt text

WinDBG takes some getting used to, but it is as good as any other debugger out there.

Dizon answered 31/5, 2009 at 4:32 Comment(11)
"Somehow get source code" is a silly statement since Minesweeper is sent without source. And reverse engineering with source isn't reverse engineering... it's source-code analysis.Baylor
@Baylor there are applications that can decompile assembly into the source language. There is no term called "source-code analysis".Dizon
@Dizon There are applications that attempt to reconstruct a program in a source language from a given compiled binary. But you cannot get "source code" with the author's comments and quotations from a compiled binary. Sure, some of those "decompilers" do a better job than others but they are not giving you the code the author wrote (compiler optimized code is often very different from programmer's code). And have you never done quality assurance testing? What do tools like PREfast and Sparse do? Static source code analysis.Baylor
Static source code analysis in PREfast and Sparse is completely different from manually reading decompiled code in order to hack it. I don't think anyone would confuse those two different ideas as each other.Dizon
@Dizon I take it one further and agree that you should not confuse reverse engineering disassembly with looking at source code (decompiled or otherwise, if you have the source you're performing source code analysis). That was my whole point. So please, stop confusing the two. :)Baylor
@mrduclaw, then why did you say that it was "source-code analysis"? :)Dizon
@Dizon If you can't take the time to properly read what I said, I don't think it's worth me reposting. We'll try it once however: "And reverse engineering with source isn't reverse engineering... it's source-code analysis." And: "you should not confuse reverse engineering disassembly with looking at source code". Third time's the charm, I hope.Baylor
"And reverse engineering with source isn't reverse engineering... it's source-code analysis." "What do tools like PREfast and Sparse do? Static source code analysis." With these two quotes you are saying that they are doing the same thing, so you are the one that is being confused with your own doublespeak.Dizon
@Dizon The second statement is in response to your "There is no term called "source-code analysis".[sic]" I'm not confused about what I'm saying. But look, I don't think this is the place to argue these points as it has little to do with OP's question. Feel free to continue this by emailing me.Baylor
"Static source-code analysis" is completely different from what you think is "source-code analysis". Recovering source code is a form of reverse-engineering despite you not believing it so. It is possible to decompile bytecode of Java and Python and Actionscript to nearly their respective forms, and I don't think anyone would call that "source-code analysis" instead of "reverse-engineering".Dizon
What a completely vacuous answer.Belief
C
0

The mines will probably be stored in some kind of two-dimensional array. This means that it is either an array of pointers or a single C style array of booleans.

Whenever the form receives a mouse-up event this data structure is referenced. The index will be calculated using the mouse coordinate, probably using integer division. That means that you should probably look for a cmp or a similar instruction, where one of the operands is computed using an offset and x, where x is the result of a calculation involving integer division. The offset will then be the pointer to the beginning of the data structure.

Crider answered 31/5, 2009 at 4:24 Comment(0)
I
0

A good point to start tracing in debugger would be on mouse up. So find main window procedure (I think tools like spyxx can inspect windows properties and event handler address is one of them). Break in to it and find where it handles mouse events -- there will be a switch, if you can recognize it in assembler (look at value of WM_XXX for mouse up in windows.h).

Put a breakpoint there and start stepping in. Somewhere between the time you released mouse button and screen being updated the victum will access the datastructure you are looking for.

Be patient, try to identify what is being done at any given time, but don't bother looking too deep into code you suspect of being uninteresting for your current objective. It might take several runs in debugger to nail it down.

Knowledge of normal win32 applications workflow helps too.

Impurity answered 21/7, 2009 at 4:51 Comment(0)
G
0

It is fairly reasonable to assume that information about mines is layed out contiguously in memory at least for rows (i.e. it's a 2D-array, or an array-of-arrays). Thus, I would try opening several adjacent cells in the same row, making memory dumps of the process as I go, and then diff them and look for any repeating changes in the same memory region (i.e. 1 byte changed on first step, the next byte changed to exact same value on the next step, etc).

There's also possibility that it's a packed bit array (3 bits per mine should be sufficient to record all possible states - closed/open, mine/no-mine, flagged/non-flagged), so I'd look out for that too (the patterns would also be repeatable, though harder to spot). But it's not a convenient structure to deal with, and I don't think memory usage was a bottleneck for Minesweeper, so it is unlikely that this sort of thing would be used.

Gamo answered 22/7, 2009 at 2:46 Comment(0)
H
0

While not strictly a "reverse engineer's tool", and more of a toy even an idiot like me could use, check out Cheat Engine. It makes it somewhat easy to track what parts of memory have changed, when, and even has provisions for tracking the changed memory parts through pointers (though you probably don't need that). A nice interactive tutorial is included.

Hug answered 22/7, 2009 at 21:32 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.