[BUG] Integer overflow in sort() function

From: MichaÅ WysoczaÅski
Date: Sat Oct 29 2016 - 10:11:19 EST

Hello,

There is possible integer overflow in kernel sort() function leading to page
fault. sort() function accepts number of items and item size as two 64-bit
arguments (size_t) but internal calculations are done using 32-bit integers:

void sort(void *base, size_t num, size_t size,
int (*cmp_func)(const void *, const void *),
void (*swap_func)(void *, void *, int size))
{
/* pre-scale counters for performance */
int i = (num/2 - 1) * size, n = num * size, c, r;

As these values are later used for iterations over buffer being sorted
and there is no checking for overflow some combinations of num
and size args will lead to page fault.
Here is sample code to reproduce this issue:

=============================
#include <linux/module.h>
#include <linux/vmalloc.h>
#include <linux/sort.h>

#define SORT_ITEMS_COUNT 160000000

struct sort_item {
uint64_t buf[2];
};

static int sort_test_cmp(const void *a,
const void *b)
{
const struct sort_item *p1 = a;
const struct sort_item *p2 = b;
return p1->buf[0] > p2->buf[0] ? 1 : -1;
}

static void sort_test(void)
{
struct sort_item *items;

items = vmalloc(sizeof(*items) * SORT_ITEMS_COUNT);
if (!items)
return;
sort(items, SORT_ITEMS_COUNT, sizeof(*items),
sort_test_cmp, NULL);
vfree(items);
}

static int __init sorttest_init_module(void)
{
sort_test();
return 0;
}
module_init(sorttest_init_module);

static void __exit sorttest_exit_module(void)
{
}
module_exit(sorttest_exit_module);

MODULE_LICENSE("GPL");
=============================

And kernel BUG report:

[ 1668.230986] BUG: unable to handle kernel paging request at ffffc8ffb8968ff0
[ 1668.240094] IP: [<ffffffffa077a008>] sort_test_cmp+0x8/0x1c [sorttest]
[ 1668.248565] PGD 0 [ 1668.250620]
[ 1668.253415] Oops: 0000 [#1] SMP
[ 1668.258019] Modules linked in: sorttest(OE+) xt_CHECKSUM
ipt_MASQUERADE nf_nat_masquerade_ipv4 tun nls_utf8 isofs loop
rpcsec_gss_krb5 nfsv4 dns_resolver nfs fscache ip6t_rpfilter
ip6t_REJECT nf_reject_ipv6 ipt_REJECT nf_reject_ipv4 xt_conntrack
ebtable_nat ebtable_broute bridge stp llc ebtable_filter ebtables
ip6table_nat nf_conntrack_ipv6 nf_defrag_ipv6 nf_nat_ipv6
ip6table_mangle ip6table_security ip6table_raw ip6table_filter
ip6_tables iptable_nat nf_conntrack_ipv4 nf_defrag_ipv4 nf_nat_ipv4
nf_nat nf_conntrack iptable_mangle iptable_security iptable_raw
iptable_filter dm_mirror dm_region_hash dm_log dm_mod sb_edac
edac_core x86_pkg_temp_thermal intel_powerclamp coretemp kvm_intel kvm
irqbypass crct10dif_pclmul crc32_pclmul ghash_clmulni_intel
aesni_intel iTCO_wdt lrw ipmi_devintf iTCO_vendor_support gf128mul
ipmi_ssif mei_me ioatdma glue_helper ablk_helper shpchp mei ipmi_si
i2c_i801 cryptd pcspkr ipmi_msghandler lpc_ich sg i2c_smbus wmi
mfd_core nfsd auth_rpcgss nfs_acl lockd grace sunrpc ip_tables ext4
jbd2 mbcache sd_mod mgag200 drm_kms_helper isci syscopyarea
sysfillrect sysimgblt fb_sys_fops ttm libsas igb drm ptp ahci libahci
scsi_transport_sas pps_core dca libata crc32c_intel i2c_algo_bit nvme
i2c_core nvme_core [last unloaded: sorttest]
[ 1668.394028] CPU: 23 PID: 6109 Comm: insmod Tainted: G OEL
4.9.0-rc2 #1
[ 1668.403491] Hardware name: Intel Corporation S2600CP/S2600CP, BIOS
SE5C600.86B.02.06.0002.101320150901 10/13/2015
[ 1668.416075] task: ffff88042a151600 task.stack: ffffc90004b2c000
[ 1668.423814] RIP: 0010:[<ffffffffa077a008>] [<ffffffffa077a008>]
sort_test_cmp+0x8/0x1c [sorttest]
[ 1668.434980] RSP: 0018:ffffc90004b2fc00 EFLAGS: 00010246
[ 1668.442059] RAX: 0000000000000000 RBX: 0000000098967ff0 RCX: 0000000000000010
[ 1668.451186] RDX: ffffffff98967ff0 RSI: ffffc8ffb8968ff0 RDI: ffffc9006c4b4ff0
[ 1668.460307] RBP: ffffc90004b2fc70 R08: 000000004c4b3ff0 R09: 8000000000000163
[ 1668.469439] R10: 0000000000000000 R11: 0000000000000000 R12: ffffc8ffb8968ff0
[ 1668.478564] R13: ffffc9006c4b4ff0 R14: ffffc90020001000 R15: 0000000000000010
[ 1668.487684] FS: 00007f93cadc0740(0000) GS:ffff88042edc0000(0000)
knlGS:0000000000000000
[ 1668.497876] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 1668.505440] CR2: ffffc8ffb8968ff0 CR3: 000000042a467000 CR4: 00000000000406e0
[ 1668.514563] Stack:
[ 1668.517955] ffffffff81363372 9896800006b02000 98967fe0ffffffe0
024002c22b110400
[ 1668.527424] ffffffff813632a0 ffffffff98967ff0 ffffffff98968000
000000104c4b3ff0
[ 1668.536888] ffffffffa077a000 ffffc90020001000 ffffffffa0064000
ffffc90004b2fe80
[ 1668.546353] Call Trace:
[ 1668.550246] [<ffffffff81363372>] ? sort+0xa2/0x240
[ 1668.556865] [<ffffffff813632a0>] ? u64_swap+0x20/0x20
[ 1668.563769] [<ffffffffa077a000>] ? 0xffffffffa077a000
[ 1668.570664] [<ffffffffa0064000>] ? 0xffffffffa0064000
[ 1668.577551] [<ffffffffa0064033>] sorttest_init_module+0x33/0x1000 [sorttest]
[ 1668.586677] [<ffffffff81002190>] do_one_initcall+0x50/0x190
[ 1668.594156] [<ffffffff811ffd4b>] ? kmem_cache_alloc_trace+0x14b/0x1b0
[ 1668.602605] [<ffffffff811980e7>] do_init_module+0x60/0x1f1
[ 1668.609985] [<ffffffff8111804b>] load_module+0x15ab/0x1aa0
[ 1668.617366] [<ffffffff811149e0>] ? __symbol_put+0x60/0x60
[ 1668.624647] [<ffffffff812f9d6d>] ? ima_post_read_file+0x3d/0x80
[ 1668.632511] [<ffffffff812d5beb>] ? security_kernel_post_read_file+0x6b/0x80
[ 1668.641544] [<ffffffff81118756>] SYSC_finit_module+0xa6/0xf0
[ 1668.649123] [<ffffffff811187be>] SyS_finit_module+0xe/0x10
[ 1668.656485] [<ffffffff81003a47>] do_syscall_64+0x67/0x180
[ 1668.663727] [<ffffffff816e786b>] entry_SYSCALL64_slow_path+0x25/0x25
[ 1668.672032] Code: <48> 39 06 55 48 89 e5 19 c0 83 e0 02 83 e8 01 5d
c3 0f 1f 00 55 48
[ 1668.682239] RIP [<ffffffffa077a008>] sort_test_cmp+0x8/0x1c [sorttest]
[ 1668.690753] RSP <ffffc90004b2fc00>
[ 1668.695760] CR2: ffffc8ffb8968ff0
[ 1668.704363] ---[ end trace ece3898e4521cd0c ]---
[ 1668.727879] Kernel panic - not syncing: Fatal exception
[ 1668.734844] Kernel Offset: disabled
[ 1668.753273] ---[ end Kernel panic - not syncing: Fatal exception
[ 1668.760811] ------------[ cut here ]------------

Linux kernel 4.9-rc2.


--
Michal Wysoczanski