Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #74757 > unrolled thread
| Started by | G G <gdotone@gmail.com> |
|---|---|
| First post | 2015-11-03 06:31 -0800 |
| Last post | 2015-11-20 10:43 +0000 |
| Articles | 20 on this page of 167 — 29 participants |
Back to article view | Back to comp.lang.c
Is it possible C is the security problem? G G <gdotone@gmail.com> - 2015-11-03 06:31 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 14:57 +0000
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-03 15:04 +0000
Re: Is it possible C is the security problem? G G <gdotone@gmail.com> - 2015-11-03 07:11 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 15:25 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-03 20:13 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-03 15:18 -0500
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 20:34 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-03 22:47 +0000
Re: Is it possible C is the security problem? Udyant Wig <udyantw@gmail.com> - 2015-11-04 15:36 +0530
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 10:34 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-03 15:18 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-03 17:42 -0800
Re: Is it possible C is the security problem? Geoff <geoff@invalid.invalid> - 2015-11-03 15:32 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 23:57 +0000
Re: Is it possible C is the security problem? Geoff <geoff@invalid.invalid> - 2015-11-03 21:13 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 07:22 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 11:32 +0100
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 10:54 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 13:38 +0100
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-07 08:27 +0000
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-05 09:26 +0000
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 10:03 +0000
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-05 08:53 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-06 10:04 +0000
Re: Is it possible C is the security problem? Reinhardt Behm <rbehm@hushmail.com> - 2015-11-05 21:06 +0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-05 11:14 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-05 11:44 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-07 02:43 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-07 17:30 -0800
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-10 16:35 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-10 11:52 -0500
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-11 00:48 -0600
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-17 21:55 +0000
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-17 19:14 -0600
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-18 03:40 +0000
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-17 23:01 -0600
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-18 09:00 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-18 09:09 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-18 15:35 -0600
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-18 21:35 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-18 20:38 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-19 05:40 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-18 22:55 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-19 19:56 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-18 23:40 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-19 21:05 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 06:40 -0800
Re: Is it possible C is the security problem? asetofsymbols@gmail.com - 2015-11-19 11:37 -0800
Re: Is it possible C is the security problem? asetofsymbols@gmail.com - 2015-11-19 12:09 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 12:52 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-20 12:20 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 15:34 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-22 16:43 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-21 21:28 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-22 20:51 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-22 07:26 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-22 09:42 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-22 09:59 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-23 07:08 +0000
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-23 11:57 +1300
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-22 16:06 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-23 13:26 +1300
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-19 09:09 +0000
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-20 02:29 -0800
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-20 12:33 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-20 09:26 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-19 13:37 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-19 14:07 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 01:38 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-19 18:43 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 12:09 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 01:48 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 11:16 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 05:04 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-20 18:18 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 11:55 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-21 00:27 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 18:57 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-20 19:50 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 20:06 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-20 20:46 -0800
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 20:56 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 04:58 -0600
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-21 04:59 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 13:26 -0600
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-21 14:38 -0500
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 06:49 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-20 22:56 -0800
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 04:36 -0600
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 06:44 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-21 15:59 +0000
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 18:33 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-21 19:19 +0000
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-21 13:33 -0600
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-22 14:42 +0000
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-22 14:17 -0800
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-20 14:51 +1300
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-19 08:06 -0600
Re: Is it possible C is the security problem? Robert Wessel <robertwessel2@yahoo.com> - 2015-11-18 15:40 -0600
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-20 13:57 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-21 06:56 +0000
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-23 03:16 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-23 22:28 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-23 21:11 -0800
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-24 10:29 -0800
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-25 02:38 +0000
Re: Is it possible C is the security problem? Tim Rentsch <txr@alumni.caltech.edu> - 2015-11-27 13:54 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-10 10:23 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-10 11:21 -0800
Re: Is it possible C is the security problem? Melzzzzz <mel@zzzzz.com> - 2015-11-04 00:58 +0100
Re: Is it possible C is the security problem? Les Cargill <lcargill99@comcast.com> - 2015-11-03 18:26 -0600
Re: Is it possible C is the security problem? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-11-04 02:06 +0000
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-04 14:12 +1300
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 07:02 +0000
Re: Is it possible C is the security problem? Ian Collins <ian-news@hotmail.com> - 2015-11-04 20:42 +1300
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 08:06 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 11:25 +0100
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-04 11:49 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 13:46 +0100
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-17 21:58 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-17 23:37 +0100
Re: Is it possible C is the security problem? David Thompson <dave.thompson2@verizon.net> - 2015-12-06 07:55 -0500
Re: Is it possible C is the security problem? Les Cargill <lcargill99@comcast.com> - 2015-12-06 14:23 -0600
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-03 15:59 +0000
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-03 16:55 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-04 02:29 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-04 10:48 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-04 14:11 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 00:39 +0000
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-05 01:15 +0000
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 02:02 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-04 18:31 -0800
Re: Is it possible C is the security problem? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-11-05 12:38 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-04 18:24 -0800
Re: Is it possible C is the security problem? Keith Thompson <kst-u@mib.org> - 2015-11-04 19:37 -0800
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-05 13:24 +0100
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-05 06:47 -0800
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-05 00:35 -0800
Re: Is it possible C is the security problem? Richard Heathfield <rjh@cpax.org.uk> - 2015-11-05 09:55 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-05 05:02 -0800
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-06 10:18 +0000
Re: Is it possible C is the security problem? see.my.homepage@gmail.com - 2015-11-06 05:57 -0800
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-04 08:32 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-03 15:01 +0000
Re: Is it possible C is the security problem? Bartc <bc@freeuk.com> - 2015-11-03 15:10 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-03 11:02 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-03 18:13 +0000
Re: Is it possible C is the security problem? Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-11-03 15:16 -0500
Re: Is it possible C is the security problem? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2015-11-04 09:38 +0000
Re: Is it possible C is the security problem? David Brown <david.brown@hesbynett.no> - 2015-11-04 11:38 +0100
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-03 11:58 -0500
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-03 09:13 -0800
Re: Is it possible C is the security problem? gazelle@shell.xmission.com (Kenny McCormack) - 2015-11-03 18:08 +0000
Re: Is it possible C is the security problem? Nobody <nobody@nowhere.invalid> - 2015-11-04 04:49 +0000
Re: Is it possible C is the security problem? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-11-04 02:22 -0800
Re: Is it possible C is the security problem? gazelle@shell.xmission.com (Kenny McCormack) - 2015-11-04 13:28 +0000
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-04 08:39 -0800
Re: Is it possible C is the security problem? John Bode <jfbode1029@gmail.com> - 2015-11-03 10:45 -0800
Re: Is it possible C is the security problem? supercat@casperkitty.com - 2015-11-03 11:05 -0800
Re: Is it possible C is the security problem? Les Cargill <lcargill99@comcast.com> - 2015-11-03 18:09 -0600
Is it possible C is the security problem? Chad <cdalten@gmail.com> - 2015-11-04 01:15 -0800
Re: Is it possible C is the security problem? gazelle@shell.xmission.com (Kenny McCormack) - 2015-11-04 13:31 +0000
Re: Is it possible C is the security problem? G G <gdotone@gmail.com> - 2015-11-18 10:55 -0800
Re: Is it possible C is the security problem? James Kuyper <jameskuyper@verizon.net> - 2015-11-18 14:05 -0500
Re: Is it possible C is the security problem? "D. Aaron Sawyer" <aaron@110.net> - 2015-11-18 19:47 -0500
Re: Is it possible C is the security problem? raltbos@xs4all.nl (Richard Bos) - 2015-11-20 10:43 +0000
Page 6 of 9 — ← Prev page 1 2 3 4 5 [6] 7 8 9 Next page →
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2015-11-20 13:57 -0800 |
| Message-ID | <kfnlh9s8hb2.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #76461 |
Robert Wessel <robertwessel2@yahoo.com> writes: > On Wed, 18 Nov 2015 09:00:23 -0800, Keith Thompson <kst-u@mib.org> > wrote: > >> Robert Wessel <robertwessel2@yahoo.com> writes: >> [...] >>> Bubble sort is good on almost sorted lists only when none of the out >>> of place items have to move a long way towards the front of the list >>> (assuming the sort starts at the front end). So: >>> >>> 9 1 2 3 4 5 6 7 8 >>> >>> is fine, the 9 will be moved to the end in the first pass. But: >>> >>> 2 3 4 5 6 7 8 9 1 >>> >>> is horrible, since each pass can only move the 1 back a single >>> position. >> >> There's a variant of bubble sort that reverses direction on each pass. >> (Shuttle sort?) It should deal well with that kind of data. >> >> But of course the worst case is still pretty bad. >> >> [...] > > I've usually heard it called cocktail [shaker] sort. And yes, it > improves bubble sort a bit, but insertion sort still generally > (always?) has better performance. [...] My measurements show cocktail sort (which in my undergraduate days we called a "brick and bubble" sort, but never mind that) uses slightly fewer comparisons and about half as many swaps as the version of insertion sort posted upthread. Obviously, insertion sort can do much better, because it can be written to use rotations rather than swaps, and use binary search to find each insertion point, which gives O( n log n ) compares rather than O( n**2 ) compares. But if one of the arguments is that insertion sort is trivial to code, I think that should be factored in when making comparisons of this sort (gak! no pun intended!).
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2015-11-21 06:56 +0000 |
| Message-ID | <n2p4jc$ls1$1@speranza.aioe.org> |
| In reply to | #76686 |
Tim Rentsch <txr@alumni.caltech.edu> wrote: > Robert Wessel <robertwessel2@yahoo.com> writes: (snip on sort algorithms) >> I've usually heard it called cocktail [shaker] sort. And yes, it >> improves bubble sort a bit, but insertion sort still generally >> (always?) has better performance. [...] > My measurements show cocktail sort (which in my undergraduate > days we called a "brick and bubble" sort, but never mind that) > uses slightly fewer comparisons and about half as many swaps as > the version of insertion sort posted upthread. I suspect it depends on the starting state. > Obviously, insertion sort can do much better, because it can be > written to use rotations rather than swaps, and use binary search > to find each insertion point, which gives O( n log n ) compares > rather than O( n**2 ) compares. But if one of the arguments is > that insertion sort is trivial to code, I think that should be > factored in when making comparisons of this sort (gak! no pun > intended!). There are different ways to implement insertion sort, specifically on which order you use to do the insertions. Some orders are very efficient for almost sorted data. -- glen
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2015-11-23 03:16 -0800 |
| Message-ID | <kfn37vx55kh.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #76734 |
glen herrmannsfeldt <gah@ugcs.caltech.edu> writes: > Tim Rentsch <txr@alumni.caltech.edu> wrote: >> Robert Wessel <robertwessel2@yahoo.com> writes: > > (snip on sort algorithms) > >>> I've usually heard it called cocktail [shaker] sort. And yes, it >>> improves bubble sort a bit, but insertion sort still generally >>> (always?) has better performance. [...] >> >> My measurements show cocktail sort (which in my undergraduate >> days we called a "brick and bubble" sort, but never mind that) >> uses slightly fewer comparisons and about half as many swaps as >> the version of insertion sort posted upthread. > > I suspect it depends on the starting state. Of course. The result I reported had arrays initialized with random data. >> Obviously, insertion sort can do much better, because it can be >> written to use rotations rather than swaps, and use binary search >> to find each insertion point, which gives O( n log n ) compares >> rather than O( n**2 ) compares. But if one of the arguments is >> that insertion sort is trivial to code, I think that should be >> factored in when making comparisons of this sort (gak! no pun >> intended!). > > There are different ways to implement insertion sort, specifically > on which order you use to do the insertions. Some orders are > very efficient for almost sorted data. I don't know what you're getting at by this. In my understanding of how the term "insertion sort" is used, the order of insertions is fixed and sequential through the array - a[1], a[2], a[3], and so on. It could be done starting at the high end rather than the low end - a[n-2], a[n-3], a[n-4], and so on - but that should not be essentially different in its results. Please explain further.
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2015-11-23 22:28 +0000 |
| Message-ID | <n303tq$79s$1@speranza.aioe.org> |
| In reply to | #76977 |
Tim Rentsch <txr@alumni.caltech.edu> wrote: (snip, I wrote) >> There are different ways to implement insertion sort, specifically >> on which order you use to do the insertions. Some orders are >> very efficient for almost sorted data. > I don't know what you're getting at by this. In my understanding > of how the term "insertion sort" is used, the order of insertions > is fixed and sequential through the array - a[1], a[2], a[3], and > so on. It could be done starting at the high end rather than the > low end - a[n-2], a[n-3], a[n-4], and so on - but that should not > be essentially different in its results. Please explain further. For insertion sort, you insert successive elements into a previously sorted region of the array. You can start the sort at either end (or, I suppose, somewhere in the middle) and do the insertion search starting from either end. For random data, it doesn't matter which end you start searching for the place to insert. For already sorted data, it does. -- glen
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2015-11-23 21:11 -0800 |
| Message-ID | <5bf1fcf5-72db-402b-b642-d167d095ca87@googlegroups.com> |
| In reply to | #77034 |
On Monday, November 23, 2015 at 10:28:24 PM UTC, glen herrmannsfeldt wrote: > Tim Rentsch <txr@alumni.caltech.edu> wrote: > > (snip, I wrote) > >> There are different ways to implement insertion sort, specifically > >> on which order you use to do the insertions. Some orders are > >> very efficient for almost sorted data. > > > I don't know what you're getting at by this. In my understanding > > of how the term "insertion sort" is used, the order of insertions > > is fixed and sequential through the array - a[1], a[2], a[3], and > > so on. It could be done starting at the high end rather than the > > low end - a[n-2], a[n-3], a[n-4], and so on - but that should not > > be essentially different in its results. Please explain further. > > For insertion sort, you insert successive elements into a previously > sorted region of the array. You can start the sort at either end > (or, I suppose, somewhere in the middle) and do the insertion > search starting from either end. For random data, it doesn't > matter which end you start searching for the place to insert. > For already sorted data, it does. > If we've got an array that is sorted except for one out of place element, which is in the middle (N is 11, it's at index five), then if it needs to go to the bottom we do 14 comparisons and 5 swaps / moves, if it needs to go to the top we need 14 comparisons, and 5 swaps, non-optimisable to block moves. There's a small difference. Is there another?
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2015-11-24 10:29 -0800 |
| Message-ID | <kfnlh9n2qu0.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #77034 |
glen herrmannsfeldt <gah@ugcs.caltech.edu> writes: > Tim Rentsch <txr@alumni.caltech.edu> wrote: > > (snip, I wrote) >>> There are different ways to implement insertion sort, specifically >>> on which order you use to do the insertions. Some orders are >>> very efficient for almost sorted data. >> >> I don't know what you're getting at by this. In my understanding >> of how the term "insertion sort" is used, the order of insertions >> is fixed and sequential through the array - a[1], a[2], a[3], and >> so on. It could be done starting at the high end rather than the >> low end - a[n-2], a[n-3], a[n-4], and so on - but that should not >> be essentially different in its results. Please explain further. > > For insertion sort, you insert successive elements into a previously > sorted region of the array. You can start the sort at either end > (or, I suppose, somewhere in the middle) and do the insertion > search starting from either end. For random data, it doesn't > matter which end you start searching for the place to insert. > For already sorted data, it does. I see now why I was confused. I have never seen a description of insertion sort that mentions the idea of searching starting at the fixed end rather than the moving end. I see no reason to want to do such a thing. If we want to speed up the search part of an insertion sort, binary search is better than linear search in almost all cases, and is still reasonably good in worst case situations such as sorted data. In any case the algorithm I was testing is the same as the one shown upthread, and not any variations on that.
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2015-11-25 02:38 +0000 |
| Message-ID | <n336uu$ibb$1@speranza.aioe.org> |
| In reply to | #77120 |
Tim Rentsch <txr@alumni.caltech.edu> wrote: (snip, I wrote) >> For insertion sort, you insert successive elements into a previously >> sorted region of the array. You can start the sort at either end >> (or, I suppose, somewhere in the middle) and do the insertion >> search starting from either end. For random data, it doesn't >> matter which end you start searching for the place to insert. >> For already sorted data, it does. > I see now why I was confused. I have never seen a description of > insertion sort that mentions the idea of searching starting at > the fixed end rather than the moving end. I see no reason to > want to do such a thing. I was remembering, or not remembering, the programs I wrote for CS137 many years ago. I followed Knuth, so I could just look up how he does it. > If we want to speed up the search part > of an insertion sort, binary search is better than linear search > in almost all cases, and is still reasonably good in worst case I think that counts as a different algorithm with a different name, such as binary insertion sort. > situations such as sorted data. In any case the algorithm I was > testing is the same as the one shown upthread, and not any > variations on that. -- glen
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2015-11-27 13:54 -0800 |
| Message-ID | <kfnfuzryup2.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #77144 |
glen herrmannsfeldt <gah@ugcs.caltech.edu> writes: > Tim Rentsch <txr@alumni.caltech.edu> wrote: > > (snip, I wrote) >>> For insertion sort, you insert successive elements into a previously >>> sorted region of the array. You can start the sort at either end >>> (or, I suppose, somewhere in the middle) and do the insertion >>> search starting from either end. For random data, it doesn't >>> matter which end you start searching for the place to insert. >>> For already sorted data, it does. >> >> I see now why I was confused. I have never seen a description of >> insertion sort that mentions the idea of searching starting at >> the fixed end rather than the moving end. I see no reason to >> want to do such a thing. > > I was remembering, or not remembering, the programs I wrote > for CS137 many years ago. I followed Knuth, so I could just > look up how he does it. The insertion sort given in Knuth starts at the low end and inserts into the moving edge. He briefly mentions a variation of starting in the middle and moving out both edges, but doesn't dwell on it. >> If we want to speed up the search part >> of an insertion sort, binary search is better than linear search >> in almost all cases, and is still reasonably good in worst case > > I think that counts as a different algorithm with a > different name, such as binary insertion sort. Using a binary search is such an obvious improvement that it hardly seems deserving of a different name, except perhaps to distinguish it from an ordinary "dumb" insertion sort. The binary search technique was described in early writings about the insertion sorting method, dating back to the 1940's.
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2015-11-10 10:23 -0800 |
| Message-ID | <8f223bc8-1e77-44c8-ba2e-c18f8950fc8e@googlegroups.com> |
| In reply to | #75602 |
On Tuesday, November 10, 2015 at 10:36:09 AM UTC-6, Richard Bos wrote: > Part of the problem is that there are edge cases - demonstrating the > differences between sorting algorithms, for one - where you _want_ > bubble sort rather than quicksort. In security code, it may well be > important that all paths through an algorithm be a. optimised, but also > b. optimised to use the exact same time. I'm not sure when optimizers changed from trying to identify the best code to perform the indicated operations, from trying to produce a higher-level description of what the code does in defined cases and then produce the best code to accomplish that, but I don't think that approach has ever been a really good fit for C. It's all well and good to try to have a language that can automatically generate code to sort N things, but that should be accomplished by having it define a way to say "Sort these N things", rather than by having a programmer write code which is illustrative of what is supposed to happen and having the compiler say "Ah, the programmer wants these N things sorted", and then generate code to perform the sort.
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2015-11-10 11:21 -0800 |
| Message-ID | <lnbnb1u0c2.fsf@kst-u.example.com> |
| In reply to | #75647 |
supercat@casperkitty.com writes:
> On Tuesday, November 10, 2015 at 10:36:09 AM UTC-6, Richard Bos wrote:
>> Part of the problem is that there are edge cases - demonstrating the
>> differences between sorting algorithms, for one - where you _want_
>> bubble sort rather than quicksort. In security code, it may well be
>> important that all paths through an algorithm be a. optimised, but also
>> b. optimised to use the exact same time.
>
> I'm not sure when optimizers changed from trying to identify the best code
> to perform the indicated operations, from trying to produce a higher-level
> description of what the code does in defined cases and then produce the best
> code to accomplish that, but I don't think that approach has ever been a
> really good fit for C. It's all well and good to try to have a language
> that can automatically generate code to sort N things, but that should be
> accomplished by having it define a way to say "Sort these N things", rather
> than by having a programmer write code which is illustrative of what is
> supposed to happen and having the compiler say "Ah, the programmer wants
> these N things sorted", and then generate code to perform the sort.
Your remarks appear to assume that optimizers will actually transform a
bubble sort to a quicksort. I don't believe that's the case. (And the
circumstances in which an optimizer could even theoretically do that are
limited, since the behavior is different, particularly in the way items
with equal keys are treated.)
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | Melzzzzz <mel@zzzzz.com> |
|---|---|
| Date | 2015-11-04 00:58 +0100 |
| Message-ID | <20151104005817.5c507890@maxa-pc> |
| In reply to | #74782 |
On Tue, 03 Nov 2015 15:32:34 -0800 Geoff <geoff@invalid.invalid> wrote: > > The C language: > 0. malloc doesn't zero-fill. Bad idea. There is calloc. > 1. memcpy doesn't automatically bounds-check. Good thing. One can always bounds check before issuing memcpy. > 2. The standard library sucks when it comes to secure code. > ?
[toc] | [prev] | [next] | [standalone]
| From | Les Cargill <lcargill99@comcast.com> |
|---|---|
| Date | 2015-11-03 18:26 -0600 |
| Message-ID | <n1bivv$gqs$1@dont-email.me> |
| In reply to | #74782 |
Geoff wrote: > On Tue, 03 Nov 2015 20:13:35 +0000, Ben Bacarisse > <ben.usenet@bsb.me.uk> wrote: > >> Richard Heathfield <rjh@cpax.org.uk> writes: >> >>> On 03/11/15 15:11, G G wrote: >>> >>> <snip> >>> >>>> I wonder as the language gets better, well, changes, I know better >>>> maybe too subjective, if the code of yesteryear should be re thought >>>> and then written using today's C standard. >>> >>> It wouldn't make things any more secure than they are now. >>> >>>> Yes, I see your point, it boils down to the programmer. >>> >>> Take Heartbleed as an example. >>> >>> This is an example of a new vulnerability that was introduced (in >>> 2012, I think?) into previously secure (well, as far as we know) code. >>> >>> The idea of Heartbeat was to allow TLS/DTLS to keep a connection alive >>> by sending occasional "heartbeat" packets. Alice sends Bob some data, >>> Bob sends it back, and thus Alice and Bob prove to each other that >>> they are still alive. How much data? Alice tells Bob this, and *Bob >>> believes her*! And that was how the Heartbleed exploit was made >>> possible: all Alice has to do is tell a little lie to Bob, and Bob >>> will send her absolutely shedloads of data in the belief that she had >>> already sent it to him and therefore there couldn't be any security >>> risk, right? >>> >>> So Bob does, say, some private key finagling, and then Alice sends in >>> a heartbeat: "Bob, my heartbeat is DOG, that's 64KB", she says with a >>> straight face. And Bob sends her 64KB of, for example, private keys. >>> >>> You won't fix this by fixing the language. >> >> This struck me as an extraordinary claim, but then I calmed down and >> thought about it bit more! I think your reply comes from a position of >> conflating the error with the consequences. Yes, programmers will >> always make mistakes, and the mistake that was made in this case was a >> simple failure to check a bound. That could happen in any programming >> language, but the actual harm was done because of a >> >> memcpy(bp, pl, payload); >> >> a few lines later. The incoming request (pointed to by pl), and the >> outgoing reply (pointed to by bp) are treated as un-typed byte arrays, >> and data is copied from one to the other with no regard to the sizes or >> types of the source objects. >> >> There are many programming languages in which the error (the missing >> test) would just be a relatively harmless logic bug because there would >> be no way for a reckless request to a copy of data from one buffer to >> another to actually succeed. >> >>> You fix this by fixing the >>> programmer - or, at the very least, by having white-hats sit in on >>> code reviews. >> >> I'm not sure we know how to fix programmers. > > There were several failures (it always takes more than one to make a > disaster) but they weren't all human errors. > > Human: > 0. Writing the OpenSSL in C and not in C++. Disagree. C++ is absolutely no more secure than 'C'. Id may have made sense for other reasons, but that's not what's being said here. > 1. Failure to write safe code. > 2. Failure to test. > 3. Failure to zero out buffers before use. > 4. Failure to review & critique. > 5. Adoption of the protocol before 2 & 3. > > The C language: > 0. malloc doesn't zero-fill. Still human. Call memset(). > 1. memcpy doesn't automatically bounds-check. Use memmove() at least and check your parameters. To an extent, it's *unreasonable* to expect a library routine to do everything for you. > 2. The standard library sucks when it comes to secure code. > It is entirely possible to use even ANSI 'C' standard library completely securely. > It's easy to write "bad C" because so much of the standard library is > bad C. It carries a legacy of standards of practice that were > instantiated when it was assumed that "everybody plays by the rules". > This is why it's possible to double-free, dereference after free, fail > to zero terminate, fail to check error returns, error returns occur > in-band and often interfere with "good C practices". > -- Les Cargill
[toc] | [prev] | [next] | [standalone]
| From | glen herrmannsfeldt <gah@ugcs.caltech.edu> |
|---|---|
| Date | 2015-11-04 02:06 +0000 |
| Message-ID | <n1bp74$50a$1@speranza.aioe.org> |
| In reply to | #74782 |
Geoff <geoff@invalid.invalid> wrote: > On Tue, 03 Nov 2015 20:13:35 +0000, Ben Bacarisse (snip) >>This struck me as an extraordinary claim, but then I calmed down and >>thought about it bit more! I think your reply comes from a position of >>conflating the error with the consequences. Yes, programmers will >>always make mistakes, and the mistake that was made in this case was a >>simple failure to check a bound. That could happen in any programming >>language, but the actual harm was done because of a >> memcpy(bp, pl, payload); >>a few lines later. The incoming request (pointed to by pl), and the >>outgoing reply (pointed to by bp) are treated as un-typed byte arrays, >>and data is copied from one to the other with no regard to the sizes or >>types of the source objects. >>There are many programming languages in which the error (the missing >>test) would just be a relatively harmless logic bug because there would >>be no way for a reckless request to a copy of data from one buffer to >>another to actually succeed. PL/I, which came out a little earlier than C, and was likely known to the C originators, by default does bounds-check on strings. PL/I allows one to turn on and off, by statement or by block, string bounds checking and array bounds checking. (Separately.) (The defaults might be sysgen options, and some installations might change them.) Matching Fortran at the time, array bounds checking is usually off by default. (snip) > The C language: > 0. malloc doesn't zero-fill. > 1. memcpy doesn't automatically bounds-check. > 2. The standard library sucks when it comes to secure code. > It's easy to write "bad C" because so much of the standard library is > bad C. It carries a legacy of standards of practice that were > instantiated when it was assumed that "everybody plays by the rules". > This is why it's possible to double-free, dereference after free, fail > to zero terminate, fail to check error returns, error returns occur > in-band and often interfere with "good C practices". One doesn't have to use the standard library. People could write their own string handling routines that were better, but that is rare. -- glen
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-11-04 14:12 +1300 |
| Message-ID | <d9t4c9Fs0krU1@mid.individual.net> |
| In reply to | #74776 |
Ben Bacarisse wrote: > > I'm not sure we know how to fix programmers. Testers! -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-11-04 07:02 +0000 |
| Message-ID | <n1caee$7k1$1@dont-email.me> |
| In reply to | #74787 |
On 04/11/15 01:12, Ian Collins wrote: > Ben Bacarisse wrote: >> >> I'm not sure we know how to fix programmers. > > Testers! And how do we fix testers? Testers didn't spot the Heartbleed bug. -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2015-11-04 20:42 +1300 |
| Message-ID | <d9tr7dFs0krU3@mid.individual.net> |
| In reply to | #74799 |
Richard Heathfield wrote: > On 04/11/15 01:12, Ian Collins wrote: >> Ben Bacarisse wrote: >>> >>> I'm not sure we know how to fix programmers. >> >> Testers! > > And how do we fix testers? > > Testers didn't spot the Heartbleed bug. I was thinking of most of the professional testers I have worked with (which includes an ex-soviet rocket scientist!). They think differently from developers and test the stuff we don't think of. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Richard Heathfield <rjh@cpax.org.uk> |
|---|---|
| Date | 2015-11-04 08:06 +0000 |
| Message-ID | <n1ce5q$ij2$1@dont-email.me> |
| In reply to | #74803 |
On 04/11/15 07:42, Ian Collins wrote: > Richard Heathfield wrote: >> On 04/11/15 01:12, Ian Collins wrote: >>> Ben Bacarisse wrote: >>>> >>>> I'm not sure we know how to fix programmers. >>> >>> Testers! >> >> And how do we fix testers? >> >> Testers didn't spot the Heartbleed bug. > > I was thinking of most of the professional testers I have worked with > (which includes an ex-soviet rocket scientist!). So was I, actually. And they /still/ didn't spot it. > They think differently > from developers and test the stuff we don't think of. They do, but there are two problems with them, which I think I can combine in such a way as to make the whole thing All Their Fault. Here we go. If testers are not perfect, then they're not good enough at their job, so it's clearly all their fault. But if they *are* perfect, then the fact that such problems still hit production code indicates that testers are not capable of breeding in sufficient numbers to meet the demand, which means it's still their fault. We can now relax and get on with programming more vulnerabilities into our code, safe in the knowledge that we can't be blamed for them. All right - seriously, yes, you're right, professional testers are a right royal PITN[1], which is good because it means they're doing their job properly. But testing is a very different skill from developing code, and in far too many places testing is done by people who have a vested interest in *not* finding problems. [1] The better of them try not to be, but it doesn't really work. Thorough testing is a necessarily intrusive activity. -- Richard Heathfield Email: rjh at cpax dot org dot uk "Usenet is a strange place" - dmr 29 July 1999 Sig line 4 vacant - apply within
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2015-11-04 11:25 +0100 |
| Message-ID | <n1cm9q$e1m$1@dont-email.me> |
| In reply to | #74776 |
On 03/11/15 21:13, Ben Bacarisse wrote: > Richard Heathfield <rjh@cpax.org.uk> writes: > >> On 03/11/15 15:11, G G wrote: >> >> <snip> >> >>> I wonder as the language gets better, well, changes, I know better >>> maybe too subjective, if the code of yesteryear should be re thought >>> and then written using today's C standard. >> >> It wouldn't make things any more secure than they are now. >> >>> Yes, I see your point, it boils down to the programmer. >> >> Take Heartbleed as an example. >> >> This is an example of a new vulnerability that was introduced (in >> 2012, I think?) into previously secure (well, as far as we know) code. >> >> The idea of Heartbeat was to allow TLS/DTLS to keep a connection alive >> by sending occasional "heartbeat" packets. Alice sends Bob some data, >> Bob sends it back, and thus Alice and Bob prove to each other that >> they are still alive. How much data? Alice tells Bob this, and *Bob >> believes her*! And that was how the Heartbleed exploit was made >> possible: all Alice has to do is tell a little lie to Bob, and Bob >> will send her absolutely shedloads of data in the belief that she had >> already sent it to him and therefore there couldn't be any security >> risk, right? >> >> So Bob does, say, some private key finagling, and then Alice sends in >> a heartbeat: "Bob, my heartbeat is DOG, that's 64KB", she says with a >> straight face. And Bob sends her 64KB of, for example, private keys. >> >> You won't fix this by fixing the language. > > This struck me as an extraordinary claim, but then I calmed down and > thought about it bit more! I think your reply comes from a position of > conflating the error with the consequences. Yes, programmers will > always make mistakes, and the mistake that was made in this case was a > simple failure to check a bound. That could happen in any programming > language, but the actual harm was done because of a > > memcpy(bp, pl, payload); > > a few lines later. The incoming request (pointed to by pl), and the > outgoing reply (pointed to by bp) are treated as un-typed byte arrays, > and data is copied from one to the other with no regard to the sizes or > types of the source objects. > That was not the problem in Heartbleed. The problem was that the code blindly trusted data from an outside source - the "length" field in the incoming packet. For any sort of secure coding, you simply don't do that. It was not a problem caused by buffer overflows, or untyped byte arrays - it was a problem caused by the developers being careless. No programming language will fix this. "Fixing" the programmers will seldom fix it either - it is the apparatus /around/ the actual coding that needs fixed. The TLS library programmers were a small group, with little or no funding, working away by themselves without review or outside checks or controls. So the way to avoid such problems (IMHO) is to give the people behind such important software an appropriate level of support. Pay them for the work, so that they can do it full-time and not just as a hobby. Pay others to check the code. Pay for computers powerful enough for massive testing. Pay for someone to document the code, and someone to manage the project. Pay for the /boring/ stuff that rarely receives the care needed when code is written voluntarily. A great many people make money from software or services that depend critically on the code behind Heartbleed - they often contribute money, people and resources to all sorts of open source software, but they need to be a good deal better at making sure they also support these quite yet critical projects as a well as the big and visible ones. > There are many programming languages in which the error (the missing > test) would just be a relatively harmless logic bug because there would > be no way for a reckless request to a copy of data from one buffer to > another to actually succeed. > Different programming languages can make it /easier/ to write secure code, as can different programming styles and idioms. Heavy use of "unique_ptr" and "shared_ptr" in C++ makes it much less likely that you will have leaked memory or use-after-free than using "malloc" and "free" in C. But simply having those programming language features does not make code written in C++ leak-free - you still have to work at it. (I've written leaky code in Python, despite its garbage collection.) >> You fix this by fixing the >> programmer - or, at the very least, by having white-hats sit in on >> code reviews. > > I'm not sure we know how to fix programmers. >
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2015-11-04 11:49 +0000 |
| Message-ID | <87vb9i2de1.fsf@bsb.me.uk> |
| In reply to | #74813 |
David Brown <david.brown@hesbynett.no> writes: > On 03/11/15 21:13, Ben Bacarisse wrote: >> Richard Heathfield <rjh@cpax.org.uk> writes: >> >>> On 03/11/15 15:11, G G wrote: >>> >>> <snip> >>> >>>> I wonder as the language gets better, well, changes, I know better >>>> maybe too subjective, if the code of yesteryear should be re thought >>>> and then written using today's C standard. >>> >>> It wouldn't make things any more secure than they are now. >>> >>>> Yes, I see your point, it boils down to the programmer. >>> >>> Take Heartbleed as an example. >>> >>> This is an example of a new vulnerability that was introduced (in >>> 2012, I think?) into previously secure (well, as far as we know) code. >>> >>> The idea of Heartbeat was to allow TLS/DTLS to keep a connection alive >>> by sending occasional "heartbeat" packets. Alice sends Bob some data, >>> Bob sends it back, and thus Alice and Bob prove to each other that >>> they are still alive. How much data? Alice tells Bob this, and *Bob >>> believes her*! And that was how the Heartbleed exploit was made >>> possible: all Alice has to do is tell a little lie to Bob, and Bob >>> will send her absolutely shedloads of data in the belief that she had >>> already sent it to him and therefore there couldn't be any security >>> risk, right? >>> >>> So Bob does, say, some private key finagling, and then Alice sends in >>> a heartbeat: "Bob, my heartbeat is DOG, that's 64KB", she says with a >>> straight face. And Bob sends her 64KB of, for example, private keys. >>> >>> You won't fix this by fixing the language. >> >> This struck me as an extraordinary claim, but then I calmed down and >> thought about it bit more! I think your reply comes from a position of >> conflating the error with the consequences. Yes, programmers will >> always make mistakes, and the mistake that was made in this case was a >> simple failure to check a bound. That could happen in any programming >> language, but the actual harm was done because of a >> >> memcpy(bp, pl, payload); >> >> a few lines later. The incoming request (pointed to by pl), and the >> outgoing reply (pointed to by bp) are treated as un-typed byte arrays, >> and data is copied from one to the other with no regard to the sizes or >> types of the source objects. >> > > That was not the problem in Heartbleed. The problem was that the code > blindly trusted data from an outside source - the "length" field in > the incoming packet. For any sort of secure coding, you simply don't > do that. It was not a problem caused by buffer overflows, or untyped > byte arrays - it was a problem caused by the developers being > careless. Of course it was blindly trusting data -- the error was not to check the value of 'payload' -- but the harm was done by the memcpy. That copy was able to copy data that followed the message buffer -- either outside of it altogether, of data that just happened to be lying around from some other use (I think it was the former, but I'm not sure). If all it could do was copy some or all of the buffer it could send back nothing that was not already know to the sender. In some languages this bug could have been just a logic bug. Maybe it would show up in the logs. Maybe it would cause the server to crash -- bad news for sure, but no need to change everyone's keys! > No programming language will fix this. But it might prevent the harm. If the memcpy had been a 'substring' operation on a bounded string, the request to extract more than was there would simply have stopped at the boundary set when the message was received. > "Fixing" the programmers will > seldom fix it either - it is the apparatus /around/ the actual coding > that needs fixed. The TLS library programmers were a small group, > with little or no funding, working away by themselves without review > or outside checks or controls. > > So the way to avoid such problems (IMHO) is to give the people behind > such important software an appropriate level of support. Pay them for > the work, so that they can do it full-time and not just as a hobby. > Pay others to check the code. Pay for computers powerful enough for > massive testing. Pay for someone to document the code, and someone to > manage the project. Pay for the /boring/ stuff that rarely receives > the care needed when code is written voluntarily. A great many people > make money from software or services that depend critically on the > code behind Heartbleed - they often contribute money, people and > resources to all sorts of open source software, but they need to be a > good deal better at making sure they also support these quite yet > critical projects as a well as the big and visible ones. These are all good points, and I don't want to give the impression that I think changing languages is the right (let alone only) solution. In fact it may not be possible for many reasons both technical and social. But there are cases where C is used because people think they should use C, not because it is the best technical solution for the problem, and in those cases the programmer is taking on a greater responsibility for the safety of the end result than they need to. The correctness of the program is always the programmer's responsibility, but the harm caused by programming errors is shared with the language and the run-time environment. (As it happens, I think that some languages can help with getting the program logic right in the first place, but that's another issue not related to the bug being discussed here.) <snip> -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2015-11-04 13:46 +0100 |
| Message-ID | <n1cuio$bu8$1@dont-email.me> |
| In reply to | #74826 |
On 04/11/15 12:49, Ben Bacarisse wrote: > David Brown <david.brown@hesbynett.no> writes: > >> On 03/11/15 21:13, Ben Bacarisse wrote: >>> Richard Heathfield <rjh@cpax.org.uk> writes: >>> <snip> >> No programming language will fix this. > > But it might prevent the harm. If the memcpy had been a 'substring' > operation on a bounded string, the request to extract more than was > there would simply have stopped at the boundary set when the message was > received. Fair enough. I fully agree that many languages can make it easier to safe code (or harder to write unsafe code), and perhaps other languages (or other C libraries) would have reduced the effects of such errors. > >> "Fixing" the programmers will >> seldom fix it either - it is the apparatus /around/ the actual coding >> that needs fixed. The TLS library programmers were a small group, >> with little or no funding, working away by themselves without review >> or outside checks or controls. >> >> So the way to avoid such problems (IMHO) is to give the people behind >> such important software an appropriate level of support. Pay them for >> the work, so that they can do it full-time and not just as a hobby. >> Pay others to check the code. Pay for computers powerful enough for >> massive testing. Pay for someone to document the code, and someone to >> manage the project. Pay for the /boring/ stuff that rarely receives >> the care needed when code is written voluntarily. A great many people >> make money from software or services that depend critically on the >> code behind Heartbleed - they often contribute money, people and >> resources to all sorts of open source software, but they need to be a >> good deal better at making sure they also support these quite yet >> critical projects as a well as the big and visible ones. > > These are all good points, and I don't want to give the impression that > I think changing languages is the right (let alone only) solution. In > fact it may not be possible for many reasons both technical and social. Yes. > But there are cases where C is used because people think they should use > C, not because it is the best technical solution for the problem, and in > those cases the programmer is taking on a greater responsibility for the > safety of the end result than they need to. The correctness of the > program is always the programmer's responsibility, but the harm caused > by programming errors is shared with the language and the run-time > environment. Agreed. I see many questions in this group about how to handle a particular problem in C, and think that rather than writing 100 lines of C, you could do it in three or four lines of Python, and it would probably run faster too (since Python's libraries are written in very fast C). The C language has its uses - I use it every day - but often it is not the best choice for the job. > > (As it happens, I think that some languages can help with getting the > program logic right in the first place, but that's another issue not > related to the bug being discussed here.) >
[toc] | [prev] | [next] | [standalone]
Page 6 of 9 — ← Prev page 1 2 3 4 5 [6] 7 8 9 Next page →
Back to top | Article view | comp.lang.c
csiph-web