220 38869 article Path: news.gmane.org!.POSTED!not-for-mail From: Nicol Bolas Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Re: Limit iterative functions Date: Wed, 27 Jun 2018 09:18:34 -0700 (PDT) Lines: 171 Approved: news@gmane.org Message-ID: References: <4932fdae-3a5a-4212-bf89-b75f855e9634@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_43516_1207349919.1530116314538" X-Trace: blaine.gmane.org 1530116190 21738 195.159.176.226 (27 Jun 2018 16:16:30 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 27 Jun 2018 16:16:30 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCEKFTV6ZUMBBW7RZ3MQKGQEZR73N5Y@isocpp.org Wed Jun 27 18:16:26 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yw0-f197.google.com ([209.85.161.197]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1fYD7J-0005Xx-7X for gclcip-std-proposals@m.gmane.org; Wed, 27 Jun 2018 18:16:25 +0200 Original-Received: by mail-yw0-f197.google.com with SMTP id p11-v6sf2005358ywm.4 for ; Wed, 27 Jun 2018 09:18:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=ZVeWPq50XWumNMbrS1nOY8YSFzsDapfb+Ld27ZzeOqo=; b=akguVWVcfoPx/xu7GZex+U2isiS+3pvGoFKEJ+KDrkwTwxN1s2TsMJNWvUkWkEDiv5 pPqmin+mtiLXfN3s14PFeKn9iFqijOEZfYukBGYTUD7rteJZP9i2NYIXcREWUJIVnH5a 3lfz9RGmtmplK1jL7dVBl9ltQuoRCLjp1IL/9lbPBHyozRZ8tfIYaah82SsUnsq4rkOR K4hJ4fgMDttfDMtD04Brg0zCsLH+w0eO+ybidazEfJylYW0giRBJJgTXJhnYspguP2tz vHfqrFydsPyfKRC4lr2l2y7gMReGYA2CNJRFtFDFIbgfEr0TncJ1/6bBvqJRDS2E7W7V EfdQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=ZVeWPq50XWumNMbrS1nOY8YSFzsDapfb+Ld27ZzeOqo=; b=M0xjQK6/o8TWMphNnsCyiSXa5qXgU/aQSvQx5xj8JGmLDKLD36sB228aYEfMxHL89w R1TwhfqjERXgw+BTIFl+ljfb2PxRlDiBRIqjbnkDifaGal91HqLOCe9xWX02zpdwtQTE /9x+0lsM3jcipdlo9sWS2ysmjDDQkWazyEm4QX8yFC6FLcxbStCKEhXvVBjz8CnlUD2j Db3NVHw8XOeT2bOnaFZLLlSV1qZRGdskCaIRXVZEwjFfXSEeSDEbzuW9oSXhK2f/13nQ EBZAlBlOGzo3CNCvjESpUXtpNzoN3UciruFMpkdROXe8eoKuvkZtGKvHKRJXOQe/asXj G0dg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version:x-original-sender:reply-to:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=ZVeWPq50XWumNMbrS1nOY8YSFzsDapfb+Ld27ZzeOqo=; b=HctVT08BI5hmSnm76/V1l3NKvTvFuXQPFsnK8/j3GYEmbunZRmezQt5gkjNat/75KF YeMqc0GwOGTOIScQ6N5VtN6+LPid3EEq7kly+IdSYTrcwyCPp+nlyHhXIoUdJwFSxR6A jed6bOAZmx5Ly96OLzHxCRhvapXU4Vj3nfu0f8XVnHQ8A+mxhsvDY/9rQ19kYIGc8mJp z5JaOZDwA3+i8LXYH4MaZ4WIeJ6BQHNNgTXHhl2MyJmAemyM0SkzIcAVHaw7LwGvY1Uj LVUJLPsZE7UxKGoVJMMh9E5ObQ++GKhjUop9eYGo3YgkukogqDthWK3I2bPXXCWQD3V1 Hr8w== X-Gm-Message-State: APt69E0AHqKEfiyqaB32MXRcotUBSERqrGHAnepG3gnlWDy+YoPNGbh6 G4U2yD1no+I5kaZDyVbPx04UFw== X-Google-Smtp-Source: AAOMgpeSn8FTc2A1TyCHbgzHewdbX0izX+++IS3ZMIHdrdYO5Zy3kX+c64tvD7kLGh2KQcBGKC8nog== X-Received: by 2002:a81:2044:: with SMTP id g65-v6mr1719952ywg.182.1530116316166; Wed, 27 Jun 2018 09:18:36 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a25:2e46:: with SMTP id b6-v6ls1531308ybn.4.gmail; Wed, 27 Jun 2018 09:18:35 -0700 (PDT) X-Received: by 2002:a25:8486:: with SMTP id v6-v6mr594167ybk.3.1530116315016; Wed, 27 Jun 2018 09:18:35 -0700 (PDT) In-Reply-To: X-Original-Sender: jmckesson@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:38869 Archived-At: ------=_Part_43516_1207349919.1530116314538 Content-Type: multipart/alternative; boundary="----=_Part_43517_307327165.1530116314538" ------=_Part_43517_307327165.1530116314538 Content-Type: text/plain; charset="UTF-8" On Wednesday, June 27, 2018 at 12:06:00 PM UTC-4, Daniel Gutson wrote: > > On Wed, Jun 27, 2018 at 12:59 PM, Nicol Bolas > wrote: > >> On Wednesday, June 27, 2018 at 11:47:50 AM UTC-4, Daniel Gutson wrote: >>> >>> Some functions may keep looping for an unbounded amount of iterations, >>> such as std::distance. This may cause DoS. >>> I propose to add *_n versions so things are controlled in case of >>> invalid input. >>> >> >> 1. What does a function return if it reached `n`? Is that considered to >> produce a correct iterator, or are you just catching invalid input? If it's >> the latter, then I imagine some form of exception would be thrown. Is that >> what we want? >> > > I want to survey the idea at high level first, then we can dig into the > implementation, expected behavior, interface. > Without considering expected behavior, the idea cannot reasonably be considered at the high level. If the caller cannot tell the difference between early termination and the getting a legitimate distance `distance_n`, then that will strongly affect who will and will not use this function. If it's not considered valid behavior, then it changes how users have to interact with it, which again affects who will and will not be willing to call it. So yes, these are things that must be considered, even from a high level. They affect the usability of the tool. And since this tool exists purely for safety reasons, then such usability needs to be taken into account. There's no point in having "safe" interfaces nobody is willing to use, after all. 2. What is an appropriate "n" for detecting invalid input for a particular >> range, and how do you communicate that value to those who directly call >> `std::distance_n` or similar functions? After all, `std::distance` and the >> like are usually used deep down in various systems; even if they were using >> `distance_n`, how would you tell them what the right "n" is? >> > > There are two non-mutually-exclusive approaches about this. > 1- iteration limit > 1.1 - based on known boundaries (e.g. memory space knowlege) > 1.2 - based on measurements > 1.2.1 - experimentally determined > 1.2.2 - run-time determined based on running statistics > 2- time limit > > Maybe a better interface (discussion I'd like to postpone a little bit > after getting more consensus) could be to accept a caller-provided > termination_policy, and offer 3 basic policies (count-based, time-based, > and an OR-combining policy). > It doesn't matter what the information is. I want to know how you get that information from the high-level code that supplied the potentially invalid iterators (and therefore is the code that has some idea of what such boundary conditions ought to be) to the low-level code that will actually call `std::distance` (which probably has no idea what a reasonable boundary is). Take `std::lower_bound`. It probably uses `std::advance` or `std::next`, which would have similar boundary condition functions. `lower_bound` has *no idea* what a reasonable boundary condition would be; only the caller would know. So do we now need a version of `lower_bound` that takes this boundary condition as an optional parameter? -- You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/c3a0e827-0580-4c49-af1e-fd1b192f7734%40isocpp.org. ------=_Part_43517_307327165.1530116314538 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Wednesday, June 27, 2018 at 12:06:00 PM UTC-4, Daniel G= utson wrote:
<= div>
On Wed, Jun 27, 2018 at 12:59 PM, Nicol Bola= s <jmck...@gmail.com> wrote:
On Wednesday, June 27, 2018 at 11:= 47:50 AM UTC-4, Daniel Gutson wrote:
Some functions may keep looping for an unbounded amount o= f iterations, such as std::distance. This may cause DoS.
I propose to a= dd *_n versions so things are controlled in case of invalid input.

1. What does a= function return if it reached `n`? Is that considered to produce a correct= iterator, or are you just catching invalid input? If it's the latter, = then I imagine some form of exception would be thrown. Is that what we want= ?

I want to survey the idea= at high level first, then we can dig into the implementation, expected beh= avior, interface.

W= ithout considering expected behavior, the idea cannot reasonably be conside= red at the high level. If the caller cannot tell the difference between ear= ly termination and the getting a legitimate distance `distance_n`, then tha= t will strongly affect who will and will not use this function. If it's= not considered valid behavior, then it changes how users have to interact = with it, which again affects who will and will not be willing to call it.

So yes, these are things that must be considered, e= ven from a high level. They affect the usability of the tool. And since thi= s tool exists purely for safety reasons, then such usability needs to be ta= ken into account. There's no point in having "safe" interface= s nobody is willing to use, after all.

2. What is an appropriate "n" for detecting invalid= input for a particular range, and how do you communicate that value to tho= se who directly call `std::distance_n` or similar functions? After all, `st= d::distance` and the like are usually used deep down in various systems; ev= en if they were using `distance_n`, how would you tell them what the right = "n" is?

There are two= non-mutually-exclusive approaches about this.
1- iteration limit=
1.1 - based on known boundaries (e.g. memory space knowlege)
1.2 - based on measurements
1.2.1 - experimentally determi= ned
1.2.2 - run-time determined based on running statistics
=
2- time limit

Maybe a better interface (discu= ssion I'd like to postpone a little bit after getting more consensus) c= ould be to accept a caller-provided termination_policy, and offer 3 basic p= olicies (count-based, time-based, and an OR-combining policy).
<= /div>

It doesn't matter what the = information is. I want to know how you get that information from the high-l= evel code that supplied the potentially invalid iterators (and therefore is= the code that has some idea of what such boundary conditions ought to be) = to the low-level code that will actually call `std::distance` (which probab= ly has no idea what a reasonable boundary is).

Take `std::lower_bound`. It probably uses `std::advance` or `std::next`, w= hich would have similar boundary condition functions. `lower_bound` has = no idea what a reasonable boundary condition would be; only the caller = would know. So do we now need a version of `lower_bound` that takes this bo= undary condition as an optional parameter?

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.= com/a/isocpp.org/d/msgid/std-proposals/c3a0e827-0580-4c49-af1e-fd1b192f7734= %40isocpp.org.
------=_Part_43517_307327165.1530116314538-- ------=_Part_43516_1207349919.1530116314538-- .