Transcript ppt

On Designing and Thwarting
Worms using Co-ordination
Jayanthkumar Kannan
Karthik Lakshminarayanan
{kjk, karthik}@cs.berkeley.edu
Impact of P2P Technology
• Widespread deployment of P2P networks
– Large user base: half a million nodes at any time
– Significantly different traffic patterns
• DHT technology
–
–
–
–
Efficient distributed lookup systems
Share information efficiently
Achieve load-balancing
Achieve locality properties
Brief outline of the talk
• Part I: How malicious can a worm get?
–
–
–
–
Stealth – avoid alarms at intrusion detection systems
Efficiency – quicker scanning
Use p2p systems for hit-list generation
Understanding how bad a worm can get is essential
in designing defenses
• Part II: Is there any hope against such worms?
DHTs enable sharing of information across nodes
State-of-the-art
• Worm attacks
–
–
–
–
Pre-collected IP address hit-lists
Divide and conquer (permutation scanning)
Random probing of IP addresses
…
• Defense Techniques
– Unusual high number of rejected packets
– Might do well if ISPs deploy it
Using a deployed P2P network
• Hit-list generation
– How fast can one get IP addresses from crawling a
p2p network like Gnutella?
– How stale is this information after a period of
time?
• Passive probing
– Exploit security loopholes in P2P application
– Use existing communication patterns of p2p
networks
Coordinated worm attacks
• Avoid detection
– Policies followed by worms to avoid triggering alarms
– For e.g., restrict number of probes to an address prefix, probe
internal IP address, bound number of unique probes from source
• Reduce failed probes
– Uneven IP address allocation: random probing not ideal
– Some IDS count number of unsuccessful attempts
– Large number of “missed” probes
• Reduce network utilization
– Some worms caused congestion in the backbone
– Local probes to reduce number of peering links crossed
• Faster propagation
Assumptions
• Bandwidth-limited worm (such as Slammer)
– Not affected by parameters such as number of
outstanding TCP connections
– Issue if it is a TCP worm and uses kernel TCP
implementation
I: Uneven IP address allocation
• Goal: Probe prefixes at a rate proportional to the
probability of finding a vulnerable host
• For each prefix maintain:
– Fraction of vulnerable hosts
– Extent of IP address that has been scanned
• Let P be the total probes performed to a prefix, V be
the total number of vulnerable hosts, I be the number
of infected hosts, S is size of the prefix
– P(finding a vulnerable host), pi = (S * V/P – I)/S
I: Uneven IP address allocation
• Use a DHT for maintaining P,V,I,S:
– Infected nodes probe DHT and get a prefix that is likely
to have vulnerable hosts
– Probe k-prefixes, and sample according to the
vulnerability metric
• Desired characteristics of DHT:
–
–
–
–
–
Performs admission control
Allow high query/update rate
High degree of churn
Target size of DHT not large (~5000 nodes)
We chose “Kelips” as our DHT
A brief overview of Kelips
• Combination of DHT and unstructured
network with O(sqrt(n)) memory usage
• Basic Idea: Gossiping used to maintain
consistency
• Information propagates to group in
O(log(n)) time
Affinity Groups:
peer membership thru consistent hash
0
1
2
Affinity Group
pointers
Kelips
Slide borrowed from authors
Cross-group
“contacts”
N 1
filename, location
“filetuple”
hash
filename 0
File Replica
inserted
Somewhere
(DHT or DOLR)
Kelips
Affinity Groups:
peer membership by consistent hash
1
2
N 1
replicate
filetuple
Slide borrowed from authors
Our Modifications
• Longest Prefix Match among home pointers
– Allows flexibility in relocating sub-prefixes
– Eg: Node A has information about 10.1.0.0/16, Node B
has information about 10.1.2.0/24.
• Inconsistency Resolution
– Application-level resolution
– If two home pointers (id,A1), and (id,A2), then merge
data in A1 and A2, and choose one randomly
• Choose number of groups such that number of
nodes in one group is small
– Simulations: Consistency attained within 10 secs.
II. Evading intrusion detection
systems
• By following specific policies
• By minimizing number of AS-level hops
– Assuming ISPs do monitoring
• Can be achieved by having the home
pointer allocate prefixes to infecting nodes
– Home pointer can maintain number of nodes
probing such addresses
– Can be used to implement powerful policies
III. Exploiting locality to reduce
network utilization
• Kelips can be made location-aware
• Adaptive improvement through gossiping: Pick
closest RTT ones
• Assumption:
– If A is close to B, and B is close to C, A is close to C.
• Gives two advantages:
– Each low-bandwidth host can find a nearest kelips
‘proxy’
– When inserting new item, inserter asks k random nodes
to measure latencies to prefix, chooses best
– Conflict resolution: Resolve in favor of closer node
Using DHTs for worm defenses
• Some initial high-level thoughts on this
• Our model of defense
• Some firewalls around Internet coordinate
with one another
– Need to cut off traffic from infected networks
– Need to maintain models of normal traffic from
every network, and shut
– Models that offer hope: New IP addresses
probed, New Prefixes probed etc
Using DHTs for worm defenses
• Expensive for every firewall to maintain and even
observe required state
– DHT can be used to share such traffic model
information
– Allocates responsibility in a secure fashion (replication)
– Means traffic models can be verified from multiple
views
– Information across firewalls coordinated using a DHT
• Use redundant routing in DHTs to exchange
information in the presence of network congestion
due to worms
Simulation methodology
• Strawman:
– Random probing (today, worms operate this way)
• Issues in simulation:
– Scalability with size of topology, number of nodes
– Lack of data on distributions of typical AS-level
and last-hop bandwidths
– Address space occupancy information unavailable
Simulation methodology
• What we used:
– Discrete-time simulator
– Scaled down AS-level Internet graph (from Subramanian
et al, Infocom 2002)
– Assigned IP prefixes as in SSFNet
– Access bandwidth from Gummadi et al, MMCN
– Kelips parameters: contacted Kelips’ authors
• Parameters:
– 100,000 vulnerable nodes (CodeRed had 400,000)
– Living in 5000 Ases (/16 prefixes)
Quantifying hit-list generation
n = number of crawlers
n=25
n=20
n=15
n=10
n=5
n=1
• Gnutella crawlers on PlanetLab (thanks to Boon!)
• Harvest a huge number of IP addresses within 1 hour!
– Further growth possibly due to the degree of churn
Quantifying hit-list generation
• Diminishing returns
• 57% of the hosts can be contacted after 1 week
Coordinated worm: Infection rate
Coordinated
Random probe
• Vanilla implementation of coordinated worm
• 1.5x faster than random probing
• Useful during initial phases of worm propagation (~2x faster)
Number of failed probes
Random probe
Coordinated
• Once our algorithm “learns” the distribution,
it out-performs random probing worm
Effect of imbalance in address
distribution
• Summary:
– Relative performance of coordinated worm
increases with increases with increase in
imbalance
– … number of IP addresses seen
– … number of failed probes
Implementation
• Oops…
Conclusion
• Have shown how DHT technology has a
bearing on the worm vs. defense tug of war
• Possible to have much stealthier and faster
worms using DHTs.
• Have also shown that if worm is aware of
security policies, can circumvent
– Security through obscurity is no good