Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #3254 > unrolled thread
| Started by | boltar2003@boltar.world |
|---|---|
| First post | 2011-05-05 09:37 +0000 |
| Last post | 2011-05-11 03:43 -0700 |
| Articles | 20 on this page of 241 — 42 participants |
Back to article view | Back to comp.lang.c
Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-05 09:37 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? China Blue Veins <chine.bleu@yahoo.com> - 2011-05-05 02:51 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-05 09:58 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? China Blue Veins <chine.bleu@yahoo.com> - 2011-05-05 04:47 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-07 23:22 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-05 11:58 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-06 03:27 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-06 00:03 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-06 09:18 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-06 02:56 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-05 12:24 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Lowell Gilbert <lgusenet@be-well.ilk.org> - 2011-05-05 15:40 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 02:18 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-05 21:17 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Datesfat Chicks <datesfat.chicks@gmail.com> - 2011-05-05 18:45 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 02:44 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-06 09:58 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Richard Kettlewell <rjk@greenend.org.uk> - 2011-05-06 11:11 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-06 10:16 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Richard Kettlewell <rjk@greenend.org.uk> - 2011-05-06 11:28 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 02:34 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-06 15:09 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-07 13:03 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-07 09:01 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-07 14:32 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-07 16:27 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-07 16:43 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-05-08 06:19 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-08 17:18 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-08 09:58 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-09 11:34 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-05-11 03:48 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-11 10:51 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-11 08:11 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-11 15:47 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-05-12 15:05 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-07 16:23 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-07 18:12 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 10:30 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-07 20:01 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 12:37 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-07 18:15 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-08 15:26 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 09:32 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-08 10:46 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 21:49 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 09:59 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-07 20:24 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-07 15:04 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 15:15 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-07 19:57 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-07 20:26 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-07 21:06 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-07 23:27 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-05 20:07 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-06 02:53 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "io_x" <a@b.c.invalid> - 2011-05-08 19:27 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Tim Rentsch <txr@alumni.caltech.edu> - 2011-05-18 19:54 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-06 10:07 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 02:58 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-06 07:08 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 08:18 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Marco Parrone <marco@marcoparrone.com> - 2011-05-06 17:32 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 08:51 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-06 21:46 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 00:28 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-07 09:01 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 06:35 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-07 22:52 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-08 01:26 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-08 09:37 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-08 03:21 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Willem <willem@toad.stack.nl> - 2011-05-08 10:44 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-08 07:23 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-09 11:30 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-09 13:36 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-09 07:08 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 07:38 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 07:44 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-09 21:44 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-09 13:59 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-09 14:19 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-09 15:05 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 10:20 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-14 19:04 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-14 11:13 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-09 15:40 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-09 23:44 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 11:06 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-10 00:11 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 11:17 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-10 07:10 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-10 12:24 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? ImpalerCore <jadill33@gmail.com> - 2011-05-10 13:43 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-11 08:48 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-11 08:54 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? ImpalerCore <jadill33@gmail.com> - 2011-05-12 05:56 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-11 00:44 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-10 19:36 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-10 23:21 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-11 07:08 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-11 11:48 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-11 10:03 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-11 10:12 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-11 21:23 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-12 09:45 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-11 08:00 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-11 19:35 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-12 06:51 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-12 14:36 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-12 22:57 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-11 11:47 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-11 08:07 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-10 21:16 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-11 02:40 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-11 09:39 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-11 19:42 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-15 00:23 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? pacman@kosh.dhis.org (Alan Curry) - 2011-05-14 22:30 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-16 04:19 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-16 08:40 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-16 17:53 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-16 21:39 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-17 09:12 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-17 10:20 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-17 15:00 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? pacman@kosh.dhis.org (Alan Curry) - 2011-05-17 20:28 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-17 14:45 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-17 14:51 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-17 16:23 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-17 23:06 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-18 01:02 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-18 01:29 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-18 04:03 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ben Pfaff <blp@cs.stanford.edu> - 2011-05-17 16:47 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-17 17:21 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-23 21:57 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-23 21:57 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-23 17:45 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-24 11:43 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-24 10:58 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Sherm Pendley <sherm.pendley@gmail.com> - 2011-05-11 11:11 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-11 19:48 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-09 16:22 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-09 21:25 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Seebs <usenet-nospam@seebs.net> - 2011-05-10 17:28 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-09 17:11 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 12:20 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-10 03:53 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-10 20:18 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-10 04:42 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-10 09:12 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-10 03:21 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-10 10:53 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-10 08:12 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? pete <pfiland@mindspring.com> - 2011-05-10 09:39 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-10 12:51 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Ian Collins <ian-news@hotmail.com> - 2011-05-11 08:12 +1200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-10 15:16 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-10 19:43 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-11 07:41 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-11 19:51 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-11 12:45 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-10 07:50 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-10 11:04 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-08 09:27 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-08 08:04 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-08 22:50 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-09 00:18 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-08 19:49 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-08 20:05 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-08 13:44 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-09 00:22 -0700
Re: Avoiding recursive stack overflow in C? Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-15 17:05 +0100
Re: Avoiding recursive stack overflow in C? James Kuyper <jameskuyper@verizon.net> - 2011-05-15 14:07 -0400
Re: Avoiding recursive stack overflow in C? Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-15 22:49 +0100
Re: Avoiding recursive stack overflow in C? James Kuyper <jameskuyper@verizon.net> - 2011-05-15 21:08 -0400
Re: Avoiding recursive stack overflow in C? Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-05-16 11:10 +0100
Re: Avoiding recursive stack overflow in C? Ilya Zakharevich <nospam-abuse@ilyaz.org> - 2011-05-16 08:04 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2011-05-07 19:11 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? "io_x" <a@b.c.invalid> - 2011-05-08 07:17 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Niklas Holsti <niklas.holsti@tidorum.invalid> - 2011-05-08 10:16 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? "io_x" <a@b.c.invalid> - 2011-05-09 09:03 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-06 08:59 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 03:01 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-06 07:13 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-06 09:02 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-06 15:41 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 02:53 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? boltar2003@boltar.world - 2011-05-07 16:17 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 10:08 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-07 20:20 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 14:26 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-05-07 14:31 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 22:49 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-07 17:22 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 10:24 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-07 17:32 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 11:43 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-08 10:57 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-08 08:09 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-08 19:41 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Shao Miller <sha0.miller@gmail.com> - 2011-05-07 21:35 -0500
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-08 23:31 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-09 00:26 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-09 08:39 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-05-09 09:03 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-09 10:06 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? James Kuyper <jameskuyper@verizon.net> - 2011-05-09 17:52 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Herbert Rosenau" <os2guy@pc-rosenau.de> - 2011-05-10 11:20 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-08 17:59 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Xavier Roche <xroche@free.fr.NOSPAM.invalid> - 2011-05-09 09:01 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-07 20:41 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-07 12:48 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-08 11:01 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? gazelle@shell.xmission.com (Kenny McCormack) - 2011-05-08 13:10 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-08 19:51 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-08 22:21 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? gazelle@shell.xmission.com (Kenny McCormack) - 2011-06-04 12:54 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-06-04 12:59 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? ImpalerCore <jadill33@gmail.com> - 2011-06-07 06:30 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Michael Press <rubrum@pacbell.net> - 2011-06-10 21:56 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-05-07 13:53 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-07 15:16 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-07 23:42 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Keith Thompson <kst-u@mib.org> - 2011-05-07 19:37 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? "io_x" <a@b.c.invalid> - 2011-05-08 07:17 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? "io_x" <a@b.c.invalid> - 2011-05-08 09:24 +0200
Re: Avoiding recursive stack overflow in C on Unix/Linux? Måns Rullgård <mans@mansr.com> - 2011-05-08 10:36 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-14 13:29 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-08 00:28 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? William Ahern <william@wilbur.25thandClement.com> - 2011-05-07 23:06 -0700
Re: Avoiding recursive stack overflow in C on Unix/Linux? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-08 07:30 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-08 15:51 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-05-14 13:33 +0300
Re: Avoiding recursive stack overflow in C on Unix/Linux? Barry Margolin <barmar@alum.mit.edu> - 2011-05-14 11:08 -0400
Re: Avoiding recursive stack overflow in C on Unix/Linux? scott@slp53.sl.home (Scott Lurndal) - 2011-05-14 15:53 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-10 22:14 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Casper H.S. Dik <Casper.Dik@OrSPaMcle.COM> - 2011-05-08 11:08 +0000
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nobody <nobody@nowhere.com> - 2011-05-08 08:15 +0100
Re: Avoiding recursive stack overflow in C on Unix/Linux? Nick Keighley <nick_keighley_nospam@hotmail.com> - 2011-05-11 03:43 -0700
Page 7 of 13 — ← Prev page 1 … 5 6 [7] 8 9 … 13 Next page →
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2011-05-16 08:40 -0700 |
| Message-ID | <lnmximfyca.fsf@nuthaus.mib.org> |
| In reply to | #4042 |
Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:
> pacman@kosh.dhis.org (Alan Curry) writes:
>> In article <87r581ugbe.fsf@bazspaz.fatphil.org>,
>> Phil Carmody <thefatphil_demunged@yahoo.co.uk> wrote:
>> >
>> >And getting to the root of things, since when has "a worst-case
>> >O(n^2) algorithm may, in worst case, take O(n^2) operations" been
>> >a security hole. Citations, rather than flim-flam, would be nice.
>>
>> You must be sure that hostile input can't turn the worst case into the
>> average.
>
> I'm aware of sentences that make sense, and that one doesn't.
> I would say "try again", but I would't mean it.
It seemed clear enough to me, though perhaps a bit awkwardly phrased.
Quicksort is O(n log n) in the average case, O(N^2) in the worst
case. But that "average case" assumes random input. If Quicksort
is running in an environment where an attacker can feed it carefully
crafted input, its average case can become O(N^2), where the averate
is computed over the set of inputs it actually receives. This can
be used as a denial-of=service attack, which can, in some cases,
constitute a security hole.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2011-05-16 17:53 +0100 |
| Message-ID | <0.87a5c50b680ce02d158c.20110516175320BST.87zkmmvb7j.fsf@bsb.me.uk> |
| In reply to | #4078 |
Keith Thompson <kst-u@mib.org> writes: > Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes: >> pacman@kosh.dhis.org (Alan Curry) writes: >>> In article <87r581ugbe.fsf@bazspaz.fatphil.org>, >>> Phil Carmody <thefatphil_demunged@yahoo.co.uk> wrote: >>> > >>> >And getting to the root of things, since when has "a worst-case >>> >O(n^2) algorithm may, in worst case, take O(n^2) operations" been >>> >a security hole. Citations, rather than flim-flam, would be nice. >>> >>> You must be sure that hostile input can't turn the worst case into the >>> average. >> >> I'm aware of sentences that make sense, and that one doesn't. >> I would say "try again", but I would't mean it. > > It seemed clear enough to me, though perhaps a bit awkwardly phrased. > > Quicksort is O(n log n) in the average case, O(N^2) in the worst > case. But that "average case" assumes random input. If Quicksort > is running in an environment where an attacker can feed it carefully > crafted input, its average case can become O(N^2), where the averate > is computed over the set of inputs it actually receives. This can > be used as a denial-of=service attack, which can, in some cases, > constitute a security hole. This, too, seems awkward to me and it perpetuates a misunderstanding about Big O -- it's not a lower bound, only an upper bound. Carefully crafted input can't make quicksort become O(n^2) because it already is. It's also O(n^3). The simplest fix is just to say that it is "no longer O(n log n)" when the cost is taken over all these "bad" inputs. Picking a new, higher, upper bound does not help express the meaning. In day-to-day chat, O(f) has acquired a meaning much more like Theta(f) but, just as you don't like "implicit casts" it seems to me nonsensical to use it in this loose way. If you translate to a literal bound you can see how odd it sounds: "my sort takes less than a minute to run on average, but with malicious input it can be made to take less than a year". -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Barry Margolin <barmar@alum.mit.edu> |
|---|---|
| Date | 2011-05-16 21:39 -0400 |
| Message-ID | <barmar-91C45E.21395016052011@news.eternal-september.org> |
| In reply to | #4078 |
In article <lnmximfyca.fsf@nuthaus.mib.org>, Keith Thompson <kst-u@mib.org> wrote: > Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes: > > pacman@kosh.dhis.org (Alan Curry) writes: > >> In article <87r581ugbe.fsf@bazspaz.fatphil.org>, > >> Phil Carmody <thefatphil_demunged@yahoo.co.uk> wrote: > >> > > >> >And getting to the root of things, since when has "a worst-case > >> >O(n^2) algorithm may, in worst case, take O(n^2) operations" been > >> >a security hole. Citations, rather than flim-flam, would be nice. > >> > >> You must be sure that hostile input can't turn the worst case into the > >> average. > > > > I'm aware of sentences that make sense, and that one doesn't. > > I would say "try again", but I would't mean it. > > It seemed clear enough to me, though perhaps a bit awkwardly phrased. > > Quicksort is O(n log n) in the average case, O(N^2) in the worst > case. But that "average case" assumes random input. If Quicksort > is running in an environment where an attacker can feed it carefully > crafted input, its average case can become O(N^2), where the averate > is computed over the set of inputs it actually receives. This can > be used as a denial-of=service attack, which can, in some cases, > constitute a security hole. If an attacker wants to make your system spend huge amounts of time sorting, he can simply feed it arbitrarily large inputs. Regardless of the algorithm, more input means more CPU time used. So it's kind of silly to worry about an attacker when designing something like this, and more useful to design the algorithm around the expected normal input. -- Barry Margolin, barmar@alum.mit.edu Arlington, MA *** PLEASE post questions in newsgroups, not directly to me *** *** PLEASE don't copy me on replies, I'll read them in the group ***
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2011-05-17 09:12 -0700 |
| Message-ID | <lnk4dpe273.fsf@nuthaus.mib.org> |
| In reply to | #4143 |
Barry Margolin <barmar@alum.mit.edu> writes:
> In article <lnmximfyca.fsf@nuthaus.mib.org>,
> Keith Thompson <kst-u@mib.org> wrote:
[...]
>> Quicksort is O(n log n) in the average case, O(N^2) in the worst
>> case. But that "average case" assumes random input. If Quicksort
>> is running in an environment where an attacker can feed it carefully
>> crafted input, its average case can become O(N^2), where the averate
>> is computed over the set of inputs it actually receives. This can
>> be used as a denial-of=service attack, which can, in some cases,
>> constitute a security hole.
>
> If an attacker wants to make your system spend huge amounts of time
> sorting, he can simply feed it arbitrarily large inputs. Regardless of
> the algorithm, more input means more CPU time used.
>
> So it's kind of silly to worry about an attacker when designing
> something like this, and more useful to design the algorithm around the
> expected normal input.
(I don't remember who pointed this out, but yes, in an earlier
article I was sloppy in my use of big-O notation.)
It's probably easier to guard against unreasonably large inputs.
(A slow network connection will do the job nicely.) It's harder
to guard against attacks where a large input causes the program
to consume vastly more resources than another input of exactly the
same size.
If I were designing a program that needs to sort arrays whose
contents are not under my control, I'd avoid using an algorithm
whose run-time behavior can vary tremendously depending on the
nature of the input -- not just because of the possibility of
malicious attacks, but because even random data could conceivably
cause the same problem. Even if the problem is unlikely to occur,
it's good to have one less thing to worry about.
If this were difficult to do, I'd stop and consider whether it's
worth the effort, but it shouldn't be. Though a naive Quicksort
algorithm does suffer from this problem, my guess is that most,
perhaps all, library sorting algorithms avoid it, either by tweaking
Quicksort or by using a different algorithm.
A concrete question: Are there any existing C library implementations
of qsort() that are vulnerable to this kind of problem?
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> |
|---|---|
| Date | 2011-05-17 10:20 -0700 |
| Message-ID | <c314adca-7b06-4146-9afa-f02e5d523e96@g12g2000yqd.googlegroups.com> |
| In reply to | #4165 |
On May 17, 11:12 am, Keith Thompson <ks...@mib.org> wrote: > Barry Margolin <bar...@alum.mit.edu> writes: > > In article <lnmximfyca....@nuthaus.mib.org>, > > Keith Thompson <ks...@mib.org> wrote: > [...] > >> Quicksort is O(n log n) in the average case, O(N^2) in the worst > >> case. But that "average case" assumes random input. If Quicksort > >> is running in an environment where an attacker can feed it carefully > >> crafted input, its average case can become O(N^2), where the averate > >> is computed over the set of inputs it actually receives. This can > >> be used as a denial-of=service attack, which can, in some cases, > >> constitute a security hole. > > > If an attacker wants to make your system spend huge amounts of time > > sorting, he can simply feed it arbitrarily large inputs. Regardless of > > the algorithm, more input means more CPU time used. > > > So it's kind of silly to worry about an attacker when designing > > something like this, and more useful to design the algorithm around the > > expected normal input. > > (I don't remember who pointed this out, but yes, in an earlier > article I was sloppy in my use of big-O notation.) > > It's probably easier to guard against unreasonably large inputs. > (A slow network connection will do the job nicely.) It's harder > to guard against attacks where a large input causes the program > to consume vastly more resources than another input of exactly the > same size. > > If I were designing a program that needs to sort arrays whose > contents are not under my control, I'd avoid using an algorithm > whose run-time behavior can vary tremendously depending on the > nature of the input -- not just because of the possibility of > malicious attacks, but because even random data could conceivably > cause the same problem. Even if the problem is unlikely to occur, > it's good to have one less thing to worry about. > > If this were difficult to do, I'd stop and consider whether it's > worth the effort, but it shouldn't be. Though a naive Quicksort > algorithm does suffer from this problem, my guess is that most, > perhaps all, library sorting algorithms avoid it, either by tweaking > Quicksort or by using a different algorithm. > > A concrete question: Are there any existing C library implementations > of qsort() that are vulnerable to this kind of problem? Based solely on personal experience, I believe most C qsorts actually implement some version of quicksort, and are vulnerable. A few do introsort, and introsort is fairly common for C++ sort. I've also seen one qsort that implemented heapsort* (which would not have the issue). I think the issue is mainly history - most of the C implementations have been around longer than introsort, and fall into the if-it-ain't-broke category. *arguably a better general purpose choice than quicksort, but that’s a different topic
[toc] | [prev] | [next] | [standalone]
| From | pete <pfiland@mindspring.com> |
|---|---|
| Date | 2011-05-17 15:00 -0400 |
| Message-ID | <4DD2C5BF.5CB0@mindspring.com> |
| In reply to | #4167 |
robertwessel2@yahoo.com wrote: > > On May 17, 11:12 am, Keith Thompson <ks...@mib.org> wrote: > > Barry Margolin <bar...@alum.mit.edu> writes: > > > In article <lnmximfyca....@nuthaus.mib.org>, > > > Keith Thompson <ks...@mib.org> wrote: > > [...] > > >> Quicksort is O(n log n) in the average case, > > >> O(N^2) in the worst case. > > A concrete question: Are there any existing C library > > implementations > > of qsort() that are vulnerable to this kind of problem? > Based solely on personal experience, I believe most C qsorts actually > implement some version of quicksort, and are vulnerable. A few do > introsort, and introsort is fairly common for C++ sort. I've also > seen one qsort that implemented heapsort* (which would not have the > issue). I think the issue is mainly history - most of the C > implementations have been around longer than introsort, and fall into > the if-it-ain't-broke category. > > *arguably a better general purpose choice than quicksort, but that’s a > different topic It's been a few years since I've looked at a library implementation of qsort, but not much more than a few years. I've seen some remarkably bad ones, and never a remarkably good one. -- pete
[toc] | [prev] | [next] | [standalone]
| From | pacman@kosh.dhis.org (Alan Curry) |
|---|---|
| Date | 2011-05-17 20:28 +0000 |
| Message-ID | <iqulop$8mf$1@speranza.aioe.org> |
| In reply to | #4165 |
In article <lnk4dpe273.fsf@nuthaus.mib.org>, Keith Thompson <kst-u@mib.org> wrote: >Barry Margolin <barmar@alum.mit.edu> writes: >> In article <lnmximfyca.fsf@nuthaus.mib.org>, >> Keith Thompson <kst-u@mib.org> wrote: >[...] >>> Quicksort is O(n log n) in the average case, O(N^2) in the worst >>> case. But that "average case" assumes random input. If Quicksort >>> is running in an environment where an attacker can feed it carefully >>> crafted input, its average case can become O(N^2), where the averate >>> is computed over the set of inputs it actually receives. This can >>> be used as a denial-of=service attack, which can, in some cases, >>> constitute a security hole. >> >> If an attacker wants to make your system spend huge amounts of time >> sorting, he can simply feed it arbitrarily large inputs. Regardless of >> the algorithm, more input means more CPU time used. >> >> So it's kind of silly to worry about an attacker when designing >> something like this, and more useful to design the algorithm around the >> expected normal input. > >(I don't remember who pointed this out, but yes, in an earlier >article I was sloppy in my use of big-O notation.) > >It's probably easier to guard against unreasonably large inputs. >(A slow network connection will do the job nicely.) It's harder That's great. You run an Internet service that handles a zillion transactions per day, it's someone figures out how to make an algorithm degenerate to the worst case, he brings your server farm to permanent 100% CPU usage with a series of malicious packets that use up only .0001% of your network bandwidth. What's your solution? Host the service on a 9600-baud modem! That'll stop the attack! And your other users too. But they were an unreasonably large group. Did anybody read the Algorithmic Complexity Attacks paper before rushing to post their ignorant opinions? It matters a lot whether denial of service can be accomplished by an attacker without superior network bandwidth. That's why people who make widely used server software have responded to issues of this nature with algorithm modifications, not with "DoS defense is hard, let's go shopping" -- Alan Curry
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2011-05-17 14:45 -0700 |
| Message-ID | <lnboz1dmsh.fsf@nuthaus.mib.org> |
| In reply to | #4185 |
pacman@kosh.dhis.org (Alan Curry) writes:
> In article <lnk4dpe273.fsf@nuthaus.mib.org>,
> Keith Thompson <kst-u@mib.org> wrote:
[...]
>>It's probably easier to guard against unreasonably large inputs.
>>(A slow network connection will do the job nicely.) It's harder
>
> That's great. You run an Internet service that handles a zillion transactions
> per day, it's someone figures out how to make an algorithm degenerate to the
> worst case, he brings your server farm to permanent 100% CPU usage with a
> series of malicious packets that use up only .0001% of your network
> bandwidth. What's your solution? Host the service on a 9600-baud modem!
> That'll stop the attack! And your other users too. But they were an
> unreasonably large group.
>
> Did anybody read the Algorithmic Complexity Attacks paper before rushing to
> post their ignorant opinions?
Did you really think my passing remark about a slow network connection
was seriously intended as a solution to the problem?
It wasn't. It was a joke.
Sheesh.
[...]
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2011-05-17 14:51 -0700 |
| Message-ID | <ln7h9pdmie.fsf@nuthaus.mib.org> |
| In reply to | #4165 |
Keith Thompson <kst-u@mib.org> writes:
[...]
> If I were designing a program that needs to sort arrays whose
> contents are not under my control, I'd avoid using an algorithm
> whose run-time behavior can vary tremendously depending on the
> nature of the input -- not just because of the possibility of
> malicious attacks, but because even random data could conceivably
> cause the same problem. Even if the problem is unlikely to occur,
> it's good to have one less thing to worry about.
>
> If this were difficult to do, I'd stop and consider whether it's
> worth the effort, but it shouldn't be. Though a naive Quicksort
> algorithm does suffer from this problem, my guess is that most,
> perhaps all, library sorting algorithms avoid it, either by tweaking
> Quicksort or by using a different algorithm.
On re-reading this, I realize that the sentence
If this were difficult to do, I'd stop and consider whether it's
worth the effort, but it shouldn't be.
was unclear. I meant that it shouldn't be difficult to do, not
that it shouldn't be worth the effort.
> A concrete question: Are there any existing C library implementations
> of qsort() that are vulnerable to this kind of problem?
I took a look at the glibc implementation of qsort(). It does
use Quicksort, but with some tweaks. It picks the pivot using a
median-of-three decision tree, it falls back to insertion sort for
small segments, it uses an explicit stack rather than recursion,
and it always handles the larger partition first. I don't know
whether this completely avoids the worst-case N**2 behavior or not,
but it should make it less likely to happen accidentally.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> |
|---|---|
| Date | 2011-05-17 16:23 -0700 |
| Message-ID | <a8108bf0-8262-400b-91ef-35f4b95d005b@t19g2000yql.googlegroups.com> |
| In reply to | #4194 |
On May 17, 4:51 pm, Keith Thompson <ks...@mib.org> wrote: > Keith Thompson <ks...@mib.org> writes: > > [...] > > > If I were designing a program that needs to sort arrays whose > > contents are not under my control, I'd avoid using an algorithm > > whose run-time behavior can vary tremendously depending on the > > nature of the input -- not just because of the possibility of > > malicious attacks, but because even random data could conceivably > > cause the same problem. Even if the problem is unlikely to occur, > > it's good to have one less thing to worry about. > > > If this were difficult to do, I'd stop and consider whether it's > > worth the effort, but it shouldn't be. Though a naive Quicksort > > algorithm does suffer from this problem, my guess is that most, > > perhaps all, library sorting algorithms avoid it, either by tweaking > > Quicksort or by using a different algorithm. > > On re-reading this, I realize that the sentence > > If this were difficult to do, I'd stop and consider whether it's > worth the effort, but it shouldn't be. > > was unclear. I meant that it shouldn't be difficult to do, not > that it shouldn't be worth the effort. > > > A concrete question: Are there any existing C library implementations > > of qsort() that are vulnerable to this kind of problem? > > I took a look at the glibc implementation of qsort(). It does > use Quicksort, but with some tweaks. It picks the pivot using a > median-of-three decision tree, it falls back to insertion sort for > small segments, it uses an explicit stack rather than recursion, > and it always handles the larger partition first. I don't know > whether this completely avoids the worst-case N**2 behavior or not, > but it should make it less likely to happen accidentally. It does *not*. Again, I recommend Musser's original Introsort paper for a quite interesting description of how to generate worst case sequences for the common variants of Quicksort. It's actually remarkably straight-forward.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2011-05-17 23:06 -0700 |
| Message-ID | <ba2a5ac6-a1d7-4928-b148-de6dbb09c4d7@m10g2000yqd.googlegroups.com> |
| In reply to | #4199 |
On May 18, 2:23 am, "robertwess...@yahoo.com" <robertwess...@yahoo.com> wrote: > > It does *not*. Again, I recommend Musser's original Introsort paper > for a quite interesting description of how to generate worst case > sequences for the common variants of Quicksort. It's actually > remarkably straight-forward. > You just shuffle the input. Then it becomes far more likely that the computer will break than that you hit a worst case or even a bad case.
[toc] | [prev] | [next] | [standalone]
| From | "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> |
|---|---|
| Date | 2011-05-18 01:02 -0700 |
| Message-ID | <ae27074f-5070-4738-a2e8-74c5ace1dd21@c41g2000yqm.googlegroups.com> |
| In reply to | #4211 |
On May 18, 1:06 am, Malcolm McLean <malcolm.mcle...@btinternet.com> wrote: > On May 18, 2:23 am, "robertwess...@yahoo.com"<robertwess...@yahoo.com> wrote: > > > It does *not*. Again, I recommend Musser's original Introsort paper > > for a quite interesting description of how to generate worst case > > sequences for the common variants of Quicksort. It's actually > > remarkably straight-forward. > > You just shuffle the input. Then it becomes far more likely that the > computer will break than that you hit a worst case or even a bad case. Where are we going to get the entropy to do a good shuffle? And if we just use a deterministic shuffle, it should be trivial for the attacker to reverse that before sending the data. Obviously intermediate approaches are possible (use 32 bit of entropy to select one of ~2**32 permutations, for example, possibly by using the entropy to seed a PRNG to drive the shuffle). And why would any of this be meaningfully easier, or faster, than just using an introsort or heapsort instead? Doing a shuffle+quicksort ought to be a bit faster than heapsort on small elements, assuming a reasonably fast shuffle. Heapsort will definitely be simpler to implement (heck, heapsort is simpler than quicksort with median-of- three and separate small partition handling anyway). Shuffle +quicksort will certainly be slower than introsort in the typical cases (where introsort is identical to a straight quicksort). Assuming the preexistence of a useable entropy source, shuffle +quicksort ought to be slightly simpler to implement than introsort.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.mclean5@btinternet.com> |
|---|---|
| Date | 2011-05-18 01:29 -0700 |
| Message-ID | <5a611fd8-d57a-4dd3-8a91-87c21fb8a681@y4g2000yqm.googlegroups.com> |
| In reply to | #4213 |
On May 18, 11:02 am, "robertwess...@yahoo.com" <robertwess...@yahoo.com> wrote: > > > Where are we going to get the entropy to do a good shuffle? > From the clock. The attacker can still time his input so that the clock comes up with the right number, but that's likely to be challenging. Certainly it will be a lot harder than getting the source for Microsoft Visual C++ qsort(), and engineering an input that takes N^3 iterations to complete.
[toc] | [prev] | [next] | [standalone]
| From | "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> |
|---|---|
| Date | 2011-05-18 04:03 -0700 |
| Message-ID | <123d7165-a273-49c6-bb96-2c394a73ead7@z13g2000yqg.googlegroups.com> |
| In reply to | #4214 |
On May 18, 3:29 am, Malcolm McLean <malcolm.mcle...@btinternet.com> wrote: > On May 18, 11:02 am, "robertwess...@yahoo.com"<robertwess...@yahoo.com> wrote: > > > Where are we going to get the entropy to do a good shuffle? > > From the clock. > The attacker can still time his input so that the clock comes up with > the right number, but that's likely to be challenging. Certainly it > will be a lot harder than getting the source for Microsoft Visual C++ > qsort(), and engineering an input that takes N^3 iterations to > complete. The clock is a poor source of entropy, especially if you're using actual time. Sure, timing is bit of a challenge, but nothing that hasn't been done before. FWIW, the source to MS's qsort is in vc\crt \src\qsort.c (assuming you installed source when you installed VS), and implements a slightly modified median-of-three quicksort. And quicksort's worst case is N**2.
[toc] | [prev] | [next] | [standalone]
| From | Ben Pfaff <blp@cs.stanford.edu> |
|---|---|
| Date | 2011-05-17 16:47 -0700 |
| Message-ID | <8762p851pm.fsf@blp.benpfaff.org> |
| In reply to | #4194 |
Keith Thompson <kst-u@mib.org> writes: > I took a look at the glibc implementation of qsort(). It does > use Quicksort, but with some tweaks. It picks the pivot using a > median-of-three decision tree, it falls back to insertion sort for > small segments, it uses an explicit stack rather than recursion, > and it always handles the larger partition first. I don't know > whether this completely avoids the worst-case N**2 behavior or not, > but it should make it less likely to happen accidentally. It also uses merge sort instead of quicksort when enough memory is available. -- Ben Pfaff http://benpfaff.org
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2011-05-17 17:21 -0700 |
| Message-ID | <lnzkmk505h.fsf@nuthaus.mib.org> |
| In reply to | #4200 |
Ben Pfaff <blp@cs.stanford.edu> writes:
> Keith Thompson <kst-u@mib.org> writes:
>> I took a look at the glibc implementation of qsort(). It does
>> use Quicksort, but with some tweaks. It picks the pivot using a
>> median-of-three decision tree, it falls back to insertion sort for
>> small segments, it uses an explicit stack rather than recursion,
>> and it always handles the larger partition first. I don't know
>> whether this completely avoids the worst-case N**2 behavior or not,
>> but it should make it less likely to happen accidentally.
>
> It also uses merge sort instead of quicksort when enough memory
> is available.
What I wrote above appears to be only a subset of the truth.
I grabbed the glibc sources and took a quick look at qsort.c
(mostly just skimming the comments). Had I looked more closely,
I would have realized that qsort.c doesn't actually define qsort().
qsort() is defined in msort.c; it's a wrapper around qsort_r, which
*sometimes* calls the _quicksort function that's defined in qsort.c.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | Phil Carmody <thefatphil_demunged@yahoo.co.uk> |
|---|---|
| Date | 2011-05-23 21:57 +0300 |
| Message-ID | <87aaedtfcb.fsf@bazspaz.fatphil.org> |
| In reply to | #4194 |
Keith Thompson <kst-u@mib.org> writes: > Keith Thompson <kst-u@mib.org> writes: > [...] > > If I were designing a program that needs to sort arrays whose > > contents are not under my control, I'd avoid using an algorithm > > whose run-time behavior can vary tremendously depending on the > > nature of the input -- not just because of the possibility of > > malicious attacks, but because even random data could conceivably > > cause the same problem. Even if the problem is unlikely to occur, > > it's good to have one less thing to worry about. > > > > If this were difficult to do, I'd stop and consider whether it's > > worth the effort, but it shouldn't be. Though a naive Quicksort > > algorithm does suffer from this problem, my guess is that most, > > perhaps all, library sorting algorithms avoid it, either by tweaking > > Quicksort or by using a different algorithm. > > On re-reading this, I realize that the sentence > > If this were difficult to do, I'd stop and consider whether it's > worth the effort, but it shouldn't be. > > was unclear. I meant that it shouldn't be difficult to do, not > that it shouldn't be worth the effort. > > > A concrete question: Are there any existing C library implementations > > of qsort() that are vulnerable to this kind of problem? > > I took a look at the glibc implementation of qsort(). It does > use Quicksort, but with some tweaks. It picks the pivot using a > median-of-three decision tree, it falls back to insertion sort for > small segments, it uses an explicit stack rather than recursion, > and it always handles the larger partition first. Odd, in order to reduce actual recursion (and do tail recursion instead), and to keep locality of reference tight, I'd handle the smaller part first were I to use an actual quicksort. Not that I'd do that, being more of a fan of heapsort in situations where I want an acceptable worst-case big-Oh for reasons such as availability. > I don't know > whether this completely avoids the worst-case N**2 behavior or not, > but it should make it less likely to happen accidentally. Nope, reduces the constant, that's all. If the median is selected from 3 random (i.e. unpredicatable to an attacker) elements, then the worst case behaviour can not be forced, and you would average to the theoretical average. But then you have to secure information about your (P)RNG state. Phil -- "At least you know where you are with Microsoft." "True. I just wish I'd brought a paddle." -- Matthew Vernon
[toc] | [prev] | [next] | [standalone]
| From | Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> |
|---|---|
| Date | 2011-05-23 21:57 +0100 |
| Message-ID | <IU.D20110523.T205837.P9147.Q0@J.de.Boyne.Pollard.localhost> |
| In reply to | #4575 |
>> I took a look at the glibc implementation of qsort(). It does use >> Quicksort, but with some tweaks. It picks the pivot using a >> median-of-three decision tree, it falls back to insertion sort for >> small segments, it uses an explicit stack rather than recursion, and >> it always handles the larger partition first. >> > Odd, in order to reduce actual recursion (and do tail recursion > instead), and to keep locality of reference tight, I'd handle the > smaller part first were I to use an actual quicksort. > You've made me curious enough to revisit the code of my standard library's sorting function after many years. It does median-of-three and falls back to insertion sort (or even just a straight immediate swap for fewer than three elements). But, like M. Carmody, I pick the smaller portion to tail recurse on. This is what Robert Sedgewick does. All of these "tweaks" mentioned are discussed by Sedgewick, in fact.
[toc] | [prev] | [next] | [standalone]
| From | "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> |
|---|---|
| Date | 2011-05-23 17:45 -0700 |
| Message-ID | <bb9329d4-1361-4fbe-a939-772c1f09da59@m10g2000yqd.googlegroups.com> |
| In reply to | #4575 |
On May 23, 1:57 pm, Phil Carmody <thefatphil_demun...@yahoo.co.uk> wrote: > Keith Thompson <ks...@mib.org> writes: > > Keith Thompson <ks...@mib.org> writes: > > [...] > > > If I were designing a program that needs to sort arrays whose > > > contents are not under my control, I'd avoid using an algorithm > > > whose run-time behavior can vary tremendously depending on the > > > nature of the input -- not just because of the possibility of > > > malicious attacks, but because even random data could conceivably > > > cause the same problem. Even if the problem is unlikely to occur, > > > it's good to have one less thing to worry about. > > > > If this were difficult to do, I'd stop and consider whether it's > > > worth the effort, but it shouldn't be. Though a naive Quicksort > > > algorithm does suffer from this problem, my guess is that most, > > > perhaps all, library sorting algorithms avoid it, either by tweaking > > > Quicksort or by using a different algorithm. > > > On re-reading this, I realize that the sentence > > > If this were difficult to do, I'd stop and consider whether it's > > worth the effort, but it shouldn't be. > > > was unclear. I meant that it shouldn't be difficult to do, not > > that it shouldn't be worth the effort. > > > > A concrete question: Are there any existing C library implementations > > > of qsort() that are vulnerable to this kind of problem? > > > I took a look at the glibc implementation of qsort(). It does > > use Quicksort, but with some tweaks. It picks the pivot using a > > median-of-three decision tree, it falls back to insertion sort for > > small segments, it uses an explicit stack rather than recursion, > > and it always handles the larger partition first. > > Odd, in order to reduce actual recursion (and do tail recursion > instead), and to keep locality of reference tight, I'd handle the > smaller part first were I to use an actual quicksort. Not that I'd > do that, being more of a fan of heapsort in situations where I want > an acceptable worst-case big-Oh for reasons such as availability. The usual approach for the semi-recursive implementation is to recurse on the smaller partition, and then loop (or allow tail recursion, assuming your implementation language supports that) on the bigger one. If you do a fully iterative version (managing your own stack), you need to “push” the smaller partition last, so that you sort it first. If you do it the other way, you can't bound your stack size to log(N). A fully recursive implementation is stuck with order-N worst case stack requirements (no matter which order you process the partitions), unless you can guarantee tail recursion elimination. > > I don't know > > whether this completely avoids the worst-case N**2 behavior or not, > > but it should make it less likely to happen accidentally. > > Nope, reduces the constant, that's all. If the median is selected > from 3 random (i.e. unpredicatable to an attacker) elements, then > the worst case behaviour can not be forced, and you would average > to the theoretical average. But then you have to secure information > about your (P)RNG state. And producing large quantities of good random numbers with low overhead is much harder than the problem you wanted to solve in the first place.
[toc] | [prev] | [next] | [standalone]
| From | Rainer Weikusat <rweikusat@mssgmbh.com> |
|---|---|
| Date | 2011-05-24 11:43 +0100 |
| Message-ID | <87r57ojs40.fsf@sapphire.mobileactivedefense.com> |
| In reply to | #4638 |
"robertwessel2@yahoo.com" <robertwessel2@yahoo.com> writes: [...] >>> I don't know whether this completely avoids the worst-case N**2 >>> behavior or not, but it should make it less likely to happen >>> accidentally. >> >> Nope, reduces the constant, that's all. If the median is selected >> from 3 random (i.e. unpredicatable to an attacker) elements, then >> the worst case behaviour can not be forced, and you would average >> to the theoretical average. But then you have to secure information >> about your (P)RNG state. > > And producing large quantities of good random numbers with low > overhead is much harder than the problem you wanted to solve in the > first place. In theory. In practice, all this takes is linking with OpenSSL, assuming that some source of good randomness will always be available/ nobody except the person who wrote the code will ever bother to check it with that much detail (especially, since the chances that anyone who is at least remoteley superior insofar job positions go both understands the issue and cares about it in absence of a pending customer lawsuit are extremly slim) and then go on a happy, four week holiday somewhere in the sun with the pleasant conviction that an inherently wrong solution for some problem can always be turned into something which gives a 'good enough' appearance of working for all practical purposes by making the implementation complicated enough to hide its deficiencies.
[toc] | [prev] | [next] | [standalone]
Page 7 of 13 — ← Prev page 1 … 5 6 [7] 8 9 … 13 Next page →
Back to top | Article view | comp.lang.c
csiph-web