CS 354 Spring 2021

Lab 4: Enhanced Kernel IPC and Run-time Modification of Process Behavior (310 pts)

Due: 04/07/2021 (Wed.), 11:59 PM

1. Objectives

The objectives of this lab are, one, to enhance XINU's IPC services by adding receiver message queues and supporting blocking message send, receive()/send() system calls, and two, to utilize run-time stack manipulation to modify and monitor process behavior in the XINU kernel.

2. Readings


Please use a fresh copy of XINU, xinu-spring2021.tar.gz, but for preserving the myhello() function from lab1 and removing all code related to xsh from main().

3. IPC with receiver message queue: qreceive() and qsend() [80 pts]

Implement system calls, umsg32 qreceive(), in system/qreceive.c, and syscall qsend(pid32 pid, umsg32 msg) in system/qsend.c that use a per-process receiver FIFO queue to store up to RECVQSIZE (defined in include/process.h as 5) messages transmitted by senders using qsend(). Introduce a new process table field, umsg32 prrecvqueue[RECVQSIZE], that acts as a circular buffer to store messages. Two additional fields, prqrecvbeg and prqrecvend of type uint16, are used to manage the circular FIFO queue. prqrecvbeg specifies the index of precvqueue[] where the first unread message is stored, which is meaningful only when Boolean flag prhasmsg is set. prqrecvend specifies the first free slot of prrecvqueue[] where a new message can be stored. If prhasmsg is set and prqrecvbeg equals prqrecvend then it means that the queue is full. The queue is empty if prhasmsg is 0. Thus qreceive() is an extension of receive() that supports a FIFO IPC message queue of size RECVQSIZE.

A second feature of qreceive() is that a message's sender PID is conveyed to the receiver process through global variable, pid32 senderpid, declared in initialize.c whose value is meaningful when qreceive() returns. Sender PIDs are remembered in process table field, pid32 prsenderpid[RECVQSIZE]. Hence a new message arrival, if there is free buffer space in the receiver, causes two pieces of information to be queued: the message itself and the sender's PID. Test and verify that your IPC extension works correctly. Describe in lab4ans.pdf the test cases you have used to gauge correctness.


4. Blocking IPC send(): qsendb() and qreceiveb() [80 pts]

qsend() which is an extension of send() to be compatible with qreceive() is nonblocking so that a sender returns immediately from qsend() if the receiver's FIFO queue is full. In this problem, implement a blocking version of qsend(), syscall qsendb(pid32 pid, umsg32 msg) in system/qsendb.c, and its counterpart umsg32 qreceiveb() in system/qreceiveb.c to support blocking message send. If the receiver's message queue is full, instead of returning immediately SYSERR the sender process is blocked by changing its process state to a new state, PR_SENDERBLK, defined in a include/process.h as 12. The scheduler, resched(), is called which context-switches out the sender and context-switches in a highest priority ready process. The blocked sender's PID is remembered in a FIFO circular buffer of size NUMSENDERBLK at the receiver. Set NUMSENDERBLK as 3 in process.h. Hence up to NUMSENDERBLK sender processes can be blocked when the receiver's message buffer of size RECVQSIZE is full. If the number of blocked sender processes exceeds NUMSENDERBLK, qsendb() behaves in a nonblocking manner and returns immediately SYSERR.

Add process table fields, pid32 prsenderblkid[NUMSENDERBLK], and prsndblkbeg, prsndblkend of type uint16 to implement a circular FIFO buffer to remember blocked sender processes. Add process table field, uint16 prnumblockedsenders, which specifies the number of blocked senders. To store a blocked process's message, introduce process table field, umsg32 prsendermsg. When qreceiveb() is called, it checks if there are any blocked senders. If so, its message stored in prsendermsg is copied to the receiver's message queue. Then the sender is unblocked by changing its state from PR_SENDERBLK to PR_READY after which resched() is called. As we discussed the necessity of receive()'s local variable, umsg32 msg, to assure correctness, be mindful that the receiver process may be preempted by the unblocked sender if it has higher priority. Shared variables must not get corrupted when execution of multiple processes becomes interleaved in time due to scheduling. If making modifications to resched() to be compatible with qsendb() and qreceiveb(), make sure that your code is backward compatible with legacy XINU. That is, if your modified resched() were to replace the legacy resched() in xinu-spring2021.tar.gz, it would work correctly subject to well-defined and minimal modification of XINU's source code. Describe in lab4ans.pdf how you achieve that. Test and verify that your IPC extension works correctly. Describe in lab4ans.pdf the test cases used to gauge correctness.


5. Modifying process behavior at run-time [80 pts]

For builders of software systems and those that may seek to compromise them, modifying run-time behavior is an important software engineering tool in the arsenal. In the next three problems, we will take an adversarial approach to induce running programs to behave in a manner they were not designed and implemented to do.

5.1 Wrong turn I [30 pts]

Code an app, void wrongturnI(pid32 z), in wrongturnI.c that checks if a process with pid z exists and that it is suspended. If so, wrongturnI() checks if this process is a newly created process that has never executed. To do so, utilize the fact that the stack of a newly created process "looks different," hence can be distinguished from processes that have executed before and then have been context-switched out. Do not use the value of prstate field in the process table which cannot be used to differentiate from suspended processes that have executed before. Explain in lab4ans.pdf your method for identifying newly born processes based on properties of their stack.

If process z is not a newly created process in suspended state, wrongturnI() terminates. Otherwise, wrongturnI() uses the saved stack pointer of the process (prstkptr) in its process table entry to find the location in the stack where ctxsw()'s return address is located. wrongturnI() overwrites the return address with the address of its malware, void malwareI(void), in malwareI.c which prints the value returned by getpid() and a suitable message containing string "malwareI success" and terminates. The newly born process, void abc(void) in abc.c, under normal operation when it is resumed, prints a different message containing the value returned by getpid() and string "normal execution" before returning. Test and verify that wrongturnI() works correctly.

5.2 Wrong turn II [25 pts]

Code an app, void wrongturnII(pid32 z), in wrongturnII.c that checks if process z exists and is ready. If not, wrongturnII() terminates. Otherwise, wrongturnII() uses process z's saved stack pointer to access the address in its stack where the return address of resched() is located. wrongturnII() overwrites the return address with the address of malwareI().

Explain in lab4ans.pdf your method for determining the location of resched()'s return address in process z's stack. Test and verify that wrongturnII() works correctly.

5.3 Wrong turn III [25 pts]

Hackers who attack computing systems must have specific information about a victim system's vulnerability that can be exploited. Sometimes such information is imprecise in which case hackers may resort to crude forms of attack. In the case of 5.1, an attacker may not know the exact location in the stack where the return address of ctxsw() is located. A common method is to overwrite a block of locations in the stack with malwareI()'s address in the hope of hitting the jackpot, i.e., overwriting the correct location from 5.1.

Code an app, void wrongturnIII(pid32 z), under the assumption that it knows the top of stack address of process z but does not know the precise location where the return address of ctxsw() is located. That is, besides that it is somewhere above the top of stack address. Note that "above" means "below" in the stack of process z since stacks grow from high to low memory. Test if overwriting a sufficient number of words starting at the top of the stack induces successful jump to malwareI() when ctxsw() returns. The crude attack overwrites state information saved by ctxsw() in addition to overwriting its return address. Discuss in lab4ans.pdf what, if any, consequences this has on successfully jumping to the attacker's malwareI() function and its correct execution.


6. Thwarting stack overflow attack [70 pts]

The method of 5.3 is the basis for the most widespread attack on networked systems since the 1980s, also called buffer overflow, stack overflow (or smashing) attack. A software technique aimed at thwarting 5.3 performs integrity checking of return addresses before executing actual jumps. A common method, by default utilized by gcc on Purdue CS computing systems, is to insert a specific bit pattern (e.g., 32-bit word in our Galileo x86-32) below the return address that is to be protected. Say the bit pattern, called canary, is all 0's. When a hacker engages in crude attacks of the 5.3 variety, the canary bit pattern below the actual return address is likely to be overwritten as well. In the case of gcc, the compiler inserts code before a function executes the ret instruction which checks that the canary bits are intact. If not, i.e., integrity check has failed, the process is terminated to prevent jumping to malware code that can harm the system. As a side note, before the introduction of physical sensors, coal miners took along canaries underground because they possess sensitive respiratory systems. If noxious gases are released, canaries would be incapacitated first which served as an alarm to evacuate. The canary bit pattern plays a similar role. Note that the canary integrity check is imperfect (e.g., does not work for surgical attack 5.2 that leaves the canary undisturbed) and incurs overhead since potentially every return address must be guarded.

In this problem, implement a kernel version of the canary defense by modifying ctxsw() so that it checks integrity of its return address before executing ret. Upon invocation by resched(), ctxsw() pushes a 32-bit canary word of all 0's onto its stack. In production systems the canary is an irregular bit pattern that is less easily recognized by hackers. Then ctxsw() proceeds with the regular task of checkpointing the "old" process being context-switched out and context-switching in the "new" process. Before executing ret, ctxsw() checks that the canary remained intact. If so, the canary is popped before executing ret. Otherwise, ctxsw() calls a function, void hackalert(void), in system/hackalert.c that prints a message "stack smashing detected" and calls exit() to terminate the compromised process. Save the modified ctxsw.S and any other modified kernel code to implement your solution to Problem 6 under lab4/v2. Save legacy copies of the files in lab4/v1. Test and verify that your kernel solution for guarding the return address of ctxsw() works correctly. In particular, attack 5.3 should now fail.


Bonus problem [30 pts]

In Problem 4 where XINU is extended to support blocking message send, it may happen that while one or more sender processes are waiting in PR_SENDERBLK state the receiver process terminates. Modify the code of Problem 4 so that blocked sender processes are unblocked (i.e., state changed to PR_READY) and qsendb() returns SYSERR. Note that as with semdelete() of a semaphore that one or more processes are waiting on, all blocked sender processes must be put into ready state and inserted into XINU's readylist before calling resched() once. Save the files containing code changes from Problem 4 in lab4/v3.

Note: The bonus problem provides an opportunity to earn extra credits that count toward the lab component of the course. It is purely optional.


Turn-in instructions

General instructions:

When implementing code in the labs, please maintain separate versions/copies of code so that mistakes such as unintentional overwriting or deletion of code is prevented. This is in addition to the efficiency that such organization provides. You may use any number of version control systems such as GIT and RCS. Please make sure that your code is protected from public access. For example, when using GIT, use git that manages code locally instead of its on-line counterpart github. If you prefer not to use version control tools, you may just use manual copy to keep track of different versions required for development and testing. More vigilance and discipline may be required when doing so.

The TAs, when evaluating your code, will use their own test code (principally main()) to drive your XINU code. The code you put inside main() is for your own testing and will, in general, not be considered during evaluation.

If you are unsure what you need to submit in what format, consult the TA notes link. If it doesn't answer your question, ask during PSOs and office hours which are scheduled M-F.

Specific instructions:

1. Format for submitting written lab answers and kprintf() added for testing and debugging purposes in kernel code:

2. Before submitting your work, make sure to double-check the TA Notes to ensure that any additional requirements and instructions have been followed.

3. Electronic turn-in instructions:

        i) Go to the xinu-spring2021/compile directory and run "make clean".

        ii) Go to the directory where lab4 (containing xinu-spring2021/ and lab4ans.pdf) is a subdirectory.

                For example, if /homes/alice/cs354/lab4/xinu-spring2021 is your directory structure, go to /homes/alice/cs354

        iii) Type the following command

                turnin -c cs354 -p lab4 lab4

You can check/list the submitted files using

turnin -c cs354 -p lab4 -v

Please make sure to disable all debugging output before submitting your code.


Back to the CS 354 web page