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

Question

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?

Answer 1

"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)

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.