Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

#74 Integer overflow during brace expansion

open
nobody
Core shell (16)
5
2013-01-25
2012-02-27
Leon Weber
No

When parsing and expanding brace expressions (e.g. {1..3}), zsh can encounter integer overflows because the range start and end values are stored in two integers without proper bounds checking (rstart and rend in glob.c:2092 in git revision eaaf6bbb). Particularly, this happens when one of the range boundaries is <=-2147483648 or >=2147483648, like in this example:

zsh% echo {-2147483648..-2147483646}

This will cause zsh to eat up 100% CPU iterating through the loop declared in line 2147 in glob.c. In that loop, rend is decreased until it underflows. In the third and fourth iterations, we have these conditions:

//
// third iteration
//
Breakpoint 15, xpandbraces (list=0x7ffff7fee340, np=0x7fffffffd460) at glob.c:2149
2149 p = dupstring(str3);
(gdb) p rend
$56 = -2147483648
(gdb) p rstart
$57 = -2147483648
(gdb) cont
Continuing.

//
// fourth iteration
//
Breakpoint 15, xpandbraces (list=0x7ffff7fee340, np=0x7fffffffd460) at glob.c:2149
2149 p = dupstring(str3);
(gdb) p rend
$58 = 2147483647
(gdb) p rstart
$59 = -2147483648

This gdb output clearly shows that rend has underflown and is now at the far positive end of the valid integer values. zsh will keep iterating over that loop and decreasing rend for a really long time.

For comparison, a bash shell handles this correctly:

bash$ echo {-2147483648..-2147483646}
-2147483648 -2147483647 -2147483646

I have been able reproduce this issue on Ubuntu x86_64 and x86 using zsh 4.3.10, 4.3.11, and git revision db7d0ac34143ed2378c2fd98845b2ae5eaaf6bbb.

Discussion