16

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.

15

(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.

  • Exactly the type of answer I was looking for, thanks ! – perror Mar 27 '13 at 10:26
  • Comments are not for extended discussion; this conversation has been moved to chat. – Igor Skochinsky May 10 at 12:29
9

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

8

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

  • You give nice investigation paths, but there must be some existing 'ad-hoc' techniques. For example, what are the techniques used in hex-rays Decompiler or boomerang to identify variables within a stack-frame ? – perror Mar 26 '13 at 17:15
  • 1
    Hex-Rays decompiler is actually pretty poor at understanding variable boundaries. It simply seems to assume that anything which can be a variable is. This can lead to gross over-estimation of the number of variables. You generally have to map quite a lot of variables as aliases in order to get a clean decompilation. It's still an awesome product though. Igor probably knows a lot more but this may border on trade secrets or something. – Peter Andersson Mar 26 '13 at 18:14
  • endeavor: not only compiler-dependent, though. Consider call conventions, they are dictated by architecture or platform. – 0xC0000022L Mar 26 '13 at 20:01
  • @PeterAndersson: it likely wouldn't be anything they'd disclose. I suppose on top of what any of us could come up with, Hex-Rays (the company) has probably come up with a bunch of heuristics to identify things as this or that. And I concur, having tested the beta of the decompiler plugin, I wasn't convinced at all. It was misleading me a lot where IDA never was. Still, it's been a few years, but as a private person I don't want to afford it at the moment ;) – 0xC0000022L Mar 26 '13 at 20:04
  • 1
    @0xC0000022L, the decompiler is awesome. It saves us a lot of time. You just have to be pretty thorough with typing and mapping everything. It still makes mistakes and sometimes misleads but it's a net positive. – Peter Andersson Mar 26 '13 at 20:21
-2

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!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.