Answers.Body: <p>This is a great question! <em>(I doubt my answer will do it justice, but I wanted to get the ball rolling.)</em>  </p>
  
  <p>Part of me want to take the position that if automata are smart enough to solve a new captcha, they "deserve" to spam a post. <em>(By contrast the intelligence of the average human who uses social media does not impress me nearly as much;)</em>  </p>
  
  <ul>
  <li>Clearly, making captchas NP-hard is not feasible, as you astutely point out</li>
  </ul>
  
  <p><strong>To me, this basic fact would seem to be an indicator of the impending demise of captchas.</strong>  </p>
  
  <p>Specifically:</p>
  
  <ul>
  <li>Visual captchas are useful b/c they require only basic, human common sense. </li>
  <li>Captchas cannot be too difficult because they must be solvable by the average human</li>
  </ul>
  
  <p>Just based on random sampling of content that drives social media, the average human is not very smart. </p>
  
  <ul>
  <li>My guess is that sites that want to block spam at the gateway will have to adopt some form of biometric validation, like the fingerprint scan on contemporary smartphones.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-06T18:04:21.407Z
Answers.LastActivityDate: 2017-09-06T18:04:21.407Z
Answers.UserDisplayName: DukeZhou
Answers.Body: <p>I think that captchas can be substituted or augmented by questions which require understanding of context, for example:</p>
  
  <p><a href="https://i.sstatic.net/WUe2K.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/WUe2K.png" alt="enter image description here"></a></p>
  
  <p>How many hands keep the rose?</p>
  
  <p>Or</p>
  
  <p><a href="https://i.sstatic.net/69yg6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/69yg6.png" alt="enter image description here"></a></p>
  
  <p>Which number of books under the bench and in hands?</p>
  
  <p>These examples are simple, but they can be improved, for example, by generation of images with random  numbers of objects and their positions</p>
  
  <p>It looks like it will be hard to use CNN to hack such kind of captchas, especially if we have a large amount of different objects and their combinations</p>
  
  <p>In addition, it can be improved by adding more complicated logical questions to compositions on pictures</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-07T20:56:50.900Z
Answers.Text: I like this answer, and will only note that Natural Language Processing is making enormous strides, and I'm not certain overly complex questions will serve the function, as CAPTCHS's have to be understandable to the human ["lowest common denominator"](http://tvtropes.org/pmwiki/pmwiki.php/Main/LowestCommonDenominator).  Another way to put it is that, automata keep getting smarter, but human intelligence stays about the same.
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-08T17:37:52.030Z
Answers.Text: I suspect that a stronger image recognition+NLP AI will eventually be able determine with high confidence that "keep" is synonymous with relevant concepts such as "grasp".  Similarly, the AI should be able to determine that "hands" may be taken to indicate the single hand depicted (typo or determination that only one hand is visible, and therefore relevant.) But even with these simple examples, a growing subset of humans will become confused: i.e. what is the verb tense of "keep"?  Should the phrase be taken to mean that only one of the hands will ultimately possess the rose?
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-09T09:50:31.627Z
Answers.Text: @DukeZhou: I also hope that AI reaches this level soon, because in this case we all will get ticket into a civilization of the second type by Kardashev scale. I described how it's possible to do it with such AI level here - https://ai.stackexchange.com/a/3791/8861
Answers.UserDisplayName: Stepan Novikov
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-11T15:45:05.580Z
Answers.Text: I guess we'll find out in the coming years.  I do think this answer is strengthened by the fact that botnets aren't likely going to have access to the same [degree of rationality](https://en.wikipedia.org/wiki/Bounded_rationality) that the big boys like DeepMind can utilize (supercomputers, unlimited db volume) so they probably won't get smart enough in the near term to solve the type of captchas you propose.  But we can always hope!
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-07T20:21:39.873Z
Answers.LastActivityDate: 2017-09-07T20:21:39.873Z
Answers.UserDisplayName: Stepan Novikov
Body: <p><strong>CAPTCHAs</strong>, which are often seen in web applications, are working under the assumption, that they <strong>pose a challenge which a human can solve easily while a machine will most likely fail</strong>. Prominent examples are identifying distorted letters or categorizing certain objects in images.</p>
  
  <p><strong>Neural networks are threatening this approach</strong>, as they are capable of solving problems that are easy for humans and difficult for classic algorithms. Especially with the incredible results modern CNN architectures have achieved in image recognition during the last years, the established forms of CAPTCHAs won't be able to distinguish a human and a machine using a neural network anymore.</p>
  
  <p><strong>Is this the end of CAPTCHAs as we know them or are there evolved versions available</strong> or at least in the making <strong>that still pose a challenge to modern neural networks</strong>?</p>
  
  <p>Clarification: I am talking about challenges that are feasible for use in web applications and do not have an unjustifiable impact on usability.</p>
  
Tags: <convolutional-neural-networks>
Title: Will CNNs kill CAPTCHAs or can they survive in an evolved form?
UserDisplayName: Demento
ThreadText: # Will CNNs kill CAPTCHAs or can they survive in an evolved form?
  
  (Asked by: username_0 on 2017-09-05)
  
  **CAPTCHAs**, which are often seen in web applications, are working under the assumption, that they **pose a challenge which a human can solve easily while a machine will most likely fail**. Prominent examples are identifying distorted letters or categorizing certain objects in images.
  
  **Neural networks are threatening this approach**, as they are capable of solving problems that are easy for humans and difficult for classic algorithms. Especially with the incredible results modern CNN architectures have achieved in image recognition during the last years, the established forms of CAPTCHAs won't be able to distinguish a human and a machine using a neural network anymore.
  
  **Is this the end of CAPTCHAs as we know them or are there evolved versions available** or at least in the making **that still pose a challenge to modern neural networks**?
  
  Clarification: I am talking about challenges that are feasible for use in web applications and do not have an unjustifiable impact on usability.
  
  **Tags:** convolutional-neural-networks
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2017-09-07. Score: 3 | Accepted answer
  
  I think that captchas can be substituted or augmented by questions which require understanding of context, for example:
  
  [![enter image description here](https://i.sstatic.net/WUe2K.png)](https://i.sstatic.net/WUe2K.png)
  
  How many hands keep the rose?
  
  Or
  
  [![enter image description here](https://i.sstatic.net/69yg6.png)](https://i.sstatic.net/69yg6.png)
  
  Which number of books under the bench and in hands?
  
  These examples are simple, but they can be improved, for example, by generation of images with random numbers of objects and their positions
  
  It looks like it will be hard to use CNN to hack such kind of captchas, especially if we have a large amount of different objects and their combinations
  
  In addition, it can be improved by adding more complicated logical questions to compositions on pictures
  
  > **Comments:**
  > **username_1**: I like this answer, and will only note that Natural Language Processing is making enormous strides, and I'm not certain overly complex questions will serve the function, as CAPTCHS's have to be understandable to the human ["lowest common denominator"](http://tvtropes.org/pmwiki/pmwiki.php/Main/LowestCommonDenominator).  Another way to put it is that, automata keep getting smarter, but human intelligence stays about the same.  
  > **username_1**: I suspect that a stronger image recognition+NLP AI will eventually be able determine with high confidence that "keep" is synonymous with relevant concepts such as "grasp".  Similarly, the AI should be able to determine that "hands" may be taken to indicate the single hand depicted (typo or determination that only one hand is visible, and therefore relevant.) But even with these simple examples, a growing subset of humans will become confused: i.e. what is the verb tense of "keep"?  Should the phrase be taken to mean that only one of the hands will ultimately possess the rose?  
  > **username_2**: @username_1: I also hope that AI reaches this level soon, because in this case we all will get ticket into a civilization of the second type by Kardashev scale. I described how it's possible to do it with such AI level here - https://ai.stackexchange.com/a/3791/8861  
  > **username_1**: I guess we'll find out in the coming years.  I do think this answer is strengthened by the fact that botnets aren't likely going to have access to the same [degree of rationality](https://en.wikipedia.org/wiki/Bounded_rationality) that the big boys like DeepMind can utilize (supercomputers, unlimited db volume) so they probably won't get smart enough in the near term to solve the type of captchas you propose.  But we can always hope!  
  
  ---
  
  ### Answer by username_1 on 2017-09-06. Score: 1
  
  This is a great question! *(I doubt my answer will do it justice, but I wanted to get the ball rolling.)*
  
  Part of me want to take the position that if automata are smart enough to solve a new captcha, they "deserve" to spam a post. *(By contrast the intelligence of the average human who uses social media does not impress me nearly as much;)*
  
  * Clearly, making captchas NP-hard is not feasible, as you astutely point out
  
  **To me, this basic fact would seem to be an indicator of the impending demise of captchas.**
  
  Specifically:
  
  * Visual captchas are useful b/c they require only basic, human common sense.
  * Captchas cannot be too difficult because they must be solvable by the average human
  
  Just based on random sampling of content that drives social media, the average human is not very smart.
  
  * My guess is that sites that want to block spam at the gateway will have to adopt some form of biometric validation, like the fingerprint scan on contemporary smartphones.
  
  
  ---
  
  