Code Injection Attacks

A code injection attack exploits a program's failure to validate the size or content of an input, using that failure to place attacker-chosen machine code (shellcode) into the process's address space, and then diverting the CPU's control flow (via a corrupted return address, function pointer, or saved instruction pointer) to execute it. It is distinct from code-reuse attacks — such as Return-Oriented Programming — in one crucial respect: in classical injection, the attacker's own bytes are the executed instructions; nothing pre-existing in the binary is reused. The prerequisite vulnerability is almost always a memory-safety violation. The paradigm case is the stack buffer overflow: a fixed-size local buffer is written using an unchecked-length operation (`strcpy`, `gets`, `sprintf` without a width specifier, manual loops without bounds checks), and the write proceeds past the buffer's allocated end into adjacent stack memory — most dangerously, into the saved return address that tells the CPU where to resume execution when the current function returns. Two conditions must jointly hold for classical code injection to succeed. First, the region into which the shellcode is written must be executable at the time of the jump — historically true of the stack and heap on most systems, before DEP/W^X (Data Execution Prevention / "Write XOR Execute") policies made writable memory non-executable by default. Second, the attacker must know, or be able to guess with workable probability, the absolute address of the injected shellcode, since the corrupted return address must point precisely there — a requirement that ASLR (Address Space Layout Randomization) was designed to defeat by randomizing that address on every run.

The attack proceeds through a fixed sequence of stages, each of which the defender can, in principle, individually block.

Stage 1 — Locate the vulnerability. The attacker finds a code path where attacker-controlled input is copied into a fixed-size stack buffer without a length check, and determines the exact offset (in bytes) from the start of the buffer to the saved return address on the stack.

Stage 2 — Construct the shellcode. The attacker writes a short sequence of machine instructions that perform the desired action — spawn a shell, open a reverse network connection, add a user — using position-independent code with no embedded null bytes if the overflow is triggered through a C-string function (since `\x00` would terminate the copy).

Stage 3 — Build the padded payload. Because the exact stack address where the shellcode will land is hard to predict precisely, the payload is typically: ``` [ NOP sled ][ shellcode ][ repeated guessed return address ] ``` A NOP sled is a long run of no-op instructions (`0x90` on x86). If the corrupted return address lands anywhere inside the sled, execution slides forward harmlessly until it reaches the shellcode — turning an exact-address guess into a much easier "land somewhere in this wide window" guess.

Stage 4 — Overwrite the return address. The overflow writes past the buffer boundary, through saved registers (e.g., a saved base pointer), and finally overwrites the return address slot with the attacker's guessed address — a pointer into the sled/shellcode region.

Stage 5 — Redirect control flow. When the vulnerable function executes its `return` (or `ret`) instruction, the CPU pops the corrupted value off the stack into the instruction pointer and jumps there — into the NOP sled, and from there into the shellcode.

Stage 6 — Shellcode executes. Now running with the privileges of the victim process, the shellcode performs its payload — classically an `execve("/bin/sh", ...)` syscall sequence, granting the attacker a shell. ``` ALGORITHM ClassicStackInjection(vulnerable_function, target_process) // Attacker-side construction Input: buf_offset // bytes from buffer start to saved return address shellcode // machine code bytes, no embedded 0x00 if via strcpy-like copy guessed_addr // predicted address inside the NOP sled sled_len // length of NOP sled, chosen to widen the address guess window 1. sled <- REPEAT(0x90, sled_len) // NOP sled 2. payload <- sled || shellcode 3. pad_len <- buf_offset - LENGTH(payload) if pad_len < 0: payload <- TRUNCATE_OR_RESIZE(payload, buf_offset) // must fit before ret addr pad_len <- 0 4. filler <- REPEAT(0x41, pad_len) // arbitrary padding to reach saved regs 5. ret_bytes <- ENCODE_ADDRESS(guessed_addr) // little-endian address bytes 6. exploit <- payload || filler || ret_bytes 7. SEND(target_process, exploit) // e.g. as a network request or argv // Victim-side execution (inside the vulnerable function) 8. vulnerable_function receives `exploit` as input 9. UNCHECKED_COPY(local_buffer, exploit) // e.g. strcpy — overflow occurs here 10. // stack memory beyond local_buffer, including saved // frame pointer and return address, is now overwritten 11. RETURN // pops corrupted return address into IP 12. CPU jumps to guessed_addr -> lands in NOP sled 13. execution slides forward through sled -> reaches shellcode 14. shellcode executes with victim's privileges ```

Time complexity (attack construction). Building the exploit payload is $O(n)$ in the size of the buffer being overflowed, where $n$ is the number of bytes written: constructing the sled, shellcode, filler, and return address is a linear scan and concatenation. Finding the correct buffer offset (`buf_offset`) is typically a one-time, small-constant search — done offline via disassembly, source inspection, or a handful of probing test inputs with an incrementing cyclic pattern (e.g., the "De Bruijn pattern" technique), so it does not scale with input size in the online attack.

Space complexity. The payload occupies $O(n)$ bytes, bounded above by the space available in the vulnerable buffer plus whatever adjacent stack memory the overflow is permitted to reach before hitting a guard page or unrelated memory that would crash the process before the return executes.

Correctness argument (why the attack necessarily works absent defenses). The argument rests on an invariant of the calling convention on architectures like x86: at the moment a function executes its return instruction, it unconditionally trusts the memory word at a fixed stack offset to be the address of the next instruction to execute — there is no CPU-level verification that this word was not modified during the function's execution. Formally, let $R$ denote the return-address memory cell and let $W$ be the sequence of writes issued by the (buggy) copy operation. If the vulnerable function contains no bounds check, then $W$ is determined entirely by attacker input length, and the attacker can choose $|W|$ such that $R \in \text{range}(W)$. Since the architecture's `ret` semantics are simply "jump to $M[R]$" with no authentication of $M[R]$'s provenance, whichever value the attacker last wrote to $R$ becomes the next instruction pointer. This is a direct consequence of the stack being a single, undifferentiated linear memory region shared between control data (return addresses) and program data (buffers) — the root architectural fact that all defenses in this space (canaries, ASLR, DEP) attack from different angles.

Probability of success (address guessing). If the attacker cannot read the target's memory layout and must guess the shellcode's address blindly, the effective success probability per attempt is approximately

where $L$ is the width of the NOP sled (the tolerance window) and $2^b$ is the size of the address space region the guess must land in ($b$ effective bits of entropy in the target address, e.g. from stack randomization). A larger sled linearly increases $p$; this is precisely why NOP sleds exist — they trade payload space for probability of a correct landing, converting an exact point-guess into an interval-guess. Without any address randomization ($b \approx 0$ in practice, since stack layout is deterministic on non-ASLR systems), $p \to 1$: the attack is deterministic. This single equation is also why ASLR works as a defense — it inflates $b$, driving $p$ toward zero exponentially.

Honesty about tradeoffs. Classical injection is fragile in ways an attacker must engineer around: null-byte-terminated copy functions restrict which byte values shellcode may contain; stack alignment and canary values (where present) must be preserved or recomputed; and modern non-executable stacks (DEP/W^X) make the entire technique fail outright regardless of address prediction, forcing the pivot to code-reuse techniques such as Return-Oriented Programming that never write new executable code at all.

Consider a vulnerable C function on a 32-bit x86 Linux system with no protections enabled (no ASLR, no DEP, no canary — the historical default in the 1990s): ```c void handle_request(char *input) { char buf[64]; strcpy(buf, input); // no length check } ``` The stack layout, low to high addresses, places `buf` first, then the saved frame pointer (4 bytes), then the saved return address (4 bytes).

The key numerical point: with a 40-byte sled and a stack region that varies by, say, only a few hundred bytes across runs on a non-ASLR system, the guess succeeds essentially every time — matching the $p \approx L/2^b$ model with $b$ effectively near zero. Enable ASLR (randomizing the stack base by roughly 20+ bits on modern 64-bit Linux) and the same sled gives $p \approx 40 / 2^{20} \approx 0.00004$ per attempt — the identical exploit code now almost always crashes the process instead of succeeding, illustrating exactly why address-space randomization is such an effective, low-cost mitigation.

The technique's canonical public exposition came from the exploit-development and security-research community of the 1990s, most famously formalized in Aleph One's 1996 Phrack article "Smashing the Stack for Fun and Profit," which gave the security field its first widely circulated, precise walkthrough of stack layout, return-address overwriting, and shellcode construction. The underlying insight — that a stored program's data and its instructions occupy the same undifferentiated memory, and thus can be confused — traces conceptually to the von Neumann architecture itself.

Code injection via memory corruption underlies decades of real-world exploitation: the 1988 Morris Worm, countless CGI and network-daemon compromises through the 1990s and 2000s, and a large fraction of CVEs still reported today in C/C++ codebases — browsers, kernels, VPN clients, IoT firmware, and embedded control systems where memory-safe languages are not (yet) universal. Understanding this classical mechanism is the essential foundation for every mitigation taught afterward: DEP/W^X blocks Stage 6 by refusing to execute writable memory; ASLR blocks Stage 4's precondition by randomizing the target address so the guess in Stage 3 fails with overwhelming probability; stack canaries detect the overwrite in Stage 4 before the corrupted return address is ever used, aborting the process safely. When all three are deployed together, direct shellcode injection becomes impractical, which is exactly why attackers evolved Return-Oriented Programming — reusing existing executable code fragments instead of injecting new ones, sidestepping DEP entirely while still exploiting the same underlying stack buffer overflow primitive. Security-critical software today is routinely audited, fuzzed, and rewritten in memory-safe languages (Rust, Go) precisely to eliminate this attack surface at its root rather than relying solely on runtime mitigations.

Ask the tutor: How does Return-Oriented Programming construct a working exploit once DEP prevents shellcode execution?