Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I was just thinking about how recaptcha is getting harder when I thought about another posible solution. Images won't last forever so we will need something else some day - like human logic or emotion. Google and others are trying grouping images by category (find the image that doesn't belong) but that requires a large amount of images and doesn't work for the blind.

Anyway, what if a massive collection of text was gathered (public-domain books from each language) and a sentence was shown to the user with 1 (or 2) words that were a select box of choices? Only computers that knew correct English/Spanish/German grammar would be able to tell which of the words belonged in the sentence.

Would there be any problems with this approach? I would assume that it would be easy enough for anyone that knew the language that the sentense was displayed in to figure out the answer easier than trying to read the reCAPTCHA text. Plus, storing an insane number of sentences would only take a couple gigabytes of space and wouldn't take anywhere near the CPU time creating images/audio takes. In other words, anyone could host their own captcha system with minimal impact on system performance.

Is there a problem with this approach? More specifically I'm looking for the main problem with this approach.

migrated from stackoverflow

share|improve this question
4  
I tried doing one of the listening ones the other day as I was struggling with the visual ones on some sight. The sound was completely incomprehensible. All getting a bit silly, isn't it. –  Alison Mar 8 '11 at 19:46
2  
Or you could try to administer a Voight-Kampff test as a captcha. It seems to work on replicants... –  FrustratedWithFormsDesigner Mar 8 '11 at 19:58
4  
This sounds like an xkcd comic.... xkcd.com/810 –  Tyanna Mar 8 '11 at 20:10
1  
Well, firstly, not everybody may know a language perfectly, and many users may not be native speakers (e.g. me). But, most importantly, I wouldn't rely too much on the assumpion that all humans are endowed with logic. Experience taught me that in certain cases human logic is but a myth.. So chance may be that you would end up filtering out humans and letting bots through.. –  Lucius Mar 8 '11 at 20:45
2  
I don't know, but I've seriously considered buying captcha-breaking software just to legitimately log in to some sites. :) –  davidhaskins Mar 8 '11 at 20:48
show 6 more comments

9 Answers

up vote 6 down vote accepted

First, I give you IBM's Watson. I think computing has far exceeded the simple fill in the blank problems of language.

Next, I give you all the Spelling/Grammar checkers implemented in software. Determining if a word is grammatically correct in a sentence is solved in > 90% of cases. I'll even stick my neck out and say they are better at literacy than most humans I know.

I don't think your CAPTCHA idea will work as well as you are expecting...

share|improve this answer
    
Spelling and grammars obey to rules, which even if obscure, do work. On the other hand, it would definitely stirr research in that direction too... –  Matthieu M. Mar 9 '11 at 18:10
    
Assuming the high rate of correct usage by many spell-checkers, and the probability of guessing the remaining words as Jeff mentioned, I believe this would greatly reduce the effectiveness of the CAPTCHA. I think it would work fine for many smaller sites - but not one that spammers would mind spending a little time trying to break. Computers already speak better language than humans - spell-checkers prove that. –  Xeoncross Mar 10 '11 at 15:49
add comment

Let's see, how long would it take to always select the first choice and eventually get it right?

share|improve this answer
3  
Ha, the base case for my own overengineered response. But, yes, this is why multiple-choice CAPTCHAs are silly. –  Meredith L. Patterson Mar 8 '11 at 20:02
    
Certainly a problem that needs to be addressed. However, for now, my sites employ IP rate limiting and failure logging. Unless the spammer has a large-unrelated network (same as a distributed DoS) I would catch him. –  Xeoncross Mar 8 '11 at 20:05
    
You wouldn't even give someone 3 chances? –  JeffO Mar 8 '11 at 20:07
    
3? I'm thinking more like 40 hits in 30mins before I ban them. –  Xeoncross Mar 8 '11 at 20:17
2  
Suppose wrong answer gives you 10 minute penalty and good answer reduces penalty by 5 minutes. If your penalty is greater than zero, you enter penalty mode. The penalty mode means application requires you to pass captcha before you reach any functionality. A brute force bot will reach a few years of penalty in no time, while human can (given clear instructions) recover from initial mistake in two steps. –  Jacek Prucia Mar 8 '11 at 21:07
show 2 more comments

If you are pulling sentences from public domain books, a bot wouldn't need to know anything about grammar. It would merely need to index those same sentences and do a search to find which word the actual sentence used. And that assumes that you reasonably solve the problem Jeff O suggested where you can circumvent the problem by guessing the first option every time.

Plus, many of the sentences in the universe of public domain books would be inappropriate for this sort of endeavor. Many would be ambiguous without context. Many would contain objectionable content (imagine presenting a random sentence from Huckleberry Finn). So you'd have to have invest a decent amount of effort to get to a set of sentences that won't be offensive and won't be ambiguous. If you accept that some sentences will be ambiguous, you lose much of the ability to punish bots for incorrect guessing.

share|improve this answer
add comment

A more challenging problem for bots would be to remove a word from a sentence, then present a choice between four different words of the same part of speech. (E.g., remove a noun; which of these four nouns fits best here?)

Tagging and parsing algorithms aren't perfect, but corpus-based approaches have gotten to the point where you can train up a parser well enough to help you beat the odds on a CAPTCHA with commodity or open-source software. (When you're spamming in volume, it's okay if some messages don't get through, as long as enough of them do to increase your overall success rate.)

Computers aren't as good with semantics yet though.

share|improve this answer
    
Yes, I was thinking about the word being a certain part of speech with matching PoS replacements since I have worked in automated text parsing and can see a compute beating this system if the choice of correct words was obvious. Then again, the less obvious - the harder for non-[language] speakers to answer. –  Xeoncross Mar 8 '11 at 20:08
    
Of couse, there are times when people aren't so great with semantics... –  FrustratedWithFormsDesigner Mar 8 '11 at 20:59
add comment

Most of the spam I get these days is actually not bot-generated. I get a lot of spam coming from third-world countries where people are hired for a few cents an hour to post messages on forums and blogs and such.

No system which differentiates between humans and computers will stop this.

For that reason, I've totally done away with CAPTCHA on my sites. Instead, I have a fairly simple javascript-based solution (basically, Javascript running on the client rearranges fields so that if you post with Javascript turned off, it fails). This stops 95% of bot spam, but obviously has no effect on the human spam - but then, neither would a CAPTCHA.

share|improve this answer
    
I'm starting to see more and more sites that simply require a checkbox with a random id be clicked else a post isn't added, or a text printed somewhere on the page to be entered into a randomly named input field. Works far better than captcha, and is more userfriendly. –  jwenting Mar 9 '11 at 7:20
add comment

Only computers that knew correct English/Spanish/German grammar would be able to tell which of the words belonged in the sentence.

The answer could become subjective (it is not in reality subjective but lack of language concepts spans all societies) and difficult for those who do not speak the language natively.

If there is a finite list of grammatical rules (which every language has) being presented then it simply becomes an algorithm; approachable now by any machine willing to implement the algorithm.

share|improve this answer
    
And what about people who don't fully understand the language that the sentence is in? Will they not be able to pass the captcha? –  FrustratedWithFormsDesigner Mar 8 '11 at 19:51
1  
Good point, but it's the same answer as What about people who don't fully understand the text in the reCAPTCHA image? –  Xeoncross Mar 8 '11 at 20:03
2  
@Xeoncross There is a difference. The text in a typical CAPTCHA is abstracted. It's not that a user doesn't know that A == A; it's the presentation. The problem exists in the fact that the abstraction unfortunately removes legibility in the hope of creating a gap between what a human versus a machine can understand. It is basic in nature. An A will always equal an A. When you bring grammar into the mix you change the approach. You are now assuming each and every individual is at a given grade level of comprehension with regard to the language being used. –  Aaron McIver Mar 8 '11 at 20:46
1  
I must admit that I was rather excited by your analyses. Not only does it stop spam bots - but you have to be semi-literate to leave a comment! That would be so awesome! ;P –  Xeoncross Mar 8 '11 at 22:01
1  
@Frustrated: Some of us would consider that a feature, not a bug. ;) –  Mason Wheeler Mar 8 '11 at 23:57
add comment
  1. All captchas are susceptible to captcha farming.
  2. Multiple choice is too easy to solve by random trying. (As pointed out by others.)

But ignoring these serious gotchas, there is the problem of languages.

Agglutinating languages like Hungarian or Finnish lend themselves easily to this kind of captchas, because words can have many suffixes and each one serves a different purpose in the sentence (e.g. the same noun has a different suffix when used as an object or a subject) However the rules are only complicated for humans, a machine will find the correct one in a few tries.

Isolating languages (English being an approximate example, Mandarin Chinese a much cleaner one) are even worse, as grammar is mostly dictated by position in the sentence and not word form.

Fusional languages like Russian or Greek probably pose yet another set of problems and so on.

To sum it up, linguistic riddles that translate well and are hard to guess randomly are notoriously hard to find. It's probably much easier to concentrate on semantics, than syntax. For example, "Continue the following sequence: Thursday, Wednesday, Tuesday..." or "bake, fry, roast..." and so on.

share|improve this answer
add comment

The usual idea behind a captcha is that it should stop bots almost all of the time. A multiple choice between N answers stops the bot only (N - 1)/N of the time, and so the bot will get through in an average of N tries.

You can implement time-outs for wrong captcha answers, but you can't be too stringent about this without seriously inconveniencing people who aren't good English (or whatever) speakers or have problems with select boxes (shaky hands, bad mice, other handicaps). What's more, time-outs are not going to stop a botnet, since the guesses can come from different IPs.

Moreover, how do you make sure there's only one legit answer? A randomly selected sentence from Project Gutenberg may make sense with several randomly selected nouns, but only one is the right answer.

share|improve this answer
add comment

All you're doing is making it harder for humans to use your site, while for the bots you're not adding any obstacles at all.

What you should rather focus on is creating a mechanism that automagically detects whether something that's posted is spam, and block the post if it is (deferring it to human moderation for example, and giving the poster a message to that extent).

CAPTCHAs have got to the point where they're so annoying I tend to ever more avoid sites using them, and many with me. This especially as they are widely known to have no effect on spambots whatsoever.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.