Re: svn commit: r241373 - head/lib/libc/stdlib
On Tue, Oct 09, 2012 at 01:51:05PM -0400, Eitan Adler wrote: On 9 October 2012 13:27, m...@freebsd.org wrote: The original behavior can be recovered by using inline assembly to fetch the value from a register into a local C variable; this would at least not rely on undefined behavior. But I agree it's of dubious value anyways. I proposed this (with a patch). We want to move to not using /dev/random and instead make a kernel system call directly. The patch for this is not finished yet though. You should do something similar to: http://people.freebsd.org/~pjd/patches/libc_arc4random.c.patch -- Pawel Jakub Dawidek http://www.wheelsystems.com FreeBSD committer http://www.FreeBSD.org Am I Evil? Yes, I Am! http://tupytaj.pl pgpF47iS54IbM.pgp Description: PGP signature
Re: svn commit: r241373 - head/lib/libc/stdlib
On 11.10.2012 19:23, Peter Wemm wrote: On Thu, Oct 11, 2012 at 6:14 AM, Andrey Chernov a...@freebsd.org wrote: On 11.10.2012 15:44, Pawel Jakub Dawidek wrote: On Tue, Oct 09, 2012 at 01:51:05PM -0400, Eitan Adler wrote: On 9 October 2012 13:27, m...@freebsd.org wrote: The original behavior can be recovered by using inline assembly to fetch the value from a register into a local C variable; this would at least not rely on undefined behavior. But I agree it's of dubious value anyways. I proposed this (with a patch). We want to move to not using /dev/random and instead make a kernel system call directly. The patch for this is not finished yet though. You should do something similar to: http://people.freebsd.org/~pjd/patches/libc_arc4random.c.patch Already half of year I told people of our serious problem with kernel's arc4 (used here in sysctl) - it have very weak initialization at the kernel start (only from processor clock) which is auto-fixed because of its periodic reseeds, but only at the next reseed which happens late. I post two patches (both working, one using atomic, another don't use it) which reseeds kernel's arc4 as fast as we have enough real entropy. NetBSD don't have this problem because of their different kernel's arc4 implementation. How late is late? Since this was a userland patch, has it been reseeded by then? See /sys/libkern/arc4random.c #define ARC4_RESEED_SECONDS 300 i.e. first 5 minutes at least it is very bad seeded and vulnerable. But we don't have guarantee to have enough entropy even after first 5 minutes, it very depends of entropy sources turned on the machine configuration at whole (diskless, etc). Moreover, arc4random(3) code have its own reseed happens after arc4_count = 160; (divided by 4) iterations which increases bad seeded bytes initially taken from kernel's arc4 until whole count will be exhausted which is _very_ long time (consider that typical application issue only several rare arc4random(3) calls and exits, left arc4_count not decreased globally at all). Regardless, this is getting way off topic from using an xor of an uninitialized userland variable and what the compiler optimizer might do with it. Of course that's assuming it is even a memory based stack. The sparc or ia64 register stack makes that xor even more dubious. I pass this subj to the people who knows clang compiler better to say for sure is it right to generate LLVM intermediate call void @srand(i32 undef) or not. Xoring the stack (or register) there is not essential step. ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
Do you check assembler output for _both_ cases? In my testing clang and gcc xor's 'junk' properly in case it have 'volatile' keyword (as in srandomdev()) and elide it without 'volatile'. IMHO this change should be backed out for srandomdev() and adding 'volatile' for sranddev() instead. On 09.10.2012 18:25, Eitan Adler wrote: Author: eadler Date: Tue Oct 9 14:25:14 2012 New Revision: 241373 URL: http://svn.freebsd.org/changeset/base/241373 Log: Remove undefined behavior from sranddev() and srandomdev(). This doesn't actually work with any modern C compiler: In particular, both clang and modern gcc verisons silently elide any xor operation with 'junk'. Approved by:secteam MFC after: 3 days Modified: head/lib/libc/stdlib/rand.c head/lib/libc/stdlib/random.c Modified: head/lib/libc/stdlib/rand.c == --- head/lib/libc/stdlib/rand.c Tue Oct 9 13:21:08 2012 (r241372) +++ head/lib/libc/stdlib/rand.c Tue Oct 9 14:25:14 2012 (r241373) @@ -130,10 +130,9 @@ sranddev() if (!done) { struct timeval tv; - unsigned long junk; gettimeofday(tv, NULL); - srand((getpid() 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk); + srand((getpid() 16) ^ tv.tv_sec ^ tv.tv_usec); } } Modified: head/lib/libc/stdlib/random.c == --- head/lib/libc/stdlib/random.c Tue Oct 9 13:21:08 2012 (r241372) +++ head/lib/libc/stdlib/random.c Tue Oct 9 14:25:14 2012 (r241373) @@ -312,10 +312,9 @@ srandomdev(void) if (!done) { struct timeval tv; - volatile unsigned long junk; gettimeofday(tv, NULL); - srandom((getpid() 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk); + srandom((getpid() 16) ^ tv.tv_sec ^ tv.tv_usec); return; } ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On 9 Oct 2012, at 17:33, Andrey Chernov wrote: Do you check assembler output for _both_ cases? In my testing clang and gcc xor's 'junk' properly in case it have 'volatile' keyword (as in srandomdev()) and elide it without 'volatile'. IMHO this change should be backed out for srandomdev() and adding 'volatile' for sranddev() instead. In it's original form, it is very dangerous - the whole expression reduces to undefined and so the LLVM IR for the call is: call void @srand(i32 undef) The back end is then free to use any value for the call argument, including any register value or 0. Since the value is passed in a register, it will probably just use whatever the last value there is, which may or may not be anything sensible. On MIPS, for example, this is most likely to be tv, and so is 100% deterministic. Adding the volatile means that we are doing an XOR with a value left on the stack. If this is early on in the application, then it is most likely to be 0. If it's later on, then there may be a value here, but it's still not very likely to be something particularly unpredictable. David ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On Tue, Oct 9, 2012 at 10:16 AM, David Chisnall thera...@freebsd.org wrote: On 9 Oct 2012, at 17:33, Andrey Chernov wrote: Do you check assembler output for _both_ cases? In my testing clang and gcc xor's 'junk' properly in case it have 'volatile' keyword (as in srandomdev()) and elide it without 'volatile'. IMHO this change should be backed out for srandomdev() and adding 'volatile' for sranddev() instead. In it's original form, it is very dangerous - the whole expression reduces to undefined and so the LLVM IR for the call is: call void @srand(i32 undef) The back end is then free to use any value for the call argument, including any register value or 0. Since the value is passed in a register, it will probably just use whatever the last value there is, which may or may not be anything sensible. On MIPS, for example, this is most likely to be tv, and so is 100% deterministic. Adding the volatile means that we are doing an XOR with a value left on the stack. If this is early on in the application, then it is most likely to be 0. If it's later on, then there may be a value here, but it's still not very likely to be something particularly unpredictable. The original behavior can be recovered by using inline assembly to fetch the value from a register into a local C variable; this would at least not rely on undefined behavior. But I agree it's of dubious value anyways. ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On 9 October 2012 12:33, Andrey Chernov a...@freebsd.org wrote: Do you check assembler output for _both_ cases? Yes. In my testing clang and gcc xor's 'junk' properly in case it have 'volatile' keyword (as in srandomdev()) and elide it without 'volatile'. volatile is still undefined: see 5.1.2.2.3 and 6.7.2.4 of ISO9899 IMHO this change should be backed out for srandomdev() and adding 'volatile' for sranddev() instead. http://blog.eitanadler.com/2012/10/reduced-entropy-in-rand-and-random.html for additional details and actual assembler output. -- Eitan Adler Source Ports committer X11, Bugbusting teams ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On 9 October 2012 13:27, m...@freebsd.org wrote: The original behavior can be recovered by using inline assembly to fetch the value from a register into a local C variable; this would at least not rely on undefined behavior. But I agree it's of dubious value anyways. I proposed this (with a patch). We want to move to not using /dev/random and instead make a kernel system call directly. The patch for this is not finished yet though. -- Eitan Adler Source Ports committer X11, Bugbusting teams ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On 9 October 2012 13:16, David Chisnall thera...@freebsd.org wrote: On 9 Oct 2012, at 17:33, Andrey Chernov wrote: Do you check assembler output for _both_ cases? In my testing clang and gcc xor's 'junk' properly in case it have 'volatile' keyword (as in srandomdev()) and elide it without 'volatile'. IMHO this change should be backed out for srandomdev() and adding 'volatile' for sranddev() instead. In it's original form, it is very dangerous - the whole expression reduces to undefined and so the LLVM IR for the call is: call void @srand(i32 undef) The back end is then free to use any value for the call argument, including any register value or 0. In fact, the backend is free to jump to a random location and potentially kill kittens. There is *no* guarantee when it comes to undefined behavior. Adding the volatile means that we are doing an XOR with a value left on the stack. If this is early on in the application, then it is most likely to be 0. If it's later on, then there may be a value here, but it's still not very likely to be something particularly unpredictable. volatile only helps by mistake because clang is overly aggressive is turning off optimizers. The code is still undefined. -- Eitan Adler Source Ports committer X11, Bugbusting teams ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On 09.10.2012 21:47, Eitan Adler wrote: On 9 October 2012 12:33, Andrey Chernov a...@freebsd.org wrote: Do you check assembler output for _both_ cases? Yes. ... http://blog.eitanadler.com/2012/10/reduced-entropy-in-rand-and-random.html At this URL I see only already known buggy assembler without 'volatile' keyword (which is fixed by adding 'volatile' in srandomdev()). As I already mention, adding 'volatile' helps any gcc and clang finally generated assembler code (checked by cc -S ...). What happens with LLVM intermediate code, I mean mentioned by David call void @srand(i32 undef) is a big question and perhaps clang bug. Please note that we use 'volatile' a lot in the kernel, just 'grep -r volatile /sys'. Some of that potentially can hit the same (probably) bug. And, in case it is the bug, it should be fixed in clang. volatile is still undefined: see 5.1.2.2.3 and 6.7.2.4 of ISO9899 I don't have ISO9899 nearby, could you directly quote mentioned sections, please? Do you against 'volatile' usage at all? It seems whole kernel (see above) contradicts with such point of view. ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On 9 October 2012 14:24, Andrey Chernov a...@freebsd.org wrote: I don't have ISO9899 nearby, could you directly quote mentioned sections, please? Accesses to volatile object (a) produce side effects (b) have implementation defined values. A more careful re-reading of the relevant section leads me to believe I may have been wrong with this comment. It isn't made explicit, but the C standard never says that accesses to uninitialized volatile is defined. On the other hand, the existence of const volatile proves me wrong. Interestingly, clang and gcc disagree on whether to warn: [8084 eitan@radar ~ ]%gcc46 -Wall -Wextra -ansi -pedantic a.c [8089 eitan@radar ~ ]%clang -Wall -Wextra -ansi -pedantic a.c a.c:3:9: warning: variable 'a' is uninitialized when used here [-Wuninitialized] I still don't like volatile though here for the other reasons mentioned. In general, the entire piece of code should be replaced with something that can't fail, so this is a moot point. Do you against 'volatile' usage at all? It seems whole kernel (see above) contradicts with such point of view. Not, I never said any such thing. Volatile is designed for memory mapped I/O and it makes sense to use for such things. I haven't audited every use of 'volatile' though. -- Eitan Adler Source Ports committer X11, Bugbusting teams ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On Tue, Oct 09, 2012 at 04:23:59PM -0400, Eitan Adler wrote: On 9 October 2012 14:24, Andrey Chernov a...@freebsd.org wrote: I don't have ISO9899 nearby, could you directly quote mentioned sections, please? Accesses to volatile object (a) produce side effects (b) have implementation defined values. A more careful re-reading of the relevant section leads me to believe I may have been wrong with this comment. It isn't made explicit, but the C standard never says that accesses to uninitialized volatile is defined. On the other hand, the existence of const volatile proves me wrong. Interestingly, clang and gcc disagree on whether to warn: [8084 eitan@radar ~ ]%gcc46 -Wall -Wextra -ansi -pedantic a.c [8089 eitan@radar ~ ]%clang -Wall -Wextra -ansi -pedantic a.c a.c:3:9: warning: variable 'a' is uninitialized when used here [-Wuninitialized] Given that I cannot see a.c, I'll assume that 'a' is declared with a volatile-qualified type. In that case, it appears that clang has a bug. From 6.7.3, page 109 in n1256.pdf, one finds: An object that has volatile-qualified type may be modified in ways unknown to the implementation or have other unknown side effects. Therefore any expression referring to such an object shall be evaluated strictly according to the rules of the abstract machine, as described in 5.1.2.3. Furthermore, at every sequence point the value last stored in the object shall agree with that prescribed by the abstract machine, except as modified by the unknown factors mentioned previously. 116) 116) A volatile declaration may be used to describe an object corresponding to a memory-mapped input/output port or an object accessed by an asynchronously interrupting function. Actions on objects so declared shall not be ``optimized out'' by an implementation or reordered except as permitted by the rules for evaluating expressions. Clang has no way of determining if 'a' is initialized or not. If David is correct that 'junk' is optimized out by clang/llvm, then it seems that clang violates footnote 116. Yes, I know it is non-normative text. I still don't like volatile though here for the other reasons mentioned. In general, the entire piece of code should be replaced with something that can't fail, so this is a moot point. Agreed. -- Steve ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On 9 October 2012 17:25, Steve Kargl s...@troutmask.apl.washington.edu wrote: ... yes, I was misreading the text. Clang has no way of determining if 'a' is initialized or not. If David is correct that 'junk' is optimized out by clang/llvm, then it seems that clang violates footnote 116. Yes, I know it is non-normative text. Sorry if I was not clear: clang does *not* optimize away the volatile version. I removed it for other reasons. I still don't like volatile though here for the other reasons mentioned. In general, the entire piece of code should be replaced with something that can't fail, so this is a moot point. Agreed. -- Steve -- Eitan Adler Source Ports committer X11, Bugbusting teams ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On 9 October 2012 18:06, Eitan Adler ead...@freebsd.org wrote: On 9 October 2012 17:25, Steve Kargl s...@troutmask.apl.washington.edu wrote: ... yes, I was misreading the text. Clang has no way of determining if 'a' is initialized or not. If David is correct that 'junk' is optimized out by clang/llvm, then it seems that clang violates footnote 116. Yes, I know it is non-normative text. Sorry if I was not clear: clang does *not* optimize away the volatile version. I removed it for other reasons. For those interested in volatile you may also want to read: www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf -- Eitan Adler Source Ports committer X11, Bugbusting teams ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org
Re: svn commit: r241373 - head/lib/libc/stdlib
On Tue, Oct 09, 2012 at 06:06:55PM -0400, Eitan Adler wrote: On 9 October 2012 17:25, Steve Kargl s...@troutmask.apl.washington.edu wrote: ... yes, I was misreading the text. Clang has no way of determining if 'a' is initialized or not. If David is correct that 'junk' is optimized out by clang/llvm, then it seems that clang violates footnote 116. Yes, I know it is non-normative text. Sorry if I was not clear: clang does *not* optimize away the volatile version. I removed it for other reasons. OK, but clang still has a bug. Clang should not issue a warning that 'a' is uninitialized because 'a' is volatile and clang has no way of knowning whether 'a' has been initialized by some other means. At most, clang can state 'a' may be uninitialized. -- Steve ___ svn-src-head@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-head To unsubscribe, send any mail to svn-src-head-unsubscr...@freebsd.org