Answers.Body: <p>While it is certainly possible to have NLP algorithms ending up in infinite loops, chatbots will typically not be affected by this.</p>
  <p>A first-year pitfall you learn is in the construction of grammars. If you do a top-down analysis of a sentence, the following grammar rule will send it into an infinite loop:</p>
  <blockquote>
  <p>NP -&gt; NP of NP | det N | N</p>
  </blockquote>
  <p>This allows a noun phrase to be expanded to &quot;noun phrase <em>of</em> noun phrase&quot;; and the parser next tries to expand the non-terminal symbol 'NP', which handily expands to a rule which has the very same symbol at the beginning.</p>
  <p>However, modern day chatbots don't tend to use parsers, as their input is not commonly well-formed enough to allow application of grammars. They either use pattern matching (Eliza-style), or machine learning, neither of which would be susceptible to this issue.</p>
  <p>And commercial chatbots are typically tested with all kinds of junk input to make sure they don't break or crash (In my previous job I designed chatbots for five years).</p>
  <p>One possibility I can think of is if the pre-processing step is poorly coded, that using eg non-ASCII characters or extremely long nonsense words etc might lead to problems (eg buffer overflows), but modern programming languages make it increasingly difficult to actually break anything this way. And as you rightly say, you would separate input from executable code, so no <a href="https://xkcd.com/327/" rel="nofollow noreferrer">Bobby Tables</a> issues should happen.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-02T08:22:24.457Z
Answers.LastActivityDate: 2021-09-02T08:22:24.457Z
Answers.UserDisplayName: Oliver Mason
Answers.Body: <p>It all depends on your architecture.</p>
  <h3>What a chatbot is made of?</h3>
  <p>Most of the current commercial AI chatbots have an architecture somehow like this:</p>
  <pre><code> ┌────┐┌─────────┐┌────────┐┌─────────┐┌────────┐┌───┐
   │User││Messenger││Back-end││NLP (NLC)││Database││API│
   └─┬──┘└────┬────┘└───┬────┘└────┬────┘└───┬────┘└─┬─┘
     │        │         │          │         │       │  
     │Message │         │          │         │       │  
     │───────&gt;│         │          │         │       │  
     │        │         │          │         │       │  
     │        │ Message │          │         │       │  
     │        │────────&gt;│          │         │       │  
     │        │         │          │         │       │  
     │        │         │ Message  │         │       │  
     │        │         │─────────&gt;│         │       │  
     │        │         │          │         │       │  
     │        │         │  Intent  │         │       │  
     │        │         │&lt;─────────│         │       │  
     │        │         │          │         │       │  
     │        │         │       Intent       │       │  
     │        │         │───────────────────&gt;│       │  
     │        │         │          │         │       │  
     │        │         │       Answer       │       │  
     │        │         │&lt;───────────────────│       │  
     │        │         │          │         │       │  
     │        │         │          │ Call    │       │  
     │        │         │───────────────────────────&gt;│  
     │        │         │          │         │       │  
     │        │         │          Response  │       │  
     │        │         │&lt;───────────────────────────│  
     │        │         │          │         │       │  
     │        │ Answer  │          │         │       │  
     │        │&lt;────────│          │         │       │  
     │        │         │          │         │       │  
     │ Answer │         │          │         │       │  
     │&lt;───────│         │          │         │       │  
   ┌─┴──┐┌────┴────┐┌───┴────┐┌────┴────┐┌───┴────┐┌─┴─┐
   │User││Messenger││Back-end││NLP (NLC)││Database││API│
   └────┘└─────────┘└────────┘└─────────┘└────────┘└───┘
  </code></pre>
  <p>So the question is: What are the vulnerable points here?</p>
  <ol>
  <li>Messenger: Theoretically, the messenger should only forward the message, but it's usual for the front-end to have some security flaws, like <a href="https://www.androidpolice.com/2018/05/05/emoji-message-crashes-android-app-no-big-deal/" rel="nofollow noreferrer">breaking on some special characters</a>.</li>
  <li>Back-end: If the message is not validated / sanitized, there might be some vulnerability to SQL injection.</li>
  <li>Most of the AI behind a Chatbot are NLC (Natural Language Classifiers), NER (Named Entity Recognition) and other specific API (like a weather forecast). I don't see how the Machine Learning models can be attacked directly.</li>
  <li>But if the Chatbot directly accepts (or uses NER to extract) a user input, it could be used to extend the attack into Database or API's (Like: &quot;<code>My name is Robert'); DROP TABLE students;--</code>&quot; - inspired on this <a href="https://xkcd.com/327/" rel="nofollow noreferrer">xkcd comic</a>).
  <ul>
  <li>The NER extracts the name=&quot;<code>Robert'); DROP TABLE students;--</code>&quot;</li>
  <li>Is is used as a query parameter for the Database <code>Check if name exist in Database</code></li>
  <li>The Database trusts your Back-end.</li>
  <li>The Back-end attacks the Database with the injected code.</li>
  </ul>
  </li>
  </ol>
  <hr />
  <h3>Paradox Loop</h3>
  <p>Another (more philosophical) way to bug the AI would be trying to cause a <strong>paradox loop</strong> which is well explained on <a href="https://ai.stackexchange.com/questions/1768/could-a-paradox-kill-an-ai">this link</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-04T03:04:01.507Z
Answers.Text: Good answer! I especially appreciate the note on database hacking.  I'd assume one could scramble that good, and even mess it up if it's still learning.  (But most, unlike myself, don't seem to find talking to bots interesting.)
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-04T03:07:38.827Z
Answers.Text: I assume search functions are going to be truncated by some time limit, allowing an escape hatch from any non-computable function that may be imposed on the rationality simulating the human rationality?  I tend to think in the combinatorial sense of games and tricking the algorithm to find exploits, similar to what a Q/A tester does, but attempting to bridge a semantic gap to the function under the output.  (But that may be all just crazy talk;)
Answers.UserDisplayName: DukeZhou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-05T11:54:36.967Z
Answers.Text: Actually, most Machine Learning algorithms have an indefinite (and long) time during training, where they are wrapped in a (long/infinite) loop. But the evaluation is usually very straightforward, with no loops whatsoever, meaning there is not even where to get trapped.
Answers.UserDisplayName: Andre Goulart
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-02T16:26:47.727Z
Answers.LastActivityDate: 2021-09-02T16:26:47.727Z
Answers.UserDisplayName: Andre Goulart
Body: <p>I was asked an interesting question today by a student in a cybersecurity and information assurance program related to getting spammed by chatbots on snapchat.  He's tried many conventional means of blocking them, but he's still getting overwhelmed:</p>
  <ul>
  <li>Theoretically, are there lines of code that could disrupt processing, such as commands or syntactic symbols?</li>
  </ul>
  <p>My sense is no — the functions would be partitioned such that linguistic data would not execute. But who knows.</p>
  <ol>
  <li>Many programmers are sloppy.</li>
  <li>I've had friends in video game QA produce controller inputs that programmers claim is impossible — until demonstrated.</li>
  </ol>
  <ul>
  <li>Theoretically, is it possible to &quot;break&quot; a chatbot in the sense of the <a href="https://bladerunner.fandom.com/wiki/Voight-Kampff_test" rel="nofollow noreferrer">Voight-Kampff test</a> thought experiment?</li>
  </ul>
  <p>This was, of course, popularized via one of the most famous films on AI, BladeRunner, adapted from one of the most famous books, ElectricSheep, and extended recently via WestWorld. In these contexts, it's a psychological test designed to send the automata into loops or errors.</p>
  <p>My question here is not related to &quot;psychology&quot; as in those popular media treatments, but linguistics:</p>
  <ul>
  <li>Are there theoretically linguistic inputs that could send an NLP algorithm into infinite loops or produce errors that halt computation?</li>
  </ul>
  <p>My guess is no, all the way around, but still a question potentially worth asking.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-02T04:41:24.103Z
Comments.Text: I think it depends on the algorithm. If you use a neural net, no input will make it stop executing (unless you break the underlying code with integer overflows and cause it to crash like that, but that would be incredibly easy to prevent with sanitization), but you could certainly give it seemingly normal looking inputs that produce bogus outputs with adversarial attacks: https://en.wikipedia.org/wiki/Adversarial_machine_learning
Comments.UserDisplayName: Recessive
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-02T14:14:24.153Z
Comments.Text: Spam bots don't tend to use AI.
Comments.UserDisplayName: Criticize SE actions means ban
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-09-02T16:47:38.483Z
Comments.Text: You're asking multiple questions here, although they are related. I would focus on one question. A question can be closed as too broad if it contains multiple questions (and you already know this, of course).
Comments.UserDisplayName: nbro
Tags: <chat-bots><programming-languages><computational-linguistics>
Title: Are there theoretically linguistic inputs that could send an NLP algorithm into infinite loops or break the chatbot?
UserDisplayName: DukeZhou
ThreadText: # Are there theoretically linguistic inputs that could send an NLP algorithm into infinite loops or break the chatbot?
  
  (Asked by: username_0 on 2021-09-01)
  
  I was asked an interesting question today by a student in a cybersecurity and information assurance program related to getting spammed by chatbots on snapchat. He's tried many conventional means of blocking them, but he's still getting overwhelmed:
  
  * Theoretically, are there lines of code that could disrupt processing, such as commands or syntactic symbols?
  
  My sense is no — the functions would be partitioned such that linguistic data would not execute. But who knows.
  
  1. Many programmers are sloppy.
  2. I've had friends in video game QA produce controller inputs that programmers claim is impossible — until demonstrated.
  
  * Theoretically, is it possible to "break" a chatbot in the sense of the [Voight-Kampff test](https://bladerunner.fandom.com/wiki/Voight-Kampff_test) thought experiment?
  
  This was, of course, popularized via one of the most famous films on AI, BladeRunner, adapted from one of the most famous books, ElectricSheep, and extended recently via WestWorld. In these contexts, it's a psychological test designed to send the automata into loops or errors.
  
  My question here is not related to "psychology" as in those popular media treatments, but linguistics:
  
  * Are there theoretically linguistic inputs that could send an NLP algorithm into infinite loops or produce errors that halt computation?
  
  My guess is no, all the way around, but still a question potentially worth asking.
  
  **Tags:** chat-bots, programming-languages, computational-linguistics
  
  > **Comments:**
  > **username_1**: I think it depends on the algorithm. If you use a neural net, no input will make it stop executing (unless you break the underlying code with integer overflows and cause it to crash like that, but that would be incredibly easy to prevent with sanitization), but you could certainly give it seemingly normal looking inputs that produce bogus outputs with adversarial attacks: https://en.wikipedia.org/wiki/Adversarial_machine_learning  
  > **username_2**: Spam bots don't tend to use AI.  
  > **username_3**: You're asking multiple questions here, although they are related. I would focus on one question. A question can be closed as too broad if it contains multiple questions (and you already know this, of course).  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2021-09-02. Score: 1
  
  While it is certainly possible to have NLP algorithms ending up in infinite loops, chatbots will typically not be affected by this.
  
  A first-year pitfall you learn is in the construction of grammars. If you do a top-down analysis of a sentence, the following grammar rule will send it into an infinite loop:
  
  > NP -> NP of NP | det N | N
  
  This allows a noun phrase to be expanded to "noun phrase *of* noun phrase"; and the parser next tries to expand the non-terminal symbol 'NP', which handily expands to a rule which has the very same symbol at the beginning.
  
  However, modern day chatbots don't tend to use parsers, as their input is not commonly well-formed enough to allow application of grammars. They either use pattern matching (Eliza-style), or machine learning, neither of which would be susceptible to this issue.
  
  And commercial chatbots are typically tested with all kinds of junk input to make sure they don't break or crash (In my previous job I designed chatbots for five years).
  
  One possibility I can think of is if the pre-processing step is poorly coded, that using eg non-ASCII characters or extremely long nonsense words etc might lead to problems (eg buffer overflows), but modern programming languages make it increasingly difficult to actually break anything this way. And as you rightly say, you would separate input from executable code, so no [Bobby Tables](https://xkcd.com/327/) issues should happen.
  
  
  ---
  
  ### Answer by username_5 on 2021-09-02. Score: 1
  
  It all depends on your architecture.
  
  ### What a chatbot is made of?
  
  Most of the current commercial AI chatbots have an architecture somehow like this:
  
  ```
   ┌────┐┌─────────┐┌────────┐┌─────────┐┌────────┐┌───┐
   │User││Messenger││Back-end││NLP (NLC)││Database││API│
   └─┬──┘└────┬────┘└───┬────┘└────┬────┘└───┬────┘└─┬─┘
     │        │         │          │         │       │  
     │Message │         │          │         │       │  
     │───────>│         │          │         │       │  
     │        │         │          │         │       │  
     │        │ Message │          │         │       │  
     │        │────────>│          │         │       │  
     │        │         │          │         │       │  
     │        │         │ Message  │         │       │  
     │        │         │─────────>│         │       │  
     │        │         │          │         │       │  
     │        │         │  Intent  │         │       │  
     │        │         │<─────────│         │       │  
     │        │         │          │         │       │  
     │        │         │       Intent       │       │  
     │        │         │───────────────────>│       │  
     │        │         │          │         │       │  
     │        │         │       Answer       │       │  
     │        │         │<───────────────────│       │  
     │        │         │          │         │       │  
     │        │         │          │ Call    │       │  
     │        │         │───────────────────────────>│  
     │        │         │          │         │       │  
     │        │         │          Response  │       │  
     │        │         │<───────────────────────────│  
     │        │         │          │         │       │  
     │        │ Answer  │          │         │       │  
     │        │<────────│          │         │       │  
     │        │         │          │         │       │  
     │ Answer │         │          │         │       │  
     │<───────│         │          │         │       │  
   ┌─┴──┐┌────┴────┐┌───┴────┐┌────┴────┐┌───┴────┐┌─┴─┐
   │User││Messenger││Back-end││NLP (NLC)││Database││API│
   └────┘└─────────┘└────────┘└─────────┘└────────┘└───┘
  
  ```
  
  So the question is: What are the vulnerable points here?
  
  1. Messenger: Theoretically, the messenger should only forward the message, but it's usual for the front-end to have some security flaws, like [breaking on some special characters](https://www.androidpolice.com/2018/05/05/emoji-message-crashes-android-app-no-big-deal/).
  2. Back-end: If the message is not validated / sanitized, there might be some vulnerability to SQL injection.
  3. Most of the AI behind a Chatbot are NLC (Natural Language Classifiers), NER (Named Entity Recognition) and other specific API (like a weather forecast). I don't see how the Machine Learning models can be attacked directly.
  4. But if the Chatbot directly accepts (or uses NER to extract) a user input, it could be used to extend the attack into Database or API's (Like: "`My name is Robert'); DROP TABLE students;--`" - inspired on this [xkcd comic](https://xkcd.com/327/)).
     * The NER extracts the name="`Robert'); DROP TABLE students;--`"
     * Is is used as a query parameter for the Database `Check if name exist in Database`
     * The Database trusts your Back-end.
     * The Back-end attacks the Database with the injected code.
  
  ---
  
  ### Paradox Loop
  
  Another (more philosophical) way to bug the AI would be trying to cause a **paradox loop** which is well explained on [this link](https://ai.stackexchange.com/questions/1768/could-a-paradox-kill-an-ai).
  
  > **Comments:**
  > **username_0**: Good answer! I especially appreciate the note on database hacking.  I'd assume one could scramble that good, and even mess it up if it's still learning.  (But most, unlike myself, don't seem to find talking to bots interesting.)  
  > **username_0**: I assume search functions are going to be truncated by some time limit, allowing an escape hatch from any non-computable function that may be imposed on the rationality simulating the human rationality?  I tend to think in the combinatorial sense of games and tricking the algorithm to find exploits, similar to what a Q/A tester does, but attempting to bridge a semantic gap to the function under the output.  (But that may be all just crazy talk;)  
  > **username_5**: Actually, most Machine Learning algorithms have an indefinite (and long) time during training, where they are wrapped in a (long/infinite) loop. But the evaluation is usually very straightforward, with no loops whatsoever, meaning there is not even where to get trapped.  
  
  ---
  
  