CS:APP Labs

Computer Systems: A Programmer's Perspective (3rd ed.) Lab Solutions

---

Solutions to the lab assignments from CMU's CS:APP course. Click any lab below for details.

✅ Data Lab — Bit manipulation, integer/float encoding

Implement integer and floating-point operations using only bitwise operators, under strict constraints on allowed operators and operation count.

✅ Bomb Lab — Reverse engineering, GDB, x86-64 assembly

Defuse a binary bomb by reverse engineering its phases with GDB. Includes cracking a hidden phase backed by a binary tree recursive search.

✅ Attack Lab — Buffer overflow, ROP chain, ASLR bypass

Exploit stack buffer overflows to hijack control flow.

• Phase 1–3: code injection
• Phase 4–5: ROP chain to bypass NX and ASLR

✅ Cache Lab — Cache simulation, matrix transpose optimization

Part A — Implement an LRU cache simulator in C, supporting arbitrary (S, E, b) parameters.

Part B — Optimize matrix transpose for cache performance. The 64x64 case splits each 8x8 block into four 4x4 sub-blocks, repurposing unused regions of B as a staging buffer to minimize conflict misses.

✅ Shell Lab — Processes, signals, job control

Implement a Unix shell (tsh) with:

• Foreground / background job control
• Signal handling (SIGINT, SIGTSTP, SIGCHLD)
• Built-in commands: jobs, fg, bg, quit

Signal masking eliminates race conditions between fork and addjob.

✅ Malloc Lab — Dynamic memory allocator, segregated free lists

Implement malloc, free, and realloc from scratch.

• Segregated explicit free lists with 12 size classes
• Boundary tags with prev_alloc bit to eliminate footers on allocated blocks
• Circular doubly-linked free lists; each class stores one head pointer
• Immediate coalescing on every free
• realloc tries in-place growth (next block, heap end, prev block, both neighbors) before falling back to malloc-copy-free

Score: 97 / 100

• 🔄 Proxy Lab — In progress

---

Acknowledgment

Special thanks to virgiling for the helpful blog that provided great guidance throughout these labs.