Sandboxing, the first form of software based fault isolation, derives its name from the idea of isolating a user program in a sandbox where it can execute safely without the possibility of damaging anything outside the sandbox. Like hardware implemented memory protection, sandboxing ensures that unsafe instructions cannot access memory outside the sandbox. The idea is presented by Wahbe et al. [102], where the authors consider write and jump instructions as unsafe. However, as Small and Seltzer [86] point out, read operations must also be regarded as unsafe, since some hardware devices change state when they are read. Of course, privileged instructions such as reset, instructions that change the memory access privileges, instructions that disable (the watchdog timer) interrupts, and illegal instructions must be prohibited. Sandboxed code has to be inspected during code insertion. There is no need to trust the compiler to have done the sandboxing correctly.
A sandbox consists of two memory segments. One for text and the other for data. The segments are aligned such that the upper n bits, the segment index, of all addresses in each segment are the same. During compilation, code is inserted before each unsafe instruction to prevent access to locations outside the allocated segments. This code sequence forces the upper n bits of the unsafe instruction address to be the same as the segment index. This prevents any reads and writes outside the data segment and prevents jumps to locations outside the text segment.
Figure 2.10 and Figure 2.11 illustrate examples
of sandboxing a load and a jump instruction. The Intel i860
instruction to the left is sandboxed by the instruction sequence to
the right. Five dedicated registers are used. Two are needed for
load and stores (r
, r
), two for jumps
(r
, r
), and one can be shared by all
sandboxed instructions (r
). r can be shared if the
segment index is of the same width for both the data and the code
segment. The inspection that is performed during code insertion has
to ensure that the dedicated registers are not modified outside the
sandboxing sequence.
Figure 2.10: Sandboxing a Load Instruction in i860
Assembly: r, r, and
r are dedicated registers the user code
cannot use.
Figure 2.11: Sandboxing a Jump Instruction in i860
Assembly: r, r, and
r are dedicated registers the user code
cannot use.
Segment matching is the second form of software based fault isolation. It is an extension of sandboxing and allows pinpointing the location of an offending instruction and simplifies debugging. Instead of simply forcing the upper n bits to be the same as the segment index, the n bits are compared with the segment index. If they are the same, it is safe to execute the instruction. If not, execution flow branches to an error handling routine that can output detailed information and abort the offending procedure. Figures 2.12 and 2.13 illustrate segment matching.
Figure 2.12: Load Instruction With Segment Matching
in i860 Assembly: r, r, and
r are dedicated registers the user code
cannot use. r
is a temporary register that
can be used outside the segment matching code.
Figure 2.13: Branch Instruction With Segment Matching in i860
Assembly: r, r, and
r are dedicated registers the user code
cannot use. r is a temporary register that
can be used outside the segment matching code.
To prevent self-modifying code, two segments are needed. One for data (static, heap, and stack), and one for the code. Load and store instructions are restricted to the data segment, while branch instructions have to stay in the code segment. Note that branches into any part of the sandboxing code are possible and the sandboxing code has to be written in such a manner that none of the dedicated registers can be compromised. Both software based fault isolation techniques require five dedicated registers. (Under certain conditions it is possible to save one register in the segment matching case.) On a RISC CPU with 32 general purpose registers, this is not a big problem. On a CISC architecture, such as the Pentium Pro, with only 8 general purpose registers, the techniques can still be used, albeit at the cost of slower performance. In the case of the Pentium Pro which has segmentation registers, it would be interesting to compare the cost of using segment registers instead of software based fault isolation.
The authors of [102] report an average fault isolation
overhead of 
in a variety of benchmarks, isolating writes and
jumps only, and allowing reads from any location of mapped memory.
This agrees with the reported 
to 
in [96].
The insertion of the sandboxing or segment matching instructions before each unsafe instruction can be done at compile time or at the time the code is inserted into the kernel. In the former case, the kernel has to ensure that the function has been properly sandboxed. Wahbe et al. present an algorithm to do that [102]. The algorithm ensures the following:
.
.
, r,
r, r, r) are updated
outside the sandboxing codes.
To limit running time, a watchdog timer is used. The timer is set at the time the handler starts executing and terminates the handler if it goes off before the handler has finished.