Read past end of buffer in xt_scan_branch_single() and similar functions

[Kristian Nielsen]

I found this from a Valgrind warning:

==3619== Invalid read of size 4
==3619== at 0x9FF73F: xt_get_res_record_ref(unsigned char*, XTIdxResult*) (index_xt.h:454)
==3619== by 0x9F4E90: xt_scan_branch_single(XTTable*, XTIndex*, XTIdxBranch*, XTIdxKeyValue*, XTIdxResult*) (index_xt.cc:501)
==3619== by 0x9FEE6B: xt_idx_insert(XTOpenTable*, XTIndex*, unsigned, unsigned, unsigned char*, unsigned char*, int) (index_xt.cc:1877)
==3619== by 0xA1924B: xt_tab_new_record(XTOpenTable*, unsigned char*) (table_xt.cc:4392)
==3619== by 0x9EECD9: ha_pbxt::write_row(unsigned char*) (ha_pbxt.cc:2645)
==3619== by 0x7C4CC1: handler::ha_write_row(unsigned char*) (handler.cc:4642)
==3619== by 0x7E3087: copy_data_between_tables(st_table*, st_table*, List<Create_field>&, bool, unsigned, st_order*, unsigned long long*, unsigned long long*, enum_enable_or_disable, bool) (sql_table.cc:7779)
==3619== by 0x7F05E2: mysql_alter_table(THD*, char*, char*, st_ha_create_information*, TABLE_LIST*, Alter_info*, unsigned, st_order*, bool) (sql_table.cc:7221)
==3619== by 0x68BE71: mysql_execute_command(THD*) (sql_parse.cc:2959)
==3619== by 0x692F7F: mysql_parse(THD*, char const*, unsigned, char const**) (sql_parse.cc:6034)
==3619== by 0x693D91: dispatch_command(enum_server_command, THD*, char*, unsigned) (sql_parse.cc:1247)
==3619== by 0x69528F: do_command(THD*) (sql_parse.cc:886)
==3619== by 0x68066C: handle_one_connection (sql_connect.cc:1132)
==3619== by 0x50463F6: start_thread (pthread_create.c:297)
==3619== by 0x6026B4C: clone (in /usr/lib/debug/libc-2.7.so)
==3619== Address 0xcf98030 is 0 bytes after a block of size 33,701,888 alloc'd
==3619== at 0x4C22FAB: malloc (vg_replace_malloc.c:207)
==3619== by 0x9FF9A2: xt_malloc(XTThread*, unsigned long) (memory_xt.cc:101)
==3619== by 0xA439F2: xt_ind_init(XTThread*, unsigned long) (cache_xt.cc:632)
==3619== by 0x9EBDBC: pbxt_call_init(XTThread*) (ha_pbxt.cc:974)
==3619== by 0x9EC109: pbxt_init(void*) (ha_pbxt.cc:1194)
==3619== by 0x7C8E01: ha_initialize_handlerton(st_plugin_int*) (handler.cc:429)
==3619== by 0x88ADD6: plugin_initialize(st_plugin_int*) (sql_plugin.cc:1033)
==3619== by 0x88E979: plugin_init(int*, char**, int) (sql_plugin.cc:1258)
==3619== by 0x67A21C: init_server_components() (mysqld.cc:4069)
==3619== by 0x67ACF5: main (mysqld.cc:4541)

This is from test case pbxt.multi_update (which takes ~1h to run under
Valgrind :-/).

I think this is a real bug, although possibly minor. Not knowing the code in
detail, I need help in determining the proper fix.

xt_scan_branch_single() basically does a binary search on a block of
memory. There is a while () loop, which exits with i pointing at the position
being searched for.

Note that (at least from a quick look at the code), if the value being
searched for is bigger than all values in the buffer, then the loop will exit
with i pointing past the last element.

After the loop, the code does this:

        bitem = base + i * full_item_size;
        xt_get_res_record_ref(bitem + ind->mi_key_size, result);

From the Valgrind trace, it seems to me the problem is that in this case i
points past the last element as described above, so the
xt_get_res_record_ref() reads 8 bytes past the end of the buffer.

This should probably be fixed (in theory this could cause the process to
segfault if memory allocation is really unfortunate and these 8 bytes happen
to be unmapped). Maybe just something like

   if (result.sr_found)
        xt_get_res_record_ref(bitem + ind->mi_key_size, result);

in case the values read are only used in the "found" case?

Hope you can sort out the rest from this explanation.

[Kristian Nielsen (knielsen)]

Here is a similar Valgrind error for xt_scan_branch_fix(), which can be
obtained by running test case pbxt.type_enum (much easier, takes only about 1
minute under Valgrind):

==7276== Invalid read of size 4
==7276== at 0x9FF73F: xt_get_res_record_ref(unsigned char*, XTIdxResult*) (index_xt.h:454)
==7276== by 0x9F878E: xt_scan_branch_fix(XTTable*, XTIndex*, XTIdxBranch*, XTIdxKeyValue*, XTIdxResult*) (index_xt.cc:622)
==7276== by 0x9FEE6B: xt_idx_insert(XTOpenTable*, XTIndex*, unsigned, unsigned, unsigned char*, unsigned char*, int) (index_xt.cc:1877)
==7276== by 0xA1924B: xt_tab_new_record(XTOpenTable*, unsigned char*) (table_xt.cc:4392)
==7276== by 0x9EECD9: ha_pbxt::write_row(unsigned char*) (ha_pbxt.cc:2645)
==7276== by 0x7C4CC1: handler::ha_write_row(unsigned char*) (handler.cc:4642)
==7276== by 0x728939: write_record(THD*, st_table*, st_copy_info*) (sql_insert.cc:1632)
==7276== by 0x72D504: mysql_insert(THD*, TABLE_LIST*, List<Item>&, List<List<Item> >&, List<Item>&, List<Item>&, enum_duplicates, bool) (sql_insert.cc:860)
==7276== by 0x68CDF5: mysql_execute_command(THD*) (sql_parse.cc:3244)
==7276== by 0x692F7F: mysql_parse(THD*, char const*, unsigned, char const**) (sql_parse.cc:6034)
==7276== by 0x693D91: dispatch_command(enum_server_command, THD*, char*, unsigned) (sql_parse.cc:1247)
==7276== by 0x69528F: do_command(THD*) (sql_parse.cc:886)
==7276== by 0x68066C: handle_one_connection (sql_connect.cc:1132)
==7276== by 0x50463F6: start_thread (pthread_create.c:297)
==7276== by 0x6026B4C: clone (in /usr/lib/debug/libc-2.7.so)
==7276== Address 0xcf9802e is 33,701,886 bytes inside a block of size 33,701,888 alloc'd
==7276== at 0x4C22FAB: malloc (vg_replace_malloc.c:207)
==7276== by 0x9FF9A2: xt_malloc(XTThread*, unsigned long) (memory_xt.cc:101)
==7276== by 0xA439F2: xt_ind_init(XTThread*, unsigned long) (cache_xt.cc:632)
==7276== by 0x9EBDBC: pbxt_call_init(XTThread*) (ha_pbxt.cc:974)
==7276== by 0x9EC109: pbxt_init(void*) (ha_pbxt.cc:1194)
==7276== by 0x7C8E01: ha_initialize_handlerton(st_plugin_int*) (handler.cc:429)
==7276== by 0x88ADD6: plugin_initialize(st_plugin_int*) (sql_plugin.cc:1033)
==7276== by 0x88E979: plugin_init(int*, char**, int) (sql_plugin.cc:1258)
==7276== by 0x67A21C: init_server_components() (mysqld.cc:4069)
==7276== by 0x67ACF5: main (mysqld.cc:4541)

Seems like exactly the same issue as xt_scan_branch_single(). Probably all the
xt_scan_branch_* functions needs to be checked for this issue.

[Kristian Nielsen (knielsen)]

Actually, there is an even simpler case where i points after the array:

 else if (search_flags & XT_SEARCH_AFTER_LAST_FLAG)
  i = (result->sr_item.i_total_size - node_ref_size) / full_item_size;

[Paul McCullagh (paul-mccullagh)]

Yes, you are right. This code is accessing uninitialized data at the
end of the item list.

I think the fix should maybe look something like this:

 register u_int i, total;

...
total = result->sr_item.i_total_size - node_ref_size) / full_item_size;

...
if (i < total)
 xt_get_res_record_ref(bitem + ind->mi_key_size, result);

total can then be used where "result->sr_item.i_total_size -
node_ref_size) / full_item_size" is used.

On Mar 16, 2010, at 11:57 AM, Kristian Nielsen wrote:

> Actually, there is an even simpler case where i points after the
> array:
>
> else if (search_flags & XT_SEARCH_AFTER_LAST_FLAG)
> i = (result->sr_item.i_total_size - node_ref_size) / full_item_size;
>
> --
> Read past end of buffer in xt_scan_branch_single() and similar
> functions
> https://bugs.launchpad.net/bugs/539480
> You received this bug notification because you are subscribed to PBXT.
>
> Status in Maria: New
> Status in PrimeBase XT: New
>
> Bug description:
> I found this from a Valgrind warning:
>
> ==3619== Invalid read of size 4
> ==3619== at 0x9FF73F: xt_get_res_record_ref(unsigned char*,
> XTIdxResult*) (index_xt.h:454)
> ==3619== by 0x9F4E90: xt_scan_branch_single(XTTable*, XTIndex*,
> XTIdxBranch*, XTIdxKeyValue*, XTIdxResult*) (index_xt.cc:501)
> ==3619== by 0x9FEE6B: xt_idx_insert(XTOpenTable*, XTIndex*,
> unsigned, unsigned, unsigned char*, unsigned char*, int)
> (index_xt.cc:1877)
> ==3619== by 0xA1924B: xt_tab_new_record(XTOpenTable*, unsigned
> char*) (table_xt.cc:4392)
> ==3619== by 0x9EECD9: ha_pbxt::write_row(unsigned char*)
> (ha_pbxt.cc:2645)
> ==3619== by 0x7C4CC1: handler::ha_write_row(unsigned char*)
> (handler.cc:4642)
> ==3619== by 0x7E3087: copy_data_between_tables(st_table*,
> st_table*, List<Create_field>&, bool, unsigned, st_order*, unsigned
> long long*, unsigned long long*, enum_enable_or_disable, bool)
> (sql_table.cc:7779)
> ==3619== by 0x7F05E2: mysql_alter_table(THD*, char*, char*,
> st_ha_create_information*, TABLE_LIST*, Alter_info*, unsigned,
> st_order*, bool) (sql_table.cc:7221)
> ==3619== by 0x68BE71: mysql_execute_command(THD*) (sql_parse.cc:
> 2959)
> ==3619== by 0x692F7F: mysql_parse(THD*, char const*, unsigned,
> char const**) (sql_parse.cc:6034)
> ==3619== by 0x693D91: dispatch_command(enum_server_command, THD*,
> char*, unsigned) (sql_parse.cc:1247)
> ==3619== by 0x69528F: do_command(THD*) (sql_parse.cc:886)
> ==3619== by 0x68066C: handle_one_connection (sql_connect.cc:1132)
> ==3619== by 0x50463F6: start_thread (pthread_create.c:297)
> ==3619== by 0x6026B4C: clone (in /usr/lib/debug/libc-2.7.so)
> ==3619== Address 0xcf98030 is 0 bytes after a block of size
> 33,701,888 alloc'd
> ==3619== at 0x4C22FAB: malloc (vg_replace_malloc.c:207)
> ==3619== by 0x9FF9A2: xt_malloc(XTThread*, unsigned long)
> (memory_xt.cc:101)
> ==3619== by 0xA439F2: xt_ind_init(XTThread*, unsigned long)
> (cache_xt.cc:632)
> ==3619== by 0x9EBDBC: pbxt_call_init(XTThread*) (ha_pbxt.cc:974)
> ==3619== by 0x9EC109: pbxt_init(void*) (ha_pbxt.cc:1194)
> ==3619== by 0x7C8E01: ha_initialize_handlerton(st_plugin_int*)
> (handler...

[Paul McCullagh (paul-mccullagh)]

Actually, I think the solution here is to change:

#define IDX_GET_NODE_REF(t, x, o) XT_GET_NODE_REF(t, (x) - (o))

to:

#define IDX_GET_NODE_REF(t, x, o) ((o) ? XT_GET_NODE_REF(t, (x) - (o) : 0)

Because if the node reference size (o) is zero, then this particular index node is leaf. And leaves to not have any references to other nodes.