9 ms·

On bananas and string matching algorithms

260 points by cjbprime 12y ago

StefanKarpinski 12y ago
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.
zackmorris 12y ago
I've seen some very strange things in my career. I find posts like this delightful, because I can point to them and say "see, here is proof that even code written with the best of intentions can still have bugs." Programmers tend to fall into (at least) two camps: the skeptics and the pragmatists. Sometimes when I report a finding, programmers accuse me in one way or another of messing something up because “that can’t possibly be failing.” Those are the skeptics, using incredulousness almost like a shield to protect their worldview. They tend to have an up-close/what’s right in front of them approach to programming, are prolific and usually take a positive stance on programming. At other times, reporting a finding is met with resignation, almost like “please work around it because we just don’t need this right now”. Those are the pragmatists, taking the long view/forest for the trees approach, knowing that programming is more than the some of its parts but also that it’s a miracle it even works at all. They are the daydreamers and sometimes are perceived as negative or defeatist. I was a pragmatist for as long as I could remember, but had a change of heart working with others in professional settings. I saw that certain things like databases or unix filesystems could largely be relied upon to work in a deterministic manner, like they created a scaffolding that helps one stay grounded in reality. They help one command a very mathematical/deliberate demeanor, and overcome setbacks by treating bugs as something to be expected but still tractable. But here is one of those bugs, where the floor seemed to fall out from under our feet. One day I mentioned that “SSL isn’t working” and about half the office flipped out on me and the other half rolled their eyes and had me track it down: https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=694667 https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=694667 The gist of it is that OpenSSL was failing when the MTU was 1496 instead of 1500, because of path MTU discovery failing and SSL thinking it was a MITM attack and closing (at least, that is how I remember it, I am probably futzing some details). That was odd behavior to me, because I see SSL as something that should be a layer above TCP and not bother with the implementation details of underlying layers. It should operate under the assumption that there is always a man in the middle. If you can open a stream to a server, you should be able to send secure data over it. Anyway, we fixed the router setting and got back to work. All told I probably lost a day or two of productivity, because the office network had been running just fine for years and so I discounted it for a long time until I ruled out every other possibility. I’ve hit crazy bugs like this at least once a year, and regret not documenting them I suppose. Usually by the time they are fixed, people have forgotten the initial shock, but they still remember that you are the one weirdo who always seems to break everything.
sitkack 12y ago
Why is this code so damn fancy? Shouldn't the fanciness be offset by proofs or extended testing? Open loop!
- TTPrograms 12y ago
  My guess is that naive searcher is O(nm) and two way is O(n) for haystack length n and needle length m.
- pcwalton 12y ago
  Two-way searching is the norm for substring matching. Even your libc is probably using it for strstr(). For example, here's musl's implementation: http://git.musl-libc.org/cgit/musl/tree/src/string/strstr.c http://git.musl-libc.org/cgit/musl/tree/src/string/strstr.c
- userbinator 12y ago
  Agreed, this seems like a case of excessive complexity. I hadn't even heard of "two-way" before, but I don't think an algorithm the paper claims to be "remarkably simple" should require twenty-five pages to describe. "two-way" isn't all that fast either, so I don't see any good reason for its use; in the benchmarks I could find, the simpler BMH easily beats it (and optimised BMH variants go even faster): http://volnitsky.com/project/str_search/benchmark-4.5.1.png http://volnitsky.com/project/str_search/benchmark-4.5.1.png http://blog.phusion.nl/2010/12/06/efficient-substring-searching/ http://blog.phusion.nl/2010/12/06/efficient-substring-search...
  - sitkack 12y ago
    It would be interesting to put a trace on `strstr` for a couple days and see what the distribution of arguments look like. ToDo: Profile libc for various workloads, record arguments and code coverage
alayne 12y ago
I try to never look at GPL/LGPL code if I'm going to implement something at work or under another license. Sorry for suggesting a good practice to avoid legal liability.
- JadeNB 12y ago
  > Sorry for suggesting a good practice to avoid legal liability. Why is this good practice? Has anyone ever been exposed to a legal liability that could be creditably attributed to their merely looking at (as opposed to using) such code? (Although my suspicion is that the answer is 'no', this is an honest question.)
  - steveklabnik 12y ago
    Yes, it can come up. See the recent Google / Oracle lawsuit, where it was specifically presented that Dalvik was a 'clean room' implementation.
    - JadeNB 12y ago
      > Yes, it can come up. See the recent Google / Oracle lawsuit, where it was specifically presented that Dalvik was a 'clean room' implementation. I have no doubt that it can come up—all sorts of ludicrousness can; but my question was rather whether there have actually been any legal consequences, not just legal challenges. I haven't been following the lawsuit, and can't find at http://en.wikipedia.org/wiki/Oracle_v._Google http://en.wikipedia.org/wiki/Oracle_v._Google any clear indication of whether any of the decisions specifically find Google at fault specifically for copying GPL'd code. This article (http://www.zdnet.com/blog/bott/the-real-history-of-java-and-android-as-told-by-google/3924 http://www.zdnet.com/blog/bott/the-real-history-of-java-and-...), which may or may not be reliable, implies that there are subtle concerns at play: If this were a simple matter of some code being open and some not, this wouldn't be a multi-billion-dollar lawsuit. But the precise details of how Sun chose to write its licensing terms are extremely important.
  - cjbprime 12y ago
    I think the idea is that it's going to be difficult, having looked at the code, to implement a version that is not similar enough to the original to trigger a copyright "derivative work". For example, I believe it used to be the case (just a few years ago) that Microsoft employees were contractually prohibited from looking at GPL'd code. But if alayne is planning on bringing that up every time someone shares a post that might contain GPL code, alayne is quickly going to become the most tedious person at the party, and that's why the downvotes are happening. If your situation prevents you from studying and learning from GPL'd code, then just don't study it, and don't brag about not studying it.
srean 12y ago
There are many comments discussing whether length should be unsigned or signed. There are arguments for and against it. This a prototypical carpet bump, you squash it in one place it raises its head somewhere else. I see it not as a question whether lengths should be signed or unsigned but whether subtraction, assignment etc should be polymorphic w.r.t signed and unsigned. I think the issue here is the polymorphic variants of these binary operators are inherently risky. Casting gets a little tedious, but languages that do not have operator overloading should disallow subtraction from unsigned and subtraction that return unsigned. You either cast it up, or if possible reorder the expression/comparison so that the problem goes away. Even assignment can be a problem. Ocaml can get irritating because it takes this view but I think it is safer this way. It is very hard to be always vigilant about the unsigned signed issue, but hopefully a compiler error will mitigate risks, not completely, but it is better than nothing. That leaves languages that allow operator overloading, in those cases if you are overloading an operator you better know what you are doing, and watch out for cases where the operator is not closed.
- judk 12y ago
  What is the signed value of 0-UINT_MAX? There is no way to handle this issue on machine types, unless part of the range is reserved for overflow and checked. But performance nuts intentionally discard safety for performance.
  - srean 12y ago
    As I suggested there should not be a '-' that returns unsigned. If you want to cast it back to unsigned you would have to do it explicitly, and ideally a checked cast, though I am not averse to a more verbose unchecked cast. I am not averse to binary operators with wrap around / modulo arithmetic, but they should be look different from the usual '+', '-' etc. This only applies to languages that do not allow overloading operators.
    - gweinberg 12y ago
      I agree. It seems to me that saying unsigned - unsigned is unsigned is just asking for trouble.

260 points by cjbprime 12y ago

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.

zackmorris 12y ago

I've seen some very strange things in my career. I find posts like this delightful, because I can point to them and say "see, here is proof that even code written with the best of intentions can still have bugs." Programmers tend to fall into (at least) two camps: the skeptics and the pragmatists. Sometimes when I report a finding, programmers accuse me in one way or another of messing something up because “that can’t possibly be failing.” Those are the skeptics, using incredulousness almost like a shield to protect their worldview. They tend to have an up-close/what’s right in front of them approach to programming, are prolific and usually take a positive stance on programming. At other times, reporting a finding is met with resignation, almost like “please work around it because we just don’t need this right now”. Those are the pragmatists, taking the long view/forest for the trees approach, knowing that programming is more than the some of its parts but also that it’s a miracle it even works at all. They are the daydreamers and sometimes are perceived as negative or defeatist. I was a pragmatist for as long as I could remember, but had a change of heart working with others in professional settings. I saw that certain things like databases or unix filesystems could largely be relied upon to work in a deterministic manner, like they created a scaffolding that helps one stay grounded in reality. They help one command a very mathematical/deliberate demeanor, and overcome setbacks by treating bugs as something to be expected but still tractable. But here is one of those bugs, where the floor seemed to fall out from under our feet. One day I mentioned that “SSL isn’t working” and about half the office flipped out on me and the other half rolled their eyes and had me track it down: https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=694667 https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=694667 The gist of it is that OpenSSL was failing when the MTU was 1496 instead of 1500, because of path MTU discovery failing and SSL thinking it was a MITM attack and closing (at least, that is how I remember it, I am probably futzing some details). That was odd behavior to me, because I see SSL as something that should be a layer above TCP and not bother with the implementation details of underlying layers. It should operate under the assumption that there is always a man in the middle. If you can open a stream to a server, you should be able to send secure data over it. Anyway, we fixed the router setting and got back to work. All told I probably lost a day or two of productivity, because the office network had been running just fine for years and so I discounted it for a long time until I ruled out every other possibility. I’ve hit crazy bugs like this at least once a year, and regret not documenting them I suppose. Usually by the time they are fixed, people have forgotten the initial shock, but they still remember that you are the one weirdo who always seems to break everything.

sitkack 12y ago

Why is this code so damn fancy? Shouldn't the fanciness be offset by proofs or extended testing? Open loop!

TTPrograms 12y ago
My guess is that naive searcher is O(nm) and two way is O(n) for haystack length n and needle length m.
pcwalton 12y ago
Two-way searching is the norm for substring matching. Even your libc is probably using it for strstr(). For example, here's musl's implementation: http://git.musl-libc.org/cgit/musl/tree/src/string/strstr.c http://git.musl-libc.org/cgit/musl/tree/src/string/strstr.c
userbinator 12y ago
Agreed, this seems like a case of excessive complexity. I hadn't even heard of "two-way" before, but I don't think an algorithm the paper claims to be "remarkably simple" should require twenty-five pages to describe. "two-way" isn't all that fast either, so I don't see any good reason for its use; in the benchmarks I could find, the simpler BMH easily beats it (and optimised BMH variants go even faster): http://volnitsky.com/project/str_search/benchmark-4.5.1.png http://volnitsky.com/project/str_search/benchmark-4.5.1.png http://blog.phusion.nl/2010/12/06/efficient-substring-searching/ http://blog.phusion.nl/2010/12/06/efficient-substring-search...
- sitkack 12y ago
  It would be interesting to put a trace on `strstr` for a couple days and see what the distribution of arguments look like. ToDo: Profile libc for various workloads, record arguments and code coverage

alayne 12y ago

I try to never look at GPL/LGPL code if I'm going to implement something at work or under another license. Sorry for suggesting a good practice to avoid legal liability.

JadeNB 12y ago
> Sorry for suggesting a good practice to avoid legal liability. Why is this good practice? Has anyone ever been exposed to a legal liability that could be creditably attributed to their merely looking at (as opposed to using) such code? (Although my suspicion is that the answer is 'no', this is an honest question.)
- steveklabnik 12y ago
  Yes, it can come up. See the recent Google / Oracle lawsuit, where it was specifically presented that Dalvik was a 'clean room' implementation.
  - JadeNB 12y ago
    > Yes, it can come up. See the recent Google / Oracle lawsuit, where it was specifically presented that Dalvik was a 'clean room' implementation. I have no doubt that it can come up—all sorts of ludicrousness can; but my question was rather whether there have actually been any legal consequences, not just legal challenges. I haven't been following the lawsuit, and can't find at http://en.wikipedia.org/wiki/Oracle_v._Google http://en.wikipedia.org/wiki/Oracle_v._Google any clear indication of whether any of the decisions specifically find Google at fault specifically for copying GPL'd code. This article (http://www.zdnet.com/blog/bott/the-real-history-of-java-and-android-as-told-by-google/3924 http://www.zdnet.com/blog/bott/the-real-history-of-java-and-...), which may or may not be reliable, implies that there are subtle concerns at play: If this were a simple matter of some code being open and some not, this wouldn't be a multi-billion-dollar lawsuit. But the precise details of how Sun chose to write its licensing terms are extremely important.
- cjbprime 12y ago
  I think the idea is that it's going to be difficult, having looked at the code, to implement a version that is not similar enough to the original to trigger a copyright "derivative work". For example, I believe it used to be the case (just a few years ago) that Microsoft employees were contractually prohibited from looking at GPL'd code. But if alayne is planning on bringing that up every time someone shares a post that might contain GPL code, alayne is quickly going to become the most tedious person at the party, and that's why the downvotes are happening. If your situation prevents you from studying and learning from GPL'd code, then just don't study it, and don't brag about not studying it.

srean 12y ago

There are many comments discussing whether length should be unsigned or signed. There are arguments for and against it. This a prototypical carpet bump, you squash it in one place it raises its head somewhere else. I see it not as a question whether lengths should be signed or unsigned but whether subtraction, assignment etc should be polymorphic w.r.t signed and unsigned. I think the issue here is the polymorphic variants of these binary operators are inherently risky. Casting gets a little tedious, but languages that do not have operator overloading should disallow subtraction from unsigned and subtraction that return unsigned. You either cast it up, or if possible reorder the expression/comparison so that the problem goes away. Even assignment can be a problem. Ocaml can get irritating because it takes this view but I think it is safer this way. It is very hard to be always vigilant about the unsigned signed issue, but hopefully a compiler error will mitigate risks, not completely, but it is better than nothing. That leaves languages that allow operator overloading, in those cases if you are overloading an operator you better know what you are doing, and watch out for cases where the operator is not closed.

judk 12y ago
What is the signed value of 0-UINT_MAX? There is no way to handle this issue on machine types, unless part of the range is reserved for overflow and checked. But performance nuts intentionally discard safety for performance.
- srean 12y ago
  As I suggested there should not be a '-' that returns unsigned. If you want to cast it back to unsigned you would have to do it explicitly, and ideally a checked cast, though I am not averse to a more verbose unchecked cast. I am not averse to binary operators with wrap around / modulo arithmetic, but they should be look different from the usual '+', '-' etc. This only applies to languages that do not allow overloading operators.
  - gweinberg 12y ago
    I agree. It seems to me that saying unsigned - unsigned is unsigned is just asking for trouble.