Transcript OS Slide Master

Information Flow
Language and System Level
Dennis Kafura – CS5204 – Operating Systems
1
Information Flow
Concept

Information flow




Long-term confinement of information to authorized
receivers
Controls how information moves among data
handlers and data storage units
Applied at language, system, or application levels
Examples:



Insure that “secret” data is only revealed to
individuals with a suitably high clearance level
Guarantee that information available to a process
cannot leak to the network
Certify that the outputs of a program only contain
information derived from specified inputs
Dennis Kafura – CS5204 – Operating Systems
2
Information Flow
System Example

Guarantee that the anti-virus (AV) scanner
cannot leak to the network any data found in its scan of user files

Possible leak methods





Send data directly to a network connection
Conspire with other processes (e.g, sendmail or httpd)
Subvert another process and use its network access to send data
Leave data in /tmp for other processes (e.g., the AV update
daemon) to send
Use other in/direct means of communication with the update
daemon
Dennis Kafura – CS5204 – Operating Systems
3
Information Flow
Denning Model

Flow model



where
N = {a,b,…} is a set of logical storage objects
P = {p,q,…} is a set of processes (active objects)
SC = {A.,B,…} is a set of security classes
Disjoint classes of information
 Each
is bound to a security class





Notation: a
may be static or dynamic (varies with content)
Class combining operator: a b
N
Flow relation:
iff information in class A is
allowed to flow into class B
Dennis Kafura – CS5204 – Operating Systems
4
Information Flow
Example Security Classes
(TS,[dip,mil])
top secret
secret
(TS,[dip])
(TS,[mil])
(S,[dip,mil])
confidential
public
(TS,[])
(S,[mil])
(S,[dip])
(S,[]}
.
Adapted from K. Rosen Discrete Mathematics and its Applications, 2003
Dennis Kafura – CS5204 – Operating Systems
5
Information Flow
Class Combining Operations
least upper bound
(TS,[dip,mil])
(TS,[dip])
(TS,[])
(TS,[mil])
(S,[dip,mil])
(S,[mil])
(S,[dip])
greatest lower bound
(S,[]}
Dennis Kafura – CS5204 – Operating Systems
6
Information Flow
Implicit/Explicit flows

In the statement: a=b+c;



There is explicit flow from b to a and from c to a
Here written as a b and ac
In the statement: if (a =0) {b = c;}


There is an explicit flow from c to b (bc)
There is an implicit flow from a to b (ba)


Because testing the value of b before and after the
statement can reveal the value of a
In the statement: if (c) {a=b+1;d=e+2;}


explicit flows from b to a and from e to d (ab, ed)
implicit flows from c to a and from c to d (ac, dc)
Dennis Kafura – CS5204 – Operating Systems
7
Information Flow
Security Requirements

Elementary statement





Sequence



S: b  a1,…,an
is secure if ba1 ,…, ban are secure
i.e., if a1  b ,…, an  b
i.e., if
is allowed
S = S1; S2
Is secure if both S1 and S2 are secure
Conditional



S = c: S1 ,…, Sn where Si updates bi
is secure if bi  c for i=1..n are secure
i.e. if
is allowed
Dennis Kafura – CS5204 – Operating Systems
8
⊕
Information Flow
Static Binding

Access Control




Process p can read from a only if ap
Process p can write to b only if pb
In general,
Data Mark Machine


Associate a security class with the program counter
For conditional statement c:S
Push p onto the stack
 Set p to p ⊕ c


For statement S that with ba1,…,an

Verify that
Dennis Kafura – CS5204 – Operating Systems
9
Information Flow
Static Binding

Compiler-based

For elementary statement S: f(a1,…,an)b
verify that
 Set S to b
is allowed


For sequence S = S1;S2


Set S to S1
S2
For conditional structure S = c: S1,…,Sm
Set S to S1 … Sm
 Verify that c  S

Dennis Kafura – CS5204 – Operating Systems
10
Information Flow
Dynamic Binding

A pure dynamic binding is not practical


Typical that some objects and most users have a
static security class
Dynamic Data Mark Machine




Difficult to account for implicit flows, so…
Compiler determines implicit flows and
Inserts additional instructions to update class
associated with program counter accordingly
Accounts for implicit flows even if flow not
executed
Dennis Kafura – CS5204 – Operating Systems
11
Information Flow
HiStar : System Level Flow Control

Basic ideas



Files and process are associated with a label whose
taint restricts the flow to lesser tainted components
Many categories of taint each owned by its creator
Selected components (e.g., wrap) can be given
untainting privileges
Dennis Kafura – CS5204 – Operating Systems
12
Information Flow
Labels

Structure





L = {c1l1, c2l2,…,cnln,ldefault}
Each ci is a category and li is the taint level in that
category
ldefault is the default level for unnamed categories
L(c) = li if c=ci for some i and ldefault otherwise
Levels
Dennis Kafura – CS5204 – Operating Systems
13
Information Flow
Information Flow

General rule:




information can flow from O1 to O2 only if O2 is at
least as tainted as O1 in every category
Information cannot flow from O1 to O2 if O1 is more
tainted in some category than O2
Example




Thread T with LT={1}, object O with LO={c3,1}
LT(c)=1 < 3=LO(c)
Flow is permitted from T to O (i.e., T can write to O)
No flow permitted from O to T (i.e., T cannot
read/observe O)
Dennis Kafura – CS5204 – Operating Systems
14
Information Flow
Example with Labels



User data labels set so that only owner can read (br3) and write (bw0)
Wrap program has ownership to read (br⋆) user data which it
delegates to scanner
Wrap creates category v to (1) prevent the scanner from modifying
User Data (since User Data has default level 1) and (2) prevent
scanner from communicating with network
Dennis Kafura – CS5204 – Operating Systems
15
Information Flow
Notation


Information flow
Treatment of level ⋆
 ⋆ should be high for reading, but low for writing


Notation provides two ownership symbols

Used as L⋆ and L⍟; for example if L={a⋆, b⍟, 1} then
L⍟ = {a⍟,b⍟,1} and L⋆ = {a⋆,b⋆,1}
Flow restriction:


T can read/observe O only if
T can write/modify O only if
Dennis Kafura – CS5204 – Operating Systems
16
Information Flow
Kernel Object Types

Object structure





objectID (unique, 61 bit)
label (threads also have clearance label)
quota
metadata (64 bytes)
flags
Segment: variable-length
byte array
Dennis Kafura – CS5204 – Operating Systems
17
Information Flow
Design Rationale

Kernel interface



The contents of object A can only affect object B if,
for every category c in which A is more tainted than
B, a thread owning c takes part in the process.
Provides end-to-end guarantee of which system
components can affect which others without need
to understand component details
Application structure


Organize applications so that key categories are
owned by small amounts of code
Bulk of the system is not security critical
Dennis Kafura – CS5204 – Operating Systems
18
Information Flow
Threads

Labels
normal label, LT
 clearance label, CT , giving an upper bound on its own label
and the label of objects it creates or grants storage to


Category creation
Creates a random previously unused category
 with LT(c)  ⋆ and CT(c)  3







Raise its own label to L provided
Change clearance label to C provided
Object with label L created by T have
Spawned threads T’ have labels
T can read label of T’ only if
Have a one-page local segment for scratch space
Dennis Kafura – CS5204 – Operating Systems
19
Information Flow
Containers





Hierarchical object allocation/deallocation
Creating object with label L in container D by thread
T requires
and
object in a container is referenced by a
<container ID, object ID> container entry
Automatic deallocation of objects unreachable from a
specially-designated root container
Quotas


Limits each objects storage usage
Container usage is its own space + quotas of all
contained objects
Dennis Kafura – CS5204 – Operating Systems
20
Information Flow
Address Spaces


Associated with a running thread
A collection of segments mapped via the list





VA  <S, offset, npages, flags>
S = <D,O>
offset, napges can specify subset of S
flags contain memory permission bits
Thread T can


modify address space A only if
use or observe A only if
Dennis Kafura – CS5204 – Operating Systems
21
Information Flow
Gates
[stack pointer]
LG, CG
State
address space
closure
arguments
T
Gate



entry point
Provide protected control transfer
Arguments and return values passed via thread local segment
May be used to transfer privileges
Dennis Kafura – CS5204 – Operating Systems
22
Information Flow
Invocation using Gates
[stack pointer]
LG, CG
State
address space
closure
arguments
T
(LR, CR)
LV
Gate

Invocation permitted when

Note: LV used only for verification at Gate
Dennis Kafura – CS5204 – Operating Systems
entry point
23
Information Flow


authentication
daemon
network
daemon
HiStar Implementation
uClibc
Linux sys call emulation
10,000 lines
HiStar Kernel
15,200 lines
Design for a simple interface to a small fully-trusted kernel
Typical Unix abstractions provided at the user level
Dennis Kafura – CS5204 – Operating Systems
24
Information Flow
Processes in HiStar

Note: a process is a user-level convention
Dennis Kafura – CS5204 – Operating Systems
25
Information Flow
User Authentication





No highly-trusted processes
User supplied (tailorable) authentication service
Directory Service: maps user names to authentication
service daemons (returns gate to user auth. service)
Authentication service: owns categories and grants them
to successful login clients
Complication: login does
not trust the authentication
service with the user’s
password!
Dennis Kafura – CS5204 – Operating Systems
26
Information Flow
User Authentication


Solution: a three step process
Key point: login and UAS collaborate
to create trusted check gate


Login creates check code in
segment marked immutable and
a gate with clearance to have
password
UAS can verify code to assure
safe execution with user
privileges
Dennis Kafura – CS5204 – Operating Systems
27
Information Flow
Performance: microbenchmarks
Dennis Kafura – CS5204 – Operating Systems
28
Information Flow
Performance: application-level
Dennis Kafura – CS5204 – Operating Systems
29