Way to check if two assembly programs (one possibly compiled with optimizations) come from the same C source code?

Question

Let's suppose I have two programs in assembly code. And I want to check if they both came from the same source code, but one was compiled with optimizations. Is there a tool that can do this? Or some general process that can verify this?

Answer 1

While you can potentially prove that two pieces of binary code are equivalent (i.e. they produce the same results given the same input), this does not by itself mean that the source code was the same. For example, the following two snippets will likely be compiled to the same binary even though the source is different:

 int f(int x)
 {
  return x+1;
 }

 int g(int y)
 {
  return ++y;
 }

(check on https://godbolt.org/)

That said, if you do want to prove that (for example) two functions are equivalent, you can try many different approaches, e.g.:

• manual comparison of assembly code/binary diffing (may not work if very different compilers or optimizations settings were used)
• decompile both functions and compare outputs (same caveat)
• if the input state is not huge, you can run both functions with all possible inputs and compare outputs
• in some cases things like symbolic execution or SMT solvers can be applied

A more generic problem of detecting authorship of arbitrary code is called "code provenance" and there are several papers on the topic, e.g.:

• Who Wrote This Code? Identifying the Authors of Program Binaries (Nathan Rosenblum et al.)
• BinPro: A Tool for Binary Source Code Provenance (Dhaval Miyani et al.)