Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cryptic genetic variation in software: hunting a buffered 41-year-old bug

cryptogenomicon.wordpress.com

Post reply on HN
Print view View original

41–50 of 50 posts

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#41

Post by abecedarius »

PhantomGremlin wrote: post #29

At least one, possibly two other bugs lurking in the implementation. 1) Algorithm FT says: 1. Generate u. Store the first bit of u as a sign s (s=0 if u =1/2). and yet the C code implements if ( u 2) I can't be sure of the following w/o access to doc. But i4_uni() says a uniform distribution over (1, 2147483562) which, offhand, is suspicious. A distribution over positive integers would probably want to use all availa…

Good point about the C code. OTOH, 2147483562 is 1 less than a prime, which is unlikely to be an accident.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#43

Post by nknighthb »

munificent wrote: post #38
kator wrote: post #31

I always cringe when I see or have to write: for ( ; ; ) or: while ( true ) etc. You just know you're setting yourself up for undocumented bugs later. I've been known to build "escape" vars into these like: int attempts = 1000; for(;attempts > 0;attempts--) { ** DO SOMETHING ** } if (attempts Where 1000 or whatever number is a reasonable estimate of the function's need to loop x 10 or etc.

Really? I use "while (true)" pretty frequently in my code. In my mind, all loops are composed of these parts: 1. Some initialization (optional). 2. Some stuff you do each iteration (optional). 3. Check the exit condition and exit the loop (optional). 4. Some stuff you do each iteration (optional). "while" loops nicely handle the case where 2 is empty. "do while" loops handle 4 being empty. "for" loops handle both 2 a…

Burying the only way out in the loop body is more error-prone, especially for those who come after you. Putting an escape hatch in the loop setup makes it less likely that an operationally-problematic[0] infinite loop scenario will be triggered. This is particularly important when your code doesn't have a runtime environment that can easily kill runaway requests.

[0] Or utterly catastrophic. Think embedded system with limited debugging facilities. This kind of bug could manifest as the system completely locking up, and take much, much longer to track down than a "infinite loop detected!" message in an error log.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#44

Post by na85 »

kator wrote: post #31

I always cringe when I see or have to write: for ( ; ; ) or: while ( true ) etc. You just know you're setting yourself up for undocumented bugs later. I've been known to build "escape" vars into these like: int attempts = 1000; for(;attempts > 0;attempts--) { ** DO SOMETHING ** } if (attempts Where 1000 or whatever number is a reasonable estimate of the function's need to loop x 10 or etc.

I'm not sure why any competent programmer would use for(;;) or while(true) without explicitly including a break; statement.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#45

Post by captaincrowbar »

ZoFreX wrote: post #12
imurray wrote: post #7

It would be safest for most rand() functions to omit both zero and one, unless a user was really sure they wanted otherwise. If we were generating real numbers, we'd never see precisely zero or one. The fact that we do is an artifact of limited precision. These boundary cases cause problems in common computations like u.log(u) or (1-u).log(1-u).

It's pretty common in practice to want [0,1) (that is, 0 <= x < 1) from your random number generator. Never generating 0 would be a problem when the range is small and discrete - generating random letters for example.

If you're generating integers, or selecting from a discrete set with uniform probabilities, there's no reason to involve floating point at any point in the process.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#46

Post by gh02t »

ntlve wrote: post #23
jdpage wrote: post #19

Earlier quoted context omitted.

From a real analysis standpoint... the definition of a 'closed set' in an N-dimensional metric space (of which Euclidean space, i.e. normal space, is an example) is as follows: a set C is 'closed' if and only if, given any sequence of elements (x_n) converging on x, such that (x_n) is a subset of C, it follows that x is also in C. Under this definition, 'closed' makes sense in the larger context, since in mathematics…

Out of curiosity, do you have any examples or references to something with examples of sets that are neither open nor closed?

Also, it is possible for the opposite to occur. So-called clopen sets are both open and closed.

http://en.m.wikipedia.org/wiki/Clopen_set

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#47

Post by jdpage »

ntlve wrote: post #23
jdpage wrote: post #19

Earlier quoted context omitted.

From a real analysis standpoint... the definition of a 'closed set' in an N-dimensional metric space (of which Euclidean space, i.e. normal space, is an example) is as follows: a set C is 'closed' if and only if, given any sequence of elements (x_n) converging on x, such that (x_n) is a subset of C, it follows that x is also in C. Under this definition, 'closed' makes sense in the larger context, since in mathematics…

Out of curiosity, do you have any examples or references to something with examples of sets that are neither open nor closed?

The simplest example I can think of is the interval (0, 1].

Proof that it's not closed: the sequence (1, 1/2, 1/4, 1/8, ...) is entirely inside the interval, but converges on 0, which is outside the interval, therefore etc.

Proof that it's not open: the sequence (2, 3/2, 5/4, 9/8, ...) is entirely outside the interval (i.e. inside the complement), but it converges on 1, which is inside the interval (i.e. outside the complement). Thus the complement of the interval is not closed, therefore etc.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#48

Post by munificent »

nknighthb wrote: post #43
munificent wrote: post #38

Earlier quoted context omitted.

Really? I use "while (true)" pretty frequently in my code. In my mind, all loops are composed of these parts: 1. Some initialization (optional). 2. Some stuff you do each iteration (optional). 3. Check the exit condition and exit the loop (optional). 4. Some stuff you do each iteration (optional). "while" loops nicely handle the case where 2 is empty. "do while" loops handle 4 being empty. "for" loops handle both 2 a…

Burying the only way out in the loop body is more error-prone, especially for those who come after you. Putting an escape hatch in the loop setup makes it less likely that an operationally-problematic[0] infinite loop scenario will be triggered. This is particularly important when your code doesn't have a runtime environment that can easily kill runaway requests. [0] Or utterly catastrophic. Think embedded system wit…

> Burying the only way out in the loop body is more error-prone, especially for those who come after you.

I don't prefer to exit from the middle of a loop, but if that's the most succinct way to implement the correct behavior, I'll do it. I think short code that exits from the middle is less error-prone than code that has to be more convoluted to put the exit at the top of bottom.

> Putting an escape hatch in the loop setup makes it less likely that an operationally-problematic[0] infinite loop scenario will be triggered.

An escape hatch is yet more code that has to be tested and debugged. What if the escape hatch triggers to early?

> [0] Or utterly catastrophic. Think embedded system with limited debugging facilities.

Sure, but unusual platforms require unusual coding styles. If I was targeting that I might adjust my practices.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#49

Post by nknighthb »

munificent wrote: post #48
nknighthb wrote: post #43

Earlier quoted context omitted.

Burying the only way out in the loop body is more error-prone, especially for those who come after you. Putting an escape hatch in the loop setup makes it less likely that an operationally-problematic[0] infinite loop scenario will be triggered. This is particularly important when your code doesn't have a runtime environment that can easily kill runaway requests. [0] Or utterly catastrophic. Think embedded system wit…

> Burying the only way out in the loop body is more error-prone, especially for those who come after you. I don't prefer to exit from the middle of a loop, but if that's the most succinct way to implement the correct behavior, I'll do it. I think short code that exits from the middle is less error-prone than code that has to be more convoluted to put the exit at the top of bottom. > Putting an escape hatch in the loo…

> code that has to be more convoluted to put the exit at the top of bottom

Note I said only way out. The point is that if "the" (intended) exit can't reasonably be in the loop condition, then adding an escape hatch to have a second way out is useful.

Assuming C you can even just compress the whole thing to a for_x_tries(n) macro.

> What if the escape hatch triggers to early?

You'll get a helpful message and can bump the count. Easily-isolated errors are preferable to frozen/DoS'd systems.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#50

Post by segmondy »

kator wrote: post #31

I always cringe when I see or have to write: for ( ; ; ) or: while ( true ) etc. You just know you're setting yourself up for undocumented bugs later. I've been known to build "escape" vars into these like: int attempts = 1000; for(;attempts > 0;attempts--) { ** DO SOMETHING ** } if (attempts Where 1000 or whatever number is a reasonable estimate of the function's need to loop x 10 or etc.

I wonder what you will do when you see tail call optimization functions in prolog or lisp.
Post reply on HN