Obscure overflow with very long path; completion

Obscure overflow with very long path; completion

[David Remahl]

I found an interesting problem today...I'm not familiar enough with  
the code base to fully diagnose it myself, so I need your help.  
Although I think it is unlikely, it may have security implications.

Summary:
Some very special circumstances triggers a buffer overflow of some  
kind (I believe it is on the heap, but I have not had time to look  
into it in detail) in the cd builtin.

How to reproduce:
0) The following steps assume that you are working on a file system  
that supports (very) long path names. zsh on Mac OS X 10.4 satisfies  
this, but I have not tested it on other systems.
1) Perform the following script to create a string of 100  
directories, each with a 20 character name in /tmp/work:

mkdir work
cd work

$i=0

while ((i++ < 100)); do
     mkdir "aaaaaaaaaaaaaaaaaaaa"
     cd "aaaaaaaaaaaaaaaaaaaa"
done

2) cd /tmp/work
3) autoload -U compinit; compinit -u
4) cdpath=(.. ~)
5) cd a couple of levels. Type "a" followed by <tab> and "/", then  
tab a number of times.
6) Repeat 5) until you reach the end of the directory hierarchy.  
Pressing tab to complete at this time does nothing or beeps.
7) Press enter.

Expected result:
No crash. I expected cwd to be set to /tmp/work/aaaaaaaaaaaaaaaaaaaa/ 
aaaaaaaaaaaaaaaaaaaa/......./aaaaaaaaaaaaaaaaaaaa

Actual result:
zsh crashes with the following backtrace:

0   libSystem.B.dylib     0x90003364 strcmp + 132
1   zsh                   0x0005ea24 finddir + 164
2   zsh                   0x0005e820 fprintdir + 28
3   zsh                   0x00004a84 cd_able_vars + 1184
4   zsh                   0x00003e00 bin_cd + 464
5   zsh                   0x00002cc4 execbuiltin + 1436
6   zsh                   0x00015838 execsubst + 7144
7   zsh                   0x00012d14 execlist + 4816
8   zsh                   0x000122a0 execlist + 2140
9   zsh                   0x00011c38 execlist + 500
10  zsh                   0x00011888 execode + 68
11  zsh                   0x000268a4 loop + 676
12  zsh                   0x00029470 zsh_main + 596
13  zsh                   0x00001d18 start + 412
14  zsh                   0x00001bb8 start + 60

The full crash log can be found below. Note how address 0x61616161 is  
accessed, indicating that our string of "a":s has overwritten  
something it should not have clobbered. Completion must be turned on,  
and cdpath must be set to (.. ~) (just .. may be sufficient).

I hope someone more experienced with zsh can have a look and fix the  
problem.

/ Regards, David Remahl

% zsh --version
zsh 4.2.3 (powerpc-apple-darwin8.0)

Command: zsh
Path:    /bin/zsh
Parent:  login [4067]

Version: ??? (???)

PID:    4068
Thread: 0

Exception:  EXC_BAD_ACCESS (0x0001)
Codes:      KERN_INVALID_ADDRESS (0x0001) at 0x61616161

Thread 0 Crashed:
0   libSystem.B.dylib     0x90003364 strcmp + 132
1   zsh                   0x0005ea24 finddir + 164
2   zsh                   0x0005e820 fprintdir + 28
3   zsh                   0x00004a84 cd_able_vars + 1184
4   zsh                   0x00003e00 bin_cd + 464
5   zsh                   0x00002cc4 execbuiltin + 1436
6   zsh                   0x00015838 execsubst + 7144
7   zsh                   0x00012d14 execlist + 4816
8   zsh                   0x000122a0 execlist + 2140
9   zsh                   0x00011c38 execlist + 500
10  zsh                   0x00011888 execode + 68
11  zsh                   0x000268a4 loop + 676
12  zsh                   0x00029470 zsh_main + 596
13  zsh                   0x00001d18 start + 412
14  zsh                   0x00001bb8 start + 60

Thread 0 crashed with PPC Thread State:
   srr0: 0x90003364 srr1: 0x0200f030                vrsave: 0x00000000
     cr: 0x48022244  xer: 0x20000004   lr: 0x0005ea24  ctr: 0x000003a7
     r0: 0x000003a7   r1: 0xbffff4e0   r2: 0x00075bec   r3: 0x0181a400
     r4: 0x6161615d   r5: 0xfefefeff   r6: 0x80808080   r7: 0x2f707269
     r8: 0x00000000   r9: 0x00000e9f  r10: 0x5642feff  r11: 0x00071534
    r12: 0x900032e0  r13: 0x00000001  r14: 0x00000000  r15: 0x00000000
    r16: 0x00000000  r17: 0xbffff760  r18: 0x0007f7c0  r19: 0xbffff740
    r20: 0x0006e1f0  r21: 0x00000001  r22: 0x00073c38  r23: 0xbffff760
    r24: 0x00073c38  r25: 0x000748cc  r26: 0x0000000a  r27: 0x0181a400
    r28: 0x0181a400  r29: 0x0006e990  r30: 0x000759dc  r31: 0x0005e990

Binary Images Description:
     0x1000 -    0x6dfff zsh     /bin/zsh
    0x97000 -    0x9bfff parameter.so     /usr/lib/zsh/4.2.3/zsh/ 
parameter.so
    0x9f000 -    0xc0fff zle.so     /usr/lib/zsh/4.2.3/zsh/zle.so
    0xce000 -    0xe4fff complete.so     /usr/lib/zsh/4.2.3/zsh/ 
complete.so
    0xea000 -    0xeefff zutil.so     /usr/lib/zsh/4.2.3/zsh/zutil.so
   0x205000 -   0x210fff computil.so     /usr/lib/zsh/4.2.3/zsh/ 
computil.so
0x8fe00000 - 0x8fe50fff dyld 43    /usr/lib/dyld
0x90000000 - 0x901a6fff libSystem.B.dylib     /usr/lib/libSystem.B.dylib
0x901fe000 - 0x90202fff libmathCommon.A.dylib     /usr/lib/system/ 
libmathCommon.A.dylib
0x92c9b000 - 0x92d89fff libiconv.2.dylib     /usr/lib/libiconv.2.dylib
0x9680c000 - 0x9683afff libncurses.5.4.dylib     /usr/lib/libncurses. 
5.4.dylib

Model: PowerBook3,5, BootROM 4.5.3f2, 1 processors, PowerPC G4   
(3.2), 1 GHz, 1 GB
Graphics: ATY,RV250M9, ATY,RV250M9, AGP, 64 MB
Memory Module: SODIMM0/J16TOP, 512 MB, SDRAM, PC133U-333
Memory Module: SODIMM1/J16BOTTOM, 512 MB, SDRAM, PC133U-333
AirPort: AirPort, 9.52
Modem: MicroDash, Euro, V.92, 1.0F, APPLE VERSION 2.6.4
Network Service: AirPort, AirPort, en1
PCI Card: TXN,PCI1410-02, cardbus, PC Card
Parallel ATA Device: FUJITSU MHS2060AT, 55.89 GB
Parallel ATA Device: MATSHITADVD-R   UJ-815, 3.91 GB

Re: Obscure overflow with very long path; completion

[Peter Stephenson]

David Remahl wrote:
> Summary:
> Some very special circumstances triggers a buffer overflow of some  
> kind (I believe it is on the heap, but I have not had time to look  
> into it in detail) in the cd builtin.

I couldn't get this to happen with Fedora Core 3 on x86.  It's possible
it's some library bug, but I agree it's more likely there's some
well-masked problem in memory management in zsh.

-- 
Peter Stephenson <pws@csr.com>                  Software Engineer
CSR PLC, Churchill House, Cambridge Business Park, Cowley Road
Cambridge, CB4 0WZ, UK                          Tel: +44 (0)1223 692070


**********************************************************************
This email and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they
are addressed. If you have received this email in error please notify
the system manager.

**********************************************************************

Re: Obscure overflow with very long path; completion

[Geoff Wing]

Peter Stephenson <pws@csr.com> typed:
: David Remahl wrote:
:> Summary:
:> Some very special circumstances triggers a buffer overflow of some  
:> kind (I believe it is on the heap, but I have not had time to look  
:> into it in detail) in the cd builtin.
: I couldn't get this to happen with Fedora Core 3 on x86.  It's possible
: it's some library bug, but I agree it's more likely there's some
: well-masked problem in memory management in zsh.

I get 98 of them built using the provided method before crashing.  Then

% zsh -f
% cd /tmp
% for I in {1..98}; cd aaaaaaaaaaaaaaaaaaaa
% pwd | wc
       1       1    2063
% setopt chaselinks
% cd /tmp
% for I in {1..98}; cd aaaaaaaaaaaaaaaaaaaa

(gdb) bt
#0  0xbdbcba91 in xsymlink (
    s=0x80e80c8 "/tmp/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/aaaaaa"...) at utils.c:395
#1  0xbdbcb701 in findpwd (
    s=0x80e80c8 "/tmp/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/", 'a' <repeats 20 times>, "/aaaaaa"...) at utils.c:279
#2  0xbdb7482e in cd_new_pwd (func=10, dir=0x8091ca8) at builtin.c:1107

These two in utils.c:
   static char xbuf[PATH_MAX*2];
and
   char xbuf2[PATH_MAX*2], ...
are insufficient because the path is over twice the allowed PATH_MAX (1024) on
my machine.  I guess there should be some limiters to stop somewhere and obey
PATH_MAX (or some magic number we wish to support).

Regards,
Geoff

Re: Obscure overflow with very long path; completion

[Bart Schaefer]

On May 6,  4:10am, Geoff Wing wrote:
} Subject: Re: Obscure overflow with very long path; completion
}
} These two in utils.c:
}    static char xbuf[PATH_MAX*2];
} and
}    char xbuf2[PATH_MAX*2], ...
} are insufficient because the path is over twice the allowed PATH_MAX
} (1024) on my machine.

Try this patch?

My fear is that this is going to lead to slowness such as that fixed by
the recent patches to the globbing code, but hopefully this isn't called
quite as often.

Index: Src/utils.c
===================================================================
retrieving revision 1.23
diff -c -r1.23 utils.c
--- Src/utils.c	14 Apr 2005 04:33:51 -0000	1.23
+++ Src/utils.c	7 May 2005 16:11:26 -0000
@@ -358,14 +358,19 @@
 	    *p = '\0';
 	    continue;
 	}
-	sprintf(xbuf2, "%s/%s", xbuf, *pp);
-	t0 = readlink(unmeta(xbuf2), xbuf3, PATH_MAX);
+	if (ztrlen(xbuf) >= PATH_MAX-1 || ztrlen(*pp) >= PATH_MAX-1) {
+	  t0 = -1;
+	} else {
+	  sprintf(xbuf2, "%s/%s", xbuf, *pp);
+	  t0 = readlink(unmeta(xbuf2), xbuf3, PATH_MAX);
+	}
 	if (t0 == -1) {
 	    strcat(xbuf, "/");
 	    strcat(xbuf, *pp);
 	    zsfree(*pp);
 	} else {
-	    ret = 1;
+	    DPUTS(t0 == PATH_MAX, "BUG: overflow in readlink()");
+ 	    ret = 1;
 	    metafy(xbuf3, t0, META_NOALLOC);
 	    if (*xbuf3 == '/') {
 		strcpy(xbuf, "");

Re: Obscure overflow with very long path; completion

[Geoff Wing]

On Saturday 2005-05-07 16:23 +1000, Bart Schaefer output:
:Try this patch?

Quick response.  Haven't investigated.

% cd /tmp
% for I in {1..100}; mkdir aaaaaaaaaaaaaaaaaaaa && cd aaaaaaaaaaaaaaaaaaaa
MEM: allocation error at sbrk.
zsh: fatal error: out of memory
% 
% gdb zsh
(gdb) run
% cd /tmp
% for I in {1..100}; cd aaaaaaaaaaaaaaaaaaaa
(gdb) bt
#0  0xbdb94f83 in strcmp () from /usr/lib/libc.so.12
#1  0x61616161 in ?? ()
(stack trashed)

Re: Obscure overflow with very long path; completion

[Bart Schaefer]

On May 8, 10:41am, Geoff Wing wrote:
} Subject: Re: Obscure overflow with very long path; completion
}
} On Saturday 2005-05-07 16:23 +1000, Bart Schaefer output:
} :Try this patch?
} 
} Quick response.  Haven't investigated.
} 
} % cd /tmp
} % for I in {1..100}; mkdir aaaaaaaaaaaaaaaaaaaa && cd aaaaaaaaaaaaaaaaaaaa
} MEM: allocation error at sbrk.
} zsh: fatal error: out of memory

Hmm.

I finally had a chance to gdb-trace this, and although I only get it to
crash -- in finddir() -- with 500 levels of directory and only when I
"setopt chaselinks", I think my patch is incomplete even for xsymlinks().

Potential problems are in:

zexecve		exec.c 357		via exec.c 590
execute		exec.c 560
findcmd		exec.c 643		(if $path contains a long path)
xsymlinks	utils.c 340
finddir		utils.c 500

There are a number of other places that use PATH_MAX, but they all seem
(from examination, not rigorous testing) to check for overflow.