Vector35 / Vector35/binaryninja-api

Poor decompilation of code using multiply-add instructions to access array

Open
#7,190 0 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

Component: Core Core: HLIL Effort: Medium Impact: Medium
Dominant language
C++
Stars
1.3k
Forks
298
Avg merge
5d 5h
Merged PRs (30d)
19

Description

Version and Platform (required):

  • Binary Ninja Version: 5.2.8012-dev (aec518eb)
  • Edition: Commercial
  • OS: macOS
  • OS Version: 15.5 (24F74)
  • CPU Architecture: arm64

Bug Description:

Some common code idioms used on arm64 to access arrays of structs produce poor decompilation.

Steps To Reproduce:
Open this binary. It contains three functions that all index into an array of structs. All are equivalent except that one of them takes a 32-bit index and the other two take a 64-bit index. The corresponding source code is:

struct s {
    char x[100];
    int y;
};
int get_y_32bit_index(struct s *s, unsigned idx) {
    return s[idx].y;
}
int get_y_64bit_index(struct s *s, unsigned long idx) {
    return s[idx].y;
}
int get_y_64bit_index_without_madd(struct s *s, unsigned long idx) {
    /* some hacky asm block you don't want to see,
     * but the effect is the same as the other two functions */
}

However, Binary Ninja's decompilation is of varying quality:

00400000    int get_y_32bit_index(struct s* s, unsigned int idx)
0040000c        return *(&s->y + mulu.dp.d(idx, 0x68))

00400010    int get_y_64bit_index(struct s* s, unsigned long idx)
0040001c        return *(&s->y + idx * 0x68)

00400020    int get_y_64bit_index_without_madd(struct s* s, unsigned long idx)
00400030        return s[idx].y

The first function uses UMADDL, a multiply-add instruction where the multiplied inputs are 32-bit but the multiply result is 64-bit:

00400000  080d8052   mov     w8, #0x68
00400004  2800a89b   umaddl  x8, w1, w8, x0
00400008  006540b9   ldr     w0, [x8, #0x64]
0040000c  c0035fd6   ret     

In LLIL this turns into LLIL_MULU_DP aka mulu.dp.d, and it stays as an intrinsic call all the way through to HLIL.

The second function uses MADD, a multiply-add instruction where everything is 64-bit:

00400010  080d8052   mov     w8, #0x68
00400014  2800089b   madd    x8, x1, x8, x0
00400018  006540b9   ldr     w0, [x8, #0x64]
0040001c  c0035fd6   ret     

This does get turned into separate add and multiply operands in LLIL, but for some reason the decompilation is still different from the third function, which uses separate MUL and ADD instructions:

00400020  020d80d2   mov     x2, #0x68
00400024  217c029b   mul     x1, x1, x2
00400028  0000018b   add     x0, x0, x1
0040002c  006440b9   ldr     w0, [x0, #0x64]
00400030  c0035fd6   ret     

Expected Behavior:
All three functions should decompile to return s[idx].y.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the attached umaddl.zip and compare the LLIL and HLIL for the UMADDL, MADD, and separate MUL/ADD cases described in the report. Trace how the multiply-add forms are represented through decompilation; done means all three functions produce the expected s[idx].y output.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, cpp
Domain
compilers, reverse-engineering
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.