Homework 6 Solutions

22C:116, Fall 1999

Douglas W. Jones

  1. Part A: What storage allocation or free list management scheme would you suggest using to manage the free space on a WORM?
    Obviously, no linked list or other free-list data structure could be used, because once a pointer is written, it can never be changed.

    Therefore, the description of the free space must not be contained in the data parts of the blocks that have been used. If we allocate blocks sequentially, a simple counter would suffice, but this counter itself must use a data representation where no bit changes more than once.

    The only counter that fits this requirement uses a unary encoding, so 0 is represendted as 0000, 1 as 1000, 2 as 1100 and 3 as 1110. This data structure is really just a bit vector, with one bit per sector, where that bit is changed to a 1 when data is recorded on that sector.

    Part B: When a user creates a new version of /local_user/jones/temp on a WORM, what files must be replaced by new versions.

    We must record a new version of the directory /local_user/jones/, with the directory entry for temp pointing to the new version.

    Having created a new version of /local_user/jones/, we must now create a new version of /local_user/ with one entry changed.

    Having created a new version of /local_user/, we must now create a new version of / (the root directory) with one entry changed.

    Part C: How would you suggest finding the root of the file system on a WORM when the file system is mounted.

    With every change to any file on the WORM, the consequence is new versions of all directories on the path to that file, and therefore, all changes involve a change to the root!

    If we do not take advangate of the potential for random allocation, and instead, allocate files sequentially, using consecutive free sectors for each allocation, the most recently allocated sector will always be a sector of the root. If we agree to write files with their sectors in the right order, we can arrange things so the last sector written will be the first sector of the root.

    So, on mount, the WORM driver would search the allocation bit vector for the boundary between allocated and non-allocated sectors. This search would set things up for the next allocation at the same time that it finds the root.

  2. The Question: Macro viruses attached to Microsoft Word documents are a major problem today. Given what you know about the requirements a virus must meet in order to propagate through a computer system (see section 4.4 of the text) what features can you infer must be present in Microsoft Word's macro language?
    There must be some way for a macro attached to a word document to:
    1. begin execution when that document is opened,
    2. find other word documents in the file system,
    3. load another document for editing,
    4. attach a copy of a word macro to that document,
    5. mark that macro for auto-execution when that document is opened,
    6. and save the modified document, replacing the original.

    The above requirements are minimal. Virulence requires more, specifically, that the user be unaware of the activity of the virus as the user opens the document. Virulence would require one or more of the following:

    1. when the virus surrepiticiously opens a document to attach itself, nothing should appear on the screen.
    2. the virus must only modify a few documents when it is invoked or the time taken would make the user suspicious.
    3. the virus should be have persistant state information so that, on future invocations, it will begin its search for new documents to infect after the ones it has already infected. If this were not the case, the virus would re-infect the same few documents each time it became active.

  3. The Question What operations permitted in a conventional 2-level security model (user state/system state) are formally modeled as enter operations?
    System calls, typically implemented using traps, are enter operations from a user domain to the system domain.

  4. The Question What feature of CHMOD and the setuid bit prevent the use of the setuid bit to solve the mutual suspicion problem?
    Having exec'ed a file that has the setuid bit set, the effective user ID will now be that of the file's owner, so we are executing in the owner's domain. The problem is, UNIX maintains the old user ID as the real user ID, and UNIX allows the user to call setuid() to change the effective user ID to the real user ID.

    This feature destroys the utility of the setuid bit as a solution to the mutual suspicion problem because the caller of exec cannot prevent the called routine from reverting to the caller's user ID and performing arbitrary changes in the caller's domain.