Transcript Slides

HARDWARE SUPPORT FOR
ENFORCING INFORMATION
FLOW CONTROL ON
MANYCORE SYSTEMS
Sarah Bird
David McGrogan
PARALLEL COMPUTING & THE
FUTURE

Parallel designs are emerging
Scaling increases transistor counts
 Cannot extract any more ILP from programs


Security is Important
Mobile Devices
 Everything connected to the internet
 Open Source Code
 More personal data on the net

SECURITY
Current Systems have only a couple rings of
protection
 Adding features to an application compromises
the entire application

Plug-ins in Browsers
 Device Drivers in Operating Systems

PROJECT GOALS
Provide many levels of protection
 Reduce trusted code



Low Overhead in Area


Can’t afford to just tag everything
Low Overhead in Performance


More easily verified
Clients measure success in performance (security is
still hard to quantify)
Flexible System
RELATED WORK

Fine-Grained Protection
Mondrian Memory Protection (MIT)
 Legba (New South Wales)


Information Flow Control





HiStar (Stanford)
Asbestos (UCLA, MIT, Stanford)
Raksha (Stanford)
Loki (Stanford)
Dstar (Stanford)
INFORMATION FLOW CONTROL
Provide Labels on Processes, Data, Devices, etc.
 Restrict the flow of information from more secure
labels to less labels
 Can be done in hardware, software or both

HISTAR
Operating System
 Uses Asbestos Labels
 Enforces Information Flow Control in Software

MONDRIAN MEMORY PROTECTION
Compressed Protection
Tables in Memory
 Protection Check in
Parallel with Standard
Pipeline
 Protection Lookaside
Buffer functions caches
protection results
 Sidecars store protection
for addresses

PROJECT GOALS

Provide many levels of protection


Reduce trusted code


Compressed Protection Tables in Memory
Low Overhead in Performance


Enforce Protection in Hardware
Low Overhead in Area


HiStar Labels
Cache Protection Checks
Flexible System

Put Policies in Software
OUR DESIGN
Tags Per Cache
Line
Protection Check
Cache System
Pipeline
Protection
Check Cache
Network
Interface
Protection Table
Memory
RELABLING

Two Possible Solutions

Local Relabling


Takes advantage of locality
Global Relabling
Doesn’t need to be translated for different cpus
 Reduces network traffic


Final Solution:

Global Relabling with 16 bit tags
16 extra bits for read requests and responses across the
network
 16 extra bits per cache line in the cache system

PIPELINE
Thread 1 PC
Thread 2 PC
Thread 1 Tag
Thread 2 Tag
Tread ID
Data Tag
1
57
111
2
68
100
Protection Check
Commit
Protection
Check
MEMORY PROTECTION TABLE

Flat Table
More compressed
 Insert must slide down
everything
 Completely flexible
representation
 Binary Search to look up


Multilevel Table
Simple look up algorithm
 Less flexible
 Easy insert

METHODOLOGY



Simulate design using Simics with a simple
memory hierarchy
Insert delays in the memory hierarchy to
represent the delays for protection lookup
Run simple benchmarks to measure the worst
case overhead
OVERHEADS
16 bits/read request = 33.3% overhead
 16 bits/read response =1.56% overhead
 Memory Protection Table Lookup (3 extra
memory accesses)/memory read = 300% overhead
 Protection Cache Miss (1 memory access)
 Protection Check Miss = runs the software
handler (2000 cycles)
 Memory Overhead = ~6 %

FUTURE/IN PROGRESS WORK



Compare overheads with Original Histar System
on a single core
Develop a more realistic model of the protection
system in Simics
Analyze more realistic workloads for category
usage
USES OF A TAGGED SYSTEM

Debugging
Detecting wild writes
 Array bounds overflows
 Profiling


Security
Isolate Processes
 Protect Data
 Restrict the flow of information

CONCLUSIONS

Security is becoming increasingly important

Essential to reduce trusted code and isolate processes
from each other

Parallel is happening

Low over usage security systems are necessary
Information Flow Control is a viable option
 Hardware support is necessary for performance


Complex power may have negative power effects
REFERENCES









Nickolai Zeldovich, Silas Boyd-Wickizer, Eddie Kohler, and David Mazières. Making information flow
explicit in HiStar. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation,
Seattle, WA, November 2006
Nickolai Zeldovich, Silas Boyd-Wickizer, and David Mazières. Securing Distributed Systems with
Information Flow Control. In Proceedings of the 5th Symposium on Networked Systems Design and
Implementation, San Francisco, CA, April 2008
Hari Kannan, Nickolai Zeldovich, Michael Dalton, Christos Kozyrakis. Architectural Support for
Minimizing Trusted Code.
Emmett Witchel, Junghwan Rhee, Krste Asanović, "Mondrix: Memory Isolation for Linux using Mondriaan
Memory Protection", 20th ACM Symposium on Operating Systems Principles (SOSP-20) Brighton, UK,
October 2005.
Emmett Witchel, Josh Cates, and Krste Asanović, "Mondrian Memory Protection", Tenth International
Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-X) ,
San Jose, CA, October 2002.
Maxwell Krohn, Petros Efstathopoulos, Cliff Frey, Frans Kaashoek, Eddie Kohler, David Mazières, Robert
Morris, Michelle Osborne, Steve VanDeBogart and David Ziegler. Make Least Privilege a Right (Not a
Privilege). Proceedings of the 10th Workshop on Hot Topics in Operating Systems, Santa Fe, NM, June
2005.
Petros Efstathopoulos, Maxwell Krohn, Steve VanDeBogart, Cliff Frey, David Ziegler, Eddie Kohler, David
Mazières, Frans Kaashoek and Robert Morris. Labels and Event Processes in the Asbestos Operating
System. Proceedings of the 20th Symposium on Operating Systems Principles, Brighton, United Kingdom,
October 2005.
Michael Dalton, Hari Kannan, Christos Kozyrakis, Raksha: A Flexible Information Flow Architecture for
Software Security. Proceedings of the 34th Intl. Symposium on Computer Architecture (ISCA), San Diego,
CA, June 2007.
Adam Wiggins, Simon Winwood, Harvey Tuch and Gernot Hesier, Legba: Fast Hardware Support for FineGrained Protection.