5 ms·
This particular issue (AI performance on captchas) is really quite fascinating. It's an arms race, but the problem is, only one side can win. Google is claiming
by zwegner 13y ago
This particular issue (AI performance on captchas) is really quite fascinating. It's an arms race, but the problem is, only one side can win. Google is claiming they have improved their system in some (understandably) unspecified way, but there's only so far this can go. Captchas need to detect whether someone is human, but it has to work for everyone, ideally, even those with disabilities. Any simple task a human can do will eventually be able to be automated. Tasks that aren't currently feasible to be automated, say some natural language processing tasks, have another problem: scalability. To prevent simple databases of problems -> solutions, the problems need to be generated en masse, and for cheap, which means a computer needs to generate the solutions in the first place. And of course, paying people to just do captchas all day already happens.
The street address/book scan approach that Google uses is interesting in that the exact solution is not known, so they presumably have to be somewhat forgiving in accepting answers (as their machine learning might have gotten it wrong). Perhaps this is what their "risk analysis" refers to--whether their response seems "human" enough according to their data, not necessarily whether it's correct.
I don't see a way around this problem for free services that still preserves privacy (so directly using some government-issued ID is off the table). Maybe some Persona-like digital signature system, where a person can go to a physical location with a government ID, and get a signature that says "Trusted authority X affirms that person Y is in fact a person". Obviously this still has problems, as you need to trust X, and it's a big pain in the ass.
There are parallels to the realm of passwords, which are also becoming obsolete (not that there's a good replacement...). Anything that a human can feasibly remember for a bunch of sites is becoming easier and easier for computers to guess.
So basically, computers are taking over the world, and we can't do anything to stop it. God help us all.
- kevinchen 13y ago> The street address/book scan approach that Google uses is interesting in that the exact solution is not known, so they presumably have to be somewhat forgiving in accepting answers reCAPTCHA presents a known problem and an unknown problem to the user. If the user answers the known one correctly, it assumes that the answer to the unknown problem is correct too. I believe the text-based reCAPTCHAs will accept an answer within a character or two as correct.
- nileshtrivedi 13y agoHumans have had an easy time for a while. Good to finally see some competition. :) On the other hand, why is that we insist on humanity? None of the systems can block a captcha-solving team based in Nigeria. What we need to block is bad behavior by users and not their humanity.
- zwegner 13y agoGood point. I imagine that detecting such behavior will also be pretty difficult. It's one thing in a forum, where you'd maybe want to discriminate against idiots (but that would still leave you open to the problem of shills/sock puppets). But for big companies like Google, would they really want to open that can of worms? Of course, there's a quite relevant xkcd: https://xkcd.com/810/ https://xkcd.com/810/
- im3w1l 13y agoI think a big problem is Sybil attacks. Let's suppose I make a bot that posts thousands of reports of my computer crashing after using product X. To determine if such a post is bad behavior or not, you have to know if the claim is genuine. That can't be determined by the content of the post itself.
- Lambdanaut 13y agoThe suggestion to "go to a physical location to get a trusted government signature" has deeper flaws as well. What's to stop a bot writer from getting a signature and plugging it into his bot?
- toyg 13y agoBlacklisting would soon force him to get hundreds or thousands of signatures, which would slow down the operation. This said, i don't think "trusted authorities" are the way to go - we've seen the failure of that model with x.509, there is no need to repeat it elsewhere.
- zwegner 13y agoPresumably a service would only allow one (or a few) accounts per actual person. The end user will still need some amount of security. I had in mind some challenge-response mechanism, like: Person signs government ID number with public key, presents it to authority Authority signs public key and asserts it belongs to a real human Service presents random number at signup time Person signs the random number with the same public key, and presents the key signed by the authority
- Lambdanaut 13y agoI'm not entirely sure how that would mitigate people from passing the government signed public key to their bot and letting it take over from there.
- zwegner 13y agoThat's what I was referring to with services only allowing one (or N) accounts per person. A spammer could use the signature multiple times, but would need new email providers for every single account. And as an uncle (?) comment points out, there could possibly be blacklists of signatures of spammers shared between providers. That definitely would cause some new problems, of course, but who knows what the future may hold...
- dave_sullivan 13y agoIf you're curious about how the algorithm works, here's a recent talk from one of the authors of the paper where he talks about it: http://www.youtube.com/watch?v=iK3HIIsZGJY&t=1m32s http://www.youtube.com/watch?v=iK3HIIsZGJY&t=1m32s As to your questions, I think the way it's going with these convolutional neural nets, the idea of being able to tell a human from a computer with something like captcha isn't going to work. I'm thinking a captcha that still would work would be a randomly generated natural language instruction that a user has to interpret with some top down reasoning (possibly with a natural text answer). We've still got a ways to go before we can do that really effectively with software.
- bentcorner 13y agoAsk for x BTC on signup, on the promise that it is returned in y weeks. I was going to propose that it's only returned on good behavior, but that gives sites an incentives to harshly police their new user population. Ideally you'd have some sort of service that both parties trust that is holding the BTC.
- dbpatterson 13y agoAnd then anyone who doesn't have extra resources is prevented from using your service... As if it is a trivial amount, spammers will pay it, and if it is non-trivial, then some people won't be able to afford it. Doesn't seem like a great idea.
- roywiggins 13y agoMetaFilter is a web forum that charges $5 to create an account. Between that and aggressive but professional moderation, spam basically doesn't happen since a couple of obvious spam comments and you're permabanned. However, it limits the user population to people with a debit card and $5 to spend. A bitcoin-based solution right now would be even more restrictive, since apart from buying bitcoin in person, you pretty much need a bank account to acquire them.
- daenz 13y ago> It's an arms race, but the problem is, only one side can win. I don't disagree, but although this specific problem can be automated, the arms race will continue as newer problems (requiring uniquely human intelligence) are presented. We can keep moving the bar until the singularity. For example, a captcha: "Pick the most unsafe environment", followed by pictures of a house, a park, a volcano, a bed. To solve this, AI would have to have a mastery of language, a mastery of object identification, and a mastery of the metadata of those objects as they apply to human safety.
- sukuriant 13y agoAt the same time, though, a human would have to have familiarity with all of those objects in the context of their environment. A house doesn't look the same to everyone, nor does a park, bed, etc. People's life experiences can also affect their responses. The problem we would then experience is unintentional prejudice and Western-mindedness in our "are you human" queries, similar to a problem that SATs and other standardized testing methods have been criticized for.
- zwegner 13y agoThat runs into the scalability problem that I mentioned--someone (say, a Mechanical Turk user) can solve that problem once, and put it in a database. To avoid this, there needs to be a way to generate them cheaply, so you pretty much need a computer that can solve the problem in the first place. Basically, my point is that there's no such thing as "uniquely human intelligence". There's lots of problems that fall into that category now, but with the continuing rise of computational power, it's getting harder and harder to find new problems of this sort without excluding a lot of real people.
- adw 13y agoSo that begins to look a bit like the RSA problem, doesn't it? Find a problem which can only be solved efficiently given some "secret" knowledge – where, instead of that knowledge (the prime factors) being secret, the knowledge is something it's easy for a computer to use but hard for it to recognize. I'm probably overgeneralizing, but it's an interesting framing.
- Houshalter 13y agoI can not remember the name of the paper, but researchers have recently discovered that neural networks can fairly easily be disrupted by carefully perturbing the pixels in incredibly slight amounts. Completely invisible to a human, but can ruin the ability of neural networks to classify it.
- chris_va 13y ago> It's an arms race, but the problem is, only one side can win. It's already happening. It turns out humans come quite cheaply, and you can actually solve captchas using humans at very high QPS for very low cost. And people do! Site owners will have to come up with alternate means of "bot" enforcement that does not rely on human vs computer detection.
- User8712 13y agoAgreed, cheap labor isn't hard to find, and there are countless people that would answer captchas all day long for a few dollars. How many captchas could you answer in a day? Let's say you work 8 hours, and answer one every 20 seconds. That's 1,440 captchas answered for $3/day. You get 5 captchas for a penny. If you can make more than a penny off 5 captchas and whatever you're trying to post or accomplish, you have a business.
- 6d0debc071 13y agoI wonder about the computer's ability to figure out what's spam and to manage the visibility of posts from new accounts dependent on its confidence in that. If captcha proves unwinnable, which I agree with you it very well may be, then all isn't necessarily lost.
- BoppreH 13y agoAll captchas I have seen were used to stop spam. The problem with spam is that 1) it's noise and 2) appears in large amounts. Captchas approach the problem 1), by assuring only people can post and then hopefully increase the signal quality. It sucks because it requires mental effort, is hard on people with disabilities, blocks potentially useful bots (see reddit bots) and leads to an arms race. What if we tried to solve the problem 2)? One possible solution is requiring a proof of work. Some computation that requires a few seconds, easily disguised while the user is typing the comment or filling the fields. It's an old idea but I've never seen an implementation in the wild. (yes, it would fail for mobile devices. fall back to captcha or something)
- sugarfactory 13y agoA few seconds of googling gave me this WordPress plugin that requres a proof-of-work when posting a comment: http://wordpress-plugins.feifei.us/hashcash/ http://wordpress-plugins.feifei.us/hashcash/
- michaelt 13y agoIsn't most spamming done by botnets these days, to avoid IP bans? So they have a plentiful supply of CPU cycles? Also, regular users who visited your site without wouldn't install any software, so they'd be running the proof-of-work as slow javascript, while spammers could use GPU or even ASIC acceleration if proof-of-work became widespread.
- frozenport 13y agoIt is only a security problem is somebody keeps track. You can be issued a secure key ('a passport') to make new ids ('HN registration') but nobody needs to know who ('the passport') generated the website specific ids once your key has been used. The passport only gives access to generate further keys.
- twistedpair 12y agoIf the recognition algorithms for numbers and faces in StreetView are so wonderful, why are there so many randomly blurred out bushes and bus stop signs? In a typical frame you can find a row of No Parking signs or parking meters and randomly one of them is blurred out, as if they thought it was a face. Machine learning has plenty of learning left to do.
- Theodores 13y ago> The street address/book scan approach that Google uses is interesting in that the exact solution is not known, so they presumably have to be somewhat forgiving in accepting answers (as their machine learning might have gotten it wrong). In the original captcha algorithm there are two images shown, one where the answer is known and one where the answer is not known. The unknown - the street sign or that extract from an old newspaper - is guessed at by those filling in the captcha. If 90 people say it looks like '11' and 5 people say it looks like '71' and another 5 say it looks like '77' then you can be 90% certain that it is '11'. The machine has therefore 'learned' what that number is, it is '11'. This can continue being used in the captcha however, now that it is known, people will have to type '11' for it. That is how it fundamentally works and why the two snippets of information 'to get right'. You can try it for yourself, get the first one of the street sign deliberately wrong and see if it lets you through.