How can i remove dead code and opaque predicates?

Question

---

I have the following problem on my agenda: There is an obfuscated .exe (this is a virus that I am investigating) in addition to having an MBA, etc. bullshit, he has Opaque predicates and dead code, I know there are solvers to solve this gap(z3), but they have problems with execution speed, when I delete one instruction in a graph and compare it with the original graph, it takes too much time, I also made the solver see not just one graph, but the entire function, because of this, I have big problems with the speed of execution, since there are more than 1000 instructions in the function - I delete one at a time, and it's simply unbearable to wait so long, the solver also has problems with registers, since there is no inheritance of data from variables and I have to update the lower part of the registers every time.

Are there any elegant ways to solve opaque predicates and dead code?(my implementations of this on solver are: https://github.com/Nitr0-G/DynamicRetDec and https://github.com/Nitr0-G/Z3-Dead-Code-Elemination). Perhaps opaque predicates and dead code elimination can be solved somehow with the help of data tracking? Are there any implementations that I could look at or maybe concepts?

Answer 1

So, as I understand it, it is impossible to do this at the level of an assembly language as such.

In order to delete dead code in a normal sense, it is necessary to carry out the stages of code analysis, or rather data flow graph, it is impossible to do this in one run of the assembler code with the unicron emulator, i.e. I need to form a conditional data map (This also applies to opaque predicates) https://www.sciencedirect.com/topics/computer-science/data-flow-graph

http://bears.ece.ucsb.edu/research-info/DP/dfg.html

Let's say I add the second phase of the run, i.e. on the first I will form a data flow graph, and on the second I will already apply this data flow graph to the code and start optimizing it all. Then I stumble upon another problem, in order to understand at the assembler level whether the command is correct even with a dfg(data flow graph), we need to delete one variable or number and compare it with the original tree and check that our calculations are not broken in any way. If I take a real case of a virus that is very well obfuscated, then you and I will sit in a puddle, because if there are more than 1000 instructions in one function, then our optimization will be extremely long.

But many readers may object and say that the same can be done with a solver, but I will answer you that it takes about 534MC to recalculate our example with a certain solver constraint

    s.add(!(*orig.rax == *opt.rax && *orig.rbx == *opt.rbx && *orig.rcx == *opt.rcx && *orig.rdx == *opt.rdx && *orig.rbp == *opt.rbp && *orig.rsp == *opt.rsp && *orig.rsi == *opt.rsi 
        && *orig.rdi == *opt.rdi 
        && *orig.r8 == *opt.r8 && *orig.r9 == *opt.r9 && *orig.r10 == *opt.r10 && *orig.r11 == *opt.r11 && *orig.r12 == *opt.r12 && *orig.r13 == *opt.r13 && *orig.r14 == *opt.r14 
        && *orig.r15 == *opt.r15 && *orig.xmm0 == *opt.xmm0 && *orig.xmm1 == *opt.xmm1 && *orig.xmm2 == *opt.xmm2 && *orig.xmm3 == *opt.xmm3 && *orig.xmm4 == *opt.xmm4
        && *orig.xmm5 == *opt.xmm5 && *orig.xmm6 == *opt.xmm6 && *orig.xmm7 == *opt.xmm7 && *orig.xmm8 == *opt.xmm8 && *orig.xmm9 == *opt.xmm9 && *orig.xmm10 == *opt.xmm10
        && *orig.xmm11 == *opt.xmm11 && *orig.xmm12 == *opt.xmm12 && *orig.xmm13 == *opt.xmm13 && *orig.xmm14 == *opt.xmm14 && *orig.xmm15 == *opt.xmm15 && *orig.zf == *opt.zf 
        && *orig.of == *opt.of && *orig.cf == *opt.cf && *orig.pf == *opt.pf && *orig.sf == *opt.sf && *orig.af == *opt.af && *orig.df == *opt.df));

The constraint above will take you about 534MC for one repeat, and now imagine that we have ten such repetitions, it will just be incomprehensible in terms of execution time. With opaque predicates, things are a little better, but everything is still performed for an extremely long time... Along the way, we can only optimize only those instructions that obviously fall out of our dfg at all, but there are few such cases and in real cases this will be extremely rare for us.

Of all the cases, only one will help us: We need to collect the entire trace of the program to the place we need, despite the garbage data and dead code, etc. obfuscation. Then we will need to lift the collected instructions to llvm-ir or any other ir and after that we can proceed to normal optimization.

In its own way, you need to develop a source to source compiler for deobfuscation(asm2asm with different optimizations): https://github.com/rose-compiler/rose https://en.wikipedia.org/wiki/Source-to-source_compiler