Slashdot Mirror
Reverse Engineering Large Software Projects?
stalebread queries: "Me and a team of other students have been tasked with reverse engineering a massive C/C++ (mostly C) computer game of about half a million lines. We have most of the source, but no clue of how to approach a task of this magnitude. Anyone have suggestions of programs, or techniques we could use to understand the structure of the game?"
Since you're probably proficient with C++, try a flowcharting solution to give you a high-level map of all the classes. Maybe that will help.
LOAD "SIG",8,1
LOADING...
READY.
RUN
I presume you mean reverse engineering in the program understanding sense. In which case the way to go about it is to sit down and read the source code, taking notes as you go. You should then set yourself some maintenance tasks - modifying the source code is the best way to find out if you understand it or not.
How we know is more important than what we know.
One like Rational Rose. It can create iconographic models of programs from source code.
Other UML tools exist, like Argo and Umbrello, but I'm not sure if they reverse engineer.
http://sourcenav.sourceforge.net/
I like to use it when browsing through code, you can search and browse as much as you like. It will still take an effort though.
"It's too bad that stupidity isn't painful." - Anton LaVey
Yeah, the "most of the source code" part is a bit scary. If they really are talking about reverse engineering from executables they are in for a hell of a time. The state of the art is a project I work on now and then, Boomerang, and it isn't for the faint of heart. I've been hearing for years about people who are working on decompilation tools that are integrated into IDA Pro but I've yet to see it. The time where you can enter a binary, press a button and get back compilable, maintainable source code is still a long long way off. But that's good, friends of mine do commercial decompilation work.
How we know is more important than what we know.
...a maintenance task, not a coding task. S/he is probably looking for a UML model, as I implied elsewhere in the thread. IBM Rational, Gentleware, Borland and some FOSS projects have software just for this sort of thing: Modeling all of the classes, structs, member variables and functions along with displayable relationships (using arrows, lines, and nesting).
Whats more, some of these tools can be used to modify programs within the model, and then update the source code (forward-engineering). They can also create tables/databases from your persistent entity classes, represented with their own DBMS variety of UML icons...and can even update the actual database (sometimes directly, other times with DDL scripts) and track/display relationships between tables, and with the classes that use them.
UML tools will seldom be able to reverse-engineer information about procedural code (declarations, conditionals, etc.) also this can usually be modeled by hand when such detail is necessary.
But the article poster has access to the source code, something not usually associated with 'reverse engineering'. Products are still protected by patents, copyright and trademarks, and writing Samba (for example) after seeing Microsofts code would open one up to legal woes.
IANAL, or USian.
"A language that doesn't affect the way you think about programming, is not worth knowing" - Alan Perlis
>We have most of the source, but no clue of how to approach a task of this magnitude.
Reverse engineering is generally thought of as a "cleanroom" technique that involves having the binary and/or specification but not the source. If you have the source, then you're just reading/rewriting it (or perhaps just copying it and doing s/Old Name/Our Cool New Game That's Nothing Like Old Name/).
>Anyone have suggestions of programs, or techniques we could use to understand the structure of the game?
If it's mostly C, then you definitely need to get cscope, but that won't tell you where to start reading because it cannot resolve calls to function pointers. To get that information, you might also try running gprof.
Another neat trick is to compile the program and use nm to help map out object file dependencies. You'll want to use perl or something to create a database of where the symbols are defined and where they're imported. This can help you establish which files are the meat and which ones are the potatoes.
It sounds like you are unable to build the complete system and run it, since you're missing functionality. This removes the possibility of using runtime tracing tools.
The first thing I would do is run something like Doxygen over it to generate a cross-referenced description of the structures. It won't give you a global view of things, but it will give you a decent browsable view of the code itself. Another response mentioned GNU GLOBAL which may work better for you. Yet another possibility is LXR, though it may not work as well in C++. Regardless, a nice thing about Doxygen is that, when used with GraphViz, you can get useful diagrams generated showing class containment and file inclusion graphs.
After you have that, get out your paper and pencil, and start drawing and manually tracing things. That's how I go about coming up to speed on new code I can't execute and step through. Eventually transfer that knowledge into a text file (or, nowadays, a wiki) so that others can benefit from it.
"Human capital" is a rather common economics term to refer to those skills and knowledge that enable an employee to produce the desired works. Use the wiki, Luke. In this case, it is the experience and serenity which makes the Tao Master of programming worth several novice salaries :)
I applaud your professor or thesis advisor or whoever for this real-world task. Here's a few resources which I wouldn't do without:
Code Reading: The Open Source Perspective
Object-Oriented Reengineering Patterns
Reading Computer Programs: Instructor's Guide and Exercise
Tips for Reading Code
I've been through this sort of exercise several times in my career so far. 500k LOC is too much for a small team to get a handle on in any reasonable amount of time, so don't feel too helpless... You're professor is throwing you guys to the wolves and seeing what you are able to accomplish.
As for the actual suggestions, read on:
First, you'll need a tool to generate some form of cross reference for the entire codebase... I'd recommend Doxygen (hack the config file to generate the inheritance and call graphs). This will speed up your ability read the code; being able to look up the interface to any class with a couple of clicks in a web browser will make life a lot less painful.
Next, find a text editor/IDE that's good at navigating large projects. This is a must. I personally do this with vi and ctags (although many people will tell you that there are better alternatives). Being able to look at more than one source file at a time is a good thing (tm).
These are the two primary tools that you'll need. There are some other pointers that I can give too:
Anyway, good luck!
I'd start buy actually reading the source - building it if you can. Run profilers on it and try to get some kind of visual representation of the underlying code tree. If you have source, try using something like DOXYGEN to autogen some documentation (and structure) out of it. Someone mentioned Rational - you can get a trial license. Try to understand what the code does. For the most part games are straight forward, in that you have objects that have specific behaviours. You can try to establish the object hierarchies and see if you can redefine these to make more sense - or just be different.
For the fragments of source you don't have - try using tools such as truss to track flow of what is going on. GDB is your friend and you probably want to try running it through the debugger - especially if the extracts you were given were compiled without stripping the symbols. nm is also another useful one at trying to get an idea of the symbols in your binary and establishing 'from meaningful names' what on earth goes on inside.
Push your binaries through a disassembler like ldasm or datarescue - win. NASM also has a disassembler. Try and get a feel for what is going on.
Now comes the hardpart - it's not called reverse 'engineering' for nothing. You've done the reverse bit. It's now time to engineer a solution which shows that you've gone through the 'reverse' bit. It can be y our view on how the code should work. Don't be affraid to reuse resource files/bitmaps, etc. That's allowed. It's the code which counts. You'll probably find that the assignment gave you something which was sub-optimal, in either design or processing - or both. It's your turn to write it the way which it should have been written. I'll leave the 'team dynamic' to you. Don't let one person have all the fun. Probably you - it's good to give others a chance. See what people are intersted in and allocate the work load. Just be prepared to fix everyone's bugs the night before submission - it's not so bad - it's 'fun.'
It's pretty simple, just time consuming. I've seen a few reverse engineering books floating around: "Reversing," "Exploiting Software." Since it's mostly stdC, it shouldn't be nearely as difficult to reverse engineer. Other languages can make things more complicated (Multiple calling mechanisms, more dynamic memory allocation, etc..).
Tools:
OllyDbg - Awesome usermode debugger, probably better suited than softice for this particular task. You can add assembly wherever you want, and it will create patches for the exe that can be automagically applied. It's also FREE.
Numega Softice - Just in case you need to bring in the big guns.
IDA Pro - Best reverse engineering tool available. Lots of extension scripts to do anything imaginable..
TSearch - Can search memory at runtime, set breakpoints, disassemble code on the stack, and dynamically insert new assembly at runtime. Nice for understanding the flow of the software as it runs, and identifying interesting variables and structures.
REC Decompiler - Awesome decompiler that produces a high level representation of the code. Not a replacement for your brain, but can save a lot of time tracing over assembly code to understand the purpose of a function.
WinPCap & Ethereal - For reversing game protocols, and understanding client-server interaction. Sometimes it's nicer to just figure out where the host name/IP string is located in the binary and replace it with 127.0.0.1, then write a little proxy program to sit in between the client and the server.
HVIEW: Hex editor with the ability to disassemble.
(Use Cygwin or mingw for the following) strace: Traces signals, system calls, and spits them out to the screen.
nm: Dump binary symbol table and names.
I've definitely forgotten a plethora of other useful tools (especially the binutils ones), but the above consist of some of my favorites.
For a game, you'll probably be dealing mostly with OllyDbg, HVIEW, REC, and winpcap/proxy. I'd recommend using nm to get a list of all of the symbols in the program, and then maybe split up and assign each student some number of symbols to understand and rewrite in C. Then they can use HVIEW or OllyDbg to navigate to those symbols, and try translating them. If they have a difficult time, have them use REC to get a higher level representation they can cheat off of.
-Jason Thomas.