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?"
Just curious... is this something legal? For example, isn't it illegal to reverse engineer Windows?
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.
It sounds like you are wanting to refactor the code, or port it to another platform. If you are missing some of the code, then you'll have to reverse engineer that portion of it.
As for how to approach it - I think it depends on the size of your team, and what goals you set for the effort. Are you just wanting to learn? Or do you want to improve performance? Or make it work on another platform? What are the goals for this project?
Once you know those details, they might give you an idea where to begin.
. 62,400 repetitions make one truth -- Brave New World, Aldous Huxley
To understand how games are made in the first place. What kind of a game is it? Is it a single player game, or multiplayer game? If it's multiplayer you'll have to watch out for code designed to keep the game logic at a fixed rate; all other code will be built on top of that. Singly player games on the other hand don't have to worry about all the intricacies of keeping the various game clients in sync.
So it really depends on the kind of game it is. Since I'm assuming you know this, I would suggest trying to first think how you would write the game yourself, and then see if you find any similarities between your ideas for the engine structure and the games.
Best. Webhost. Ever. Dreamhost.
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
I don't agree with anything in the above comment except this: "If you have to ask slashdot, you are NOT QUALIFIED for the job."
Ditto on that. And we wonder what the fuck happened to higher education? Small rocks have been know to have more ingenuity than this.
...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.
If you wish to start getting a handle on a chunk of code, start by reading main() along with a profilers output. Grep is your friend.
"A language that doesn't affect the way you think about programming, is not worth knowing" - Alan Perlis
If he already has the source, then this problem may be easy enough to make asking Slashdot unnecessary. However, there are instances in which asking Slashdot is necessary. If they didn't have most of the source, for example. Or, for example, in this article, where an IT guy was asked to make an infrastructure for over one million email accounts that must scale perfectly and have 99.9% uptime. Show me a university that trains students for that.
IDA pro, best dissasembler around ;)
http://www.datarescue.com/
>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.
Graphviz and GNU GLOBAL used in combination give a graphical and web-accessible view of a large, unknown software system. This will give your team a high-level view of the modules and how they interact. This will make it easier to discern the system design.
I would start by trying to get someone on the internet to do my homework for me.
Oh, wait, you've already come that far. Well, I'm stumped now. Good luck!
Slashdot - where whining about luck is the new way to make the world you want.
www.cse.unsw.edu.au/~drt
:)
Not that I'm biased or anything. The idea is to monitor the program while it's running and use the call graph to generate sequence diagrams and such. Feedback and ideas for further reasearch welcome
Whats the goal of your project? To figure out how they do one particular thing? To figure out how the code works in a general way? To understand 1 subsystem?
For the first, I'd try and find the functions called around when it occurs, and use a debugger to step through what happens.
For the second, I'd study the interface files and use cscope. Figure out what is calling what, and see how its interlinked.
For the third, you need to do the same as above on a local level- between files of the module. Then dig into individual parts.
Really, if you want better advice, you need to tell us what you want to do.
I still have more fans than freaks. WTF is wrong with you people?
let's see:
if you have access to (ir)rational rose, runing your code through that will probably speed up a lot of this process. otherwise, a combination of cccc and doxygen with the appropriate config files will give you about the best start you can hope for. hopefully, the code has reasonable documentation. if not, you're basically screwed --- you'll have to work out the use cases and reconstruct your software from there.
reenigne
I read
It is not 'reverse engineering' if you already have the code. So you'll be reverse engineering the part that you dont have a code for, and making sense out of the code that you do have.
Draw flow charts. Then assign a seperate person for each module to make sense out of it. Next you'll do what you plan to do....
Make mods for it? Make a clone? Rewrite the code and sell the code? Recompile and port to Linux?
"Give orange me give eat orange me eat orange give me eat orange give me you." -Nim Chimpsky
There are some automatic UML generators that will give you an overview of the code, or parts of the code:
http://droogs.org/autodia/
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.
So my suggestion is start by getting it compiled, up and running ;) You can then use the debugger to breakpoint the code and follow it through. You say you have most of the source code. Is the rest available as libararies to link to? Otherwise you could create 'fake' libraries just to get it compiling and running.
Probably best to start with a top down approach. Games invariably have a 'game loop', so locate it and start there. It'll be something along the lines of
InitStuff();
while(running)
{
DoStuff();
}
CloseStuffDown();
Whilst games are many and varied in their complexity they more often than not follow the same kind of pattern. During DoStuff() they will update the user input, update the world state (objects in the world), and finally render stuff on the screen. Once you've got a basic handle on which bits, try changing or commenting out things to see what effect that has.
You could try mapping out all the source code with various software tools and the like, but the best way I've found to understand the code is just to dive in and have a play around. You'll probably find there are one or two files that do most of the interesting stuff anyway. If you have the change information from source control (eg if it's including at the top of the file) then look for the ones with the most changes ;)
Also - grep is your friend ;)
HTH & Good luck
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
You my friend obviously havn't attended the World Famous Tarzan and Tanto School of Communication Arts.
Come on Down! TaT School of Comm. Arts am accepting applications now!
Stop intellectual property from infringing on me
This isn't a plural versus singular problem, as you might initially think. "Jack and Jill have a dog named Spot," cannot be changed to "Jack have a dog named Spot", because it's plural versus singular. That's pretty obvious, but it doesn't apply here.
The real problem is that 'me' is a direct object, and 'I' is a subject. You don't say "Me is going to the store" or "Me would like ice cream", unless you're trying to be funny. And you wouldn't say, "Give that ice cream to I!"
Better phrasing for the original submission would have been "A team of students and I have been assigned....."
-- Grammar Nazi
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!
Hmmm ... from reading your post, I suddenly had to remember this email address "help_valve@valve.com". As the name implies, they offer help to folks trying to understand the unfinished engine they released a few years ago.
Just in case this "massive" game has something to do with Half Life 2.
Are there any configuration files? If no, there may be some code that's reading supposed to be found conf files.
if you're trying to rev engineer code from a company that's gone bust - go hire their lead programmer for 6 months, and task him with documenting it. seriously.
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.'
We are evaluating some tools along these lines. The ones we liked most are RedHat's Source-Navigator (GPL) and Scitool's Understand for C++ ($$$).
Sorce-Navigator seems to be slow compared to Understand C++, I'm sure this has to do with the way they index the DB. On the other hand, the Linux version of Understand C++ needs some polishing IMHO (too many crashes on Debian/serge).
As for report-generating tools that just index and cross-reference the whole project, Gonzui is a pretty good one.
If that's the task, you probably want to use DCG rules in Prolog. :)
Hmm. I was sure I'd posted under the guy who joked that they had to improve their grammer..
...it's improved mightily since I last used it. Granted, it was reverse-engineering some Java code, but it wouldn't do squat unless it could compile the whole thing (I assume it created a symbol table/parse tree and based its analysis on that). Which made it useless for documenting portions of a product, or one that was in flux and not in a cleanly-compilable state. Sure, you could stub out everything, but if you're talking an entire package that isn't available, then it's more work than it's worth.
Personally, I'd try to break it down functionally first. Set off the graphics, the user interaction, the game core, any AI. Then break them down into their respective functions, and so on and so forth. Keep an eye out for "extern struct" declarations (esp. things like "extern struct _common" or "extern struct shared_vars", these will be communication vectors and be a general pain source).
Just junk food for thought...
OK, these should not be juxtaposed:
:)"
"It can't be fully enjoyed if you're worried about your girlfriend walking in on you fucking a jar of spaghetti."
immediately followed by:
"Use our tool
First of all this is not a massive code base for a commercial computer game, it's about average. Many games get into the 1-2 million lines of code. Having said that most games also have teams that are probably much larger than your group of students.
I'm not exactly sure what you're trying to do here. As many ppl have said reverse engineering something that you already have the source for is not really reverse engineering at all. However if I make the (somewhat suspect) assumption that your objective is to examine the code and extract some kind of high-level understanding of the entire engine which you can then demonstrate in some way, I would advise you to think again. Most games (again, I am assuming that you have a commercially developed code base of some kind) are a giant mess with no overall design or direction in the code.
Generally you'll find that a few sub-systems have been implemented with some kind of clean design (although not necessarily in a coordinated manner) and then the rest of the game is just a mass of glue code that holds these pieces together. During the original implementation no-one will have had the kind of general overview that you're looking for, each member of the team will know their specific area or areas, and how that part interfaces to the next, but no-one will know how all of them work together. Trying to summarize how all the systems work together will either give you something very high-level (and essentially meaningless) or something so complex that it's almost as hard to understand as the source (and not suitable to give to your professor as 'proof of understanding').
My advice would be to choose one or more parts of the game and try to gain an understanding (in whatever manner you choose) of those areas. One of the best ways to choose these areas is to look at the USP (unique selling points) of the game itself. Some areas of the game will have been very important to the final product, while others will have been done just because they had to. For example, if the game is an RTS with a focus on the tactical aspect of the single player experience, then the scripting and ai systems will have been very important (and made as good as possible) while the sound engine will not have been very important (and made just good enough). The parts of code which are important to the actual gameplay will have had much more time and attention spent on them and will probably be far more interesting. Having said that the most important parts of the game will also have had more ppl working on them and they may well contain much less readable code.
Perhaps you should give us some more info on what exactly you want to do, so that we can give you more relevant advice?
Doxygen... Best thing I've to recommend to you
(and yes, I am in a project involving understanding several lines of code)
Doxygen beats the crap out of SourceNav and other stuff. It creates lots of graphics of major relationships thorout your code.
how long until
How about forward-engineering it? Try and add a feature to the game that doesn't already exist (and doesn't make use of any built-in scripting system/tools, etc.) That's the only way you'll really learn what's going on in there. Reading code in and of itself doesn't mean you underestand what it does. But if you have to change the code, there's no doubt that you'll figure out how (at least a part of) it works!
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.
I submitted this question. Sorry about any confusion. I have all the code I care about, I can compile and run it, and I'm (unfortunately ) forced to use Visual Studio .Net.
I was thinking about that tool for Perl that uses Devel::DProf and a diagramming program (GraphViz I think) to draw flow charts of the program as it runs, showing which routines are called, that would be great.
See graphviz.org's resources section for some links to profilers
I wonder if something like that is avaiable for C++. Found ROCASE which looks like a CASE tool that can "reverse-engineer" (analyze) C++ files and automatically format diagrams for you to help understand the code structure. Post back here if you find it to work well!
Start with "main" and go from there :-)
I want to play Free Market with a drowning Libertarian.
For programs that primarily do file processing, you can get a similar understanding by analyzing the input files and the output files.
For database programs you often can get the DBMS to log the transactions or the SQL.
For embedded systems you would need a hardware device called a logic analyzer to get the data to make the analysis.
For communications software you'd need to get something to dump the packets to log files. Lots of these for the popular protocols.
From the above analysis you might be able to write a spec (that is, a doc that would tell somebody what the program is supposed to do, so they could code it from scratch just by reading the spec).
Later on, modify the code and see what happens.
I18N == Intergalacticization
Just in case your still looking at this topic.
Primary Questions
What is your target environment, language?
What is your objective?
What is your time line?
What are your available resources and what is their available time to apply to this effort?
Additional questions?
Do you have a working version of the original installed Game?
Can you get the missing source or if not possibly "Reverse Engineer" it?
It becomes so very apperent the people who read about the scene, and the people who do it, and/or at least know enough to ask for more detials. After reading through various posts, it was somewhat easy to pick through the people who read about reverse engineering. Mostly the choice of tools, and attitudes they had reflected the general material about reverse engineering. Also I found the "I need mores" which I describe as people who don't wont to guess. "Tell me exactly what you are doing, and I will tell you exactly why I don't know that", is thier general war cry. However, reading through the posts; There where some really insitefull ones, (this not including the people who said, "If you have the souce, how can it be reverse engineering?".