Transcript Mapping the Internet and Intranets

Mapping the Internet and Intranets
1 of 75
Mapping the
Internet and
Intranets
Bill Cheswick
[email protected]
http://www.cheswick.com
75 slides
Motivations
• Intranets are out of
control
– Always have been
• Highlands “day after”
scenario
• Internet tomography
• Curiosity about size
and growth of the
Internet
• Same tools are useful
• Panix DOS attacks
– a way to trace
anonymous packets
back!
for understanding any
large network,
including intranets
Mapping the Internet and Intranets
3 of 75
Related Work
• See Martin Dodge’s cyber geography page
• MIDS - John Quarterman
• CAIDA - kc claffy
• Mercator
• “Measuring ISP topologies with
rocketfuel” - 2002
– Spring, Mahajan, Wetherall
• Enter “internet map” in your search engine
Mapping the Internet and Intranets
4 of 75
The Goals
• Long term reliable
collection of Internet
and Lucent
connectivity
information
– without annoying
too many people
– movie of Internet
growth!
• Develop tools to probe
intranets
• Probe the distant
corners of the Internet
• Attempt some simple
visualizations of the
data
Mapping the Internet and Intranets
5 of 75
Methods - data collection
• Single reliable host connected at the
company perimeter
• Daily full scan of Lucent
• Daily partial scan of Internet, monthly full
scan
• One line of text per network scanned
– Unix tools
Mapping the Internet and Intranets
6 of 75
Methods - network scanning
• Obtain master network list
– network lists from Merit, RIPE, APNIC, etc.
– BGP data or routing data from customers
– hand-assembled list of Yugoslavia/Bosnia
• Run a traceroute-style scan towards each
network
• Stop on error, completion, no data
– Keep the natives happy
Mapping the Internet and Intranets
7 of 75
TTL probes
• Used by traceroute and other tools
• Probes toward each target network with
increasing TTL
• Probes are ICMP, UDP, TCP to port 80, 25,
139, etc.
• Some people block UDP, others ICMP
Mapping the Internet and Intranets
8 of 75
TTL probes
Hop 1
Hop 2
Hop 3
Router
Router
Router
IP
IP
IP
IP
Hardware
Hardware
Hardware
Hardware
Client
Application level
TCP/UDP
Hop 3
Hop 4
Server
Application level
Router
Router
IP
IP
IP
Hardware
Hardware
Hardware
Mapping the Internet and Intranets
TCP/UDP
9 of 75
Send a packet with a TTL of
1…
Hop 1
Hop 2
Hop 3
Router
Router
Router
IP
IP
IP
IP
Hardware
Hardware
Hardware
Hardware
Client
Application level
TCP/UDP
Hop 3
Hop 4
Server
Application level
Router
Router
IP
IP
IP
Hardware
Hardware
Hardware
Mapping the Internet and Intranets
TCP/UDP
10 of 75
…and we get the death notice
from the first hop
Hop 1
Hop 2
Hop 3
Router
Router
Router
IP
IP
IP
IP
Hardware
Hardware
Hardware
Hardware
Client
Application level
TCP/UDP
Hop 3
Hop 4
Server
Application level
Router
Router
IP
IP
IP
Hardware
Hardware
Hardware
Mapping the Internet and Intranets
TCP/UDP
11 of 75
Send a packet with a TTL of
2…
Hop 1
Hop 2
Hop 3
Router
Router
Router
IP
IP
IP
IP
Hardware
Hardware
Hardware
Hardware
Client
Application level
TCP/UDP
Hop 3
Hop 4
Server
Application level
Router
Router
IP
IP
IP
Hardware
Hardware
Hardware
Mapping the Internet and Intranets
TCP/UDP
12 of 75
… and so on …
Hop 1
Hop 2
Hop 3
Router
Router
Router
IP
IP
IP
IP
Hardware
Hardware
Hardware
Hardware
Client
Application level
TCP/UDP
Hop 3
Hop 4
Server
Application level
Router
Router
IP
IP
IP
Hardware
Hardware
Hardware
Mapping the Internet and Intranets
TCP/UDP
13 of 75
Advantages
• We don’t need access (I.e. SNMP) to the
routers
• It’s very fast
• Standard Internet tool: it doesn’t break
things
• Insignificant load on the routers
• Not likely to show up on IDS reports
• We can probe with many packet types
Mapping the Internet and Intranets
14 of 75
Limitations
• Outgoing paths only
• Level 3 (IP) only
– ATM networks appear as a single node
– This distorts graphical analysis
• Not all routers respond
• Many routers limited to one response per
second
Mapping the Internet and Intranets
15 of 75
Limitations
• View is from scanning host only
• Takes a while to collect alternating paths
• Gentle mapping means missed endpoints
• Imputes non-existent links
Mapping the Internet and Intranets
16 of 75
The data can go either way
B
C
D
A
E
F
Mapping the Internet and Intranets
17 of 75
The data can go either way
B
C
D
A
E
F
Mapping the Internet and Intranets
18 of 75
But our test packets only go
part of the way
B
C
D
A
E
F
Mapping the Internet and Intranets
19 of 75
We record the hop…
B
C
D
A
E
F
Mapping the Internet and Intranets
20 of 75
The next probe happens to go
the other way
B
C
D
A
E
F
Mapping the Internet and Intranets
21 of 75
…and we record the other
hop…
B
C
D
A
E
F
Mapping the Internet and Intranets
22 of 75
We’ve imputed a link that
doesn’t exist
B
C
D
A
E
F
Mapping the Internet and Intranets
23 of 75
Data collection complaints
• Australian parliament was the first to
complain
• List of whiners (25 nets)
• Military noticed immediately
– Steve Northcutt
– arrangements/warnings to DISA and CERT
• These complaints are mostly a thing of the
past
– Internet background radiation
predominates
Mapping the Internet and Intranets
24 of 75
Visualization goals
• make a map
– show interesting features
– debug our database and collection
methods
– hard to fold up
• geography doesn’t matter
• use colors to show further meaning
Mapping the Internet and Intranets
25 of 75
Mapping the Internet and Intranets
26 of 75
Mapping the Internet and Intranets
27 of 75
Infovis state-of-the-art in 1998
• 800 nodes was a huge graph
• We had 100,000 nodes
• Use spring-force simulation with lots of
empirical tweaks
• Each layout needed 20 hours of Pentium
time
Mapping the Internet and Intranets
28 of 75
Mapping the Internet and Intranets
29 of 75
Visualization of the
layout algorithm
Laying out the Internet graph
75 slides
Mapping the Internet and Intranets
31 of 75
Visualization of the
layout algorithm
Laying out an intranet
75 slides
Mapping the Internet and Intranets
33 of 75
A simplified map
• Minimum distance spanning tree uses 80%
of the data
• Much easier visualization
• Most of the links still valid
• Redundancy is in the middle
Mapping the Internet and Intranets
34 of 75
Colored by
AS number
Mapping the Internet and Intranets
35 of 75
Map Coloring
• distance from test host
• IP address
– shows communities
• Geographical (by TLD)
• ISPs
• future
– timing, firewalls, LSRR blocks
Mapping the Internet and Intranets
36 of 75
Colored by IP address!
Mapping the Internet and Intranets
37 of 75
Colored by geography
Mapping the Internet and Intranets
38 of 75
Colored by ISP
Mapping the Internet and Intranets
39 of 75
Colored by distance
from scanning host
Mapping the Internet and Intranets
40 of 75
US military
reached by ICMP ping
Mapping the Internet and Intranets
41 of 75
US military networks
reached by UDP
Mapping the Internet and Intranets
42 of 75
Mapping the Internet and Intranets
43 of 75
Mapping the Internet and Intranets
44 of 75
History of the Project
• Started in August 1998 at Bell Labs
• April-June 1999: Yugoslavia mapping
• July 2000: first customer intranet scanned
• Sept. 2000: spun off Lumeta from
Lucent/Bell Labs
Mapping the Internet and Intranets
45 of 75
Yugoslavia
An unclassified peek at a new
battlefield
75 slides
Mapping the Internet and Intranets
47 of 75
Intranets: the rest
of the Internet
75 slides
The Pretty Good
Wall of China
Mapping the Internet and Intranets
52 of 75
Mapping the Internet and Intranets
53 of 75
Mapping the Internet and Intranets
54 of 75
Mapping the Internet and Intranets
55 of 75
Mapping the Internet and Intranets
56 of 75
Mapping the Internet and Intranets
57 of 75
This was
Supposed
To be a
VPN
Mapping the Internet and Intranets
58 of 75
Mapping the Internet and Intranets
59 of 75
Mapping the Internet and Intranets
60 of 75
Anything large
enough to be
called an
“intranet” is
out of control
75 slides
Case studies: corp. networks
Some intranet statistics
Intranet sizes (devices)
Corporate address space
% devices in unknown address space
Min
Max
7,900
365,000
81,000 745,000,000
0.01%
20.86%
% routers responding to "public"
% routers responding to other
0.14%
0.00%
75.50%
52.00%
0
0%
0%
176,000
79%
82%
Outbound host leaks on network
% devices with outbound ICMP leaks
% devices with outbound UDP leaks
Inbound UDP host leaks
0
% devices with inbound ICMP leaks
0%
% devices with inbound UDP leaks
0%
% hosts running Windows
36%
Mapping the Internet and Intranets
5,800
11%
12%
84%
62 of 75
Leak Detection
Lumeta’s “special sauce”
75 slides
Leak Detection
mitt
D
Mapping host
A
• A sends packet to B,
with spoofed return
address of D
• If B can, it will reply
Internet
intranet
C
to D with a
response, possibly
through a different
interface
B
Test host
Mapping the Internet and Intranets
64 of 75
Outbound Leak Detection
mitt
D
Mapping host
A
• Packet must be crafted
so the response won’t
be permitted through the
firewall
• A variety of packet types
Internet
intranet
and responses are used
• Either inside or outside
address may be
discovered
• Packet is labeled so we
C
B
know where it came from
Test host
Mapping the Internet and Intranets
65 of 75
Inbound Leak Detection
mitt
D
Mapping host
A
• This direction is
usually more
important
• It all depends on the
Internet
intranet
site policy…
• …so many leaks
might be just fine.
C
B
Test host
Mapping the Internet and Intranets
66 of 75
Inbound Leak Detection
mitt
D
Mapping host
A
Internet
intranet
C
B
Test host
Mapping the Internet and Intranets
67 of 75
Some Lumeta lessons
• Reporting is the really hard part
– Converting data to information
• “Tell me how we compare to other clients”
• Offering a service was good practice, for a
while
• The clients want a device
• We have >70 Fortune-200 companies and
government agencies as clients
• Need-to-have vs. want-to-have
Mapping the Internet and Intranets
68 of 75
Honeyd – network emulation
• Anti-hacking tools by Niels Provos at
citi.umich.edu
• Can respond as one or more hosts
• I am configuring it to look like an entire
client’s network
• Useful for testing and debugging
• Product?
Mapping the Internet and Intranets
69 of 75
Open questions
and future work
75 slides
How do you analyze a large
graph over time?
• Five years of Internet data, mostly
unanalyzed
• Alternate paths to a target country
• Sample insight: “Poland was off the Internet
yesterday”
• Placement of monitoring tools?
• Compute a display differences between two
complex graphs
Mapping the Internet and Intranets
71 of 75
Visualizations
• These graphs are too big for a piece of paper
• Various approaches available, but none
really satisfactory
• Build visualization graph as the data comes
in, and as the network evolves
Mapping the Internet and Intranets
72 of 75
Mapping the Internet and Intranets
73 of 75
Mapping the
Internet and
Intranets
Bill Cheswick
[email protected]
http://www.cheswick.com
75 slides
Mapping the Internet and Intranets
75 of 75