homepage

If a PyTokenizer_FromString() is called with an empty string, the 
tokenizer's line_start member never gets initialized. Later, it is 
compared with the token pointer 'a' in parsetok.c:193 and that behavior 
can result in undefined behavior.
Found using Rational Purify for windows.
A patch is provided.

This patch was applied in rev. 65539, but then reverted; it turns out to 
break Lib/test/test_parser.py. The exception is:
 raise TestFailed(err)
test.test_support.TestFailed: Traceback (most recent call last):
 File "Lib/test/test_parser.py", line 222, in test_position
 terminals)
AssertionError: [(1, 'def', 1, 0), (1, 'f', 1, 4), (7, '(', 1, 5), (1,
'x', 1, 6), (8, ')', 1, 7), (11, ':', 1, 8), (4, '', 1, 9), (5, '', 2,
-1), (1, 'return', 2, 4), (1, 'x', 2, 11), (14, '+', 2, 13), (2, '1', 2,
15), (4, '', 2, 16), (6, '', 2, -1), (4, '', 2, -1), (0, '', 2, -1)] != 
[(1, 'def', 1, 0), (1, 'f', 1, 7033504), (7, '(', 1, 7033505), (1, 'x',
1, 7033506), (8, ')', 1, 7033507), (11, ':', 1, 7033508), (4, '', 1,
7033509), (5, '', 2, -1), (1, 'return', 2, 7033514), (1, 'x', 2,
7033521), (14, '+', 2, 7033523), (2, '1', 2, 7033525), (4, '', 2,
7033526), (6, '', 2, 0), (4, '', 2, 0), (0, '', 2, 0)]
In the resulting output, the columns are incorrect large values
(7033504, 7033505) or they're 0 where -1 is expected.
I took a look into why this happened, but made no progress. Removing
the 'easy' keyword. :)

Kristján, you suggested this patch to be considered for 2.5.3.
It seems the patch is incorrect. Can you provide a correct one?

Now that the 'easy' keyword is absent, I'm afraid this is out of my 
depth.
I'll run purify again and try to find the exact repro case.

Ok, un-targetting it from 2.5.3 for now.

According to issue 1562308, "exec ''" is enough to reproduce this.

Confirmed in trunk:
~/trunk-py$ ./configure --with-pydebug --without-pymalloc && make
[...]
~/trunk-py$ valgrind --suppressions=Misc/valgrind-python.supp ./python
==29730== Memcheck, a memory error detector.
[...]
Python 2.7a0 (trunk:72608M, May 16 2009, 17:31:09)
[GCC 4.2.4 (Ubuntu 4.2.4-1ubuntu3)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> exec ""
==29730== Conditional jump or move depends on uninitialised value(s)
==29730== at 0x805BF14: parsetok (parsetok.c:193)
==29730== by 0x805BB96: PyParser_ParseStringFlagsFilenameEx
(parsetok.c:66)
==29730== by 0x812A0D3: PyParser_ASTFromString (pythonrun.c:1434)
==29730== by 0x8129B43: PyRun_StringFlags (pythonrun.c:1299)
==29730== by 0x8101D37: exec_statement (ceval.c:4631)
[...]
[40389 refs]
>>>
[exit]
==29730==
==29730== Conditional jump or move depends on uninitialised value(s)
==29730== at 0x805BF14: parsetok (parsetok.c:193)
==29730== by 0x805BCF0: PyParser_ParseFileFlagsEx (parsetok.c:106)
==29730== by 0x812A214: PyParser_ASTFromFile (pythonrun.c:1462)
==29730== by 0x812829C: PyRun_InteractiveOneFlags (pythonrun.c:823)
[...]

I think this was fixed with checkins r76689 and r76230, made by Benjamin. Since we are using "exec ''" as the reproduction case, the token state is setup in 'PyTokenizer_FromString', which causes 'tok->inp == ""'. The code before these checkins (see attached revert patch) caused the following else branch in 'tok_nextc' to be taken:
 char *end = strchr(tok->inp, '\n');
 if (end != NULL)
 end++;
 else {
 end = strchr(tok->inp, '0円');
 if (end == tok->inp) {
 tok->done = E_EOF;
	 return EOF;
 }
 }
 if (tok->start == NULL)
 tok->buf = tok->cur;
 tok->line_start = tok->cur;
 tok->lineno++;
 tok->inp = end;
 return Py_CHARMASK(*tok->cur++);
because under these circumstances 'tok->inp == ""'. Thus 'tok->line_start' is not assigned. This trickled back out to 'parsetok:159' followed by 'parsetok:187' where 'tok->line_start' gets read unitialized.
After r76689 and r76230 the call to 'translate_newlines' was added in 
'decode_str' which is called from 'PyTokenizer_FromString' when the token state is created. The 'translate_newlines' call adds a newline to the end of the input buffer which ends up causing 'tok->input == "\n"'. Thus when 'tok_nextc' is called the initial if branch is taken instead of the else and 'tok->line_start' is initialized properly.
I also verified the current trunk with valgrind, which now shows no issue with this particular scenario:
euclid:trunk minge$ valgrind ./python.exe -c "exec ''"
==77940== Memcheck, a memory error detector
==77940== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==77940== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==77940== Command: ./python.exe -c exec\ ''
==77940== 
--77940-- ./python.exe:
--77940-- dSYM directory has wrong UUID; consider using --dsymutil=yes
==77940== Conditional jump or move depends on uninitialised value(s)
==77940== at 0x29D99D: __setenv (in /usr/lib/libSystem.B.dylib)
==77940== by 0x2E9354: putenv$UNIX2003 (in /usr/lib/libSystem.B.dylib)
==77940== by 0x165217: posix_putenv (in ./python.exe)
==77940== by 0x6E422: PyCFunction_Call (in ./python.exe)
==77940== by 0x10E971: call_function (in ./python.exe)
==77940== by 0x1095FE: PyEval_EvalFrameEx (in ./python.exe)
==77940== by 0x10EE3B: fast_function (in ./python.exe)
==77940== by 0x10EB47: call_function (in ./python.exe)
==77940== by 0x1095FE: PyEval_EvalFrameEx (in ./python.exe)
==77940== by 0x10C073: PyEval_EvalCodeEx (in ./python.exe)
==77940== by 0x10EF3C: fast_function (in ./python.exe)
==77940== by 0x10EB47: call_function (in ./python.exe)
==77940== 
[15652 refs]
==77940== 
==77940== HEAP SUMMARY:
==77940== in use at exit: 590,354 bytes in 4,795 blocks
==77940== total heap usage: 34,635 allocs, 29,840 frees, 6,689,168 bytes allocated
==77940== 
==77940== LEAK SUMMARY:
==77940== definitely lost: 0 bytes in 0 blocks
==77940== indirectly lost: 0 bytes in 0 blocks
==77940== possibly lost: 451,997 bytes in 4,461 blocks
==77940== still reachable: 137,793 bytes in 321 blocks
==77940== suppressed: 564 bytes in 13 blocks
==77940== Rerun with --leak-check=full to see details of leaked memory
==77940== 
==77940== For counts of detected and suppressed errors, rerun with: -v
==77940== Use --track-origins=yes to see where uninitialised values come from
==77940== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Excellent!

I can still reproduce it in py3k just by hitting Ctrl-D in the interactive
interpreter:
$ valgrind --db-attach=yes --suppressions=Misc/valgrind-python.supp ./python 
==16724== Memcheck, a memory error detector
==16724== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==16724== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==16724== Command: ./python
==16724== 
Python 3.2a3+ (py3k:85735M, Oct 20 2010, 14:19:24) 
[GCC 4.2.4 (Ubuntu 4.2.4-3ubuntu4)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 
==16724== Conditional jump or move depends on uninitialised value(s)
==16724== at 0x4F4DB7: parsetok (parsetok.c:198)
==16724== by 0x4F4B03: PyParser_ParseFileFlagsEx (parsetok.c:100)
==16724== by 0x49C8FB: PyParser_ASTFromFile (pythonrun.c:1884)
==16724== by 0x49AAC6: PyRun_InteractiveOneFlags (pythonrun.c:1124)
==16724== by 0x49A7B8: PyRun_InteractiveLoopFlags (pythonrun.c:1035)
==16724== by 0x49A677: PyRun_AnyFileExFlags (pythonrun.c:1004)
==16724== by 0x4B1EDE: run_file (main.c:296)
==16724== by 0x4B293E: Py_Main (main.c:681)
==16724== by 0x417D6B: main (python.c:51)
==16724=わ=わ 
=わ=わ16724=わ=わ 
=わ=わ16724== ---- Attach to debugger ? --- [Return/N/n/Y/y/C/c] ---- y
==16724== starting debugger with cmd: /usr/bin/gdb -nw /proc/16725/fd/1014 16725
GNU gdb 6.8-debian
Copyright (C) 2008 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu"...
Attaching to program: /proc/16725/fd/1014, process 16725
0x00000000004f4db7 in parsetok (tok=0x6c705d0, g=0x80bac0, start=256, err_ret=0x7fefffee0, flags=0x7feffff1c) at Parser/parsetok.c:198
198 if (a >= tok->line_start)
(gdb)

I don't have a working valgrind or purify, but I was able to reproduce the problem using a poor man's solution of adding
 assert(0xcbcbcbcbcbcbcbcb != tok->line_start);
before
 if (a >= tok->line_start)
 
With that assert the debug build indeed crashes once I hit Ctrl-D. Attached patch fixes that. 
I have also added tok->line_start in a few tok constructors for which I don't have a test case demonstrating access to uninitialized value, but it seems to be good defensive programming.

George,
This is not really important enough to get into the 3.2 release, but uninitialized variable bugs tend to be nasty when they bite you, so I'll ask your opinion before bumping the version.

No need to bump the version, it can go into 3.2.1. But seeing the history of this case, I don't want to play around here before 3.2 final.

On Fri, Feb 4, 2011 at 11:35 AM, Georg Brandl <report@bugs.python.org> wrote:
>.. But seeing the history of this case, I don't want to play around here before 3.2 final.
Here is my understanding of the history of this case: tmp1.patch was
applied in r65539 and reverted in r65543 with the log entry saying:
------------------------------------------------------------------------
r65543 | andrew.kuchling | 2008年08月04日 22:05:23 -0400 (2008年8月04日) | 1 line
#3367: revert rev. 65539: this change causes test_parser to fail
------------------------------------------------------------------------
Revision 65539 has never been applied to py3k, but it would be
equivalent to the following diff:
Index: Parser/tokenizer.c
===================================================================
--- Parser/tokenizer.c	(revision 88320)
+++ Parser/tokenizer.c	(working copy)
@@ -1289,7 +1289,7 @@
 register int c;
 int blankline, nonascii;
- *p_start = *p_end = NULL;
+ tok->line_start = *p_start = *p_end = NULL;
 nextline:
 tok->start = NULL;
 blankline = 0;
Applying the above diff now makes test_parser crash on a debug and
fail on a regular build. The problem with initializing
tok->line_start to NULL is that doing so trades one undefined behavior
for another: pointer comparison such as a >= tok->line_start is only
defined if both pointers point to the same buffer. Ordering between
NULL and non-NULL pointers is undefined. My patch does not have this
issue because it initializes tok->line_start to tok->buf.

bump, what is the status of this? Was it fixed?

It isn't fixed. Also, there's now an additional invalid read in
sys_update_path():
$ valgrind --db-attach=yes --suppressions=Misc/valgrind-python.supp ./python 
==20258== Memcheck, a memory error detector
==20258== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==20258== Using Valgrind-3.6.1 and LibVEX; rerun with -h for copyright info
==20258== Command: ./python
==20258== 
Python 3.3.0a1+ (default:0554183066b5, Mar 20 2012, 10:47:41) 
[GCC 4.4.3] on linux
Type "help", "copyright", "credits" or "license" for more information.
==20258== Invalid read of size 8
==20258== at 0x4C9F6F: sys_update_path (sysmodule.c:1742)
==20258== by 0x4CA268: PySys_SetArgvEx (sysmodule.c:1830)
==20258== by 0x4CA28F: PySys_SetArgv (sysmodule.c:1836)
==20258== by 0x4D9930: Py_Main (main.c:647)
==20258== by 0x41AE1F: main (python.c:63)
==20258== Address 0x5a58048 is 0 bytes after a block of size 8 alloc'd
==20258== at 0x4C27878: malloc (vg_replace_malloc.c:236)
==20258== by 0x41DF90: PyMem_Malloc (object.c:1841)
==20258== by 0x41ACC4: main (python.c:25)
==20258=わ=わ 
=わ=わ20258=わ=わ 
=わ=わ20258== ---- Attach to debugger ? --- [Return/N/n/Y/y/C/c] ---- n
>>> 
==20258== Conditional jump or move depends on uninitialised value(s)
==20258== at 0x52B030: parsetok (parsetok.c:207)
==20258== by 0x52AD51: PyParser_ParseFileFlagsEx (parsetok.c:108)
==20258== by 0x4BFCDA: PyParser_ASTFromFile (pythonrun.c:1973)
==20258== by 0x4BDB5A: PyRun_InteractiveOneFlags (pythonrun.c:1196)
==20258== by 0x4BD83D: PyRun_InteractiveLoopFlags (pythonrun.c:1106)
==20258== by 0x4BD6E2: PyRun_AnyFileExFlags (pythonrun.c:1075)
==20258== by 0x4D9118: run_file (main.c:306)
==20258== by 0x4D9C0B: Py_Main (main.c:720)
==20258== by 0x41AE1F: main (python.c:63)
==20258==

Here is a patch for the sysmodule.c problem

Victor, could you check out the last patch here for sysmodule? I gather that you are familiar with it.

I'm unable to reproduce this error:
----------
$ valgrind --db-attach=yes --suppressions=Misc/valgrind-python.supp ./python 
Python 3.3.0a1+ (default:0554183066b5, Mar 20 2012, 10:47:41) 
...
==20258== Invalid read of size 8
==20258== at 0x4C9F6F: sys_update_path (sysmodule.c:1742)
==20258== by 0x4CA268: PySys_SetArgvEx (sysmodule.c:1830)
...
----------
My try:
----------
$ ./configure --with-pydebug --with-valgrind && make
(...)
$ valgrind --suppressions=Misc/valgrind-python.supp ./python 
==10692== Memcheck, a memory error detector
==10692== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==10692== Using Valgrind-3.6.1 and LibVEX; rerun with -h for copyright info
==10692== Command: ./python
==10692== 
Python 3.3.0a1+ (default:f8d01c8baf6a+, Mar 26 2012, 01:12:33) 
[GCC 4.6.2 20111027 (Red Hat 4.6.2-1)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 1+1
2
>>> 
==10692== 
==10692== HEAP SUMMARY:
==10692== in use at exit: 2,896,586 bytes in 14,491 blocks
==10692== total heap usage: 86,344 allocs, 71,853 frees, 12,370,023 bytes allocated
==10692== 
==10692== LEAK SUMMARY:
==10692== definitely lost: 0 bytes in 0 blocks
==10692== indirectly lost: 0 bytes in 0 blocks
==10692== possibly lost: 2,779,467 bytes in 14,287 blocks
==10692== still reachable: 117,119 bytes in 204 blocks
==10692== suppressed: 0 bytes in 0 blocks
==10692== Rerun with --leak-check=full to see details of leaked memory
==10692== 
==10692== For counts of detected and suppressed errors, rerun with: -v
==10692== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2)
----------
sysmodule.patch	looks to be useless: n is not used if argc <= 0.
At the revision 0554183066b5, sysmodule.c:1742 is the following line:
 if (argc > 0) {
but sysmodule.c:1830 is:
 if (av == NULL)
whereas it should be:
 sys_update_path(argc, argv);
Stephan: can you redo the Valgrind test on copy the exact line where the invalid read occurs (in sysmodule.c).

> Stephan: can you redo the Valgrind test on copy the exact line
> where the invalid read occurs (in sysmodule.c).
Oops: ... *and* copy the exact line ...

I don't quite understand what you're saying about line mismatch Victor.
Anyway, if you look at it, it is clear that:
1) sys_update_path() can be called with argc==0 (main.c line 647)
2) 1742 was always setting arg0 to argv[0] that is undefined and this access may cause a crash if 1) above is true
3) line 1812 assumes n to be equal to the length of arg0, but depending on conditional compilation, it may not get set at all, and in any case, in line line 1805 it gets set only if p is not NULL.
I think it is simply safer to make the proper assumptions.

It's the line argv0 = argv[0] in sys_update_path(). The copies of
argv made in python.c aren't NULL terminated. Kristján's patch
worked around that (and fixes the problem), but I'd prefer to
make a full copy of argv in python.c.
Could one of you look at the patch? I didn't check if there are other
problems in sys_update_path() that Kristján's patch addressed.

> 3) line 1812 assumes n to be equal to the length of arg0, but depending > on conditional compilation, it may not get set at all, and in any > case in line line 1805 it gets set only if p is not NULL.
n is initialized to 0 when its declared. I think it's deliberate
to call a = PyUnicode_FromWideChar(argv0, 0) in order to insert
an empty path.

Kristján's patch is wrong: n should be set to 0 even if argc > 0. The
patch is also useless with argv-alloc.diff.
@Stefan: Your patch is correct and solves the issue. You can commit it
to 2.7, 3.2 and 3.3.

I'm sure you didn't intend to use words such as "wrong" and "useless" Victor. Perhaps n must be 0 even for argc>0, but I did that as an afterthought. Which is the reason I asked you to take a look rather than committing this right away.
Please allow me to point out that relying on an extra NULL pointer at the end of argv is dangerous. C makes no such guarantees with main() and you are coupling implementation details betweeen layers using this. The "correct" thing to do is to simply not dereference argv at argc or beyond.

I only have the C99 standard. It says [5.1.2.2.1]:
 - argv[argc] shall be a NULL pointer.
Is this different in C89?
Also, my patch terminates the *copies* of argv, not argv itself.

K&R page 115 also says: The standard requires that argv[argc] be a NULL pointer.
So it must be in C89 as well.

> I'm sure you didn't intend to use words such as "wrong" and "useless" Victor. Perhaps n must be 0 even for argc>0, but I did that as an afterthought.
If n is initialized as wcslen(argv[0]), test_cmd_line_script fails.

New changeset c0900fd6e4b3 by Stefan Krah in branch '3.2':
Issue #3367: NULL-terminate argv[] copies to prevent an invalid access
http://hg.python.org/cpython/rev/c0900fd6e4b3
New changeset 1ab8fa2277d9 by Stefan Krah in branch 'default':
Issue #3367: Merge fix from 3.2.
http://hg.python.org/cpython/rev/1ab8fa2277d9 

You are right, Stefan, argv[argc] is defined to be NULL by the standard. Jolly good.

Should this be closed?

I think the original issue in parsetok.c is still present. The
fix that was committed was for sys_update_path().

I can still reproduce the parsetok.c problem on the 'default' branch using the CTRL+D method Stefan described.

I see a crash with valgring even without hitting Ctrl-D.
$ valgrind --db-attach=yes --suppressions=Misc/valgrind-python.supp ./python
==26172== Memcheck, a memory error detector
==26172== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==26172== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==26172== Command: ./python
==26172== 
==26172== Conditional jump or move depends on uninitialised value(s)
==26172== at 0x414E578: __wcslen_sse2 (wcslen-sse2.S:95)
==26172== by 0x807788D: calculate_path (getpath.c:647)
==26172== by 0x807803B: Py_GetProgramFullPath (getpath.c:875)
==26172== by 0x8070C5E: _PySys_Init (sysmodule.c:1628)
==26172== by 0x8060680: _Py_InitializeEx_Private (pythonrun.c:400)
==26172== by 0x8060939: Py_InitializeEx (pythonrun.c:467)
==26172== by 0x806094D: Py_Initialize (pythonrun.c:473)
==26172== by 0x807956A: Py_Main (main.c:683)
==26172== by 0x805CFE3: main (python.c:69)
==26172=わ=わ 
=わ=わ26172=わ=わ 
=わ=わ26172== ---- Attach to debugger ? --- [Return/N/n/Y/y/C/c] ----

Serhiy, probably a false positive:
https://bugs.kde.org/show_bug.cgi?id=298281 

The fix proposed by Alexander in issue3367.diff has never been applied. How would I go about reproducing the original issue on Windows?

I close the issue, it has been fixed.
I'm no longer able to reproduce the initial issue:
$ ./configure --with-pydebug --with-valgrind
$ make clean
$ make
$ valgrind --suppressions=Misc/valgrind-python.supp ./python 
==2670== Memcheck, a memory error detector
==2670== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2670== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==2670== Command: ./python
==2670== 
Python 3.9.0a0 (heads/master:91528f40c3, Oct 23 2019, 01:36:01) 
[GCC 9.2.1 20190827 (Red Hat 9.2.1-1)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 
>>> exec("")
>>> ^D # CTRL+D
==2670== 
==2670== HEAP SUMMARY:
==2670== in use at exit: 1,530,371 bytes in 26,288 blocks
==2670== total heap usage: 49,485 allocs, 23,197 frees, 10,318,174 bytes allocated
==2670== 
==2670== LEAK SUMMARY:
==2670== definitely lost: 0 bytes in 0 blocks
==2670== indirectly lost: 0 bytes in 0 blocks
==2670== possibly lost: 872,665 bytes in 5,936 blocks
==2670== still reachable: 657,706 bytes in 20,352 blocks
==2670== suppressed: 0 bytes in 0 blocks
==2670== Rerun with --leak-check=full to see details of leaked memory
==2670== 
==2670== For lists of detected and suppressed errors, rerun with: -s
==2670== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Moreover, Python initialization code has been reworked in the PEP 587 implementation to ensure that sys.argv is never empty. If it's called with an empty list, [""] is used instead.