8 ms·

Really interesting post and good debugging work. A couple of take-aways: 1. This is one reason it's a good idea to use signed ints for lengths even though they

Really interesting post and good debugging work. A couple of take-aways: 1. This is one reason it's a good idea to use signed ints for lengths even though they can never be negative. Signed 64-bit ints have plenty of range for any array you're actually going to encounter. It may also be evidence that it's a good idea for mixed signed/unsigned arithmetic to produce signed results rather than unsigned: signed tends to be value-correct for "small" values (less than 2^63), including negative results; unsigned sacrifices value-correctness on all negative values to be correct for very large values, which is a less common case – here it will never happen since there just aren't strings that large. 2. If you're going to use a fancy algorithm like two-way search, you really ought to have a lot of test cases, especially ones that exercise corner cases of the algorithm. 100% coverage of all non-error code paths would be ideal.

QuantumChaos 12y ago
Regarding 2., I'm going to assume they have at least some unit tests. It's not clear that even 100% coverage would have picked up this bug, since it doesn't automatically appear as a result of taking a particular code path. I think that comparing to a naive algorithm on a large number of strings, or using a fuzzing tool, might be helpful, but this might also slow down the test suite excessively. I find unit tests are a bit like good form at the gym. Whenever someone gets injured, they think back to the last exercise they did and find some imperfection in their form. They then attribute their injury to not using perfect form. Similarly, whenever a bug appears, there is a tendency to find a unit test that would have caught the bug, and therefore attribute it to insufficient testing. The real value of testing (and good form) can only be demonstrated by having a criteria for good testing and seeing if following this reduces the number of bugs.
- Ono-Sendai 12y ago
  They did have some tests, obviously not enough though.
  - sitkack 12y ago
    I don't think it is the number but the depth. Something like QuickCheck would help. Or, having simpler code.
    - cjbprime 12y ago
      This is a really good point, and it looks like QuickCheck is supported on Rust -- here's one of several implementations: https://github.com/BurntSushi/quickcheck https://github.com/BurntSushi/quickcheck Would be pretty cool to see someone hook it up to the standard library tests.
- akkartik 12y ago
  No unit tests for the string library: https://github.com/rust-lang/rust/blob/6843d8ccd5/src/libcoretest/str.rs https://github.com/rust-lang/rust/blob/6843d8ccd5/src/libcor... (That's the hash for tip at the time of this comment.)
  - pcwalton 12y ago
    There are more tests that test the string library in src/test/run-pass/. This reflects the fact that std::str predates the current unit testing infrastructure, basically.
  - dbaupp 12y ago
    There's a lot of tests: https://github.com/rust-lang/rust/blob/f66fd2eed10de2acacd8af73c704bf4d140410bb/src/libcollections/str.rs#L870-L2356 https://github.com/rust-lang/rust/blob/f66fd2eed10de2acacd8a... Testing is something Rust is very big on, e.g. we run the test suite on many architectures/platforms each pull request and merge only if it passes on all: master is always green.
    - akkartik 12y ago
      Ah, I see the ones for contains: https://github.com/rust-lang/rust/blob/f66fd2eed1/src/libcollections/str.rs#L1518 https://github.com/rust-lang/rust/blob/f66fd2eed1/src/libcol... Thanks for pointing them out.
haberman 12y ago
I'm not sure I agree with #1. While it's true that using signed integers for lengths would have solved this problem, a negative length doesn't generally make sense or have any defined meaning. So if you have any logic that is doing case analysis on lengths, you basically have no reasonable action in the case of a negative length: all you can do is complain that the length got corrupted at some point. For example, imagine that instead of testing whether the strings differed by more than 20, you were just testing whether the needle was >= 20 in length: impl Searcher { fn new(haystack: &[u8], needle: &[u8]) -> Searcher { match needle.len() { 0..20 => Naive(NaiveSearcher::New) 20..uint::MAX => TwoWay(TwoWaySearcher::New(needle)) _ => fail!("Negative length, shouldn't happen!") } } } Part of the feature of an unsigned type IMO is that it cannot have an out-of-domain value by definition.
- CJefferson 12y ago
  The problem is that while unsigned types cannot have an out-of-domain value, they wrap. Also, often negative lengths make sense as meaning "backwards". In C++ I often hit in algorithms code that looks like some variant of: a.size()-1 >= capacity But when a.size() == 0, a.size() - 1 is MAXINT. Of course I could re-write this as a.size() >= capacity + 1, but that requires remembering / noticing. Personally I find this so annoying that when I recently had to write a set of my own C++ containers (as I needed 1-indexed rather than 0-indexed containers), I decided to make the return value of size() signed.
  - haberman 12y ago
    > But when a.size() == 0, a.size() - 1 is MAXINT. This is exactly the same problem class of bug as mentioned in the original article. But my argument is that while signed lengths fix some problems, they cause others. Maybe I'd put it this way: I dislike using signed integers for lengths, because it creates an entirely new class of undefined (or arbitrarily-defined) behavior. Imagine that memcpy() took a signed length instead of unsigned. What should it do if it receives a negative length? There is no great answer to that question. It's true that if you have a bug, you might accidentally pass a very large unsigned integer to memcpy(). But at least you can predict what memcpy() will do now: it will attempt to copy a very large number of bytes and probably crash. Whereas if you pass a negative integer, it might reasonably do any of these things: - nothing - crash - attempt to copy bytes *before* the supplied ptr - assert()-fail and/or call abort() What's worse, it creates a sense of anxiety for anyone implementing a function like memcpy(), because there is no right answer for what they should do with a negative length. Callers of memcpy() might reasonably want any of the above. But then you get your callers angry with you because "obviously" a negative length means you should do nothing, or "obviously" a negative length means you should assert()-fail (a programmer's opinion about what is the "obvious" right behavior is often unduly influenced by their specific circumstances).
wyager 12y ago
> This is one reason it's a good idea to use signed ints for lengths I disagree. Types are a form of documentation, and a constraint on proper program behavior. Length types can't be negative; that doesn't make any sense. If you end up with a negative length, you are doing something wrong. One should just write correct code and use the proper length type. In C that's `size_t`, and in Rust it's `uint`.
- yongjik 12y ago
  The problem is that C (and many other languages) only have the notion of "signed" vs. "unsigned" values, and nothing else. For example, if 'len' is a variable that holds the length of something, then its range is defined by (len >= 0). So far so good. But what is the range of the expression (len - 1)? In a perfect world, its range is {-1, 0, 1, ...} (up to some maximum value), but C(++) doesn't have such notion. If we used uint, -1 will silently change to MAX_UINT. Oops.
  - wyager 12y ago
    >But what is the range of the expression (len - 1)? Ill-defined, which is as it should be. Naturals are not closed under subtraction or negation, and therefore you should never negate or subtract a length.
    - thaumasiotes 12y ago
      You subtract lengths from other lengths all the time. How far have you gone recently? How much taller are you than your wife? Subtracting a length from another length isn't a problem at all; a problem would be if you wanted to subtract a length from a weight. This > Naturals are not closed under subtraction or negation, and therefore you should never negate or subtract a length. assumes that a paramount goal in having types is to make function signatures like the following impossible: public static String format(String format, Object... args); Infinite-dimensional vectors (in which the first element is a String) sure aren't closed under format -- it maps them to scalars! But somehow string formatting is wildly popular. Or think of public Color(int r, int g, int b); public Color(int rgb); Are you comfortable having a mapping from ℤ to Color, and from ℤ^3 to Color? If so, why does it bother you less than a mapping from ℤ ∩ [0, ∞) to ℤ ∩ [-1, ∞)? Try a simple rewording of your argument: Hash tables aren't closed under access. Therefore, you should never retrieve values from a hash table.
SolarNet 12y ago
I think the correct solution is for the type system to be able to say "Hey, this unsigned int is being subtracted from and was not checked to ensure it is greater than the value being subtracted." And the typical solution would be to either a) invert the subtraction to an addition, b) do a check, or c) annotate the type.
- eru 12y ago
  Or add a proof.
nly 12y ago
On #1: Signed under and overflow in C and C++ is undefined behaviour and can do weird things. In combination with compiler optimizations especially, the compiler can simply assume it never happens. Using unsigned types means when someone passes you a negative int at least the result is well-defined and can be debugged when your program explodes. Use unsigned types for unsigned values, and ensure all (new at least) code compiles cleanly with -Wconversion and -Wsign-conversion enabled, which should really be the default warning level these days.

QuantumChaos 12y ago

Regarding 2., I'm going to assume they have at least some unit tests. It's not clear that even 100% coverage would have picked up this bug, since it doesn't automatically appear as a result of taking a particular code path. I think that comparing to a naive algorithm on a large number of strings, or using a fuzzing tool, might be helpful, but this might also slow down the test suite excessively. I find unit tests are a bit like good form at the gym. Whenever someone gets injured, they think back to the last exercise they did and find some imperfection in their form. They then attribute their injury to not using perfect form. Similarly, whenever a bug appears, there is a tendency to find a unit test that would have caught the bug, and therefore attribute it to insufficient testing. The real value of testing (and good form) can only be demonstrated by having a criteria for good testing and seeing if following this reduces the number of bugs.

Ono-Sendai 12y ago
They did have some tests, obviously not enough though.
- sitkack 12y ago
  I don't think it is the number but the depth. Something like QuickCheck would help. Or, having simpler code.
  - cjbprime 12y ago
    This is a really good point, and it looks like QuickCheck is supported on Rust -- here's one of several implementations: https://github.com/BurntSushi/quickcheck https://github.com/BurntSushi/quickcheck Would be pretty cool to see someone hook it up to the standard library tests.
akkartik 12y ago
No unit tests for the string library: https://github.com/rust-lang/rust/blob/6843d8ccd5/src/libcoretest/str.rs https://github.com/rust-lang/rust/blob/6843d8ccd5/src/libcor... (That's the hash for tip at the time of this comment.)
- pcwalton 12y ago
  There are more tests that test the string library in src/test/run-pass/. This reflects the fact that std::str predates the current unit testing infrastructure, basically.
- dbaupp 12y ago
  There's a lot of tests: https://github.com/rust-lang/rust/blob/f66fd2eed10de2acacd8af73c704bf4d140410bb/src/libcollections/str.rs#L870-L2356 https://github.com/rust-lang/rust/blob/f66fd2eed10de2acacd8a... Testing is something Rust is very big on, e.g. we run the test suite on many architectures/platforms each pull request and merge only if it passes on all: master is always green.
  - akkartik 12y ago
    Ah, I see the ones for contains: https://github.com/rust-lang/rust/blob/f66fd2eed1/src/libcollections/str.rs#L1518 https://github.com/rust-lang/rust/blob/f66fd2eed1/src/libcol... Thanks for pointing them out.

haberman 12y ago

I'm not sure I agree with #1. While it's true that using signed integers for lengths would have solved this problem, a negative length doesn't generally make sense or have any defined meaning. So if you have any logic that is doing case analysis on lengths, you basically have no reasonable action in the case of a negative length: all you can do is complain that the length got corrupted at some point. For example, imagine that instead of testing whether the strings differed by more than 20, you were just testing whether the needle was >= 20 in length: impl Searcher { fn new(haystack: &[u8], needle: &[u8]) -> Searcher { match needle.len() { 0..20 => Naive(NaiveSearcher::New) 20..uint::MAX => TwoWay(TwoWaySearcher::New(needle)) _ => fail!("Negative length, shouldn't happen!") } } } Part of the feature of an unsigned type IMO is that it cannot have an out-of-domain value by definition.

CJefferson 12y ago
The problem is that while unsigned types cannot have an out-of-domain value, they wrap. Also, often negative lengths make sense as meaning "backwards". In C++ I often hit in algorithms code that looks like some variant of: a.size()-1 >= capacity But when a.size() == 0, a.size() - 1 is MAXINT. Of course I could re-write this as a.size() >= capacity + 1, but that requires remembering / noticing. Personally I find this so annoying that when I recently had to write a set of my own C++ containers (as I needed 1-indexed rather than 0-indexed containers), I decided to make the return value of size() signed.
- haberman 12y ago
  > But when a.size() == 0, a.size() - 1 is MAXINT. This is exactly the same problem class of bug as mentioned in the original article. But my argument is that while signed lengths fix some problems, they cause others. Maybe I'd put it this way: I dislike using signed integers for lengths, because it creates an entirely new class of undefined (or arbitrarily-defined) behavior. Imagine that memcpy() took a signed length instead of unsigned. What should it do if it receives a negative length? There is no great answer to that question. It's true that if you have a bug, you might accidentally pass a very large unsigned integer to memcpy(). But at least you can predict what memcpy() will do now: it will attempt to copy a very large number of bytes and probably crash. Whereas if you pass a negative integer, it might reasonably do any of these things: - nothing - crash - attempt to copy bytes *before* the supplied ptr - assert()-fail and/or call abort() What's worse, it creates a sense of anxiety for anyone implementing a function like memcpy(), because there is no right answer for what they should do with a negative length. Callers of memcpy() might reasonably want any of the above. But then you get your callers angry with you because "obviously" a negative length means you should do nothing, or "obviously" a negative length means you should assert()-fail (a programmer's opinion about what is the "obvious" right behavior is often unduly influenced by their specific circumstances).

wyager 12y ago

> This is one reason it's a good idea to use signed ints for lengths I disagree. Types are a form of documentation, and a constraint on proper program behavior. Length types can't be negative; that doesn't make any sense. If you end up with a negative length, you are doing something wrong. One should just write correct code and use the proper length type. In C that's `size_t`, and in Rust it's `uint`.

yongjik 12y ago
The problem is that C (and many other languages) only have the notion of "signed" vs. "unsigned" values, and nothing else. For example, if 'len' is a variable that holds the length of something, then its range is defined by (len >= 0). So far so good. But what is the range of the expression (len - 1)? In a perfect world, its range is {-1, 0, 1, ...} (up to some maximum value), but C(++) doesn't have such notion. If we used uint, -1 will silently change to MAX_UINT. Oops.
- wyager 12y ago
  >But what is the range of the expression (len - 1)? Ill-defined, which is as it should be. Naturals are not closed under subtraction or negation, and therefore you should never negate or subtract a length.
  - thaumasiotes 12y ago
    You subtract lengths from other lengths all the time. How far have you gone recently? How much taller are you than your wife? Subtracting a length from another length isn't a problem at all; a problem would be if you wanted to subtract a length from a weight. This > Naturals are not closed under subtraction or negation, and therefore you should never negate or subtract a length. assumes that a paramount goal in having types is to make function signatures like the following impossible: public static String format(String format, Object... args); Infinite-dimensional vectors (in which the first element is a String) sure aren't closed under format -- it maps them to scalars! But somehow string formatting is wildly popular. Or think of public Color(int r, int g, int b); public Color(int rgb); Are you comfortable having a mapping from ℤ to Color, and from ℤ^3 to Color? If so, why does it bother you less than a mapping from ℤ ∩ [0, ∞) to ℤ ∩ [-1, ∞)? Try a simple rewording of your argument: Hash tables aren't closed under access. Therefore, you should never retrieve values from a hash table.

SolarNet 12y ago

I think the correct solution is for the type system to be able to say "Hey, this unsigned int is being subtracted from and was not checked to ensure it is greater than the value being subtracted." And the typical solution would be to either a) invert the subtraction to an addition, b) do a check, or c) annotate the type.

eru 12y ago
Or add a proof.

nly 12y ago

On #1: Signed under and overflow in C and C++ is undefined behaviour and can do weird things. In combination with compiler optimizations especially, the compiler can simply assume it never happens. Using unsigned types means when someone passes you a negative int at least the result is well-defined and can be debugged when your program explodes. Use unsigned types for unsigned values, and ensure all (new at least) code compiles cleanly with -Wconversion and -Wsign-conversion enabled, which should really be the default warning level these days.