Are there theoretically linguistic inputs that could send an NLP algorithm into infinite loops or break the chatbot?

Question

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 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.

Answer 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 issues should happen.

Answer 2

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.
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).
   • 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.