W4118 OPERATING SYSTEMS I

Homework 6 is due 05/04 at 12:01am EDT

The test program is due 04/27 at 12:01am EDT

Chia-yu will be holding a TA session on this homework at CSB 477 (the open area) from 10-12 on Friday, April 16.

The written problems are to be done individually. The programming problems are to be done in your assigned programming groups. All homework submissions are to be made via Courseworks. Refer to the homework policy section on the class web site for further details.

Written Assignment (40 pts)

Exercise numbers refer to the course textbook, Modern Operating Systems. Each problem is worth 4 points. Make your answers concise. You'll lose points for verbosity.

1. MOS 5.15
2. MOS 5.21
3. MOS 4.5
4. MOS 4.11 & 4.12
5. MOS 4.19
6. MOS 4.21
7. MOS 4.27
8. MOS 4.32
9. MOS 4.33
10. The ext3 fsck program recovers a crashed ext3 file system by scanning the journal of this file system and replaying each record in the journal. The ext3 fsck program also clears the journal to save space for new journal records. Is there a strict order between the two steps? Justify your answer.

Please complete and submit a private group programming assignment evaluation. The evaluation should be in a separate file called evaluation.txt that is submitted with your individual written assignment submission.

Programming Assignment: Prevent Time-of-Check-to-Time-of-Use attacks on Linux file systems (60 pts)

Programming problems are to be done in your assigned groups using copies of the virtual machine (VM) image already provided. For all programming problems you will be required to submit source code, a README file documenting your files and code, and a test run of your programs. In addition, you should submit a cover sheet using either homework_work.txt or homework_nonwork.txt, depending on whether or not the programming assignment is completely working or not. For source code submissions, you only need to submit new source code files that you created and kernel source code files that you changed. You should clearly indicate your names, email addresses, and assigned group number on your submission. Each group is required to submit one writeup for the programming assignment.

You will build your own Linux kernel for this class. The image of the kernel you build for this assignment should be vmlinuz.hmwk6. Grading for this assignment will be done based on vmlinuz.hmwk6. You will base your changes on the 2.6.11 kernel that you installed for Homework 2, but without the modifications you made for the new systems calls you wrote for Homework 2. In particular, submitted kernel patches should be patched against your modified KDB-enabled kernel from Homework 2, i.e. do not include KDB code in your patch.

Description

A TOCTOU attack is a popular type of file system attack that allows an attacker to access files that she has no permission to access. To launch a TOCTOU attack, an attacker need exploit a race condition in a setuid program. A setuid program is a special kind of program that runs with root privilege on a regular user's behalf. Such a program is dangerous because its root privilege allows itself to access whatever files in the file system, yet it can be invoked by a regular user. Thus, a setuid program must carefully check that the user invoking the program has the right permissions, before it goes ahead and accesses a file on the user's behalf. Moreover, it must ensure that the check step and the use step are one atomic operation, or an attacker may slip in and change the file to something else that she has no permission to access.

The code below shows an example TOCTOU attack on a buggy setuid program:

        buggy setuid program                               attacker

                                                     // create a file the attacker can access
                                                     touch /home/attack/bad
   // check user permissions to file
   if (access("/home/attack/bad", R_OK) != 0) {
       exit(1);
   }
                                                     // remove file
                                                     rm /home/attacker/bad

                                                     // create a symbolic link to a secret file
                                                     ln -s /top/secret /home/attack/bad
   // use file
   fd = open("/home/attacker/bad", O_RDONLY);
   // Do something about fd...

In the above example, the buggy setuid program checks user permissions to file "/home/attack/bad" then accesses the file. Unfortunately, these two steps are not atomic, and an attacker can replace the file with a symbolic link to "/top/secret" in between, to get access to files she can't access.

The following example shows a variant of the TOCTOU attack you just saw. It exploits the same vulnerable setuid program, but using a symbolic link instead of a regular file.

        buggy setuid program                               attacker

                                                     // create a symbolic link to a file the attacker can access
                                                     ln -s /home/attack/bad /home/attack/symlink
   // check user permissions to file
   if (access("/home/attack/symlink", R_OK) != 0) {
       exit(1);
   }
                                                     // update symbolic link to a secret file
                                                     ln -sf /top/secret /home/attack/symlink
   // use file
   fd = open("/home/attacker/symlink", O_RDONLY);
   // Do something about fd...

In this assignment, you will create a new defense mechanism against Time-of-Check-to-Time-of-Use (TOCTOU) attacks on Linux file systems. Your defense mechanism will focus on the prevention of a key step in the attack that replaces an existing file or symbolic link with a symbolic link to a secret file. The idea is, once a process calls access(pathname, ...), your mechanism will pin all components of pathname, so that it can fail all subsequent attempts by other processes to remove pinned path components or update pinned symbolic links.

Of course you cannot pin files or directories forever. You should unpin a file or directory after 20 timer interrupts have occurred since it was pinned. This period of 20 time interrupt can be viewed as a grace period for the process that has called access() to really access the file. An alternative design is to unpin a file or directory after the process calls open(pathname, ...), but we will not use this design because the process may call open(pathname, ...) multiple times and it's incorrect to unpin on first open().

You will implement your defense mechanism in the VFS layer in Linux, so that you can prevent TOCTOU attacks for all Linux file systems. Linux VFS represents each file or directory as a struct inode object in memory, which your defense mechanism should operate on.

You are strongly advised to read Understanding Linux Kernel Chapter 12 Virtual File System before starting the programming assignment. You may also find Chapter 18 The Ext2 and Ext3 File Systems useful.

1. (50 pts.) Design and implement a TOCTOU defense mechanism for Linux file systems

   1. Add the following three functions (not system calls)) to the Linux kernel :

      void pin_inode(struct inode *inode); // pins the specified inode

      void unpin_inode(struct inode *inode); // unpins the specified inode

      int inode_pinned(struct inode *); // tests if the specified inode is pinned

      You are free to change the signatures of these functions to fit your design.

      Hint: Since multiple processes may call access() on the same file, your implementation of these functions must handle that case that a single inode is pinned by multiple processes.

   2. Modify VFS to pin and unpin inodes.

      When a process calls access(pathname, ... ), your code must pin all inodes along pathname by calling pin_inode(). In case that pathname is a relative path, your code must also pin all inodes from the current working directory of the process to the file system root.

      After 20 timer interrupts have occurred since the inodes were pinned in previous step, your code must unpin all the inodes that was pinned in previous step by calling unpin_inode(). Note an inode may be pinned by multiple process, and you should keep track of the grace periods for these processes separately.

      Hint: Linux uses function path_lookup(const char *name, unsigned int flags, struct nameidata *nd) to resolute a pathname into a file or directory. The name argument is the pathname to resolute. The flags argument indicates what kind of path lookup should be performed. The nd argument stores intermediate or final results of the path resolution. You may want to modify this function to perform pinning of inodes. Specifically, you may create a LOOKUP_PIN flag in include/linux/namei.h to indicate the need to pin inodes. You may also add an extra field to nameidata to record the list of inodes you'd like to pin.

   3. Modify VFS to prevent removal of a pinned file or directory by a process if the file or directory is pinned by at least another process.

      Hint: Linux VFS uses may_delete to check if a file or directory may be removed. You may want to implement the removal check within this function.

   4. Modify VFS to prevent modifications of a pinned symbolic link by a process if the symbolic link is pinned by at least another process.

      Hint: Linux VFS uses may_open to check if a file or directory may be opened. You may want to implement the modification check within this function.

   Your solution should have the appropriate synchronization mechanisms. It should also correctly handle normal file system operations (like creating/deleting files, umount/mount filesystem).

   You should properly handle errors that may occur and report meaningful error codes. As always, you are encouraged to look for existing kernel code that performs similar tasks and follow the conventions and practices it provides.

2. (10 pts.) Write a test program for the TOCTOU protection mechanism

   You should create a setuid program with an TOCTOU vulnerability. You can reuse the vulnerability shown at the beginning of this homework page. To create a setuid program, You can create an executable program as root then run the following commands:

       # make program world readable
       $ chmod a+r  
       # set setuid bit for the program            
       $ chmod ug+s 
           

   You should also create a normal user in your virtual machine using the useradd program (e.g., useradd alice). Then, you should create testcases that test for TOCTOU attacks on regular files, directories, and symbolic links using commands such as ln, mv, and rm.

Additional Information

Backup your kernel changes outside your VM often. Sometimes your virtual disk can get corrupted, and you may lose all changes you've made. Remember, as a safety measure, you are strongly encouraged to backup your VMware image from time to time. printk statements in system calls will print their output to the console whenever they are invoked. To request printk messages be sent to a log file, insert the following line into the /etc/syslog.conf file: kern.* /var/kern.log This will cause printk messages to be written to /var/kern.log. You can send a signal to request the syslog daemon re-read the updated /etc/syslog.conf file, with the command "kill -1 pid" where pid is the pid of the syslogd process. A lot of your problems will come from system administration issues. If nobody in your group in familiar with unix, you might want to pick up a book on Unix/Linux system administration. You can find some Linux programming tips at the course resources page.