A program is a file - so are pictures and text documents.
You can choose how to perceive the contents of these files. A good way to perceive each of these is as code in a language. To understand the code, it needs to be interpreted by an interpreter.
There are numerous ways to design an interpreter:
Essential the interpreter rewrites the program into a simpler form. Much like when you rewrite
2 * 5 as
Here the OS has a known safe function that it executes whenever it sees a particular instruction in the code.
The benefits here are that this function can have numerous safety checks and security measures.
A Big Step interpreter risks being wrong/non-terminating in order to resolve operations.
Non-Deterministic Finite State Machines fall into this category, as they can be wrong and have to back-track, or have to track each potential solution simultaneously.
The benefit to this approach is that the interpreter can finish the program in one of three top-level states:
- The program ran and succeeded
- The program ran but failed
- The program was wrong
The code is composed of discrete and finite steps. The job of the interpreter is to track the effects produced by the code.
Running Untrusted Code
The job of the OS is to run this untrusted code in such a way that none of the other applications are adversely affected (roughly).
So the OS literally interprets the program, and updates a model of the state of that program.
At this point the OS does have a choice in how it interprets the program. It could for example be Denotational when loading the program, and "rewrite" every instruction. It will already need to do this to bind dynamic-link-addresses, but the concept can be expanded to include all instructions.
- all "safe" instructions are rewritten (copied) as themselves
- any "unsafe" instruction can be
- substituted for an OS interrupt that fulfils the intention securely
- substituted for a sequence of "safe" instructions
- cause the program to be rejected and never run.
At the end of this process is a rewritten program which is "safe" at the per instruction level. This doesn't mean that the program cannot exploit hardware flaws, just that no "bad" instructions were found.
The OS could us Substitution to interpret patterns of instructions - particularly vulnerable sequences. These could be replaced with a more secure code pattern that achieves the same outcomes.
This will protect against some well known issues, but comes at the cost of having to analyse the code. This is a lot harder for languages (like machine languages) which are built to take advantage of small-step semantics.
The OS could use Big-Step interpretation, though generally this occurs in the hardware itself. Generally the CPU operates so quickly that memory is slow. It often pays to evaluate a tree of paths simultaneously and pick the correct path from the tree when the results from the relevant branch checks come back.
Of course these hardware implementations are not necessarily safe. The recent Spectre and Meltdown exploits highlight this, the fixes across the variants for many processors/work-loads caused slowdowns by 10-30%. The difference between using Big-Step semantics provided through hardware, and the software interpretation required to replace them, or make them safe.
Finally the OS can apply small-step semantics. This could be achieved by emulating a machine, and updating the state on that emulation appropriately. However this is slow, the OS could take advantage of the fact that the Processor is a real world example of that machine.
This relies on trusting the program/processor enough that either the program will behave well (even if the hardware could allow sneaky sneaky operations), or that the processor will tell the OS when the program misbehaves. Usually it is a balance of these two extremes with the OS interpreting the program enough to be satisfied that it is not out-right bad news, and the OS using the controls that the processors gives it to prevent certain instructions from being executed.
Most Processors have:
a Virtual Memory Table which maps the virtual memory space of a process to the physical memory address. The memory access instructions use it to map from process memory to physical memory, with missing entries causing an OS interrupt. The OS then is only needed when dealing with non-memory resident pages, and unallocated memory. The processor itself does not allow access to the other physical memory locations.
Security levels that enable/disable certain instructions. A program running within that processor will cause a OS interrupt if it executes a privileged instruction and its security level isn't correct. It is then up to the OS as to how to handle this privileged behaviour.