php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #52550 integer undefined behaviors executed during "make test"
Submitted: 2010-08-06 07:30 UTC Modified: 2013-12-05 19:49 UTC
Votes:1
Avg. Score:2.0 ± 0.0
Reproduced:0 of 0 (0.0%)
From: regehr at cs dot utah dot edu Assigned:
Status: Feedback Package: *General Issues
PHP Version: master OS: linux
Private report: No CVE-ID:
Have you experienced this issue?
Rate the importance of this bug to you:

 [2010-08-06 07:30 UTC] regehr at cs dot utah dot edu
Description:
------------
I run php-trunk-201008060430's "make test" under a tool that detects integer undefined behaviors.  This is on an x86 box running Ubuntu 10.04.  The list of problems is below.  Some of these could be security problems waiting to happen.

Hopefully the error messages are self-explanatory.  If more details are required, please let me know.

</home/regehr/z/php-trunk-201008060430/Zend/zend_compile.c, (5144:5)> : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int32): 2147483640 right (int32): 9 

</home/regehr/z/php-trunk-201008060430/Zend/zend_compile.c, (5144:5)> : Op: -, Reason : Signed Subtraction Overflow, UNARY OPERATION: left (int32): 0 right (int32): -2147483648 

</home/regehr/z/php-trunk-201008060430/Zend/zend_compile.c, (5176:4)> : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int32): 2147483640 right (int32): 8 

</home/regehr/z/php-trunk-201008060430/Zend/zend_compile.c, (5176:4)> : Op: -, Reason : Signed Subtraction Overflow, UNARY OPERATION: left (int32): 0 right (int32): -2147483648 

</home/regehr/z/php-trunk-201008060430/Zend/zend_hash.h, (350:2)> : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int32): 2147483640 right (int32): 8 

</home/regehr/z/php-trunk-201008060430/Zend/zend_hash.h, (350:2)> : Op: -, Reason : Signed Subtraction Overflow, UNARY OPERATION: left (int32): 0 right (int32): -2147483648 

</home/regehr/z/php-trunk-201008060430/Zend/zend_operators.c, (1181:2)> : Op: <<, Reason : Signed Left Shift Error: Right operand is negative or is greater than or equal to the width of the promoted left operand, BINARY OPERATION: left (int32): 0 right (int32): 65 

</home/regehr/z/php-trunk-201008060430/Zend/zend_operators.c, (1194:2)> : Op: >>, Reason : Signed Right Shift Error: Right operand is negative or is greater than or equal to the width of the promoted left operand, BINARY OPERATION: left (int32): 0 right (int32): 65 

</home/regehr/z/php-trunk-201008060430/Zend/zend_operators.c, (766:31)> : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int32): 2147483647 right (int32): 1 

</home/regehr/z/php-trunk-201008060430/Zend/zend_operators.c, (828:31)> : Op: -, Reason : Signed Subtraction Overflow, BINARY OPERATION: left (int32): -2147483648 right (int32): 1 

</home/regehr/z/php-trunk-201008060430/ext/date/lib/parse_tz.c, (133:35)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int32): 255 right (int32): 16777216 

</home/regehr/z/php-trunk-201008060430/ext/ereg/regex/regcomp.c, (350:3)> : Op: -, Reason : Signed Subtraction Overflow, BINARY OPERATION: left (int32): 35 right (int32): 34 

</home/regehr/z/php-trunk-201008060430/ext/ereg/regex/regcomp.c, (351:3)> : Op: -, Reason : Signed Subtraction Overflow, BINARY OPERATION: left (int32): 35 right (int32): 33 

</home/regehr/z/php-trunk-201008060430/ext/ereg/regex/regcomp.c, (955:3)> : Op: -, Reason : Signed Subtraction Overflow, BINARY OPERATION: left (int32): 15 right (int32): 14 

</home/regehr/z/php-trunk-201008060430/ext/ereg/regex/regcomp.c, (956:3)> : Op: -, Reason : Signed Subtraction Overflow, BINARY OPERATION: left (int32): 15 right (int32): 13 

</home/regehr/z/php-trunk-201008060430/ext/spl/php_spl.c, (748:17)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int32): 1281072119 right (int32): 993 

</home/regehr/z/php-trunk-201008060430/ext/standard/math.c, (130:24)> : Op: -, Reason : Signed Subtraction Overflow, BINARY OPERATION: left (int32): 14 right (int32): -2147483648 

</home/regehr/z/php-trunk-201008060430/ext/standard/math.c, (693:2)> : Op: /, Reason : Divisor is 0, BINARY OPERATION: left (double): 1.000000 right (double): 0.000000 

</home/regehr/z/php-trunk-201008060430/ext/standard/rand.c, (239:10)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int32): 1281072285 right (int32): 7685 

</home/regehr/z/php-trunk-201008060430/ext/standard/rand.c, (255:10)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int32): 1281072284 right (int32): 7583 

</home/regehr/z/php-trunk-201008060430/ext/standard/rand.c, (322:16)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int32): 1281072284 right (int32): 7581 

</home/regehr/z/php-trunk-201008060430/ext/standard/rand.c, (68:13)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int32): 1281072357 right (int32): 9099 

</home/regehr/z/php-trunk-201008060430/ext/standard/string.c, (1876:7)> : Op: -, Reason : Signed Subtraction Overflow, UNARY OPERATION: left (int32): 0 right (int32): -2147483648 

</home/regehr/z/php-trunk-201008060430/ext/standard/string.c, (1954:8)> : Op: -, Reason : Signed Subtraction Overflow, UNARY OPERATION: left (int32): 0 right (int32): -2147483648 

</home/regehr/z/php-trunk-201008060430/ext/standard/string.c, (1986:7)> : Op: -, Reason : Signed Subtraction Overflow, UNARY OPERATION: left (int32): 0 right (int32): -2147483648 

</home/regehr/z/php-trunk-201008060430/ext/standard/string.c, (4886:29)> : Op: -, Reason : Signed Subtraction Overflow, BINARY OPERATION: left (int32): -2147483647 right (int32): 9 

</home/regehr/z/php-trunk-201008060430/ext/standard/string.c, (4904:19)> : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int32): 2147483647 right (int32): 1 

</home/regehr/z/php-trunk-201008060430/ext/standard/var_unserializer.c, (228:25)> : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int32): 2147483640 right (int32): 55 

</home/regehr/z/php-trunk-201008060430/ext/standard/var_unserializer.c, (228:34)> : Op: -, Reason : Signed Subtraction Overflow, BINARY OPERATION: left (int32): -2147483601 right (int32): 48 

<conftest.cpp, (60:13)> : Op: %, Reason : Signed Modulus Error: The first operand is INT_MIN, the second operand is -1, BINARY OPERATION: left (int32): -2147483648 right (int32): -1 



Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2010-08-06 08:00 UTC] rasmus@php.net
-Status: Open +Status: Analyzed
 [2010-08-06 08:00 UTC] rasmus@php.net
They don't make much sense to me.  Starting from the bottom, conftest.cpp is a 
test file generated by the autoconf/libtool chain and only used during the 
configure run.  So even if there was an issue in that, it really wouldn't matter 
since no user data ever gets to it, and even if it did, you are reporting it to 
the wrong project.

Next one up, ext/standard/var_unserializer.c line 228?  There is no substraction 
there.  But assuming it means close to line 228, it would be in the parse_iv2() 
function?  I see nothing wrong with that code.  The only code in it that does 
any sort of addition is:

        if (cursor >= '0' && cursor <= '9') {
            result = result * 10 + cursor - '0';

How exactly do you get a signed subtraction overflow from that?  cursor is 
constrained and result is initialized to 0.

The 3rd last one seems to point at the same code.

There may very well be bugs hiding in there, but a static analysis full of false 
positives isn't very useful.
 [2010-08-06 08:10 UTC] regehr at cs dot utah dot edu
Hi--  It's not static analysis and there are no false positives.  These behaviors really happen (unless our tool is buggy, of course this is always possible).

Yes, I should have edited out the undefined behavior that occurred during conftest.

My copy of var_unserializer.c has this code at line 228:

	result = result * 10 + cursor - '0';

It looks to me like "result * 10 + cursor" evaluates to -2147483601 and then the subtraction overflow occurs.  This is not obvious?  Anyway, this is easy to verify: put an appropriate assertion in the code and run "make test" yourself.
 [2010-08-06 08:33 UTC] rasmus@php.net
No, it isn't obvious since that line of code is only executed when the value of 
cursor is between '0' and '9'.  It would require the argument to parse_iv2() to be  
above MAXINT which re2c checks for earlier.
 [2010-08-06 16:52 UTC] regehr at cs dot utah dot edu
Hi Rasmus-- You're right, this overflow is not totally obvious. It occurs when '2147483647;' is passed to parse_iv2() in this test:

  ext/standard/tests/serialize/serialization_miscTypes_001.phpt

The first problem is that the signed add in (result * 10 + cursor) overflows; the subtraction overflow is secondary.  If you re-associate the expression and instead compute (result * 10 + (cursor - '0')) the problems go away.
 [2010-08-06 16:57 UTC] regehr at cs dot utah dot edu
To reiterate: this isn't static analysis.  Our tool runs your code under your test suite and looks for integer operations that the C standard tells us are undefined.  I manually verified a few more of these reported bugs and they were also real.  Anyway, I leave the rest to you.  Thanks.
 [2010-08-06 17:43 UTC] rasmus@php.net
Do you have a way to generate the list with the test case filename that triggered 
the problem?
 [2010-08-06 19:21 UTC] regehr at cs dot utah dot edu
Is there a way to attach files here?  Anyway I've put a verbose error log here:

http://www.cs.utah.edu/~regehr/php-trunk-201008060430-errors.txt

Searching for lines containing the string "CLANG UNDEFINED" in this log should give you the right information.
 [2010-08-06 20:19 UTC] rasmus@php.net
Automatic comment from SVN on behalf of rasmus
Revision: http://svn.php.net/viewvc/?view=revision&amp;revision=301934
Log: Do these ops in the right order here.  First of many fixes for
bug #52550
 [2010-08-06 21:11 UTC] iliaa@php.net
Automatic comment from SVN on behalf of iliaa
Revision: http://svn.php.net/viewvc/?view=revision&amp;revision=301936
Log: Use correct order of operations. Second of many fixes for bug #52550
 [2010-08-06 21:20 UTC] rasmus@php.net
Hey, we are starting to see the light on these.  Some of them are quite subtle.  Is this tool available so we can check out fixes and run it on a continuous basis before new releases?
 [2010-08-06 21:42 UTC] regehr at cs dot utah dot edu
The tool isn't yet available.  It is a modified version of LLVM's Clang compiler and it still has some rough edges that we're working out.  However, we'll contribute it to the LLVM project fairly soon, at which point it'll be really easy to run as you suggest.  In the meantime I'd be happy to rerun it in a few weeks or whenever seems good to you.
 [2010-08-06 21:55 UTC] iliaa@php.net
Automatic comment from SVN on behalf of iliaa
Revision: http://svn.php.net/viewvc/?view=revision&amp;revision=301938
Log: Fixed issues inside str_pad() identified by bug #52550
 [2010-08-06 22:04 UTC] iliaa@php.net
Automatic comment from SVN on behalf of iliaa
Revision: http://svn.php.net/viewvc/?view=revision&amp;revision=301939
Log: Another fix for issue indentified in bug #52550
 [2010-08-06 23:53 UTC] regehr at cs dot utah dot edu
FYI there are a few bogus errors in the list I posted earlier.  Obviously (35 - 33) is well-defined in C.  Sorry about that.  It should be easy to recognize and ignore these.
 [2010-08-08 17:45 UTC] iliaa@php.net
Automatic comment from SVN on behalf of iliaa
Revision: http://svn.php.net/viewvc/?view=revision&amp;revision=301991
Log: Additional fix for bug #52550 &amp; fix test &amp; warning from previous fixes
 [2010-09-03 05:52 UTC] regehr at cs dot utah dot edu
Below are some updated results from our integer undefined behavior checker.  These are from php-trunk-201009022030 on x86-64 Linux.

The .log files from "make test" can be found here:

http://www.cs.utah.edu/~regehr/php-trunk-201009022030.test-logs.tar.gz

Basically you just want to grep for "CLANG UNDEFINED" in these files.

Summary:

</home/regehr/z/php-trunk-201009022030/Zend/zend_hash.h, (350:2)> : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int64): 9223372036854775800 right (int64): 8 

</home/regehr/z/php-trunk-201009022030/Zend/zend_hash.h, (350:2)> : Op: -, Reason : Signed Subtraction Overflow, UNARY OPERATION: left (int64): 0 right (int64): -9223372036854775808 

</home/regehr/z/php-trunk-201009022030/Zend/zend_operators.c, (1181:2)> : Op: <<, Reason : Signed Left Shift: Right operand is negative or is greater than or equal to the width of the promoted left operand, BINARY OPERATION: left (int64): 0 right (int64): 65 

</home/regehr/z/php-trunk-201009022030/Zend/zend_operators.c, (1194:2)> : Op: >>, Reason : Signed Right Shift: Right operand is negative or is greater than or equal to the width of the promoted left operand, BINARY OPERATION: left (int64): 0 right (int64): 65 

</home/regehr/z/php-trunk-201009022030/Zend/zend_operators.c, (766:31)> : Op: +, Reason : Signed Addition Overflow, BINARY OPERATION: left (int64): 9223372036854775807 right (int64): 1 

</home/regehr/z/php-trunk-201009022030/Zend/zend_operators.c, (828:31)> : Op: -, Reason : Signed Subtraction Overflow, BINARY OPERATION: left (int64): -9223372036854775808 right (int64): 1 

</home/regehr/z/php-trunk-201009022030/Zend/zend_operators.c, (877:5)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int64): 9223372036854775807 right (int64): 7 

</home/regehr/z/php-trunk-201009022030/ext/date/lib/parse_tz.c, (133:35)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int32): 255 right (int32): 16777216 

</home/regehr/z/php-trunk-201009022030/ext/standard/math.c, (616:5)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int64): 2147483647 right (int64): 4611686014132420609 

</home/regehr/z/php-trunk-201009022030/ext/standard/math.c, (620:5)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int64): 110075314176 right (int64): 110075314176
 [2011-06-12 02:56 UTC] cataphract@php.net
Automatic comment from SVN on behalf of cataphract
Revision: http://svn.php.net/viewvc/?view=revision&amp;revision=312074
Log: - Reverted r301991, which is a (partial) fix to bug #52550, addressing an
  overflow in a signed subtraction. This fixes the overflow without
  changing the algorithm.
 [2012-06-21 04:30 UTC] regehr at cs dot utah dot edu
Updated results from today's PHP.

ARITHMETIC UNDEFINED at </home/regehr/tmp/php-src/ext/date/lib/parse_tz.c, 
(135:35)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: 
left (int32): 255 right (int32): 16777216 

ARITHMETIC UNDEFINED at </home/regehr/tmp/php-src/ext/standard/math.c, (148:24)> 
: Op: -, Reason : Signed Subtraction Overflow, BINARY OPERATION: left (int32): 
14 right (int32): -2147483648 

ARITHMETIC UNDEFINED at </home/regehr/tmp/php-src/Zend/zend_hash.h, (350:2)> : 
Op: -, Reason : Signed Subtraction Overflow, UNARY OPERATION: left (int64): 0 
right (int64): -9223372036854775808 

ARITHMETIC UNDEFINED at </home/regehr/tmp/php-src/Zend/zend_operators.c, 
(1178:2)> : Op: <<, Reason : Signed Left Shift: Right operand is negative or is 
greater than or equal to the width of the promoted left operand, BINARY 
OPERATION: left (int64): 0 right (int64): 65 

ARITHMETIC UNDEFINED at </home/regehr/tmp/php-src/Zend/zend_operators.c, 
(1178:2)> : Op: <<, Reason : Signed Left Shift: Right operand is negative or is 
greater than or equal to the width of the promoted left operand, BINARY 
OPERATION: left (int64): 9223372036854775807 right (int64): -1 

ARITHMETIC UNDEFINED at </home/regehr/tmp/php-src/Zend/zend_operators.c, 
(1191:2)> : Op: >>, Reason : Signed Right Shift: Right operand is negative or is 
greater than or equal to the width of the promoted left operand, BINARY 
OPERATION: left (int64): 0 right (int64): 65 

ARITHMETIC UNDEFINED at </home/regehr/tmp/php-src/Zend/zend_operators.c, 
(1191:2)> : Op: >>, Reason : Signed Right Shift: Right operand is negative or is 
greater than or equal to the width of the promoted left operand, BINARY 
OPERATION: left (int64): 9223372036854775807 right (int64): -1
 [2012-06-21 04:35 UTC] regehr at cs dot utah dot edu
Also, our integer overflow checking tool can now be grabbed here:

http://embed.cs.utah.edu/ioc/
 [2013-12-05 19:49 UTC] mike@php.net
-Status: Analyzed +Status: Feedback -PHP Version: trunk-SVN-2010-08-06 (snap) +PHP Version: master
 [2013-12-05 19:49 UTC] mike@php.net
Any chance on getting an updated report or some automatic report?
 [2013-12-05 19:55 UTC] regehr at cs dot utah dot edu
Sure I'll do this tonight.
 [2013-12-06 17:50 UTC] regehr at cs dot utah dot edu
See below.  I got this by using "clang -fsanitize=undefined" to compile today's PHP from git, then running "make test".  These kinds of problems are generally pretty easy to debug by putting an assertion in front of each offending line of code.

Zend/zend_execute_API.c:146:46: runtime error: index -1 out of bounds for type 'HashTable *[32]'

Zend/zend_execute_API.c:146:46: runtime error: index -1 out of bounds for type 'HashTable *[32]'

Zend/zend_operators.c:1287:2: runtime error: shift exponent 65 is too large for 64-bit type 'long'

Zend/zend_operators.c:1307:2: runtime error: shift exponent -1 is negative

Zend/zend_operators.c:1307:2: runtime error: shift exponent 65 is too large for 64-bit type 'long'

Zend/zend_operators.h:108: runtime error: value nan is outside the range of representable values of type 'long'

ext/date/lib/parse_tz.c:135:35: runtime error: signed integer overflow: 255 * 16777216 cannot be represented in type 'int'

ext/phar/zip.c:150:34: runtime error: left shift of negative value -11

ext/sqlite3/libsqlite/sqlite3.c:57012:22: runtime error: member access within null pointer of type 'Mem' (aka 'struct Mem')

ext/standard/crypt_freesec.c:632:15: runtime error: left shift of negative value -61

ext/standard/math.c:148:24: runtime error: signed integer overflow: 14 - -2147483648 cannot be represented in type 'int'

ext/standard/math.c:41: runtime error: value -inf is outside the range of representable values of type 'int'

ext/standard/string.c:1671: runtime error: value 1.01235e+11 is outside the range of representable values of type 'int'

ext/standard/string.c:1671: runtime error: value 1.05e+11 is outside the range of representable values of type 'int'

ext/standard/url_scanner_ex.re:414:57: runtime error: member access within null pointer of type 'url_adapt_state_ex_t'
 
PHP Copyright © 2001-2014 The PHP Group
All rights reserved.
Last updated: Mon Apr 21 12:02:07 2014 UTC