- Due 12/13
- eXplode. Identify three places where eXplode simplifies model checking by exploiting the fact that it is checking storage systems.
- Malicious disk. The paper presents the rewrite transformation for if-statement. Show the rewrite transformation for a for loop.
- Due 12/06
- Meta Compilation. Explain what the following text
means (in the paragraph above Section 5.3)
"Without Independence the number of times that we analyze each program point would grow exponentially with the number of variable-specific instances."
If this Independence assumption does not hold, what lines in Figure 4 must be changed? Explain. - Deviant behavior. Given a C code example with fewer than 50 lines that causes the internal-null checker to emit a false positive.
- Due 11/29
- Valgrind. Write a C program with fewer than 100 lines that makes valgrind yield the worst performance. Justify your answer. Compile and run this program on moscow.clic.cs.columbia.edu; report the original execution time and execution time with Valgrind.
- Program shepherding. Write C-like pseudo code to implement the policy that a return may only return to the instruction after the Call instruction.
- Due 11/22
- Hybrid race detection. Construct a code example with fewer than 50 lines that can demonstrate reductions using the Oversized Lock Condition.
- RaceFuzz.Construct a code example with fewer than 50 lines that contains a race and RazeFuzzer has a probability 1/1024 of detecting that race.
- Due 11/15
- Concurrency error study. The Firefox order bug
referred to in the paper is a very complicated bug. The
following pseudo code captures the bug.
void js_DestroyContext() { if (last) { // last thread state = LANDING; ** wait for gcLevel = 0; gcPoke = true; js_GC(); while (gcPoke) js_GC(); FreeAtomState(); } else { gcPoke = true; js_GC(); } } void js_GC() { * if (state == LANDING) return; gcLock.acquire(); if (!gcPoke) { gcLock.release(); return; } if (gcLevel > 0) { gcLevel++; wait for gcLevel == 0; gcLock.release(); return; } gcLevel = 1; gcLock.release(); restart: MarkAtomState(); gcLock.acquire(); if (gcLevel > 1) { gcLevel = 1; gcLock.release(); goto restart; } gcLevel = 0; gcPoke = false; gcLock.release(); }
In the above code, FreeAtomState() races with MarkAtomState(). The line starts with * correspond to first "fix" developers added; the line starts with ** correspond to the "final fix". However, the bug is still not fixed yet. Draw a schedule to show the race remaining in this code. - Eraser. Would Eraser report a race for the following
code? Why or why not?
foo(int x) { pthread_t child; pthread_create(&child, NULL, bar, (void*)&x); pthread_join(child, NULL) x = 10; } bar(int *x) { x = 100; }
- Due 11/8
- ClearView. The paper says that one can just plug in new error monitors to make ClearView work with new defect types. Is it so? Justify your answer.
- ClearView and Rx. Both systems can recover from errors. Describe a scenario where you prefer RX over ClearView and a scenario where you prefer ClearView over RX.
- Due 10/25
- Pros of Failure oblivious and ASSURE. The papers talk about how to continue execution in face of errors.Choose three types of bugs other than memory safety errors (e.g. array overflow), and describe how you would apply the failure-oblivious or ASSURE ideas to recover from them.
- Cons of Failure oblivious and ASSURE. Describe a scenario in which the approaches of failure oblivious and ASSUE make a fault worse.
- Due 10/18
- Delta Debugging. 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.
- Statistical Debugging. Outline how you would use the statistical debugging idea to debug a race condition for software with many users.
- Due 10/11
- Amsterdam. In Heuristic Metamorphic Testing, described in Section 5, false negatives are possible in that the framework may say that no bug exists when, in fact, one actually does. How can this happen? What can be done about it?
- Amsterdam. In the empirical study, what sorts of other "mutations" could have been used to seed defects in the applications? Do you think the approach would be effective at detecting these defects? Why or why not?
- Corduroy. Whereas the first paper uses metamorphic properties of the entire system, this paper suggests using properties of individual functions to perform the metamorphic testing. Do you think this approach would be more effective in detecting the types of defects described in the study from the first paper? Why or why not?
- Due 10/4
- seL4. Describe the cost associated with adding a shortest-job-first scheduler to seL4.
- RESIN. Write pseudo code to implement the first strategy for preventing SQL injection attacks.
- Due 9/27
- PRES v.s. ODR. These two systems use similar algorithms
to reproduce race (or race triggered failures). Some of the errors
they used appear to be the same as well. However, their results
seem very different.
- Compare Table 5 in PRES and Figure 13 in ODR. ODR seems to require more runs to reproduce a bug. Can you explain this difference?
- Compare Table 7 in PRES and the first few paragraphs in Section 9.3.1 in ODR. The two papers seem to report very different number of races. Can you explain this difference as well?
- Due 9/20
- Liblog wrappers. Write pseudo code to implement liblog wrappers for read() and write(). Hint: what special processing do you have to do to the file descriptors?
- You are Kendo expert. The algorithm in Figure 4 solves
the deadlock problem in Figure 3 yet still ensures deterministic
execution. If we change the line
if(l.released_logical_time >= get_logical_clock())
toif(l.released_logical_time - 10 >= get_logical_clock())
will the execution be deterministic? Support your answer with concrete thread schedules. - Liblog practices Kendo.
- Your distributed system has very good throughput and performance on multicore processors because it has multiple threads. You love Liblog and integrated it with your distributed system. Unfortunately, you noticed a performance and throughput drop. What's going on?
- How do you adapt the techniques learned in Kendo to solve this problem? Assuming you are a good programmer and your distributed system is free of race conditions.