6.2.3: Problem Sets 21-30

Last updated
Save as PDF

Page ID: 76176

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Problem Set 21: Speedy Taxi Company$^*$

$^*$ Credit for developing this problem set goes to Robert T. Morris

2008–2–9

(Chapter 3)

The Speedy Taxi company uses a computer to help its dispatcher, Arnie. Customers call Arnie, each asking for a taxi to be sent to a particular address, which Arnie enters into the computer. Arnie can also ask the computer to assign the next waiting address to an idle taxi; the computer indicates the address and taxi number to Arnie, who informs that taxi over his two-way radio.

Arnie's computer stores the set of requested addresses and the current destination address of each taxi (if not idle) in an in-memory database. To ensure that this information is not lost in a power failure, the database logs all updates to an on-disk log. Since the database is kept in volatile memory only, the state must be completely reconstructed after a power failure and restart, as in Figure 3.4.6. The database uses write-ahead logging as in Chapter 3: it always appends each update to the log on disk, and waits for the disk write to the log to complete before modifying the cell storage in main memory. The database processes only one transaction at a time (since Arnie is the only user, there is no concurrency).

The database stores the list of addresses waiting to be assigned to taxis as a single variable; thus any change results in the system logging the entire new list. The database stores each taxi’s current destination as a separate variable. A taxi is idle if it has no address assigned to it.

Consider one action that uses the database: DISPATCH_ONE_TAXI . Arnie's computer presents a UI to him consisting of a button marked DISPATCH_ONE_TAXI . When Arnie presses the button, and there are no failures, the computer takes one address from the list of addresses waiting to be assigned, assigns it to an idle taxi, and displays the address and taxi to Arnie.

Here is the code for DISPATCH_ONE_TAXI :

1 procedure DISPATCH_ONE_TAXI () 2 BEGIN_TRANSACTION 3 // read and delete the first address in list 4 list ← READ () 5 if LENGTH (list) < 1 then 6 ABORT_TRANSACTION 7 address ← list[0] 8 DELETE (list[0]) 9 WRITE (list) 10 // find first free taxi 11 taxi_index ← -1 12 for i from 0 until NUMBER_OF_TAXIS - 1 13 taxis[i] ← READ () 14 if taxis[i] = NULL and taxi_index = -1 then 15 taxi_index ← i 16 if taxi_index = -1 then 17 ABORT_TRANSACTION 18 // record address as the taxi’s destination 19 taxis[taxi_index] ← address 20 WRITE (taxis[taxi_index]) 21 COMMIT_TRANSACTION 22 display “DISPATCH TAXI ” + taxi_index + “ TO ” + address

When Arnie starts work, list contains exactly two addresses: a₁ and a₂. There are two taxis ( taxis[0] and taxis[1] ) and both are idle ( NULL ). Arnie pushes the DISPATCH_ONE_TAXI button, but he sees no DISPATCH TAXI display, and the computer crashes, restarts, and runs database recovery. Arnie pushes the button a second time and again sees no DISPATCH TAXI display, and again the computer crashes, restarts, and runs recovery. There is no activity beyond that described or necessarily implied.

Q21.1 If you were to look at last few entries of the database log at this point, which of the following might you see, and which are not possible? B_x stands for a BEGIN record for transaction ID x , M_x is a MODIFY (i.e. change) record for the indicated variable and new value, and C_x is a COMMIT record.

A. No log records corresponding to Arnie's actions.
B. B_101; M_101list = a₂; M_101taxis[0] = a₁; C_101; B_102; M_102list = (empty); M_102taxis[1] = a₂; C_102
C. B_101; M_101 list = a₂; M_101 taxis[0] = a₁; B_102; M_102 list = (empty); M_102 taxis[1] = a₂
D. B_101; M_101 list = a₂; M_101 taxis[0] = a₁; C_101; B_102; M_102 list = a₂; M_102 taxis[0] = a₁
E. B_101; M_101 list = a₂; M_101 taxis[0] = a₁; B_102; M_102 list = a₂; M_102 taxis[0] = a₁

Suppose again the same starting state (the address list contains a₁ and a₂, both taxis are idle). Arnie pushes the button, the system crashes without displaying a DISPATCH TAXI message, the system reboots and runs recovery, and Arnie pushes the button again. This time the system does display a DISPATCH TAXI message. Again, there is no activity beyond that described or necessarily implied.

Q21.2 Which of the following are possible messages?

A. DISPATCH TAXI 0 TO a₁
B. DISPATCH TAXI 0 TO a₂
C. DISPATCH TAXI 1 TO a₁
D. DISPATCH TAXI 1 TO a₂

Arnie questions whether it's necessary to make the whole of DISPATCH_ONE_TAXI a single transaction. He suggests that it would work equally well to split the program into two transactions, the first comprising lines 2 through 9, and the other comprising lines 12 through 21. Arnie makes this change to the code.

Suppose again the same starting state and no other activity. Arnie pushes the button, the system crashes without displaying a DISPATCH TAXI message, the system reboots and runs recovery, and Arnie pushes button again. This time the system displays a DISPATCH TAXI message.

Q21.3 Which of the following are possible messages?

A. DISPATCH TAXI 0 TO a₁
B. DISPATCH TAXI 0 TO a₂
C. DISPATCH TAXI 1 TO a₁
D. DISPATCH TAXI 1 TO a₂

Problem Set 22: Locking for Transactions Exercise$^*$

$^*$ Credit for developing this problem set goes to Robert T. Morris.

2008–3–14

(Chapter 3)

Alyssa has devised a database that uses logs as described in Section 3.4. The logging and recovery works as shown in Figure 3.4.6 (the in-memory database with write-ahead logging). Alyssa claims that if programmers insert ACQUIRE and RELEASE calls properly they can have transactions with both before-or-after and all-or-nothing atomicity.

Alyssa has programmed the following transaction as a demonstration. As Alyssa claims, it has both before-or-after and all-or-nothing atomicity.

T₁: BEGIN_TRANSACTION () ACQUIRE (X.lock) ACQUIRE (Y.lock) X ← X + 1 if X = 1 then Y ← Y + 1 COMMIT_TRANSACTION() RELEASE (X.lock) RELEASE (Y.lock)

X and Y are the names of particular database fields, not parameters of the transaction.

Q22.1 The database starts with contents X=0 and Y=0. Two instances of T₁ are started at about the same time. There are no crashes, and no other activity. After both transactions have finished, which of the following are possible database contents?

A. X=1, Y=1
B. X=2, Y=0
C. X=2, Y=1
D. X=2, Y=2

Ben changes the code for T₁ to RELEASE the locks earlier:

T_1b: BEGIN_TRANSACTION () ACQUIRE (X.lock) ACQUIRE (Y.lock) X ← X + 1 if X = 1 then Y ← Y + 1 RELEASE (X.lock) RELEASE (Y.lock) COMMIT_TRANSACTION ()

With this change, Louis suspects that there may be a flaw in the program.

Q22.2 The database starts with contents X=0 and Y=0. Two instances of T_1b are started at about the same time. There is a crash, a restart, and recovery. After recovery completes, which of the following are possible database contents?

A. X=1, Y=1
B. X=2, Y=0
C. X=2, Y=1
D. X=2, Y=2

Ben and Louis devise the following three transactions. Beware: the locking in T₂ is flawed.

T₂: BEGIN_TRANSACTION () ACQUIRE (M.lock) temp ← M RELEASE (M.lock) ACQUIRE (N.lock) N ← N + temp COMMIT_TRANSACTION () RELEASE (N.lock)

T₃: BEGIN_TRANSACTION () ACQUIRE (M.lock) M ← 1 COMMIT_TRANSACTION () RELEASE (M.lock)

T₄: BEGIN_TRANSACTION () ACQUIRE (M.lock) ACQUIRE (N.lock) M ← 1 N ← 1 COMMIT_TRANSACTION () RELEASE (M.lock) RELEASE (N.lock)

Q22.3 The initial values of M and N in the database are M=2 and N=3. Two of the above transactions are executed at about the same time. There are no crashes, and there is no other activity. For each of the following pairs of transactions, decide whether concurrent execution of that pair could result in an incorrect result. If the result is always correct, give an argument why. If an incorrect result could occur, give an example of such a result and describe a scenario that leads to that result.

A. T₂ and T₂:
B. T₂ and T₃:
C. T₂ and T₄:

Problem Set 23: "Log"-ical Calendaring $^*$

$^*$ Credit for developing this problem set goes to Hari Balakrishnan.

2004–3–7…15

(Chapters 3 and 4)

Ally Fant is designing a calendar server to store her appointments. A calendar client contacts the server using the following remote procedure calls (RPCs):

ADD (timeslot, descr): Adds the appointment description ( descr ) to the calendar at time slot timeslot .
SHOW (timeslot): Reads the appointment at time slot timeslot from the calendar and displays it to the user. (If there is no appointment, SHOW displays an empty slot.)

The RPC between client and server runs over a transport protocol that provides "at-most-once" semantics. The server runs on a separate computer and it stores appointments in an append-only log on disk. The server implements ADD in response to the corresponding client request by appending an appointment entry to the log. Each appointment entry has the following format:

structure appt_entry integer id // unique id of action that created this entry string timeslot // the timeslot for this appointment string descr // description of this appointment

Ally would like to make the ADD action atomic. She realizes that she can use ALL_OR_NOTHING_PUT (data, sector) and ALL_OR_NOTHING_GET (data, sector) as described in Section 3.3.1. These procedures guarantee that a single all-or-nothing sector is written either completely or not at all.

Each appointment entry is for one timeslot , which specifies the time interval of the appointment (e.g., 1:30 pm–3:00 pm on May 20, 2005). Each appointment entry is exactly as large as a single all-or-nothing sector (512 bytes). The first all-or-nothing sector on disk, numbered 0, is the master_sector , which stores the all-or-nothing sector number where the next log record will be written. The number stored in master_sector is called the end of the log, end_of_log , and is initialized to 1.

Ally designs the following procedure:

1 procedure ADD (timeslot; descr) 2 id ← NEW_ACTION_ID () // returns a unique identifier 3 appt ← MAKE_NEW_APPT (id; timeslot; descr) // make and fill in an appt entry 4 if ALL_OR_NOTHING_GET (end_of_log; master_sector) ≠ OK then return 5 if ALL_OR_NOTHING_PUT (appt; end_of_log) ≠ OK then return 6 end_of_log ← end_of_log + 1 7 if ALL_OR_NOTHING_PUT (end_of_log; master_sector) ≠ OK then return

The procedure NEW_ACTION_ID returns a unique action identifier. The procedure MAKE_NEW_APPT allocates an appt_entry structure and fills it in, padding it to 512 bytes.

Ally implements SHOW as follows:

Use ALL_OR_NOTHING_GET to read the master sector to determine the end of the log.
Scan the log backwards starting from the last written all-or-nothing sector (end_of_log – 1), using ALL_OR_NOTHING_GET on each sector, and stopping as soon as an entry for the timeslot is found.

To help understand if her implementation of the calendar system is correct or not, Ally defines the following properties that her calendar server should ensure:

P1: SHOW (timeslot) should display the appointment corresponding to the last committed ADD to that timeslot, even if system crashes occur during calls to ADD .
P2: The calendar server must store the appointments corresponding to all committed ADD actions for at least three years.
P3: If multiple ADD and SHOW actions run concurrently, their execution should be serializable and property P1 should hold.
P4: No ADD should be committed if it has a time slot that overlaps with an existing appointment.

Ally has learned a number of apparently relevant concepts: before-or-after atomicity, all-or-nothing atomicity, constraint, durability, and transaction.

Q23.1 Which of the apparently relevant concepts does ADD correctly implement?

Q23.2 For each of the properties P2, P3, and P4, identify the apparently relevant concept that best describes it.

Q23.3 What is the earliest point in the execution of the ADD procedure that ensures that a subsequent SHOW is guaranteed to observe the changes made by the ADD . (Assume that the SHOW does not fail.)

A. The successful completion of ALL_OR_NOTHING_PUT in line 5 of ADD .
B. The successful completion of line 6.
C. The successful completion of ALL_OR_NOTHING_PUT in line 7.
D. The instant that ADD returns to its caller.

Q23.4 Ally sometimes uses the calendar server concurrently from different client machines. Which of these statements is true of properties P3 and P4? (Assume that no failures occur, but that the server may be processing multiple RPCs concurrently.)

A. If exactly one ADD and several SHOW actions run concurrently on the server, then property P3 is satisfied even if those actions are for the same timeslot.
B. If more than one ADD and exactly one SHOW run concurrently on the server, then property P3 is satisfied as long as the actions are for different timeslots.
C. Suppose ADD (timeslot, descr) calls SHOW (timeslot) before line 7 and immediately returns to its caller if the timeslot already has an appointment. If multiple ADD and SHOW actions run concurrently on the server, then property P4 is satisfied whether or not property P3 holds.
D. Suppose ADD (timeslot, descr) calls SHOW (timeslot) before line 7 and immediately returns to its caller if the timeslot already has an appointment. If multiple ADD and SHOW actions run concurrently on the server, then property P4 is satisfied as long as property P3 holds.

Q23.5 Ally finds two disks A and B whose conditional failure probabilities follow the "bathtub curve", shown below. She also learns that the disk manufacturers sell units that have been "burned in" but otherwise are unused.Which disk should she buy new to have a higher likelihood of meeting property P2 for at least one year?

Graph of conditional failure rate h(t) vs time in years, for two disks A and B. At time = 0 h(t) is infinite for both disks. For disk A, h(t) has fallen to roughly 0.05 by time = 1 year and it rises dramatically after year 6. For disk B, h(t) has fallen to roughly 0.01 by time = 1 year and it rises dramatically after time = 4.5 years.

Figure $PS.23.1$: Graph of conditional failure probabilities over time in years for disks A and B.

Multi-user calendar.

Ally becomes president of Scholarly University and opens her server calendar to the entire University community to add and show entries. People start complaining that it takes a long time for them to SHOW Ally's appointments. Ally's new provost, Lem E. Fixit, tells her that a single log makes reading slow.

Lem convinces Ally to use the log as a recovery log, and use a volatile in-memory table, named table, to store the appointments to improve the performance of SHOW . The table is indexed by the timeslot. SHOW is now a simple table lookup, keyed by the timeslot. If the system crashes, the table is lost; when the system recovers, the recovery procedure reinstalls the table. Lem shows Ally how to modify the recovery log to include an "undo" entry in it, as well as a "redo" entry. All the log writes are done using ALL_OR_NOTHING_PUT .

Ally writes the following lines in her NEW_ADD pseudocode. (For now, the writes to the log are only shown in COMMIT .)

1 procedure NEW_ADD (timeslot, descr) 2 id ← NEW_ACTION_ID () 3 appt ← MAKE_NEW_APPT (id, timeslot, descr) 4 table[timeslot] ← appt 5 if OVERLAPPING (table, appt) then ABORT (id) 6 COMMIT (id)

7 procedure COMMIT (id) 8 if ALL_OR_NOTHING_GET (end_of_log, master_sector) ≠ OK then ABORT (id) 9 if ALL_OR_NOTHING_PUT (“COMMITTED”, id, end_of_log) ≠ OK then ABORT (id) 10 end_of_log ← end_of_log + 1 11 if ALL_OR_NOTHING_PUT (end_of_log, master_sector) ≠ OK then ABORT (id)

The procedure named OVERLAPPING checks table to see if appt overlaps with a previously committed appointment (property P4). ABORT uses the log to undo any changes to table made by NEW_ADD , releases any locks that NEW_ADD set, and then terminates the action.

Ally modifies SHOW to look up an appointment in table, instead of scanning the log.

Q23.6 Which of the following statements is true for NEW_ADD with respect to property P1? (Assume that there are no concurrent actions.)

A. If NEW_ADD writes the log entry corresponding to the table write just before line 4, then P1 holds.
B. If NEW_ADD writes the log entry corresponding to the table write just before line 6, then P1 holds.
C. Because table is in volatile memory, there is no need for ABORT to undo any changes made by NEW_ADD in order for P1 to hold.
D. If Ally had designed table to be in non-volatile storage, and NEW_ADD inserts the log entry just before line 4, then P1 holds.

Lem convinces Ally that using locks can be a good way to ensure property P3. Ally uses two locks, λ_t and λ_g. λ_t protects table[timeslot] and λ_g protects accesses to the log. She needs help to figure out where to place the lock ACQUIRE and RELEASE statements to ensure that property P3 holds when multiple concurrent NEW_ADD and SHOW actions run.

Q23.7 Which of the following placements of ACQUIRE and RELEASE statements in NEW_ADD correctly ensures property P3? Assume that SHOW implements correct locking.

A. ACQUIRE (λ_t) just before line 3,
  RELEASE (λ_t) just after line 6,
  ACQUIRE (λ_g) just before line 3,
    RELEASE (λ_g) just after line 6.

B. ACQUIRE (λ_t) just before line 4,
    RELEASE (λ_t) just after line 5,
    ACQUIRE (λ_g) just before line 6 but after RELEASE(λ_t) ,
    RELEASE (λ_g) just after line 6.

C. None of the above.

Disconnected calendar.

Ally Fant wants to use her calendar in disconnected operation, for example, from her PDA, cell phone, and laptop. Ally modifies the client software as follows. Just before a client disconnects, the client copies the log from the calendar server atomically, and then reinstalls table locally. When the user (i.e., Ally) adds an item, the client runs NEW_ADD on the client, updating the local copy of the log and table .

When the client can connect to the calendar server or any other client, it reconciles. When reconciling, one of the two machines is the primary. If a client connects to the calendar server, the server is the primary; if a client connects to another client, then one of them is the primary. The client that is not the primary calls RECONCILE , which runs locally on the client:

1 procedure RECONCILE (primary, client_log) 2 for each entry ∈ client_log do 3 if entry.state = COMMITTED then 4 invoke NEW_ADD (entry.timeslot, entry.descr) at primary 5 COPY (primary.log, client_log) // overwrite client_log 6 DELETE (table) 7 rebuild table from client_log // create new table

Assume that RECONCILE is atomic and that no crashes occur during reconciliation. Assume also that between any pair of nodes there is at most one active RECONCILE at any time.

Q23.8 Which of the following statements is true about the implementation that supports disconnected operation?

A. RECONCILE will resolve overlapping appointments in favor of appointments already present on the primary.
B. Some appointments added on a disconnected client may not appear in the output of SHOW after the reconciliation is completed.
C. The result of client C1 reconciling with client C2 (with C2 as the primary), and then reconciling C2 with the calendar server, is the same as reconciling C2 with client C1 (with C1 as the primary), and then reconciling C1 with the calendar server.
D. Suppose Ally stops making changes, and then reconciles all clients with the server once. After doing that, the logs on all machines will be the same.

Lem E. Fixit notices that the procedure RECONCILE is slow. To speed it up, Lem invents a new kind of record, called the RECONCILED record. Each time RECONCILE runs, it appends a RECONCILED record listing the client's unique identifier to the primary's log just before line 5.

Q23.9 Which of the following uses of the RECONCILED record speeds up RECONCILE correctly? (Assume that clients reconcile only with the calendar server.)

A. Modify line 2 to scan the client log backwards (from the end of the log), terminating the scan if a RECONCILED record with the client's identifier is found, and then scan forward until the end of the log calling NEW_ADD on the appointment entries in the log.
B. Modify line 2 to scan the client log forwards (from the beginning of the log) calling NEW_ADD on the appointment entries in the log, but terminating the scan if a RECONCILED record with the client's identifier is found.
C. Don't reinstall table from scratch at the end of reconciliation, but instead update it by adding the entries in the primary log (which the client just copied) that are between the previous RECONCILED record and the RECONCILED record from the current reconciliation. If an entry in the log overlaps with an entry in the table, then replace the table entry with the one in the log.
D. Assign Lem E. Fixit a different job. None of these optimizations maintains correctness.

Problem Set 24: Ben's Calendar Exercise$^*$

$^*$ Credit for developing this problem set goes to Robert T. Morris.

2001–3–14…19

(Chapter 4)

Ben Bitdiddle has just been promoted to Engineering Manager. He quickly notices two facts about his new job. First, keeping an accurate appointment calendar is crucial. Second, he no longer has any programming responsibilities. He decides to address both problems at once by building his own highly available replicated calendar system.

Ben runs a client user interface on his workstation. The client talks over the network to one of three replicated servers. Ben places the three servers, called S1, S2, and S3, in three different cities to try to ensure independent failure. Ben only runs one client at a time.

Each server keeps a simple database of Ben's appointments. The database holds a string for every hour of every day, describing the appointment for that hour. The string for each hour starts out empty. A server can perform just two operations on its own database:

DBREAD (day, hour) returns the appointments for a particular day and hour. The argument day indicates the desired day, where 0 means January 1st, 2000. The argument hour is an integer between 0 and 23, inclusive.
DBWRITE (day, hour, string) changes the string for the hour hour . Writing an empty string to an hour effectively deletes any existing appointment for that hour.

Each server allows Ben's client to invoke these operations by RPC. The RPC system uses a powerful checksum that detects all errors and discards any corrupted message. If the RPC client implementation doesn't receive a response from the server within a few seconds, it times out, sets the variable rpc_OK to false, and returns NIL . If the client does receive a reply from the server, the RPC implementation sets rpc_OK to true and returns the result from the server, if any. The RPC system does not resend requests. Thus, for example, if the network discards or corrupts the request or response message, the RPC call returns with rpc_OK set to false.

Ben's client user interface can display the appointments for a day and also change an appointment. To support these operations, Ben writes client software based on this pseudocode (the notation S[i].F indicates an RPC call to procedure F on server i ):

procedure CLIENTREAD (day, hour) string s for i from 1 to 4 do // try each server one by one s ← S[i].DBREAD (day, hour) if rpc_OK then return s // return with the first reply return “Error”

procedure CLIENTWRITE (day, hour, what) for i from 1 to 4 do // write to all three servers boolean done ← FALSE while done = FALSE do S[i].DBWRITE (day, hour, what) if rpc_OK then done ← TRUE

Q24.1 Suppose the network connecting Ben's client to servers S1 and S2 is fast and reliable, but the network between the client and S3 often stops working for a few minutes at a time. How will Ben's system behave in this situation?

A. CLIENTWRITE will often take a few minutes or more to complete.
B. CLIENTREAD will often take a few minutes or more to complete.
C. CLIENTWRITE will often fail to update all of the servers.
D. CLIENTREAD will often fail, returning "Error".

Ben tests his system by reading and writing the entry for January 1st, 2000, 10 a.m.; he calls:

CLIENTWRITE (0, 10, "Staff Meeting") CLIENTWRITE (0, 10, "Breakfast") CLIENTREAD (0, 10)

Q24.2 Suppose there are no faults. What string will the CLIENTREAD call return?

Just to be sure, Ben tries a different test, involving moving a meeting from 10 a.m. to 11 a.m., and scheduling breakfast:

CLIENTWRITE (0, 10, "Free at 10") CLIENTWRITE (0, 11, "Free at 11") CLIENTWRITE (0, 10, "Talk to Frans at 10") CLIENTWRITE (0, 11, "Talk to Frans at 11") CLIENTWRITE (0, 10, "Breakfast at 10")

Ben starts the test, but trips over the power cord of his client computer while the test is running, causing the client to reboot. The client forgets that it was executing the test after the reboot; it doesn't restart or continue the test. After the reboot Ben calls CLIENTREAD (0, 10) and CLIENTREAD (0, 11) . Other than the mentioned client reboot, the only faults that might occur during the test are lost messages (and thus RPC failures).

Q24.3 Which of the following results might Ben see?

A. Breakfast at 10, Talk to Frans at 11
B. Talk to Frans at 10, Talk to Frans at 11
C. Breakfast at 10, Free at 11
D. Free at 10, Talk to Frans at 11

Q24.4 Ben is getting a little paranoid, so he calls ClientREAD (0, 10) twice, to see how consistent his database is. Which of the following results might Ben see?

A. Breakfast at 10, Breakfast at 10
B. Talk to Frans at 10, Talk to Frans at 10
C. Free at 10, Breakfast at 10
D. Talk to Frans at 10, Free at 10

Ben feels this behavior is acceptable. Before he starts to use the system, however, his younger brother Mark points out that Ben's system won't be able to complete updates if one of the servers is down. Mark says that if a server is down, a DBWRITE RPC to that server will time out, so CLIENTWRITE will have higher availability if it ignores RPC timer expirations. Mark suggests the following changed CLIENTWRITE :

procedure CLIENTWRITE (day, hour, what) for i from 1 to 4 do S[i].DBWRITE (day, hour, what) // Ignore RPC failure

Ben adopts this change, and starts using the system to keep his appointments. However, his co-workers start to complain that he is missing meetings. Suspicious of Mark's change, Ben tests the system by manually clearing all database entries on all servers to empty strings, then executing the following code on his client:

CLIENTWRITE (0, 10, "X") v1 ← CLIENTREAD (0, 10) CLIENTWRITE (0, 10, "Y") v2 ← CLIENTREAD (0, 10) CLIENTWRITE (0, 10, "Z") v3 ← CLIENTREAD (0, 10)

Assume that the only possible faults are losses of RPC messages, and that RPC messages are delivered instantly.

Q24.5 With Mark's change, which of the following sequences of v1 , v2 , and v3 are possible?

A. X, Y, Z
B. X, Z, Y
C. X, X, Z
D. X, Y, X

Q24.6 In Ben's original system, what sequences of v1 , v2 , and v3 would have been possible?

A. X, Y, Z
B. X, Z, Y
C. X, X, Z
D. X, Y, X

Problem Set 25: Alice's Replicas

2003–3–6…12

(Chapter 4)

After reading Chapter 4 and the end-to-end argument, Alice explores designing an application for reconciling UNIX file systems. Her program, RECONCILE , takes as input the names of two directory trees and attempts to reconcile the differences between the two trees. The typical scenario for RECONCILE is that one of the directory trees is on a file service. The other one is a replica of that same directory tree, located on Alice's laptop.

When Alice is disconnected from the service, she modifies files on her laptop while her friends may modify files on the service When Alice reconnects to the service, she runs RECONCILE to reconcile the differences between the directory tree on her laptop and the service so that they are identical again. For example, if a file has changed on her laptop, but not on the service, RECONCILE copies the file from the laptop to the service. If the file has changed on both the laptop and server, then RECONCILE requires guidance to resolve conflicting changes.

The RECONCILE program maintains on each host a database named fsinfo , which is stored outside the directory tree being reconciled. This database is indexed by path name, and it stores:

character pathname[1024] // path name of this file integer160 hash // cryptographic hash of the content of the file

On disk a UNIX file consists of metadata (the inode) and content (the data blocks). The cryptographic hash is computed using only the file's content. Path names are less than 1024 bytes. For this problem, ignore the details of reconciling directories, and assume that Alice has permission to read and write everything in both directory trees.

The RECONCILE program operates in 4 phases:

Phase 1: Compute the set of changes on the laptop since the last reconciliation and the set of changes on the server since the last reconciliation.
Phase 2: The laptop retrieves the set of changes from the service. Using the two change sets, the laptop computes a set of actions that must be taken to reconcile the two directory trees. In this phase, reconcile might decide that some files cannot be reconciled because of conflicting changes.
Phase 3: The laptop carries out the actions determined in phase 2. The laptop updates the files and directories in its local directory tree, and retrieves files, sends files, and sends instructions to the server to update its directory tree.
Phase 4: Both the laptop and the service update the fsinfo they used to reflect the new content of files that were successfully reconciled on this run.

Assume that RECONCILE runs to completion before starting again. Furthermore, assume that when reconcile runs no concurrent threads are allowed to modify the file system. Also assume that initially the fsinfo databases are identical in content and computed correctly, and that after reconciliation they also end up in an identical state.

The first phase of RECONCILE runs the procedure COMPUTEMODIFICATIONS on both the laptop and the service. On each machine COMPUTEMODIFICATIONS produces two sets: a set of files that changed on that machine and a set of files that were deleted on that machine.

set changeset, deleteset;

procedure COMPUTEMODIFICATIONS (path, fsinfo) changeset ← NULL deleteset ← NULL COMPUTECHANGESET (path, fsinfo) COMPUTEDELETESET (fsinfo)

procedure COMPUTECHANGESET (path, fsinfo) info ← LOOKUP (path, fsinfo) if info = NULL then ADD (path, changeset) else if ISDIRECTORY (path) then for each file in path do COMPUTECHANGESET (path/file, fsinfo) else if CSHA (CONTENT (path) ≠ info.hash then ADD (path, changeset)

procedure COMPUTEDELETESET (fsinfo) for each entry in fsinfo do if not (EXIST (entry.pathname)) then ADD (pathname, deleteset)

The COMPUTEMODIFICATIONS procedure takes as arguments the path name of the directory tree to be reconciled and the fsinfo database. The procedure COMPUTECHANGESET walks the directory tree and checks every file to see if it was created or changed since the last time RECONCILE ran. CSHA is a cryptographic hash function, which has the property that it is computationally infeasible to find two different inputs i and j such that

CSHA (i) = CSHA (j)

The COMPUTEDELETESET procedure checks for each entry in the database whether the corresponding file still exists; if not, it adds it to the set of files that have been deleted since the last run of RECONCILE .

Q25.1 What files will RECONCILE add to changeset or deleteset ?

A. Files whose content has decayed.
B. Files whose content has been modified.
C. Files that have been created.
D. Files whose inodes have been modified.
E. Files that have been deleted.
F. Files that have been deleted but recreated with identical content.
G. Files that have been renamed.

The second phase of reconcile compares the two changesets and the two deletesets to compute a set of actions for reconciling the two directory trees. To avoid confusion we call changeset on the laptop changeLeft , and changeset on the service changeRight . Similarly, deleteset on the laptop is deleteLeft and deleteset on the service is deleteRight . The second phase consists of running the procedure COMPUTEACTIONS with the 4 sets as input. COMPUTEACTIONS produces 5 sets:

additionsLeft : files that must be copied from server to the laptop
additionsRight : files that must be copied from laptop to the service
removeLeft : file that must be removed from laptop
removeRight : file that must be removed from service
conflicts : files that have conflicting changes

In the following code fragment, the notation A - B indicates all elements of the set A after removing the elements that also occur in the set B . With this notation, the 5 sets are computed as follows:

conflicts ← NULL;

procedure COMPUTEACTIONS (changeLeft, changeRight, deleteLeft, deleteRight) for each file ∈ changeLeft do if file ∈ (changeRight ∪ deleteRight) then ADD (file, conflicts) for each file ∈ (deleteLeft) do if file ∈ (changeRight) then ADD (file, conflicts) additionsRight ← changeLeft - conflicts additionsLeft ← changeRight - conflicts removeRight ← deleteLeft - conflicts removeLeft ← deleteRight - conflicts

Q25.2 What files end up in the set additionsRight ?

A. Files created on the laptop that don't exist on the service.
B. Files that have been removed on the server but not changed on the laptop.
C. Files that have been removed on the laptop but not on the service.
D. Files that have been modified on the laptop but not on the service.
E. Files that have been modified on the laptop and on the service.

Q25.3 What files end up in the set conflicts?

A. Files that have been modified on the laptop and on the service.
B. Files that have been removed on the laptop but that exist unmodified on the service.
C. Files that have been removed on the laptop and on the service.
D. Files that have been modified on the service but not on the laptop.
E. Files that have been created on the laptop and on the service but with different content.
F. Files that have been created on the laptop and on the service with the same content.

Phase 3 of the reconcile executes the actions: deleting files, transferring files, and resolving conflicts. All conflicts are resolved by asking the user.

We focus on transferring files from laptop to service. Alice wants to ensure that transfers of files are atomic. Assume that all file system calls execute atomically. The RECONCILE program transfers files from additionsRight by invoking the remote procedure RECEIVE on the service:

procedure RECEIVE (data, size, path) tname ← UNIQUENAME () fd ← CREATE_FILE (tname) if fd ≥ 0 then n ← WRITE (fd, data, size) CLOSE (fd) if n = size then RENAME (tname, path) else DELETE (tname) return (n = size) // boolean result tells success or failure else return (FALSE)

The RECEIVE procedure takes as arguments the new content of the file ( data and size ) and the name ( path ) of the file to be updated or created. As its first step, RECEIVE creates a temporary file with a unique name ( tname ) and writes the data into in it. After the write is successful, RECEIVE renames the temporary file to its real name ( path ), which incidentally removes any existing old version of path ; otherwise, it cleans up and deletes the temporary file. Assume that RENAME always executes successfully.

Q25.4 Where is the commit point in the procedure RECEIVE ?

A. right after RENAME completes
B. right after CLOSE completes
C. right after CREATE_FILE completes
D. right after DELETE completes
E. right after WRITE completes
F. none of the above

After the server or laptop fails, it calls a recovery procedure to back out or roll forward a RECEIVE operation that was in progress when the host failed.

Q25.5 What must this recovery procedure do?

A. Remove any temporary files left by receive.
B. Nothing.
C. Send a message to the sender to restart the file transfer.
D. Rename any temporary files left by receive to their corresponding path name.

Q25.6 Which advantages does this version of RECONCILE have over the reconciliation procedure described in Chapter 4?

A. This RECONCILE repairs files that decay.
B. This RECONCILE doesn't require changes to the underlying file system implementation.
C. This version of RECONCILE doesn't require a log on the laptop.
D. This RECONCILE propagates changes from the laptop to the service, and vice versa.
E. This RECONCILE will run much faster on big files.

Alice wonders if her code extends to reconciling more than two file systems. Consider 3 hosts (A, B, and C) that all have an identical copy of a file f , and the following sequence of events:

at noon B modifies file f
at 1 pm B reconciles with A
at 2 pm C modifies f
at 3 pm B reconciles with C
at 4 pm A modifies f
at 5 pm B reconciles with A

Assume that B has two distinct fsinfo databases, one used for reconciling with A and one for reconciling with C.

Q25.7 Which of the following statements are correct, given this sequence of events and Alice's implementation of RECONCILE ?

A. If the conflict at 3 pm is reconciled in favor of B's copy, then RECONCILE will not report a conflict at 5 pm.
B. If the conflict at 3 pm is reconciled in favor of C's copy, then RECONCILE will report a conflict at 5 pm.
C. If the conflict at 3 pm is resolved by a modification to f that merges B's and C's versions, then RECONCILE will report a conflict at 5 pm.
D. If the conflict at 3 pm is resolved by removing f from B and C, then RECONCILE will not report a conflict at 5 pm.

Problem Set 26: JailNet$^*$

$^*$ Credit for developing this problem set goes to Stephen A. Ward.

1998–2–7…14

(Some Chapter 1, but mostly Chapter 5)

The Computer Crimes Correction Facility, a federal prison for perpetrators of information-related crimes, has observed curious behavior among their inmates. Prisoners have discovered that they can broadcast arbitrary binary strings to each other by banging cell bars with either the tops or bottoms of their tin cups, making distinct sounds for "0" and "1". Since such sounds made in any cell can typically be heard in every other cell, they have devised an Ethernet-like scheme for communicating varying-length packets among themselves.

The basic communication scheme was devised by Annette Laire, a CCCF lifer convicted of illegal exportation of restricted information when the GIF she emailed to her cousin in El Salvador was found to have some bits in common with a competent cryptographic algorithm.

Annette defined the following basic communication primitive:

procedure SEND (message, from, to) BANG (ALL_ONES) // Start with a byte of eight 1’s BANG (to) // destination inmate number BANG (from) // source inmate number BANG (message) // the message data BANG (CHECKSUM ({to, from, message})) // Checksum of whole message

where the operation BANG (data) is executed by banging ones tin cup to signal the sequence of bits corresponding to the specified null-terminated character string, including the zero byte at its end. The special string ALL_ONES sent initially has a single byte of (eight) 1 bits (followed by the terminating null byte). The high-order bit of each 8-bit character (in to , from , message , and the result of CHECKSUM ) is zero.

Annette specified that the to and from strings be the unique numbers printed on every inmate's uniform, since all of the nerd-inmates quickly learn the numbers of each of their colleagues. Each inmate listens more or less continuously for packets addressed to them, ignoring all packets whose to field don't match their number or whose checksums are invalid.

Q26.1 What function(s) are served by sending the initial byte of all 1's?

A. Bit framing.
B. Byte (character) framing.
C. Packet framing.
D. Packet Reassembly.
E. None of the above.

Typical higher-level protocols involve sequences of packets exchanged between inmates, for example:

Annette ⇒ Ty: SEND (“I thought the lobster bisque was good tonight”, ANNETTE, TY);

Ty ⇒ Annette: SEND (“Yes, but the filet was a bit underdone”, TY, ANNETTE);

where the symbols ANNETTE and TY are bound to character strings containing the uniform numbers of Annette and Ty, respectively.

Of course, prison guards quickly catch on to the communication scheme, listen in on the conversations, and sometimes even inject messages of their own, typically with false source addresses:

Guard: SEND (“Yeah? Then it’s dog food for you tomorrow!”, JIMMIETHEGEEK, ANNETTE);

Such experiences motivate Ty Debole, the inmate in charge of cleaning, to add security measures to the JailNet protocols. Ty reads up on public-key cryptography and decides to use it as the basis for JailNet security. He chooses a public-key algorithm and asks each inmate to generate a public/private key pair and tell him the public key.

KEY represents the inmate's public key. Since Ty runs the CCCF laundry, he prints the numbers on inmates' uniforms. He replaces each inmate's assigned number with a representation of KEY;
$KEY is the inmate's private key. This key is known only to the inmate whose uniform bears KEY .

Ty assures each inmate that so long as they don't reveal their private $KEY , nobody else—inmates or guards—will be able to determine it. Inmates continue to address each other by the numbers on their uniforms, which now specify their public Keys.

Q26.2 What is an assumption on which Ty bases the security of the secret $KEY ?

A. $KEY is theoretically impossible to compute from KEY .
B. $KEY takes an intractably long time to compute from KEY .
C. $KEY takes at least as long to compute from KEY as the generation of the KEY , $KEY pair.
D. There is a reasonably efficient way to compute $KEY , but it's not generally known by guards and inmates.

Ty then teaches inmates the 4 security primitives for messages of up to 1,500 bytes:

ENCRYPT (plaintext, KEY) // returns a message string
DECRYPT (ciphertext, $KEY) // returns a message string
SIGN (message, $KEY) // returns an authentication tag
VERIFY (message, KEY, signature) // returns ACCEPT or REJECT

These primitives have the properties described in Chapter 5.

Ty proposes improving the security of communications by replacing calls to SEND with calls like:

SEND (TYCODE (message, from, to), from, to);

where TYCODE is defined as

procedure TYCODE (message, from, to) return ENCRYPT (message, to)

Ty and Annette are smugly confident that although the guards might hear their conversation, they won't be able to understand it since the encrypted message appears as gibberish until properly decoded. The first use of TYCODE involves the following message, received by Annette:

SEND (TYCODE (“Meet by the wall at ten for the escape”, TY, ANNETTE), TY, ANNETTE)

Q26.3 What computation did Annette perform to decode Ty's message? Assume rmessage is the message as received, message is to be the decoded plaintext, and that $Annette and $Ty contain the secret keys of Annette and Ty, respectively.

A. message ← VERIFY (rmessage, Ty, $Annette);
B. message ← ENCRYPT (rmessage, $Ty);
C. message ← ENCRYPT (rmessage, Ty);
D. message ← DECRYPT (rmessage, $Annette);
E. message ← SIGN (rmessage, $Ty);
F. message ← DECRYPT (rmessage, Annette);

After receiving the message, Annette sneaks out at ten to meet Ty, whom she expects will help her climb over the prison wall. Unfortunately Ty never shows up, and Annette gets caught by a giggling guard and is punished severely (early bed, no dessert). When she talks to Ty the next day, she learns that he never sent the message. She concludes that it must have been sent by a guard, but is puzzled since the cryptography is secure.

Q26.4 What is the most likely explanation?

A. Annette's secret key was compromised during a search of her cell.
B. Some other message Ty sent was garbled in transmission, and accidentally came out "Meet me by the wall at ten for the escape".
C. Annette’s secret key was broken by a dictionary attack.
D. Ty's secret key was broken by a dictionary attack.
E. Annette was victimized by a replay attack.

Annette's friend Cert Defy, on hearing this story, comes up with a new cryptographic procedure:

procedure CERT (message, A) signature ← SIGN (message, A) return {message, signature}

Unfortunately, Cert is placed in solitary confinement before fully explaining how to use this procedure, though he did state that sending a message with

SEND (CERT (message, A), from, to)

can assure the receiver of the integrity of the message body and the authenticity of the sender's identity. So the inmates need some help from you.

Q26.5 When Ty sends a message to Annette, what value should he supply for A ?

A. ENCRYPT (Annette, $Ty)
B.Ty
C. $Ty
D. Annette
E. $Annette

After Ty determinines the answer to Q26.5, Annette receives a packet purportedly from Ty. She splits the received packet into message and signature , and VERIFY (message, TY, signature) returns ACCEPT .

Q26.6 Which of the following can Annette conclude about message ?

A. message was initially sent by Ty.
B. The packet was sent by Ty.
C. message was initially sent to Annette.
D. Only Annette and Ty know the contents of message .
E. If Ty sent message to Annette and Annette only, then only they know its contents.
F. message was not corrupted in transmission.

Annette, intrigued by Cert's contribution, decides to combine SEND , TYCODE , and CERT to achieve both authentication and confidentiality. She proposes to use NEWSEND , combining both features:

procedure NEWSEND (message, A, from, to) SEND (TYCODE (CERT (message, A), from, to), from, to)

Annette engages in the following conversation:

Ty ⇒ Annette: NEWSEND (“Let’s escape tonight at ten”, TY, ANNETTE);

Ty ⇒ Annette: NEWSEND (“Not tonight, Survivor is on”, ANNETTE, TY);

The following night, Annette gets the message

Ty ⇒ Annette: NEWSEND (“Let’s escape tonight at ten”, TY, ANNETTE);

Once again Annette goes to meet Ty at ten, but Ty never shows up. Eventually Annette gets bored and returns. Ty subsequently disclaims having sent the message. Again, Annette is puzzled by the failure of her allegedly secure system. She suspects that a guard has figured out how to break the system.

Q26.7 Explain why this happened, yet no guard showed up at the wall to punish Annette for plotting to escape. Suggest a change that Ty could have made that would have eliminated the problem.

Pete O’Fender, who has been in and out of CCCF at regular intervals, wants to extend the security protocols to deal with JailNet key distribution. Whenever he’s jailed, Pete is placed directly into solitary confinement where he has no contact with inmates (except via bar banging), and where the TV gets only 3 channels. The problem is complicated by the facts that (a) Everyone (including Pete) forgets Pete's uniform number as soon as he leaves, so when he returns he can't just re-use the old key; (b) Pete may not even remember the key for Ty or other trusted long-term inmates; (c) Pete is issued an unnumbered uniform while in solitary, and (d) guards often pose as newly-jailed solitary occupants to learn inmate secrets. Pete asks you to devise JailNet key distribution protocols to address these problems.

Q26.8 Which of the following are true of the best protocol you can devise, given the assumptions stated about ENCRYPT , DECRYPT , SIGN , and VERIFY ?

A. Assuming Pete is thrust into Solitary remembering no keys, he can devise a new Key/$Key pair and broadcast Key . Using this Key , Ty can be assured that messages he sends to Pete are confidential.
B. Assuming Pete is thrust into Solitary remembering no keys, he can't convince inmates that they aren't communicating with a guard.
C. If Pete remembers Ty's uniform number and trusts Ty, an authenticated broadcast message from Ty could be used to remind Pete of other inmates' uniform numbers without danger of deluding Pete.
D. Even if Pete remembers a trusted inmate's uniform number, any communication from Pete can be understood by guards.
E. Even if Pete remembers a trusted inmate's uniform number, any communication to Pete might have been forged by guards.

Problem Set 27: PigeonExpress!.com II

1999–2–16,17

(Chapter 5)

To drive up the stock value of PigeonExpress!.com at the planned Initial Public Offering (IPO), Ben needs to make the pigeon net secure. To focus on just security issues, assume for this problem that pigeons never get lost.

First, Ben goes for achieving confidentiality. Ben generates 20 CDs ( KCD[0] through KCD[19] ) filled with random numbers, makes two copies of each CD, and mails the copies through a secure channel to the sender and receiver. He plans to use the CDs as a onetime pad.

Ben slightly modifies the original BEEP code (which appeared just before question Q2.1) to use the key CDs. The sender's computer runs these two procedures:

shared next_sequence initially 0 // a global sequence number, starting at 0. shared nextKCD initially 0 // index in the array of key CDs.

procedure SECURE_BEEP (destination, n, CD[]) // send n CDs to destination header h // h is an instance of header. nextCD ← 0 h.source ← MY_GPS // set source to my GPS coordinates h.destination ← destination // set destination h.type ← REQUEST // this is a request message while nextCD < n do // send the CDs h.sequence_no ← next_sequence // set seq number for this CD send pigeon with {h, (CD[nextCD] ⊕ KCD[nextKCD])} // send encrypted wait 2,000 seconds

procedure SECURE_PROCESS_ACK (h) // process acknowledgment if h.sequence_no = sequence then // ack for current outstanding CD? next_sequence ← next_sequence + 1 nextCD ← nextCD + 1 // allow next CD to be sent nextKCD ← (nextKCD + 1) modulo 20 // increment with wrap-around

Ben also modifies the procedures running on the receiver's computer to match:

integer nextkcd initially 0 // index in array of KCDs.

procedure SECURE_PROCESS_REQUEST (h, CD) PROCESS (CD ⊕ KCD[nextKCD]) // decrypt and process the data on the CD nextKCD ← (nextKCD + 1) modulo 20 // increment with wrap-around h.destination ← h.source // send to where the pigeon came from h.source ← MY_GPS h.sequence_no ← h.sequence_no // unchanged h.type ← ACKNOWLEDGMENT send pigeon with h // send an acknowledgment back

Q27.1 Do SECURE_BEEP , SECURE_PROCESS_ACK , and SECURE_PROCESS_REQUEST provide confidentiality of the data on the CDs?

A. No, since acknowledgments are not signed;
B. No, since the KCDs are reused, SECURE_BEEP is vulnerable to a known-plaintext attack;
C. Yes, since one-time pads are unbreakable;
D. No, since one can invert XOR .

To make the system more practical, Ben decides to switch to a short key and to exchange the key over the pigeon net itself instead of using an outside secure channel. Every principal has a key pair for a public-key system. He designs the following key-distribution protocol:

Alice ⇒ Bob: “I propose we use key k” (signed with Alice’s private key)

Bob ⇒ Alice: “OK, key k is fine” (signed with Bob’s private key)

The two key-distribution messages are written on a CD and sent with BEEP (not SECURE_BEEP ). From key k the sender and receiver generate a bit string using a well-known pseudorandom number generator, and employ the bit string in SECURE_BEEP and SECURE_PROCESS_REQUEST to encrypt and decrypt CDs.

Q27.2 Which statements are true of the above protocol?

A. It is insecure because key k travels in the clear, and therefore an intruder can find out key k and listen in on future instances of SECURE_BEEP .
B. It is secure because only Bob can verify the message from Alice.
C. It is insecure because Alice's public key is widely known.
D. It is secure, since the messages are signed and key k is only used as a seed to a pseudorandom number generator.

Problem 28: WebTrust.com

2001–2–6…17

(Chapter 5)

A group of accomplished 16-year-olds wants to go into business as a technology provider. Reading many war stories about security has convinced the kid wizards that there should be a market for a secure client authentication product for Web services. The kids incorporate as WebTrust.com, and study up on how the Web works. They discover that HTTP 1.0 is a simple protocol whose essence consists of two remote procedure calls:

GET (document) // returns a document POST (document, form) // sends a form and returns a document

The GET procedure gets the document identified by the Uniform Resource Locator (URL) document from a Web service. The POST procedure sends back to the service the entries that the user filled out on a form that was in a previously retrieved document. The POST procedure also gets a document. The browser invokes the POST procedure when the user hits the submit button on the form.

These remote procedure calls are sent over a reliable transport protocol, TCP. A Web browser opens a TCP connection, calls a procedure ( GET or POST ), and waits for a result from the service. The Web service waits for a TCP connection request, accepts the connection, and waits for a GET or POST call. Once a call arrives, the service executes it, sends the result over the connection, and closes the connection. The browser displays the response and closes the connection on its side. Thus, a new connection must be set up for each request.

Simple URLs are of the form: http://www.WebTrust.com/index.html

Q28.1 "www.WebTrust.com" in the above URL is

A. a DNS name
B. a protocol name
C. a path name for a file
D. an Internet address

The objective of WebTrust.com's product is to authenticate users of online services. The intended use is for a user to login once per session and to allow only logged-in users access to the rest of the site. The product consists of a collection of Web pages and some server software. The company employs its own product to authenticate customers of the company's Web site.

To allow Internet users to create an account, WebTrust.com has a Web form in which a user types in a user name and two copies of a proposed password. When the user types the password, the browser doesn't echo it, but instead displays a "•" for each typed character. When the user hits the submit button, the user’s browser calls the POST procedure to send the form to the server.

When the server receives a CREATE_ACCOUNT request, it makes sure that the two copies of the password match and makes sure that the proposed user name hasn't already been taken by someone else. If these conditions are true, then it creates an entry in its local password file. If either of the conditions is false, the server returns an error.

The form to create an account is stored in the document "create.html" on WebTrust's Web site. Another document on the server contains:

<a href="create.html">Create an account<\a>

Q28.2 What is the source of the context reference that identifies the context in which the name "create.html" will be resolved?

A. The browser derives a default context reference from the URL of the document that contains the relative URL.
B. It is configured in the Web browser when the browser is installed.
C. The server derives it from information it remembers about previous documents it sent to this client.
D. The user types it into the browser.

Q28.3 Why does the form for creating an account ask a user to type in the password twice?

A. To allow a password not to be echoed on the screen while enabling users to catch typos.
B. To detect transmission errors between the keyboard and the browser.
C. To reduce the probability that a packet with a password has to be retransmitted if the network deletes the packet.
D. To make it harder for users to create fake accounts.

Q28.4 In this system, to what attacks is creating an account vulnerable? (Assume an active attacker.)

A. An attacker can learn the password for a user by eavesdropping
B. An attacker can modify the password
C. An attacker can overwhelm the service by creating many accounts
D. An attacker can run a service that pretends to be "www.WebTrust.com"

To login, the user visits the Web page " login.html ", which asks the user for a user name and password. When the user hits the submit button, the browser invokes the POST procedure, which sends the user name and password to the service. The service checks the stored password against the password in the login request. If they match, the user is allowed to access the service; otherwise, the service returns an error.

Q28.5 To what attacks is the login procedure vulnerable? (Assume an active attacker.)

A. An attacker can login by replaying a recorded POST from a legitimate login
B. An attacker can login as any user by replaying a single recorded POST for login
C. An attacker can impersonate WebTrust.com to any registered user
D. An attacker can impersonate WebTrust.com to an unregistered user

To authenticate subsequent Web requests from a user after logging in, WebTrust.com exploits a Web mechanism called cookies. A service can install some state (called a cookie) in the Web browser. The service installs this state by including in a response a SET_COOKIE directive containing data to be stored in the cookie. WebTrust.com's use of cookies is summarized in the figure below.

The login procedure consists of the browser sending a username and password to the Web server, and the server sending a cookie to the browser. Subsequent requests consists of the browser sending a POST or GET for a document, as well as a cookie to the server, and the server sending the appropriate document to the server.

Figure $PS.28.1$: How WebTrust.com makes use of cookies.

The document containing the response to a login request comes with the directive:

POST (webtrustcookie)

The browser stores the cookie in memory. (In practice, there may be many cookies, so they are named, but for this problem, assume that there is only one and no name is needed.) On subsequent calls (i.e., GET or POST ) to the service that installed the cookie, the browser sends the installed cookie along with the other arguments to GET or POST . Thus, once WebTrust.com has set a cookie in a browser, it will see that cookie on every subsequent request from that browser.

The service requires that the browser send the cookie along with all instances of GET , and also all instances of POST except those posting a CREATE or LOGIN form. If the cookie is missing (for example, the browser has lost the cookie because the client computer crashed, or an attacker is leaving the cookie out on purpose), the service will return an error to the browser and ask the user to log in again.

An important issue is to determine suitable contents for webtrustcookie . WebTrust.com offers a number of alternatives.

The first option is to compute the cookie as follows:

cookie ← {expiration_time}_key

using a MAC with a shared-secret key . The key is known only to the service, which remembers it for just 24 hours. All cookies in that period use the same key. All cookies expire at 5 a.m., at which time the service changes to a new key .

When the server receives the cookie, it checks it for authenticity and expiration using:

procedure CHECK (cookie) if VERIFY (cookie, key) = ACCEPT then if cookie.expiration_time ≤ CURRENT_TIME () then return ACCEPT return REJECT

The procedure VERIFY recomputes and checks the MAC. If the MAC is valid, then the service checks whether cookie is still fresh (i.e., if the expiration time is later than the current time). If it is, then CHECK returns ACCEPT ; the server can now execute the request. In all other cases, CHECK returns REJECT and the server returns an error to the browser.

Q28.6 What is the role of the MAC in this protocol?

A. To help detect transmission errors
B. To privately communicate key from the server to the browser
C. To privately communicate expiration-time from the server to the browser.
D. To help detect a forged cookie.

Q28.7 Which of these attacks does this protocol prevent?

A. Replayed cookies
B. Forged expiration times
C. Forged cookies
D. Dictionary attacks on passwords

Another option supported by webtrust.com is to compute cookie as follows:

cookie ← {expiration_time, username}_key

The server uses for username the name of the user in the login request. The usage of this cookie is similar to before and the checking procedure is unchanged.

Q28.8 If the service receives a cookie with "Alice" as username and CHECK returns ACCEPT , what does the service know? (Assume active attacks.)

A. No one modified the cookie
B. The server accepted a login from "Alice" recently
C. The cookie was generated recently
D. The browser of the user "Alice" sent this cookie recently

Q28.9 Assume temporarily that all of Alice's Web requests are sent over a single TCP connection that is encrypted and authenticated, and that the setup all has been done appropriately (i.e., only the browser and server know the encryption and authentication keys). After Alice has logged in over this connection, the server has received a cookie with "Alice" as the username over this connection, and has verified it successfully (i.e., VERIFY returns ACCEPT ), what does the server know? (Assume active attacks.)

A. No one but the server and the browser of the user "Alice" knows the cookie
B. The server accepted a login from "Alice" recently
C. The cookie was generated recently
D. The browser of the user "Alice" sent this cookie recently

Q28.10 Is there any additional security risk with storing cookies durably (i.e., the browser stores them in a file on the local operating system) instead of in the run-time memory of the browser? (Assume the operating system is a multi-user operating system such as Linux or Windows, including a virtual memory system.)

A. Yes, because the file with cookies might be accessible to other users.
B. Yes, because the next user to login to the client machine might have access to the file with cookies.
C. Yes, because it expands the trusted computing base to include the local operating system.
D. Yes, because it expands the trusted computing base to include the hard disk.

Q28.11 For what applications is WebTrust's product (without the encrypting and authenticating TCP connection) appropriate (i.e., usable without grave risk)?

A. For protecting access to bank accounts of an electronic bank
B. For restricting access to electronic news articles to clients that have a subscription service
C. For protecting access to student data on a university's online student services
D. For electronic shopping, say, at amazon.com
E. None of the above

Mark Bitdiddle—Ben's 16-year kid brother—proposes to change the protocol slightly. Instead of computing cookie as:

cookie ← {expiration_time, username}_key

Mark suggests that the code be simplified to:

cookie ← {{expiration_time}_key, username}

He also suggests the corresponding change for the procedure VERIFY . The protocol, as originally, runs over an ordinary unencrypted and unauthenticated TCP connection.

Q28.12 Describe one attack that this change opens up and illustrate the attack by describing a scenario (e.g., "Lucifer can now … by …").

Problem Set 29: ByteStream Encryption

1997–2–3a…c

(Chapter 5)

Observing recent interest in security in the popular press, ByteStream Inc. decides to offer products that have the function of obtaining confidentiality by encryption. ByteStream decides to use the simple shared-secret system shown below:

A shared-secret key functions as the seed for a pseudorandom number generator, and the result is used in an XOR operation to encrypt text. The XOR of the resulting ciphertext and the bit stream produced by the pseudorandom number generator seeded with the shared-secret key is computed in order to decrypt the ciphertext.

Figure $PS.29.1$: A simple shared-secret encryption/decryption system.

ByteStream uses the exclusive-OR (XOR, shown as ⊕) function. The pseudorandom number generator (PRNG) generates a stream of hard-to-predict bits, using the shared-secret key as a seed. Whenever it is seeded with the same key, it will generate the same bit stream. Messages are encrypted by computing the XOR of the message and the bit stream produced by the generator. The resulting ciphertext is decrypted by computing the XOR of the ciphertext and the bit stream produced by the PRNG, seeded with some key. The code for the PRNG is publicly available.

To check the implementation, ByteStream Inc. hires a tiger team that include Eve S. Dropper and Lucy Fer. The tiger team verifies that the code for computing the XOR is bug-free and the PRNG does not contain cryptographic weaknesses. The tiger team subsequently studies the following scenario. Alice shares a 200-bit key K with Bob. Alice encrypts a message with K and sends the resulting ciphertext to Bob. Bob decrypts this message with K . The result after decryption is Alice’s message. Assume that every message is equally likely (i.e., Alice's message contains no redundancy whatever).

Q29.1 Given that Eve sees only the cipher text, can she cryptanalyze Alice's message?

A. No, since only Alice and Bob know the key, and the PRNG generates a 0 or 1 with equal probability, Eve has no way of telling what the content of Alice's message is.
B. Yes, since with a supercomputer Eve could try out all possible combinations of 0s and 1s for K and check whether they match the cipher text.
C. No, since it is hard to compute the XOR of two bit streams.
D. Yes, since XOR is a simple function, Eve can just compute the inverse of XOR .

Q29.2 Alice and Bob switch to a new shared key. Lucy mounts an active attack by tricking Alice into sending a message that begins with 500 ones, followed by Alice's original message. Given the ciphertext can Lucy cryptanalyze Alice's message?

A. Yes, since the key is smaller than 500 bits.
B. Maybe, but with probability so low that it is negligible.
C. No, since only Alice and Bob know the key and the PRNG generates a 0 or 1 with equal probability, Lucy cannot extract Alice's message.
D. No, since it is hard to compute the XOR of two bits.

ByteStream is interested in a product that supports two-way communication. ByteStream implements two-way communication by having one stream for requests and another stream for replies. ByteStream seeds both streams with the same key. Since ByteStream worries that using the same key in both directions might be a weakness, it asks the tiger team to check the implementation.

The tiger team studies the following scenario. Alice seeds the PRNG for the request stream with K and sends Bob a message. Upon receiving Alice's message, Bob seeds the PRNG for the reply stream with K , and sends a response to Alice. Again, assume that every request and response is equally likely.

Q29.3 What can Eve deduce about the content of the messages?

A. Nothing.
B. The content of the request, but not the reply.
C. The XOR of the request and the reply.
D. The content of both the request and the reply.

Problem Set 30: Stamp Out Spam$^*$

$^*$ Credit for developing this problem set goes to Hari Balakrishnan.

2005–3–6

(Chapter 5)

Spam, defined as unsolicited messages sent in large quantities, now forms the majority of all email and short message service (SMS) traffic worldwide. Studies in 2005 estimated that about 100 billion (100 × 10⁹) emails and SMS messages were sent per day, two-thirds of which were spam. Alyssa P. Hacker realizes that spam is a problem because it costs virtually nothing to send email, which makes it attractive for a spammer to send a large number of messages every day. Alyssa starts designing a spam control system called SOS, which uses the following approach:

A. Allocation. Every sender is given some number of stamps in exchange for payment. A newly issued stamp is fresh, while one that has been used can be cancelled to ensure that it is used only once.

B. Sending. The sender (an outgoing mail server) attaches a fresh stamp to each email message.

C. Receiving. The receiver (an incoming mail server) tests the incoming stamp for freshness by contacting a quota enforcer that runs on a trusted server using a TEST_AND_CANCEL remote procedure call (RPC), which is described below. If the stamp is fresh, then the receiver delivers the message to the human user. If the stamp is found to be cancelled, then the receiver discards the message as spam.

D. Quota enforcement. The quota enforcer implements the TEST_AND_CANCEL RPC interface for receivers to use. If the stamp was not already cancelled, the quota enforcer cancels it in this procedure by storing cancellations in a database.

Alyssa's hope is that allocating reasonable quotas to everyone and then enforcing those quotas would cripple spammers (because it would cost them a lot), while leaving legitimate users largely unaffected (because it would cost them little).

Like postage stamps, SOS's stamps need to be unforgeable, for which cryptography can help. SOS relies on a central trusted stamp authority, SA , with a well-known public key, SA_pub, and a corresponding private key, SA_priv. Each sender S generates a public/private key pair, (S_pub, S_priv) , and presents S_pubto SA along with some payment. In return, the stamp authority SA gives sender S a certificate (C_S) and allocates it a stamp quota.

C_S = {S_pub, expiration_time, daily_quota}_SApriv

The notation {msg}_kstands for the marshaling of msg and the signature (signed with key k ) of msg into a buffer. We assume that signing the same message with the same key always generates the same bit string. In the certificate, expiration_time is set to a time one year from the time that SA issued the certificate, and daily_quota is a positive integer that specifies the maximum number of messages per day that S can send.

S is allowed to make up to daily_quota stamps, each with a unique integer id between 1 and daily_quota , and the current date. To send a message, S constructs and attaches a stamp with the following format:

stamp = {C_S, {id, date}_Spriv}

When a receiver gets a stamp, it first checks that the stamp is valid by running CHECK_STAMP_VALIDITY (stamp) . This procedure verifies that C_Sis a properly signed, unexpired certificate, and that the contents of the stamp have not been altered. It also checks that the id is in the range specified in C_S , and that the date is either yesterday's date or today's date (thus a stamp has a two-day validity period).

If any check fails the receiver assumes that the message is spam and discards it. If all the checks pass, then the stamp is considered valid. The receiver calls TEST_AND_CANCEL on valid stamps.

Unless otherwise mentioned, assume that:

No entity's private key is compromised.
All of the cryptographic algorithms are computationally secure.
SA is trusted by all participants and no aspect of its operation is compromised.
Senders may be malicious. A malicious sender will attempt to exceed his quota; for example, he may attempt to send many messages with the same stamp, or steal another sender's unused stamps.
Receivers may be malicious; for example, a malicious receiver may attempt to cancel stamps belonging to other senders that it has not seen.
Most receivers cancel stamps that they have seen, especially those attached to spam messages.
Each message has exactly one recipient (don't worry about messages sent to mailing lists).
Spammers and other unsavory parties may mount denial-of-service and other resource exhaustion attacks on the quota enforcer, which SOS should protect against.

Alyssa implements TEST_AND_CANCEL as shown below.

1 procedure TEST_AND_CANCEL (stamp, client) 2 // assume that client is not a spoofed network address 3 if CHECK_STAMP_VALIDITY (stamp) ≠ VALID then return 4 u ← GET (num_uses, stamp) 5 if u > 0 then status ← CANCELLED 6 else status ← FRESH 7 u ← u + 1 8 PUT(num_uses, stamp, u) 9 SEND(client, status); // assume reliable data delivery

Because spammers have an incentive to reuse stamps, she wants to keep track of the total number of TEST_AND_CANCEL requests done on each stamp. num_uses is a hash table keyed by stamp that keeps track of this number. The hash table supports two interfaces:

PUT (table, key, value) inserts the (key, value) pair into table.
GET (table, key) returns the value associated with key in table, if one was previously PUT , and 0 otherwise. A value of 0 is never PUT .

Q30.1 Louis Reasoner looks at the TEST_AND_CANCEL procedure and declares, "Alyssa, the client would already have checked that the stamp is valid, so you don’t need to call CHECK_STAMP_VALIDITY again." Alyssa thinks about it, and decides to keep the check. Why?

Q30.2 Suppose that a recipient R gets an email message that includes a valid stamp belonging to S. Then, which of the following assertions is true?

A. R can be certain that the email message came from S.
B. R can be certain of both the data integrity and the origin integrity of the certificate in the stamp.
C. R may be able to use the information in this stamp to cancel another stamp belonging to S with a different id.
D. If an attacker breaks into a computer that has fresh stamps on it, he may be able to use those stamps for his own messages, even though the stamps were signed by another entity.
E. S can tell whether or not R received an e-mail message by calling TEST_AND_CANCEL to see if the stamp attached to that message has been cancelled at the quota enforcer.
F. If S has encrypted the email message with R_pub, then no entity other than S or R could have read the contents of the message without S or R knowing.

The United Nations Privacy Organization looks at Alyssa's proposal and throws a fit, arguing that SOS compromises the privacy of sender-receiver email communication because the stamp authority, which also runs the quota enforcer, may be able to guess that a given sender communicated with a given receiver. Alyssa decides that the SOS protocol should be amended to meet two goals:

G1. It should be computationally infeasible for the stamp authority (quota enforcer) to associate cancelled stamps with a sender-receiver pair.
G2. It should still be possible for a receiver to call TEST_AND_CANCEL and correctly determine a stamp's freshness.

Alyssa considers several alternatives to achieve this task. Louis proposes using an encryption method he calls DETERMINISTIC_ENCRYPT (msg, k), which always produces the same output string for the same (msg, k) input. A second scheme involves an off-the-shelf ENCRYPT (msg, k) that, because it adds a timestamp to the plaintext message, always produces different output for the same (msg, k) input. A third alternative uses HASH (msg) , a cryptographically secure one-way hash function of msg . Alyssa removes line 3 of TEST_AND_CANCEL so that it no longer calls CHECK_STAMP_VALIDITY and she checks to make sure that TEST_AND_CANCEL will accept any bit-string as its first argument. S_pub is S's public key (from the certificate in the stamp) and R_pub is R's public key.

Q30.3 Which of these methods achieves goals G1? Which achieves G2?

A. The receiving client R extracts u = {C_S, {id, date}_Spriv} from the stamp, and computes e₁ = DETERMINISTIC_ENCRYPT (u, S_pub) . It then calls TEST_AND_CANCEL (e₁, R) .

B. The receiving client R extracts u = {C_S, {id, date}_Spriv} from the stamp, and computes e₂ = ENCRYPT (u, R_pub) . It then calls TEST_AND_CANCEL (e₂, R) .

C. The receiving client R extracts u = {C_S, {id, date}_Spriv} from the stamp, and computes h = HASH (u) . It then calls TEST_AND_CANCEL (h, R) .

Alyssa realizes that if SOS is to be widely used she will need several computers to run the quota enforcer to handle the daily TEST_AND_CANCEL load. Alyssa finds that storing the num_uses hash table used by TEST_AND_CANCEL on disk gives poor performance because the accesses to the hash table are random. When Alyssa stores this hash table in RAM, she finds that one computer can handle 50,000 TEST_AND_CANCEL RPCs per second on a realistic input workload, including the work required to find the machine storing the key (compared to ≈100 RPCs per second for a disk-based hash table implementation). The network connecting clients to the quota enforcer servers has extra capacity and is thus not the bottleneck.

The space required to store stamps in Alyssa's current design is rather large. She decides to save space by storing HASH (stamp) rather than the much larger stamp. With this optimization, storing each cancellation in the num_uses hash table consumes 20 bytes of space. Assume that num_uses stores only stamps that are from today or yesterday. Alyssa purchases computers that each have one gigabyte of RAM available for stamp storage.

Q30.4 Alyssa finds that the peak TEST_AND_CANCEL request rate is 10 times the average. Estimate the number of servers that Alyssa needs for SOS in order to handle 100 billion TEST_AND_CANCEL operations per day. (Use the approximation that there are 10⁵ seconds in one day.) Be sure to consider all of the potential bottlenecks.

Alyssa builds a prototype SOS system with multiple servers. She runs multiple TEST_AND_CANCEL threads on each server. Alyssa wants each thread to be recoverable and for all cancelled stamps to be durable for at least two days. She also wants the different concurrent threads to be isolated from one another.

Alyssa decides that a good way to implement the quota enforcer is to use transactions. She inserts a call to BEGIN_TRANSACTION at the beginning of TEST_AND_CANCEL and a call to COMMIT just before the call to SEND . She implements a disk-based undo/redo log of updates to the num_uses hash table using the write-ahead log protocol (each disk sector write is recoverable). She uses locks for isolation.

Because all stamp cancellations are stored in RAM, Alyssa finds that a server crash loses the entire in-RAM hash table of previously cancelled stamps. A thread could also ABORT at any time before it COMMITs (for example, the operating system could decide to ABORT a thread that is running too long).

Q30.5 Which of these statements about SOS's recoverability and durability is true?

A. When a thread ABORTs, under some circumstances, the ABORT procedure must undo some operations from the log.
B. When a thread ABORTs, under some circumstances, the ABORT procedure must redo some operations from the log.
C. The failure recovery process, under some circumstances, must undo some operations from the log.
D. The failure recovery process, under some circumstances, must redo some operations from the log.
E. When the failure recovery process is recovering from the log after a failure, there is no need for it to ACQUIRE any locks as long as no new threads run until recovery completes.

Q30.6 Recall that an important goal in SOS is to detect if any stamp is used more than once. Louis Reasoner asserts, "Alyssa, any reuse of stamps will be caught even if you don't worry about before-or-after atomicity between TEST_AND_CANCEL threads." Give an example to show why before-or-after atomicity is necessary.

Satisfied that her prototype works and that it can handle global message volumes, Alyssa turns to the problem of pricing stamps. Her goal is "modest": to reduce spam by a factor of 10. She realizes that her answer depends on a number of assumptions and is only a first-cut approximation.

Q30.7 Alyssa reads various surveys and concludes that spammers would be willing to spend at most US $11 million per day on sending spam. She also concludes that 66% (two-thirds) of the 100 billion daily messages sent today are spam. Under these assumptions, what should the price of each stamp be in order to reduce the number of spam messages by at least a factor of 10?