Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Race conditions on Facebook, DigitalOcean and others (fixed)

josipfranjkovic.blogspot.com

Post reply on HN
Print view View original

61–70 of 90 posts

Re: Race conditions on Facebook, DigitalOcean and others (fixed)

#61

Post by MichaelGG »

pyvpx wrote: post #52
MichaelGG wrote: post #46

We should see lots more of these if people embrace eventual consistency instead of "slow" ACID transactions. And interestingly, the more larger scale a system, the more likely that globally consistent operations are too expensive to enable in general, and developers will overlook cases where they must implement some locking or double checking.

when did eventual consistency equate to race conditions, or even increased susceptibility to race conditions? I don't follow. could you explain your reasoning further?

It's probably just an ease-of-use question. The more guarantees your database can deliver, the easier it is to reason about things and make sure you aren't being caught on a gotcha.

It's not necessarily different than using a normal RDBMS, right - you could do a check in SQL outside a transaction and end up writing multiple times. But with an RDBMS, you can easily solve the situation by turning on a transaction and leaving no question about things.

This is why things like VoltDB ("NewSQL") are pushing to keep SQL and ACID, and figure out a way to scale, instead of throwing it all aside and making the developer deal with consistency issues.

It's not that you can't end up with the same functionality using eventual consistency, just that it's harder. Just look at Amazon's "apology based computing" (I think that was the name) and how they structure their systems to be resilient by being able to resolve multiple conflicting commands in a proper way (deciding, without communication, which command wins, figuring out rollbacks, etc.) It's fantastic, and perhaps it's the only feasible way to operate at their scale. But it's also a hell of a lot more complicated than "UseTransaction = true".

(So my predictions/guesses: If developers that'd otherwise use a traditional ACID RDBMS switch to non-ACID (BASE?) systems, they'll end up introducing bugs due to the shifted responsibility of handling data consistency. And seeing how big servers are, and even how far sharding can take you with normal RDBMS, the scale at which people "need" to drop ACID is probably far higher than the point at which people are dropping it.)

Re: Race conditions on Facebook, DigitalOcean and others (fixed)

#62

Post by MichaelGG »

nmjohn wrote: post #56
dsacco wrote: post #49

Earlier quoted context omitted.

Hi, I'm a security engineer. I work at one of the largest private infosec firms and I've done research on bug bounties that Google, Facebook, Twitter, CERT and 50+ other companies participated in. Now that I've sufficiently named my experience, allow me to give my side: 1. You will never receive $100,000 for selling a vulnerability in PayPal. You probably couldn't even find a buyer for it on the "black market." I hav…

> 3. I'm sorry, but you lose credibility by claiming most security reports can be qualified in a minute or less. You can certainly throw out many in a similar time frame, perhaps five minutes, but real vulnerabilities? No. That was exactly what I was trying to convey: real vulnerabilities can easily be separated from non-issues quite quickly because the later mostly entail things which can be checked in a matter of m…

>That was exactly what I was trying to convey: real vulnerabilities can easily be separated from non-issues quite quickly because the later mostly entail things which can be checked in a matter of minutes.

What about the non-issues that are reported with complicated conditions but don't actually work? Just because you can throw out the obviously bad items doesn't mean the rest are real.

>Orchestrated correctly one could walk away with a few million dollars from exploiting such a vulnerability.

Exploiting it is rather different from selling it, though, right? And since a vuln in a website can literally be closed immediately, and PayPal's got whole divisions dedicated to preventing and undoing the damage you can do even with "account takeover", it'd be rather much a risk to pay someone cash for a vulnerability. At the first slip, the value drops to $0. Plus all the issues of verifying the bug and establishing trust for both parties. Seems rather difficult.

Re: Race conditions on Facebook, DigitalOcean and others (fixed)

#63

Post by MichaelGG »

nmjohn wrote: post #53
smitherfield wrote: post #43

Earlier quoted context omitted.

It's hard to think of an easier decision. Get $100,000 for a couple months before you go to federal prison for 30 years, or hire a publicist and get featured on every tech blog in existence as "the guy who found the PayPal complete account takeover bug," and let the 7-figure job offers roll in.

> let the 7-figure job offers roll in. I would know far more millionare engineers/hackers if that was actually true > go to federal prison for 30 years If one was talented enough to find such a vuln, it is hardly a stretch to say they would be smart enough to avoid getting caught.

>If one was talented enough to find such a vuln, it is hardly a stretch to say they would be smart enough to avoid getting caught.

... This is plainly not true. First, the ease of finding a bug in a web app varies considerably. This article, for instance, was simply about resending requests quickly. It doesn't necessarily require amazing intellect to come across such a bug. Look at famous "hackers" that dicked around with querystrings and got into all sorts of fun.

Second, even if someone is smart and figures out how to solve a certain problem to gain root, it does not mean they're clever, aware, or dedicated enough to maintain opsec. One mistake, any time, and you're toast.

Re: Race conditions on Facebook, DigitalOcean and others (fixed)

#64

Post by MichaelGG »

hobarrera wrote: post #41
underwater wrote: post #15

Earlier quoted context omitted.

Not every database is powered by SQL. Add to that sharding, caching, cross data center traffic and the problem becomes non trivial very quickly.

sharding is what confuses me the most. How would you avoid these race conditions with a distributed database?

Pick a good shard key. In the case of a per-page-per-user ratings system, if you shard on the PageId, then you can locally check consistency to make sure there's no duplicate (PageId, UserId) keys. You can check the same if you shard on UserId, but then doing aggregates can be more difficult since you need to talk to every shard to find out a page's rating.

Re: Race conditions on Facebook, DigitalOcean and others (fixed)

#65

Post by MichaelGG »

pilif wrote: post #34
andersonmvd wrote: post #4

More interesting than the bounty itself is to understand which defense works best at scale and the nitty gritty details of those kind of attacks. Intuitively I think that we just need to avoid inconsistencies between the Time of Check (TOC) and Time of Use (TOU), so veryfing the existence of a discount coupon while inserting it in one query should do the trick (INSERT INTO coupons (...) Values (...) WHERE NOT EXISTS…

In many databases, your suggested "where not exists" sub query might not actually protect you but just make the possible window to hit the race much smaller. What happens is that your database would evaluate the subquery, the rest of the where, commit another transaction and then finally run the insert part of your query. There are no guarantees in the SQL standard that queries with subqueries should be atomic. The o…

>only truly safe way

Or put the whole thing in a transaction, right?

Re: Race conditions on Facebook, DigitalOcean and others (fixed)

#66

Post by MichaelGG »

hobarrera wrote: post #42
ekimekim wrote: post #33

Earlier quoted context omitted.

cynical answer: I've seen alot of races get "fixed" by adding a sleep() or similar less cynical answer: Commonly you already have some kind of means to handle races - locking, transactions, some other variety of extra check - and the fix for newly discovered races is "oh, I didn't realise that could happen. add lock "

If you get three requests in at the same time, and sleep the tree for N (say, 400) miliseconds they'll all still run concurrently. Adding a random time to sleep might work, but some requests would run noticeably slower.

Unless the code is doing read-write-read. If you're using a system that doesn't reflect writes immediately (like Elasticsearch), waiting after the writes can give time for the system to flush and make the other writes visible then you can execute rollback logic.

It'd be much better to make sure you're updating the same unique key and/or use the DB's conflict resolution system.

Re: Race conditions on Facebook, DigitalOcean and others (fixed)

#67

Post by codenut »

spdy wrote: post #60
Kiro wrote: post #57

I'm a novice but would like to know how these issues can arise. What kind of backend setup is needed for it to be a problem? What is happening when a race condition occurs in these examples?

Its actually quite simple as example for the promo code the code looks like this: 1. Code sent. 2. Check if valid. 3. Redeem code. 4. Invalid code. Now if i send 10 requests at the same time with the same code maybe 4-6 will hit the code part after 2. And your window of opportunity is the time it takes to go from 3 to 4. Sometimes certain tasks are put inside async queue, you have a slight delay to your database serv…

Can this issue be prevented if we use the promo code as the table primary key or document ID?

Re: Race conditions on Facebook, DigitalOcean and others (fixed)

#68

Post by nmjohn »

MichaelGG wrote: post #62
nmjohn wrote: post #56

Earlier quoted context omitted.

> 3. I'm sorry, but you lose credibility by claiming most security reports can be qualified in a minute or less. You can certainly throw out many in a similar time frame, perhaps five minutes, but real vulnerabilities? No. That was exactly what I was trying to convey: real vulnerabilities can easily be separated from non-issues quite quickly because the later mostly entail things which can be checked in a matter of m…

>That was exactly what I was trying to convey: real vulnerabilities can easily be separated from non-issues quite quickly because the later mostly entail things which can be checked in a matter of minutes. What about the non-issues that are reported with complicated conditions but don't actually work? Just because you can throw out the obviously bad items doesn't mean the rest are real. >Orchestrated correctly one co…

> What about the non-issues that are reported with complicated conditions but don't actually work? Just because you can throw out the obviously bad items doesn't mean the rest are real.

Yes. There will be some which don't fit into the overly simplistic categories I provided.

However in what I've seen the complicated condition requiring reports which turn out to not actually be bugs are rare enough where they aren't relevant to the discussion.

> Exploiting it is rather different from selling it, though, right? And since a vuln in a website can literally be closed immediately, and PayPal's got whole divisions dedicated to preventing and undoing the damage you can do even with "account takeover", it'd be rather much a risk to pay someone cash for a vulnerability. At the first slip, the value drops to $0. Plus all the issues of verifying the bug and establishing trust for both parties. Seems rather difficult.

You are hung up on what was an arbitrary example.

My point simply is if the reward for serious vulnerabilities is orders of magnitude higher if the researchers chooses the black hat instead of the white one - the overall result is a huge net negative for the world.

Re: Race conditions on Facebook, DigitalOcean and others (fixed)

#69

Post by jaysh »

codenut wrote: post #67
spdy wrote: post #60

Earlier quoted context omitted.

Its actually quite simple as example for the promo code the code looks like this: 1. Code sent. 2. Check if valid. 3. Redeem code. 4. Invalid code. Now if i send 10 requests at the same time with the same code maybe 4-6 will hit the code part after 2. And your window of opportunity is the time it takes to go from 3 to 4. Sometimes certain tasks are put inside async queue, you have a slight delay to your database serv…

Can this issue be prevented if we use the promo code as the table primary key or document ID?

That won't be enough because the promo codes are shared amongst many users. If the promo code became the primary key, then only one user would be able to redeem it.

If you introduced some combination of a user ID and promo code, then it won't prevent a race of one user firing many queries with different promo codes and stacking them up. It would, however, fix the original problem.

Re: Race conditions on Facebook, DigitalOcean and others (fixed)

#70

Post by potatosareok »

MichaelGG wrote: post #61
pyvpx wrote: post #52

Earlier quoted context omitted.

when did eventual consistency equate to race conditions, or even increased susceptibility to race conditions? I don't follow. could you explain your reasoning further?

It's probably just an ease-of-use question. The more guarantees your database can deliver, the easier it is to reason about things and make sure you aren't being caught on a gotcha. It's not necessarily different than using a normal RDBMS, right - you could do a check in SQL outside a transaction and end up writing multiple times. But with an RDBMS, you can easily solve the situation by turning on a transaction and l…

I've always wondered, (but apparently not enough to figure it out by reading the Spanner whitepaper), but how do these systems typically handle it?

I guess if you were using an append only log that recorded the exact timestamp of the transcation, your datastore would eventually reconcile that for example promo code 1 was applied twice. But what do you do then? Rollback the 2nd application of promo code and deduct the credit from user account?

Where would the logic for that be programmed?

Post reply on HN