Identify targets of a switch table in ARM

Question

I'm working on a disassembler for ARM Thumb2 (stripped) binaries. I can already recover the CFG of Basic Blocks (BB) that use direct jumps. My next goal is to handle indirect jumps. I'm currently working on identifying targets of switch statements which I'll discuss based on the following example:

int main(int argc, char** argv){
  int i = 0;
  switch (argc) {
    case 0: i++; break;
    case 1: i+=2; break;
    case 3: i+=3; break;
    case 6: i+=6; break;
    case 5: i+=8; break;
    case 7: i+=10; break;
    default: i+=87; break;
  }
  return i;
}

When compiling the above example using:

arm-linux-gnueabihf-gcc-4.8 -o3 -mthumb main.c -o main.out

Disassembling main using objdump show that the switch table data words start at 0x83d8 as can be seen here:

83bc:       b480            push    {r7}
83be:       b085            sub     sp, #20
83c0:       af00            add     r7, sp, #0
83c2:       6078            str     r0, [r7, #4]
83c4:       6039            str     r1, [r7, #0]
83c6:       2300            movs    r3, #0
83c8:       60fb            str     r3, [r7, #12]
83ca:       687b            ldr     r3, [r7, #4]
83cc:       2b07            cmp     r3, #7
83ce:       d82b            bhi.n   8428 <main+0x6c>
83d0:       a201            add     r2, pc, #4      ; (adr r2, 83d8 <main+0x1c>)
83d2:       f852 f023       ldr.w   pc, [r2, r3, lsl #2]
83d6:       bf00            nop
83d8:       000083f9        .word   0x000083f9
83dc:       00008401        .word   0x00008401
83e0:       00008429        .word   0x00008429
83e4:       00008409        .word   0x00008409
83e8:       00008429        .word   0x00008429
83ec:       00008419        .word   0x00008419
83f0:       00008411        .word   0x00008411
83f4:       00008421        .word   0x00008421
83f8:       68fb            ldr     r3, [r7, #12]
83fa:       3301            adds    r3, #1
83fc:       60fb            str     r3, [r7, #12]
83fe:       e017            b.n     8430 <main+0x74>
8400:       68fb            ldr     r3, [r7, #12]
8402:       3302            adds    r3, #2
8404:       60fb            str     r3, [r7, #12]
8406:       e013            b.n     8430 <main+0x74>
8408:       68fb            ldr     r3, [r7, #12]
840a:       3303            adds    r3, #3
840c:       60fb            str     r3, [r7, #12]
840e:       e00f            b.n     8430 <main+0x74>
8410:       68fb            ldr     r3, [r7, #12]
8412:       3306            adds    r3, #6
8414:       60fb            str     r3, [r7, #12]
8416:       e00b            b.n     8430 <main+0x74>
8418:       68fb            ldr     r3, [r7, #12]
841a:       3308            adds    r3, #8
841c:       60fb            str     r3, [r7, #12]
841e:       e007            b.n     8430 <main+0x74>
8420:       68fb            ldr     r3, [r7, #12]
8422:       330a            adds    r3, #10
8424:       60fb            str     r3, [r7, #12]
8426:       e003            b.n     8430 <main+0x74>
8428:       68fb            ldr     r3, [r7, #12]
842a:       3357            adds    r3, #87 ; 0x57
842c:       60fb            str     r3, [r7, #12]
842e:       bf00            nop
8430:       68fb            ldr     r3, [r7, #12]
8432:       4618            mov     r0, r3
8434:       3714            adds    r7, #20
8436:       46bd            mov     sp, r7
8438:       f85d 7b04       ldr.w   r7, [sp], #4
843c:       4770            bx      lr
843e:       bf00            nop

Observations:

• Data words store the absolute target addresses of the switch table not offsets.
• The indirect branch is implemented using ldr.w pc, [base, index, lsl #2] where base (here r2) stores the address of the beginning of data words and index (here r3) is used to calculate the offset.

Questions:

1. Can the aforementioned observations be generalized? in other words, can I assume the this is the (de-facto) standard way for (most) ARM compilers to implement switch statements?
2. Why are the addresses stored in data words odd? I can't see any mode switching between ARM/Thumb here. For example, the default case can be found at 0x8428 but the corresponding address is stored as 0x00008429.

Answer 1

No, you can't assume that's how most ARM compilers will implement switch statements. For example, here's gcc 5.2.1 on that same code:

cosimo:~ moyix$ arm-none-eabi-gcc-5.2.1 -o3 -mthumb -c x.c -o x.o
cosimo:~ moyix$ arm-none-eabi-objdump -d x.o

x.o:     file format elf32-littlearm


Disassembly of section .text:

00000000 <main>:
   0:   b580        push    {r7, lr}
   2:   b084        sub sp, #16
   4:   af00        add r7, sp, #0
   6:   6078        str r0, [r7, #4]
   8:   6039        str r1, [r7, #0]
   a:   2300        movs    r3, #0
   c:   60fb        str r3, [r7, #12]
   e:   687b        ldr r3, [r7, #4]
  10:   2b07        cmp r3, #7
  12:   d81d        bhi.n   50 <main+0x50>
  14:   687b        ldr r3, [r7, #4]
  16:   009a        lsls    r2, r3, #2
  18:   4b13        ldr r3, [pc, #76]   ; (68 <main+0x68>)
  1a:   18d3        adds    r3, r2, r3
  1c:   681b        ldr r3, [r3, #0]
  1e:   469f        mov pc, r3
  20:   68fb        ldr r3, [r7, #12]
  22:   3301        adds    r3, #1
  24:   60fb        str r3, [r7, #12]
  26:   e017        b.n 58 <main+0x58>
  28:   68fb        ldr r3, [r7, #12]
  2a:   3302        adds    r3, #2
  2c:   60fb        str r3, [r7, #12]
  2e:   e013        b.n 58 <main+0x58>
  30:   68fb        ldr r3, [r7, #12]
  32:   3303        adds    r3, #3
  34:   60fb        str r3, [r7, #12]
  36:   e00f        b.n 58 <main+0x58>
  38:   68fb        ldr r3, [r7, #12]
  3a:   3306        adds    r3, #6
  3c:   60fb        str r3, [r7, #12]
  3e:   e00b        b.n 58 <main+0x58>
  40:   68fb        ldr r3, [r7, #12]
  42:   3308        adds    r3, #8
  44:   60fb        str r3, [r7, #12]
  46:   e007        b.n 58 <main+0x58>
  48:   68fb        ldr r3, [r7, #12]
  4a:   330a        adds    r3, #10
  4c:   60fb        str r3, [r7, #12]
  4e:   e003        b.n 58 <main+0x58>
  50:   68fb        ldr r3, [r7, #12]
  52:   3357        adds    r3, #87 ; 0x57
  54:   60fb        str r3, [r7, #12]
  56:   46c0        nop         ; (mov r8, r8)
  58:   68fb        ldr r3, [r7, #12]
  5a:   0018        movs    r0, r3
  5c:   46bd        mov sp, r7
  5e:   b004        add sp, #16
  60:   bc80        pop {r7}
  62:   bc02        pop {r1}
  64:   4708        bx  r1
  66:   46c0        nop         ; (mov r8, r8)
  68:   00000000    .word   0x00000000

And there are more complex schemes possible, including things like binary search on the switch value to find the right case. In general you need to do a more complex analysis to recover switch statements. Some academic work exists on this topic, e.g.:

http://www.cs.tufts.edu/~nr/cs257/archive/cristina-cifuentes/switch-proof.pdf

As to your second question, jumps using ldr pc must explicitly specify the mode. Since you compiled the code with -mthumb, you're in thumb mode, and to stay in thumb mode those addresses need to have bit 0 set to 1 (see note [a] on this page).