写fork函数的时候发现实际传给trap handler的ts地址和用(struct trap_state *) (KSTACK_TOP(old))) - 1 计算出来的结果不一样，后者比前者小0x10。另外ts的实际地址加上ts的大小(92个字节)后就超出了内核栈的范围。 /* * This structure corresponds to the state of user registers * as saved upon kernel trap/interrupt entry. * As always, it is only a default implementation; * a well-optimized kernel will probably want to override it * with something that allows better optimization. */ struct trap_state { /* Saved segment registers */ unsigned int gs; unsigned int fs; unsigned int es; unsigned int ds; /* PUSHA register state frame */ unsigned int edi; unsigned int esi; unsigned int ebp; unsigned int cr2; /* we save cr2 over esp for page faults */ unsigned int ebx; unsigned int edx; unsigned int ecx; unsigned int eax; /* Processor trap number, 0-31. 阅读全文 →

Linux 2.4.18的linux/linkage.h文件定义了若干相关的宏 #define SYMBOL_NAME(X) X #ifdef __STDC__ #define SYMBOL_NAME_LABEL(X) X##: #else #define SYMBOL_NAME_LABEL(X) X/**/: #endif #define __ALIGN .align 16,0x90 #define __ALIGN_STR ".align 16,0x90" #define ALIGN __ALIGN #define ALIGN_STR __ALIGN_STR #define ENTRY(name) .globl SYMBOL_NAME(name); ALIGN; SYMBOL_NAME_LABEL(name) 用ENTRY(name)就能定义函数了。后来发现Flux OSKit中本来就提供了类似功能的宏，定义在inc/asm.h中。 使用的时候需要再写一个c语言的wrapper function（至少2.4.18里面是这么做的） asmlinkage void ret_from_fork(void) __asm__("ret_from_fork"); 阅读全文 →

Paper: LeakSurvivor: Towards Safely Tolerating Memory Leaks for Garbage-Collected Languages http://www.usenix.org/events/usenix08/tech/tang.htmlYan Tang, Qi Gao, and Feng Qin, The Ohio State University三位作者好像都是中国人 这篇paper针对支持垃圾收集的语言中内存泄露问题，提出了一种比较保守的“换出”策略，即把可疑的内存泄露的对象（这些对象通常都是长时间没有被访问的）从内存移动到硬盘上暂时保存，减小内存的压力；如果这些对象后来被再次访问（这种可能性很小），就把它们从硬盘上移回内存。 阅读全文 →

看 OOP 教材时，书里提到了一个双检测锁定（Double-Checked Lock, DCL）的问题，但是没有更多介绍，只是说这是一个和底层内存机制有关的漏洞。查阅了下相关资料，对这个问题大致有了点了解。 从头开始说吧。 在多线程的情况下Singleton模式会遇到不少问题，一个简单的例子 class Singleton { private static Singleton instance = null; public static Singleton instance() { if (instance == null) { instance = new Singleton(); } return instance; } } 假设这样一个场景，有两个线程调用 Singleton.instance()，首先线程一判断 instance 是否等于 null，判断完后一瞬间虚拟机把线程二调度为运行线程，线程二再次判断 instance 是否为 null，然后创建一个Singleton 实例，线程二的时间片用完后，线程一被唤醒，接下来它依然会创建一个新的 Singleton 实例，导致两次调用范围的对象不同。 最简单的方法自然是在类被载入时就初始化这个对象： private static Singleton instance = new Singleton(); JLS (Java Language Specification) 中规定了一个类只会被初始化一次，所以这样做肯定是没问题的。 但是如果要实现延迟初始化（Lazy initialization），比如这个实例初始化时的参数要在运行期才能确定，应该怎么做呢？ 依然有最简单的方法：使用 synchronized 关键字修饰初始化方法： public synchronized static Singleton instance() { if (instance == null) { instance = new Singleton(); } return instance; } 然而引入 synchronized 关键字后，产生了一个性能问题：多个线程同时访问这个方法时，会因为同步原语而导致每次只有一个线程执行这段代码，影响程序性能。而事实上初始化完毕后只需要简单的返回 instance 的引用就行了。 阅读全文 →

折腾了一下午加晚上，看了一堆包后总算把HTTPS协议搞定了，趁热写点心得。 这个Lab很强大，把11 12 13三章的内容全串起来了。 HTTP部分很简单，读个请求头把主机分析出来（有现成的函数），然后把客户端的所有请求传给Web服务器，再把服务器的所有反馈信息传给客户端就行了。另外注意传信息的时候不要使用Rio_readlineb之类的函数，而要用Rio_readnb，否则传图像时会碰到问题。 另外把版本统一成HTTP 1.0能明显的提高代理服务器的速度，具体原因还不清楚，明天再问问。 如果要把这个代理服务器写得健壮一点，要注意各种异常的处理，比如通常浏览器都能发送正确的报头，但是如果有人通过telnet发送了错误的报头也要能够正确的释放内存再结束线程。 然后是线程，这个问题也不大，使用信号量实现互斥锁，另外在即时free资源就好。 最后就是HTTPS协议的处理了，由于没正确理解文档的意思，在这上面花了很多时间，不过倒也接触了不少新东西。 首先是用gdb调试多线程程序，使用info threads查看当前所有线程，然后thread #切换到该线程就能查看那个线程的相关信息了。 然后来说下HTTPS协议的处理。一开始我有个错误的概念，就是代理服务器的责任是把所有客户端的信息转发到服务器端，把所有服务器端的信息转发到客户端，或者说在浏览器的眼中代理服务器和普通的Web服务器没有区别。其实并非如此，在我用OmniPeek截包看了半天后才意识到自己错了 =_= 浏览器不通过代理进行HTTPS连接时，只发送加密后的数据；而通过代理服务器时，先告诉代理服务器相关信息，然后再发送密文。另外，HTTPS的明码报头一般不会像文档中那样只有一行，代理服务器要记得所有的明文都读进来（但不转发给Web服务器），然后回复HTTP/1.0 200 Connection established，最后再负责密文的转发。 HTTPS的数据转发也和HTTP不一样，它需要客户端和服务器端多次的双向数据传输。而默认的read方法在没有信息读取和其他中断发生的时候是会block的。对于这个问题我的解决方法是结合I/O Multiplexing和Non-blocking I/O（搜资料的时候看到过这样处理的效率也比较高，见http://www.kegel.com/c10k.html）。用fcntl设置两个file descriptor的模式为O_NONBLOCK，然后再用select/poll实现multiplexing即可。不知道还有没有更好的方法。 另外测试HTTPS时建议使用https://mail.google.com，文档中的两个网页貌似firefox都打不开的。 阅读全文 →

这个Lab是要自己实现一个malloc函数，要求内存利用率和速度尽可能高。 用红黑树的版本最后得分是97/100，没有针对测试数据作任何优化，据说可以改到100/100，不过95分以上就满分了我也懒得再改了。 这个Lab的重点在可用内存的管理上。关于数据的组织，似乎有两种比较常见的形式（我不知道的就不算进来了，下同 =_=）。一是slab/buddy系统，就是书上讲的segregated list；还有一种用二叉树实现，这个lab我用了二叉树。 第一种方法对提高性能很有帮助，但是利用率方面就比较有限了。而这个lab似乎提高性能比较容易，难点在于利用率的提高。 二叉树方面，也有两种：平衡二叉搜索树（AVL树、红黑树等），字典树（Trie, 似乎也叫Radix tree） 这些数据结构都比较经典，很多书上都有现成的代码，网上也有一堆，拿来改一下就行了（注意算法导论上的红黑树的left-rotate是有bug的，见勘误表）。 另外还有个优化，树的结点要保存很多数据，比如父结点、左右结点、前后结点（考虑到同一大小的块的存在），红黑树中还需要保存一个颜色值（当然这个值可以保存在header中）。如果所有的空结点都以这种形式保存的话，势必对利用率影响很大。 所以建议另外维护一个block size相对较小的（比如小于128字节）的list，把小于这个值的空闲块都放到那个list里。 差不多就这样了，思路还是蛮简单的，就是实现起来很恶心。 另外做的时候还可以考虑考虑多线程的情况下这个malloc的表现会如何。 感觉下学期的几个lab，Lab 4 5 7都和优化程序性能有关，颗粒度不断提高，从最底层的汇编指令，到语言级别的unrolling、splitting，直到现在和具体语言无关的算法层次，对写高效代码的帮助蛮大的。 阅读全文 →

Application-Level Isolation and Recovery with SolitudeShvetank Jain, Fareha Shafique, Vladan Djeric, Ashvin Goel Department of Electrical and Computer Engineering, University of Torontohttp://portal.acm.org/citation.cfm?id=1357010.1352603引入一个新的文件系统层(Isolation File System)将安全可信的基础文件系统和不可信的环境（如网上下载的文件等）隔离开来，并对不可信的环境中做出的改动加以记录，一旦发现问题就能即使恢复。 阅读全文 →

重定向： 主要用到open, close, read和write这几个函数，关于它们的使用方法可以使用 man 2 <函数名> 查看。 这里简单介绍下： Linux内核为每个进程维护了一张已打开的文件的表格，用File Descriptor（整型，以下简写成fd）可以访问到这些文件。所以很容易理解tsh.c中的函数listjobs为什么需要一个output_fd的整型参数，注意它的后面有这么一行： if (writer(output_fd, buf, strlen(buf)) < 0) … 这一行就把前面构造好的buf字符串（包括当前进程的信息）输出到这个output_fd对应的文件中了。 每个进程的值为0, 1, 2的fd都指向相同的文件，0对应标准输入（通常是键盘输入），1对应标准输出（通常为屏幕），2对应标准错误输出。 可以看到在main方法的开头，有这么一句 dup2(1, 2); dup2的作用是把参数二指向的文件改成和参数一一样（如果之前打开了文件，则先关闭），这句话的作用就是把原来要输出到标准错误端(stderr)的内容 输出到标准输出端(stdout)，便于调试。 理解了fd和dup2的作用后，重定向也就很容易实现了，一种最简单的方法就是先用open函数打开输出文件并得到对应的fd，然后用dup2把标准输出/输入端的指向改成文件的fd。 另外注意用open创建输出重定向的文件的时候要加上S_IRUSR和S_IWUSR选项，否则创建后的文件没有读写权限。（不过好像这个lab的测试数据比较厚道，会事先touch一下，不加这两个选项应该也能通过测试） 一些文档中未定义的行为： argv 假如我输入的命令是/bin/ls -l > ls.txt，对应的argv应该包括哪些内容呢？ 一般的情况argv的内容应该是['/bin/ls’, ‘-l’]，后面的重定向符是不包括的不过在这个lab中似乎没有这个限制，不去掉重定向和管道部分应该还是能通过测试的。 Job ID的分配 如果现在1, 2, 4号子任务在后台运行，再新增一个进程的话应该给它分配多少呢？ 这个问题不需要处理，只要所有的jobs队列操作统一使用tsh.c中给出的几个函数就行。 其他： 关于信号的转发、后台前台的转换等内容，文档和书上都说得很清楚了，这里不再赘述。 P.S. 多进程程序的调试大家之前应该接触的比较少，其实这个lab大致的代码不难写，难点在于细节上的debug比较困难，调试过程对第八章的理解很有帮助。 阅读全文 →

Proceedings of the 2006 IEEE Symposium on Security and Privacy 作者来自密西根大学和微软研究部门 一个利用虚拟机进行攻击的rootkit。 1. Introduction传统的攻击程序通常和安全工具（杀毒软件等）在同一个级别上（kernel mode），两者间没有绝对优势可言，因此有很大的限制，比如强大的功能和良好的隐蔽性不能兼得。而虚拟机的出现则可以解决这个问题，通过把恶意程序放在虚拟机上，可以做到对目标机(guest os)的完全监控，同时目标机完全不会知情。这种程序称为VMBR(virtual-machine based rootkit)。 2. Virtual machinesVMM(virtual-machine monitor)这里就不多介绍了。VMM上跑着一些其他服务进程，主要用于操作系统的debug，运行中的虚拟机的迁移等功能。这些服务的主要面临的一个问题是理解对应的guest os状态和事件。因为在VMM和虚拟机处在不同的抽象级别，前者只能看到磁盘块(disk blocks)，网络包(network packets)，以及内存；而后者则把这些东西抽象为例如文件、TCP连接、变量等概念，这种差异称为语义差异(semantic gap)。 于是有了Virutal-machine introspection(VMI)，它包含了一系列让VMM上的服务了解并修改guest os的技术。 3. Virtual-machine based rootkit design and implementation 3.1 Installation VMBR的安装和一般病毒程序类似，通过欺骗有管理员权限的用户执行安装程序实现。 当目标机是WinXP时，VMBR被安装在第一个活动分区的开始部分；目标机是Linux时，安装程序会禁止swap分区，把VMBR放在swap分区上（够狠的。。。） 修改系统引导信息的时候还有一个细节，直接修改容易被安全检查程序发现。WinXP上的一种解决方案就是尽可能的在所有程序退出之后再修改（通过注册一个LastChanceShutdownNotification事件处理器），并且使用底层的磁盘驱动进行VMBR启动代码的复制，这样可以绕过文件系统层，而大多数反病毒软件都跑在文件系统层上。Linux上，通过修改关机脚本来保证安装程序在其他程序退出后执行。 安装完成后，目标系统的内容就被保存到了一个虚拟磁盘上。重启后就由VMM控制最底层，它把目标机的对虚拟磁盘的访问转换为对应的物理磁盘的访问。 3.2 Malicious servicesVMBR使用一个独立的系统执行各种攻击程序，这样目标机就无法察觉到了。对目标系统的攻击主要分三种： 一种是不需要和目标系统进行交互的恶意服务，例如垃圾电子邮件的发送(spam relays)，DDoS攻击，网络钓鱼(phishing web servers)。 第二种恶意服务需要监视目标系统的数据和事件。通过修改VMM的设备模拟软件就能记录下所有硬件级的数据（比如按键信息、网络包等），而这个过程不需要修改guest os，所以目标系统完全不知情。 VMBR还可以用VMI帮助理解目标系统软件级的抽象信息，VMI可以中断目标系统的任意指令，并重新组织数据。例如一个目标应用程序将要使用一个加密的socket发送信息，攻击者可以截获所有的SSL write函数调用并且在明文被加密前得到它。同样这个过程对目标系统完全透明，因为攻击程序跑在它的外层，或者说是“上帝”层 ;-) 第三种攻击是恶意修改目标系统的执行。例如篡改网络通讯，删除email，改变目标应用程序的行为。最简单的，开了个thttpd web服务器进行网络钓鱼，任何发送到8080端口的TCP请求都会被这个服务器截获。 然后是一个按键记录程序，号称只用了60行代码就搞定了这个模块，然后写了一个254行的带图形界面的程序来分析日志并显示。 一个扫描目标机文件系统的程序，这是一个24小时运行的perl脚本，会把诸如/etc/shadow, user_home/.ssh/id_dsa之类的机密信息保存下来。 最后是防止VMM被目标机侦测到的一个服务。paper中提到了一种叫做redpill的虚拟机侦测手段，通过使用sidt指令。这个指令会读出处理器的中断列表(interrupt descritor table)，在VMM上跑的系统和普通的操作系统读出来的结果不一样，当这个指令在内核态被执行时，VMM会模拟这个指令的执行；但是用户态却不会被截获（考虑到性能因素）。所以redpill通过用户态执行sidt来判断当前系统是否运行在虚拟机上。这篇paper提到的针对redpill的解决方案是在每个可执行文件的sidt指令前设置一个断点，截获这个指令后就模拟这个指令，以此绕过redpill检测。但是这种方法不适合于在程序运行期动态生成二进制的sidt指令的程序（想到我的lab4了，呵呵）。道高一丈魔高一尺（原文是Continuing the arms race，军备战争），通过二进制转换(binary translation)，动态生成的sidt同样可以被截获，但是这种方法的overhead会很大。 3.4 Maintaining Control这块主要讲了对系统重启、关闭的处理。 系统要求重启时，VMBR总是尽可能的通过重启guest os来完成，这样就能最大化的掌握控制权。 阅读全文 →

算法导论第27章，在并行处理的条件下效率很高的排序算法。 介绍如下面左图所示，每条横线(wire)代表一个待 比较的数值，竖线(comparator)表示连接的两条横线要做一次比较，并将较小的值放在输出横线的上方，较大的放在下面。排序过程就是从左往右依次 调用各个comparator（在同一位置上的comparator可以同时做） 有图表示了四个数字3, 2, 4, 1在经过这个Sorting Network时的行为。（由于背景为深色，建议点击图片查看） 下图是一个冒泡排序的Sorting Network表示 可以看到所有的比较都没有并行，效率很低。接下来先介绍一个0-1原理，然后利用它来构造一些比较高效的网络。 性质首先是引理27.1： 对 于输入数据A = <a_1, a_2, .., a_n>，如果某个比较网络(comparison network)的输出是B = <b_1, b_2, …, b_n>，那么对于任一单调递增的函数f，这个网络能把输入数据f(A) = <f(a_1), f(a_2), …, f(a_n)>变为f(B) = <f(b_1), f(b_2), …f(b_3)> 这个引理的证明很简单，关键在于min(f(x), f(y)) = f(min(x,y)) 接下来就是0-1原理： 一个有n个输入数据的比较网络，如果它能将仅由0和1组成的序列正确的排序（这种输入共有2^n种可能），那么它也能正确的将任意数字组成的序列排序。 证明也不难，利用前面的引理反正即可得到这个定理。 双调排序接 下来先考虑双调序列(bitonic sequence)这种特殊情况，所谓双调序列就是先单调递增，后单调递减，或者可以通过环形旋转变化出上述特性的序列，比如<1, 4, 6, 8, 3, 2>和<6, 9, 4, 2, 3, 5>都满足条件（对于后面一种序列，只要把最后的3, 5移到序列开头就行了）。 双调排序(bitonic sorter)有若干步骤，其中有一步叫做half-cleaner，每一次half-cleaner讲数据放到一个深度为1的排序网络中，第i行和第i+n/2行比较(i=1,2,..,n/2) 引理27.3： 做完上述的half-cleaner后，输出的上半部分和下半部分都保持双调的特点，而且上半部分的每个元素都不大于下半部分的任一元素。 分四种情况讨论即可。 通过递归调用half-cleaner即可完成双调队列的排序。要对n个元素进行双调排序Bitonic-Sorter(n)，首先调用Half-Cleaner(n)，将元素分成上下两部分，接着依次对这两部分执行Bitonic-Sorter(n/2)即可。 调用的深度D(n) = lgn 归并网络 书上只给出了对0-1序列排序的算法，任意数字的排序算法留作了习题。 合并网络基于这样一个事实：对于两个已经排序了的序列X = 00000111，Y = 00001111，将Y倒过来后和X拼接的结果是一个双调序列。对这个双调序列再做一次Bitonic-Sorter就能有序。 通 过修改Bitonic-Sorter方法的第一步就能实现Merger，关键在于隐式的反转输入的下半部分。Half-Cleaner方法中比较了第i和 第i+n/2两个元素，如果下半部分反转的话就相当于比较第i和第n-i+1个元素。直接继续执行Bitonic-Sorter方法即可，如下图所示。 阅读全文 →