The brk() vulnerability [LWN.net]

It has been disclosed that the compromise of the Debian Project's servers was made possible, in part, by a previously unpatched vulnerability in the kernel's memory management code. For the curious, this article describes how that vulnerability works, and what is required to exploit it. We'll also look at how it could have remained unfixed for months.

Process memory
0x00000000-0x08047FFF Unmapped area
0x08048000-0x08?????? Program text
0x08??????- Named memory and heap
0x40000000-0x4??????? Shared libraries, shared memory segments
0x4???????-0xbfffcfff Unmapped area
0xbfffd000-0xc0000000 Stack

The kernel organizes a process's memory in a way vaguely similar to the diagram at the right. The addresses shown there correspond to the default ia-32 implementation. This picture has been simplified somewhat, but it conveys the basic idea. The real picture on a specific system can be had by running "cat /proc/self/maps".

The bulk of the memory used by a program for its variables and heap storage is found in the section marked "named memory and heap" in the diagram. This memory area is initially made large enough to hold the static variables created by the program, but, as soon as more memory is required (to satisfy malloc() calls, perhaps) that region of memory must be expanded. Since the beginning, Unix-like systems have provided a system call (named brk()) which can be used to change the size of the heap area. The caller simply passes in the virtual address indicating where the new "break point" should be set, and the area is expanded or contracted as need be.

Back in September, Andrew Morton noticed that no sort of bounds checking was being applied to the address passed to brk(). In theory, this omission means that a process could request an arbitrarily large heap area. In practice, most programs would not get that far. The kernel does not allow virtual memory areas to overlap each other, so any expansion of the heap area that caused it to impinge upon the shared library areas starting at 0x40000000 would be rejected with an error. So it would appear that the lack of bounds checking was never that serious of a problem; all it could do is allow a user to set up some huge page tables.

Obviously, the situation is worse than that. The memory layout diagram is missing one important area; on ia-32 systems, the kernel itself is mapped in starting at 0xc0000000 - right above the process stack area. Processes normally do not have any access to that part of memory, of course. But, as it turns out, if you can convince brk() to expand your heap area up into the kernel's address range, you have direct access to the kernel code and data areas. At that point, the integrity of the system is lost.

The key to cracking the system is changing the process memory layout so that the heap area can be expanded into the kernel's space. You cannot easily do that with a normal C program, but, with a bit of assembly trickery things become easier. A proof of concept exploit has already been posted to Bugtraq, so one can see how it is done. It is really a matter of (1) moving the program origin up into the highest part of virtual memory, where the stack usually lives, and (2) shorting out the C library's startup code which sets up the address space in the first part. Once you do that, an unpatched system will happily expand your heap area into kernel space.

So, as the Debian Project learned at great cost, this little omission in the implementation of the brk() system call is fully usable for a complete local root exploit.

There have been a lot of questions about how such a vulnerability could remain unfixed for so long. In fact, it was patched in the 2.6.0-test series almost as soon as it was found. The fix also went to Marcelo Tosatti, the 2.4 maintainer, but it was too late for the 2.4.22 release, which happened on August 25. So the fix was merged into 2.4.23-pre7, which came out on October 9. The current 2.4.23 kernel is not vulnerable - but that was too late to help Debian.

The real problem, of course, is that nobody realized the severity of this bug. Had the kernel developers understood that current kernels were vulnerable to this sort of attack, the alert would have gone out and the various distributors would have sent out the usual set of updates. But this patch was just one of over 2000 patches merged by Linus in September. It would seem that it simply became part of the stream of fixes, and nobody looked at it particularly closely.

Except, of course, somebody did. Chances are, the posting of this fix drew an attacker's attention to the brk() code. With a bit of effort, the exploit got written, and now thousands or millions of systems are at risk.

What the kernel (along with most other projects) needs is more friendly eyes looking for this sort of problem. We do reasonably well, in that most vulnerabilities are found and fixed by the good guys before they can be exploited. There are cases where that doesn't happen, however, and the brk() bug was one of them. Security auditing is hard work, and usually unrewarding. But it would have been nice if somebody had looked hard enough at this problem to raise the alarm.

to post comments

The brk() vulnerability

Posted Dec 2, 2003 18:28 UTC (Tue) by parimi (guest, #5773) [Link] (2 responses)

Thank you for such an informative article on exploit! In the line The kernel organizes a process's memory in a way vaguely similar to the diagram at the left, should the ending portion of the line have been diagram at the right ?

The brk() vulnerability

Posted Dec 2, 2003 18:29 UTC (Tue) by corbet (editor, #1) [Link]

No...I meant the other left...

The brk() vulnerability

Posted Dec 2, 2003 19:20 UTC (Tue) by stijn (subscriber, #570) [Link]

Remember that Jon is looking at the article from the other side of your screen.

How far back?

Posted Dec 2, 2003 18:43 UTC (Tue) by ncm (guest, #165) [Link] (5 responses)

When was this hole introduced? Apparently 2.2 has a proper range check, but that was deleted.

Whose patch deleted it, and when, and in which release?

How far back?

Posted Dec 2, 2003 21:47 UTC (Tue) by alan (subscriber, #4018) [Link]

2.2 and 2.4 are so different, it likely wouldn't have mattered anyway

How far back?

Posted Dec 3, 2003 0:15 UTC (Wed) by pblanco (guest, #16087) [Link] (2 responses)

It's interesting that my SuSE 9.0 with the 2.4.21-144 kernel has the patch. The article implied that 2.4.22 and 2.4.23 had the patch, so I assumed that earlier releases wouldn't have it. What gives?

How far back?

Posted Dec 3, 2003 3:17 UTC (Wed) by Mithrandir (guest, #3031) [Link]

SuSE have applied 144 patches to that kernel, so it could hardly be called a vanilla 2.4.21. I'd be guessing that they applied the patch as a routine security patch at the time that it was released for 2.4.23-pre.

How far back?

Posted Dec 11, 2003 6:59 UTC (Thu) by wildpossum (guest, #17744) [Link]

No that is not implied. What SUSE (and other vendors) do is patch the kernel that was released with that box version, rather than risk breaking things by upping the kernel version without adequate testing. So the bug was in the 9.0's 2.4.21 kernel, SUSE patched it when the alarm went out, and you got this update when you ran the YaST Online Update tool.

How far back?

Posted Dec 4, 2003 12:07 UTC (Thu) by IkeTo (subscriber, #2122) [Link]

2.2 does not have the special case code for brk(), i.e., do_brk, which tries to speed things up because the end of the text segment is special. In 2.2, do_mmap is used to do brk, and do_mmap do all the checking. I think the kernel developers forget that the ELF-header can be modified to start the program such that the text segment might be at the end of the memory space, so they think that it is not possible to have brk() called in such a way that can extend through the end of the address space---normally, the virtual memory bound checking will stop anything wrong from happening.

The brk() vulnerability

Posted Dec 2, 2003 19:04 UTC (Tue) by JoeBuck (subscriber, #2330) [Link] (4 responses)

The problem with doing kernel maintainance in public is that the bad guys are watching. Every commit to the source control system that fixes a flaw is an opportunity for a cracker to ponder whether unpatched systems can be exploited. I fear that publicity surrounding this particular exploit will alert others to this way of finding new cracks. Of course, the kernel maintainers are already aware of this possibility, so they will be more cautious when they are conscious that they are fixing a security hole. But any missing integrity check might make an exploit possible.

The brk() vulnerability

Posted Dec 2, 2003 19:14 UTC (Tue) by beejaybee (guest, #1581) [Link] (2 responses)

Sure - but it's better to do your washing in public than not to do it at all.

Let's prove ourselves better than the Windows admins by getting our systems patched reasonably quickly!

The brk() vulnerability

Posted Dec 2, 2003 20:21 UTC (Tue) by elanthis (guest, #6227) [Link] (1 responses)

This isn't really true. It's similar to how bugtraq and other security organizations give companies time to release fixed software before the announcement of the vulnerability is even made - the fix exists and users can download it, and have had ample time to do so, before most attackers even know there is a hole.

With the open nature of the kernel developement, the "announcement" is out there before anyone but a few kernel developers have a chance to so much as know the patch exists.

Some good policy on keeping security fixes "secret" until after they're in a release (or at least -pre patch), and then keeping the details secret until the fix has been out for a while, could solve this problem. *could*.

The brk() vulnerability

Posted Dec 2, 2003 23:00 UTC (Tue) by lacostej (guest, #2760) [Link]

Exactly. And with the open development of the kernel, it's not up to the maintainer to detect the risk of a fix, but it has to come has low/early as possible from the development process. Because as soon as a potential fix goes into the open, even before reaching the point where a maintainer must take a decision to include or not a patch, somebody may see and use this patch to find out a security problem.

The way I understand it, a maintainer is just follows some kind of agenda. He gets patches, like recommendations/ideas, and based on HIS own feelings, based on the fact that others have put their confidence on him to do a good job, he decides or not to accept/reject the fix. The more patches the less time to know about all the intricate details of every fix. That's why the security level of a patch must be assessed before they reach him, so that he can make the good decision. That's exactly like politics.

And to me, Marcelo does a great job, I am pretty happy with the 2.4 series. If he didn't put the fix in, it's because he didn't have all the information about the fix.

Because of the openess and increasing use of Linux and other open solutions, the number of attacks following this particular way of working will probably increase. It will also be used by the competition. This openess is one of the biggest weakness of open source, a weakness that also supposedly makes its greatness. People will try to turn that around. Make it an example.

Because of all that, perhaps some kind of patch security assessment policy should be introduced. Like patches should perhaps be tracked and reviewed with security in mind. That's thousands of patches, but we must probably be able to find a handful of detection hints sufficient to remove 80% of the risks.

The brk() vulnerability

Posted Dec 4, 2003 5:52 UTC (Thu) by brouhaha (guest, #1698) [Link]

The problem with doing kernel maintainance in public is that the bad guys are watching.

The problem with doing kernel maintenance secretly (e.g., proprietary kernels such as that of Windows) is that it's a little harder for the bad guys to find exploits, but it's a lot harder (effectively impossbile) for the good guys to audit the code to discover and fix weaknesses before they are used for attacks.

Like any engineering decision, it is a tradeoff. Most people that don't have a vested interest in promoting proprietary software believe that the open development model results in better security. The studies Microsoft has funded that claim Linux security is worse reach that conclusion based purely on the number of advisories issued, ignoring the fact that the number of advisories is not a measure or even a good predictor of the number of remaining vulnerabilities in the software.

Bad Maintainance!

Posted Dec 2, 2003 19:34 UTC (Tue) by AnswerGuy (guest, #1256) [Link] (8 responses)

I'm increasingly unhappy with Marcelo's maintenance of the 2.4 kernels.

He has to learn that fixes that impact security in the core kernel must be released as a new kernel IMMEDIATELY! Pussy footing around with 5 or 6 pre-releases that contain lots of lesser fixes is a dis-service to the entire community. There are times to release a new stable kernel with a single bug fix, even it that's ONLY A SINGLE LINE.

I seem to recall there was a similar problem around 2.4.19 or 2.4.20 --- a known fix for a vulnerability was deferred in favor of the release based on the rc* series --- business as usual. That's not the way it should be done.

I long for the days when the "ping of death" elicited a new kernel IN LESS THAN ONE DAY! (Alan Cox).

Jim

Re: Bad Maintainance!

Posted Dec 2, 2003 20:03 UTC (Tue) by crimsun (guest, #13750) [Link] (1 responses)

I think it's a fundamental difference in how a maintainer follows the rigor of his release schedule. The argument has been made that people who track exploits closely will patch their systems regardless of whether a version bump is made to accomodate the release of a critical fix. I feel Marcelo's doing a fine job maintaining 2.4. Yes, Alan's policy with 2.2 has always been more finely-suited to security releases reflecting version bumps. That way there is no confusion.

The original closing hook really stands; we all need to be watching cset merges.

Re: Bad Maintainance!

Posted Dec 2, 2003 21:20 UTC (Tue) by freethinker (guest, #4397) [Link]

I don't agree. Yes, we can have some people, who have the skills and time to track exploits, patch their systems. But wouldn't it be better if the maintainer patched the kernel and issued a new release with an appropriate message regarding the urgency? Then many more people would be aware and would upgrade. That's what the maintainer is for: to track these things, to be aware of urgent issues, and to do the right thing with them.

I won't go so far as to say that Marcelo fell down on the job here. I don't know all the circumstances. But the question should be asked.

Bad Maintainance!

Posted Dec 2, 2003 21:29 UTC (Tue) by smoogen (subscriber, #97) [Link]

Let me follow your logic:
Linus, Andrew, Alan, et al dont think of it as a security bug fix, but more of a cleanup and possible problem. They dont tell people to stop using 2.6.0.x and go to the next test version.
Marcelo applies the patch and is supposed to know that it is a security bug fix of great importance.

I have thought that Marcelo was pretty slow during his Connectiva days.. but this is a bit ridiculous.

Bad Maintainance!

Posted Dec 2, 2003 22:14 UTC (Tue) by LogicG8 (guest, #11076) [Link] (2 responses)

I disagree, I think Marcelo is doing the right thing.
It represents a fundamental shift in the way the
kernel is maintained, but I think it's for the best.
What this does is shift responsibility from the
vanilla source tree to individual distributions. All
the mainstream distros have their own kernel trees.
They should keep on top of security fixes and
immediately bump out a new release when something
happens. The vanilla sources aren't for everybody
anymore. I'm not trying to be elitist here, most
people just don't recompile their kernel. If you are
smart enough to compile your own kernel you are
probably smart enough to patch it when a fix comes
out. If not you might want to consider letting a
proffessional do it for you and use the kernel that
comes with your distro.

Stable releases should be for milestones in development
not for every security bug that comes out. Distributions
should provide security updates. To do otherwise dilutes
version numbers and makes them useless for indicators of
progress.

Bad Maintainance!

Posted Dec 3, 2003 0:26 UTC (Wed) by dlang (guest, #313) [Link] (1 responses)

you see it as a good thing to discourage people from useing the vanilla tree and instead have everyone use a tree patched with some arbatrary set of patches? (last I heard Suse and Redhat both have >200 patches in their trees)

if every distro does this how in the world can anyone track down a bug report?

I agree that the way the 2.4 kernel releases have been done tends to encourage this, but I see this as a bad thing as it further fragments the testing base.

If a security hole is found and itentified as such (which I agree this was not) then the proper procedure is to apply the fix to the last released kernel, release a new kernel, and then take all the work that was done in the meantime and apply it to this new kernel and pick up where you left off (you can even keep the same preX number if you want) the use of source control systems makes this fairly trivial to do.

counting on people to be paying enough attention to every patch that is released to know that it's a security patch and then apply it themselves (or wait for a distro to do so) becouse you have a fixed 'release procedure' is being lazy

Bad Maintainance!

Posted Dec 4, 2003 5:22 UTC (Thu) by iabervon (subscriber, #722) [Link]

For vanilla kernels, I think the best idea is really a patch that applies
to all of the affected versions. Releasing 2.4.23 with that as the only
change is fine for x86 users with standard hardware, but if you're
running on a SA-1110 with a CS integrated NIC that requires a patch that
applies cleanly only to 2.4.8, a patched kernel which is very similar to
2.4.2x isn't going to be very useful. Furthermore, this sort of security
fix is generally only a line or two in a part of the kernel that doesn't
change very much.

What I think should happen in this situation is really that Marcelo
should bless a particular patch as the correct fix for the problem for
each 2.4 release, and kernel.org should distribute it, and it should get
into the next release. Fixing this sort of security problem should really
be orthogonal to the regular kernel development process.

Bad Maintainance!

Posted Dec 2, 2003 23:22 UTC (Tue) by jafo (guest, #8892) [Link]

The issue is that the security implications weren't fully realized before the compromise of the Debian systems.

My problem with the 2.4.23 release is that it is (IMHO) much more than just a maintenance release. Adding USB gadget drivers, IPVS, SCTP, and others seems well beyond what I'd think of in a maintenance release. These can often cause other patches to fail to apply, making it difficult for admins to get their systems up to date.

Sean

Bad Maintainance!

Posted Dec 4, 2003 17:51 UTC (Thu) by hazelsct (guest, #3659) [Link]

I cannot agree with you regarding this particular flaw, as the nature of the bug was not known to people maintaining the code.

But I do agree regarding your earlier example. Alan's practice with 2.2 has been to make a new point release as soon as a vulnerability is discovered and patched, a release which *only* fixes the vulnerability (saving all other developments for the subsequent point release). This greatly simplifies keeping track of secure kernel releases, rather than having to know exactly which revision fixes things for each separate distribution. (For example, "You have 2.4.19-15? Is that RedHat, SuSE, Mandrake or TurboLinux? Let's see, I can't remember exactly which one fixed that problem for your particular distribution...") Marcelo has not done this, and I wish he would commit to doing so moving forward.

4G/4G

Posted Dec 2, 2003 23:22 UTC (Tue) by brugolsky (guest, #28) [Link]

So presumably systems with Ingo's 4G/4G patches are not vulnerable?
I hadn't thought of 4G/4G as an additional security barrier, but perhaps it is.

The brk() vulnerability

Posted Dec 3, 2003 5:45 UTC (Wed) by stuart2048 (guest, #6241) [Link] (4 responses)

I too would like to offer a big thumbs up on LWN's coverage of this event. Thanks guys!

One thing puzzles me though. How did the attacker gain unpriviledged shell access to the systems in the first place? Apparently this was done via a sniffed password. But how did this password get sniffed? Was it cleartext on the wire? If so, what was it -- telnet, rlogin, X11 keystrokes?

If this was a network sniff, what was the topology? Where did the sniff happen?

--Stuart

The brk() vulnerability

Posted Dec 3, 2003 8:12 UTC (Wed) by dlang (guest, #313) [Link]

remember that the Debian project boasts 1000 developers. I don't know how many had access to the initial machine, but it's not unreasonable to consider that at least half of them did.

if these people each accessed this machine from 2 different machines (home and work for example) that means that there are 1000 different places that the inirial login password could have been aquired from.

remember that if you use ssh to connect to a machine that machine is only as secure as the least secure of the machines that are allowed to connect to it. chain this a few times, multiplied by a lot of people and you should figure that a determined enough person _will_ be able to get user access to it.

The brk() vulnerability

Posted Dec 3, 2003 8:21 UTC (Wed) by pwaechtler (guest, #5075) [Link]

I guess POP3 or HTTP (cvs repository?) with password

The brk() vulnerability

Posted Dec 3, 2003 8:33 UTC (Wed) by ridrid (guest, #10092) [Link] (1 responses)

Heres a hypthosesis from the debian-devel mailing list:

http://lists.debian.org/debian-devel/2003/debian-devel-200311/msg02170.html

Rich Dougherty

The brk() vulnerability

Posted Dec 4, 2003 12:13 UTC (Thu) by IkeTo (subscriber, #2122) [Link]

In other words, if you don't want it to happen to you, don't ssh from ssh'ed accounts.

The brk() vulnerability

Posted Dec 3, 2003 6:34 UTC (Wed) by dkite (guest, #4577) [Link]

This hit the news here in Canada. Didn't see it, but a coworker said they
heard something during the lunch news.

This is a local exploit. From what I understand, it isn't exploitable
unless you can install and run an application that does the dirty work.

Which raises the question of how the servers were compromised. Obviously
this bug was not the only problem.

Derek

Learn from this!

Posted Dec 3, 2003 9:58 UTC (Wed) by walles (guest, #954) [Link] (1 responses)

What should be done now is:

Assume you have a perfect kernel with an unknown problem in brk(). Ask yourself, what security measures (other than finding the bug and fixing it) could prevent the bug from being exploited?

When you have a good answer, go implement it and this won't happen again.

Our local Windows guru says that MS has started using the following procedure when security problems are found in their sources:
1. Report the problem to a group making static code analysis tools.
2. That group is responsible for making a tool that can find the bug that was just fixed.
3. The static code analysis tool is run on the sources at regular intervals.

Linux has the Stanford checker and another Free tool of which I cannot currently remember the name, but I don't know if the feedback works as outlined above. And regardless of whether MS actually manages to implement the above procedure or not, the Linux community should.

Learn from this - flawfinder, RATS

Posted Dec 3, 2003 17:11 UTC (Wed) by dwheeler (guest, #1216) [Link]

A somewhat similar process is already in place. Folks like Viega and myself have developed static analysis tools; when we see an error, we try to modify our tools to find that too. My flawfinder tool (http://www.dwheeler.com/flawfinder) looks for previous mistakes, as does Viega's RATS. I'm sure more can be done, please do contribute!

The brk() vulnerability

Posted Dec 3, 2003 11:45 UTC (Wed) by mwh (guest, #582) [Link]

It's interesting how this backs up the OpenBSD view that any bug is a potential security hole.

The brk() vulnerability

Posted Dec 4, 2003 12:21 UTC (Thu) by IkeTo (subscriber, #2122) [Link]

Note that the patch cause a problem on the VMA of the process which calls brk(), and the actually memory read is done by /proc/<pid>/mem. In other words, the exploit depends on an interface of the kernel that will use the VMA without checking whether it is in the kernel region. If that interface does not exist, then the attacker will have a very hard time thinking about any way to use the wrongly placed VMA.

What are those interfaces, actually? I think there are just a few of them: the mem of the pid, and the core dump. Both not performance critical. Does it make sense for the kernel to just check the addresses also in these cases (i.e., not to trust its own VMA's) so that when such a problem occurs in the future, the attackers will not find it so easy to get through the kernel-user protection?