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.

  • 1
    I'm not sure if I understand your question. Are you asking if avoiding XSS with proper application design is a solved problem as I read into your title or if finding XSS in existing applications is a solved problems as the question text suggests. – Steffen Ullrich Mar 9 '20 at 8:44
  • 1
    Regardless, I think gigasai might need to add some clarity to the question. Right now it reads as "are there existing processes or approaches to find all possible XSS in any arbitrary code?" And your question seems to confuse "it's solved" with "it's hard". Those are not exclusive concepts. What I think you want to ask is, "is it so Complex of a problem that remediating XSS is not linear or predictable and has that Complexity threshold been studied?" – schroeder Mar 9 '20 at 8:59
  • 3
    I would say that XSS as a technical problem is solved - it is possible to write XSS free code. But XSS as a social problem remains unsolved - we do not know how to get developer to write that code. And it is not possible to say with absolute certainty wheater they did or not. – Anders Mar 9 '20 at 9:55
  • 3
    @anders I would go farther than that. As a technical problem XSS is easy to solve. With something like Angular or React, 95% of you XSS problems are solved simply by using the framework as-intended. You only have to worry when wandering into edge cases. The tricky part is that people often don't realize when they have wandered into edge cases ... – Conor Mancone Mar 9 '20 at 11:54
  • 2
    In order to be formally solved, it first needs to be formally posed. That would be the first place to look, i.e. to see if anyone has managed to state the problem in CS terms. – postoronnim Mar 9 '20 at 15:33

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.

  • Thanks. For 1) and 3) There are also DOM XSS and those about postMessage which are processed by client side. – gigasai Mar 10 '20 at 8:04
  • The inputs don't even really matter. You should just assume that all input is unsafe and therefore apply context-aware escaping to all outputs – Conor Mancone Mar 10 '20 at 10:17
  • Yes, if we talk about prevention. I answered specifically about detection. – Demento Mar 10 '20 at 14:47

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.

  • 1
    CSP is to XSS is like NX bit in CPUs is to Memory-corruption bugs. There are ways to get around XSS using code-reuse much like return oriented programming does. – gigasai Mar 16 '20 at 2:50
  • "There have been some cases of WAFs attempts to defence XSS actually introducing XSS flaws." Would like to know if there are high-profile real-life cases of such? – gigasai Mar 16 '20 at 2:55
  • 1
    @gigasai - That's an interesting link! I will read it thoroughly when I get a minute. I've generally thought that CSP can be stronger than NX, provided you write a tight CSP, but maybe not :( Here's an example of the WAF thing: portswigger.net/research/when-security-features-collide – paj28 Mar 16 '20 at 6:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.