Machine code: How can an OS prevent user-level programs from accessing each other's memory? [duplicate]

Question

Okay, I’ve done a lot of research on this, but I can’t seem to wrap my head around it. Essentially, the question is as follows: How can an operating system prevent a machine instruction from a user-level program (Firefox, Word, etc.) from accessing memory locations that it isn’t supposed to access?

Here’s what I think I understand so far: Machine code, as you would for example find it in a .exe file after building your C/C++ program, is a sequence of binary instructions. These instructions can run directly on the CPU (assuming that the program was compiled for that CPU’s instruction set, e.g. x86). So, you don’t technically need an operating system to “run a program” in a broader sense – which isn’t surprising, since an operating system is just a program itself. Also, the CPU doesn’t work in terms of “programs” or “processes”, but in terms of individual instructions.

Now, if we do have an operating system (e.g. Windows), part of its job is to assign an encapsulated memory segment to each running user-level program (e.g. Firefox, Word, my own C++ program, …), and to make sure that they can’t read/corrupt each other’s memory.

This is where things get fuzzy for me. If I were to write my own operating system (or other bare-metal program), I would need to be able to use machine instructions to read/write to and from any existing location in the entire memory, right? So, how does an operating system make sure that no user-level program sends such instructions to the CPU on its own, without “asking the OS for permission” to access a certain memory location?

I would actually love to learn more on the entire topic of going from high-level code to machine instructions. For instance, I would also like to understand what user-level program threads and OS-level processes look like on bare-metal, etc. So, if anyone could point me to a good resource, that would be highly appreciated. Nonetheless, this isn’t the core of my post, just a side note.

Answer 1

The key is Virtual Memory.

There might be many ways to do this, but the reigning one across most OSes (*nix or Windowses alike) is Virtual Memory. And it needs CPU support, which is given in x86 by the MMU (Memory Management Unit) and in which I'll base my examples further on.

The secret is: no user-level process has access to the whole CPU. x86 has four rings of execution, and certain CPU opcodes (instructions) execute only within the appropriate ring. Ring 0 is for the kernel (the heart of the OS), and ring 3 is for user-level processes (rings 1 and 2 are most often not used, and if used, it's usually for virtualisation purposes -- out of the scope of this answer). If you execute an instruction within the wrong ring, the CPU faults to the kernel. Hence, if a process tries to execute a privilege instruction, when the CPU is on ring 3 mode, the CPU itself stops that process and gives control to the kernel, which will usually kill that process. Only the kernel can change the ring mode.

The secret-key for memory protection is that, all memory accesses, unless executed within the kernel's ring 0 (and perhaps even within that ring mode, but that's not relevant for this discussion, as we're talking only about user processes, not the kernel), need to go through the MMU, which will translate the memory address of the process to that which the kernel has actually given.

So two different processes can access a memory cell by the same address, say, 0x45b3c1, whatever. In reality, the MMU will translate real-time each process's request to what the kernel says it should be.

For this, the kernel prepares page tables, which you can imagine as a "map<void*, void*>" (forgive my over-simplification here, and try to imagine the crazy optimisations needed), of what the process actually has. And it prepares tables only for what the process previously said it would use. If the process asks for an address that hasn't previously asked the kernel to prepare a table for him, then the CPU says this process got nuts and in reference of this process, it signals the infamous SEGFAULT to the kernel, which will decide what to do next.

I know that this is sort of self-promotion, but I just recently wrote a lot about this topic and even gave a talk at my company, in case the link is welcomed I'd like to share: https://www.farfromready.com/malloc-alone-a-story-of-the-computers-memory/

Answer 2

Interpretation

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:

• Substitution
• Denotational
• Big-Step
• Small-Step

Substitution

Essential the interpreter rewrites the program into a simpler form. Much like when you rewrite 2 * 5 as 10.

Denotational

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.

Big-Step

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

Small-Step

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.

Answer 3

The simple solution is that the processor has different modes where the CPU has different capabilities. For example : The OS runs in mode 0. In mode 0 an application can set up memory protection for others, and start applications running in mode 1. In mode 1 the processor fails if you try to use one of the instructions that change memory protection or the current mode. The mode 0 program can also set a timer which will give control back to the operatin system after some time.