Is 'looking for all XSS in my code' a solved computer science problem?

Question

I have a fundamental theory question. Is looking for cross-site scripting a solved computer science problem? Or is it an open problem? Does it approximate the halting problem, injection problem or similar known CS problems?

Or is XSS not intractable but just tedious to find and fix as there are many possible sources and sinks to a scripted web page, poor programmer understanding of the vulnerability, etc or the plethora of web technologies out there that impede the solution to a sound solution? (I'm thinking about content security policy as an equivalent of NX bit in native code).

Anyone can point me to any resource (academia included) would be much appreciated.

Edit 2020-03-10: The XSS problem is far from being solved despite it being 'easy' to solve as a technical problem. According to HackerOne, it is the by far the most preferred attack vector. Further in 2019 it is increasingly the favourite attack vector among white-hats: 38% in 2019 vs 28% in 2018.

Answer 1

I am no expert on formal proofs, but I can at least point you in the right direction.

Searching for XSS vulnerabilities comes down to three elements:

1. A finite set of untrusted entry point. XSS can only happen, if you process untrusted data. The first thing you have to do is identify all untrusted entry points. In a web application those are usually GET and POST parameters as well as headers. But there are potentially many more indirect / second order entry points like environment variables, untrusted database content, data fetched from untrusted local files or from remote, etc. If those sources are considered trusted or not, depends on your architecture and the attacker types you want to protect against.
2. A finite set of locations where dynamically generated data is included in a server response (i.e. the website). To trigger a XSS vulnerability, an attacker must be able to create malicious output that is interpreted by at least one browser engine as script code. To identify all locations where this can happen, you have to analyze the output layer of the application and check where dynamically generated output is injected into the website.
3. All paths between untrusted entry points (1) and potentially vulnerable output locations (2). Performing data flow analysis allows you to find all paths that connect (1) and (2). Each path has the potential to allow XSS, as it connects untrusted input to a potentially vulnerable data output location.

That's the model you are working with. The next step is tracing all identified paths and check for functions that validate or encode the data in a way that prevents XSS. This is tricky, because different types of output locations may require different types of filtering / encoding to protect against XSS. Only the correct method can protect against exploitation of a specific path.

Please note that I deliberately ignored additional protection mechanisms against XSS, which can be considered a second line of defense.

So what does this mean? Yes, you can find all XSS vulnerabilities if you are able to identify all untrusted entry points, all dynamically generated data output locations and all paths between them, including the verification that certain functions protect against specific types of XSS. So why isn't there a single source code scanner out there that will find all XSS vulnerabilities in a complex website?

Fulfilling any of those requirements is highly complicated in practice. Today's web applications consist of a huge amount of different frameworks, containing millions of lines of code. Entry points - especially second order entry points - are easily overlooked and often vast. Data flows are highly complicated, passing through a lot of frameworks and functions. Modern coding patterns (e.g. reflection) make data flow analysis even harder. Judging, if a validation function really protects against a specific type of XSS, can be complicated for certain types of input.

So while it seems to be feasible in theory, there is still no source code scanner out there, that can handle all those difficulties. Which means, no one had yet been able to implement this seemingly simple approach for a wide variety of technology stacks.

Answer 2

It's not a solved problem as of 2020 but we're getting closer. Although XSS vulnerabilities are common, they generally occur in sites that don't follow basic security practices. When sites do follow good security practice, they are rare. A big part of the problem is that there are dozens or hundreds of potentially vulnerable inputs even in quite a simple application.

The main approaches to fix XSS are:

• Developer tools that do automatic escaping. e.g. with JSP the developer needs to remember to escape every input, but with the newer ThymeLeaf, escaping is automatic. This isn't a 100% fix though as there are page contexts (e.g. within a <script> tag) that need additional escaping. Also, sometimes developers need to turn off escaping, and that can introduce a vulnerability.

• Browser improvements. Content security policy is the main one, and there have been other measures, such as removing scripting contexts from CSS and tightening up content sniffing. Other security measures, such as same-site cookies can help with XSS too.

• Pen test / audit tools. Both DAST and SAST are pretty good these days, certainly if you buy commercial tools, and increasingly for open-source too. Neither are 100%. DAST often fails to find hard-to-reach corners of an application. SAST struggles with the wide variety of developer technologies. By the way, in theory SAST suffers from the halting problem, although in practice it's not a problem 99% of the time.

• Active defences - such as WAFs. These have generally had a pretty bad time blocking XSS. They generally block automated attacks, but a skilled manual attacker can usually get around them. There have been some cases of WAFs attempts to defence XSS actually introducing XSS flaws.

Of course, XSS is a completely solved problem if you don't use HTML, which is an option for mobile apps.