Memory safety problem in insert_many()

[Qwaz]

Hello, we recently reported a buffer overflow bug in SmallVec::insert_many() servo/rust-smallvec#252.

This crate contains a slightly older copy of insert_many() that has the same vulnerability.

rust-lexical/lexical-core/src/util/sequence.rs

Lines 34 to 46 in 8c75e29

	/// Insert multiple elements at position `index`.
	///
	/// Shifts all elements before index to the back of the iterator.
	/// It uses size hints to try to minimize the number of moves,
	/// however, it does not rely on them. We cannot internally allocate, so
	/// if we overstep the lower_size_bound, we have to do extensive
	/// moves to shift each item back incrementally.
	///
	/// This implementation is adapted from [`smallvec`], which has a battle-tested
	/// implementation that has been revised for at least a security advisory
	/// warning. Smallvec is similarly licensed under an MIT/Apache dual license.
	///
	/// [`smallvec`]: https://github.com/servo/rust-smallvec

Please update the code when the fix is published.

Thanks!

[KamilaBorowska]

For what it's worth, the way this crate uses insert_many won't trigger the issue, but it's still worth fixing I would say.

[myrrlyn]

Hi! Thank you for this report.

I am fairly confident that my commit addresses the concerns of an iterator that underestimates its contents. That said, I would appreciate a double check. Please close this issue if you believe my commit is correct, or comment if it requires further work.

[Qwaz]

The patch breaks the element ordering:
[old head][new elements][old tail][new elements (extend)]

Maybe apply the patch from the upstream smallvec?
https://github.com/servo/rust-smallvec/pull/254/files#diff-b1a35a68f14e696205874893c07fd24fdb88882b47c23cc0e0c80a30c7d53759

[myrrlyn]

Gah. Figured I'd miss something. Thanks for the patch note. This ought to do it.

You know, there's a perfectly good .splice method that already does this work. You'd think they'd just copy alloc::Vec's homework on this one

[Qwaz]

1. Line 75-81 could be deleted for less distraction
2. I didn't test it, but wouldn't it panic at runtime? The length is set to index and never changed before calling vec.insert(index + num_added, elem);, so I expect it would panic because index + num_added > index (=vec.len()).

[Alexhuszagh]

@Qwaz I believe I've now addressed this, I've also independently tested the logic just to ensure it works with faulty iterators. I'll keep this issue open until the new version with the patch is released. The implementation is essentially identical to servo/rust-smallvec's current implementation, just to avoid any risks with unusual edge-cases.

Does this fix look satisfactory?

[Qwaz]

Thanks for the fix, it looks good.

[Alexhuszagh]

Wonderful, I'll keep this issue open until the newest version is released (and also backport it to maintained branches). So far this has been backported to every branch. Once again, thank you.

[Alexhuszagh]

Closed as of v0.4.8, v0.6.8, and v0.7.6. This did not affect the v0.5 branch, since that depends on stack-vector, which has patched it upstream.