30/09/2019

”Something is Better than Nothing”

Curbing and Curing Distributed
Denial of Service Attack

Contents

 History
 Introduction of Network Security
 Proposed Mechanism
 Simulation Results
 Conclusion

1
 30/09/2019

History

 first seen DoS attack relied on software bug in

IOS/700 version 4.1
 in 1996, some Internet service providers were being
affected by SYN flooding
 first DDoS attack against commercial sites like Yahoo
take place in Feb, 2000

Introduction to Security (1)

• Way to Define Security Requirements

• Security Attacks
• Action that Compromise the Security
• Security Mechanisms
• Mechanism designed to Detect, Prevent,
Recover from Security Attacks
• Security Services
• Use of One or More Mechanisms

2
 30/09/2019

Network Security (1)

• Security Attacks
• Authentication
• Confidentiality
• Integrity
• Availability
• Passive Attacks
• Active Attacks

Network Security (2)

• Security Mechanisms
• Cryptography
• Firewalls
• Intrusion Detection
• Communication Security
• Access Control
• DBMS Security
• Application Security

3
 30/09/2019

Network Security (3)

• Defensive Strategies
• Coarse: Isolate - Keep Everybody Out
• Medium: Exclude - Keep the Bad guys out - Firewall
• Fine: Restrict - Let the Bad guy in but keep them
away from doing damages
• Recover - Undo the Damages - Backup
• Punish – Prosecution
Best Strategy is NOT LOCK but PUNISHMENT

Network Security (4)

• Firewall
• First Line of Defense
• Intrusion Detection
• Second Line of Defense
• Communication Security
• IPSec, IPv6
• Authentication Application
• Kerberos

4
 30/09/2019

Hacking TCP: SYN Flooding

 Attacker sends many connection requests w/
spoofed source addresses to victim
 Victim allocates resources for each request
 Finite # half-open connection requests supported
 Connection requests exist for TIMEOUT period
 Once resources exhausted, all other requests rejected

Normal connection est. Syn Flooding attack

Hacking TCP: SYN Flooding

Defenses
 System Configuration Improvements
 Reduce timeout period
 Increase length of backlog queue to support more
connections
 Disable non-essential services to make a smaller target
 Router Configuration Improvements
 Configure router external interfaces to block packets with
source addresses from internal network
 Configure router internal interfaces to block packets to
outside that have source addresses from outside the internal
network
 TCP SYN cookies
 Make handshake stateless on server end
 Server makes ISN a function of a secret nonce it keeps and
pieces of the SYN connection ID
 Only create TCB and establish connection upon verifying
client’s ACK

10

5
 30/09/2019

Hacking TCP: SYN Flooding

Defenses

 Firewall as a Relay
 Firewall answers on behalf of
Destination
 Once connection established,
firewall predicts seq # and
establishes 2nd connection to
Destination
 Disadvantage: Adds delay for
every packet

11

Hacking TCP: SYN Flooding

Defenses
 Firewall as a Semi-transparent
Gateway
 Forges the 3rd handshake (ack) from the client to the
destination
 This moves connection out of backlog queue, freeing
resources
 If this is attack, no “real” ack will happen
 Destination will send RST packet terminating connection
 If this is actual connection request the eventual ack will be
ignored as a duplicate
 Disadvantages:
 Large # illegitimate open connections if system under
attack
 Must very carefully choose timeout periods

12

6
 30/09/2019

Hacking TCP: SYN Flooding

Defenses

Attack w/ semi- Legit connection w/ semi-

transparent gateway transparent gateway

13

Hacking TCP: SYN Flooding

Defenses
 Active Monitor
 Program that promiscuously monitors and injects
network traffic to/from machines it is protecting
 Monitors net for SYN packets not acknowledged
after a certain period of time
 If it detects problems with a half-open connection
it can
 Send RST packets to the sender to release destination
resources
 Complete the TCP connections by sending the ACK
message
• Similar to Semi-Transparent gateways

14

7
 30/09/2019

Hacking TCP: Congestion control

tricks
 ACK Division
 Receiver can acknowledge segments multiple times (up to
#bytes acks)
 Leads Sender to grow cwnd faster than normal.
 Solution to ACK Division
 Modify congestion control to guarantee segment-level
granularity
 Only increment MSS when a valid ACK arrives for the entire
segment. Bunch of
acks

Burst 1 RTT later

15

Hacking TCP: Congestion control

tricks
 Duplicate Ack Spoofing
 Receiver sends multiple acks/sequence #
 no way to tell what segment is being acked
 Causes sender to enter fast-recovery mode and inflate cwnd
 Solution to Duplicate Ack Spoofing
 Add new fields to TCP headers.
 “nonce & nonce-reply” – random values sent with segments
and replies
 Only increment cwnd for ACKs with previously unseen nonces

Burst of dup acks

Sender enters
Fast Recovery
and bursts 1
RTT later

16

8
 30/09/2019

Hacking TCP: Congestion control

tricks
 Optimistic ACKing
 Send acks for segments not yet received
 Decrease perceived RTT, affecting CW growth.

Segment acks

Segs arrive

17

Hacking TCP: Congestion control

tricks
 Solution to optimistic
acking: Cumulative
Nonce
 Sender sends random
number (nonce) with each
packet
 Segment size slightly
randomized
 Receiver sends cumulative
sum of nonces
 if receiver detects loss, it
sends back the last nonce it
received
 Why cumulative?
 Requires modifications to
stack
18

9
 30/09/2019

Hacking routing: RIP attacks

 Attack
 Intruder sends bogus routing information to a
target and each of the gateways along the route
 Impersonates an unused host
• Diverts traffic for that host to the intruder’s machine
 Impersonates a used host
• All traffic to that host routed to the intruder’s machine
• Intruder inspects packets & resends to host w/ source
routing
• Allows capturing of unencrypted passwords, data, etc

19

Hacking routing: RIP attacks

 Defenses
 Paranoid gateway
 Filters
packets based on source and/or destination
addresses
 Don’t accept new routes to local networks
 Messes with fault-tolerance but detects intrusion
attempts
 Authenticate RIP packets
 Difficultin a broadcast protocol
 Only allows for authentication of prior sender and
doesn’t address information from a deceived gateway
upstream

20

10
 30/09/2019

Hacking ICMP
 Attack
 Targeted Denial of Service (DoS)
 Attacker sends ICMP Redirect message to give a bogus
route
 Attacker sends Destination Unreachable or TTL exceeded
messages to reset existing connections
 Attacker sends fraudulent Subnet Mask Reply messages
• Blocks communication with target
 Defenses
 Verify ICMP packet contains a plausible sequence
#
 Don’t modify Global Route Table due to ICMP
Redirect messages
 Disallow ICMP Redirects?
 Check to see if multiple ICMPs from a host agree

21

Hacking DNS
 DNS : Domain Name System
 BSD r*
 rlogin, rcp, rsh use address based authentication (reverse
lookup)
 The problem
 No authentication
 Responses can contain entries that should not be trusted but
are
 Responses are cached
 Attacks
 Inject bogus DNS responses
 Attach additional bogus entries in valid DNS responses
(especially for internal names)
Firewall

Local Name Server Remote Name Server

*
Application Resolver
(Trusted) (?)

22

11
 30/09/2019

Hacking DNS
 Solution: DNS Proxy
 Filter
 Drop malformed packets
 Verify
 Does the answer, really answer the query made?
 Was the answer received from the appropriate server?

 Proxy performs checks on the answers from

outside DNS servers
 Located within the firewall on a trusted host
 Intercepts DNS queries, filters, modifies and forwards in
appropriate direction

23

Hacking the stack: Reflector

attacks
 A reflector is any IP host that will return a
packet or more if sent a packet.
 Reflector cannot easily locate the slave because of IP
spoofing.
 Examples:
 Web servers: return SYN ACKS or RSTs in response to SYN
or other TCP packets.
 DNS servers: return query replies in response to query
requests.
 Routers: return ICMP Time Exceeded or Host Unreachable
messages in response to particular IP packets.

24

12
 30/09/2019

25

Hacking the stack: ICMP

reflectors
 ICMP echo, timestamp, address mask,
router solicitation, information
request/reply.
 ICMP echo is widely used.
 Smurf attacks
 ICMP source quench, unreachable, time
exceeded, parameter problem, and
redirect.
 Important ICMP messages:
 Hostunreachable.
 Time exceeded.
 Need fragmentation.

26

13
 30/09/2019

Hacking the stack: TCP reflectors

 TCP stack can be made to reflect via…
 SYN ACK by sending an initial SYN.
 Filtering leads to no-remote access.
 RST by sending a FIN.
 Filtering RST results in clogging of stale connections
state

27

Hacking the stack: TCP reflectors

 Predictable TCP sequence numbers
 If reflector stack has guessable TCP sequence
numbers, it’s a DISASTER for the victim.
 Attacker can drive the Reflector TCP state
machine, making it send ACKs, data segments.
 Attack can be amplified by transmitting large items
and exploiting “ACK splitting” techniques.

28

14
 30/09/2019

Hacking the stack: TCP for

Transactions (T/TCP) reflectors

 Spoof initial SYN packet with acceptable

seq. no.
 Make an expensive request.
 Factors that limit the T/TCP attack
 T/TCP server will begin in slow start.
 Unless the server’s stack has predictable seq. no.
 Amenable to stateless packet filtering.
 T/TCP is not widely deployed.

29

Hacking the stack: UDP

reflectors

 UDP
 Application-specific
 Quake Qstat
 Counter-strike clients
 DNS

30

15
 30/09/2019

Hacking the stack: DNS

reflectors
 DNS
 Reflector sending DNS reply in response to a spoofed DNS
request.
 Victim can configure its local DNS servers so as to filter out
unknown DNS server responses.
 If the victim is a name server
 Attacker can query a large number of DNS servers which in
turn recursively query the Victim.
 Victim server gets bombarded due to multiple queries.

 DNS queries needn’t even be spoofed.

 Send valid queries to a large set of known DNS servers
 Arbitrary names not just the ones responsible for
 Caching at the reflector server doesn’t help.
 Solution: Provide filtering in name servers so as to serve
recursive queries from local addresses, coupled with ingress
filtering.

31

Hacking the stack: SNMP

reflectors
 SNMP (UDP-based request/reply)
 Sites that fail to block off-site access to SNMP
provide a large number of reflectors.
 SNMP attack is sourced at port 161.
 Filtering out the external SNMP messages leads to
major problem for service providers.
 Configure the filter to receive SNMP messages from
interested hosts.

32

16
 30/09/2019

Hacking the stack: HTTP

reflectors
 HTTP proxies
 HTTP proxy caches provide a way that an HTTP client can
manipulate a proxy server into initiating a connection to a
victim web server.
 HTTP proxy servers act as reflectors for the DDOS attacks.
 HTTP - Limitations
 Proxies can be configured to serve a restricted set of clients.
 There are not enough proxy caches to constitute a large
pool of possible reflectors.
 Connection between slave and the reflector cannot be
spoofed unless the reflecting proxy has predictable sequence
numbers. Logging helps in identifying the slave’s location.

 Definitely a major threat if servers running on

stacks with predictable sequence numbers are
widely deployed.

33

Analyzing attacks: Backscatter

 Attackers spoof source address
randomly
 Small frequent packets. (packet/sec bottleneck)
 e.g. TCP SYN -> victim allocate data structure for
arriving packets (for unmatched to existing
connections)
 Victims, in turn, respond to attack
packets
 Remotely controlled “Zombies” for DDoS
 Unsolicited responses (backscatter)
equally distributed across IP space
 Received backscatter is evidence of an attacker
elsewhere
34

17
 30/09/2019

From caida page

35

From caida page

36

18
 30/09/2019

Analyzing attacks: Backscatter

 Backscatter analysis provides

quantitative data for a global view on
DoS activity using local monitoring
 Videos
 Traffic Characterisation (How Data Gathered)
• [Link]
ve_monitoring/traffic_char.mpg (1min12s)
 TCP Port Analysis
• [Link]
ve_monitoring/tcp_port_analysis.mpg (2min15s)
 Backscatter
• [Link]
ve_monitoring/[Link] (1min26)

37

Analyzing attacks: Assumptions

 Address Uniformity
 Reliable delivery
 Backscatter not lost
 Backscatter hypothesis
 Unsolicited packets represent backscatter
 In fact any server can send
 Reflector attack may not be detected
 Not random IP-forgery
 Some attacks (e.g. TCP-RST) doesn’t produce
backscatter.

38

19
 30/09/2019

39

Analyzing attacks: Few Results

 13000 attacks in 3 weeks
 5000 victim IP addresses on 2000 domains
 200 million backscatter packets
 *256 < Real attack packets
 Most attacks short, some longer persistent
ones
 Mostly TCP (90-94%)
 Some large ICMP storms (43% of all packets)
 Attacks cover most ports, but HTTP and IRC singled out
 How serious is this?
 500 packets enough to overwhelm server
 38-46 % of attacks (unif.-all)
 14000 packets enough to overwhelm firewall
 0.3-2.4 % of attacks (unif.-all)

40

20
 30/09/2019

Analyzing attacks: Victim

characterization
 Entire spectrum of sites and businesses
 Yahoo!, Amazon, CNN, etc.
 Small attacks from personal vendettas
 10-20% targeted towards home machines
 Attacks on infrastructure
 5% directed towards routers and root DNS servers

41

Traceback: Motivation
 DoS attacks
 IP spoofing
 No one checks source IP address to drop spoofed
packets
 TCP SYN floods, Smurf (ICMP echo to broadcast
addresses)
 Difficult to get the help of upstream ISP
 Lack skill
 Lack resources (might be 6pm on Friday)
 In a different country (speak different language, etc)

 Require automatic way of identifying where the

traffic is coming from without human intervention

42

21
 30/09/2019

Traceback: Problem
 Goal
 Given set of packets
 Determine path A1 A2 A3 A4 A5
 Assumptions
 Most routers remain R6 R7 R8
uncompromised
 Attacker sends many
packets R9 R10
 Route from attacker
to victim remains
relatively stable R12

43

Traceback: schemes
 Record Route
 Traffic injection
 ICMP Trace (ITRACE)
 Probabilistic packet marking
 Logging and query
 Source Path Isolation Engine (SPIE)
 Reverse ITRACE
 Subverting Traceback schemes

44

22
 30/09/2019

Traceback: Record Route

 Record path
 Each router adds IP address to packet
 Victim reads path from packet

 Problem
 Requires space in packet
 Path can be long
 No extra fields in current IP format
• Changes to packet format are not practical

45

Traceback: Traffic injection

 Create a map of routes from victim to every
network
 Burst TCP/UDP packets to each and see if you are affected
 TCP/UDP chargen service
 Generates continuous data to anyone who connects to service
 If DoS stream perturbed, you have a candidate
 Problems
 Finding open chargen service
 Asymmetric routing
 Must generate sufficient load to perturb stream especially
when there are multiple attacking hosts
 Easy to thwart
 Vary source of attack by altering frequency of packets
 Attack from many sources
 Still can’t turn attacker’s off…Must notify upstream ISP to stop

46

23
 30/09/2019

Traceback: Leverage volume of

attack
 Many packets
 DDoS involves many A1 A2 A3 A4 A5
packets on same path
 Have routers
R6 R7 R8
periodically send
message to victim
 Each router sends R9 R10
message to Victim for
every X packets it
R12
forwards to victim

47

Traceback: ICMP trace

 ICMP traceback messages
 Routers periodically issue traceback ICMP messages to
destination
 Send 1 message for every 20000 packets forwarded to
destination
• 0.1% overhead
 Similar to RouteRecord, collects intermediate hops along the
way to destination
 Over time, leaves a trail of where packets are being sourced
from
 Problems
 Skilled attacker spoofing traceback messages to conceal the
real source of attack
• Requires some signature and trust management
 Skilled attacker uses zombies to flood each other along with
victim to reduce the amount of traceback messages sent
• “Background noise”
 Only want traceback messages from far away

48

24
 30/09/2019

Routing

 The most complicated and important

function the network layer provides
 Directing data from source to destination
 Routing algorithms and architectures
 Link state algorithms
 Distance vector algorithms
 Routing hierarchies
 Area routing
 Landmark routing

49

Routing algorithms

Routing protocol
Goal: determine “good” path
5
(sequence of routers) thru
network from source to dest. B 3
C
2 5

Graph abstraction for A 2 1 F

3
routing algorithms: 1 2
D E
 graph nodes are 1
routers
 graph edges are • “good” path:
physical links – typically means
 link cost
minimum cost path
 Delay
 $ cost – other def’s possible
 congestion level

50

25
 30/09/2019

Router Architecture Overview

Key functions:
 Routing
 Run protocol (RIP, OSPF, BGP)
 Can run one or more routing protocols
 Run algorithms to determine routing information (LS,DV)
 Generate forwarding table.
 Forwarding
 Process of moving packets from input port to output port
 Lookup forwarding table given information in packet
 Switch/forward datagrams from incoming to outgoing link
based on route

51

Typical mode of operation

 Packet arrives at inbound line card

 Header transferred to forwarding engine
 Forwarding engine determines output
interface given a table initialized by routing
processor
 Forwarding engine signals result to line
card
 Packet copied to outbound line card

52

26
 30/09/2019

What Does a Router Look Like?

 Routing processor/controller
 Handles routing protocols, error conditions
 Line cards
 Network interface cards
 Forwarding engine
 Fast path routing (hardware vs. software)
 Backplane
 Switch or bus interconnect

53

Routing Processor

 Runs routing protocol

 Uploads forwarding table to forwarding
engines
 Forwarding engines with two forwarding tables to allow
easy switchover (double buffering)
 Typically performs “slow-path” processing
 ICMP error messages
 IP option processing
 IP fragmentation
 IP multicast packets

54

27
 30/09/2019

Input Port Functions

Physical layer:
bit-level reception
Decentralized switching:
Data link layer:
e.g., Ethernet  given datagram dest., lookup output port
using routing table in input port memory
 goal: complete input port processing at
‘line speed’
 queuing: if datagrams arrive faster than
forwarding rate into switch fabric

55

Input Port Queuing

 Fabric slower than input ports combined =>

queuing may occur at input queues
 Head-of-the-Line (HOL) blocking: queued
datagram at front of queue prevents others in
queue from moving forward
 queueing delay and loss due to input buffer
overflow!

56

28
 30/09/2019

Input Port Queuing

 Possible solution
 Virtual output buffering
 Maintain per output buffer at input
 Solveshead of line blocking problem
 Each of MxN input buffer places bid for output

57

Caches
 Leverage temporal locality
 Many packets to same destination
 Long flows help, short flows do not
 Similar to idea behind IP switching (ATM/MPLS) where long-
lived flows map into single label
 Example
 Partridge, et. al. “A 50-Gb/s IP Router”, IEEE Trans. On Networking,
Vol 6, No 3, June 1998.
 8KB L1 Icache
 Holds full forwarding code
 96KB L2 cache
 Forwarding table cache
 16MB L3 cache
 Full forwarding table x 2 - double buffered for updates

58

29
 30/09/2019

Speeding up Prefix Match - Alternatives

 Lookup via content addressable memory (CAM)

 Hardware based route lookup
 Input = tag, output = value associated with tag
 Requires exact match with tag
 Multiple cycles (1 per prefix searched) with single CAM
 Multiple CAMs (1 per prefix) searched in parallel
 Ternary CAM
 0,1,don’t care values in tag match
 Priority (i.e. longest prefix) by order of entries in CAM

 “Spatial caching” via protocol acceleration

 Add clue (5 bits) to IP header
 Indicate where IP lookup ended on previous node (Bremler-Barr
SIGCOMM 99)

59

Types of network switching fabrics

Memory

Crossbar interconnection
Multistage interconnection
Bus

60

30
 30/09/2019

Types of network switching fabrics

 Issues
 Switch contention
 Packets arrive faster than switching fabric can switch
 Speed of switching fabric versus line card speed determines
input queuing vs. output queuing

61

Switching Via Memory

First generation routers:
 packet copied by system’s (single) CPU
 2 bus crossings per datagram
 speed limited by memory bandwidth

Second generation routers:

 input port processor performs lookup, copy into memory
 Cisco Catalyst 8500

Input Memory Output

Port Port

System Bus

62

31
 30/09/2019

Switching Via Bus

 Datagram from input port memory directly to
output port memory via a shared bus
 Issues
 Bus contention: switching speed limited by bus
bandwidth
 Examples
 1 Gbps bus, Cisco 1900: sufficient speed for access
and enterprise routers (not regional or backbone)

63

Switching Via An Interconnection Network

 Overcome bus bandwidth limitations
 Crossbar networks
 Fully connected (n2 elements)
 All one-to-one, invertible permutations supported
 Issues
 Crossbar with N2 elements hard to scale

64

32
 30/09/2019

Switching Via An Interconnection Network

 Multi-stage interconnection networks (Banyan)

 Initially developed to connect processors in multiprocessor
 Typically O(n log n) elements
 Datagram fragmented fixed length cells, switched through the fabric
 Issues
 Blocking (not all one-to-one, invertible permutations supported)
 Example
 Cisco 12000: Gbps through an interconnection network

A W
B X
C Y
D Z

65

Output Ports

 Output contention
 Datagrams arrive from fabric faster than output port’s transmission
rate
 Buffering required
 Scheduling discipline chooses among queued datagrams for
transmission

66

33
 30/09/2019

Output port queueing

 buffering when arrival rate via switch exceeds ouput line

speed
 queueing (delay) and loss due to output port buffer
overflow!

67

34