Multics

  • ‌Multiplexed Information and Computing Service
  • MIT, 1969 (in cooperation with Bell Labs and GE)
  • Basis for UNIX
  • Features
    • Virtual memory with segmentation and paging
    • Hierarchical file system (with symbolic names and automated backup)
    • Concepts for security
  • Problem:
    • Slow + complex
    • Lead to development of security kernels

Fundamentals

  • Core concept:
    • Processes (executable contexts)
    • Segments (storage of code/data/devices)

Process

  • Executable context (i.e., runs program code)
  • Process is assigned to the user/subject
  • Protection domain of process:
    • Segments it has access to
    • Complete Descriptor segment
  • Descriptor segment:
    • Each process has a descriptor segment
    • Contains the segment a process can access (without segfaults)
    • Composed of segment descriptor words (SDWs)
  • Segment descriptor word: Address of the segment

../_images/multics.png

Segments

  • Storage of code/data/devices
  • Have symbolic names in hierarchical name space (directories and segments)
  • Are granularity/unit of sharing
    • Protection ring
    • Segment protection level (all processes having access)
  • Segments are made known
    • Process is interrupted
    • Translate segment name to address
    • Construct SDW
    • Perform access control
  • Segmentation to extend address space: Divide process memory into segments
  • References across segments using dynamic linking (not used anymore)
  • Addressing:
    • Inside a process
    • By name from secondary storage (e.g., disk)
  • Multics Kernel is responsible for segment swapping

Security fundamentals

  • Security goals of system
    • Secrecy (prevent leakage)
    • Integrity (Prevent unauthorized modification)
    • Comprehensive control
  • Architecture:
    • Secrecy: Multilevel security
    • Reference Monitor:
      • Mediate segment access
      • Mediate ring crossing
  • Security evaluation
    • Mandatory protection state guarantees failed
    • Reference monitor guarantees failed
  • But: Integrity can be achieved
  • Concepts
    • Supervisor
    • Protections rings
    • Segment description word

Example

  • Answering service: Process responsible for login/logout
  • Supervisor authorizes access to password segment

../_images/answering.png

Supervisor

  • Core component
  • Implements the reference monitor
  • Has highest privilege level
    • Ring 0: Access control, I/O, memory management
    • Ring 1: Accounting, file system search
  • Isolated from other processes (supervisor ring 0/1 only)
  • Tasks
    • Authorization (enforced at each instruction)
    • Segmentation
    • File systems
    • I/O
    • Scheduling
  • Most SDW authorization is enforced in hardware (formerly by supervisor)
  • Responsible:
    • Set descriptor segments
    • Protect descriptor segments (no modification by untrusted processes)
    • Protection domain transitions: Requires gatekeeper
  • Execution of segments:
    • Segments provide call gates for lower-privileged rings
    • Gatekeeper:
      • Is a special segment (program/code)
      • Performs Argument validation
        • Checking the number of expected arguments
        • Data type of each argument
        • Accessibility of each argument (e.g., copy arguments to lower-privileged segment)
      • Compare to Assured Guards
      • Runs in ring 0
    • Supervisor manages return gates (shared memory for return values)
    • Important: Domain transitions carry security risk!
      • High to low: Process data could be leaked
      • Low to high: Process could retrieve malicious data

Protection rings

  • Mechanism to isolate processes with different privilege levels
  • see ‌‌Multics Protection System Fundamentals > Ring mechanism
  • Hierarchical layering
    • Most privileged level 0
    • Less privileged level 64
  • e.g., GE 645 Multics hardware implemented 8

Segment description word

  • Define access restrictions and permissions (using the fields)
  • SDW points to segment
  • Contains access information for a specific process
  • Structure
    • Address of segment
    • Length of segment
    • Ring brackets (\( r_1,r_2,r_3 \))
      • Limit access based on process
    • Access control list
      • rwe bits
      • Purpose: Limit operations on that segment by user
    • Number of gates/Gate address
      • Enable access from lower-privileged ring
      • Define rings that may execute segment
      • Gatekeeper is code (running in ring 0) performing argument validation
      • Called gatekeeper (compare to Assured Guards)
  • Access Indicator: Ring brackets, ACL, Gates

../_images/sdw.png

Multics Protection System Fundamentals

  • Consists of three different models
    • Access Control Lists (limit access on user-basis)
    • Rings and brackets (limit access on process-basis)
    • Multilevel security (limit access on clearance-level)
  • Each model defines aspects of the Multics Protection System
  • Together, they perform the overall authorization

Access Control List

  • Each objects (segment or directory) gets an ACL
  • ACL composed of user identity and allowed operations (wildcards are allowed)
  • Purpose: Limit access based on user identity
  • Operations:
    • Segment: read, write, execute
    • Directory: status, modify, append
  • Segment ACL:
    • Stored in parent directory
    • A change requires a modification permission on the parent directory
  • Segment access:
    • Process requests access to segment
    • Check if user associated with the process has in the ACL of the segment
    • If the entry exists, the reference monitor authorizes the construction of an SDW with the requested operations and assigns it to the process

Ring mechanism

  • Ring bracket specification
    • Assigned to each segment (in parent directory)
    • \( r_1\leq r_2\leq r_3 \)
    • Can be changed by segment owner
  • Purpose:
    • Limit access based on the calling process (with its ring)
    • Define whether a process from ring \( r \) can read/write/execute the segment
    • Define protection domain transition rules (i.e., range of possible target rings)
    • Basically, access rights of ring \( i \) are superset of access rights of ring \( i+1 \)
  • Are Ring brackets a Mandatory protection system?
    • No
    • Mandatory protection state
      • Realization: 64 Rings and actions
      • Not immutable: Modifiable by owner
    • Labeling state
      • Realization: Ring determined at login
      • Not immutable: Ring of objects can be changed by owner
    • Transition state
      • Realization: Brackets define privileges and transition rules
      • Immutable by ring brackets

Access bracket

  • Access bracket \( r_1\leq r_2 \)
  • Define read/write access
  • \( 0 \leq r < r_1 \): Process can read and write (Write bracket)
  • \( 0 \leq r_1\leq r\leq r_2 \): Process can read only (Read bracket)
  • \( r_2 < r \): Process has no access
  • Ensure, that higher-privileged rings have more access than lower-privileged rings

Call/execute bracket

  • Call bracket \( r_2\leq r_3 \)
  • Define execute access (invoke code segment)
  • Define transition state
  • \( r < r_1 \): Process invokes code segment but process \( r \) makes a ring transition to new ring \( r' \) with \( r_1\leq r' \leq r_2 \)
  • \( r_1\leq r\leq r_2 \): Process invokes code segment in its ring
  • \( r_2\leq r\leq r_3 \): Process invokes code segment but ring transition to higher-privileged ring \( r' \) if authorized by the gates in SDW
  • \( r_3<r \): No access

Multilevel Security (MLS)

  • Goal:
    • Enforce secrecy
    • Prevent information leakage
  • see Access Control Policies > MLS
  • Mappings
    • Directory contains mapping from segment to secrecy level
    • Mapping from process to secrecy level
    • Secrecy levels are independent from rings
      • Multics-Docs: 4 levels
  • Request authorization conditions (one must be met)
    1. Write request: Grant if target (segment/directory) secrecy level if greater or equal than the process level (write up)
    2. Read request: Grant if target secrecy level if less or equal than the process level (read down)
    3. Read/write access: Target secrecy level is equal to the process level
  • Is MLS a Mandatory protection system?
    • Yes
    • Mandatory protection state:
      • Realization: Set of levels
      • Immutable
    • Labeling state:
      • Realization: Set level at login / at creation
      • Immutable
    • Transition state:
      • Realization: Only from low to high secrecy
      • Immutable

Multics Protection System

  • Protection state:
    • Access Control Lists
    • Ring brackets
    • Multilevel Security
  • Request:
    1. Check ACL if user has access
    2. Check MLS policy for secrecy levels
    3. Check ring bracket for access
  • Execution request:
    • MLS must permit reading
    • Protection domain transition possible
    • Process has higher privilege: Transition to lower-privileged ring
    • Process has lower privilege: Transition to higher-privileged ring if specified by call gate
  • Mandatory protection system:
    • Labeling state:
      • Not specified
      • New objects could get ACL/MLS by creator
    • Transition state:
      • Ring brackets (only for subjects)
      • Not specified for objects
  • Policies:
    • ACL: DAC
    • Ring brackets: DAC
    • MLS: MAC (loaded at boot time, immutable)

Vulnerability Analysis

  • Schell/Karger, 1974
  • Criteria:
    • Practicability of the reference monitor
    • Identify security enhancements
    • Determine scope of certification effort
  • Hardware
    • 1 Vulnerability/1 undocumented instruction
    • Address checking can be bypassed (fails complete mediation)
  • Software
    • Multics Master Mode: Permits running instructions in higher-privileged ring without a ring transition
    • Vulnerability in this Master Mode: Run privileged code with ring 0 permissions
  • Report
    • 54 kLOC with hundreds of programmers
    • Security mechanisms are ad-hoc (overlapping semantics)

Evaluation

Complete Mediation

  • Correct mediation:
    • Mediate on object references (segment level)
    • Weakness: Indirect addressing
    • Weakness: MLS labels are stored in parent directory (prevent TOCTTOU attack, directory contains segments from single directory class)
  • All resources:
    • Segment/object access is mediated at instruction level
    • Ring transitions in both directions
    • Weakness: Master mode executes code in higher ring without transitions
    • Argument validation via gatekeepers is not part of reference monitor
  • Verifiability of mediation:
    • Ring transitions and segment access are well-defined
    • Implementation is too complex for verification

Tamper-proofing

  • Protection of reference monitor and protection system
    • Supervisor implements reference monitor
    • Runs in ring 0
    • Ring bracket policy prevents writing to ring 0
    • Gatekeeper must ensure that inputs to ring 0 by untrusted parties are non-malicious
  • Protection of system TCB
    • Managed by brackets
    • TCB in rings 0-3
    • User programs in ring 4 or higher
    • Weakness: Ring bracket policy is discretionary
      • Can be changed with subject having modify access to a directory containing system segment

Verifiability

  • Correctness of the TCB

    • Too large for formal verification
    • Further research: Motivated development of security kernels

  • Protection system enforces system security goals

    1. Ensure that secrecy/integrity are enforced by the protection state
      • Secrecy by MLS
      • Integrity is hardened by the ring mechanism (read-down)
    2. Ensure that labeling state works correctly
      • Not specified
    3. Ensure that protection domain transitions protect secrecy/integrity
      • Secrecy given
      • Integrity problematic (transfer from low- to high-privileged ring)
    • Not an MPS