Homework 13

22C:116, Fall 1995

Due Friday Dec. 1, 1995, in class

Douglas W. Jones
  1. Background: Consider the notion of cached copies of files used in the Andrew File System described in section 13.2.5. One interesting alternative to this hierarchical architecture, where cached copies of files replicate files stored on servers is to use a flat system in which there are no file servers, and where all files are stored in caches on client machines.

    In such a file system, when a user needs access to a file, a copy of that file is brought into the local cache. Files have no permanent residence on a server, but migrate freely from cache to cache as various users reference them. Widely read files will, as a result, be widely replicated.

    Part A: In the absence of a file server, what kind of protocol would you propose to use in such a system when a user program opens a file? Do not propose any details of this protocol! Instead, clearly state the problems the protocol must solve!

    Part B: Can you propose a way to deal with the problem of incoherency that results when multiple processes open a file for write access? Before answering this question, consider how Andrew deals with this problem and ask yourself how the lack of servers in this "all cache" file system architecture changes the nature of the problem.

  2. Background: Consider the problem of protecting access rights in a distributed file system where stateless servers retain no record of how a file was opened, and where, therefore, users must hold tokens representing the access rights they have for files they have opened.

    For this problem, we will use the following notation:

    In the following list of alternatives, the access rights handed to the user is given by the function U(R):
    1. U(R) = E(K,R)
    2. U(R) = E(K,<R,N>)
    3. U(R) = E(K,<R,C(R)>))
    4. U(R) = <E(K,R),H(E(K,R))>
    5. U(R) = <R,H(R)>
    6. U(R) = <R,N,H(<R,N>)>

    Part A: For each of the above alternatives, how would the system, on receiving U(R) from a user, reconstruct the rights R that the user has and verify that the set of rights R have not been tampered with.

    Part B: For each of the above alternatives, what must the user accomplish in order to defeat the system -- that is, in order to forge a set of rights differing from the rights issued to the user by the system. Assume that all sets of rights are members of the powerset of {read, write}. Based on this, which of the alternatives listed above are sufficiently resistant to tampering to be acceptable as a basis for a secure distributed file system.

    Part C: There is something fundamentally wrong with all of the above alternatives. What?