Reliable Software: Junfeng Yang

Due 12/8

Prepare one good question about the determinism verification papers and ask Martin the question during his talk.

Due 12/1

RaceFuzzer. Section 5.3 shows a bug example, which is the only bug example in the paper. Unfortunately, this "bug" is actually a false positive. Explain why.
Hybrid Race Detector. Construct a code example with fewer than 50 lines that shows that the Oversized Lock Condition reduces the number of events to track.

Due 11/17

Prepare two good questions about Determinator and ask Bryan about these questions.

Due 11/10

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(true);
        while (gcPoke)
            js_GC(true);
        FreeAtomState();
    } else {
        gcPoke = true;
        js_GC(false);
    }
}

void js_GC(bool last) {
*   if (state == LANDING && !last) 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 starting with * corresponds to first "fix" developers added; the line starting with ** corresponds to the "final fix". However, the bug as shown above is still not fixed yet. Draw a thread interleaving that causes the bug to manifest.

Eraser. Would Eraser report a race on the following code? Why or why not?

int x = 0;
main() {
    pthread_t child;
    pthread_create(&child, NULL, bar, NULL);
    pthread_join(child, NULL)
    x = 10;
}

bar(void* unused) {
    x = 100;
}

Due 11/3

Respec. The paper claims that one motivating application of online replay is decoupled checks. The idea is to perform expensive checks in replayed executions so that we avoid slowing down normal executions. What may go wrong though?
Kivati. Suppose we recorded a multiprocessor execution using SMP-revirt. The execution unfortunately had a data race. Instead of using page protections, how can you use the watchpoint trick in Kivati to make the replayed executions deterministic? Write detailed pseudo code to implement your idea.

Due 10/27

Liblog. Write pseudo code to implement the liblog wrappers to send() and recv().
SMP-revirt. Write pseudo code to implement the CREW protocol. Note: be specific about how you modify page table permissions, and make sure your pseudo code is deterministic.

Due 10/20

Context-sensitive Alias analysis. How would you adapt the algorithm described to compute context-sensitive alias relations for C programs? What features of C make it difficult? Be specific.

Due 10/13

EXE. Construct a worst case example to make the array-based refinement algorithm add n(n-1)/2 array axioms. State the assumptions you make.
Bouncer. If you remove the WrittenBetween condition in Figure 5, the algorithm 5 becomes incorrect. Construct a code example to show why the algorithm becomes incorrect.

Due 10/6

Memcheck. Would valgrind --tool=memcheck detect the buffer overrun in the following code? Why or why not?
```
  int foo(void) {
      int a[2] = {0};
      a[2] = 10; // off by 1
  }
            
```
TaintDroid. How can you steal private data without being caught by TaintDroid? Show your idea by writing pseudo code to steal 1-bit of secrecy.

Due 9/29

Loom. In Section 4.3, the authors claim: "Note that the statement if(wait[stmt id]) in Figure 10 is for performance, not correctness." What does it mean? Do you agree?
Tern. Write pseudo code to implement the pthread_create wrapper of the memoizer. Note you need to describe your data structure for maintaining deterministic thread IDs. In addition, think of what may go wrong when the child thread calls self().

Due 9/22

Pin. Write a Pin module that replaces malloc() calls with my_malloc() calls. You can get Pin from here. What're the pros and cons of the Pin approach v.s. the LLVM approach in solving this problem?
Detours. What may go wrong if you apply Detours to target functions written in assembly?

Due 9/15

LLVM. Write a LLVM pass that transforms malloc() calls to my_malloc() calls. You may want to download and install LLVM to try your pass. You can get the GCC frontend and LLVM backend from this link.
bddbddb. Write a Datalog program to look for cases when a piece of memory is allocated by p = malloc() but is never freed by free(p). Note you don't need to try your program with bddbddb because the version you can download from sourceforge only supports Java.

E6998-1 Reliable Software

Fall 2010 -- Junfeng Yang