seg fault pushing on either side of a VecDeque
Closed this issue · 4 comments
jesse99 commented
I've been seeing lots of bad behavior trying to use VecDeque. I've boiled it down to a relatively simple example which shows some of the bad behavior I was seeing and additionally seg faults.
This was with:
rustc 1.20.0 (f3d6973 2017-08-27)
binary: rustc
commit-hash: f3d6973
commit-date: 2017-08-27
host: x86_64-apple-darwin
release: 1.20.0
LLVM version: 4.0
and also rust 1.19
The output I expect to see is:
old packet = 00 88 01 02 03 04 05 06 01 02 03 04 05 06 01 02 03 04 05 06 00 37 03 80 45 14 00 14 00 15 00 17
pushing D9 58 FB A8
new packet = 00 88 01 02 03 04 05 06 01 02 03 04 05 06 01 02 03 04 05 06 00 37 03 80 45 14 00 14 00 15 00 17 D9 58 FB A8
The output I get is:
old packet = 00 88 01 02 03 04 05 06 01 02 03 04 05 06 01 02 03 04 05 06 00 37 03 80 45 14 00 14 00 15 00 17
pushing D9 58 FB A8
new packet = 00 88 01 02 03 04 05 06 01 02 03 04 05 06 01 02 03 04 05 06 00 37 03 80 45 14 00 14 00 15 00 17 00 58 FB A8
Segmentation fault: 11
Note that the fourth from the last byte should be D9.
Work around seems to be to use a large VecDeqeue capacity.
Here's the code:
use std::collections::VecDeque;
use std::fmt;
pub struct Packet
{
pub payload: VecDeque<u8>,
}
pub struct Header
{
pub data: Vec<u8>,
}
impl Packet
{
pub fn new() -> Self
{
let payload = VecDeque::with_capacity(32);
Packet{payload}
}
pub fn len(&self) -> usize
{
self.payload.len()
}
pub fn push_header(&mut self, header: &Header)
{
self.payload.reserve(header.data.len());
for b in header.data.iter().rev() {
self.payload.push_front(*b);
}
}
pub fn push_back_bytes(&mut self, data: &[u8])
{
self.payload.extend(data.iter());
}
}
impl fmt::Debug for Packet
{
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result
{
let mut bytes = String::with_capacity(3*self.len());
for i in 0..self.payload.len() {
bytes.push_str(&format!(" {:02X}", self.payload[i]));
}
write!(f, "{}", bytes)
}
}
impl Header
{
pub fn new() -> Self
{
let data = Vec::with_capacity(20);
Header{data}
}
pub fn with_capacity(capacity: usize) -> Self
{
let data = Vec::with_capacity(capacity);
Header{data}
}
pub fn push8(&mut self, data: u8)
{
self.data.push(data);
}
pub fn push16(&mut self, data: u16)
{
self.data.push((data >> 8) as u8);
self.data.push((data & 0xFF) as u8);
}
pub fn push32(&mut self, data: u32)
{
self.data.push((data >> 24) as u8);
self.data.push(((data >> 16) & 0xFF) as u8);
self.data.push(((data >> 8) & 0xFF) as u8);
self.data.push((data & 0xFF) as u8);
}
pub fn push_bytes(&mut self, data: &[u8])
{
self.data.extend(data);
}
}
fn push_ipv4(packet: &mut Packet)
{
let payload_len = packet.len();
let mut header = Header::with_capacity(20);
let b = 0x45; // version + IHL (we don't support options so length is fixed)
header.push8(b);
header.push8(20);
let hw = 20 + payload_len; // total length
header.push16(hw as u16);
header.push16(21); // identification
header.push16(23);
packet.push_header(&header);
}
fn push_mac(packet: &mut Packet)
{
let mut header = Header::with_capacity(30);
let hw = 0b1000_10_00; // frame control, see 9.2.4.1
header.push16(hw);
let addr = [1, 2, 3, 4, 5, 6];
for &b in addr.iter() { // address 1, see 9.3.2.1
header.push8(b);
}
for &b in addr.iter() { // address 2
header.push8(b);
}
for &b in addr.iter() {// address 3
header.push8(b);
}
header.push16(55);
let hw = 0b111_0_00_0_000; // QoS control, see 9.2.4.5.1
header.push16(hw);
packet.push_header(&header);
let fcs = [0xD9, 0x58, 0xFB, 0xA8];
println!("old packet = {:?}", packet);
println!("pushing {:X} {:X} {:X} {:X} ", fcs[0], fcs[1], fcs[2], fcs[3]);
packet.push_back_bytes(&fcs);
println!("new packet = {:?}", packet);
}
fn main()
{
let mut packet = Packet::new();
push_ipv4(&mut packet);
push_mac(&mut packet);
}
sfackler commented
Valgrind output with the allocator switched over to alloc_system:
==104800== Memcheck, a memory error detector
==104800== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==104800== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==104800== Command: ./foo
==104800==
old packet = 00 88 01 02 03 04 05 06 01 02 03 04 05 06 01 02 03 04 05 06 00 37 03 80 45 14 00 14 00 15 00 17
pushing D9 58 FB A8
==104800== Invalid write of size 1
==104800== at 0x10FE37: core::ptr::write (ptr.rs:330)
==104800== by 0x10D324: <alloc::vec_deque::VecDeque<T>>::buffer_write (vec_deque.rs:136)
==104800== by 0x10DB5B: <alloc::vec_deque::VecDeque<T>>::push_back (vec_deque.rs:1124)
==104800== by 0x1121AF: <alloc::vec_deque::VecDeque<A> as core::iter::traits::Extend<A>>::extend (vec_deque.rs:2424)
==104800== by 0x10BEB7: <alloc::vec_deque::VecDeque<T> as core::iter::traits::Extend<&'a T>>::extend (vec_deque.rs:2432)
==104800== by 0x1126F4: foo::Packet::push_back_bytes (foo.rs:44)
==104800== by 0x113234: foo::push_mac (foo.rs:149)
==104800== by 0x1132F4: foo::main (foo.rs:158)
==104800== by 0x1263EC: __rust_maybe_catch_panic (lib.rs:99)
==104800== by 0x11FE1B: try<(),closure> (panicking.rs:459)
==104800== by 0x11FE1B: catch_unwind<closure,()> (panic.rs:361)
==104800== by 0x11FE1B: std::rt::lang_start (rt.rs:59)
==104800== by 0x113872: main (foo.rs:0)
==104800== Address 0x5a31d00 is 0 bytes after a block of size 64 alloc'd
==104800== at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==104800== by 0x10C211: alloc_system::platform::<impl alloc::allocator::Alloc for &'a alloc_system::System>::alloc (lib.rs:134)
==104800== by 0x1133DB: __rg_alloc (foo.rs:9)
==104800== by 0x1118DE: <alloc::heap::Heap as alloc::allocator::Alloc>::alloc (heap.rs:84)
==104800== by 0x10DEFF: <alloc::raw_vec::RawVec<T, A>>::allocate_in (raw_vec.rs:97)
==104800== by 0x10D015: <alloc::raw_vec::RawVec<T>>::with_capacity (raw_vec.rs:141)
==104800== by 0x10D437: <alloc::vec_deque::VecDeque<T>>::with_capacity (vec_deque.rs:400)
==104800== by 0x112515: foo::Packet::new (foo.rs:25)
==104800== by 0x1132E0: foo::main (foo.rs:156)
==104800== by 0x1263EC: __rust_maybe_catch_panic (lib.rs:99)
==104800== by 0x11FE1B: try<(),closure> (panicking.rs:459)
==104800== by 0x11FE1B: catch_unwind<closure,()> (panic.rs:361)
==104800== by 0x11FE1B: std::rt::lang_start (rt.rs:59)
==104800== by 0x113872: main (foo.rs:0)
==104800==
==104800== Conditional jump or move depends on uninitialised value(s)
==104800== at 0x12B3CD: digit (num.rs:143)
==104800== by 0x12B3CD: fmt_int<core::fmt::num::UpperHex,u8> (num.rs:78)
==104800== by 0x12B3CD: core::fmt::num::<impl core::fmt::UpperHex for u8>::fmt (num.rs:184)
==104800== by 0x1298FA: run (mod.rs:1007)
==104800== by 0x1298FA: core::fmt::write (mod.rs:975)
==104800== by 0x126B2B: write_fmt<alloc::string::String> (mod.rs:223)
==104800== by 0x126B2B: alloc::fmt::format (fmt.rs:555)
==104800== by 0x112947: <foo::Packet as core::fmt::Debug>::fmt (foo.rs:54)
==104800== by 0x11164F: <&'a mut T as core::fmt::Debug>::fmt (mod.rs:1487)
==104800== by 0x129950: core::fmt::write (mod.rs:967)
==104800== by 0x117F8B: write_fmt<std::io::stdio::StdoutLock> (mod.rs:1143)
==104800== by 0x117F8B: <std::io::stdio::Stdout as std::io::Write>::write_fmt (stdio.rs:461)
==104800== by 0x11870B: print_to<std::io::stdio::Stdout> (stdio.rs:679)
==104800== by 0x11870B: std::io::stdio::_print (stdio.rs:701)
==104800== by 0x1132AA: foo::push_mac (foo.rs:151)
==104800== by 0x1132F4: foo::main (foo.rs:158)
==104800== by 0x1263EC: __rust_maybe_catch_panic (lib.rs:99)
==104800== by 0x11FE1B: try<(),closure> (panicking.rs:459)
==104800== by 0x11FE1B: catch_unwind<closure,()> (panic.rs:361)
==104800== by 0x11FE1B: std::rt::lang_start (rt.rs:59)
==104800==
==104800== Conditional jump or move depends on uninitialised value(s)
==104800== at 0x12B3DD: fmt_int<core::fmt::num::UpperHex,u8> (num.rs:80)
==104800== by 0x12B3DD: core::fmt::num::<impl core::fmt::UpperHex for u8>::fmt (num.rs:184)
==104800== by 0x1298FA: run (mod.rs:1007)
==104800== by 0x1298FA: core::fmt::write (mod.rs:975)
==104800== by 0x126B2B: write_fmt<alloc::string::String> (mod.rs:223)
==104800== by 0x126B2B: alloc::fmt::format (fmt.rs:555)
==104800== by 0x112947: <foo::Packet as core::fmt::Debug>::fmt (foo.rs:54)
==104800== by 0x11164F: <&'a mut T as core::fmt::Debug>::fmt (mod.rs:1487)
==104800== by 0x129950: core::fmt::write (mod.rs:967)
==104800== by 0x117F8B: write_fmt<std::io::stdio::StdoutLock> (mod.rs:1143)
==104800== by 0x117F8B: <std::io::stdio::Stdout as std::io::Write>::write_fmt (stdio.rs:461)
==104800== by 0x11870B: print_to<std::io::stdio::Stdout> (stdio.rs:679)
==104800== by 0x11870B: std::io::stdio::_print (stdio.rs:701)
==104800== by 0x1132AA: foo::push_mac (foo.rs:151)
==104800== by 0x1132F4: foo::main (foo.rs:158)
==104800== by 0x1263EC: __rust_maybe_catch_panic (lib.rs:99)
==104800== by 0x11FE1B: try<(),closure> (panicking.rs:459)
==104800== by 0x11FE1B: catch_unwind<closure,()> (panic.rs:361)
==104800== by 0x11FE1B: std::rt::lang_start (rt.rs:59)
==104800==
==104800== Conditional jump or move depends on uninitialised value(s)
==104800== at 0x4C3149A: memrchr (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==104800== by 0x118328: memrchr_specific (memchr.rs:39)
==104800== by 0x118328: memrchr (memchr.rs:56)
==104800== by 0x118328: memrchr (memchr.rs:55)
==104800== by 0x118328: write<std::io::stdio::Maybe<std::io::stdio::StdoutRaw>> (buffered.rs:799)
==104800== by 0x118328: <std::io::stdio::StdoutLock<'a> as std::io::Write>::write (stdio.rs:467)
==104800== by 0x118B02: std::io::Write::write_all (mod.rs:1072)
==104800== by 0x119045: <std::io::Write::write_fmt::Adaptor<'a, T> as core::fmt::Write>::write_str (mod.rs:1132)
==104800== by 0x111601: <alloc::string::String as core::fmt::Display>::fmt (string.rs:1767)
==104800== by 0x129950: core::fmt::write (mod.rs:967)
==104800== by 0x12A415: core::fmt::Formatter::write_fmt (mod.rs:1275)
==104800== by 0x1129EE: <foo::Packet as core::fmt::Debug>::fmt (foo.rs:57)
==104800== by 0x11164F: <&'a mut T as core::fmt::Debug>::fmt (mod.rs:1487)
==104800== by 0x129950: core::fmt::write (mod.rs:967)
==104800== by 0x117F8B: write_fmt<std::io::stdio::StdoutLock> (mod.rs:1143)
==104800== by 0x117F8B: <std::io::stdio::Stdout as std::io::Write>::write_fmt (stdio.rs:461)
==104800== by 0x11870B: print_to<std::io::stdio::Stdout> (stdio.rs:679)
==104800== by 0x11870B: std::io::stdio::_print (stdio.rs:701)
==104800==
==104800== Syscall param write(buf) points to uninitialised byte(s)
==104800== at 0x5255884: write (in /usr/lib/libpthread-2.26.so)
==104800== by 0x1174F0: write (fd.rs:104)
==104800== by 0x1174F0: write (stdio.rs:35)
==104800== by 0x1174F0: write (stdio.rs:85)
==104800== by 0x1174F0: write<std::io::stdio::StdoutRaw> (stdio.rs:101)
==104800== by 0x1174F0: <std::io::buffered::BufWriter<W>>::flush_buf (buffered.rs:405)
==104800== by 0x1183BA: flush<std::io::stdio::Maybe<std::io::stdio::StdoutRaw>> (buffered.rs:500)
==104800== by 0x1183BA: flush<std::io::stdio::Maybe<std::io::stdio::StdoutRaw>> (buffered.rs:828)
==104800== by 0x1183BA: write<std::io::stdio::Maybe<std::io::stdio::StdoutRaw>> (buffered.rs:812)
==104800== by 0x1183BA: <std::io::stdio::StdoutLock<'a> as std::io::Write>::write (stdio.rs:467)
==104800== by 0x118B02: std::io::Write::write_all (mod.rs:1072)
==104800== by 0x119045: <std::io::Write::write_fmt::Adaptor<'a, T> as core::fmt::Write>::write_str (mod.rs:1132)
==104800== by 0x129989: core::fmt::write (mod.rs:982)
==104800== by 0x117F8B: write_fmt<std::io::stdio::StdoutLock> (mod.rs:1143)
==104800== by 0x117F8B: <std::io::stdio::Stdout as std::io::Write>::write_fmt (stdio.rs:461)
==104800== by 0x11870B: print_to<std::io::stdio::Stdout> (stdio.rs:679)
==104800== by 0x11870B: std::io::stdio::_print (stdio.rs:701)
==104800== by 0x1132AA: foo::push_mac (foo.rs:151)
==104800== by 0x1132F4: foo::main (foo.rs:158)
==104800== by 0x1263EC: __rust_maybe_catch_panic (lib.rs:99)
==104800== by 0x11FE1B: try<(),closure> (panicking.rs:459)
==104800== by 0x11FE1B: catch_unwind<closure,()> (panic.rs:361)
==104800== by 0x11FE1B: std::rt::lang_start (rt.rs:59)
==104800== Address 0x5a31fff is 111 bytes inside a block of size 1,024 alloc'd
==104800== at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==104800== by 0x10C211: alloc_system::platform::<impl alloc::allocator::Alloc for &'a alloc_system::System>::alloc (lib.rs:134)
==104800== by 0x1133DB: __rg_alloc (foo.rs:9)
==104800== by 0x117C9F: alloc (heap.rs:84)
==104800== by 0x117C9F: allocate_in<u8,alloc::heap::Heap> (raw_vec.rs:97)
==104800== by 0x117C9F: with_capacity<u8> (raw_vec.rs:141)
==104800== by 0x117C9F: with_capacity<u8> (vec.rs:359)
==104800== by 0x117C9F: with_capacity<std::io::stdio::Maybe<std::io::stdio::StdoutRaw>> (buffered.rs:394)
==104800== by 0x117C9F: with_capacity<std::io::stdio::Maybe<std::io::stdio::StdoutRaw>> (buffered.rs:712)
==104800== by 0x117C9F: new<std::io::stdio::Maybe<std::io::stdio::StdoutRaw>> (buffered.rs:691)
==104800== by 0x117C9F: std::io::stdio::stdout::stdout_init (stdio.rs:411)
==104800== by 0x117BD2: init<std::sys_common::remutex::ReentrantMutex<core::cell::RefCell<std::io::buffered::LineWriter<std::io::stdio::Maybe<std::io::stdio::StdoutRaw>>>>> (lazy.rs:62)
==104800== by 0x117BD2: get<std::sys_common::remutex::ReentrantMutex<core::cell::RefCell<std::io::buffered::LineWriter<std::io::stdio::Maybe<std::io::stdio::StdoutRaw>>>>> (lazy.rs:39)
==104800== by 0x117BD2: std::io::stdio::stdout (stdio.rs:403)
==104800== by 0x1186D5: print_to<std::io::stdio::Stdout> (stdio.rs:679)
==104800== by 0x1186D5: std::io::stdio::_print (stdio.rs:701)
==104800== by 0x113028: foo::push_mac (foo.rs:147)
==104800== by 0x1132F4: foo::main (foo.rs:158)
==104800== by 0x1263EC: __rust_maybe_catch_panic (lib.rs:99)
==104800== by 0x11FE1B: try<(),closure> (panicking.rs:459)
==104800== by 0x11FE1B: catch_unwind<closure,()> (panic.rs:361)
==104800== by 0x11FE1B: std::rt::lang_start (rt.rs:59)
==104800== by 0x113872: main (foo.rs:0)
==104800==
new packet = 00 88 01 02 03 04 05 06 01 02 03 04 05 06 01 02 03 04 05 06 00 37 03 80 45 14 00 14 00 15 00 17 00 58 FB A8
==104800==
==104800== HEAP SUMMARY:
==104800== in use at exit: 0 bytes in 0 blocks
==104800== total heap usage: 163 allocs, 163 frees, 4,228 bytes allocated
==104800==
==104800== All heap blocks were freed -- no leaks are possible
==104800==
==104800== For counts of detected and suppressed errors, rerun with: -v
==104800== Use --track-origins=yes to see where uninitialised values come from
==104800== ERROR SUMMARY: 5 errors from 5 contexts (suppressed: 0 from 0)
sfackler commented
Here is what I believe is a minimal reproduction:
#![feature(global_allocator, alloc_system, allocator_api)]
extern crate alloc_system;
use std::collections::VecDeque;
use alloc_system::System;
#[global_allocator]
static ALLOCATOR: System = System;
fn main() {
let mut deque = VecDeque::with_capacity(32);
deque.push_front(0);
deque.reserve(31);
deque.push_back(0);
}Valgrind:
==107642== Memcheck, a memory error detector
==107642== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==107642== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==107642== Command: ./foo
==107642==
==107642== Invalid write of size 4
==107642== at 0x10E364: core::ptr::write (ptr.rs:330)
==107642== by 0x10C601: <alloc::vec_deque::VecDeque<T>>::buffer_write (vec_deque.rs:136)
==107642== by 0x10CD97: <alloc::vec_deque::VecDeque<T>>::push_back (vec_deque.rs:1124)
==107642== by 0x10FBEB: foo::main (foo.rs:14)
==107642== by 0x120F9C: __rust_maybe_catch_panic (lib.rs:99)
==107642== by 0x11A9CB: try<(),closure> (panicking.rs:459)
==107642== by 0x11A9CB: catch_unwind<closure,()> (panic.rs:361)
==107642== by 0x11A9CB: std::rt::lang_start (rt.rs:59)
==107642== by 0x110152: main (foo.rs:0)
==107642== Address 0x5a31dc0 is 0 bytes after a block of size 256 alloc'd
==107642== at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==107642== by 0x10BA51: alloc_system::platform::<impl alloc::allocator::Alloc for &'a alloc_system::System>::alloc (lib.rs:134)
==107642== by 0x10FCBB: __rg_alloc (foo.rs:8)
==107642== by 0x10F3FE: <alloc::heap::Heap as alloc::allocator::Alloc>::alloc (heap.rs:84)
==107642== by 0x10D13F: <alloc::raw_vec::RawVec<T, A>>::allocate_in (raw_vec.rs:97)
==107642== by 0x10C325: <alloc::raw_vec::RawVec<T>>::with_capacity (raw_vec.rs:141)
==107642== by 0x10C717: <alloc::vec_deque::VecDeque<T>>::with_capacity (vec_deque.rs:400)
==107642== by 0x10FBA7: foo::main (foo.rs:11)
==107642== by 0x120F9C: __rust_maybe_catch_panic (lib.rs:99)
==107642== by 0x11A9CB: try<(),closure> (panicking.rs:459)
==107642== by 0x11A9CB: catch_unwind<closure,()> (panic.rs:361)
==107642== by 0x11A9CB: std::rt::lang_start (rt.rs:59)
==107642== by 0x110152: main (foo.rs:0)
==107642==
==107642==
==107642== HEAP SUMMARY:
==107642== in use at exit: 0 bytes in 0 blocks
==107642== total heap usage: 15 allocs, 15 frees, 2,478 bytes allocated
==107642==
==107642== All heap blocks were freed -- no leaks are possible
==107642==
==107642== For counts of detected and suppressed errors, rerun with: -v
==107642== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
sfackler commented
It looks like this was introduced two years ago in bfa0e1f. Specifically, VecDeque::reserve mixes up its "raw" capacity and the user-visible capacity. These differ by one, so reserve can end up in a situation where it calls into handle_cap_increase without the capacity having actually increased. The implementation of that method assumes this doesn't happen, and as a result messes up the head and tail pointers so that the next push writes off the end of the buffer.
Making a fix right now.
naufraghi commented
This bug is referenced in CVE-2018-1000657:
Rust Programming Language Rust standard library version Commit bfa0e1f and later; stable release 1.3.0 and later contains a Buffer Overflow vulnerability in
std::collections::vec_deque::VecDeque::reserve()function that can result in Arbitrary code execution, but no proof-of-concept exploit is currently published.. This vulnerability appears to have been fixed in after commit fdfafb5; stable release 1.22.0 and later.