The Security Mechanisms in Multics Operating System

Sharing and protection in Multics Landon Cox Landon Cox January 27, 2017 January 27, 2017

User programs Layer 4 I/O devices Layer 3 Layer 2 Console Supervisor Supervisor code code Layer 1 Pager Layer 0 Scheduler

User/kernel translation data 4GB 4GB Kernel data Kernel data (same for all (same for all page tables) page tables) 3GB (0xc0000000) User data User data (different for (different for every process) every process) 0GB 0GB Virtual memory Virtual memory

Kernel vs. user mode Who sets up the data used by the MMU? Who sets up the data used by the MMU? Can t be the user process Otherwise could access anything Only kernel kernel is allowed to modify any memory Processor Processor must know to allow kernel must know to allow kernel To update the translator To execute privileged instructions (halt, do I/O)

Kernel vs. user mode How does machine know kernel is running? How does machine know kernel is running? This requires hardware support Process supports two modes, kernel and user Mode is indicated by a hardware register Mode Mode bit bit

Protection GBs GBs of protected data of protected data 1. 1. All memory accesses go through a translator All memory accesses go through a translator Who can modify translator s data? 2. 2. Only Only kernel can modify translator s data kernel can modify translator s data How do we know if kernel is running? 3. 3. Mode Mode bit indicates if kernel is running bit indicates if kernel is running Who can modify the mode bit? One bit One bit of protected data of protected data Making progress: the amount of protected data is down to a bit Making progress: the amount of protected data is down to a bit

Protecting the mode bit Can kernel change the mode bit? Can kernel change the mode bit? Yes. Kernel is completely trusted. Can Can user process change the mode bit? user process change the mode bit? Not directly directly User programs need to invoke the kernel Must be able to initiate a change

When to transition from user to kernel? 1. 1. Exceptions (interrupts, traps) Exceptions (interrupts, traps) Access something out of your valid address space (e.g., segmentation fault) Disk I/O finishes, causes interrupt Timer pre-emption, causes interrupt Page faults 2. 2. System System calls Similar in purpose to a function call Kernel as software library calls

System call implementation Syscalls Syscalls are like functions, but different are like functions, but different Implemented Implemented by special instruction by special instruction syscall Execution Execution of Processor safely transfers control to kernel Hardware invokes kernel s syscall trap handler of syscall traps to kernel traps to kernel

Kernel trap details User process can initiate mode switch User process can initiate mode switch But only transfers control in limited way (i.e., to predefined kernel code) How How does processor know where to jump? does processor know where to jump? Stored in hardware interrupt vector table Who Who can update the interrupt vector table? can update the interrupt vector table? Kernel does this at startup Code that runs first gets control of machine

User programs Layer 4 I/O devices Layer 3 Layer 2 Console Layer 1 Pager Layer 0 Scheduler

THE Were THE processes protected from each other? Were THE processes protected from each other? Yes, processes had private segment spaces Those spaces were isolated via the compiler and Layer 1 Isolation/protection was the motivation for layering Isolation/protection was the motivation for layering What is the flip side of protection? What is the flip side of protection? Sharing! There are often many benefits to sharing (i.e., features ) Sharing creates complexity Sharing requires access control (for safety and fault tolerance)

THE Could THE processes share in Could THE processes share in- -core data? Only within the structure of the hierarchy Lower layers were like shared libraries User processes could not share with each other core data? What about persistent data? What about persistent data? Not really, no common data base.

THE Important idea not supported by THE Important idea not supported by THE The notion of a user user not intended as a multi-access system What is a user in a computer system? What is a user in a computer system? Identifier assigned to processes and storage objects Unit of access control in most systems Often associated with a person, but doesn t have to Do modern machines support users? Do modern machines support users? Desktops/servers do, mobile devices kind of do

Multics Multi Multi- -user operating system user operating system Primary goal is to allow efficient, safe sharing btw users What was the central data abstraction in Multics? What was the central data abstraction in Multics? A segment segment All All data was contained within a segment No distinction between files and memory Means all stores are persistent What is a segment? What is a segment? Named range of contiguous data + associated meta-data Accessed through loads/stores in memory Think of a segment as an mmapped region of memory

Block-oriented vs byte-oriented Disks are accessed in terms of Disks are accessed in terms of blocks Also called sectors sectors Similar idea to memory pages E.g., 4KB chunks of data blocks First problem: programs First problem: programs deal with bytes E.g., want to change H in Hello world to J Disks only support block-sized, bulk accesses deal with bytes

Block-oriented vs byte-oriented To To read less than a read less than a block Read entire block Return the right portion block How How to write less than a block? to write less than a block? Read entire block Modify the right portion Write out entire block Nothing Nothing analogous to byte analogous to byte- -grained load/store Flash devices are even more complicated grained load/store

mmap overview Maps file data into virtual address space Maps file data into virtual address space Must be mapped at page granularity Data accessed via loads/stores (Most) virtual pages are mapped to a storage page (Most) virtual pages are mapped to a storage page For normal virtual memory page, place to swap in/out For mmapped region, backing is the specified file Mmaped regions w/o backing file are called anonymous pages m mmap map implementation implementation Integrated with in-memory buffer cache (i.e., kernel s file cache) Loads/stores immediately applied to buffer cache Reads by other processes hit buffer cache

mmap overview Let s do a demo Let s do a demo When When is is mmaped mmaped data actually persistent (i.e., data actually persistent (i.e., hits hits the disk)? the disk)?

Multics segments Implications of segments Implications of segments Difference between a program and process? Difference between a program and process? We think of a process as an execution of a program In Multics, there was very little distinction What does this force programmers to do? What does this force programmers to do? Must explicitly manage segments Process cannot just exit and return to a known state Places a lot of burden on programmers Beware, complexity creep

Segment access Address [ Address [s,i s,i] ] Descriptor Base Register Descriptor Segment Core Core|Ld s s Segment Descriptor Word L Ld d Segment Core Core|L Ls s|Acc|F Lookup algorithm? Lookup algorithm? ii if(DBR.L < S) fault sdw = DW[s] if(sdw.F || sdw.L<i) fault if(!verify(sdw.Acc)) fault return sdw.Core + i L Ls s word of data L = length, Acc = protection, F = resident

What about paging? How do we make sure that segments are in How do we make sure that segments are in- -core? Segments are broken into fixed-size pages Another structure to map parts of a segment to pages core? pages (1k) Page tables describe where pieces are in core Page tables describe where pieces are in core Descriptor segment is a segment too Descriptor segment is a segment too Must locate the pages on which it is located Can then walk data structure to locate data

(1) Find page table for descriptor descriptor segment segment Paged segment access (2) Page holds part of descriptor descriptor segment segment Descriptor Base Register Page Table Page Table of Descriptor Segment [ [s,i s,i] ] [ [sp,sw,ip,iw sp,sw,ip,iw] ] Core|L (3) Use descriptor descriptor segment segment to find page table for data segment Page sp of DS sp sp Core|L sw sw Segment Descriptor Word Page Table Page Table of Segment S Page ip of Segment S Core|L|Acc|F What s the problem with this? What s the problem with this? Core|L ip ip This is a lot How do we make it faster? How do we make it faster? a lot of memory accesses iw iw word of data (4) Use page table to locate data we want to access Caching in hardware: TLB

Multics supervisor code Location of THE supervisor state Location of THE supervisor state In separate processes at low-level layers In Multics, where did supervisor state reside? In Multics, where did supervisor state reside? In segments mapped into every process Supervisor segments were at top of address space How was supervisor state protected? How was supervisor state protected? Hardware protection provided by processor Hardware supported 8 protection rings Idea was to enforce layering via hardware Exactly like mode bit (kernel/user) you are used to

Multics supervisor code How did programs invoke the supervisor? How did programs invoke the supervisor? Just a procedure call Calls always reside in segments at top of addr. sp. Just jump into code in those segments What else has to happen? What else has to happen? Have to change hardware protection mode Who/what changed protection modes? Who/what changed protection modes? This was hardware enforced All segments were assigned a ring level (including code) Mode for an instruction was set in descriptor on which it resided

Segment sharing To facilitate sharing need common namespace for segments To facilitate sharing need common namespace for segments Multics uses file hierarchy to name all segments Populating address space like a bunch of mmap calls Why is this a nice abstraction? Why is this a nice abstraction? Maps human-readable names (easy to program) to data Makes it easy to specify what data you want to operate on Who manages the namespace? Who manages the namespace? Must be privileged code Common data structure used by all processes Only code trusted by all should be allowed to modify directly

Segment sharing What operations can a process perform on the namespace? What operations can a process perform on the namespace? Create a segment Delete a segment Change a segment s name Change the access policy of a segment Read the content of a directory Who prevents collisions in the namespace? Who prevents collisions in the namespace? The supervisor code On a request to create a segment, checks to see if it already exists

Segment sharing How does a process populate its address space? How does a process populate its address space? Must know or compute parts of the namespace Invokes the OS to map named segment into memory OS updates the Known Segment Table (KST) for process KST maps segments to pathnames OS returns beginning of segment, length to process Once mapped, how is data loaded into memory? Once mapped, how is data loaded into memory? Data is demand loaded Process accesses address (e.g., [s,i]) This triggers a page fault and a trap to the OS The OS uses the KST to locate data on disk

Discussion Are Are Multics Multics segments a good idea or bad? segments a good idea or bad? Programmers may have to do a lot of garbage collection Temporary state must be torn-down/re-initialized by hand Adds complexity Danger of accessing persistent data via loads/stores? Danger of accessing persistent data via loads/stores? Buggy programs can lead to stray writes Stray writes become permanent Why are permanent stray writes bad? Why are permanent stray writes bad? Important data structures could become corrupted Restarting program just puts you back in a bad state

Discussion How do most modern systems present persistent storage? How do most modern systems present persistent storage? Must access persistent storage through file system File system interface: open, read, write Why is an explicit file system interface safer? Why is an explicit file system interface safer? Write system call is similar to a commit An explicit acknowledgement that data is ready to be made persistent Buggy programs much less unlikely to generate a spurious write call Spurious loads and stores are very common in buggy programs We actually see this observation in Multics itself. Where? We actually see this observation in Multics itself. Where? In how it handles the namespace Important, persistent data structure Can only be modified in a controlled way, through narrow interface Nice to offer same interface for user data

Topic we will revisit Interfaces to persistent storage Interfaces to persistent storage Periodic source of new research In the 90s: battery In the 90s: battery- -backed RAM Memory persists across reboots Rio-Vista from Michigan (SOSP 97) backed RAM Today: phase Today: phase- -change memory, Intel 3D change memory, Intel 3D Xpoint Fast, persistent substrate BPFS from Microsoft and UCLA (SOSP 09) Xpoint (?) (?)