Careful what you search for!

Hello. Hope you had a nice lunch. Welcome to my talk about careful what you search for. This talk was inspired by a security issue in Django. We received a report that a certain function which may receive untrusted content can take a long time to process if given malicious input. Allowing a denial of service attack. After the fix, the call which used to may take more than twelve seconds now takes about one half of a millisecond. That's actually a

little more than twenty-three thousand times faster. But this vulnerability is just one instance of a whole class of vulnerabilities called Ridos, short for regular experience Denial of service. And it's this class of vulnerabilities that I want to talk to you about today. So hi again, I'm Shai. Um this little elephant is the avatar used everywhere. Um I joined the Django Core team back when that was a thing in 2013, and I've been on the Django security team since 2017. I work as a consultant.

I help organize local Pycons and you can reach me everywhere under these handles. So this talk is basically about regular expressions, also known as regexes. And up until Django 2. 0, uh you had to know regexes to use Django because that was the only way to specify URLs. And these days you don't really have to know regular expressions to use Django. But for this talk I assume that you do know them as a user. So I'm going to start with an introduction to the theory behind regXes

and how they were supposed to be safe to use everywhere. Then explain how the implementations we have diverged from this theory. Then show a little about the of this vulnerability and finally mention what can be done about reduces more generally. So I'm trying to show just enough theory To give you some intuition into where problems might arise and to give those of you who are not familiar with theory a glimpse into what it looks like. I'm going to show some abstract notations, but try to simply Sorry, and wax

over details so that if you're very practical and down to earth, you may feel a little challenged. If you're more theoretically inclined, you may be upset by all the hand waving and I just hope to offend everyone equally. So with regular expressions there's basically two ways we use them commonly, and that's match and search. Search is a little more complicated. So um we'll start just with handling match and we'll bring searching back later. Now when we say match We're talking about matching not just one string

but a set. Or more accurately, finding if the string we're looking at is within the set. A set of strings in this Context is called a language. And theory says we can be efficient if the language has some structure, some order that we can express as patterns according to specific rules. And languages. that fit these rules are called regular languages. Now we go a little more formal and abstract, so brace yourself from some theory. I want to show the rules for construction of regular languages

because they're reflected in the algorithms that are used to check if a string is in a language. So let's start. Regular languages are constructed from atoms by operations. The atoms are what's called singleton languages. These are languages that have each operation Only one string and that string is only one character long. And we also include the empty language that has no strings at all, and the language whose only member is the empty string. The operations that combine languages or sets

to create more complex languages are union, concatenation, and the star which is called clean star. Union here is just plain old set unions. There's not much to say about it. The concatenation of two sets is an operation we don't see. usually. It yields the set of all strings made with a head from the first set and the tail from the second set. The clean star works with only one set. and it returns the joint sequences of strings from the sets

with repetitions. So this means that it almost always yields an infinite language. So let's see that this theory is indeed relevant to the regexes we see in code. Let's assume that basic regexes, regex patterns, indeed define regular languages. as I've shown them here, and see how the ways we can combine them with operations or combine the regists are expressed with these operations. So assume the regex X matches the language L of X

and the regex y matches LY, then we have obvious parallels from regexes to the to the basic language operations. If we just take the two regxes and stick them together, we get an expression that matches the concatenation language. If we join them with a bar, then Then we get the union and the star is the claim star. But there are also other shorthands. For example, character classes are unions of singleton languages. So the A B C here is the union of A and B and C and backslash D is the union of all the digit singleton languages.

Competition operators can be constructed from basic operations already in Regex land. So uh there's obviously also a mapping to the operations. So So basically with singleton languages and just three operations, we cover most of the regixes. So now we come to the fun part. It turns out that But given a regular language, we can always build a state machine to check if a string is within the language. Let's see of what kind of machine we have in mind.

Machine would have a set of states. One of them is marked as a start state, and some of some of them are marked as accepting states. And on it starts in the start state, and on each step it reads the character. from the strings and follow the corresponding arrow to the next state. If there's no arrow with the uh with the given character, then we quit and say no. If we're in an ac if If we're sorry, um when the string ends, we check if we're in an accepting state. And if we are, we say yes, otherwise again we say no. Such a machine,

Once we build it, it's easy to execute in time linear in the length of the text. There's no memory other than the states. There's no complex computation. This, in essence, is series linear time. I promise. But there's going to be a twist. So let's go into more details. So to see that we really can do all these regXs with or regular languages. With state machines, let's see how we build them for the regular languages and we'll do it recursively. So for starters, for a base of the recursion, it should be clear that we can

Build machines for the singleton languages. Now it's left to see how we combine machines to account for the operations. So if we have a statement Machine for a language X and another state machine for a language Y, we can make a machine for their concatenation by uniting the accept states of X with the start state of Y. Then we get one machine. machine which basically checks first X and then Y. If we have a union then in general we'd want to compose a machine that can go either way.

Between its components. But there is a problem, and here comes the twist. The problem is that the choice is not always possible based on just the first character. So for example, if we build a machine for the union of AB with AC, if the machine reads A, it needs to guess. Now in theory We can pretend that the machine just goes both ways at the same time, following each path until it fails. This is called a non-deterministic state machine, one whose future, so to speak, is is not determined at the choice point.

And by the way, if you're familiar with the P equals NP question, the N in NP stands for non-deterministic. and it's exactly this kind of non-determinism. So to make this clearer, let's see an example of a non-determination machine in action. And let's look at exactly this the machine that we've seen before. Checking the text AC. It starts at the start date. Then Then it reads the A and follows both arrows marked A. So now it's in two states

Then it reads C. On the top branch, it can't proceed, so that state goes nowhere. But on the bottom, it can proceed to an accepting state. So you may say, okay, that's all fine in theory, but you've promised us a simple deterministic state machine that can go in linear time, not some kind of weird magic. And And um we'll deal with this shortly. But before we do, let's just finish the operations. We've handled union, we've handled concatenation, there's one more left. So By assuming we can detail

assuming we can deal with non-determinism, we can implement a clean star by adding an option to go back to the start of the machine. When we reach the end. That is, just like the machine we've seen. Before could follow two branches at the same time. This machine has a choice if it wants to loop or not to loop, and it can be in two states, two separate states on the same branch at the same time. So, how do we deal with non-determinism? There are at least two known ways to handle non-determinism while keeping the execution time linear. The first is to build an equivalent deterministic machine.

That is a regular state machine. And that is done by multiplying the states. And I won't get into details, but this is always possible. The machine can get exponentially larger but once we finish building it execution is again in linear time because it's just like the regular machines. Or we can use a different execution strategy. where we we really hold a set of states at the same time and uh proceed them with them in parallel. So to make this execution strategy more concrete This is the general idea for the change in execution.

For the single state case, we'd have on each state a table that tells us which next state to go to for every character. Through the text, moving from state to state until the end. For multiple states, we change the values in the tables to sets of states and hold a set of states at each step. This means that when we proceed from for to the next state, we need to collect states. And in the end we need to check for an accepting state in a set. But it's not that much different. And an important point Is that while the processing of each character is longer than we've seen before, the number of steps needed for each character is still bound by a constant.

At worst, the number of all the errors in the machine. So it may be slower, but it is still linear in the length of the text. So there's one last thing I still owe you and that's search with regular expressions and um the difference between search and match from a theoretical point of view is very small because searching is just like matching but with anything at in the beginning or anything added in the end. So it's really not that different and um everything is handled. So

theory tells us that we can always use regexes, whether we want to search or match, time that is linear in the length of the text. We may need to work hard to prepare for it, and complex expressions may uh require more effort but still it should all be linear. Our system should only spend a very long time processing something if the processing a text if that text is very long. Readers just shouldn't be a thing. So what went wrong? Well, you know, in theory there's no difference between theory and practice, but in practice

Practice there is. And there are two major ways here in which the practice differs from the theory. And they are linked to each other. The first is implementation. Specifically the implementation of non determinism. We've mentioned two ways to implement non deterministic state machines, but most of the Regge libraries actually use a third way, which is Backtracking. That is, whenever our machine needs to make a choice, we remember the point and just go down one of the paths. If it works, great. If it doesn't work, we go back

to the choice point and try another path. So let's see the same basic machine that we've seen before, now trying to uh check the string AA. So we start with the same thing. Start again at the start state. We read an A, we follow one of the st arrows, then we look at the other A and say, Oh, we can't proceed here, so we need to go back to the start. And again we read in we read the A and go to the other one, but again the next character is in no go. So we go back to the start, realize there's no more options, and only now fail.

So why do all these regex libraries use backtracking? One answer is that backtracking is simpler to implement, much more straightforward. Because when you do backtracking, you can always pretend that the choice you're working on right now is the only choice. You don't need to consider other states at the same time. But there is more to it. That leads to the other way in which practice diverges from theory. So far, I've tried to convince you that regular expressions and the regular languages I've shown are basically the same thing. The theory easily covers the practice.

But this is actually not the case. Some features supported by the libraries don't quite fit the theoretic mode. Assertions are scary looking ways to add checks into patterns. And it can be shown that in principle excuse me. In principle, every regex written with assertions can be written without them. So they're essentially nothing more than fancy short ends. However, sorry, the translation to state machines without backtracking is as far as I know an open problem. Nobody has suggested a good way to do this.

With backtracking, implementation is trivial. You want to add a check you just stop where you are and check. Word boundaries are essentially just shortens over assertions. So um I've marked the capital W's different from the small w So you might be able to tell the difference. Um same comments apply. Groups in regular expressions are extremely useful, but there are Have been largely uninterested. While the non-deterministic state machines and their connection to regular languages has been known since the nineteen fifties, it took until the nineteen eighties

to come up with an algorithm which both handles multiple states and take care of groups. Groups make it important not just if a string was matched, but also how it was matched. For example, if you look at the regular expression at the bottom with the two A stars and match it is against a sequence of A's, suddenly it matters how many A's go to the first group and how many go to the second. Back references and conditionals build over groups. Back references match the exact string matched by an earlier group, and conditionals use earlier group matches to make decisions. And I won't get into the details, but these features

allow specifying sets of strings which are not regular languages at all. Um again they are pretty easy to implement with backtracking. Other features like possessive quasifiers and atomic groups, which may be needed with backtracking, are easy to implement with backtracking, but don't even make sense without backtracking. And by the way, these features in Python were only added in 3. 11. But in other languages they've existed for a long time. So everybody uses backtracking. What's the problem? This is the sh

same machine run that we've seen earlier, but we're also showing for each step where in the text we're looking. Note that when we go back to the choice point, it is not just the machine state that is reverted, but also the This means that the complexity is no longer guaranteed to be linear. We have the potential to go through the text again and again for every choice that we make. Now when you look at this example, you may think that backtracking is comparable to the multiple states approach because with multiple states we may need to do multiple steps for each character. And here too, basically we did multiple steps according to the arrows in the machine.

But the conclusion that they're comparable is wrong. Consider searching this regex for look for a tag in a text or equivalent Matching the regis in the second row. The machine must each character, sorry, presents a choice for each of the stars. So the machine Must try for each position every number of open tags, of open brackets, before it moves to the next position. And this means that the time is the text length squared, not No longer multiplied by a constant.

And this is a simple example. It can get much worse. So now we know the playing ground. So let's look at the specific issue that we had in Django. The report was about codes that truncates an HTML fragment to a number of words. The regex, you can see here, tries to match either words or tags. The left arm of the regex should look uh a little familiar, as well as the payload. And uh I should say here that the super Crafted string when I see it in reports usually makes me think of some intricate

like handcrafted details and no, not always. The good news about the report was that the main branch was not affected at all. This code had been rewritten to use the proper HTML parser before the report came in. Bad news was that we couldn't backport the fixing code to the stable branches because uh full rewrite um m might introduce subtle behavior changes and we don't want that in stable branch. The change must be limited and localized. So we tried to find a better regular expression, but we failed.

Couldn't find an expression that would both match all the right strings and not take forever on evil input. The solution in the end was to find was to replace the problem part of the regex by a handwritten search. Search with a regex for an open bracket or a word, and if an open bracket bracket was found, search for the closed bracket as a string. So um we replaced the compiled regus object by a class of our own, which does just that. and uh uses match objects when it can and fakes uh match objects when it can't.

This is the crux of the code simplify the bit representation. We define a partial Reggex, to search for the open bracket or a word, where a word is just a piece of text with no brackets and no white space. And we look for this. If either nothing was found, or the right arm, the group, the word that is not at tag was found, then we just return what was matched. But if the left arm, the open bracket was found, we look for the broken f closing bracket with string find, and if one was found, we fake a match. And this is the fake match class. And the important thing to note about it is that it only implements the parts of the API that are actually used by the code that calls it, and only for the specific argument.

that would be given in the case where it is actually used. So it is only used where we had this regex that has a group in it but it wasn't matched. So group one is always returned empty. And uh likewise for the other calls. The result of all this is that the code which used to call the problem regex doesn't even notice that the thing has been replaced under its feet, and the behavior in general is pretty much guaranteed not to have changed. So to make a computation run 20,000 times faster, just find an n squared algorithm running on large enough input

and replace that algorithm by a linear one. So um I have it from a trusted source that this solution was clever. However, uh a Hebrew proverb characterizes the clever as those who know how to get out of trouble when the wise know better than to step into it in the first place. So uh can we be wise about this? Well a few years ago

Google introduced a library called RET2, which implements regexes with the strategy of holding several states in parallel. means that it has doesn't support assertions, it does it does support groups but not back references. And it has guaranteed linear time. It's not always the fastest, but it's never catastrophic. And uh I've heard that uh it's being considered for inclusion in Django itself. So that's all I have to tell you today. Thank you very much.