Linking is taking a bunch of library binaries and gluing them together into a new file.

Loading is taking a binary or multiple binaries and loading it into memory so you can run it.

They are related tasks (both are transferring binaries from one place to another and doing some hooking together), but to some degree it is conceptually unfortunate that the concepts run over each other.


Sections are for linking.


Segments are for loading. Load time view

readelf -l /bin/ls

Symbol Table

A key value mapping

objdump -t

local global weak

default hidden


relocation Relocations are “fixups” to the binary. There is a list of possible ones. The name comes from relocatable values or something. A memory address you don’t currently know. But the mechanism can get used for more things. Some relocations look for the keys coming in from the symbol table and do something with the corresponding value.

understanding relocations

Relocating Machine Instructions by Currying Norman Ramsey

a instruction is a parametrized function that outputs binary.

type insn = params -> bytes

Defunctionalizing these lambdas produces the first order form of ordinary relocation data.

Loading small elf loader VDL: Virtualizing Dynamic Linker/Loader

Auxiliary vector getauxval and the axiliary vector LD_SHOW_AUXV=1 fs/binfmt_elf.c loads elf in kernel

 od -t d8 /proc/self/auxv

Userland exec - grugq use python to gather data, then construct an assembly program to call the appropriate sequence of unmap and map calls

man execve

              [ 0 ]  <-- top of the stack
              [ envp strings ]
              [ 0 ]
              [ argv strings ]
              [ 0 ]
              [ auxv ]
              [ 0 ]
              [ envp ]
              [ 0 ]
              [ argv ]
              [ argc ] <-- stack pointer
  1. cleanup memory. People look at /proc/self for introspection /proc/self/maps
ls /sys

Dynamic Linking minimal dynamic linker implementation for ELF, supporting x86_64 and Arm/Aarch64

man elf

objdump -R for dynamic relocations readelf -r

DSO - dynamic shared object

how to write shared libraries

Better understanding Linux secondary dependencies solving with examples Shared Libraries: Understanding Dynamic Loading

The .dynamic section of the elf file is symbols to look for at runtime. readelf -d and objdump -T If the library file found during the ocmpile process has .so it is linked at load time.

ldd lists dynamic dependencies recursively.

For some purposes you really link during program execuction. For example if you’re JIT compiling this might be a way to do it. #include <dlfcn.h>

  • dlopen(libname, flags)
  • dlsym(handle, symbolname) looks up symbol name by string dlmopen

  • LD_DEBUG=help cat This is crazy. This exists?
LD_SHOW_AUXV=1 /bin/true


vdso - overview of the virtual ELF dynamic shared object Sort of a kernel provided dynamic linked object to avoid kernel call overheads

plt got

GOT global offset table - table holding global variables PLT - procedure linkage table - table holding function pointers got.plt

Compilation Units

A compilation unit is a large scale statement. Building a cu is a partial evaluation of a kind.

type env = ? String.Map.t (* symbol mappings *)
type cu = stmt = env -> env * bin
val interp: elf -> env -> env * bin

the linker is an interpreter over the elf format.

Is bin free floating or anchored at particular addresses. position independent code or not.

Link Time Optimization

Tree Shaking Debloating “smart linking” dead code elimination. Linking is “finishing” compilation, or it is compilation in the large

debloating is framed as a cybersecurity hardening sometimes

Linking Formats

Some of what makes linking formats so confusing is that they are binary representations of structured data. I am more used to thinking about the data structure and it’s serialization more separately. So many of the fields are indices and sizes of other fields. It’s also kind of flattened, in a similar way you might flatten to put something into a relational database.

In a curious way, if you are accessing these formats from C, it’s actually easier to use them than a textual format. There is no parsing necessary. You memory map in the file and just immediately interpret bytes as their appropriate structs. This does seem fraught with peril to me though.

  • elf - linux
  • stabs - old?
  • PE - windows
  • Mach-o - mac


witchcraft compiler collction “unlinks” executables back into libraries. How?

The missing link: explaining ELF static linking, semantically a fantastic paper on a formalization of elf and linking generally

man elf on your system will give you a whole spiel

The elf spec

#include <elf.h> will bring in the elf header file from your system. It isn’t persay that difficult to parse elf from within C. Everywhere else it sucks.


pyelftools can read elf from python.

The Lief library is useful for manipulating formats

A lot of stuff is powered by

Core files

/proc/kcore is a core file of the kernel memory


Not linking persay. But some useful stuff for manipulating object files

  • redefine-sym --redefine-syms


Linker scripts

linker scripts for firmware linker script guide most throughly commented linker script linker script

LMA vs VMA load memoery address vs virtual memory address. Can differe when stored in romvs ram for example

man ld
info ld
ld --help

-q emit relocs -Wl forwards commands to linker in gcc –entry

echo '
.extern _start
  mov $0x42, %rax
  jmp fred
' > /tmp/tmp.s
as /tmp/tmp.s -o /tmp/tmp.o
readelf -a /tmp/tmp.o

# Relocation 
Relocation section '.rela.text' at offset 0xa8 contains 1 entry:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000008  000200000004 R_X86_64_PLT32    0000000000000000 fred - 4

Symbol table '.symtab' contains 3 entries:
   Num:    Value          Size Type    Bind   Vis      Ndx Name
     0: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000000000000000     0 NOTYPE  LOCAL  DEFAULT    1 _start
     2: 0000000000000000     0 NOTYPE  GLOBAL DEFAULT  UND fred
objdump -d /tmp/tmp.o
echo "
. = 0x10000;
.text : { *(.text) }
. = 0x8000000;
.data : { *(.data) }
.bss : { *(.bss) }
" > /tmp.mylink.ld

DWARF dwarf explorer gui based on pyelftools

LLVM has DIBuilder in C++ but also textual access to dwarf dwarf 6 suggestins. nteresting

echo "
int fact(int x){
    if(x == 0) return 1;
    return x * fact(x-1);
}" > /tmp/fact.c
clang -g -O1 -emit-llvm -S -c /tmp/fact.c -o /tmp/fact.ll
cat /tmp/fact.ll
echo "


Take dwarf from binary and splice in

echo "
int fact(int n) {
  int acc = 1;
  for(int i = 0; i < n; i++) {
      acc *= i;
  return acc;
" > /tmp/fact.c
gcc -g -c /tmp/fact.c -o /tmp/fact.o
readelf -w /tmp/fact.o
from elftools.elf.elffile import ELFFile
from elftools.elf.sections import SymbolTableSection
from collections import defaultdict
import posixpath

def lpe_filename(line_program, file_index):
    # Retrieving the filename associated with a line program entry
    # involves two levels of indirection: we take the file index from
    # the LPE to grab the file_entry from the line program header,
    # then take the directory index from the file_entry to grab the
    # directory name from the line program header. Finally, we
    # join the (base) filename from the file_entry to the directory
    # name to get the absolute filename.
    lp_header = line_program.header
    file_entries = lp_header["file_entry"]

    # File and directory indices are 1-indexed.
    file_entry = file_entries[file_index - 1]
    dir_index = file_entry["dir_index"]

    # A dir_index of 0 indicates that no absolute directory was recorded during
    # compilation; return just the basename.
    if dir_index == 0:

    directory = lp_header["include_directory"][dir_index - 1]
    return posixpath.join(directory,
def line_entry_mapping(line_program):
    filename_map = defaultdict(int)

    # The line program, when decoded, returns a list of line program
    # entries. Each entry contains a state, which we'll use to build
    # a reverse mapping of filename -> #entries.
    lp_entries = line_program.get_entries()
    for lpe in lp_entries:
        # We skip LPEs that don't have an associated file.
        # This can happen if instructions in the compiled binary
        # don't correspond directly to any original source file.
        if not lpe.state or lpe.state.file == 0:
        filename = lpe_filename(line_program, lpe.state.file)
        filename_map[filename] += 1

    for filename, lpe_count in filename_map.items():
        print("    filename=%s -> %d entries" % (filename, lpe_count))

def dump_dwarf(filename):
  with open(filename, "rb") as f:
      elffile = ELFFile(f)
      if not elffile.has_dwarf_info():
          print('  file has no DWARF info')
      dwarfinfo = elffile.get_dwarf_info()
      for CU in dwarfinfo.iter_CUs():
          print('  Found a compile unit at offset %s, length %s' % (
              CU.cu_offset, CU['unit_length']))

          # Every compilation unit in the DWARF information may or may not
          # have a corresponding line program in .debug_line.
          line_program = dwarfinfo.line_program_for_CU(CU)
          if line_program is None:
              print('  DWARF info is missing a line program for this CU')

          # Print a reverse mapping of filename -> #entries

from elftools.elf.elffile import ELFFile
from elftools.dwarf.descriptions import describe_DWARF_expr, set_global_machine_arch, describe_reg_name

def get_file_line_column(die, dwarfinfo, cu):
    decl_file = die.attributes.get('DW_AT_decl_file')
    decl_line = die.attributes.get('DW_AT_decl_line')
    decl_column = die.attributes.get('DW_AT_decl_column')

    if decl_file:
        file_index = decl_file.value
        file_name = dwarfinfo.line_program_for_CU(cu).header['file_entry'][file_index - 1].name.decode('utf-8')
        file_name = 'Unknown'

    line_number = decl_line.value if decl_line else 'Unknown'
    column_number = decl_column.value if decl_column else 'Unknown'

    return file_name, line_number, column_number

def process_file(filename):
    with open(filename, 'rb') as f:
        elffile = ELFFile(f)

        if not elffile.has_dwarf_info():
            print("No DWARF info found in the file.")

        dwarfinfo = elffile.get_dwarf_info()

        for CU in dwarfinfo.iter_CUs():
            for DIE in CU.iter_DIEs():
                if DIE.tag in ['DW_TAG_label', 'DW_TAG_variable']:
                    var_name = DIE.attributes['DW_AT_name'].value.decode('utf-8')
                    file_name, line_number, column_number = get_file_line_column(DIE, dwarfinfo, CU)

                    if DIE.tag == 'DW_TAG_variable':
                        location = DIE.attributes.get('DW_AT_location')
                        if location and location.value:
                            loc_expr = describe_DWARF_expr(location.value, dwarfinfo.structs)
                            opcode = location.value[0]
                            # Assuming DW_OP_regx opcodes are in the range 0x50 to 0x6f (inclusive)
                            if 0x50 <= opcode <= 0x6f:
                                register_name = describe_reg_name(opcode, dwarfinfo.config)
                                location_info = f'Register {register_name}'
                                location_info = loc_expr
                            location_info = 'Unknown'
                        location_info = 'N/A for labels'

                    print(f'Type: {DIE.tag}, Name: {var_name}, File: {file_name}, Line: {line_number}, Column: {column_number}, Location: {location_info}')

process_file('/tmp/fact.o') # Replace with your ELF file name

Incomplete Debug Information testing for incompleteness of debug info Debug info unwind tables

dwarfwrite python

read-dwarf use dwarf data and Sail / C symbolic execturo to establish bisimulation

ORC unwind tables in kernel

Reliable and Fast DWARF-Based Stack Unwinding

dwarf too unreliable, back to frame pointers

How debuggers work: Part 3 - Debugging information

gimli a rust library for reading and writing dwarf

C++ uses drawf unwind tables to implement exceptions

  • .debug_line maps addresses to source code lines
  • .debug_info maps source variables to registers and stack locations
  • .eh_frame maps address location return address and callee saved registers info. “exception handling”

DWARF encodes using bytecode. CFA - canonical frame address FDE - frame description entity I suppose the dwarf bytecode is kind of a uniform abstraction of the code itself? Only replicating instructions that change frame information?

I don’t know what these are

Exploitng the hard working dwarf video

dwarf debug format .loc directive outputs into debug_lines table

pyelftools can read dwarf data

Introduction to the DWARF Debugging Format

dwarf standard

DIE - debugging information entry .debug_info field Tons of possible tags

Dwarf expressions are stack machine based. They give the ability to compute values based on machine state. The mapping of dwarf registers to machine registers is archtecture specific

Each DIE has a tag and attributes

Chapter 4

  • DW_TAG_variable
  • DW_TAG_formal_parameter function call parameters
  • DW_TAG_constant

These have attribtures DW_AT_name DW_AT_type DW_AT_location which are the most interesting

You can get line number and column info from dwarf

gcc flags related to debugging

  • -Og


linker koans

link c by hand

.PHONY: run
 gcc -c main.c -o main.o
 ar rs main.a main.o
 ld  -o success.out /usr/lib/x86_64-linux-gnu/Scrt1.o  /usr/lib/x86_64-linux-gnu/crti.o /usr/lib/gcc/x86_64-linux-gnu/11/crtbeginS.o -L/usr/lib/gcc/x86_64-linux-gnu/11 -L/usr/lib/x86_64-linux-gnu -L/lib/x86_64-linux-gnu -L/usr/lib/x86_64-linux-gnu -L/usr/lib/  main.a  -lc /usr/lib/gcc/x86_64-linux-gnu/11/crtendS.o --dynamic-linker=/lib64/


Succinct Explanation:

the linker algorithm is this:

def link(archives: List[Library]):
  unresolved_refs = set(["_start"])
  resolved_refs = set()
  for archive in archives:
    # if we have a ref in this archive that is 
    # currently unresolved, then this archive is useful.
    is_used = 
     any([ref in unresolved_ref
           for ref in def # get all references from def.
             for def in archive])
    if not is_used: continue
    # INVARIANT: if we enter here, this this means that *at least*
    #   one unresolved ref will be resolved.
    for def in archive:
      # we only add those defs that were unresolved.
      if def not in unresolved_refs: continue
      resolved_refs.add(def) # this defn is resolved.
      unresolved_refs.remove(def) # this defn is resolved.
      for ref in def:
        if ref not in resolved_refs: # we have not resolved this ref yet.
          unresolved_refs.add(def) # add to resolution worklist.
- This means we might need to link twice to resolve call chains:
gcc main.o -lfoo -lbar -lfoo -lbar -lfoo
- We can also use `--start-group` and `--end-group` to demarcate such mutual inclusion. 2-pass linkers

sRDI - Shellcode Reflective DLL Injection

I wrote a linker everyone can understand!

Pascal linker

Surfing With The Linker Aliens: Solaris Linking & ELF Blogs

packer tutorial

N. Glew and G. Morrisett. Type-Safe Linking and Modular Assembly Language

stephen kell - interopability ld has a plugin interface. Cool linker links

knit linking language

flux object files are objects statc and dynamic structures follow design patterns

newspeak cut out static state

The ABI status of ELF hash tables

redbean justine. Cosmopolitan. APE

ld - linker editor

oracle linker guide

armlink user guide A different flavor. Some interesting optimization options “veneer” as chunks of linker produced code.

mold talks about arm thunks for long jumps veneers, risc v does opposite, shrinks long jumps into short jumps. rv5 abi allows this in ways arm doesnt? What does that mean veneer linker relacation on rv5

mold design notes very interesting. performance tricks, history of linker features The teensy files - writing elf by hand On ELF, Part 2 - a ctrique of elf for being too complex compared to previous formats and for little gain. Counterpoints Assembler and loaders - David Salomon compcert linking file This file follows “approach A” from the paper “Lightweight Verification of Separate Compilation” by Kang, Kim, Hur, Dreyer and Vafeiadis, POPL 2016. Cody tweeting about it

APE - Actually portable executable, Cosmopolitan library geometry of interaction stuff. Neel Krinshnasawmi

Dwarf - it’s like complicated. But there is a lot in there.

addr2line and other binutils libdwarf. dwarfdump - lots of interesting stuff on linkers, elf, other - his small linker. Uses ocaml? - generates ocaml?

ld_preload hacking Hmm. So one thing you can do is mock out functions for testing. That’s nice referenced guide on how to write dynamic linker

ryan oneill elfmaster silvio text segement padding SCOP padding secure cide oartitioning PT_LOAD insertion - “learning linux binary analysis” book. reverse text extension techniuqe github elfmaster - skeski virus, dt data segment insertion - “learning linux binary analysis” dt_needed override dt_infect. dynamic segment .got.plt infection ymbol string redirection - global data in the .got elf binary control flow hooks, function trampolines, function pointer hooks, breakpoint hnadlerh ook, tls resolver, sigill handler

ptrace , injecting a loader


  • the author of gold, Ian Lance Taylor’s 20 part Linker posts V good

Symbols - Types and values? Relocations - Bits of code that runs in general? Kind of bytecode?

Executable config files - dhall. Others. Kaitai has executable aspects. if then else, others.

Functional models of linking

type fixups/relocs = Mov | Add | ?

    relocs: fixups
    symbols: {name : string ; typ : typ;  value : value}list
    contents: { section : name; contents : string }

bap’s model

type name = [
  | `tid of tid
  | `addr of addr
  | `symbol of string
] [@@deriving bin_io, compare, sexp]

type exn += Unbound_name of name

module type Code = functor (Machine : Machine) -> sig
  val exec : unit Machine.t

type code = (module Code)

(* the same piece of code can be referred via multiple names *)
type refs = {
  term : tid option;
  name : string option;
  addr : addr option;

type t = {
  codes : code Int.Map.t;
  alias : refs Int.Map.t;
  terms : int Tid.Map.t;
  names : int String.Map.t;
  addrs : int Addr.Map.t;

Maybe one way of thinking about it is pairs of interpolation strings and a symbol dictionary. We collect up symbols and strings (binaries) and concat them together. Then eventually we inline the appropriate symbols.

It’s fun how string interpolation is a cute toy model of interesting things like macros.

mod1 = "{foo} {bar}", {biz: 3}
mod2 = " {biz} ", {foo : 4, bar : "hi"}

def link(mod1,mod2):
  b1, sym1 = mod1
  b2, sym2 = mod2
  b1 + b2, sym1 + sym2

def finalize(mod):
  b, sym = mod

Ramsey’s relocation by currying makes one want to use lambdas rather than named representation of strnig interpolation.

mod1 = lambda foo, bar: f"{foo} {bar}", {biz ; 3}

The string interpolation pair is rather evocative of a closure

mod1 = lambda file, offset, **kwargs:  write(file, "{foo} {bar}".format(kwargs)) , 30 , {biz : "fred"} 

Typical relocations can be seen as simple bytecode instuctions / defunctionalization of general purpose concepts This is the ocaml data format of cmo files

JT’s notes

ld has default linker script ld --verbose to see -T linker script (manual)

SECTION : set current address. tell what sections from different files to include.


So could I use a linker script to build a computation? By wiring together input and output cells?

Here’s an interesting challenge: linking verification Verify a relational property that after linking the program still does the same thing. Requires a model of linking and patching requires fixups maybe you could have the loader actually do its work and pop in by peeking at /proc/mem Or maybe ld_preload ? You’d want a total program verification. In principle the problem is easy? There is link level modulairty there. So maybe that’s good