homepage

Race condition in the rmtree function in the shutils module allows local
users to delete arbitrary files and directories via a symlink attack.
See also http://bugs.debian.org/286922
Attack:
---
# emulate removing /etc
$ sudo cp -a /etc /root/etc/
$ sudo python2.6
 >>> for i in xrange(0, 50000):
... with open("/root/etc/" + str(i), "w") as f:
... f.write("0")
...
$ ls /root/etc > orig_list.txt
$ mkdir /tmp/attack
$ cp -a /root/etc/* /tmp/attack
$ sudo python2.6
 >>> from shutil import rmtree
 >>> rmtree('/tmp/attack')
 >>> # press ctrl-z to suspend execution
^Z
[1]+ Stopped sudo python2.6
$ mv /tmp/attack /tmp/dummy; ln -s /root/etc /tmp/attack
$ fg
sudo python2.6
Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
 File "/usr/local/lib/python2.6/shutil.py", line 225, in rmtree
 onerror(os.rmdir, path, sys.exc_info())
 File "/usr/local/lib/python2.6/shutil.py", line 223, in rmtree
 os.rmdir(path)
OSError: [Errno 20] Not a directory: '/tmp/attack'
$ ls /root/etc > new_list.txt
$ diff -q orig_list.txt new_list.txt
Files orig_list.txt and new_list.txt differ
---
If the attack wasn't successful, /root/etc would not be modified and
orig_list.txt and new_list.txt would be identical.

What course of action do you suggest? First chmod 0700 on the directory?

Mmmh, very recent Linux kernels (>= 2.6.16) seem to have specific
functions to deal with this (see man pages for openat, unlinkat, etc.).

A shameless copy of the Perl fix for the bug
http://bugs.debian.org/286922 looks like the evident solution.
Somebody has to examine the fix though, I'm afraid I'm not currently
able to do it.

The Perl patch is here:
http://bugs.debian.org/cgi-bin/bugreport.cgi?msg=36;filename=etch_03_fix_file_path;att=1;bug=286922
It is a recursive implementation of rmtree. What it does is 1) get the
inode of the path 2) unlink it altogether if not a dir 3) otherwise,
chdir to it 4) check that '.' still has the same inode, otherwise bail out.

Mmmh, the problem with Perl's approach is that it changes the current
working directory (calls to chdir()), which is process-specific and not
thread-specific. Currently, no function in shutil changes the current
working directory, which is a nice behaviour and should IMO be preserved.

> Mmmh, the problem with Perl's approach is that it changes the current
> working directory (calls to chdir()), which is process-specific and not
> thread-specific. Currently, no function in shutil changes the current
> working directory, which is a nice behaviour and should IMO be preserved.
Using chdir() makes sense and it doesn't look like a too big problem to me:
def rmtree(...):
 ...
 curdir = os.getcwd()
 try:
 call chdir() as required
 finally:
 try:
 os.chdir(curdir)
 except:
 warnings.warn("Unable to chdir to previous current dir")
 ...

> Using chdir() makes sense and it doesn't look like a too big problem to me:
It's a problem if another thread in the process is making file
operations using relative paths at the same time.
Since shutil functions have until now been safe against this
possibility, I don't think it's ok to make them unsafe in future
versions.

Ah, right you are. Attaching an initial alpha-quality patched shutil.py
and a script to test the attack.
Run the script by sourcing it with . test_issue4489.sh, not by executing
(job control won't work in this case).

And here's the diff so you can review what I was up to.
Note that this does not yet fix the problem (although the logic looks
about right), I have to examine the problem more thoroughly.

Aha, got it -- while removing /a/b/c/d, there's no easy way to detect
that b or c has become a symlink.
I.e.
given directory tree
a
`-- b
 |-- c
 `-- d
1. os.rmdir('/a/b/c') succeeds
2. execution is suspended
3. '/a/b' is made a symlink to a path that contains 'd'
4. '/a/b/d' is neither a symlink, nor has it's inode been recorded, so
os.rmdir('/a/b/d') succeeds
I'm afraid the solution for the Perl bug is susceptible to the same problem.

A blunt, ineffective solution would be to walk the tree before removing
it and recording path : inode pairs in a dict on first pass and then
checking that the inodes have not changed during removal on second pass.
If no clever bulletproof fix emerges, perhaps this should be added as
shutil.rmtree_safe (duh, API bloat...)?

> A blunt, ineffective solution would be to walk the tree before removing
> it and recording path : inode pairs in a dict on first pass and then
> checking that the inodes have not changed during removal on second pass.
There's no way to do the "check inode then remove" sequence atomically.

Fixed a minor bug in test script and added Perl test as well.
Perl with File-Path-2.07 passes the test.

Antoine, what if we add another function, rmtree_safe() that uses
chdir() and document that it is protected from the race condition but
may have the side effect of changing the current dir in threaded
environment?

Replying to previous comment:
> There's no way to do the "check inode then remove" sequence atomically.
Right, although the attack window would be tiny, this is not a real
solution.

> Antoine, what if we add another function, rmtree_safe() that uses
> chdir() and document that it is protected from the race condition but
> may have the side effect of changing the current dir in threaded
> environment?
I don't have any strong opinion on it, maybe it should be brought on the
mailing-list (or just wait for some other devs to show up here).

FWIW, I've opened a separate bug entry for the creation of the openat(),
etc. wrappers: #4761.
Those functions seem to exist on recent Linux distros (even Debian stable).

Mart,
I took over the maintenance of shutil, if you are interested in contributing a bullet-proof version of rmtree, please drop a line at python-ideas, and let's see what we can do in a new function maybe.
I'll be happy to review and apply patches if we get a consensus

How does "rm -rf" address this issue? Or does it?
shutils.rmtree should probably do the same thing.

Here is a draft patch.
It uses the *at functions and fdlistdir consequently it only makes it safe if those functions are available. It works using a recursive implementation and an open file descriptor pointing to a directory, instead of maintaining state by changing the current directory. If the *at functions are unavailable, it falls back to the unsafe implementation.
It requires the patches from issue4761 and issue10755 to work.

Thanks for the patch.
There seems to be a race remaining here:
+ try:
+ if os.path.islink(path):
+ # symlinks to directories are forbidden, see bug #1669
+ raise OSError("Cannot call rmtree on a symbolic link")
+ except OSError:
+ onerror(os.path.islink, path, sys.exc_info())
+ # can't continue even if onerror hook returns
+ return
+ fd = os.open(path, os.O_RDONLY)
Someone could change `path` to be a symlink between the calls to islink() and open(). You probably need to stat the fd instead.
Some other things:
- if close() is meant to be a private helper, it should be named _close()
- instead of a bare "except" in close(), use "except EnvironmentError" or "except OSError"
I haven't looked at the tests yet.

Updated patch removes the race condition. Since an open follows symlinks, you can't just fstat the fd to see if it is a link. I followed the following to overcome this:
https://www.securecoding.cert.org/confluence/display/seccode/POS35-C.+Avoid+race+conditions+while+checking+for+the+existence+of+a+symbolic+link 

Le mercredi 05 janvier 2011 à 16:58 +0000, Ross Lagerwall a écrit :
> Ross Lagerwall <rosslagerwall@gmail.com> added the comment:
> 
> Updated patch removes the race condition. Since an open follows symlinks, you can't just fstat the fd to see if it is a link. I followed the following to overcome this:
> https://www.securecoding.cert.org/confluence/display/seccode/POS35-C.+Avoid+race+conditions+while+checking+for+the+existence+of+a+symbolic+link
Nice. I am unsure about the following piece of code:
+ if stat.S_ISDIR(mode):
+ if stat.S_ISLNK(mode):
+ try:
+ raise OSError("Cannot call rmtree on a symbolic
link")
+ except OSError:
+ onerror(os.fstatat, (dirfd, name), sys.exc_info())
If rmtree() encounters a symlink *inside* the tree, I would expect it to
simply remove the symlink, rather than choke and abort (it's also what
the unsafe implementation does).

I think I misread the original implementation. Here is an updated version with that code just taken out.

I made two comments on rietveld but the email was rejected.

Updated patch based on Eric's comments:
 Store _supports_safe_rmdir at the module level.
 Move imports up to module level
 Skip test on non-threading build

I made another review but my mail was rejected.
http://bugs.python.org/review/4489/diff/3383/10563#newcode319
Lib/test/test_shutil.py:319: @unittest.skipIf(threading == None,
'requires threading')
You can just say skipUnless(threading, 'msg')
http://bugs.python.org/review/4489/diff/3383/10563#newcode344
Lib/test/test_shutil.py:344: raise
Shouldn’t this use self.fail?

http://bugs.python.org/review/4489/diff/3383/10563#newcode319
Lib/test/test_shutil.py:319: @unittest.skipIf(threading == None, 'requires
threading')
On 2011年10月07日 19:29:47, eric.araujo wrote:
> You can just say skipUnless(threading, 'msg')
Right.
http://bugs.python.org/review/4489/diff/3383/10563#newcode344
Lib/test/test_shutil.py:344: raise
On 2011年10月07日 19:29:47, eric.araujo wrote:
> Shouldn’t this use self.fail?
I would have thought it's better if the original exception is passed through and
displayed rather than some sort of failure message that just says "OSError
occurred".

There's a race:
"""
--- Lib/shutil.py 2011年11月05日 00:11:05.745221315 +0100
+++ Lib/shutil.py.new 2011年11月05日 00:11:01.445220324 +0100
@@ -307,6 +307,7 @@
 try:
 mode = os.fstatat(dirfd, name, os.AT_SYMLINK_NOFOLLOW).st_mode
 except os.error:
 mode = 0
 if stat.S_ISDIR(mode):
+ input("press enter")
 newfd = os.openat(dirfd, name, os.O_RDONLY)
 _rmtree_safe(newfd, ignore_errors, onerror)
 try:
"""
$ rm -rf /tmp/target
$ mkdir -p /tmp/target/etc
$ ./python -c "import shutil; shutil.rmtree('/tmp/target')"
press enter^Z
[1]+ Stopped ./python -c "import shutil; shutil.rmtree('/tmp/target')"
$ rm -r /tmp/target/etc; ln -s /etc /tmp/target/
$ fg
./python -c "import shutil; shutil.rmtree('/tmp/target')"
Traceback (most recent call last):
 File "<string>", line 1, in <module>
 File "/home/cf/python/cpython/Lib/shutil.py", line 290, in rmtree
 _rmtree_safe(fd, ignore_errors, onerror)
 File "/home/cf/python/cpython/Lib/shutil.py", line 314, in _rmtree_safe
 _rmtree_safe(newfd, ignore_errors, onerror)
 File "/home/cf/python/cpython/Lib/shutil.py", line 323, in _rmtree_safe
 onerror(os.unlinkat, (dirfd, name), sys.exc_info())
 File "/home/cf/python/cpython/Lib/shutil.py", line 321, in _rmtree_safe
 os.unlinkat(dirfd, name)
PermissionError: [Errno 13] Permission denied
[52334 refs]
"""
openat(3, "etc", O_RDONLY|O_LARGEFILE) = 4
dup(4) = 5
fstat64(5, {st_mode=S_IFDIR|0755, st_size=4096, ...}) = 0
fcntl64(5, F_GETFL) = 0x8000 (flags O_RDONLY|O_LARGEFILE)
fcntl64(5, F_SETFD, FD_CLOEXEC) = 0
getdents64(5, /* 162 entries */, 32768) = 5176
getdents64(5, /* 0 entries */, 32768) = 0
close(5) = 0
fstatat64(4, "passwd", {st_mode=S_IFREG|0644, st_size=980, ...}, AT_SYMLINK_NOFOLLOW) = 0
unlinkat(4, "passwd", 0) = -1 EACCES (Permission denied)
"""
You should use the lstat/open/fstat idiom.
Also, here:
"""
 mode1 = os.lstat(path).st_mode
 if stat.S_ISLNK(mode1):
 raise OSError("Cannot call rmtree on a symbolic link")
 except OSError:
 onerror(os.lstat, path, sys.exc_info())
 # can't continue even if onerror hook returns
 return
 fd = os.open(path, os.O_RDONLY)
 try:
 mode2 = os.fstat(fd).st_mode
 if mode1 != mode2:
 raise OSError("Target changed")
"""
You check that path is not a symlink, then you open it, perform fstat on it, and check that the mode is the same.
But if someone replaces path by a symlink to a directory with the same mode, then rmtree won't catch this. You should also compare st_dev and st_ino to make sure we're dealing with the same file.
One more thing :-)
"""
 fd = os.open(path, os.O_RDONLY)
 try:
 mode2 = os.fstat(fd).st_mode
 if mode1 != mode2:
 raise OSError("Target changed")
 except OSError:
 onerror(os.fstat, fd, sys.exc_info())
 # can't continue if target has changed
 return
"""
Here `fd` is not closed (there might be other places leaking FD).
Finally, since writting a such code is tricky, what do you - all - think of making this a generic walker method that would take as argument the methods to call on a directory and on a file (or link), so that we could reuse it to write chmodtree(), chowntree() and friends?

> Finally, since writting a such code is tricky, what do you - all -
> think of making this a generic walker method that would take as
> argument the methods to call on a directory and on a file (or link),
> so that we could reuse it to write chmodtree(), chowntree() and
> friends?
Sounds good.
FYI, I have a pathlib experiment in
http://hg.python.org/features/pathlib/, with an optional openat-based
accessor.

> FYI, I have a pathlib experiment in
> http://hg.python.org/features/pathlib/, with an optional openat-based
> accessor.
Interesting: I used to think that the current API for dealing with paths was a little too basic and terse.
Concerning this issue, one (last) thing: rmtree performs a depth-first traversal of the directory tree, keeping an open FD at each directory level: in case of deeply-nested directory hierarchy, or if there are many open FDs, there's the risk of running out of FDs.
I think the best thing would be to let rmtree fail (provided it closes all the FDs it opened): falling back to the "unsafe" version would be stupid (an attacker would just have to create a deeply-nested hierarchy, and then use the same old symlink race).

> I think the best thing would be to let rmtree fail (provided it closes 
> all the FDs it opened)
Agreed.

Thanks Charles, I'll take your comments into account and take a look at making a general walker method.

What's the current state here? Anyone working on a solution or are we waiting how http://hg.python.org/features/pathlib/ will work out?
If the consensus is to add a generic walker method, wouldn't be appropriate to open a new bug and add it as dependency? Or is there one I've missed?

> What's the current state here? Anyone working on a solution or are we
> waiting how http://hg.python.org/features/pathlib/ will work out?
Well, I am not working on that one, so waiting for it to work out might
be optimistic :)
I don't know what to do with it (the pathlib): is such a feature
desireable enough?
> If the consensus is to add a generic walker method, wouldn't be
> appropriate to open a new bug and add it as dependency?
Agreed.

> > What's the current state here? Anyone working on a solution or are we
> > waiting how http://hg.python.org/features/pathlib/ will work out?
> 
> Well, I am not working on that one, so waiting for it to work out might
> be optimistic :)
> I don't know what to do with it (the pathlib): is such a feature
> desireable enough?
Independently from this bug, I'd say it would be a good thing.
Proof: http://twistedmatrix.com/documents/current/api/twisted.python.filepath.html – Twisted already implemented something similar for themselves.
> > If the consensus is to add a generic walker method, wouldn't be
> > appropriate to open a new bug and add it as dependency?
> 
> Agreed.
See #13734 

In case you want opinions on pathlib: I, for one, disliked Jason Orendorff’s path module, because it did not distinguish between pure string operations and I/O-inducing operations, and also because it duplicated os/os.path functions. Your API doesn’t have these issues, so for my taste it’s conceptually better. I should clone your repo and play with the module a bit to see if I like it.

Anybody working on this one? I’d give it a shot otherwise.

> Anybody working on this one? I’d give it a shot otherwise.
Go ahead.
You could - should? - probably use the new os.fwalk() to walk
directories in a safe maner.

I've implemented a _safe_rmtree which gets used if os.fwalk() and os.unlinkat() are available.
Test suite still passes in regression mode both on Mac (= no effect) and Linux.
Let me know if I missed something.

+ Same a rmtree but uses safe functions to avoid race conditions
 ^
 typo
+ onerror(os.unlinkat, os.path.join(path, name), sys.exc_info())
+ onerror(os.fwalk, path, sys.exc_info())
The documentation currently states that the first argument of onerror will be one of os.path.islink, os.listdir, os.remove, os.rmdir. You shuld probably add os.unlinkat and os.fwalk to that list now.
Otherwise, looks good to me.

Thanks Petri. I've added the missing s in my repo and attach a proposed separate doc patch, I'd like reviewed by someone whose English is better than mine. :)

I'm taking Charles-François' review comments here.
> 1. since fwalk() uses O(depth directory tree) file descriptors, we might run out
> of FD on really deep directory hierarchies. It shouldn't be a problem in
> practise
Should I mention it in the docs? The old one uses recursion and we don't warn about the stack too...
> 2. there is a slight API change, since the API exposes the function that
> triggered the failure. I don't think there's a lot a of code that depends on
> this, but it's definitely a change
I was pondering whether I should "fake" the method names as they pretty much map: listdir instead of fwalk and unlink instead of unlink at... what do you all think about that?

I’ve incorporated all the feedback (I hope).
I had to refactor the tests slightly, but we have 100% code coverage for both versions of rmtree. Speaking of: I’ve renamed the default version of rmtree to _default_rmtree and _safe_rmtree to _safe_fwalk_rmtree as we’ll need more _safe versions for OS X and Windows. Also, that way the default version isn’t lost.
(this time both docs and code are in one patch, sorry for the experiment)
This might not be the final patch though as I’m waiting on feedback for the backward compatibility question (<http://mail.python.org/pipermail/python-dev/2012-May/119543.html>). That might simplify the tests again a bit if we decide to "fake".
Have a nice Sunday everyone. :)

A small docs update: I don't list the possible functions for onerror at all anymore, as that list is likely to grow and is a PITA to maintain. People shouldn’t rely on a certain set of functions here.
Martin proposed <http://mail.python.org/pipermail/python-dev/2012-May/119555.html> to re-implement os.fwalk inside of rmdir which I’m -1 <http://mail.python.org/pipermail/python-dev/2012-May/119556.html> on.
If error reporting is the only issue, I’d rather expand fwalk to supply the function that failed to the caller. Be it using a custom field in exceptions or be it using expanding its onerror.

> Martin proposed
> <http://mail.python.org/pipermail/python-dev/2012-May/119555.html> to
> re-implement os.fwalk inside of rmdir which I’m -1
> <http://mail.python.org/pipermail/python-dev/2012-May/119556.html> on.
I agree that it isn't worth the hassle.

I don't think that doing direct flistdir/fstatat calls would be more complex. We already have directory walking implemented (in default_rmtree), and I think the fd-based calls could nicely integrate with that. I'll provide a patch.

Martin, are you still committed to this? I still think code duplication is bad (especially for security related code) but I’d be willing to write a fwalk-less version so it doesn’t look like I’m just defending my code here.

> Martin, are you still committed to this?
Yes, I'll provide a patch RSN. I doubt that there will be that much code 
duplication.

Here is a patch with just the shutil changes. Compared to rmtree-with-fwalk-v3.diff, this changes 90 lines of rmtree, whereas the fwalk version changes only 70 lines. On the plus side, it's much more obvious in this version that the *at variant has the same algorithm as the non-*at version.

Fair enough, I'm not going to question your obviously superior judgement here. :)
However, your patch currently breaks the test suite on any platform that uses the fallback rmtree: You forgot the ignore_errors=False in the _rmtree_unsafe signature (and obviously also the argument when calling it as a fallback).
You also didn't seem to have touched the tests?

Martin, what exactly is the intended proceeding now? Are you going to fix your patch and tests as soon as you have time or was that just a PoC and expect me/us to bring it into shape? (<- troll-free question, I have no idea what to do next here and would like to see a safe rmtree in 3.3)

> Martin, what exactly is the intended proceeding now? Are you going to
> fix your patch and tests as soon as you have time or was that just a
> PoC and expect me/us to bring it into shape? (<- troll-free question,
> I have no idea what to do next here and would like to see a safe
> rmtree in 3.3)
I still plan to work on this, but I'm also really really short on time.
I still favor my own approach (obviously), so if you want to bring it
into shape - that would be appreciated.

I'll try to get it in before beta1 then.

Here is my revised patch with Martin's code integrated.
Differences:
 - fixed docs
 - added some tests, test_on_errors could still use some refactorings though
 - renamed _rmtree_safe to _rmtree_safe_fd so we can implement more of them
 - _rmtree_safe_fd & _rmtree_unsafe don't need default arguments and the unsafe version also doesn't need argument normalization as both get onerror filled out by rmtree.
If nobody objects, I'd commit it soonish (definitely before Sunday).

New changeset c910af2e3c98 by Hynek Schlawack in branch 'default':
#4489: Add a shutil.rmtree that isn't suspectible to symlink attacks
http://hg.python.org/cpython/rev/c910af2e3c98 

New changeset 53fc7f59c7bb by Hynek Schlawack in branch 'default':
#4489: Fix usage of fd-based functions to new api introduced earlier today
http://hg.python.org/cpython/rev/53fc7f59c7bb 

Can I suggest setting a "safe" attribute on the rmtree function object instead of adding another name to the module?

I thought about that too but couldn't find a precedent (I didn't look very long though :)) where we've done that before so I went for an attribute. I'd change it immediately if others agree.

I'm in the process of updating the LBYL support to use a "rmtree.avoids_symlink_attacks" function attribute rather than the "rmtree_is_safe" module level attribute.
As I said in the hmac.secure_compare function discussion, the words "safe" and "secure" are too vague to ever make for good API design. Much better to tell people exactly what they're safe against (rmtree_is_safe -> rmtree.avoids_symlink_attacks), or designed to be appropriate for (hmac.secure_compare -> hmac.compare_digest).

Excellent Nick! I discussed the very same thing with David yesterday but somehow we didn't come up with a good name. So we kept it on "safe" (which predates the secure discussion).

Bikeshedding:
(os.unlink in os.supports_dir_fd and os.open in os.supports_dir_fd)
could be rewritten as
{ os.open, os.unlink } <= os.supports_dir_fd
As you were!

The code using set operations seems slightly too cryptic for me, even though I’m comfortable with sets and functions as first-class objects. A matter of taste I guess.
BTW it sounds a bit strange to me to have the verb in the singular in supports_dir_fd when its meaning is "the functions in this set support dir_fd". I guess it’s too late to propose "os.open.supports_dir_fd and os.unlink.supports_dir_fd" (and I don’t know if that is feasible with C functions) :)

New changeset c2be81151994 by Nick Coghlan in branch 'default':
Issue #4489: Rename the feature marker for the symlink resistant rmtree and store it as a function attribute
http://hg.python.org/cpython/rev/c2be81151994 

> I guess it’s too late to propose "os.open.supports_dir_fd and
> os.unlink.supports_dir_fd" (and I don’t know if that is feasible
> with C functions) :)
Where were you when "is_implemented" was being savagely torn apart last week? ;-)

I was at work, and moving out of my apartment, and desperating at the subthreads spawned by my mail about packaging, and agreeing with the people being -1 on is_implemented on Signature objects :-)

Éric - there's almost certainly going to be a PEP for 3.4 about doing this kind of feature advertisement in a cleaner and more consistent way.

Yep, that is promising. At worst we’ll have a new cool API and three obsolete sets in the os module, not a big deal.

Okay everyone, let's call it day – after 3,5 years. :) Further enhancement requests please in separate tickets. Thanks to everybody who took part!

The fix for this issue broke support for bytes in shutil.rmtree:
$ mkdir -p /tmp/a/b
$ python3.2 -c 'import shutil; shutil.rmtree(b"/tmp/a")'
$ mkdir -p /tmp/a/b
$ python3.3 -c 'import shutil; shutil.rmtree(b"/tmp/a")'
Traceback (most recent call last):
 File "<string>", line 1, in <module>
 File "/usr/lib64/python3.3/shutil.py", line 444, in rmtree
 _rmtree_safe_fd(fd, path, onerror)
 File "/usr/lib64/python3.3/shutil.py", line 381, in _rmtree_safe_fd
 fullname = os.path.join(path, name)
 File "/usr/lib64/python3.3/posixpath.py", line 78, in join
 if b.startswith(sep):
TypeError: startswith first arg must be str or a tuple of str, not bytes
$

> The fix for this issue broke support for bytes in shutil.rmtree:
What platform? Windows, or non-Windows? It'll probably be obvious regardless, but that might help.

Tinkering with os.path.join, that traceback means that "name" is a str instance, while "path" is a bytes instance.
The culprit actually appears to be the fact that the type returned by os.listdir (et al) when handed a file descriptor is always a string (this is not explicitly documented, a problem in itself, but that's the behaviour I see here on linux).
One way to handle this would be to use the filesystem encoding with surrogateescape to decode any bytes path passed in to shutil.rmtree (at least in the _rmtree_safe_fd case) and handle the actual removal with Unicode throughout.
So long as the original encoding of the supplied bytes path is compatible with that of the underlying filesystem, surrogateescape should ensure that everything round trips correctly.

Your deduction is correct. listdir can't tell what the original argument type was based on the output--path_converter abstracts away those details. So it separately tests the type of the first argument. Staring at it again it's about as clear as mud, but the goal was, the output is always strings unless the user specified "path" as bytes.
I'll make a separate issue regarding making the code easier to read and adding a clarification to the documentation. We should spare future programmers from having to guess at this behavior :)

New changeset 2e2329aeb5c1 by Hynek Schlawack in branch 'default':
#4489 Make fd based rmtree work on bytes
http://hg.python.org/cpython/rev/2e2329aeb5c1 

The fix (c910af2e3c98 + 53fc7f59c7bb) for this issue broke deletion of directories, which contain symlinks to directories.
(Directories with symlinks to regular files or symlinks to nonexistent files are unaffected.)
$ mkdir -p /tmp/a/b
$ ln -s b /tmp/a/c
$ python3.2 -c 'import shutil; shutil.rmtree("/tmp/a")'
$ mkdir -p /tmp/a/b
$ ln -s b /tmp/a/c
$ python3.3 -c 'import shutil; shutil.rmtree("/tmp/a")'
Traceback (most recent call last):
 File "<string>", line 1, in <module>
 File "/usr/lib64/python3.3/shutil.py", line 447, in rmtree
 _rmtree_safe_fd(fd, path, onerror)
 File "/usr/lib64/python3.3/shutil.py", line 395, in _rmtree_safe_fd
 _rmtree_safe_fd(dirfd, fullname, onerror)
 File "/usr/lib64/python3.3/shutil.py", line 406, in _rmtree_safe_fd
 onerror(os.rmdir, path, sys.exc_info())
 File "/usr/lib64/python3.3/shutil.py", line 404, in _rmtree_safe_fd
 os.rmdir(path)
NotADirectoryError: [Errno 20] Not a directory: '/tmp/a/c'
$

New changeset f9f798f1421e by Hynek Schlawack in branch 'default':
#4489: Don't follow ever symlinks in rmtree
http://hg.python.org/cpython/rev/f9f798f1421e 

Thanks you for catching that! It seems we did something really stupid: followed symlinks.
I’ve fixed that and added regression tests. This one is a facepalm gentlepeople.

I'm not a security guy, but: shouldn't the os.unlink call when it isn't a directory specify follow_symlinks=False? And wouldn't it be safer if the os.rmdir() call also used dir_fd=?
Additionally, I think you missed some stuff for shutil._use_fd_functions. Assuming I'm right on both of the above, you should also check:
* os.listdir in os.supports_dir_fd
* os.rmdir in os.supports_dir_fd
* os.stat in os.supports_dir_fd
* os.stat in os.supports_follow_symlinks
* os.unlink in os.supports_follow_symlinks
I'd spell that
_use_fd_functions = ({os.listdir, os.open, os.rmdir, os.stat, os.unlink} < 
 os.supports_dir_fd and
 {os.stat, os.unlink} <= os.supports_follow_symlinks)
Finally, up to you, but I'd be tempted to change the "lstat" "and "fstat" calls to "stat" calls using the relevant parameters.

> I'm not a security guy, but: shouldn't the os.unlink call when it isn't a directory specify follow_symlinks=False? 
os.unlink has no follow_symlinks argument. Imagine what would happen if
you‘d do a os.unlink() on a link and it would just remove the link
destination. :)
> And wouldn't it be safer if the os.rmdir() call also used dir_fd=?
Unfortunately, os.rmdir('.', dir_fd=topfd) doesn’t work. As in the worst
case it could delete only an empty directory, I think it’s fine.
> Additionally, I think you missed some stuff for shutil._use_fd_functions. Assuming I'm right on both of the above, you should also check:
> * os.listdir in os.supports_dir_fd
> * os.rmdir in os.supports_dir_fd
> * os.stat in os.supports_dir_fd
> * os.stat in os.supports_follow_symlinks
> * os.unlink in os.supports_follow_symlinks
Interestingly, os.listdir is not in os.supports_dir_fd although it works:
False
Will you fix it right away or shall I open a ticket?
> I'd spell that
> _use_fd_functions = ({os.listdir, os.open, os.rmdir, os.stat, os.unlink} < 
> os.supports_dir_fd and
> {os.stat, os.unlink} <= os.supports_follow_symlinks)
It would be:
_use_fd_functions = ({os.listdir, os.open, os.stat, os.unlink} <=
 os.supports_dir_fd and
 os.stat in os.supports_follow_symlinks)
But currently can’t do.
> Finally, up to you, but I'd be tempted to change the "lstat" "and "fstat" calls to "stat" calls using the relevant parameters.
That's not 3.3 fodder IMHO, feel free to open an enhancement ticket.

I'm pretty busy right now, please open a ticket for listdir.
_rmtree_safe_fd could remove the directory just after the recursive step using the parent's dirfd. Of course you'd also have to add a rmdir for the very-tippy-top after the original call in shutil.rmtree too. But this would prevent the malicious user from even removing empty directories.

> I'm pretty busy right now, please open a ticket for listdir.
done
> _rmtree_safe_fd could remove the directory just after the recursive step using the parent's dirfd. Of course you'd also have to add a rmdir for the very-tippy-top after the original call in shutil.rmtree too. But this would prevent the malicious user from even removing empty directories.
Okay I looked into it and it seems okay. IIRC, when Martin wrote the
code (and I the fwalk version before), there was no known fd-based rmdir
function.

New changeset 9134bb4d0578 by Hynek Schlawack in branch 'default':
#4489: Use dir_fd in rmdir in _rmtree_safe_fd()
http://hg.python.org/cpython/rev/9134bb4d0578