README

OSTEP

《操作系统导论》（Operating System: Three Easy Pieces) 的读书笔记。这本书比其他的操作系统书更吸引我的点就是：语言清晰、重点明确、书中代码都是提供的 linux C 代码，方便菜鸡如我复现。而且作业也是贼有意思，不像我们老师布置的“语文作业”。

【OSTEP】梦开始的地方是本书的概述, 本书主要分为虚拟化、并发和持久化三个部分，其中虚拟化又包括 CPU 的虚拟化和内存的虚拟化。

【OSTEP】虚拟化 CPU 操作系统通过虚拟化 CPU 来提供又很多 CPU 可用的假相，从而运行很多个进程。这个部分包括进程的 fork()、wait()、exec() 等 API 的使用；操作系统通过内核模式和用户模式限制进程执行；进程在周转时间和响应时间之间权衡的 FIFO、SJF、STCF、RR、MLFQ 等调度算法。

【OSTEP】虚拟化内存操作系统通过地址映射虚拟化内存，使得每个进程独立的进程空间。这个部分包括内存操作 malloc()、free() 等 API 和内存泄漏检测工具 valgrind 的使用；虚拟内存到物理内存地址转换机制中的分段、分页机制，其中分页使用了 TLB 缓存来加快转换速度，使用了多级页表来减少内存消耗；最后介绍了使得虚拟内存超过物理内存空间的页交换机制。

【OSTEP】并发为了解决多线程程序临界区代码对共享变量修改不可控的问题，操作系统提供了并发支持。这个部分分为 pthread_create/join()、pthread_mutex_lock/unlock()、pthread_cond_wait/signal()、sem_wait/post() 等经典 API 的使用；锁、条件变量、信号量的实现原理；以及生产者-消费者问题、哲学家就餐问题等经典并发情景。本部分含有大量代码。

【OSTEP】持久化这个部分主要就是操作系统中的文件系统。包括磁盘等 I/O 设备；文件系统实现崩溃一致性的 FSCK 和日志技术；文件和目录的一些 API 和命令，包括读写文件、文件的 inode 信息、软链接和硬链接等，作业包括实现一个自己的 stat 命令、 ls 命令、tail 命令、tree 命令，我果然更喜欢写代码。

操作系统

【操作系统】修改其他进程的内存地址 linux 系统下一切皆文件，一个运行中的程序的内存存储在 /proc/[pid]/mem 中，因此，知道了一个进程的 pid 也就知道它内存文件的位置，知道了进程中变量的地址也就知道了这个变量在文件中的偏移。最后，调用 open() 打开内存文件，调用 lseek() 将文件指针偏移到我们要读/写的内存地址，调用 write() 即可修改。

【操作系统】操作系统概念 HomeWork 《操作系统概念》所有编程作业。第三、四、六、七章分别是进程、线程、同步、死锁。

【操作系统】MIT 6.S081 MIT 操作系统课的实验，运行在 xv6 操作系统平台上。可惜我是懒鬼，只做了前三个 lab。
lab1 主要是 API 的使用，比较有趣的是并发素数筛程序。使用管道实现了并发埃氏筛法。比如父进程筛去所有 2 的倍数后将剩余的写入管道，子进程从管道中读取数据并筛除 3 的倍数，如此递归。
lab2 是添加一个系统跟踪调用。跟着实验说明，了解 xv6 系统的调用流程就行了。
lab3 需要实现一个页表，这个实验太阴间了，我们需要为每个进程添加一个页表来代替之前的全局页表。在系统的 kernel 代码里增删改查，除了秃头，也让我意识到我好像对内核没有那么大的兴趣，遂放弃了后续实验。

SEEDlabs

SEEDlabs 是美国雪城大学设置的一套信息安全实验，难度不是很高，但是实验文档很详细，还提供了很详细的实验环境配置，上手还是容易的。

【SEEDlabs】Environment Variable and Set-UID Lab 这个实验可以认为是后续实验的基础。对于一些命令如 system("ls") 会使用到环境变量，如果将我们写的恶意 ls 程序路径添加到了环境变量最前面，就会调用错误的 ls 并且该 ls 会继承父进程的权限，从而实现提权。

【SEEDlabs】Buffer-Overflow Attack Lab (Set-UID Version) 缓冲区溢出实验，向 Set-UID 程序插入 shellcode 并使之执行。

【SEEDlabs】Buffer-Overflow Attack Lab (Server Version) 缓冲区溢出实验，和上个实验不同的是，这次我们要攻击的程序在服务器端，需要通过网络通信攻击。同时使用反向 shell 技术将服务端输入输出重定向到 tcp 连接上。

【SEEDlabs】Return-to-libc and ROP Attack Lab 对于堆栈不可执行的程序，我们无法执行我们的 shellcode，但是可以精心构造 shellcode 使被攻击函数返回到 libc 地址，如 system() 的地址，从而执行如 system("/bin/sh") 函数，达到提权目的。

【SEEDlabs】Shellshock Attack Lab 该漏洞是 bash 解析环境变量中的函数为 shell 函数时，会导致恶意命令执行，而子进程会继承父进程的环境变量。Web 服务器在接收到 http 请求时，会创建一个子进程来处理请求，这样就会触发子进程的环境变量解析从而使攻击成功。

【SEEDlabs】Race-Condition Vulnerability Lab 竞态条件攻击，我们构造两个线程，一号线程不断地循环将 XYZ 文件链接到特权文件和非特权文件上，二号线程不断向 XYZ 文件中写入内容。在某种情况下，二号线程在 XYZ 链接到非特权文件上通过了权限检查，接下来 XYZ 链接到特权文件上，然后二号线程写入。这样就实现了向特权文件中写入数据。

【SEEDlabs】Format-String Vulnerability Lab 格式化字符串漏洞，printf("%d%d", a, b) 扫描第一个字符串，遇到 %d 时读取第一个参数，然后参数指针后移。如果某种不规范的写法将 printf("%s", string) 写成了 printf(string)，编译器就无法检查参数和 %d 的个数是否匹配，这个时候 string 中有 %d 的话，就会往后读取非法地址上的值。这里仅仅只是读，而 %n 可以向参数指针地址写入当前已经输出过的字符个数！使用 %10000d 这种可以控制输出字符个数。

【SEEDlabs】Dirty-COW Attack Lab 大名鼎鼎的脏牛漏洞，为了复现这个漏洞，专门搞了个 Ubuntu12.04。mmap 可以将文件映射到进程的内存空间中，对内存的读写就是对文件的读写，进程间通过文件来通信就是这种方式。主线程以只读方式打开特权文件并以私有方式来映射到自己的内存空间，第一个子线程不断宣布不需要这个私有拷贝了，第二个线程向私有拷贝中写入数据，因为是私有拷贝是可以的。这样就可能在检查权限过了后（能够向私有拷贝写入了）放弃了内存映射，导致写进了原始内存中。这也是属于竞态条件漏洞。

【SEEDlabs】Spectre Attack Lab 针对 CPU 的幽灵攻击。为了加快执行速度， CPU 使用了乱序执行和分支预测技术。程序访问数据时，会先让其访问，同时来检查权限，当权限不满足时，会清空程序记忆。但是，即使清空了数据，访问仍然会留下痕迹，例如访问过的数据留在了 cache 中。这种侧信道攻击使得我们只需要检测 cache 速度即可拿到数据。例如秘密数据是 8，那么我们访问 data[8]，然后抹除记忆了。此时我们只需要循环访问 data[0] 到 data[128] 发现 data[8] 速度快（因为有 cache 了），那么秘密数据就是 8。熔断攻击原理相同，不过目前已被修复，无法复现了。

数据库

学习数据库的一些内容，一些基础知识和做过的一个 sql 注入的实验

CMU 15445

【CMU15445】Project 0 - C++ Primer 这个实验要求我们实现一个并发 trie 树，主要实现插入、删除和查找这三个算法。数据在 trie 树中以 key-value 键值对形式存储，键是非空可变长度的字符串。

【CMU15445】Project 1 - Buffer Pool Manager 这个实验是实现一个 buffer pool，缓冲池负责将物理页在主内存和磁盘之间来回移动，从而允许 DBMS 支持大于系统可用内存量的数据库。物理页面 page_id 到内存页帧 frame_id 的映射使用我们自己实现的可拓展哈希算法实现；内存满了需要释放帧时采用 LRU-K 淘汰算法。对页面的操作主要包括 New、Fetch、Unpin、Flush 和 Delete。

【CMU15445】Project 2 - B+Tree Index 这个实验是实现索引的底层数据结构 B+ 树。它是一个平衡的树，其中 internalpages 指导搜索，leafpages 包含实际的数据。因为树形结构是动态增长和收缩的，所以需要处理 split 和 merge 的逻辑。在这个实验中，我们主要需要实现 B+Tree 的 Insert、Delete、Search 这三种操作，迭代器和并发操作。

【CMU15445】Project 3 Query Execution bustub 数据库使用火山模型来处理查询，执行一条 SQL 语句，需要通过 Parser、Binder、Planner、Optimizer 处理后得到一棵执行树。然后实现执行树的 Scan、Insert、Join、Aggregation、Sort 等算子和将 Sort + Limit 优化为 TopN 算子。

【CMU15445】Project 4 - Concurrency Control 本实验使用两阶段锁技术实现 bustub 数据库中的事务支持。支持可重复读、读提交、读未提交三种隔离级别，表锁和行锁两种锁粒度，S/IS/X/IX/SIX 五种锁粒度。并使用一个线程执行死锁检测，当 DFS 算法查询到依赖链上存在环，选取最年轻的事务结束。最后，在 Project 3 实现的 Scan、Insert 和 Delete 算子中加上事务。