Hello, my name is Kevin Backhouse, and I'm a security researcher
at Semmle.
This video is about a vulnerability that was found
by my colleague Bas van Schaik
in the rsyslog project.
What I'm going to do in this video is explain a bit
about what the vulnerability was.
I'm also going to show you
how you can use QL to search
for the vulnerability--
the coding pattern that caused this vulnerability.
I'm going to show how easy that is to do in QL.
Rsyslog is an open source logging system maintained
by Rainer Gerhards.
We reported this vulnerability to him and he fixed it incredibly quickly.
I think it was only
about 24 hours between the time
that we reported the vulnerability to him
and the time that he had posted a fix
for it on GitHub.
Something I'd also like to point out
about rsyslog, is that Rainer takes security
or quality incredibly seriously.
He runs all the static analysis
and dynamic analysis tools
that he can get his hands on on this project.
This was a bug that had not been detected
by any of those other tools.
That shows the value of Semmle's technology
that we can find problems that get missed
by other tools.
Now, the backstory behind this vulnerability is that towards the end of 2017,
I was looking at this code
in the curl project.
I'd never seen this coding pattern before.
I didn't even know that snprintf had a return value,
so I was quite interested to see this coding pattern.
It's quite clever the way that it's being used here.
What they're doing is they're printing
a list of strings into a fixed size buffer,
and they're using
the return value of snprintf
to keep track of what offset
in the buffer they need to print to next.
They're using the size argument of snprintf
to make sure that they don't write
beyond the end of the buffer.
Because I'd never seen snprintf used
like this before, I pulled up the man page
for snprintf to see how it works.
Now, if we search for RETURN here,
we get the documentation on the return value.
There's a very interesting thing here.
It says that the return value
is the number of characters
which would have been written
to the final string if enough space had been available.
What that means is that this code
that we just saw in curl looks unsafe.
Because if there's a string that is too big,
it exceeds this value, then, if say the string is 100 bytes
but there's only 10 bytes left in the buffer, then ptr is still going to get incremented
by 100 bytes
and so on the next iteration of the loop, we can continue,
and we're going to continue printing.
What's worse is that this sizeof subtraction here
is actually going to compute the answer minus 90,
but the input to snprintf, the size input to snprintf,
is a size_t, it's an unsigned value.
We're going to get a negative integer overflow here.
That means that there's going to be effectively
no limit on the number of bytes
that we can write to the buffer.
Now, it turns out that this is not actually a problem in curl,
because they've got their own implementation of snprintf,
which you can see here.
This version of snprintf works the way
that you need it to in order to use this coding pattern.
So, it returns the number of bytes
that it actually wrote rather than the number of bytes
that it wanted to write.
There's no problem in curl,
but after having seen this coding pattern,
I thought,
"Well, I wonder if anybody else
has done the same thing but using the real snprintf.
Because if they have,
then they might have a buffer overflow in their code."
Let's now go to Eclipse and use QL to search
for this vulnerability.
What I'm going to do first is something
that you could do equally well
with grep,
but we're very quickly going to refine
this query to something
that is much more sophisticated
than what you can do
with grep.
To begin with, I'm just going to search
for all calls to snprintf in the project.
108 results.
Now, 108 results is not that many.
You could realistically audit all of these
by hand.
One of our customers actually had
this exact same vulnerability on some proprietary code.
If you were to run this query on their code base,
then you'd get over 600 results.
That's going to be quite tedious to look through
by hand.
QL can really help you, save you some time
by quickly ruling out the cases
that are not interesting to look at.
The most common reason that the call to snprintf
is safe is that you're just not using
the return value of snprintf.
Let's update the query to rule out those cases.
We just want to say that the call is not in a void context.
If we run the query that way, then we're now down to 45 results.
Now, let's look at one of these.
This is another common reason that it's unlikely to be a problem,
this format specifier contains only a %d.
Now, a %d is going to be quite difficult
for an attacker to do anything with,
because the number of bytes
that you can generate
with a %d is limited
and also the content of the string
that you can generate
with it is quite limited,
because you can only generate ASCII digits
rather than an arbitrary list of characters.
What an attacker is really going to want is a %s,
because that allows them to control both
the size of the string that's generated
and also the exact content
of the string that's generated.
Something that I would also like to point out
about this example is that we're now looking at a call to snprintf that is not all in one line.
That's quickly going to become a pain to search
for with regular expressions.
When you're searching with QL,
that's not a problem at all,
because we're looking
at the abstract syntax tree of the code
rather than just doing text based searching.
What we're going to do here is we're going to add
a condition that the format specifier
should contain a %s.
We use zero-based indexing for the arguments of a call.
The format specifier is going to be argument number two,
and we can get the string
like this
and then we can do regular expression matching on it
like this.
We want it to contain some stuff followed
by a %s, followed
by some more stuff.
Now, by default,
regular expressions don't match strings
that contain a newline character.
Format strings very frequently
do contain newline characters.
We're going to add this special syntax here.
We're using Java's regular expression syntax.
That's how you tell it to
also match strings that contain newline characters.
Let's run that now.
Now we're down to 18 results.
Let's have a look at some of these.
Now, that one is in fact, the vulnerability.
We'll get back to that later.
Let's first look
at some others to see
which other ones we might want to rule out.
This is an example of a result
that we're not interested in
because here the result of the return value of snprintf is being used,
but it's being used in a safe way
because we're using it to check that
it didn't want to write more characters than we expected.
Really, the vulnerability that we're looking for is the case where you have a loop,
and the output of snprintf is getting fed back
into the size parameter of snprintf.
That's what allows the buffer overflow to happen,
and also the negative integer overflow here,
which is essential in order to have the vulnerability.
What I'm going to do now is
I'm going to use one of our libraries,
I'm going to use the taint tracking library
to see if there's data flow
from the output back into the size argument.
I have to have an import statement first.
I'm going to import dataflow's TaintTracking library.
Then we're going to add a source and a sink.
Normally, when you use the TaintTracking library,
the source would be something
that you believe to be tainted
because it's controllable by an attacker,
and the sink would be a place
where it's used in a dangerous way.
QL is flexible,
and so we can use it
for this kind of situation as well which is slightly different,
where we're going to just say,
"I want the source to be the call to snprintf,
and I want the sink to be the size argument of snprintf."
It will do that equally well.
"call" is the source,
and the sink is the size argument.
In fact,
because the call is the source of the data flow,
this thing
about it being in a void context is now redundant,
so we can remove that from the query if we want.
It would be harmless if we left it in.
Now, we need to actually
use the TaintTracking library
to connect up the source
and the sink.
We only need to look for local data flow,
that means within the function. For this particular pattern,
it's always going to be within a single function.
In general, our TaintTracking library
supports interprocedural taint tracking as well,
we just don't need it here,
so that's why we're using the localTaint function.
Let's run that.
Now we have exactly one result, which is the vulnerability right here.
Now, there's one final thing
that I'd like to show you.
It's often useful to use range analysis
to see what sizes we're able to deduce.
In this particular case, we're interested in the size argument into snprintf.
If we were to apply range analysis to it
and find out that it has an upper bound of 10, then there's probably nothing wrong.
I'm just going to show you how to use the range analysis library.
We need to import it like this,
and then we can just add an extra column to the results list.
We're going to include
the upper bound of the size argument.
What I'm also going to do is I'm going to apply getFullyConverted to the size argument.
Just run that now.
When you call a function like snprintf, the argument that it expects is a size_t,
so an unsigned integer.
Now, if the argument
that you pass in is something
like an int, then there's going
to be an implicit conversion,
and those implicit conversions
can often be the source of integer overflows.
In this particular case,
the reason that there's a problem is
because we subtract something from this size,
and we get a negative integer overflow,
which means that the size parameter that we call snprintf with
is actually a huge 64 bit number.
It's more interesting here to look
at the size of the fully converted argument
so that we can make sure
that we're seeing what's going to happen
after the conversion.
Sure enough, range analysis knows
that there's a possibility of a negative integer overflow,
and so it's saying that the upper bound
is the full range of 64 bit unsigned numbers.
Okay.
That's the end of the demo.
What I've done is shown you that, using QL,
you can very quickly search for problems
like this.
I started out
with something that is equivalent to grep,
but then I very quickly moved on
to something that is much more powerful.
Now, of course, what we do
at Semmle is we also take queries
like this,
and we turn them into much more polished queries
which can then be included in our default suite.
My colleague Geoffrey White took
this rough query which I wrote in 2017
and turned it into a much more polished version,
which is now included
in our default suite on lgtm.com.
In fact, it was Geoffrey's version of this query
that found the vulnerability in rsyslog,
and Bas was the one
who was looking through the results
and noticed it,
and that then led to us reporting
the vulnerability to Rainer.