Simplifying assembly

Question

I'm analysing some binary trace, it's pretty much obfuscated. What I need to do is to understand work flow of its alghoritms. However I cannot find any reliable tool which would help me with that.

I was trying to convert these functions to LLVM IR and then optimize it but all of known to me tools weren't able to do that. As far as I remember only llvm-mctoll was generating suitable IR (but it was failing in most cases, probably because of lack of supported instructions), other generated a lot of useless junk code and after optimization it looked even worse. Other tools like Miasm or Angr optimized only IR, and that's not what I'm looking for.

How am I supposed to do that? Optimizing it by hand is pretty easy but it's time consuming (it has about 4k asm instructions). Does any tools that might help with such kind of optimising exists? Where is the problem with creating them? As far as I understand theory it's quite easy, especially that I'm not analysing binary but trace so I don't have to care about proper flow paths, disassembling etc.

Sample function:

eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=0040135d esp=0255ff78 ebp=0255ff80 nv up ei ng nz na po nc 0040135d e94f9b0000       jmp     0040aeb1
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=0040aeb1 esp=0255ff78 ebp=0255ff80 nv up ei ng nz na po nc 0040aeb1 9c               pushfd
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=0040aeb2 esp=0255ff74 ebp=0255ff80 nv up ei ng nz na po nc 0040aeb2 c7042417830b58   mov     dword ptr [esp],580B8317h
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=0040aeb9 esp=0255ff74 ebp=0255ff80 nv up ei ng nz na po nc 0040aeb9 e96fdaffff       jmp     0040892d
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=0040892d esp=0255ff74 ebp=0255ff80 nv up ei ng nz na po nc 0040892d 881424           mov     byte ptr [esp],dl
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=00408930 esp=0255ff74 ebp=0255ff80 nv up ei ng nz na po nc 00408930 c7042432962f1b   mov     dword ptr [esp],1B2F9632h
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=00408937 esp=0255ff74 ebp=0255ff80 nv up ei ng nz na po nc 00408937 e993570000       jmp     0040e0cf
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=0040e0cf esp=0255ff74 ebp=0255ff80 nv up ei ng nz na po nc 0040e0cf 9c               pushfd
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=0040e0d0 esp=0255ff70 ebp=0255ff80 nv up ei ng nz na po nc 0040e0d0 60               pushad
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=0040e0d1 esp=0255ff50 ebp=0255ff80 nv up ei ng nz na po nc 0040e0d1 e825acffff       call    00408cfb
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=00408cfb esp=0255ff4c ebp=0255ff80 nv up ei ng nz na po nc 00408cfb c7442424c8b5ca7e mov     dword ptr [esp+24h],7ECAB5C8h
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=00408d03 esp=0255ff4c ebp=0255ff80 nv up ei ng nz na po nc 00408d03 c6042488         mov     byte ptr [esp],88h
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=00408d07 esp=0255ff4c ebp=0255ff80 nv up ei ng nz na po nc 00408d07 6812a1e14e       push    4EE1A112h
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=00408d0c esp=0255ff48 ebp=0255ff80 nv up ei ng nz na po nc 00408d0c 50               push    eax
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=00408d0d esp=0255ff44 ebp=0255ff80 nv up ei ng nz na po nc 00408d0d 8d64242c         lea     esp,[esp+2Ch]
eax=ffff8001 ebx=001603b6 ecx=77781e4c edx=00000000 esi=00401233 edi=00401233 eip=00408d11 esp=0255ff70 ebp=0255ff80 nv up ei ng nz na po nc 00408d11 e973d3ffff       jmp     00406089

And after optimizing by hand (if I didn't make any mistake):

sub     esp, 4
mov     dword ptr [esp],1B2F9632h
sub     esp, 4
mov     dword ptr [esp],7ECAB5C8h

Or even:

push 1B2F9632h
push 7ECAB5C8h

---

Hi, it's again me.

So I took a deeper look at Triton and have written a simple peephole optimizer to get rid of usless instructions and these stack modifications. Original trace has 48k instructions, I ended up with something about 2k. There were still a lot crappy instructions but it was enough to completly devirtualize vm and understand shellcode.

Now I'm trying something harder, this is what I have. It looks like an IR level obfuscation, there is no any pattern. How would you approach this? I saw this but it works on a functions that have one input, one output. I don't know will it work with a function that does a lot of computations with flags a lot of memory modifications. I have also seen this talk by Rolf Rolles about synthesis. It looks great, maybe this should give better results? Also is there any simple way to apply dead removal and constant folding at Triton IR level? Does any tools exist since I couldn't find anything?

rip=00000003de72158d sub     r11d,2AD65C0Bh
rip=00000003de721594 rol     r11d,1
rip=00000003de721597 movsx   rsi,ax
rip=00000003de72159b not     r11d
rip=00000003de72159e inc     cx
rip=00000003de7215a1 sete    bl
rip=00000003de7215a4 inc     r11d
rip=00000003de7215a7 cmc
rip=00000003de7215a8 movzx   si,spl
rip=00000003de7215ad add     r11,rax
rip=00000003de7215b0 adc     bh,ch
rip=00000003de7215b2 mov r9,100000000h
rip=00000003de7215bc ror     r12,56h
rip=00000003de7215c0 add     r11,r9
rip=00000003de7215c3 bsr     r12w,r8w
rip=00000003de7215c8 mov     r12,rsp
rip=00000003de7215cb rol     r14,cl
rip=00000003de7215ce cmp     r11b,0CCh
rip=00000003de7215d2 rol     bl,95h
rip=00000003de7215d5 sub     rsp,180h
rip=00000003de7215dc and     rsp,0FFFFFFFFFFFFFFF0h
rip=00000003de7215e3 sal     bh,98h
rip=00000003de7215e6 cmc
rip=00000003de7215e7 mov     rbx,r11
rip=00000003de7215ea sar     sil,cl
rip=00000003de7215ed and     rcx,14DB3A03h
rip=00000003de7215f4 shl     ch,cl
rip=00000003de7215f6 mov r14,0FFFFF8029E610000h
rip=00000003de721600 cmovno  cx,r13w
rip=00000003de721605 and     ecx,ebp
rip=00000003de721607 sub     rbx,r14

Registers:

rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b0 rdx=ffff8a8e13e66ab0 rsi=0000000000003000 rdi=0000000000000010 rip=00000003de72158d rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=000000000ad2f6fe r12=0000000000000000 r13=0000000000000002 r14=0000000000000400 r15=ffff948059d63000 nv up ei ng nz ac po nc fffff803`de72158d 4181eb0b5cd62a  sub     r11d,2AD65C0Bh
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b0 rdx=ffff8a8e13e66ab0 rsi=0000000000003000 rdi=0000000000000010 rip=00000003de721594 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=00000000dffdf651 r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei ng nz na pe cy 00000003`de721594 41d1c3          rol     r11d,1
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b0 rdx=ffff8a8e13e66ab0 rsi=0000000000003000 rdi=0000000000000010 rip=00000003de721597 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=00000000bffbeca3 r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei ng nz na pe cy 00000003`de721597 480fbff0        movsx   rsi,ax
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b0 rdx=ffff8a8e13e66ab0 rsi=0000000000000000 rdi=0000000000000010 rip=00000003de72159b rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=00000000bffbeca3 r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei ng nz na pe cy 00000003`de72159b 41f7d3          not     r11d
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b0 rdx=ffff8a8e13e66ab0 rsi=0000000000000000 rdi=0000000000000010 rip=00000003de72159e rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=000000004004135c r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei ng nz na pe cy 00000003`de72159e 66ffc1          inc     cx
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=0000000000000000 rdi=0000000000000010 rip=00000003de7215a1 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=000000004004135c r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl nz na po cy 00000003`de7215a1 0f94c3          sete    bl
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=0000000000000000 rdi=0000000000000010 rip=00000003de7215a4 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=000000004004135c r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl nz na po cy 00000003`de7215a4 41ffc3          inc     r11d
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=0000000000000000 rdi=0000000000000010 rip=00000003de7215a7 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=000000004004135d r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl nz na pe cy 00000003`de7215a7 f5              cmc
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=0000000000000000 rdi=0000000000000010 rip=00000003de7215a8 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=000000004004135d r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl nz na pe nc 00000003`de7215a8 66400fb6f4      movzx   si,spl
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215ad rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=000000004004135d r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl nz na pe nc 00000003`de7215ad 4c03d8          add     r11,rax
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215b0 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=fffff802de65135d r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei ng nz na pe nc 00000003`de7215b0 12fd            adc     bh,ch
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215b2 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=00000000000000af r10=ffff8a8e13e667e0 r11=fffff802de65135d r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de7215b2 49b90000000001000000 mov r9,100000000h
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215bc rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff802de65135d r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de7215bc 49c1cc56        ror     r12,56h
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215c0 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff802de65135d r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de7215c0 4d03d9          add     r11,r9
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215c3 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei ng nz na pe nc 00000003`de7215c3 66450fbde0      bsr     r12w,r8w
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215c8 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=0000000000000000 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de7215c8 4c8be4          mov     r12,rsp
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215cb rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de7215cb 49d3c6          rol     r14,cl
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215ce rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de7215ce 4180fbcc        cmp     r11b,0CCh
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215d2 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 ov up ei ng nz na pe cy 00000003`de7215d2 c0c395          rol     bl,95h
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215d5 rsp=ffff8a8e13e66ca8 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei ng nz na pe nc 00000003`de7215d5 4881ec80010000  sub     rsp,180h
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215dc rsp=ffff8a8e13e66b28 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei ng nz na po nc 00000003`de7215dc 4881e4f0ffffff  and     rsp,0FFFFFFFFFFFFFFF0h
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215e3 rsp=ffff8a8e13e66b20 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei ng nz na pe nc 00000003`de7215e3 c0f798          sal     bh,98h
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215e6 rsp=ffff8a8e13e66b20 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de7215e6 f5              cmc
rax=fffff8029e610000 rbx=0000000000000000 rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215e7 rsp=ffff8a8e13e66b20 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl zr na po cy 00000003`de7215e7 498bdb          mov     rbx,r11
rax=fffff8029e610000 rbx=fffff803de65135d rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000a8 rdi=0000000000000010 rip=00000003de7215ea rsp=ffff8a8e13e66b20 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl zr na po cy 00000003`de7215ea 40d2fe          sar     sil,cl
rax=fffff8029e610000 rbx=fffff803de65135d rcx=00000000000000b1 rdx=ffff8a8e13e66ab0 rsi=00000000000000ff rdi=0000000000000010 rip=00000003de7215ed rsp=ffff8a8e13e66b20 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei ng nz na po cy 00000003`de7215ed 4881e1033adb14  and     rcx,14DB3A03h
rax=fffff8029e610000 rbx=fffff803de65135d rcx=0000000000000001 rdx=ffff8a8e13e66ab0 rsi=00000000000000ff rdi=0000000000000010 rip=00000003de7215f4 rsp=ffff8a8e13e66b20 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl nz na pe nc 00000003`de7215f4 d2e5            shl     ch,cl
rax=fffff8029e610000 rbx=fffff803de65135d rcx=0000000000000001 rdx=ffff8a8e13e66ab0 rsi=00000000000000ff rdi=0000000000000010 rip=00000003de7215f6 rsp=ffff8a8e13e66b20 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=0000000000000000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de7215f6 49be0000619e02f8ffff mov r14,0FFFFF8029E610000h
rax=fffff8029e610000 rbx=fffff803de65135d rcx=0000000000000001 rdx=ffff8a8e13e66ab0 rsi=00000000000000ff rdi=0000000000000010 rip=00000003de721600 rsp=ffff8a8e13e66b20 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=fffff8029e610000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de721600 66410f41cd      cmovno  cx,r13w
rax=fffff8029e610000 rbx=fffff803de65135d rcx=0000000000000002 rdx=ffff8a8e13e66ab0 rsi=00000000000000ff rdi=0000000000000010 rip=00000003de721605 rsp=ffff8a8e13e66b20 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=fffff8029e610000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de721605 23cd            and     ecx,ebp
rax=fffff8029e610000 rbx=fffff803de65135d rcx=0000000000000000 rdx=ffff8a8e13e66ab0 rsi=00000000000000ff rdi=0000000000000010 rip=00000003de721607 rsp=ffff8a8e13e66b20 rbp=ffff8a8e13e66e40 r8=0000000000000000 r9=0000000100000000 r10=ffff8a8e13e667e0 r11=fffff803de65135d r12=ffff8a8e13e66ca8 r13=0000000000000002 r14=fffff8029e610000 r15=ffff948059d63000 nv up ei pl zr na po nc 00000003`de721607 492bde          sub     rbx,r14

Answer 1

Interesting topic.

The first thing I do to simplify obfuscation, is to determine if the obfuscator works in assembly or IR level. In assembly level, you usually have a finer granularity and tricky instructions, where in an IR level you find better looking functions and standard instructions from a compiler.

This case should be on assembly language level, because there are lot of useless stack displacement and assignment, I suggest to start to simplify it. I manually did that, it's a way to figure out the pattern (if possible) and then automatize the process:

esp=0255ff78 jmp     0040aeb1
esp=0255ff78 pushfd                                 ;; 0255ff74 = flags
esp=0255ff74 mov     dword ptr [esp],580B8317h      ;; 0255ff74 = 0x580B8317
esp=0255ff74 jmp     0040892d
esp=0255ff74 mov     byte ptr [esp],dl              ;; 0255ff74 = 0x580B8300
esp=0255ff74 mov     dword ptr [esp],1B2F9632h      ;; 0255ff74 = 0x1B2F9632
esp=0255ff74 jmp     0040e0cf
esp=0255ff74 pushfd                                 ;; 0255ff70 = flags
esp=0255ff70 pushad                                 ;; 0255ff6c = eax = ffff8001
                                                    ;; 0255ff68 = ecx = 77781e4c
                                                    ;; 0255ff64 = edx = 00000000
                                                    ;; 0255ff60 = ebx = 001603b6
                                                    ;; 0255ff5c = esp = 0255ff70
                                                    ;; 0255ff58 = ebp = 0255ff80
                                                    ;; 0255ff54 = esi = 00401233
                                                    ;; 0255ff50 = edi = 00401233

esp=0255ff50 call    00408cfb                       ;; 0255ff4c = 0040e0d1 + 5 = 0x40e0d6
esp=0255ff4c mov     dword ptr [esp+24h],7ECAB5C8h  ;; 0255ff70 = 0x7ECAB5C8
esp=0255ff4c mov     byte ptr [esp],88h             ;; 0255ff4c = (0x40e0d6 & 0xffffff00) | 0x88 = 0x40e088
esp=0255ff4c push    4EE1A112h                      ;; 0255ff48 = 0x4EE1A112
esp=0255ff48 push    eax                            ;; 0255ff44 = ffff8001
esp=0255ff44 lea     esp,[esp+2Ch]                  ;; esp = 0255ff70
esp=0255ff70 jmp     00406089

I agree with you about the two push instructions. Between the beginning and the end, the stack was decremented of 4 + 4, and the assignment at these offsets give the value of the push. It doesn't mean these values will be eventually used, though.

I was trying to convert these functions to LLVM IR and then optimize it but all of known to me tools weren't able to do that. As far as I remember only llvm-mctoll was generating suitable IR (but it was failing in most cases, probably because of lack of supported instructions), other generated a lot of useless junk code and after optimization it looked even worse.

The main issue is how an instruction is actually converted to the IR and how it'll react with the compiler's passes. Some obfuscations could be optimized by a compiler, others don't. An example is, how a compiler is supposed to interact with the pushf or pushad instruction? If you can remap the stack usage as alloca, you could easily remove useless access. If esp access is viewed as a non-volatile write on memory, the compiler will have to keep it every time. Compilers are better to perform well-known optimization like constant propagation.

Other tools like Miasm or Angr optimized only IR, and that's not what I'm looking for.

What's the problem with the IR?

How am I supposed to do that? Optimizing it by hand is pretty easy but it's time consuming (it has about 4k asm instructions).

I recommend a tool which works on the IR level and you define your own optimization. If you can simplify the stack usage and useless jmp / call, you will get a better view of the original code.

Does any tools that might help with such kind of optimising exists?

Yes, but I think you already know them. In case of: triton and medusa (disclaimer: I'm the author of the latter, and it's kinda broken at the moment)

Where is the problem with creating them?

Most of these tools work with an IR, the first issue is to convert assembly code to an IR language to work with. The next step is to implement simplification passes (like a compiler). The final step is to construct expression by executing symbolically the code, the complexity grows very quickly and you end with poor performances / memory exhaustion. Usually, you have to simplify these expressions manually by concreting some inputs and applying optimizations.

As far as I understand theory it's quite easy, especially that I'm not analysing binary but trace so I don't have to care about proper flow paths, disassembling etc.

Analyzing a trace is usually easier, but there's a catch. Storing the trace could be very heavy, the overhead could be excessive, you can't easily build expressions from the trace, ... If you want to stay with a trace, I think you should probably write a custom tool which parse the code and optimize it. For instance: for each assignment on the stack, keep the exact address and value. At the end of each piece of code (e.g. call to a imported function, address is already executed, ...) you can remove useless write on the stack. I can't guarantee it'll work on this case. :)

BTW, can you share the executable?