220 38871 article Path: news.gmane.org!.POSTED!not-for-mail From: Daniel Gutson Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Re: Limit iterative functions Date: Wed, 27 Jun 2018 13:31:20 -0300 Lines: 320 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/alternative; boundary="00000000000012a676056fa22590" X-Trace: blaine.gmane.org 1530116958 10882 195.159.176.226 (27 Jun 2018 16:29:18 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Wed, 27 Jun 2018 16:29:18 +0000 (UTC) To: std-proposals Original-X-From: std-proposals+bncBDE3NBMV6UFBBWPXZ3MQKGQEYKUS25Y@isocpp.org Wed Jun 27 18:29:13 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-pf0-f200.google.com ([209.85.192.200]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1fYDJf-0002h3-Kr for gclcip-std-proposals@m.gmane.org; Wed, 27 Jun 2018 18:29:12 +0200 Original-Received: by mail-pf0-f200.google.com with SMTP id g20-v6sf1298493pfi.2 for ; Wed, 27 Jun 2018 09:31:23 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1530117082; cv=pass; d=google.com; s=arc-20160816; b=hVlUcn9x31PIEl8vJTVEWgxHLuWbNnRP4RckqffIXHgAmWsEYekfdAzLBMY7iVZ3Jz 5QFc1g6aCN1JhZSLCSp5ho2g5f8pmbYmAkHOVcVmb0HKIp88P7DmCeKpTYv7bK+7vJXx oT2+oHKKAAwHh4c8Cy2Zlr3Daiv52lY/JVYCS7xk1SU9SezAGXF9dw65EFWDVx0HRoXm Bv5ArYpYU89jqPPkqQDH8zaBvJIF2vypspt+o+B6ykKuLMdVmCXXss3N6LgAWjl2BhcD kovCHON3uQ5LVEkFXDM7hrifuw2o5LOXUfKt/RdDKawu4Bc/e3t2JgO7XnYjRkTPx9MZ +lhw== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:to:subject:message-id:date :from:references:in-reply-to:mime-version:arc-authentication-results :arc-message-signature:dkim-signature:arc-authentication-results; bh=zqR9uPqYT1tYAScwTn8ykC5W1FpqoSXKdj3U9nutCPg=; b=OV8N17Knd8GZP/ZZrht6lEsNROMoB0dN0DNikdvxkHhjUZP0VXFuiIsAxtqTIuXf1W tNhkZCQ4UdmCck7rBFdZ58eo1ti2Ito6rD5vVkEEzMZi6iI3vGGVOYWQbnEIpyg3V1Pb ja9Z45bUWOTXUsqcxRiLQ+6ifuKtOpkmy553UfFQY9H8DmoSVLngS9J8GFxLuf4QE9oi pnh5YuHjlC796UM/VPG1Or2B/F2QTe1aETaRcLJ73kPvGqL6eBdWV1kII07QYwWbTC71 gAf3MYlO1CL/ZgpB9I4LXbhGfqd5cdlt1laBJcXSoWxjIL242jwEXqoi0xm3KVDHNNBQ WIAA== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=tIqV1dKr; spf=pass (google.com: domain of danielgutson@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=danielgutson@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :x-original-sender:x-original-authentication-results:reply-to :precedence:mailing-list:list-id:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=zqR9uPqYT1tYAScwTn8ykC5W1FpqoSXKdj3U9nutCPg=; b=TtlNoVfmNzNg5XSb5qc0iPb3vxBhA2FzjzphagoQX4ebEV1avtgXOjL19nli1Vnr47 A51e+jcpShOfnQltIEMGQQP3CzEHi3FMxOA+QNY0oE6HEGaVztAtN9pQShvZonV0PtCo GMpbZQqtPh/fsUpZiapxaiPnizzHoBsll7w1dU/QscKWG1aVGzDhZhicHKUDwhu1WxgR BGjbesUPA14p5syTNkZm4jG6vh4xTfBxErCGT3vbXdwyDZzZHJ3sh1gtDNqC6JlS4Gi/ zEjwFxLRM5HKW/+gFtECCiWeN0vnRuCz4MYC/7w43rormG5mLgXmBrH2ufWcqZohr8jV 2JJg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:x-original-sender :x-original-authentication-results:reply-to:precedence:mailing-list :list-id:x-spam-checked-in-group:list-post:list-help:list-archive :list-subscribe:list-unsubscribe; bh=zqR9uPqYT1tYAScwTn8ykC5W1FpqoSXKdj3U9nutCPg=; b=kp/qKRhAm/ru2N3Se/v+up1+D9/W87P6De48gkS0ezPslRJaZ4jfbzPEpYg4WxTBdv mtUaAq1WAF8LK0GU1/M1CAzJXnrO3W4sW9PTHpY24u4guKWRMn/2qN7SB4KlLTdeoR/4 lFsC/4w4JUh8YeQ6j+gz0fcla8eHNZdOxpJ7C04OwIvYt9qQ+U0FwiVTlC6i01W7os45 AwAPmgIQFHerFwY9GjyNVYahJuxBST9uJiVRrURTH0p1286d2O82zBo652RrfQ9rdxZS 228rt2jkr3yMZRbVsUjq/yEM0QRpYRJuMIdzru43idmPy3Cp6Iz6dz2S0YLWCuDsLYeh NOaw== X-Gm-Message-State: APt69E1VaXwSQpVg6P8ofUtxN2yMX5nOtwIfv1mszzaRxV+qsLhcgR8j Ye2QKbYwXYoOFf5sJJuP2zolZg== X-Google-Smtp-Source: ADUXVKLIIeXtFpeJllod/h/uCBKKGHddiK+H+HJy/jTgeYeb3qe2FVfYhCflh5nCauxdBTh1/xvpwA== X-Received: by 2002:a63:6113:: with SMTP id v19-v6mr1341496pgb.54.1530117082438; Wed, 27 Jun 2018 09:31:22 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a65:4a8c:: with SMTP id b12-v6ls1222187pgu.19.gmail; Wed, 27 Jun 2018 09:31:21 -0700 (PDT) X-Received: by 2002:a65:4d4b:: with SMTP id j11-v6mr5834544pgt.430.1530117081384; Wed, 27 Jun 2018 09:31:21 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1530117081; cv=none; d=google.com; s=arc-20160816; b=B1NHBMX3nLptr8qoF1hFo0aeNAs/dzI2ne8okL4yEVYWOiwoPo+xZYvTecTmzgex8N FZ6gs5XH2z0bwuo673/0JaWemD+JPJMA1aTdvFd4HazzMz+cGdM/PhzfunD6QZ1/pPrP TlBhcI34bDJtrMdypxz9ditKZfRF+pBCDstNP5nZbcXPmCyLgg3QjAJZABqOw4LHRw6Z enk/XzzU+pydiIf7wEih05rFYCFvIP0UFX2m81ucgMu+E20j7AWz8GnWubcXuoZQT7Cy 6v6kA2Ls3rAPYpuZl0wSE3UvDON+aQFuALkKo+8W5LjhlMxrtWSDZZootz2c1JQ7qy2p i/5A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:subject:message-id:date:from:references:in-reply-to:mime-version :dkim-signature:arc-authentication-results; bh=oC0Dqg4uC66egWaqVcoyOrSF1WhMKHoTO7bDCt3cTjs=; b=x0bBdQWbETpEF5gbeaVa61b4TkS8DGiLuzDa7UFqitNF/TMLSsBQAS4NdeVuRFk3nC ihxnAeyKs+1F+XwqgJY9AAx4IUWu80xo1UIVC40zprTQ62CjM6LWmpMSyvB1h2kBMqAo wgBdAUkQhTxvzvWy0b3J3R0kQKYskajHG//FCrgC5SBWkP+jeZuprWiQp5STpE2IC6By q1v4lSi8SBj1dJb5X+NU9HwTzOmyjtWFGHI2Ah7/BMSASQR66uf1D6NPsYyN+B4+MG4w xs4v5PSR+qUADBU6UdVWBgPbUcQ9iSLzrz7+OSL8JBZJ4019BZtbUwu3PyGbIbETrlAY Z4PA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=tIqV1dKr; spf=pass (google.com: domain of danielgutson@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=danielgutson@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Original-Received: from mail-sor-f41.google.com (mail-sor-f41.google.com. [209.85.220.41]) by mx.google.com with SMTPS id 5-v6sor1477359plx.112.2018.06.27.09.31.21 for (Google Transport Security); Wed, 27 Jun 2018 09:31:21 -0700 (PDT) Received-SPF: pass (google.com: domain of danielgutson@gmail.com designates 209.85.220.41 as permitted sender) client-ip=209.85.220.41; X-Received: by 2002:a17:902:9f81:: with SMTP id g1-v6mr6813470plq.304.1530117080915; Wed, 27 Jun 2018 09:31:20 -0700 (PDT) Original-Received: by 2002:a17:90a:987:0:0:0:0 with HTTP; Wed, 27 Jun 2018 09:31:20 -0700 (PDT) In-Reply-To: X-Original-Sender: danielgutson@gmail.com X-Original-Authentication-Results: mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=tIqV1dKr; spf=pass (google.com: domain of danielgutson@gmail.com designates 209.85.220.41 as permitted sender) smtp.mailfrom=danielgutson@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=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:38871 Archived-At: --00000000000012a676056fa22590 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Wed, Jun 27, 2018 at 1:28 PM, Daniel Gutson wrote: > > > On Wed, Jun 27, 2018 at 1:18 PM, Nicol Bolas wrote: > >> 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 t= o >>>> 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 t= his >> function. If it's not considered valid behavior, then it changes how use= rs >> 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 sys= tems; >>>> 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 reasona= ble >> 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? >> > > > namespace std { > > template< class InputIt*, class TerminationPolicy* > > constexpr *std::optional<*typename std::iterator_traits: > :difference_type*>* > distance( InputIt first, InputIt last, *TerminationPolicy&& > terminationPolicy* ); > > } > > I'm using 'optional' but could be 'expected' or 'outcome' depending on > their progress (I'm not up to date about them). > > How does that look? > I forgot to propose the interface of the policy: alternative - 1) bool TerminationPolicy::operator(), where 'true' means terminate. 2) bool TerminationPolicy::terminate(), true means terminate 3) bool TerminationPolicy::keep_running(), true means not to terminate. > > > >> -- >> You received this message because you are subscribed to the Google Group= s >> "ISO C++ Standard - Future Proposals" group. >> To unsubscribe from this group and stop receiving emails from it, send a= n >> 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/is >> ocpp.org/d/msgid/std-proposals/c3a0e827-0580-4c49-af1e- >> fd1b192f7734%40isocpp.org >> >> . >> > > > > -- > Who=E2=80=99s got the sweetest disposition? > One guess, that=E2=80=99s who? > Who=E2=80=99d never, ever start an argument? > Who never shows a bit of temperament? > Who's never wrong but always right? > Who'd never dream of starting a fight? > Who get stuck with all the bad luck? > --=20 Who=E2=80=99s got the sweetest disposition? One guess, that=E2=80=99s who? Who=E2=80=99d never, ever start an argument? Who never shows a bit of temperament? Who's never wrong but always right? Who'd never dream of starting a fight? Who get stuck with all the bad luck? --=20 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 e= mail 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/CAFdMc-1R3foMw2X5wdCp1b_g55cuEyW%2BGzPZr_e_YW3LF= FA1PA%40mail.gmail.com. --00000000000012a676056fa22590 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


On Wed, Jun 27, 2018 at 1:28 PM, Daniel Gutson <danielgutson@gmai= l.com> wrote:


On Wed, Jun 27, 2018 at 1:18 PM, Nicol Bolas <= jmckesson@gmail.co= m> wrote:
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 <= ;jmck...@gmail.com> wrote:
On Wednesday,= June 27, 2018 at 11:47:50 AM UTC-4, Daniel Gutson wrote:
Some functions may keep l= ooping for an unbounded amount of iterations, such as std::distance. This m= ay 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 leg= itimate 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 wil= l and will not be willing to call it.

So yes, thes= e are things that must be considered, even from a high level. They affect t= he usability of the tool. And since this tool exists purely for safety reas= ons, then such usability needs to be taken into account. There's no poi= nt in having "safe" interfaces nobody is willing to use, after al= l.

2. What is an appropriate &q= uot;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 wo= uld you tell them what the right "n" is?
=

There are two non-mutually-exclusive approaches about t= his.
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 bi= t after getting more consensus) could be to accept a caller-provided termin= ation_policy, and offer 3 basic policies (count-based, time-based, and an O= R-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 potenti= ally invalid iterators (and therefore is the code that has some idea of wha= t such boundary conditions ought to be) to the low-level code that will act= ually call `std::distance` (which probably has no idea what a reasonable bo= undary is).

Take `std::lower_bound`. It probab= ly uses `std::advance` or `std::next`, which would have similar boundary co= ndition functions. `lower_bound` has no idea what a reasonable bound= ary condition would be; only the caller would know. So do we now need a ver= sion of `lower_bound` that takes this boundary condition as an optional par= ameter?


namespace std {

template< class InputIt= , class TerminationPolicy >
constexpr std::optional&= lt;typename std::iterator_traits<InputIt>::difference_type>=C2=A0
=C2=A0 =C2=A0 distance( InputIt first, InputIt la= st, TerminationPolicy&& terminationPolicy );
=C2=A0
}

I'm using 'optional= 9; but could be 'expected' or 'outcome' depending on their = progress (I'm not up to date about them).

How = does that look?

I f= orgot to propose the interface of the policy: alternative -
1) bo= ol TerminationPolicy::operator(), where 'true' means termi= nate.
2) bool TerminationPolicy::terminate(), true means terminat= e
3) bool=C2=A0TerminationPolicy::keep_running(), true means no= t to terminate.
=C2=A0

=C2=A0

--
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-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/c3a0= e827-0580-4c49-af1e-fd1b192f7734%40isocpp.org.



<= /div>--
Who=E2=80= =99s got the sweetest disposition?
One guess, that=E2=80=99s who?
Who= =E2=80=99d never, ever start an argument?
Who never shows a bit of tempe= rament?
Who's never wrong but always right?
Who'd never dream= of starting a fight?
Who get stuck with all the bad luck?



--
Who=E2=80=99s got t= he sweetest disposition?
One guess, that=E2=80=99s who?
Who=E2=80=99d= never, ever start an argument?
Who never shows a bit of temperament?Who's never wrong but always right?
Who'd never dream of starti= ng a fight?
Who get stuck with all the bad luck?

--
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 h= ttps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAFdMc-1R3foMw2= X5wdCp1b_g55cuEyW%2BGzPZr_e_YW3LFFA1PA%40mail.gmail.com.
--00000000000012a676056fa22590-- .