Paid Advertising
web application security lab

Why the turing halting problem dictates XSS filter evasion

I’ve put a lot of thought into why anti-virus is like an IDS (intrusion detection system) which is like mod_security and web application firewalls. Like all IPS (intrusion protection systems) you have to know what you are looking for. There are two types of detection that are widely accepted. The first is signature based. That means something as simple as looking for a SCRIPT tag in a URL parameter. The second is anomaly based, which is where you might see something like the webserver returning the string “document.cookie” when you had never seen it return something like that from that application before.

Both of these types of detection are pretty flawed. Both rely on a type of detection that can be easily circumvented. But why? There is a common theory amongst the cryptographic community called the Turing Halting Problem. The basic theory was based off the turing machine (a very simple computer) which given certain inputs would grind to a halt. Once the combination of inputs was detected they’d write that combination down. They’d know not to use that set of inputs in the future to avoid the computer “crash”. Then they’d run it again and when they found the next set of inputs that halted the machine they’d write it down, and so on. The end result is that they could tell you what not to do based on experience, but they couldn’t tell you the next set of inputs that would case the same problem.

This is the same problem anti-virus vendors and web application firewalls face. They know what has caused problems in the past, and they probably know a few variants of the same exploit code or vector, but they cannot know what they have not seen. In this way the obfuscated vectors that the community comes up with will almost always circumvent the existing detection methodologies because of the Turing Halting Problem. Web application firewalls, anti-virus detection and IPSs in general all suffer from this deficiency.

3 Responses to “Why the turing halting problem dictates XSS filter evasion”

  1. Jeremiah Grossman Says:

    I get what saying saying about the turing/halting/undecidable problem with regards to IDS. Its good to see people, other than myself, looking at this stuff from that point of view. Fully analyzing network traffic for all attacks at all times could very well be defined as one of these types of problems. The trouble we have is proving it in a mathematical sense. And what I’m not too sure of is if XSS filter evasaion IS actually an undeciable problem.

    Technically speaking it would be possible to fully enumerate everything that would result in the execution of JavaScript in a browser. And if we believe we could define that list, then by definition, its not a halting problem but more of a time investment problem. First the upfront research like you’ve done with the XSS cheat sheet that seems never ending. And then the browser vendors keep changing the rules with technology support with each browser revision. So we keep chasing the end of the list.

    Whichever problem it happens to be we still end up at the same place. Never exactly solving the problem, only maintaining the difficulty of XSS filter evasion.

  2. r0xes Says: can block the simple things, but what if I were to enter something like…


    IDS trying to block XSS is completely retarded, and should only be on the software-itself.


  3. RSnake Says:

    That reminds me of this time I was hanging out with one of the FreeBSD authors and he wanted to get a vanity plate that said “FREEBSD” but the DMV rejected it. They said they couldn’t have drug references as part of the plate. They thought it meant “Free Based”.

    Their IDS needs some work, if you ask me. False positives are just as much a problem as anything. Sure, you can block everything, but then even the good things are blocked. Finding that balance is very difficult for companies that want to allow some HTML for their consumers, but nothing malicious. It’s a tough problem.