Linux Kernel Auditing; Unsigned Integer Overflows

For those that know me, you probably will know that for the past 5 years I have not been involved in computing. I did not even own a computer during that time! However, computing, even after 5 years is a hard thing to shake from the system, so I am starting to become involved again. I will be returning to University to study IT, and will soon, hopefully, own my own PC. Donations are always welcome🙂

And so, the show must go on..

At the end of 2002 I performed audits of the operating system kernels in NetBSD, OpenBSD, FreeBSD and Linux with approximately 30-50 security patches introduced in the mainstream kernels as a result. The majority of vulnerable kernel code snippets are available as part of a 2003 archived presentation held at http://www.ruxcon.org.au.   A higher level review was presented in Las Vegas 2003, http://www.blackhat.com , also available online.

Last night I began an audit of the Linux kernel using the same methodology as in 2002. I will discuss this methodology in another blog. For now I will only discuss a particular class of C implementation bug that are still present in the Linux kernel.

Unsigned Integer overflows.These have been discussed for many years now, but were still present in a number of bugs discovered in the auditing I performed.

unsigned int a,b,c;
if (a+b > c)

This code is found in several places in the Linux Kernel, for checking exceeding rlimits. An rlimit or resource limit is a kernel limit of how many particular operating systems resources can be used by a particular user, or how much of a resource can be used. These vulnerabilities in Linux allows some resource limits to be evaded.

“a” and “b” in the Linux kernel code were not truely limits in their own right, but the cumulative total represented a resource limit. They were both unsigned in type. An integer overflow occurred when either “a” or “b” was large, making the total overflow.

Related to these vulnerabilities are the cases when signed integers overflow in an operation, or unsigned and signed integers overflow.

Other details include overflows involving integers of different sizes, and architectures where integer types are of different size.

Also signifcant to this, is type promotion, which makes vulnerable some otherwise sound code.

These problems are slightly different in semantics, and will not be discussed any furthur.

Back to what we were talking about..

As an example in the case where an unsigned integer type is 8 bits in size, 0x01 + 0xff, would overflow. The correct answer to the addition 0x100, but with only 8 bits available to store the result, the high bit is truncated and the real result becomes 0x00.

In the Linux example described earlier (a+b>c), a better (but still incorrect) implementation of vulnerable code might look like this


unsigned int a,b,c;
if (a > c || b > c || (a+b)>c)

I have seen this type of code implemented to check for these types of problems, in all the kernels I audited, espceially NetBSD. However, it is still vulnerable. An example in 8 bits is when a=0x80, b=0x80, both less than c=0x90. An integer overflow occurs in 0x80+0x80 resulting in 0x100. An explicit check for an overflow should occur.

unsigned int a,b,c;
if ((a+b)>c || (a+b) < a)

A typical correct implementation in C to check for overflow is demonstrated above. When “c=a+b” overflows, then c is always less than either “a” or “b”. In the case above checking against “a” was performed, although the choice could have been “b” also.

That concludes the story on this one class of integer overflow commonly seen in vulnerable code; in our case, the Linux kernel. I will discuss more bug classes and vulnerabilities in future posts.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s