Transcript Slides

Kill-Bots
Surviving Organized DDoS
Attacks That Mimic Flash
Crowds
Srikanth Kandula, Dina Katabi, Matthias Jacob and
Arthur Berger
Based on Srikanth Kandula’s Presentation
Boris Korenfeld
[email protected]
CyberSlam
20,000+ zombies issue requests that mimic legitimate
browsing
GET File.zip
DO DBQuery
www.foo.com
Requests Look Legitimate  Standard filters don’t help
CyberSlam Attacks Happen!

Instances of CyberSlam




First FBI DDoS Case – Hired professionals hit
competitor
Mafia extorts online gaming sites …
Code RED Worm
Why CyberSlam?



Avoid detection by NIDS & firewalls
High pay-off by targeting expensive resources
 E.g., CPU, DB, Disk, processes, sockets
Large botnets are available
Tentative Solutions

Filter big resource
consumers?

Passwords?
Computational
puzzles?

????
No big consumers;
Commodity OS do not
support fine-grained
resource accounting
 Might not exist,
expensive to check
 Computation is abundant
in a botnet

Kill-Bots is a kernel extension for web
servers
LOAD > L1
Suspected
Attack
Normal
LOAD < L2 < L1
No Overhead
New Clients are
authenticated once
and given HTTP Cookie
Reverse Turing Test (e.g.,
CAPTCHAs) to distinguish humans
from zombies
But…
3 Problems with CAPTCHA
Authentication

(1) DDoS the authentication mechanism

(2) Bias against users who can’t or won’t answer
CAPTCHAs
N
O

Can’t
see it
(3) How to divide resources between service and
authentication as to maximize system goodput?
Problem 1:
Authentication vulnerable to DDoS
Client
Server
Standard Network Stack
SYN
SYN Cookie
SYNACK
SYNACKACK
HTTP Request
Check cookie, socket, reserve buffers
Causes context switch, buffer copies
Send CAPTCHA
TCP FIN
Resources are reserved till client
sends a FIN but zombies don’t FIN
Problem 1:
Solution:
Authentication vulnerable to DDoS
Modify network stack to issue
CAPTCHAs without state
Client
Kill-Bots
Server
SYN
SYN Cookie
SYNACK
SYNACKACK
HTTP Request
Send CAPTCHA
TCP FIN
Modified Network Stack
•
Stateless & Cheap
•
Keep congestion
control semantics
•
No browser mods.
Drop;
Check cookie, send
CAPTCHA without a socket!
Kill-Bots Token
• When the Kill-Bots server issues a puzzle, it creates a Token.
• Browser reports the answer to the server along with the KillBots token.
• Server verifies the token by recomputing the hash.
• Server checks the Kill-Bots token to ensure the token was
created no longer than 4 minutes ago.
• Server checks if the answer to the puzzle is correct.
• If all checks are successful, the server creates a Kill-Bots
HTTP cookie and gives it to the user.
• Cookie allows the user to re-enter the system for 30 minutes.
• Each correctly answered graphical test allows the client to
execute a maximum of 8 simultaneous HTTP requests.
Problem 2:
Solution:
Legit. Users who don’t answer CAPTCHA
Use reaction to CAPTCHA
Humans
Zombies
(1) Answer CAPTCHA
(2) Reload; if doesn’t
work, give up
Can’t answer CAPTCHA,
but have to bombard the
server with requests
• Count the unanswered CAPTCHAs per IP, and drop
if more than T; Cheap with a Bloom Filter
Bloom Filter
increase
give captcha
COUNTER
decrease
correct ans.
Bloom Learns
Stage 1:
All Zombie IPs
 CAPTCHA
Authentication
 Learn IP addresses of
zombies using Bloom
Stage 2:
filter
 Use only Bloom filter
for Authentication
 No CAPTCHAs
Users who don’t answer CAPTCHAs can access
the server despite the attack in Stage 2
Problem 3:


To Authenticate or To Serve?
Authenticate all new arrivals
 can’t serve all authenticated clients
Authenticate very few arrivals
 too few legitimate users are authenticated
Solution:
• Authenticate new clients with prob.  (drop others)
But what  maximizes goodput?
Analysis
Modeled system using Queuing Theory
Found Optimal * (proof in paper)
But * depends on many unknown parameters
• attack rate
• mean service time
• mean session size
• legitimate request rate, etc…
Solution to Problem 3:
Kill-Bots adapts the authentication prob. by measuring
fraction of time CPU is idle
1
1
1
1
  , 1  ,  2  ,  3 
8
8
4
4
Variables used in the analysis
Tying it Together
Security Analysis








Socially-engineered attack: attacker force their own visitors to
solve CAPTCHAs before granting access.
Puzzles in Kill-Bots expire 4 minutes after they have been served.
Maximum of 8 simultaneous connections per cookie .
Polluting the Bloom Filter: attacker try to spoof his IP address and
pollute the Bloom filter.
SYN cookies prevent IP spoofing and Bloom filter entries are
modified after the SYN cookie check succeeds.
Breaking the CAPTCHA: automatic solving of simple CAPTCHAs.
Such programs are not available to the public for security reasons
yet.
When one type of CAPTCHAs get broken, Kill-Bots can switch to a
different kind.
Security Analysis









Copy attacks: attacker solves one graphical puzzle and distributes
cookie to many zombies.
Maximum of 8 simultaneous connections per cookie.
Replay attacks: attacker replay the answer packet to obtain many
Kill-Bots cookies.
If an adversary tries to replay a session cookie outside its time
interval it gets rejected.
Same Token yields the same cookie.
Database attack: attacker collects all possible puzzles and the
corresponding answers.
Kill-Bots uses a large number of puzzles and periodically replaces
puzzles with a new set.
The space of all possible graphical puzzles is huge.
Building a database, distributing it to all zombies, and ensuring they
can search it and obtain answers within 4 minutes is very difficult.
Performance
Metrics
Goodput (of Legitimate Users)
 Response time (of Legitimate Users)
 Maximum survivable attack rate

Response Time (sec)
Goodput of Legit. (Mb/s)
5-10 times
better Goodput
Response Time
Kill-Bots
underand
DDoS
Attack Rate (Request/sec)
Attack Rate (Request/sec)
Goodput of Legit. (Mb/s)
Why Adapt the Authentication
Probability?
Server with adaptive authentication
Server with authentication
Base server
Attack Rate (Request/sec)
Adaptive  is much better than
authenticating every new user
Flash Crowd
Response Time (sec)
Goodput of legit. (Mb/s)
Orders of magnitude better Response Time
Time (sec)
Adaptive  under
providesFlash
admission
control
Kill-Bots
Crowd
Time (sec)
Response Time (sec)
Authentication Prob. 
Flash Crowd
Time (sec)
Kill-Bots under Flash Crowd
Kill-Bots
360,000
80,000
Response Time (sec)
Number of dropped
legitimate requests
Base Server
Kill-Bots authenticates new clients only if it can
serve them…
Time (sec)
Kill-Bots’ Contributions

First to protect Web servers from DDoS attacks
that mimic legitimate browsing

First to deal with CAPTCHA’s bias against
legitimates users who don’t solve them

Sends CAPTCHA and checks answer without any
server state

Addresses both DDoS attacks and Flash Crowds

Orders of magnitude better response time,
goodput, and survivable attack rate
THANK YOU
Boris Korenfeld
[email protected]
Home Work Assignment
1.
2.
3.
4.
What are the differences between Stage1
and Stage2 in Kill-Bots?
What is the Kill-Bots modification to the
Network Stack?
What problem the Admission Control
solves?
What are the key components of KillBots architecture? (in paper)