Before exposing my problem, here's my understanding of the whole thing, so that you may correct me if I'm saying something wrong.

In a Mach-O file (at least on x86), the __TEXT.__stubs section typically has stubs in it that all consist of a single indirect jump, like this:

; __TEXT.__stubs
; symbol stub for unlink:
0x100000f46:  jmpq   *0xc4(%rip)
; symbol stub for puts:
0x100000f4c:  jmpq   *0xc6(%rip)

These point to a location inside the __DATA.__nl_symbol_ptr section. The pointer initially goes to a stub helper in the __TEXT.__stub_helper section:

; __TEXT.__stub_helper
; stub helper for unlink
0x100000f64:  pushq  $0x0
0x100000f69:  jmp    0x100000f54
; stub helper for puts
0x100000f6e:  pushq  $0xe
0x100000f73:  jmp    0x100000f54

The stub helper calls dyld_stub_binder, which uses the pushed argument to figure out which stub it is and which function it needs to look up, then replaces the value in __DATA.__nl_symbol_ptr with the resolved address, and then hand over control to the function that was found (which then returns to the calling code normally).

To assist debugging, debuggers find stubs and pretend that they have symbols for them. In this example program, whenever lldb sees call 0x100000f58, it determines that the stub should point to unlink, and says call 0x100000f58 ; symbol stub for: unlink in the disassembly.

However, lldb does not use the pushed value: it appears to rely on the static linker placing undefined symbols and stubs in the same order, or some variant of that. Just like that, it looks more like a heuristic than a precise way to figure out which stub goes where, unless there's something else preventing you from tampering.

So how do I reliably find which function is called by a stub? In the stub helpers, what do the constants in pushq $constant mean?

the numeric argument is is an offset into the "compressed dyld info" stream of bytecodes. see https://stackoverflow.com/a/8836580 (iOS/arm but still applies)

  • 2
    As this question has been viewed over 500 times, here's an implementation of a bytecode decoder that I wrote not long ago. – zneak Nov 28 '16 at 2:57
  • 1
    @zneak: nice, maybe you can write up a more detailed explanation as an answer so that other people know the details? I don't mind if you un-accept my answer for that. – Igor Skochinsky Nov 28 '16 at 8:48
up vote 2 down vote accepted

I wrote a Python script that parses entry points and imports from a Mach-O executable for one of my projects. The trick is to parse the LC_DYLD or LC_DYLD_ONLY loader commands. These two commands encode three import tables: bound symbols, weak symbols, and lazy symbols.

struct dyld_info_command {
  uint32_t cmd;
  uint32_t cmdsize;
  uint32_t rebase_off;
  uint32_t rebase_size;
  uint32_t bind_off;
  uint32_t bind_size;
  uint32_t weak_bind_off;
  uint32_t weak_bind_size;
  uint32_t lazy_bind_off;
  uint32_t lazy_bind_size;
  uint32_t export_off;
  uint32_t export_size;
};

The interesting fields are bind_off, bind_size, weak_bind_off, weak_bind_size, lazy_bind_off and lazy_bind_size. Each pair encodes the offset and size of a block of data, inside the executable file, that contains the import table opcodes.

Each of these tables can be seen as having four (useful) columns: the segment, segment offset, library name and symbol name. Together, the segment and segment offset indicate the address where the symbol's actual address will be written to (so for instance, if you have __TEXT and 0x40, this conceptually means that *(__TEXT+0x40) == resolvedSymbolAddress).

The table is encoded as a stream of opcodes for compression purposes. The opcodes control a state machine that contains state for a would-be symbol, has operations to manipulate that state, and operations to "bind" a symbol (take all that state and make it a part of the symbol table). For instance, you could see:

  • set segment to __TEXT
  • set offset to 0x40
  • set library to libSystem.dylib
  • set symbol name to "printf"
  • bind symbol
  • set offset to 0x48
  • set symbol name to "scanf"
  • bind symbol

At the end of this sequence, you get two symbols: printf and scanf, whose addresses are located at __TEXT+0x40 and __TEXT+0x48 respectively, from libSystem.dylib. This means that if you see an instruction like jmp [__TEXT+0x48] (an indirect jump to the address contained at __TEXT+0x48), you know that you're going to scanf. This is how you can tell the destination of stubs.

Each opcode is at least 1 byte, separated as 0xCI (where C is the command name, and I is an immediate value, both 4 bits). When the command needs a larger operand (or more operands), they are encoded in ULEB-128 format (except for BIND_OPCODE_SET_ADDEND_SLEB, which uses signed LEB, but we don't really care about it for the purpose of finding imports).

def readUleb(data, offset):
    byte = ord(data[offset])
    offset += 1

    result = byte & 0x7f
    shift = 7
    while byte & 0x80:
        byte = ord(data[offset])
        result |= (byte & 0x7f) << shift
        shift += 7
        offset += 1
    return (result, offset)

Libraries aren't actually identified by their names in the command stream. Rather, libraries are identified by their one-based "library ordinal", which is just the index of the library within all the LC_LOAD_DYLIB, LC_LOAD_WEAK_DYLIB, LC_REEXPORT_DYLIB and LC_LOAD_UPWARD_DYLIB loader commands. For instance, if an executable has a LC_LOAD_DYLIB command for libSystem and then one for libFoobar, libSystem has ordinal 1 and libFoobar has ordinal 2.

There are three special values: ordinal -2 means that the symbol is looked up in the flat namespace (first library with a symbol with that name wins); ordinal -1 looks for a symbol in the main executable, whatever it is; and ordinal 0 looks for a symbol within this file. As we've said above, ordinal 1 and above refer to libraries.

Symbol names are encoded within the command blob as null-terminated strings.

Each opcode is easily described in code, so I'll spare us the description of each.

BIND_OPCODE_DONE = 0
BIND_OPCODE_SET_DYLIB_ORDINAL_IMM = 1
BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB = 2
BIND_OPCODE_SET_DYLIB_SPECIAL_IMM = 3
BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM = 4
BIND_OPCODE_SET_TYPE_IMM = 5
BIND_OPCODE_SET_ADDEND_SLEB = 6
BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB = 7
BIND_OPCODE_ADD_ADDR_ULEB = 8
BIND_OPCODE_DO_BIND = 9
BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB = 10
BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED = 11
BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB = 12

def parseImports(self, offset, size):
    pointerWidth = self.bitness / 8
    slice = self.data[offset:offset+size]
    index = 0

    name = ""
    segment = 0
    segmentOffset = 0
    libOrdinal = 0

    stubs = []
    def addStub():
        stubs.append((segment, segmentOffset, libOrdinal, name))

    while index != len(slice):
        byte = ord(slice[index])
        opcode = byte >> 4
        immediate = byte & 0xf
        index += 1

        if opcode == BIND_OPCODE_DONE:
            pass
        elif opcode == BIND_OPCODE_SET_DYLIB_ORDINAL_IMM:
            libOrdinal = immediate
        elif opcode == BIND_OPCODE_SET_DYLIB_ORDINAL_ULEB:
            libOrdinal, index = self.__readUleb(slice, index)
        elif opcode == BIND_OPCODE_SET_DYLIB_SPECIAL_IMM:
            libOrdinal = -immediate
        elif opcode == BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM:
            nameEnd = slice.find("\0", index)
            name = slice[index:nameEnd]
            index = nameEnd
        elif opcode == BIND_OPCODE_SET_TYPE_IMM:
            pass
        elif opcode == BIND_OPCODE_SET_ADDEND_SLEB:
            _, index = self.__readUleb(slice, index)
        elif opcode == BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
            segment = immediate
            segmentOffset, index = self.__readUleb(slice, index)
        elif opcode == BIND_OPCODE_ADD_ADDR_ULEB:
            addend, index = self.__readUleb(slice, index)
            segmentOffset += addend
        elif opcode == BIND_OPCODE_DO_BIND:
            addStub()
        elif opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
            addStub()
            addend, index = self.__readUleb(slice, index)
            segmentOffset += addend
        elif opcode == BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
            addStub()
            segmentOffset += immediate * pointerWidth
        elif opcode == BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
            times, index = self.__readUleb(slice, index)
            skip, index = self.__readUleb(slice, index)
            for i in range(times):
                addStub()
                segmentOffset += pointerWidth + skip
        else:
            sys.stderr.write("warning: unknown bind opcode %u, immediate %u\n" % (opcode, immediate))
  • 1
    One addition: the list of libraries includes not only LC_LOAD_DYLIB commands but also LC_LOAD_WEAK_DYLIB, LC_REEXPORT_DYLIB, LC_LAZY_LOAD_DYLIB and LC_LOAD_UPWARD_DYLIB (see dyld sources) – Igor Skochinsky Nov 29 '16 at 18:27
  • Also, just now found this page: newosxbook.com/articles/DYLD.html – Igor Skochinsky Nov 29 '16 at 18:28
  • I'll look into it later and update the script/answer. Thanks! – zneak Nov 29 '16 at 18:30

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.