How to recover variables from an assembly code?

Question

Assuming we have an assembly code, what are the known techniques that could be used to recover the variables used in the original high-level code ?

Edit: By recovering variables, I do not mean recovering variable names, but trying to identify memory locations that are used to store temporary results that could be replaced by a variable in the high-level code. Also, I am not speaking about bytecodes, but real binary code with no type information, nor complete names embedded in it.

Answer 1

(I was planning to make it a comment but it turned out rather long and it makes an answer on its own)

Some of the comments mentioned the Hex-Rays decompiler. Its basic ideas are not a trade secret and are in fact described in the white paper by Ilfak Guilfanov which accompanies the presentation he gave in 2008.

I'll paste the relevant part here:

Local variable allocation

This phase uses the data flow analysis to connect registers from different basic blocks in order to convert them into local variables. If a register is defined by a block and used by another, then we will create a local variable covering both the definition and the use. In other words, a local variable consists of all definitions and all uses that can be connected together. While the basic idea is simple, things get complicated because of byte/word/dword registers.

It's simple on the surface but of course the implementation has to account for numerous details. And there's always room for improvement. There's this passage:

For the time being, we do not analyze live ranges of stack variables (this requires first a good alias analysis: we have to be able to prove that a stack variable is not modified between two locations). I doubt that a full fledged live range analysis will be available for stack variables in the near future.

So, for stack variables the approach right now is simple: each stack slot is considered a single variable for the whole function (with some minor exceptions). The decompiler relies here on the work done by IDA during disassembly, where a stack slot is created for each access by an instruction.

One current issue is multiple names for the same variable. For example, the compiler may cache the stack var in a register, pass it to some function, then later reload it into another register. The decompiler has to be pessimistic here. If we can't prove that the same location contains the same value at two points in time, we can't merge the variables. For example, any time the code passes an address of a variable to a call, the decompiler has to assume the call may spoil anything after that address. So even though the register still contains the same value as the stack var, we can't be 100% certain. Thus the excess of variable names. User can override it with manual mapping, however.

There are some ideas about introducing function annotations that would specify exactly how a function uses and/or changes its arguments (similar to Microsoft's SAL) which would alleviate this problem, but there are some technical implementation issues there.

Answer 2

What you are describing is exactly the problem that was tackled by Gogul Balakrishnan in his doctoral work on value-set analysis [1]. In particular, he defines a memory model for x86 in terms of concepts such as "abstract locations". Here is his description for that concept:

As pointed out earlier, executables do not have intrinsic entities like source-code variables that can be used for analysis; therefore, the next step is to recover variable-like entities from the executable. We refer to such variable-like entities as a-locs (for “abstract locations”).

Sound familiar vis-a-vis your question? You should read this thesis, although be warned that -- like most documents about abstract interpretation -- it is terse and unfriendly reading.

[1] http://pages.cs.wisc.edu/~bgogul/Research/Thesis/thesis.html

Answer 3

Soo..... this is one of the reasons binary analysis is hard, the loss of semantic information. A variable is not a concept known in computer architecture, it's reminiscent of a higher level of understanding.

The best answer I can give you is, if you're doing Compiler Output Analysis (which you are), you can look for the conventions used by that compiler to store variables, probably as a combination of registers and variable "spillage" into locations on the stack frame.

The bad news is it's compiler dependent. The good news is most compilers are more-or-less similar.

You could attempt to determine signed-ness by observing the conditional operations that work off a value (assuming the developer didn't make a mistake such as comparing a signed and unsigned value).

Answer 4

One sweet trick regarding strings inside of a binary, is the command line tool strings. It may be important to mention, that it doesn't search for "variables". It just looks for continuous valid characters and prints them. So this is also helpful to extract strings from any kind of file (when stored in cleartext).

Example program:

int main(int argc, char* argv[]) {
    char pw[]="SecretPW";
    if(!strcmp(pw,argv[1])){
        printf("Correct!\n");
    } else {
        printf("False...\n");
    }
    return 0;
}

Using string to extract the strings:

$ ./test FalsePW
False...
$ strings test
SecretPW
Correct!
False...
$ ./test SecretPW                                                           139 ↵
Correct!