Is it "theoretically" possible/impossible to reverse any binary?

Question

I know that reverse engineering from binary to source code (e.g. C++) is generally considered hard or impossible but has any computer scientist actually proven "mathematically" that it's impossible or possible to reverse engineer (any) binary to source code? Is reverse engineering simply a very hard puzzle or are there binary out there that is simply impossible to reverse whether by hand or via decompiler?

NOTE: I know the answer might be "it depends on platform and programming language" so I am going to assume the language used is C++ since it's generally considered impossible to reverse it.

Answer 1

In fact, the answer is a bit subtle.

According to Barak et al., it is impossible to obfuscate a program. Meaning that you will always leak enough information for an attacker to rebuild a blue-print of the program.

On another hand, it is also impossible to build a program that will automatically reverse-engineering any program given as input (it comes from the Rice's theorem as obfuscation used to be built on non-trivial properties that you can find in programs).

So, finally, perfect obfuscation is not possible, but full automation neither. Which means that human (and intuition) is, and will remain, the key of this Science.

Answer 2

It seems that different answers correspond to different interpretations of the question. A C++ compiler creates a binary from source code. A C++ decompiler would create source code from the binary.

It's not possible, generally, to recreate the source (comments, macro definitions and local variable names, for example often don't exist in any form in the final binary), so what we're left with is attempting to create some source that is functionally equivalent.

One simplistic way to do this would be to disassemble an executable binary, instruction by instruction, creating C++ equivalent code for each machine instruction. This would literally do the job, but the results would be utterly unusable for humans.

As the source language becomes more complex, automatically reversing it into a useful, readable, idiomatic form becomes more of a challenge. See this recent paper titled "A Refined Decompiler to Generate C Code with High Readability" by Chen, et al. which describes both the goals and challenges of decompilation.

Answer 3

As others have said, you can always write C code that simulates machine code. That's not always useful, though. Generally you want to learn more than just how to run the program -- like how to modify it in a useful way.

Researchers are still trying to figure out which definitions of obfuscation are useful. This famous paper says you can't hide all the secrets all the time. They define a "secret" to be anything you can't get from just running the program over and over and analyzing the output. This recent paper demonstrates a way to make it impossible to tell which equivalent source code was the original. Their technique is the "best possible" obfuscation, in that it hides any secrets that can be hidden.

One of the first successful obfuscations was for point functions, that output "yes" when you type in a secret password. You obfuscate this program by coding the MD5 hash of the password (like the Unix login function does). You can run the program, but you can't crack the password. Does that count as being "impossible to reverse"?

Some aspects of software static analysis have been known for some time to be formally hard. For example, see this paper and its references.

I don't know of any research specifically on making it difficult to modify a program's behavior in a certain predictable way. That would be interesting.

Answer 4

If any binary means an arbitrary binary data file, then the answer is yes, it is impossible. To prove this, just consider a case of a file with a single byte.

If you limit it to C/C++ then it is of course possible to reverse it. However, what is impossible is to reverse it to the original source code, because there is no 1:1 relation between the machine code and the source code. Depending on the optimizations the source can look very different than the original, even though it will be semantically the same.

Answer 5

Yes, any application which runs must have some logic or code in order to execute. If the a machine (turing-complete) can follow it; so can humans, (so yes, in theory its possible to reverse anything). The reality obviously depends on the circumstances, for example security restrictions may be in place to prevent attackers obtaining access to system memory or executables on the filesystem (such as certain embedded devices).

Answer 6

It depends on definition and purpose of reverse engineering.

Actually clever human brain can understand everything that stupid computer is able to execute if this clever human brain has no time limitations.

The only research direction that somehow answers your question (measuring understandability of a program and secrecy and security guarantees of program transformations) that I know is obfuscation studies. There are interesting works in this area. For example here you can find some interesting summary of current state of this research area.

Answer 7

I try to give my idea about reversing, not an answer, because I myself hope that I can find it, moreover I am quite sure that any expert here may say that what I think is crappy but I beg a generosity from the community.

The "reverse engineering" a program is rather to verify whether the program has some properties or not, than to reverse from binary code to source code (we can imagine that there are some properties that we can observe easily in the source code but not in the binary code), then the "obfuscation" is to prevent the program from such an algorithmic verification.

In the perfect (i.e. theoretical) world, some very general results assert several things. First, the Rice's theorem (as previously mentioned by @perror) and a more constructive result of Landi. W assert that a general verificator does not exist, that means we cannot write a verificator V so that when we gives V an arbitrary program P and a non-trivial property p (a trivial property is one that exists in all programs, e.g. the magic byte MZ exists in all PE files is a trivial property), V can answer P has p or not. So that means the perfect obfuscation exists ?, the answer is trivially No, that is because we never require a such strong verificator (that gives deterministic answer for all programs), we need only a verificator for some useful classes of programs.

Second, Barak et al (as previously mentioned also by @perror) asserts a somehow contradict result: there are some classes of programs that cannot be obfuscated, namely no matter what they are obfuscated, that is easy to write a verificator to answer these programs have a given property p (or not). There is actually no contradiction here because the Rice's theorem applies in the context of "all programs" and the result of Barak et al applies for the context of "several programs", indeed we have:

Third, the result of Wee. H says that we can always hide (i.e. obfuscate) some properties given a class of special programs named point functions. Again, that does not mean the obfuscation is possible in general because this result applies in the context of "several programs".

Fourth, the result of Garg. S et al says that we can obfuscate any program so that any property computed from the obfuscated one is "trivial". So that means the perfect obfuscator exists?, and if it exists then it contradict to the result of Barak et al?, obviously No, because the two results have used actually two different definitions of triviality, in the first one a property is trivial if it exists in all programs having the same semantics (so this definition is weaker than in the second one).

In the real (i.e. practial) world, I have so little experience that I cannot give any useful idea. But I doubt that the game obfuscator vs de-obfuscator will evolve in some very clever ways and we still have many gaps to work in (as an obfuscator or as a de-obfuscator).

Answer 8

It is possible to reverse engineer any binary irrespective of what language/compiler is used, but it depends on the knowledge of the reverse engineer who does that job (or) the developer who developed the tool that does that job.

Answer 9

You can reverse engineer anything. Given you got the resources (time, money and skill). When you buy a car, program, computer, super secret chip. You get everything you need to operate it.

Given this, you can figure out how it works and thus reverse engineer it.