Overview

Lab Wanderings

You need to complete the following 8 experiments within one semester:

Data Lab - Write code using a very limited set of operators (^, |, &, etc.).

/*
 * bitXnor - ~(x^y) using only ~ and |
 *   Example: bitXnor(6, -5) = 2
 *   Legal ops: ~ |
 *   Max ops: 7
 *   Rating: 1
 */
int bitXnor(int x, int y) {
    // Replace 0 with your implementation of bitXnor.
    return 0;
}

Bomb Lab - Read assembly code (x86-64) and solve puzzles.

    .section .rodata
.Lformat:
    .string "%d %d"

    .text
    .globl phase_1
    .type phase_1, @function
    .extern explode_bomb
    .extern __isoc99_sscanf

phase_1:
    subq    $24, %rsp              

    leaq    8(%rsp), %rdx         
    leaq    12(%rsp), %rcx        
    leaq    .Lformat(%rip), %rsi  
    xorl    %eax, %eax            
    call    __isoc99_sscanf@PLT

    cmpl    $2, %eax               
    jne     .Lexplode

    cmpl    $6, 8(%rsp)            
    jne     .Lexplode

    movl    8(%rsp), %eax          
    addl    %eax, %eax             
    addl    $1, %eax               

    cmpl    %eax, 12(%rsp)         
    jne     .Lexplode

    addq    $24, %rsp              
    ret

.Lexplode:
    call    explode_bomb           
    addq    $24, %rsp
    ret

    .size phase_1, .-phase_1
    .section .note.GNU-stack,"",@progbits

Attack Lab - Read vulnerable assembly code and hack it.

    .section .rodata
success_msg:
    .string "Attack successful: touch1 reached."

normal_msg:
    .string "Returned normally."

    .text

    .globl main
    .type main, @function

main:
    pushq   %rbp
    movq    %rsp, %rbp

    call    getbuf                  

    leaq    normal_msg(%rip), %rdi
    call    puts@PLT                # Printed only if getbuf returns normally

    xorl    %eax, %eax
    popq    %rbp
    ret


    .globl getbuf
    .type getbuf, @function

getbuf:
    subq    $40, %rsp               

    movq    %rsp, %rsi              
    xorl    %edi, %edi              
    movl    $128, %edx              
    call    read@PLT                

    movl    $1, %eax
    addq    $40, %rsp
    ret                             


    .globl touch1
    .type touch1, @function

touch1:
    leaq    success_msg(%rip), %rdi
    call    puts@PLT

    xorl    %edi, %edi
    call    exit@PLT                # Terminate after successful exploitation

    ud2                             # Should never be reached


    .size main, .-main
    .size getbuf, .-getbuf
    .size touch1, .-touch1

    .section .note.GNU-stack,"",@progbits

Arch Lab - Write assembly code that leverages the pipeline for very high execution efficiency.

Cache Lab - Write C code that leverages the cache, minimizing the number of cache misses.

Shell Lab - Write a tiny OS-level shell.

Malloc Lab - Write a C-style memory allocator that uses memory efficiently.

Proxy Lab - Write an I/O proxy for a server.

Happy coding~

Use Linux via CLI

Just like Windows, Linux is an operating system. Unlike Windows, Linux is distributed under an open-source license, and it is extremely lightweight. For most computer users, Windows (or macOS) can fully meet their needs, and there is no reason for them to learn Linux. But for programmers or CS researchers like us, Linux is likely to be our main operating system.

All the labs in our course run on Ubuntu 24.04 LTS. Ubuntu is a Linux distribution (or, in short, a “distro”). You may wonder what a Linux distribution is. In short, Linux provides just the “kernel” of an operating system, with little user interface, making it hard to “use” on its own. A Linux distribution provides a “shell” for Linux, allowing users to interact with it more easily.

Tip

Want to learn a little more about Linux? Click here!

Want to install an Ubuntu virtual machine on your local Windows or macOS machine? You could visit the official Ubuntu website.

Want to connect your virtual machine through vscode? This document may help. Turning to your AI agents is even better.

In this course, we focus only on Ubuntu 24.04 LTS. We can generally use Ubuntu in two ways: through a GUI or the CLI. A GUI (Graphical User Interface) is a popular and visually oriented way to interact with a computer. It is the only interface most people have encountered and is likely what you are using to browse this document right now. A CLI (Command-Line Interface), however, is an old-school textual interface used primarily by programmers.

It seems that the GUI is the GOAT and there is no reason to learn the “outdated” CLI. Unfortunately, the reason programmers prefer the CLI is not simply that using it looks cool (at least, that is not the main reason). You might find the answer in the following two articles:

Nature: Five reasons why researchers should learn to love the command line

Course Overview + Introduction to the Shell · Missing Semester

Whether or not you read the articles above, my job is to teach you how to use Ubuntu via the CLI. It is actually quite simple, so here we go.

Ubuntu CLI Basics

Whichever way you installed Ubuntu, start it. You are likely to see a text window with your cursor on the last line:

                               Your Cursor
                                    |
                                    v
your-user-name@your-machine-name:~$

We call all the text before your cursor on the last line the shell prompt. By default, it tells you who you are and where you are. You can customize your shell prompt in Ubuntu just for fun.

Note

For things that are just for fun, I won’t tell you the details, but I will tell you that they exist. In the era of AI, it won’t be hard to learn about things you know exist, and all you need is interest.

Let’s type something, such as a greeting, and press Enter:

Hello?

Unfortunately, the Ubuntu shell is not an AI agent, so it won’t reply “Hello, user!” or anything similar. Instead, it will likely display a message:

Hello?: command not found

Here we encounter the technical term “command”. Actually, the shell (sh) is a command-language interpreter, so it treats all your input as commands. The shell reads your input, tries to run it, and gives you the result. For example, the error message Hello? command not found is the result of “running” our greeting command Hello?. It seems that Hello? is not a valid command, so what is a valid command? Remember, in the CLI world, if you need help, just type help.

help

help itself is a valid command and shows all built-in commands, including itself. However, built-in commands are far from meeting our needs. GNU Coreutils provides more powerful shell commands. You could use the info command to take a look.

info coreutils

Well, I have to admit that learning the CLI from reference pages is not always a pleasant experience. When possible, we prefer to consult a cheat sheet. Turning to AI agents is also a good choice.

Note

To be exact, bash, an essential component of the Ubuntu shell, is the program that actually serves as the interpreter. We won’t go into implementation details because this course is for beginners and we want to focus on things that are really interesting.

Note

The term interpreter shouldn’t be new to you, given that all your Python code is executed by a Python interpreter (CPython, most likely). Using the shell is like using Python in interactive mode (python -i): you type one line of code and press Enter; the interpreter then parses and “evaluates” your code before waiting for your next input.

The shell also has a non-interactive mode. You can write a .sh script and execute it with the shell. For more information, click here.

If you have taken Practice of Software Design, another course I teach as a TA, you should already be familiar with these concepts, since you have implemented a Lisp interpreter yourself :>.

Basic Commands

Since each command is fairly easy to learn, I will just show you the most important ones.

pwd - Print the path of the current working directory.

pwd

ls - List files and directories. Use -l for a detailed list and -a to include hidden files.

ls -la

cd - Change the current working directory.

cd ~/projects

mkdir - Create a new directory. The -p option also creates missing parent directories.

mkdir -p projects/ics

touch - Create an empty file, or update a file’s modification time if it already exists.

touch notes.txt

cp - Copy a file or directory.

cp main.c main-backup.c

mv - Move or rename a file or directory.

mv old-name.c new-name.c

rm - Remove a file. Be careful: removed files are not normally put in a recycle bin.

rm old-name.c

cat - Print the contents of a file to the terminal.

cat README.md

less - Read a long text file one page at a time.

less large-log.txt

head and tail - Show the first or last lines of a file.

head -n 5 output.txt
tail -n 5 output.txt

grep - Search for lines that contain a pattern.

grep -n "main" main.c

find - Search for files and directories under a given path.

find . -name "*.c"

echo - Print text or the value of a shell variable.

echo $PATH

man - Open the manual page for a command.

man ls

info - Read the GNU Info documentation for a command or topic.

info coreutils

chmod - Change file permissions, such as making a script executable.

chmod +x run.sh

gcc - Compile C source code into an executable program.

gcc hello.c -o hello

make - Build a project according to the rules in its Makefile.

make

Tip

A directory (often called a folder) is a container for files and other directories.

A file stores data, such as text or source code.

In projects/ics/main.c, projects and ics are directories, while main.c is a file.

Tip

Use man for a concise command reference. Use info for more detailed, topic-oriented documentation, especially for GNU programs.

Reference Materials

1. What is Linux? - Linux.com
2. Nature: Five reasons why researchers should learn to love the command line
3. MIT CSAIL: The Missing Semester
4. The Linux command line for beginners | Ubuntu
5. Welcome to the terminal - Ubuntu Server documentation
6. Ubuntu CLI Cheat Sheet
7. Ubuntu CLI Cheat Sheet (PDF ver.)

A Journey through CSAPP

You may have heard that ICS is horrible, difficult, time consuming, GPA threatening…

Now I tell you they are all true.

You may also have heard that ICS is important, useful, inspiring, high-quality…

They are all true either.

And it is also true that you have to overcome ICS to graduate.

I will introduce what you would get from CSAPP, and I will try my best to help you find motivations to learn CSAPP. Anyway, to learn what you want to learn would usually be easier than to learn what you are forced to learn.

ICS teaches C, but it is not mainly about writing algorithms in C. Instead, it explores how C works under the hood and how to use it for advanced programming tasks such as signal processing, network programming, and concurrent programming, which play key roles in frontiers of computer science even in era of AI.

ICS focuses on the deeper principles beneath C. Once you understand them, you will have a stronger foundation for learning other programming languages.

By studying ICS, you will gain a deeper understanding of high-level languages, explain phenomena that may seem mysterious to ordinary programmers, and make small but highly significant optimizations to your programs.

Chapter 2: Data

An int can represent negative numbers. Have you ever wondered how a computer stores them?

char and double are common C types. Have you wondered how a computer stores characters and floating-point values?

An int variable occupies 4 bytes, while a char variable occupies 1 byte. How many bytes does the following structure occupy? Is the answer really 5 bytes?

struct {
    int i;
    char c;
};

After this chapter, you will have a comprehensive and clear understanding of how data is represented and stored in a computer.

Chapter 3: Assembly

When we program in a high-level language such as C, have you ever wondered how a computer executes the program we write?

A compiler transforms high-level code into an intermediate representation (IR), then into assembly language (A). After linking and other possible transformations, the result becomes executable code.

High-level code -> IR -> assembly -> executable code

Compared with high-level languages, assembly language gives a clearer picture of how programs run on a machine. Many compiler optimizations also take place at the assembly level. In this chapter, you will begin to understand x86-64 assembly and glimpse the lower-level form of code.

Chapter 4: Arch

When a computer is asked to execute a piece of code, how does it organize the work? Does it simply execute one instruction after another?

In this chapter, you will understand the secrets behind single-core CPU performance and experience the power of pipelining firsthand.

Chapter 6: Cache

When buying a laptop, we often see specifications such as:

RAM: 16 GB
Storage: 512 GB

What is the difference between memory and storage capacity? How does memory work? Is it really just a very large array?

In this chapter, you will uncover the workings of computer storage systems and understand why 16 GB of RAM and a 512 GB solid-state drive can cost roughly the same.

Chapter 7: Linking

Have you ever wondered about these questions?

• Why must a C program be compiled before it can run?
• What does #include <stdio.h> mean, and what exactly does it do?
• Does a Hello, world! program really execute only one output statement?
• What is a library file, and how is it different from our main.c?

In this chapter, you will gain an initial understanding of compilation, compilers and linkers. You will also appreciate the importance of code reuse and the effort programmers have invested in making it possible.

Chapter 8: Signal

Our computers can clearly run multiple programs at the same time. For example, your browser and your operating system appear to be running simultaneously now.

How can programs run at the same time? Can a single-core CPU run multiple programs simultaneously? Can different programs communicate with one another, and how do they do it?

In this chapter, you will get your first look at concurrency and parallelism, and develop a clearer understanding of operating systems, shells, and cooperation between programs.

Chapter 9: Malloc

Suppose two unrelated programs, A and B, each have a pointer named pa and pb. If the two programs are running simultaneously and the two pointers have the same value at runtime, do they point to the same address of the memory?

Memory errors are common and serious problems in C programs. Why do they happen? Why can’t the compiler detect them automatically?

In this chapter, you will develop a deep understanding of the computer’s address system and appreciate the importance of address-space isolation.

Chapter 10: I/O

Do you remember the file streams introduced in Introduction to Computing? What is the difference between a file stream and the standard input/output streams?

I/O is an important way for a program to communicate with the outside world, but it also hides many security risks. In this chapter, you will gain a thorough understanding of I/O streams and learn how to read and write data robustly.

Chapter 11: Web

When we turn on a computer, the first thing we do is often connect to the Internet.

We can insert a USB drive into a computer and exchange information between the drive and the computer. That is easy to understand. But when we open WeChat and message a classmate in Shanghai, we are exchanging information between a computer in Shanghai and a computer in Beijing. That is far more remarkable.

In this chapter, you will gain an initial understanding of how the Internet works and try using C to send and receive data over a network.

Chapter 12: Concurrency

Concurrency is everywhere today, but concurrent programming is not trivial.

for (int i = 0; i < 500; ++i) {
    ++j;
}

Suppose j initially equals 0. After one program executes the loop above, its value becomes 500. If two programs execute the loop concurrently, the final value may be any number between 500 and 1000, inclusive.

In this chapter, you will learn to handle one of the most common problems in concurrent programming: race conditions. You will also understand the principles behind seemingly inexplicable concurrent behavior.

Epilogue

It would be a long but meaningful journey. Keep up, and you would gain more than you could imagine.

Good luck!