Simplifying Middlebox Modifications with NFV State Management
Paving the Way for NFV: Simplifying
Middlebox Modifications with StateAlyzr
Junaid Khalid
, Aaron Gember-Jacobson,
Roney Michael, Archie Abhashkumar, Aditya Akella
1
Middleboxes
Perform sophisticated operations
on network traffic
Firewall
Caching
proxy
Intrusion
detection
system (IDS)
Maintain state about
connections and hosts
2
Network Function Virtualization (NFV)
Reroute new connections
existing
3
state
NFV enables
elastic scaling
and
high availability
State created or updated by a middlebox applies to either a
single connection
or a
set of connections
State taxonomy
4
NFV state management -> middlebox
modification
Pre-flow state
Cross-flow state
Init state
Frameworks for transferring, or sharing live middlebox state
•
Require
modifications
or
annotation
to middlebox code
5
6
NFV state management -> middlebox
modification
Frameworks for transferring, or sharing live middlebox state
•
Require
modifications
or
annotation
to middlebox code
Why is modifying a middlebox hard?
Middleboxes are
complex
,
diverse
and have
a
variety of state
Missing a change
to some structure, class or function,
may violate
output equivalence.
Output equivalence:
for any input the aggregate output
of a dynamic set of instances should be equivalent to the
output produced by single instance.
7
StateAlyzr: program analysis to the rescue
A system that relies on
data
and
control-flow analysis
to
automatically identify
state objects that need explicit
handling
Leverage middlebox code structure to
improve
precision
without
compromising soundness
Soundness
means that the system
must not miss any
critical
types, storage locations, allocations, or uses of
state
Precision
means that the system identifies
the minimal
set of state
that requires special handling.
required for
output equivalence
required for
performant state transfers
8
Fault tolerance IDS
Per flow state
Multi flow state
All state
Config state
The
primary
sends
a copy of the state to
the
hot standby
after each packet
Primary
Hot standby
9
StateAlyzr
10
while (!done)
packet = receive()
send(packet)
write(log)
Packet processing loop
Packet processing procedures
foo()
process(packet)
process(packet)
Main
loopProcedure()
init()
raiseEvent()
Logical structure of
middlebox code
11
1. Per-/cross-flow
state identification
Variables
corresponding to per-/cross-flow
state must be
persistent
Persistent state can be stored in
1.
Global variables
2.
Static variables
3.
Local variables declared in loop proc.
4.
Formal Params of loop proc.
int
loopProcedure
(int *
threshold
)
{int
count = 0
;
while
(
1
)
{struct
pcap_pkthdr pcapHdr
;
char
*
pkt
=
pcap_next
(
extPcap
,
&
pcapHdr
);
.
.
12
Improve precision by considering variables which are
used
in
packet processing code
1. Per-/cross-flow
state identification
9
6
Per
Multi
All
Initialization
13
while (!done)
packet = receive()
send(packet)
write(log)
Packet processing loop
while (event = dequeue())
Event thread
Packet processing procedures
foo()
processIndirect(event)
processIndirect(event)
process(packet)
process(packet)
Main
loopProcedure()
init()
raiseEvent()
1. Per-/cross-flow
state identification
Computes a
forward slice
from packet recv function. Any procedure
appearing
in the slice
is considered as
packet processing procedure
.
14
s
t
r
u
c
t
p
k
t
H
d
r
*
p
k
t
=
r
e
c
v
(
e
x
t
P
c
a
p
)
;
s
r
c
_
i
p
=
p
k
t
-
>
i
p
_
s
r
c
_
a
d
d
r
;
p
a
c
k
e
t
_
c
o
u
n
t
+
+
;
i
n
d
e
x
=
s
r
c
_
i
p
+
o
f
f
s
e
t
Indirect
call
2. Identify updateable
state
Whether the state is updated while processing
the packet ?
•
Strawman approach
•
Identify top-level variable on the left-hand-side(LHS)
of assignment statement
Falls short due to
aliasing
int
*
index
=
&
tail
;
*
index
=
(*
index
+
1
)%
100
;
per-/cross-flow var
11
6
State
Per
Multi
All
Read-only
Updateable
StateAlyzr
employs flow-, context-, and field-
insensitive
pointer analysis
to
identify updateable
variables
15
3. Identify states’
flowspace dimensions
Identify a set of
packet header
fields
that delineate
the subset of traffic that relates to the state
Common access patterns
1.
Square brackets
entry = table[index];
2.
Pointer arithmetic
entry = head + offset;
3.
Iteration
struct
host
*
lookup
(
uint ip
)
{struct
host
*
curr
=
hosts
;
while
(
curr
!=
NULL
)
{if
(
curr
->
ip
==
ip
)
return
curr
;
curr
=
curr
->
next
;
}
}
Hashtable
Linked List
State
Per
Multi
All
Read-only
Updateable
[Src IP, Dst IP, Src Port, Dst_Port, proto]
[Src IP, Dst IP]
Program
chopping
to determine relevant
header
fields
16
s
t
r
u
c
t
p
k
t
H
d
r
*
p
k
t
=
r
e
c
v
(
e
x
t
P
c
a
p
)
;
s
r
c
_
i
p
=
p
k
t
-
>
i
p
_
s
r
c
_
a
d
d
r
;
p
a
c
k
e
t
_
c
o
u
n
t
+
+
;
i
n
d
e
x
=
s
r
c
_
i
p
+
o
f
f
s
e
t
e
n
t
r
y
=
h
o
s
t
_
m
a
p
[
i
n
d
e
x
]
StateAlyzr steps
1.
Identify Per-/Cross-flow state
2.
Identify Updateable State
3.
Identify States’ Flowspace Dimensions
4.
Output Impacting State
•
Identify the type of output (log or packet)
that updateable state affects
5.
Tracking Run-time Update
•
Insert statements to do run time monitoring
to track whether a variable is updated
6
State
Per
Multi
All
Read-only
Updateable
Per
Multi
All
Per
Multi
[Src IP, Dst IP, Src Port, Dst_Port, proto]
[Src IP, Dst IP]
Per
Multi
Per
Flowspace
17
Used CodeSurfer to implement StateAlyzr
•
CodeSurfer has built-in support for
•
Control flow graph construction
•
Flow and context-insensitive pointer analysis
•
Forward/backward slice and chop computation
Analyzed four open-source middleboxes
1.
PRADS – a monitoring middlebox
2.
Snort – an IDS
3.
HAProxy – a load balancing proxy
4.
OpenVPN – a VPN gateway
Implementation
18
•
Precision
•
Performance benefits at run time
19
Evaluation
Evaluation: effectiveness
Step 0
Step 1
Step 2
StateAlyzr
offers useful
improvements
in
precision
Theoretically
proved
the
soundness
of our algorithms
20
Highly available PRADS
Reduction in the state
transfer by
305x
21
•
StateAlyzr
reduced the manual effort of modifying
PRADS
from
120hrs
to
6 hrs
•
StateAlyzr
found a compound variable which we
missed
in
our prior modification.
Summary
•
Goal is to aid middlebox developers to identify state
objects that need explicit handling
•
Novel state characterization algorithms that adapt
standard program analysis tools
•
Ensure soundness and high precision
•
Ultimate goal is to fully automate the process
22
Paving the Way for NFV explores how Network Function Virtualization (NFV) simplifies middlebox modifications through state analysis and management. The process involves creating or updating state in middleboxes for various connections, utilizing frameworks for transferring live state, and addressing the complexities and challenges of modifying middleboxes. The article discusses the importance of maintaining state in middleboxes and provides insights into the difficulties encountered when modifying these systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Paving the Way for NFV: Simplifying Middlebox Modifications with StateAlyzr Junaid Khalid, Aaron Gember-Jacobson, Roney Michael, Archie Abhashkumar, Aditya Akella 1
Middleboxes Perform sophisticated operations on network traffic Intrusion detection system (IDS) Caching proxy Firewall Maintain state about connections and hosts 2
Network Function Virtualization (NFV) NFV enables elastic scaling and high availability state existing Reroute new connections 3
State taxonomy State created or updated by a middlebox applies to either a single connection or a set of connections Cross-conn state Per-conn state TcpAnalyzer Connection HttpAnalyzer ConnCount Connection TcpAnalyzer HttpAnalyzer All-conns state Statistics Input state Config + Sig 4
NFV state management -> middlebox modification Frameworks for transferring, or sharing live middlebox state Requiremodifications or annotation to middlebox code Required modifications: State allocation State access State merge Shared Library Shared Library Init state Split/Merge [NSDI 2013] Pre-flow state Cross-flow state 5
NFV state management -> middlebox modification Frameworks for transferring, or sharing live middlebox state Requiremodifications or annotation to middlebox code Framework State Allocation Merge State State Access Serialization Split/Merge [NSDI 2013] OpenNF [SIGCOMM 2014] FTMB [SIGCOMM 2015] Pico Rep. [SoCC 2013] Stateless NF[HotMiddlebox 2015] 6
Why is modifying a middlebox hard? Middleboxes are complex, diverse and havea variety of state Output equivalence: for any input the aggregate output of a dynamic set of instances should be equivalent to the output produced by single instance. MB LOC (C/C++) Classes/ Structs Level of pointers Number of Procedures PRADS 10K 40 4 297 OpenVPN 62K 194 2 2023 HAProxy 63K 191 8 2560 Bro IDS 97K 1798 - 3034 Squid 166K 875 - 2133 Snort IDS 275K 898 10 4617 Missing a change to some structure, class or function, may violateoutput equivalence. 7
StateAlyzr: program analysis to the rescue required for output equivalence A system that relies on data and control-flow analysis to automatically identify state objects that need explicit handling critical types, storage locations, allocations, or uses of state Soundness means that the system must not miss any source code StateAlyzr required for performant state transfers annotated code Leverage middlebox code structure to improve precision without compromising soundness set of state that requires special handling. Precision means that the system identifies the minimal 8
Fault tolerance IDS Per flow state Multi flow state All state Config state Primary Hot standby updated Theprimarysends a copy of the state to the hot standbyafter each packet ^ 9
StateAlyzr Output- Impacting State Updateable State Per-/Cross- Flow State All State 10
Logical structure of middlebox code Main init() loopProcedure() Packet processing loop while (!done) packet = receive() raiseEvent() process(packet) process(packet) foo() send(packet) write(log) Packet processing procedures 11
1. Per-/cross-flow state identification Stack origin Variables corresponding to per-/cross-flow state must be persistent x parameters Stack frame of main return address a b local variables Persistent state can be stored in 1. Global variables 2. Static variables 3. Local variables declared in loop proc. 4. Formal Params of loop proc. x parameters return address Stack frame of foo a b local variables x parameters Stack frame of loopProcedure return address a b local variables int loopProcedure(int *threshold){ int count = 0; while(1){ struct pcap_pkthdr pcapHdr; char *pkt = pcap_next(extPcap,&pcapHdr); . . 12
1. Per-/cross-flow state identification How to identify packet processing code? Per Multi All Improve precision by considering variables which are used in packet processing code Conf Init Initialization 9 6 13
1. Per-/cross-flow state identification How to identify packet processing code? Main Event thread while (event = dequeue()) init() loopProcedure() processIndirect(event) Packet processing loop while (!done) processIndirect(event) packet = receive() raiseEvent() Indirect call process(packet) process(packet) foo() send(packet) write(log) Packet processing procedures struct pktHdr *pkt = recv(extPcap); src_ip = pkt->ip_src_addr; Computes a forward slice from packet recv function. Any procedure appearing in the slice is considered as packet processing procedure. packet_count ++; index = src_ip + offset 14
2. Identify updateable state Per Multi State Whether the state is updated while processing the packet ? Strawman approach Identify top-level variable on the left-hand-side(LHS) of assignment statement All Conf Read-only Updateable per-/cross-flow var per-/cross-flow var in_port = pkt.src_port; StateAlyzr employs flow-, context-, and field- insensitivepointer analysis toidentify updateable int *index =&tail; *index =(*index + 1)%100; Falls short due to aliasing variables 11 6 15
3. Identify states flowspace dimensions Per Updateable Multi State Identify a set of packet header fields that delineate the subset of traffic that relates to the state All [Src IP, Dst IP, Src Port, Dst_Port, proto] Conf Read-only Program chopping to determine relevant header fields value key & value Hashtable Linked List [Src IP, Dst IP] Common access patterns 1. Square brackets entry = table[index]; 2. Pointer arithmetic entry = head + offset; 3. Iteration key struct host *lookup(uint ip){ struct host *curr = hosts; while(curr !=NULL){ if(curr->ip == ip) return curr; curr = curr->next; } } struct pktHdr *pkt = recv(extPcap); src_ip = pkt->ip_src_addr; packet_count ++; index = src_ip + offset entry = host_map[index] 16
State StateAlyzr steps All All Multi Multi Conf Conf Per Per Read-only Updateable 1. Identify Per-/Cross-flow state 2. Identify Updateable State 3. Identify States Flowspace Dimensions 4. Output Impacting State Identify the type of output (log or packet) that updateable state affects 5. Tracking Run-time Update Insert statements to do run time monitoring to track whether a variable is updated Flowspace Per Per Per [Src IP, Dst IP, Src Port, Dst_Port, proto] Multi Multi [Src IP, Dst IP] 6 17
Implementation Used CodeSurfer to implement StateAlyzr CodeSurfer has built-in support for Control flow graph construction Flow and context-insensitive pointer analysis Forward/backward slice and chop computation Analyzed four open-source middleboxes 1. PRADS a monitoring middlebox 2. Snort an IDS 3. HAProxy a load balancing proxy 4. OpenVPN a VPN gateway 18
Evaluation Precision Performance benefits at run time 19
Evaluation: effectiveness Step 1 Step 0 Step 2 MB All variables Persistent variables per-/cross- flow variables Updateable variables PRADS 1529 61 29 10 Snort IDS 18393 507 333 148 HAproxy 7876 272 176 115 OpenVPN 8704 156 131 106 StateAlyzr offers useful improvements in precision Theoretically proved the soundness of our algorithms 20
Highly available PRADS State transfer after each packet 10000 per pkt state transfer (KB) 1000 StateAlyzr reduced the manual effort of modifying PRADS from 120hrs to 6 hrs All persistant state 100 All updatable state StateAlyzr found a compound variable which we missed in our prior modification. Primary Hot standby 10 Flowspace 1 0 5 k 10 k 15 k 20 k 25 k 30 k 35 k packet number Reduction in the state transfer by 305x 21
Summary Goal is to aid middlebox developers to identify state objects that need explicit handling Novel state characterization algorithms that adapt standard program analysis tools Ensure soundness and high precision Ultimate goal is to fully automate the process 22
