Transcript Innovative Technologies from the MIND Lab

Wireless Technologies
Ashok K. Agrawala
December 16, 2002
Today…
•
•
•
•
•
Wireless Traffic Characterization/Sniffing
AP Monitoring
SIM-based Wireless Security
Sensor Networks/Adhoc Networking
RSSI based Location Determination
Wireless Traffic Characterization
Understanding Wireless Traffic
Characteristics
• University UMDnet
– >1000 Aps
• >300 Now
– Large User population
• Monitoring
– Wired Net
– AP
– Over the Air (Sniffing)
Wireless Traffic Monitoring
• Easy to setup: no interaction with existing
infrastructure
• Provide local and global status of network
nodes at the same time
• Provide good traces of 802.11 link-level
operations
Captured Information
• Physical layer (Prism2 monitor header)
– RSSI (Received Signal Strength Indication, SQ (Signal
Quality), Signal strength and Noise (in dBm)
• 802.11 Link layer
– Protocol version, frame type(management, control and data),
Duration for NAV(Network Allocation Vector) calculation,
BSS Id, Source and Destination address, fragment, sequence
numbers
• TCP/IP, application layer info also available
802.11 Basic Architecture
Channel-6
WAN
Channel-1
Access
Point
DS (Distribution System)
Ethernet LAN
Access
Point
Sniffing Each Access Point
Channel-6
WAN
Ch. 6
Sniffer
Channel-1
Access
Point
Ch. 1
Sniffer
DS (Distribution System)
Ethernet LAN
Access
Point
Wireless Monitoring –
Hidden Terminal Problem, Losses
• Hidden Terminal Problem
– Difficult for sniffers to detect all the wireless stations.
• Various losses are observed in sniffers
– Frame loss
– AP loss : Some APs are not correctly detected by some
cards.
– Type loss : Control/Management types are not correctly
detected by some cards.
• Loss variability
– Due to signal strength variability and card variability
Sniffing n APs with m sniffers
Hidden
Terminals
Channel-6
WAN
Channel-6
Access
Point
Ch. 6
Sniffer
DS (Distribution System)
Ethernet LAN
Access
Point
Challenges of Wireless Monitoring –
Placement of Sniffers
• Proper placement of sniffers can improve
terminal detection ability and reduce
various losses in sniffers.
• Where to place sniffers?
– Too close to APs: incur signal saturations.
– Too far from APs: cause hidden terminals.
• How many sniffers to place?
Study to date
• Extensive passive observations on loss and
loss variability
– Observed hidden terminal problems
– Observed frame loss, AP loss and Type loss
– Observed loss varies from 0% to 100%
• Active end-to-end delay experiment
– Causes of end-to-end delay in wireless network
Methodology
• Location: A.V. Williams Bldg, UMD.
– 3 different WLANs (umd, cswireless, nist)
– 58 Access Points: 29 Cisco (umd), 12 Lucent
(cswireless), 17 Prism2-based (nist)
• Sniffers
–
–
–
–
Linux OS 2.4.19
Wireless card driver: orinoco_cs
Capturing tool: libpcap 0.7, ethereal 0.9.6
Wireless cards used: Lucent Orinoco, Linksys, DLink etc.
Passive Observations:
Hidden Terminals and Losses
• Hidden terminals: vary depending on cards used in
sniffers and sniffer locations.
• Loss in sniffers
– Frame losses are calculated from 802.11 sequence
numbers.
– “From-AP” and “To-AP” losses are noted separately.
• Findings:
– More To-AP losses are observed than From-AP.
– Most of To-AP losses are caused by a small number of
wireless stations.
– Linksys cards cannot detect some APs correctly.
– Lucent cards cannot detect ACK/RTS/CTS frames.
Passive Sniffing on Ch. 11 with 6 Sniffers
(4th floor, A.V. Williams Bldg)
APs
Ch.1
Ch.1
Ch.1
umd
cswireless
nist
L
Lucent
Sniffers
S
Z
Hidden terminals are observed by 6 sniffers.
Detected sets of wireless stations vary depending
on sniffer locations and the cards used.
LinkSys ZoomAir
L1 Z1
L3
S3
L2 Z2
Ch.11 Ch.11
sniffer@locatoin
Lucent@4449 ZoomAir@4449 Lucent@4122 ZoomAir@4122 Lucent@4149 Linksys@4149
Client MAC address # distinct
# distinct
# distinct
# distinct
# distinct
# distinct
ed:76
52221
09:d9
24777
14414
15862
3
d2:b6
5849
12
98:1f
1731
70:d8
266
9b:71
200940
5
d4:e0
39310
ad:fd
173860
202
164
1f:e7
37321
761
111
17
15:e7
10150
1796
31
42
e0:17
23539
51
12030
25:19
6934
1
3d:b0
33543
14
69:b8
8443
5
d4:eb
8175
48
15:a8
12244
8b:b9
2200
5
58:6b
293
8c:c9
3331
ab:db
266
1
36:a0
7490
9412
18:29
60090
66281
73:fb
2640
3390
9a:63
1254
1927
bd:c0
1569
1629
0c:a7
2014
1f:37
3042
Other rows are omitted
Total # distinct frames
82847
16423
314209
8667
78494
94946
# detected clients
42
22
50
31
30
33
Hidden terminals are observed by 6 sniffers. Detected set of wireless
stations varies depending on sniffer locations and the cards used.
Linksys
Lucent
Loss of AP[2e:36] frames (from sequence #)
From AP
To AP
# distinct # retrans # miss %loss # distinct # retrans # miss
%loss
2426901 102408
5214
0.21
30155
10109
2043
6.35
2402377
93297
11755
0.49
32277
9512
155854
82.84
Frame losses calculated by sequence numbers. To-AP frame loss is more
than From-AP loss.
Client MAC Address # distinct
06:f7
12
69:b8
1
e1:03
20484
71:f4
6427
(Other clients omitted)
Total
Without 06:f7, 69:b8
30155
30142
Linksys
# retrans # miss
0
51
0
0
6674
1107
108
234
10109
10109
2043
1992
TO AP Client Distribution
Lucent
%loss # distinct # retrans # miss
%loss
80.95
2959
187
150250
98.07
0.00
166
56
2462
93.68
5.13
19281
5800
2430
11.19
3.51
6379
3132
78
1.21
6.35
6.20
32277
29152
9512
9269
Majority of losses are caused by a small number of clients.
155854
3142
82.84
9.73
Linksys (# AP's = 11) Lucent (# AP's = 18)
AP BSS id
# Frames Percentage # Frames Percentage
AP1 (umd, Ch.11)
2583659
84.47% 2550568
41.26%
AP2 (nist, Ch. 6)
454630
14.86%
6391
0.10%
AP3 (nist, Ch. 11)
18579
0.61% 1172182
18.96%
AP4 (unknown)
573
0.02%
568
0.01%
AP5 (umd)
369
0.01%
167224
2.70%
AP6 (umd)
46
0.00%
91
0.00%
AP7 (umd, Ch. 11)
0
1320012
21.35%
AP8 (nist, Ch. 11)
11
0.00%
895638
14.49%
AP9 (umd)
1
0.00%
55555
0.90%
(Other AP's omitted)
Total
3058516
100%
6182077
100.00%
Linksys and Lucent sniffers are set to Ch. 11. Linksys sniffer has AP losses
on AP3 and AP7. Linksys detects AP2, whose channel is 6.
Data
Beacon
Acknowledgement
RTS
CTS
Probe
Power-Save
Reassociation
Total
Linksys
Lucent
# Frames Percentage # Frames Percentage
888082
25.94% 1318942
21.33%
2117923
61.86% 4712323
76.23%
323674
9.45%
0
34729
1.01%
0
6734
0.20%
0
52447
1.53%
150796
2.44%
44
0.00%
0
20
0.00%
16
0.00%
3423653
100.00%
6182077
100.00%
Lucent shows Type loss on control frames (ACK, RTS, CTS and PowerSave).
Passive Observation:
Loss Variability
• Findings:
– Frame loss varies upto 100% during 4-day
passive experiments
– “To-AP” shows more loss variability than
“From-AP”
– Card/AP compatibility may affect AP loss
variability.
Figure 1. Loss percentage varies from 0% to 100% during 4-day
experiment. To-AP loss shows more variability than From-AP loss.
AP
From AP
To AP
(essid, Ch.)
Card
# distinct # loss %loss # distinct # loss %loss
AP1
Linksys
4675
2 0.04
210
16 7.08
(umd, 6)
Lucent
4656
17 0.36
223
4 1.76
AP2
Linksys
3109
96 3.00
0
0
(nist, 6)
Lucent
3153
51 1.59
0
0
AP3
Linksys
4737
110 2.27
249
114 31.40
(umd, 6)
Lucent
4701
144 2.97
381
79 17.17
AP4
Linksys
694 2414 77.67
0
0
(cswireless, 6) Lucent
2840
300 9.55
0
0
AP5
Linksys
3085
78 2.47
0
0
(nist, 1)
Lucent
1
0 0.00
0
0
AP6
Linksys
2640
509 16.16
0
0
(nist, 6)
Lucent
2938
209 6.64
0
0
Frame loss varies over the card and the associated AP: All the traffics are
measured in the same experiment. Card variability affects frame loss.
Diagnosis on End-to-end Delay
• Active experiment set-up
–
–
–
–
Use NetDyn on wireless network
Source, echo and sink timestamps are available
Source and sink machines are the same
Sniffers are in between source(sink) and AP
• Objective: infer the causes of high RTT
end-to-end delays, using the sniffer traces.
NetDyn
Structure of NetDyn
Source
STS
SSN
UDP
STS
SSN
ETS
ESN
UDP
Echo
Sink
STS
SSN
ETS
ESN
SiTS
TCP
STS: Source Timestamp
ETS: Echo Timestamp
SiTS: Sink Timestamp
SSN: Source Sequence Number
ESN: Echo Sequence Number
Logger
Host 1
NetDyn Tool
Host 2
Fine-grained RTT measurements
Expose fine-grain characteristics of Networks
Avg loss of both F/B paths < 3%
Avg loss of both F/B paths > 10%
NetDyn Packet Loss
(Average)
90°
112.5°
135°
67.5°
45°
Problem case 1
X
X
22.5°
X
157.5°
X
X
X
X
S
S
180°
S
0°
Ch.11
Problem case 2
96
84
72 60 48 36
24 12
0
12
24 36
48 60
72 84
96
Effect of Weak Signal Strength
• Problem Case 1:RTT(Roundtrip Time)
delay of 1 second and 57% packet loss.
• Weak signal strength causes retransmissions
between source and the AP.
• Delays occur in the sending buffer in
source.
High RTT delays up to 0.8 seconds and 57% packet loss.
Source, echo, sink timestamps (by NetDyn), From-AP, To-AP timestamps
(by sniffers). Delays exist between source and echo every 0.5 second
periodically. No high delays exist on wireless path.
Signal strength is consistently low, which incurs many retransmissions
between source and the AP.
Effect of Signal Strength and
Card Variability
• Problem Case 2: RTT delay of 2.2 seconds and
75% packet loss.
• Signal strength variability makes the AP shift the
sending data rate (at 11/5.5/2 mbps adaptively).
• Source wireless card fails to receive traffic at
lower data rates (due to card implementation
variability).
• Delays occur on wireless “From-AP” path due to
many retransmissions at lower data rates.
High RTT delays up to 2.3 seconds and 75% packet loss.
Source, echo, sink timestamps. Delays exist between echo and sink.
To-AP/From-AP traffics are captured by the sniffers. Delays may reside on
wired echo-AP path or wireless AP-sink path.
RTS/CTS data rates captured by sniffers. AP tries to synchronize its data
rate with source consistently.
AP varies data rates at 11, 5.5 and 2 Mbps (From-AP data rate, graph on
top). Source but cannot synchronize with the AP, send/receive packets only
at 11Mbps (To-AP data rate, graph at bottom).
High variability in signal strength is observed by sniffers, which causes AP
to shift data rate adaptively.
Where are we?
• Sniffing in wireless environment is much
more difficult than we thought
• Using multiple sniffers we can get a good
estimate of wireless traffic
Access Point Monitor
(APM)
Kevin Kamel
Jaime Lafleur-Vetter
Why APM?
• Currently Available AP Monitoring Tools
– Provided By The Manufacturer
• Closed source
• Unsupported
– Functionality
• Limited feature set
• Not extendable
• Difficult to use
• More robust solution needed
Introducing APM
• AP Platform
– Soekris NET4521 Board
•
•
•
•
486 133mhz AMD (x86)
64MB onboard RAM
64MB compact flash
Prism2 PCMCIA card
– In Host AP mode
– External Antenna
• RJ-45 Port for LAN/WAN
connectivity
– Operating System
• Customized OpenBSD 3.2
APM (Continued)
• AP Patch
– Extends open source AP software
– Sends event messages to kernel device
– System daemon
• Reads and broadcasts events over the wire.
• Listens for Admin requests
• Sets daemon and AP configuration settings
• Monitor Client
–
–
–
–
.NET Windows GUI
Listens for broadcasted events from the AP
Displays event information graphically
Sends configuration information
Current Features
• Multiple simultaneous monitor applications
that can see multiple APs.
• Station Monitoring
– Current state (i.e. Auth, Assoc)
– Event history
• AP Diagnostics
– Interface counters
– Logger
Feature Walkthrough:
Initialized View
Feature Walkthrough:
Initialized Statistics
Feature Walkthrough:
Clients Are Logged In
Feature Walkthrough:
Client Disassociates
Feature Walkthrough:
Client times out
Feature Walkthrough:
AP Interface Statistics
Features Under Development
• Administrative Control
– Settings: TX Rate, SSID, MTU, Channel, MAC
– Control: Shutdown, Restart
– Access: Wireless client ACL support
• On Board Packet Monitoring
– Obsoletes traditional wireless packet capture
– Traffic log
• User Friendly Addressing
– Alias MAC addresses
SIM-based Wireless Security
KoolSpan Approach
The Real Problem…
Enterprise Network
1. We need to screen users at
the Access Point
2. We need to make sure
nobody other than
legitimate users get onto
the wired network
3. We need to guarantee data
sent across the WIRELESS
segment is safe
The point is: the problem exists ONLY between the AP and the client
Koolspan Solution
A simple, cost-effective solution
Recognize this is the problem
• Solution:
– Provide a lock at the Access Point
– Provide a network access KEY for the
client
• Result:
– Nobody gets past Access Point
without a valid key
How do we do this?
Simply and cost-effectively
• “Padlock”
– USB, Serial or Ethernet-based adapter
that secures the Access Point (can only be
unlocked with a valid client network key
• “Key Ring”
– USB adapter that can hold keys to
numerous networks
Koolspan IQ Key
Physical Identification Adapter
SIM Chip
• Tamper Resistant Physical Token
• Secure Token
• On-Chip “Crypto Engine”
 2,048 bit keys possible
 Cryptoflex processor uses DES, Triple-DES and
RSA algorithms
 Can rotate WEP keys fast enough to make WEP
secure AS IS!
• Provides




complete authentication
security
secure storage
automatic connections
SmartWiFi™• Plug It In – You’re Connected
USB-adapter
– Solves security problem
– Solves authentication problem
– Automatic Network Connection
• Advantages
– No new servers, no new headaches
– No scalability issues
– Works equally well at home and in the enterprise
• Best of all: Makes Wi-Fi easy to use!
SmartWiFi
ID Token
How does it work?
Bi-directional Authentication
Wi-Fi
SIM
1.
2.
Koolspan
Access Point
(6) R2e
3.
4.
5.
SIM
Wi-Fi
(2) R1e
Client NIC
Secret “Network Key” pre-stored in SIM
At Access Point and users PCs
6.
7.
8.
Client SIM generates random
number R1 and encrypts it with its
secret Key (NK_UIDs)
Client SIM sends client serial
number and encrypted R1 to AP
(Packet #1)
AP SIM uses Client SIM Serial
Number to look up Client SIMs
secret key.
AP SIM decrypts R1 with using
client’s secret key
AP now generates R2 and encrypts
it with Client’s secret key
AP sends Packet #2 back to Client.
Client SIM decrypts R2 from AP
with its secret key
Both AP and Client now use R1 +
R2 to generate new 256-bit Session
Key used for all further AES
transmissions.
Benefits
• Very simple solution
• No Wi-Fi settings necessary
• Only two packets are exchanged resulting in bi-directional
authentication
• No online server involved
• Very fast authentication (only 2 packets exchanged, no remote
server)
• No issues of scale
• Authentication takes place at edge of the network.
• Secret Keys pre-stored in SIMs at both ends NEVER leave SIMtherefore never exposed.
• Software impact on AP is minimal, easy retrofit
• SIM token carries user credentials in convenient portable device
Secret “Network Key” pre-stored in SIM
At Access Point and users PCs
Koolspan 802.11 Technology
•
•
•
•
makes Wi-Fi easy
solves Wi-Fi security problems
market flexibility
provides ‘frictionless’
portability
™
Adhoc Networking
Energy-Efficient Sensor Networks
• Energy is a constrained resource for wireless
environments
• Objective: Compute a low energy end-to-end path for
reliable communication in multi-hop wireless
networks
• Technique: Avoid links with high error rates or large
distance
• Studied effects of node mobility and wireless noise
Representative Results
• Grid topology of 49
nodes
• 4 traffic sources
• Between corner
nodes
• UDP and TCP sources
Representative Results: Grid Topology
Energy
Throughput
• UDP flows, fixed noise
• Proposed scheme performs better than existing
techniques
Results Summary
• Significant improvement in energy costs
and throughput if link characteristics are
modeled in computing paths
• Link properties affected by mobility
– Better models needed for link dynamics under
mobility
Localization Technologies
• Based on Signal Intensity
– The intensity of the signal from access points is used
to determine location.
– Our current results give location to within about 5-8
feet.
• Based on Arrival Time
– PinPoint Technology requires the time-stamping of
the arriving signals with accuracy of 1 ns (in order to
achieve an accuracy of 30cms in location).
– Current commercial hardware does not support this
function or accuracy. We are currently developing
hardware which will achieve this.
Signal Strength-based Localization
Localization based on signal strength is a hard problem
due to spatial and temporal variability of the signal
Horus
• At a location X measure distribution of S(X)
– Sampling Interval
– Correlation function
• Can we eliminate correlation?
– Density function
• Radio Map
– How many location?
• Interpolation Function
Signal Strength Chracteristics
200
150
100
50
-95
-85
-75
-65
Average Signal Strength (dbm)
0
-55
0.3
0.25
0.2
0.15
0.1
0.05
0
-58
-57
-56
-55
-54
-53
-52
-51
-50
-49
-48
-47
-46
-45
Mo
re
250
Probability
Number of Samples
Collected
300
Signal Strength (dbm)
Horus: Radio Map and
Estimation
• To address noise characteristics
– Radio map stores signal-strength distributions from K
strongest access points
(instead of scalar mean/maximum)
• To address scalability and cost of estimation
– Clustering techniques for radio map locations
• incremental clustering
• joint clustering
• Outperforms other RF signal strength techniques
– significantly better accuracy
– efficient enough to be implemented on PDAs
Temporal Variations:Correlation
Spatial Variations: Large-Scale
-30
5 10 15 20 25 30 35 40 45 50 55
Signal Strength
(dbm)
-35 0
-40
-45
-50
-55
-60
-65
Distance (feet)
Spatial Variations: Small-Scale
Sampling Process
• Active scanning
• Send a probe request
• Receive a probe response
• Sample:
s  (s1 , s2 ,...)
Handling Correlation: Averaging
1
0.9
0.8
0.7
Var(Y)
0.6
0.5
0.4
0.3
0.2
0.1
0
0
0
0.1
0.2
0.3
0.4
1
0.5
a
2
3
0.6
4
5
0.7
6
7
0.8
8
9
0.9
10
1
Gaussian Approximation
• Approximate signal strength histograms
using Gaussian distribution
–
–
–
–
Saves space
Smoothes histograms
Analytically tractable
Comparable accuracy
Gaussian Approximation
H
G2
G3
G4
100%
90%
80%
70%
CDF
60%
50%
40%
30%
20%
10%
0%
0
1
2
3
4
5
6
7
8
9
Distance
10
11
12
13
14
15
16
17
18
AVW Results
FLA-Mind: Ekahau vs Horus
FLA-Mind: Ekahau vs Horus
(cont)
Ekahau
Horus
Questions??