Transcript Design and Implementation of a Flow

Towards a Flow-level
Network Security System
Tim Hinrichs
University of Chicago
Local Area Networks
Network Policy Examples
“Every wireless guest user must send HTTP
requests through an HTTP proxy.”
“No phone can communicate with any private
computer.”
“Superusers have no communication
restrictions.”
“Laptops cannot receive incoming connections.”
Traditional Network Management
Today networks are managed by low-level
configuration of independent components,
e.g. firewalls, proxies, routers.
Dependent on underlying network.
Examples
– Block user access by adding an ACL entry.
Requires knowing user’s IP address.
– Force guests port 80 traffic through a proxy.
Requires knowing the network topology and the
location of each guest.
Example
10.0.0.1
Src IP
10.0.0.1
Port
80
Forward
10.0.0.25
10.0.0.25
Management by
Component Configuration
Benefits
Drawbacks
• Efficiency of
operation.
• Inefficiencies of
maintenance.
• Administrative
fiefdoms enjoy
autonomy.
• Inconsistencies are
likely.
Network Operating Systems
Provide a programmatic interface to observe
and control the entire network.
Applications perform the actual management
by making system calls.
Two paradigm shifts
– Logical Centralization: Applications are written
as if network were present on single machine.
– Abstraction: Applications are written in terms of
abstract entities, e.g. users and hosts.
Example
10.0.0.1
Application:
if (packet p originated from guest user &&
port
Src IP
Port is 80)
Forward
then m80
:= findproxy();
10.0.0.1
10.0.0.25
forward p to m on port 80
10.0.0.25
Management by
Network Operating System
Potential Benefits
Potential Drawbacks
• Efficiency of
maintenance.
• Inefficiencies of
operation.
• Inconsistencies are
less likely.
• Loss of autonomy.
Network Security
An authorization policy is implemented as an
application in a network operating system.
The same is true for an authentication policy.
Focus for today: a language for expressing
authorization policies over networks.
NOX:
A Network Operating System
Natasha Gude
Teemu Koponen
Justin Pettit
Ben Pfaff
Martìn Casado
Nick McKeown
Scott Shenker
Nicira Networks
HIIT
Nicira Networks
Nicira Networks
Nicira Networks
Stanford University
UC Berkeley
NOX Architecture
App 1
NOX Controller
Network
View
App 2
App 3
PC
OF Switch
OF Switch
Off-the-shelf
hosts
Wireless
OF Switch
Switch Abstraction
OpenFlow switch abstraction is a flow table.
Each flow table entry takes the form
<header : counters, actions>
Switch executes the actions corresponding to
the highest-priority matching header in
table.
Operation
Switch
1. Packet p reaches switch.
2. If p matches a flow entry
Then apply the corresponding actions
Else forward to the controller
Controller
1. Packet p reaches controller.
2. Update view of network state.
3. Decide the route for the packet and inform
the relevant switches of that route.
Application I/O
Observation granularity:
–
–
–
–
–
Switch-level topology
Locations of users, hosts, middleboxes
Services offered, e.g. HTTP or NFS
Bindings between names and addresses
NOT the entire packet/flow state
Control granularity: flows.
Decisions about one packet are applied to all
subsequent packets in the flow.
Programmatic Interface: Events
NOX exposes network events to applications
–
–
–
–
–
Switch join
Switch leave
User authenticated
Flow initiated
…
Applications consist of code fragments that
respond to these events.
Example: Access Control
function handle_flow_initialize(packet)
usersrc = nox.resolve_user_src(packet)
hostsrc = nox.resolve_host_src(packet)
usertgt = nox.resolve_user_tgt(packet)
hosttgt = nox.resolve_host_tgt(packet)
prot = nox.resolve_ap_prot(packet)
if deny(usersrc,hostsrc,usertgt,hosttgt,prot) then
nox.drop(packet)
else nox.installpath(p, nox.computepath(p))
function deny(usersrc, hostsrc, usertgt, hosttgt, prot)
…
Scalability
Events (per second)
– Packet arrivals (106): handled by switches
– Flow initiations (105) : handled by controller
– View change (10): handled by controller
Controller
– Can be replicated.
– Only global data structure: view.
– One currently handles 105 flow initiations per
second.
Related Work
4D project (2005): provide global view of network via
centralized controller.
SANE/Ethane (2007): extends 4D by adding
users/nodes to the namespace and captures flowinitiation.
For citations, see
NOX (2008): extends SANE/Ethane
– Scaling for large networks.
[Gude2008].
– General programmatic control of network.
Maestro (2008): “network OS” focused on controlling
interactions between applications.
Industry: deep-packet inspection, firewalls, etc. are
appliances--can be leveraged by NOX. Also,
functionality similar to Ethane.
FSL:
A Flow-based Security Language
Tim Hinrichs
Natasha Gude
Martìn Casado
John Mitchell
Scott Shenker
University of Chicago
Nicira Networks
Nicira Networks
Stanford University
UC Berkeley
NOX Operation
NOX Operation
SECURITY
POLICY
NOX Operation
FSL
FSL: Flow Security Language [Hinrichs2009]
Balances the desires to make expressing policies
natural and implementing policies efficient.
•Protocol
•User source
•Host source
•Access point source
•User target
•Host target
•Access point target
Features
•
•
•
•
•
•
Distributed policy authorship
External references
Conflicts, conflict detection, conflict resolution
Incremental policy authorship via priorities
Analyzability
High Performance: 104 queries/second
Layered language:
Prioritization
Conflict Resolution
Keywords
Logic
Data
Datalog with Attachments
Syntax
h :- b1,…,bn,c1,…,cm
•
•
•
•
h must exist.
Every variable in the body must appear in h.
No external reference occurs in h.
Nonrecursive sentence sets.
Semantics
– Statement order is irrelevant.
– Every sentence set is satisfied by exactly one model.
Keyword: allow
“Superusers have no communication
restrictions.”
allow(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot)
superuser(Usrc)
superuser(bob)
superuser(alice)
:-
Keyword: deny
“No phone can communicate with any private
computer.”
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :phone(Hsrc) , private(Htgt)
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :private(Hsrc) , phone(Htgt)
private(X) :- laptop(X)
private(X) :- desktop(X)
Keyword: visit
“Every wireless guest user must send HTTP
requests through a proxy.”
visit(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot,httpproxy)
guest(Usrc) , wireless(Asrc) , Prot=http
:-
Current Keyword List
• allow: allow the flow
• deny: deny the flow
• visit: force the flow to pass through an intermediary
• avoid: forbid the flow from passing through an
intermediary
• ratelimit: limit on Mb/second
Negation
“Every user except a guest can ssh into any
server.”
allow(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,ssh)
guest(Usrc) , server(Htgt)
:-
Traditional Security Mechanisms
NAT: disable incoming connections for laptops
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :laptop(Htgt)
VLAN: isolate machines a,b,c
vlan(a), vlan(b), vlan(c)
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :vlan(Hsrc),
vlan(Htgt)
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :-
vlan(Hsrc), vlan(Htgt)
Conflicts
deny
avoid
visit
allow
ratelimit
deny
avoid
visit
allow
ratelimit
Conflicts are vital in collaborative settings
because they allow administrators to express
their true intentions.
Authorization systems cannot enforce
conflicting security policies.
FSL Usage Overview
Policy
1
…
Policy
n
Combined
Policy
Analysis
Engine
Authorization
System
Conflict Resolution
• No conflicts: conflicts are errors.
• Most restrictive: choose instructions that give users
the least rights.
• Most permissive: choose policy instructions that
give users the most rights.
• Cancellation: a flow with conflicting constraints has
no constraints.
Conflict Resolution as a Tool
Fixing the conflict resolution mechanism allows
certain policies to be expressed very simply.
Example (Open Policy): allow everything not
explicitly denied.
allow(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot)
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :phone(Hsrc) , private(Htgt)
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :private(Hsrc) , phone(Htgt)
Incremental Policy Authoring
To tighten a FSL policy, one needs only
to add statements to it.
The conflict resolution strategy ensures
that the most restrictive constraints are
used.
To relax a FSL policy, it is therefore
insufficient to simply add statements.
Prioritized Policies
Borrow a mechanism from Cascading Style
Sheets (CSS).
To relax security incrementally, FSL allows one
policy to be overridden by another policy.
P1 < P 2
A request constrained by P2 is only constrained
by P2.
Example
P1
allow(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :- superuser(Usrc)
superuser(bob)
superuser(alice)
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :- phone(Hsrc) , private(Htgt)
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :- private(Hsrc) , phone(Htgt)
private(X) :- laptop(X)
private(X) :- desktop(X)
visit(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot,httpproxy) :- guest(Usrc) , wireless(Asrc) , Prot=http
allow(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,ssh) :-
guest(Usrc) , server(Htgt)
P2
allow(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot)  Usrc=ceo
Cascaded Policy Combination
Policy
1,m1
Policy
1,2
Policy
1,1
Policy
n,mn
…
Combined
Policy
Policy
n,2
Policy
n,1
Cascaded Policy Combination
1. Flatten cascades.
2. Combine results.
Policy
1
…
Combined
Policy
Policy
n
Features
•
•
•
•
•
•
Distributed policy authorship
External references
Conflict detection/resolution
Incremental policy authorship via priorities
Analyzability
High Performance: 104 queries/second
Layered language:
Prioritization
Conflict Resolution
Keywords
Logic
Data
Analysis Algorithms
Flattened Cascade: a policy cascade expressed as a
flat policy.
Group Normal Form: every rule body consists only of
external references (and =).
Conflict Conditions: conditions on external references
under which there will be a conflict.
Conflict-free Normal Form: equivalent policy (under
conflict resolution) without conflicts.
Performance Example
“No phone can communicate with any private
computer.”
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :phone(Hsrc) , private(Htgt)
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :private(Hsrc) , phone(Htgt)
private(X) :- laptop(X)
private(X) :- desktop(X)
Performance Example Compiled
bool deny (Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) {
return (phone(Hsrc) && private(Htgt)) ||
(private(Hsrc) && phone(Htgt));
}
bool private(X) {
return laptop(X) || desktop(X);
}
Assume the existence of functions for phone, laptop,
desktop.
FSL Complexity
Query processing is PSPACE-complete in the size of
the policy.
If the number of arguments are bounded by a
constant, query processing takes polynomial time
in the size of the policy.
If the tallest possible call stack is 1 (ignoring external
references), then query processing takes linear
time in the size of the policy.
Implementation Tests
Flows/s
0 rules
103,699
Mem
(MB)
0
Rule
Matches
0
100 rules
100,942
1
2
500 rules
85,373
1
4
1,000 rules
76,336
2
10
5,000 rules
54,416
9
30
10,000 rules
46,956
38
52
Deployment Experiences
• On a small internal network (about 50 host),
NOX has been in use over a year, and FSL
has been in use for 10 months.
• We are preparing for two larger deployments
(of hundreds and thousands of hosts).
• So far, policies are expressed over just a few
classes of objects.
Thus, we expect policies to grow slowly with the
number of principals.
Ongoing Work
Currently, each flow initiation requires
contacting a central controller.
The route for that flow is cached at the router.
Working to generalize this caching scheme.
Each trip to the central controller caches more than
just the route for one flow.
Related Work Comparison
Limitations
• Not using FOL, Modal logic, Linear logic
• No existential variables
• No recursion
For citations, see
[Hinrichs2009].
• Fixed conflict resolution scheme
• No delegation
• No history/future-dependent policies
• Centralized enforcement
• Limited metalevel operations
Novel language features
• Access control decisions are constraints.
• Conflict resolution produces constraint set
References
[Gude2008] N. Gude, et. al. NOX: Towards an Operating
System for Networks. Computer Communications Review
2008.
[Hinrichs2009] T. Hinrichs, et. al. Design and Implementation
of a Flow-based Security Language. Under review.
Available upon request.
Questions
App 1
NOX Controller
Network
View
App 2
App 3
PC
OF Switch
OF Switch
Off-the-shelf
hosts
Wireless
OF Switch
Backup
NOX Security Issues
• Switch communication with Controller.
Preconfigure switches with Controller
credentials.
• Hosts, users must authenticate.
• Spoofing Ethernet addresses. Options: (1)
Physically connect one switch port to one
host. (2) Use link-level encryption.
Examples Combined
allow(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :- superuser(Usrc)
superuser(bob)
superuser(alice)
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :- phone(Hsrc) , private(Htgt)
deny(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot) :- private(Hsrc) , phone(Htgt)
private(X) :- laptop(X)
private(X) :- desktop(X)
visit(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,Prot,httpproxy) :- guest(Usrc) ,
wireless(Asrc) , Prot=http
allow(Usrc,Hsrc,Asrc,Utgt,Htgt,Atgt,ssh) :-
guest(Usrc) , server(Htgt)
Statement order is irrelevant.
Cascade Properties
• Every Cascade can be expressed as a non-cascaded
policy.
P1: A :- B
P2: C :- D
P1 < P2:
A :- B , D
C :- D
• Flattening a cascade requires time linear in the size
of the cascade:
O(|P1 < … < Pn|)