Project 10: PLT/GOT Relocation Resolver

A tool that inspects PLT/GOT entries and resolves which symbols they correspond to.

Quick Reference

Attribute Value
Difficulty Level 4
Time Estimate 3-4 weeks
Main Programming Language Python or C (Alternatives: Rust, Go)
Alternative Programming Languages Rust, Go
Coolness Level Level 4
Business Potential 2
Prerequisites Object Files, Linking, and Relocations, Object Files, Linking, and Relocations
Key Topics Object Files, Linking, and Relocations, Object Files, Linking, and Relocations

1. Learning Objectives

By completing this project, you will:

  1. Explain why plt/got relocation resolver reveals key x86-64 behaviors.
  2. Build a deterministic tool with clear, inspectable output.
  3. Validate correctness against a golden reference output.
  4. Connect the tool output to ABI and architecture rules.
  5. Dynamic linking is central to real-world binaries and relies on relocation mechanics.

2. All Theory Needed (Per-Concept Breakdown)

Object Files, Linking, and Relocations

Fundamentals Object files are containers for machine code, data, symbols, and relocation information. The linker merges object files into executables or shared libraries, resolving symbols and applying relocations. x86-64 systems primarily use ELF on Linux and macOS (Mach-O on macOS) and PE on Windows. The System V ABI defines the general ABI and the x86-64 psABI specifies details for ELF. Understanding sections, symbols, and relocations is required for interpreting binaries, debugging linking errors, and building tooling that inspects executables. (Sources: System V gABI, System V AMD64 ABI, Linux Foundation refspecs)

Deep Dive The object file is the bridge between assembly and execution. It holds code and data in sections, along with metadata that tells the linker how to connect references across compilation units. A symbol is a named addressable entity: a function, a global variable, or a section. Relocations are placeholders that tell the linker or loader to adjust addresses when the final layout is known. Without relocation, code would need fixed addresses and would not be portable or shareable.

In ELF, sections such as .text, .data, and .bss hold code and data. The section headers describe offsets, sizes, and flags. The symbol table maps symbol names to section offsets and attributes. Relocation entries refer to symbols and specify how to patch the code or data. The relocation types indicate whether a relocation is absolute, PC-relative, or uses a GOT/PLT indirection. The x86-64 psABI defines these relocation types and their semantics, which is essential for interpreting dynamic linking and position-independent code.

The linker performs symbol resolution: it decides which definition of a symbol to use and patches references accordingly. Static linking resolves all symbols at link time. Dynamic linking defers some resolution to runtime, using the dynamic loader and data structures such as the Global Offset Table (GOT) and Procedure Linkage Table (PLT). The GOT holds addresses of global symbols and is updated by the loader. The PLT provides a stub that jumps through the GOT, enabling lazy binding. This mechanism is central to shared libraries and is a common target for debugging and security analysis.

PE on Windows uses a different layout but similar ideas: sections, import tables, and relocation entries. The import table lists external functions that must be resolved at load time. Base relocations allow the loader to rebase the executable if it cannot be loaded at the preferred address. While the details differ, the mental model is the same: object files are templates, and the loader fills in the addresses.

Relocations also matter for reverse engineering. If you see a relocation against a symbol, you know that the code depends on that symbol even if the address is not fixed. This is how tools recover call graphs and identify external dependencies. It is also how you can locate jump tables, vtables, and other data-driven control flow constructs.

Finally, debugging symbols and unwind info live alongside code in the object file. These sections are optional but invaluable for debugging and profiling. Understanding them helps you build tools that can show file/line information, variable locations, and call stacks, even in optimized binaries.

How this fits on projects

  • Projects 9 and 10 are focused on ELF/PE parsing and relocation resolution.
  • Project 6 uses unwind metadata to visualize stack frames.

Definitions & key terms

  • Object file: Compiled code and metadata before linking.
  • Section: A region of an object file with a specific purpose.
  • Symbol: Named reference to code or data.
  • Relocation: A patch applied by the linker or loader.
  • GOT/PLT: Indirection tables for dynamic linking.

Mental model diagram

SOURCE -> OBJECT (.o) -> LINKER -> EXECUTABLE -> LOADER -> RUNNING

OBJECT:
  [ .text ] [ .data ] [ .bss ] [ .symtab ] [ .rel.* ]

LINKER:
  resolve symbols + apply relocations

LOADER:
  map segments + resolve dynamic relocations

How it works

  1. Compiler/assembler emits object file with symbols and relocations.
  2. Linker merges sections and resolves symbols.
  3. Linker applies relocations or marks them for runtime.
  4. Loader maps segments and resolves dynamic relocations.

Invariants and failure modes:

  • Invariant: Relocations reference valid symbols.
  • Failure: Missing symbols cause link errors or runtime crashes.
  • Invariant: Section permissions match content (code vs data).
  • Failure: Incorrect permissions can cause execution faults.

Minimal concrete example (pseudo-structure)

# PSEUDOCODE ONLY
SECTION .text:
  CALL SYMBOL_F
RELOCATION:
  at .text+0x10 -> SYMBOL_F (PC_REL)

Common misconceptions

  • “Linking is just concatenation.” It includes symbol resolution and relocation.
  • “GOT/PLT is only for performance.” It is required for dynamic linking.
  • “Object files are the final executable.” They are templates.

Check-your-understanding questions

  1. Why do relocation entries exist at all?
  2. What problem does the PLT solve?
  3. How does a loader differ from a linker?

Check-your-understanding answers

  1. Addresses are not final until link or load time.
  2. It enables lazy binding of external functions.
  3. The linker combines objects; the loader maps and relocates at runtime.

Real-world applications

  • Diagnosing link errors and symbol conflicts
  • Reverse engineering binary dependencies
  • Building binary inspection tools

Where you will apply it Projects 6, 9, 10

References

  • System V ABI / gABI (Linux Foundation refspecs)
  • System V AMD64 ABI Draft 0.99.7
  • “Computer Systems: A Programmer’s Perspective” by Bryant and O’Hallaron - Ch. 7

Key insights Relocations and symbols are the invisible glue that makes binaries runnable.

Summary Understanding object files and linking turns binaries from opaque blobs into structured systems.

Homework/Exercises to practice the concept

  • Sketch the sections of a minimal object file and label their purpose.
  • Explain how a call to an external function is resolved.

Solutions to the homework/exercises

  • Include .text, .data, .bss, .symtab, and relocation sections.
  • Linker or loader patches a placeholder using relocation info.

    Object Files, Linking, and Relocations

Fundamentals Object files are containers for machine code, data, symbols, and relocation information. The linker merges object files into executables or shared libraries, resolving symbols and applying relocations. x86-64 systems primarily use ELF on Linux and macOS (Mach-O on macOS) and PE on Windows. The System V ABI defines the general ABI and the x86-64 psABI specifies details for ELF. Understanding sections, symbols, and relocations is required for interpreting binaries, debugging linking errors, and building tooling that inspects executables. (Sources: System V gABI, System V AMD64 ABI, Linux Foundation refspecs)

Deep Dive The object file is the bridge between assembly and execution. It holds code and data in sections, along with metadata that tells the linker how to connect references across compilation units. A symbol is a named addressable entity: a function, a global variable, or a section. Relocations are placeholders that tell the linker or loader to adjust addresses when the final layout is known. Without relocation, code would need fixed addresses and would not be portable or shareable.

In ELF, sections such as .text, .data, and .bss hold code and data. The section headers describe offsets, sizes, and flags. The symbol table maps symbol names to section offsets and attributes. Relocation entries refer to symbols and specify how to patch the code or data. The relocation types indicate whether a relocation is absolute, PC-relative, or uses a GOT/PLT indirection. The x86-64 psABI defines these relocation types and their semantics, which is essential for interpreting dynamic linking and position-independent code.

The linker performs symbol resolution: it decides which definition of a symbol to use and patches references accordingly. Static linking resolves all symbols at link time. Dynamic linking defers some resolution to runtime, using the dynamic loader and data structures such as the Global Offset Table (GOT) and Procedure Linkage Table (PLT). The GOT holds addresses of global symbols and is updated by the loader. The PLT provides a stub that jumps through the GOT, enabling lazy binding. This mechanism is central to shared libraries and is a common target for debugging and security analysis.

PE on Windows uses a different layout but similar ideas: sections, import tables, and relocation entries. The import table lists external functions that must be resolved at load time. Base relocations allow the loader to rebase the executable if it cannot be loaded at the preferred address. While the details differ, the mental model is the same: object files are templates, and the loader fills in the addresses.

Relocations also matter for reverse engineering. If you see a relocation against a symbol, you know that the code depends on that symbol even if the address is not fixed. This is how tools recover call graphs and identify external dependencies. It is also how you can locate jump tables, vtables, and other data-driven control flow constructs.

Finally, debugging symbols and unwind info live alongside code in the object file. These sections are optional but invaluable for debugging and profiling. Understanding them helps you build tools that can show file/line information, variable locations, and call stacks, even in optimized binaries.

How this fits on projects

  • Projects 9 and 10 are focused on ELF/PE parsing and relocation resolution.
  • Project 6 uses unwind metadata to visualize stack frames.

Definitions & key terms

  • Object file: Compiled code and metadata before linking.
  • Section: A region of an object file with a specific purpose.
  • Symbol: Named reference to code or data.
  • Relocation: A patch applied by the linker or loader.
  • GOT/PLT: Indirection tables for dynamic linking.

Mental model diagram

SOURCE -> OBJECT (.o) -> LINKER -> EXECUTABLE -> LOADER -> RUNNING

OBJECT:
  [ .text ] [ .data ] [ .bss ] [ .symtab ] [ .rel.* ]

LINKER:
  resolve symbols + apply relocations

LOADER:
  map segments + resolve dynamic relocations

How it works

  1. Compiler/assembler emits object file with symbols and relocations.
  2. Linker merges sections and resolves symbols.
  3. Linker applies relocations or marks them for runtime.
  4. Loader maps segments and resolves dynamic relocations.

Invariants and failure modes:

  • Invariant: Relocations reference valid symbols.
  • Failure: Missing symbols cause link errors or runtime crashes.
  • Invariant: Section permissions match content (code vs data).
  • Failure: Incorrect permissions can cause execution faults.

Minimal concrete example (pseudo-structure)

# PSEUDOCODE ONLY
SECTION .text:
  CALL SYMBOL_F
RELOCATION:
  at .text+0x10 -> SYMBOL_F (PC_REL)

Common misconceptions

  • “Linking is just concatenation.” It includes symbol resolution and relocation.
  • “GOT/PLT is only for performance.” It is required for dynamic linking.
  • “Object files are the final executable.” They are templates.

Check-your-understanding questions

  1. Why do relocation entries exist at all?
  2. What problem does the PLT solve?
  3. How does a loader differ from a linker?

Check-your-understanding answers

  1. Addresses are not final until link or load time.
  2. It enables lazy binding of external functions.
  3. The linker combines objects; the loader maps and relocates at runtime.

Real-world applications

  • Diagnosing link errors and symbol conflicts
  • Reverse engineering binary dependencies
  • Building binary inspection tools

Where you will apply it Projects 6, 9, 10

References

  • System V ABI / gABI (Linux Foundation refspecs)
  • System V AMD64 ABI Draft 0.99.7
  • “Computer Systems: A Programmer’s Perspective” by Bryant and O’Hallaron - Ch. 7

Key insights Relocations and symbols are the invisible glue that makes binaries runnable.

Summary Understanding object files and linking turns binaries from opaque blobs into structured systems.

Homework/Exercises to practice the concept

  • Sketch the sections of a minimal object file and label their purpose.
  • Explain how a call to an external function is resolved.

Solutions to the homework/exercises

  • Include .text, .data, .bss, .symtab, and relocation sections.
  • Linker or loader patches a placeholder using relocation info.

3. Project Specification

3.1 What You Will Build

A tool that inspects PLT/GOT entries and resolves which symbols they correspond to.

Why this teaches x86-64: Dynamic linking is central to real-world binaries and relies on relocation mechanics.

Included:

  • Deterministic CLI output for a fixed input
  • Clear mapping between inputs and architectural meaning
  • A small test suite with edge cases

Excluded:

  • Full compiler or full disassembler coverage
  • Production-grade UI or packaging

3.2 Functional Requirements

  1. Deterministic Output: Same input yields identical output.
  2. Architecture-Aware: Output references ABI/ISA rules where relevant.
  3. Validation Mode: Provide a compare mode against a golden output.

3.3 Non-Functional Requirements

  • Performance: Fast enough for small inputs and interactive use.
  • Reliability: Handles malformed inputs with clear errors.
  • Usability: Outputs are readable and documented.

3.4 Example Usage / Output

$ x64plt demo.elf

PLT/GOT RESOLUTION
PLT[0] -> _dl_runtime_resolve
PLT[1] -> puts
PLT[2] -> malloc

GOT[1] -> puts@GLIBC
GOT[2] -> malloc@GLIBC

3.5 Data Formats / Schemas / Protocols

  • Input format: line-oriented text or hex bytes (documented in README)
  • Output format: stable, human-readable report with labeled fields

3.6 Edge Cases

  • Empty input or missing fields
  • Invalid numeric values or malformed hex
  • Inputs that exercise maximum/minimum bounds

3.7 Real World Outcome

This section is your golden reference. Match it exactly.

3.7.1 How to Run (Copy/Paste)

  • Build: (if needed) make or equivalent
  • Run: P10-plt-got-relocation-resolver with sample input
  • Working directory: project root

3.7.2 Golden Path Demo (Deterministic)

Run with the provided demo input and confirm output matches the transcript.

3.7.3 If CLI: exact terminal transcript

$ x64plt demo.elf

PLT/GOT RESOLUTION
PLT[0] -> _dl_runtime_resolve
PLT[1] -> puts
PLT[2] -> malloc

GOT[1] -> puts@GLIBC
GOT[2] -> malloc@GLIBC

4. Solution Architecture

4.1 High-Level Design

INPUT -> PARSER -> MODEL -> RENDERER -> REPORT

4.2 Key Components

Component Responsibility Key Decisions
Parser Turn input into structured records Strict vs permissive parsing
Model Apply ISA/ABI rules Deterministic state transitions
Renderer Produce readable output Stable formatting

4.4 Data Structures (No Full Code)

  • Record: holds one instruction/event with decoded fields
  • State: represents register/flag or address state
  • Report: list of formatted output lines

4.4 Algorithm Overview

Key Algorithm: Parse and Evaluate

  1. Parse input into records.
  2. Apply rules to update state.
  3. Render the state and summary output.

Complexity Analysis:

  • Time: O(n) over input records
  • Space: O(n) for report output

5. Implementation Guide

5.1 Development Environment Setup

# Ensure basic tools are installed
# build-essential or clang, plus objdump/readelf if needed

5.2 Project Structure

project-root/
├── src/
│   ├── main.*
│   ├── parser.*
│   └── model.*
├── tests/
│   └── test_cases.*
└── README.md

5.3 The Core Question You’re Answering

How does a call to an external function become a concrete address at runtime?

5.4 Concepts You Must Understand First

  1. Relocations
    • What do relocation entries represent?
    • Book Reference: “Computer Systems: A Programmer’s Perspective” - Ch. 7
  2. Dynamic linking
    • What are PLT and GOT used for?
    • Book Reference: “Computer Systems: A Programmer’s Perspective” - Ch. 7

5.5 Questions to Guide Your Design

  1. Data extraction
    • Which sections contain PLT and GOT information?
    • How will you map relocation entries to symbols?
  2. Output format
    • How will you display the mapping in a readable form?
    • How will you handle stripped binaries?

5.6 Thinking Exercise

Resolution Timeline

Draw a timeline showing when a PLT entry is first resolved and how subsequent calls behave.

Questions to answer:

  • What changes in the GOT after resolution?
  • Why is lazy binding useful?

5.7 The Interview Questions They’ll Ask

  1. “What is the PLT and why does it exist?”
  2. “How does the GOT get populated?”
  3. “What is lazy binding?”
  4. “What happens if relocations are missing?”
  5. “How does ASLR affect dynamic linking?”

5.8 Hints in Layers

Hint 1: Starting Point Parse relocation sections that target the PLT and GOT.

Hint 2: Next Level Use symbol tables to map relocation entries to names.

Hint 3: Technical Details Track the relationship between PLT stubs and GOT slots.

Hint 4: Tools/Debugging Compare your output with readelf -r and objdump -d.

5.9 Books That Will Help

Topic Book Chapter
Dynamic linking “Computer Systems: A Programmer’s Perspective” Ch. 7
Object file format “Linkers and Loaders” by John Levine Ch. 3-5

5.10 Implementation Phases

Phase 1: Foundation (2-3 days)

Goals:

  • Parse input format
  • Produce a minimal output Tasks:
    1. Define input grammar and example files.
    2. Implement a minimal parser and renderer. Checkpoint: Golden output matches a small input.

Phase 2: Core Functionality (1 week)

Goals:

  • Implement full rule set
  • Add validation and errors Tasks:
    1. Implement rule engine for core cases.
    2. Add error handling for invalid inputs. Checkpoint: All core tests pass.

Phase 3: Polish & Edge Cases (2-3 days)

Goals:

  • Add edge-case coverage
  • Improve output readability Tasks:
    1. Add edge-case tests.
    2. Refine output formatting and summary. Checkpoint: Output matches golden transcript for all cases.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Input format Text, JSON Text Easiest to audit and diff
Output format Plain text, JSON Plain text Matches CLI tooling

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Validate parsing and rule application Valid/invalid inputs
Integration Tests End-to-end output comparison Golden transcripts
Edge Case Tests Stress unusual inputs Empty input, max values

6.2 Critical Test Cases

  1. Minimal Input: One record, verify output.
  2. Boundary Values: Largest/smallest values.
  3. Malformed Input: Ensure clean error messages.

6.3 Test Data

INPUT: sample_min.txt
EXPECTED: matches golden transcript

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Wrong assumptions Output mismatches Re-read ABI/ISA rules
Off-by-one parsing Missing fields Add explicit length checks
Ambiguous output Hard to verify Add labels and separators

Project-specific pitfalls

Problem 1: “Symbols do not resolve”

  • Why: Stripped binaries or missing symbol table.
  • Fix: Fall back to dynamic symbol table or note unknowns.
  • Quick test: Use a binary with known imports.

7.2 Debugging Strategies

  • Golden diffing: Use diff to compare outputs line by line.
  • State logging: Print intermediate state after each step.

7.3 Performance Traps

  • Avoid over-optimizing; correctness and determinism matter most.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add a new input case and golden output
  • Add a summary line with counts

8.2 Intermediate Extensions

  • Add JSON output mode
  • Add validation warnings for suspicious inputs

8.3 Advanced Extensions

  • Support additional ABI or instruction variants
  • Integrate with a real binary to collect inputs

9. Real-World Connections

9.1 Industry Applications

  • Profilers and tracers: Use similar decoding and state models.
  • Security analysis: Use precise ABI knowledge to interpret crashes.
  • objdump: reference tool for binary inspection.
  • llvm-objdump: LLVM-based disassembly and inspection.

9.3 Interview Relevance

  • ABI and calling conventions are common systems interview topics.
  • Explaining decoding and linking demonstrates low-level fluency.

10. Resources

10.1 Essential Reading

  • Intel 64 and IA-32 Architectures Software Developer’s Manual - ISA reference
  • System V AMD64 ABI Draft 0.99.7 - calling convention rules

10.2 Video Resources

  • Vendor and university lectures on x86-64 and ABIs (search official channels)