Graft Safety

One of the basic requirements of VINO is that installed graft code must not jeopardize the integrity of the system. Consequently, special care must be taken when installing grafts. The use of software fault isolation (and cryptographic techniques to ensure this step is not bypassed) ensures that graft code will not be able to make references to protected or nonexistent data, make calls to invalid locations, tinker with processor control registers, and so forth.

Unfortunately, this is not enough. It is also necessary to validate any data issued by graft code: both arguments to calls made by the graft into the kernel, and also anything returned by the graft to the function that invoked it. And in addition to this, it is necessary to keep the graft from denying service of any sort to the rest of the system.

For example, consider a function that selects a virtual memory page for eviction from main memory. In a conventional kernel, such a function might return a physical page number, a pointer to a page header, to some other artifact that identifies the page for eviction. In VINO, functions of this sort are meant to be graftable. Therefore, the return value, whatever it is, must be verified before the rest of the kernel acts upon it. Otherwise, the graft could (for example) cause the system to crash by requesting the eviction of a nonexistent page.

In order to guarantee that all graft-generated data is properly verified, any graftable function must be declared as such. This makes it an actual graft point. There are two macros we use in our source for doing this: "GRAFTABLE" is used to declare a graftable function, and "DEFAULT_GRAFT" is used when defining the default version of the function, that is, what gets run if no graft has been installed. The program stubgen finds these declarations and generates stub code that figures out what graft to invoke and invokes it, if any, otherwise calling the default function.

The additional macro "GRAFT_CALLABLE" is used to declare a function that may be called from a graft. Since we aren't interested in making graft writers reimplement reams of already existing kernel code, we needed a mechanism for letting graft code call back into the kernel. GRAFT_CALLABLE functions are expected to validate their arguments, that is, check for bad pointers and illegal flag values and so forth. A GRAFT_CALLABLE function is like a system call in that the arguments it receives may be not merely nonsense but malicious nonsense, and it must be able to cope with whatever gets thrown at it.

The other characteristic of GRAFT_CALLABLE functions is that they must be transaction-safe. (Functions that are just transaction-safe but not GRAFT_CALLABLE are declared GRAFT_SAFE.) Functions that are transaction-safe use the facilities of the transaction manager to ensure that everything they do can be rolled back if the transaction in progress is aborted. This works by either recording undo operations in the transaction's undo log (these are all called in LIFO order if the transaction is aborted) or recording commit operations in the transaction's commit log (these are called in FIFO order when the transaction commits.) If no transaction is in progress, things placed on the undo log are ignored and things placed on the commit log are executed immediately. This permits the same code to be used for normal code paths as well as GRAFT_SAFE ones.

Note that it is perfectly acceptable for a GRAFT_SAFE function to call other functions that are not GRAFT_SAFE as long as it arranges for the effects of those functions to be undone if the transaction aborts. However, when one GRAFT_SAFE function calls another, no undo records need to be created by the caller, since the callee handles that on its own.

The transaction system exists so that grafts that proceed for a while and then do something unacceptable can be removed and all traces of their activity rolled back. For instance, if a graft creates some new objects and then attempts to print another user's disk buffers, not only should it be removed, but the objects it created need to be deleted as well. This is accomplished by creating a transaction whenever a graft is invoked, and committing the transaction when the graft returns successfully. If the graft fails, the transaction is aborted.

Denial of service attacks by grafts are handled on a case-by-case basis. Attacks by resource allocation are prevented, in most cases, by not giving the graft direct access to any resource allocation code. A graft has its own data segment and a small heap and stack area; it can allocate memory within that region as it pleases, but the size of the whole thing is fixed. Attacks by consuming CPU cycles are prevented, or at least discouraged, by starting a timer when a graft is invoked: if the graft doesn't finish before the timer expires, the graft is considered to have failed and is forcibly removed. Additionally, since the VINO kernel is fully preemptible, if a graft uses excessive CPU time, that time ends up getting charged to the application that installed it, and so a graft that doesfor (int i=0; i<100000; i++); has exactly the same effect as a user-level program that does the same thing.