E6998-2 Questions

11/26
1. LLVM Describe how you may want to attack the SVA architecture. Why is it harder to hack SVA than a regular OS?
2. VMware How can binary translation (which we learned from Valgrind) help virtualization?

11/19
1. ATOM Suppose a program has 1000 branch instructions, and we run the Instrument() routine in Figure 2 over this program. How many calls to CondBranch are inserted? How many calls to PrintBranch are inserted? Now we run the instrumented program. How many times are CondBranch called? How many times are PrintBranch called?
2. ATOM and Valgrind Page 535, first paragraph of the ATOM paper says "ATOM ... does not steal any registers from the application program. ... This enables a number of mechanisms such as signals, setjmp, ... to work correctly without needing any special attention." What does it mean? What is the problem if ATOM steals registers? Use setjmp as an example to explain these sentences. Valgrind apparently steals registers used by the guest program. In fact, its JIT compilation treats instrumentation code and code in guest program equally. How does valgrind handle setjmp? Here is a short explanation of setjmp/longjmp. Here is a more involved explanation.

10/29
1. Bug Study. This is a hard problem. Understand thoroughly the bug and the fixes in Figure 9. The final "fix" is shown in the high-level pseudo code below. Now, your job is to create a thread schedule that induces a race. (Hint: you need three threads.)
```
gcLevel = 1;
atomic {
  remove one element from list;
  last = whether the list is empty;
  if (last)
    state = LANDING;
}
if (last) {
  wait for gcLevel = 0;
  UnpinAtom;
} else {
  if (state == LANDING) {
    gcLevel = 0;
    return;
  }
  MarkAtom;
  gcLevel = 0;
}
```
2. Eraser. You run Eraser on the following program. Will Eraser report any error(s)? Why or why not?
```
struct foo {
    // a and b are of size= 1 bit.
    unsigned a:1,
             b:1;
    lock a_lock; // protects field a.
    lock b_lock; // protects field b.
} f; // global variable f

// Thread T1 runs the code below:

   lock(f.a_lock);
   f.a = 1;
   unlock(f.a_lock);

// Thread T2 runs the code below:

   lock(f.b_lock);
   f.b = 1;
   unlock(f.b_lock);
```
3. Deadlock Immunity. Dimmunix can mispredict if a deadlock is going to occur because its deadlock signature may be imprecise, i.e. Dimmunix's deadlock prediction may have false positives. Create a C program with less than 50 lines of code, on which Dimmunix will generate such a false positive.

10/22
1. Outline how you would use the delta debugging idea to debug a race condition in a multi-threaded program. Assume you have full control over the thread scheduler and can generate whatever thread schedules you want.
2. Outline how you would use slicing to optimize delta debugging.

10/15
1. Failure-oblivious: the paper talks about how to continue execution in face of memory safety errors (e.g. array overflow). Choose three types of bugs other than memory safety errors, and describe how you would apply the failure-oblivious idea to them.
2. Rx + Failure-oblivious: Rx is good, and failure-oblivious is novel, so you decide to run both on your laptop. Describe what may happen.
3. Not just kernels, modern applications take extensions as well, e.g., Outlook, Firefox, Internet Explorer. Describe how you would build a nooks framework for application extensions. Note: in your answer, highlight what becomes easier, and what becomes harder, compared to a kernel nooks approach.

10/8
1. Come up with two bugs: one can be found by eXplode but not by any of the symbolic execution tools, and the other can be found by all three symbolic executions tools but not eXplode. Describe the bugs in less than 50 lines of C code.
2. Come up with two bugs: one can be found by CUTE but not by KLEE (hint: think along the line of unit testing v.s. whole program testing), the other can be found by KLEE but not CUTE. Again, describe the bugs in less than 50 lines of C code.

9/17
1. VeriSoft can only check an acyclic state space. What does it mean? Why? Consider the following philosopher who never stops eating:
```
   philosopher(i)
   {
       while(1)
       {
             // thinks
             semwait(i);
             semwait((i+1)%N);
             // eats
             semsignal(i);
             semsignal((i+1)/N);
       }
   }
   
```
  How would you fix VeriSoft's algorithm so the above always-starving philosopher is not a problem?
2. VeriSoft uses partial order reduction (POR) to soundly reduce the state space it searches. It assumes that processes communicate by performing operations on communication objects. How do you apply POR to a multi-threaded program where all threads share the same address space and communicate by modifying shared variables? What would be the runtime overhead of your approach? Can you make it faster?
1. How is FiSC's model checking approach different from VeriSoft? What are the pros and cons?
2. FiSC is tailored for checking file systems. Where does FiSC exploit this fact to make things easier?