Dead code elimination visualization

[psifertex]

For 2.3, we'd like the ability to better track which code is optimized away by dead code elimination so that the user has more insight into things that have been removed. We expect the optimizer will not change as a result, rather that the UI will offer better insight into what it's doing.

[yrp604]

So this would be a huge improvement and I am very excited for it to land. That said, is there a reason you couldn't/don't want to make a config toggle for the dead store/code elimination passes?

[psifertex]

There's already a view for that -- it's called MLIL. :-)

[yrp604]

Attaching a motivating example as to why this is such a pain point currently. This:

Gets translated to the following hlil:

All the assembly, including an allocation, a copy from user, a memset, a call into trustzone, and a free get eliminated. This is due to the type on var_38 in the copy from user at 0x4c4: it defaults to an int64_t when in actuality it's a 0x10 byte buffer. Because the later 8 bytes are explicitly zeroed by the prolog, the basic block starting at 0x4c8 which reads this value turns into if (true). This eliminates all of the now "dead" code underneath it, causing "both" branches of the initial check to point at the error path.

Once we correct the type on var_38 we start getting more reasonable output:

This behavior makes it very difficult to have confidence in the hlil output, especially on code you'd want to reverse where you'd obviously not have types at the outset.

[D0ntPanic]

The heuristics used to eliminate dead stores of stack variables has been significantly improved. Stack variables are no longer eliminated by default unless there is a good reason for them to be eliminated (for example, the variable is the target of a push of a constant during a function call setup).

In HLIL, if a variable assignment does not appear to be used, the entire line of code will be grayed out, indicating that the analysis thinks that the code has no effect. If you want Binary Ninja to actually eliminate this code, you can now right click on the target variable and choose "Allow" from the "Dead Code Elimination" submenu.

Implemented in build 2581

[yrp604]

Unfortunately I don't think this is completely resolved. Dead store elimination is better (thank you!) but dead code elimination is still a problem.

Here is a minimized testcase showing the problem with a toy parser (gcc 10 on linux, gcc -o dce dce.c):

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

struct header_t {
        uint64_t magic;
        uint64_t version;
};

int main(void) {
    struct header_t header = { 0 };

    read(0, &header, sizeof header);

    if (header.magic != 0x41424344) {
        puts("bad magic");
        exit(1);
    }

    if (header.version == 0x1)
        puts("version 1");
    else if (header.version == 0x2)
        puts("version 2");
    else {
        puts("bad version");
        exit(1);
    }
}

This turns into:

int32_t main(int32_t arg1, char** arg2, char** arg3)

0000115d  int64_t var_18 = 0
00001183  read(fd: 0, buf: &var_18, nbytes: 0x10)
0000119b  if (var_18 != 0x41424344)
0000119b      puts(str: "bad magic")
000011a5      exit(status: 1)
000011a5      noreturn
000011e1  puts(str: "bad version")
000011eb  exit(status: 1)
000011eb  noreturn
000011f6  return 0

In addition to the code being removed here, I'm also confused why var_10 is removed without any indication?

Digging into this further, this might be a MLIL problem as the condition is resolved to true before it gets to HLIL?

int32_t main(int32_t arg1, char** arg2, char** arg3)

int64_t var_18  {Frame offset -18}
int64_t var_10  {Frame offset -10}
int64_t __saved_rbp  {Frame offset -8}
void* const __return_addr  {Frame offset 0}
char** arg3  {Register rdx}
char** arg2  {Register rsi}
int64_t* rsi  {Register rsi}
int32_t arg1  {Register rdi}

main:
   0 @ 0000115d  var_18 = 0
   1 @ 00001176  rsi = &var_18
   2 @ 0000117e  rax = 0
   3 @ 00001183  read(fd: 0, buf: rsi, nbytes: 0x10)
   4 @ 00001188  rax_1 = var_18
   5 @ 00001192  if (rax_1 == 0x41424344) then 6 @ 0x11b2 else 7 @ 0x119b

   6 @ 000011b2  if (true) then 10 @ 0x11ca else 11 @ 0x11bb

   7 @ 0000119b  puts(str: "bad magic")
   8 @ 000011a5  exit(status: 1)
   9 @ 000011a5  noreturn

  10 @ 000011ca  if (true) then 13 @ 0x11e1 else 16 @ 0x11d3

  11 @ 000011bb  puts(str: "version 1")
  12 @ 000011c0  goto 18 @ 0x11f0

  13 @ 000011e1  puts(str: "bad version")
  14 @ 000011eb  exit(status: 1)
  15 @ 000011eb  noreturn

  16 @ 000011d3  puts(str: "version 2")
  17 @ 000011d8  goto 18 @ 0x11f0

  18 @ 000011f0  rax_2 = 0
  19 @ 000011f6  return 0

This is on 2582-dev personal Win10