Re: leakproof

I missed all the fun while the "leakproof" addition to function
attributes was being decided, so I know I'm late to the party. Today I
had to go and look up what it actually meant. I have to say that I was a
bit surprised. I expected it to refer to memory management in some way.
I don't honestly think "leakproof" as a term is going to convey much to
lots of people. Can we come up with a more descriptive term?

cheers

andrew

On Sun, Feb 19, 2012 at 5:29 PM, Andrew Dunstan <andrew(at)dunslane(dot)net> wrote:
> I missed all the fun while the "leakproof" addition to function attributes
> was being decided, so I know I'm late to the party. Today I had to go and
> look up what it actually meant. I have to say that I was a bit surprised. I
> expected it to refer to memory management in some way. I don't honestly
> think "leakproof" as a term is going to convey much to lots of people. Can
> we come up with a more descriptive term?

We bikeshed on that topic a while back and nobody suggested anything
that got more than 1 or 2 votes. But I'm still happy to rename it if
we can come up with something better, because I'm not in love with it
either.

Having now spent far too much time in bed with that patch, I'm feeling
like the concept that we are really looking for there is what some
languages call "pure" - that is, there must be no side effects,
whether by throwing exceptions or otherwise.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Sun, Feb 19, 2012 at 5:29 PM, Andrew Dunstan <andrew(at)dunslane(dot)net> wrote:
>> Can we come up with a more descriptive term?

> We bikeshed on that topic a while back and nobody suggested anything
> that got more than 1 or 2 votes. But I'm still happy to rename it if
> we can come up with something better, because I'm not in love with it
> either.

> Having now spent far too much time in bed with that patch, I'm feeling
> like the concept that we are really looking for there is what some
> languages call "pure" - that is, there must be no side effects,
> whether by throwing exceptions or otherwise.

Hmm, "pure" doesn't sound bad to me. Nice and short.

regards, tom lane

On Feb 19, 2012, at 5:42 PM, Tom Lane wrote:

> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>> Having now spent far too much time in bed with that patch, I'm feeling
>> like the concept that we are really looking for there is what some
>> languages call "pure" - that is, there must be no side effects,
>> whether by throwing exceptions or otherwise.
>
> Hmm, "pure" doesn't sound bad to me. Nice and short.
>

Technically, "pure" is stronger than "has no side effects":

http://en.wikipedia.org/wiki/Pure_function

Result can't depend on state (for instance, database contents), either. This is the typical definition used in functional programming.

gcc extends this to allow use of global variables in a "pure" function (the stricter definition is met by "const" functions). PG has "immutable", so a slightly weaker "pure" probably wouldn't be terribly confusing given the gcc precedent (probably across their family of compilers).

"D" adopts the stricter definition of "pure".

So there's some confusion around the term.

But …

I picked up this thread after "leakproof" was settled on and was curious as to what "leakproof" was supposed to be as I didn't read the earlier posts. I assumed it meant "doesn't leak memory", which seems admirable and typical and not needful of an attribute on the function declaration.

"pure" is definitely less confusing IMO, if it's congruent with the weaker sense of "pure" that's found in some languages/implementations.

----
Don Baccus
http://donb.photo.net
http://birdnotes.net
http://openacs.org

I suspect this is wrong for similar reasons as "pure" but I'll throw
it out there: "hermetic"

--
greg

Don Baccus <dhogaza(at)pacifier(dot)com> writes:
> On Feb 19, 2012, at 5:42 PM, Tom Lane wrote:
>> Hmm, "pure" doesn't sound bad to me. Nice and short.

> Technically, "pure" is stronger than "has no side effects":
> http://en.wikipedia.org/wiki/Pure_function
> Result can't depend on state (for instance, database contents), either. This is the typical definition used in functional programming.

Well, that condition is subsumed in our idea of an immutable function.
It's not clear to me whether pure/leakproof functions are meant to be a
strict subset of immutable functions, but if they are then they meet
this stricter definition. On the other hand, if pure/leakproof functions
don't have to be immutable but only stable, then the stricter definition
corresponds to "pure immutable". That still doesn't sound too bad, as
long as we define our terms clearly in the docs.

regards, tom lane

On Feb 19, 2012, at 7:24 PM, Tom Lane wrote:

> Don Baccus <dhogaza(at)pacifier(dot)com> writes:
>> On Feb 19, 2012, at 5:42 PM, Tom Lane wrote:
>>> Hmm, "pure" doesn't sound bad to me. Nice and short.
>
>> Technically, "pure" is stronger than "has no side effects":
>> http://en.wikipedia.org/wiki/Pure_function
>> Result can't depend on state (for instance, database contents), either. This is the typical definition used in functional programming.
>
> Well, that condition is subsumed in our idea of an immutable function.

Yes, I said that myself, perhaps you didn't bother to read closely?

> It's not clear to me whether pure/leakproof functions are meant to be a
> strict subset of immutable functions

Superset, not subset, unless my guessing is wrong. How could "pure" be a subset of "immutable"?

OK, at this point, proponents will explain why ...

But if you're not clear as to what a "leakproof" function is meant to be. then I suggest the definition must be defined very clearly, so everyone understands what it is meant to be.

> , but if they are then they meet
> this stricter definition. On the other hand, if pure/leakproof functions
> don't have to be immutable but only stable, then the stricter definition
> corresponds to "pure immutable". That still doesn't sound too bad, as
> long as we define our terms clearly in the docs.

Sure, let those making the proposal make things clear.

Just speaking as a gadfly who's not posted here for probably close on 10 years …

----
Don Baccus
http://donb.photo.net
http://birdnotes.net
http://openacs.org

On Sun, Feb 19, 2012 at 10:24 PM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Don Baccus <dhogaza(at)pacifier(dot)com> writes:
>> On Feb 19, 2012, at 5:42 PM, Tom Lane wrote:
>>> Hmm, "pure" doesn't sound bad to me.  Nice and short.
>
>> Technically, "pure" is stronger than "has no side effects":
>> http://en.wikipedia.org/wiki/Pure_function
>> Result can't depend on state (for instance, database contents), either.  This is the typical definition used in functional programming.
>
> Well, that condition is subsumed in our idea of an immutable function.
> It's not clear to me whether pure/leakproof functions are meant to be a
> strict subset of immutable functions, but if they are then they meet
> this stricter definition.  On the other hand, if pure/leakproof functions
> don't have to be immutable but only stable, then the stricter definition
> corresponds to "pure immutable".  That still doesn't sound too bad, as
> long as we define our terms clearly in the docs.

For the present application (pushdown into security views), we really
only care whether the function has side effects, such as throwing an
error or mutating global state. So, in theory, even a volatile
function could be leakproof - it could read (but not write) some piece
of global, volatile state. In practice, I'm not sure those cases are
important at all. Right now, the only things marked as leakproof are
relational operators that might be indexable, precisely so that we
might be able to push an indexable qual down far enough to allow an
index scan, even in the presence of an intervening security view.
Maybe someone will want to push down a qual like x > now() or x >
clock_timestamp(), but I guess I can't get that excited about that.
There are so few leakproof functions that the chances of making
pushdown work safely for much of anything beyond col = const seem
remote. So, my tea leaves are telling me that if we want to make pure
a subset of immutable, that probably isn't going to cause a problem.
However, I am not a CTLR (certified tea leaf reader).

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 2012-02-20 06:37, Don Baccus wrote:
> On Feb 19, 2012, at 7:24 PM, Tom Lane wrote:
>
>> It's not clear to me whether pure/leakproof functions are meant to be a
>> strict subset of immutable functions
> Superset, not subset, unless my guessing is wrong. How could "pure" be a subset of "immutable"?
If immutable functions are not necessarily leakproof/pure, and all
leakproof/pure functions are immutable.

If the latter is not the case, "pure" leads to confusion as well.

What about "discreet"?

-- Yeb

Greg Stark wrote:
> I suspect this is wrong for similar reasons as "pure" but I'll throw
> it out there: "hermetic"

I personally have no problem with "leakproof", but if it does not tickle
the right associations with many people:

What about "secure"? It is also not self-explanatory, but it might give
people the idea that it's more a problem of restricting access to
information
than anything else.

On the downside, "security" has been over- and abused so much already.

Yours,
Laurenz Albe

On mån, 2012-02-20 at 01:17 -0500, Robert Haas wrote:
> For the present application (pushdown into security views), we really
> only care whether the function has side effects, such as throwing an
> error or mutating global state.

How about [NO] SIDEEFFECTS?

Peter Eisentraut <peter_e(at)gmx(dot)net> writes:
> On mn, 2012-02-20 at 01:17 -0500, Robert Haas wrote:
>> For the present application (pushdown into security views), we really
>> only care whether the function has side effects, such as throwing an
>> error or mutating global state.

> How about [NO] SIDEEFFECTS?

Well, that's already stated to be one of the requirements for being
immutable or stable, so I think we need a term that's a bit stronger.

The real issue here is that the notion of what is a side effect is
much much broader than what we have used in the past. I don't think
we clarify that by continuing to use the same term "side effect".

regards, tom lane

On Sun, Feb 19, 2012 at 8:20 PM, Don Baccus <dhogaza(at)pacifier(dot)com> wrote:
>
> On Feb 19, 2012, at 5:42 PM, Tom Lane wrote:
>
>> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>>> Having now spent far too much time in bed with that patch, I'm feeling
>>> like the concept that we are really looking for there is what some
>>> languages call "pure" - that is, there must be no side effects,
>>> whether by throwing exceptions or otherwise.
>>
>> Hmm, "pure" doesn't sound bad to me.  Nice and short.
>>
>
> Technically, "pure" is stronger than "has no side effects":

+1 pure.

merlin

On Sun, Feb 19, 2012 at 6:20 PM, Don Baccus <dhogaza(at)pacifier(dot)com> wrote:
>
> On Feb 19, 2012, at 5:42 PM, Tom Lane wrote:
>
>> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>>> Having now spent far too much time in bed with that patch, I'm feeling
>>> like the concept that we are really looking for there is what some
>>> languages call "pure" - that is, there must be no side effects,
>>> whether by throwing exceptions or otherwise.
>>
>> Hmm, "pure" doesn't sound bad to me.  Nice and short.
>>
>
> Technically, "pure" is stronger than "has no side effects":
>
> http://en.wikipedia.org/wiki/Pure_function
>
> Result can't depend on state (for instance, database contents), either.  This is the typical definition used in functional programming.
>
> gcc extends this to allow use of global variables in a "pure" function (the stricter definition is met by "const" functions).  PG has "immutable", so a slightly weaker "pure" probably wouldn't be terribly confusing given the gcc precedent (probably across their family of compilers).
>
> "D" adopts the stricter definition of "pure".
>
> So there's some confusion around the term.
>
> But …
>
> I picked up this thread after "leakproof" was settled on and was curious as to what "leakproof" was supposed to be as I didn't read the earlier posts.  I assumed it meant "doesn't leak memory", which seems admirable and typical and not needful of an attribute on the function declaration.
>
> "pure" is definitely less confusing IMO, if it's congruent with the weaker sense of "pure" that's found in some languages/implementations.

I don't think that "pure" is sufficient to be leakproof. For example,
if I have a function which is pure but which takes an unusually long
time to evaluate for some unique pathological combination of
arguments, I don't think that it would be considered leakproof.

Cheers,

Jeff

On Tue, Feb 21, 2012 at 11:54 AM, Jeff Janes <jeff(dot)janes(at)gmail(dot)com> wrote:
> I don't think that "pure" is sufficient to be leakproof.  For example,
> if I have a function which is pure but which takes an unusually long
> time to evaluate for some unique pathological combination of
> arguments, I don't think that it would be considered leakproof.

I think we've made up our mind to largely ignore such cases, though.
There may be information that gets leaked either through the choice of
plan or the time it takes to execute it, but plugging that type of
hole completely is almost impossible. Suppose the security view
filters for rows where user = 'rhaas' and the evil rhaas requests rows
where id = 5. The planner chooses an index-scan on id = 5 and then
applies a filter of user = 'rhaas' to the result. There's probably
some slight timing difference between the case where no id = 5 row
exists, and the case where it exists but does not have user = 'rhaas',
so a sufficiently dedicated hacker might be able to employ a timing
attack to determine the existence of such a row. Also, by jiggering
with page costs and EXPLAIN, they might be able to get some idea of
the number of rows in the table.

I don't believe that this makes the feature useless, though. In most
cases, and especially when using surrogate keys (which I typically do,
whether Josh Berkus likes it or not), the existence of the row is not
a terribly interesting piece of information: it's the content of the
row that's sensitive. Neither table-level security nor column-level
security attempt to prevent you from determining that the table or
column exists; they just hide its contents. And if you need to bar
EXPLAIN so people can't peek at query plans, it's certainly possible
to do that using ProcessUtility_hook. If you're worried about more
subtle timing attacks, you should probably rethink the idea of letting
people log into the database in the first place.

Anyway, to your point, I suppose I might hesitate to mark factorial
leak-proof even if it didn't throw an error on overflow, because the
time it takes to return an answer for larger inputs does grow rather
rapidly. But it's kind of a moot point because the error makes it not
leak-proof anyway. So maybe we're just splitting hairs here, however
we decide to label this.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> Anyway, to your point, I suppose I might hesitate to mark factorial
> leak-proof even if it didn't throw an error on overflow, because the
> time it takes to return an answer for larger inputs does grow rather
> rapidly. But it's kind of a moot point because the error makes it not
> leak-proof anyway. So maybe we're just splitting hairs here, however
> we decide to label this.

Speaking of hair-splitting ...

A strict interpretation of "no errors can be thrown" would, for example,
rule out any function that either takes or returns a varlena datatype,
since those are potentially going to throw out-of-memory errors if they
can't palloc a result value or a temporary detoasted input value.
I don't suppose that we want that, which means that this rule of thumb
is wrong in detail, and there had better be some more subtle definition
of what is okay or not, perhaps along the line of "must not throw any
errors that reveal anything useful about the input value". Have we got
such a definition? (I confess to not having followed this patch very
closely.)

regards, tom lane

On 02/22/2012 10:21 AM, Tom Lane wrote:
> Robert Haas<robertmhaas(at)gmail(dot)com> writes:
>> Anyway, to your point, I suppose I might hesitate to mark factorial
>> leak-proof even if it didn't throw an error on overflow, because the
>> time it takes to return an answer for larger inputs does grow rather
>> rapidly. But it's kind of a moot point because the error makes it not
>> leak-proof anyway. So maybe we're just splitting hairs here, however
>> we decide to label this.
> Speaking of hair-splitting ...
>
> A strict interpretation of "no errors can be thrown" would, for example,
> rule out any function that either takes or returns a varlena datatype,
> since those are potentially going to throw out-of-memory errors if they
> can't palloc a result value or a temporary detoasted input value.
> I don't suppose that we want that, which means that this rule of thumb
> is wrong in detail, and there had better be some more subtle definition
> of what is okay or not, perhaps along the line of "must not throw any
> errors that reveal anything useful about the input value". Have we got
> such a definition? (I confess to not having followed this patch very
> closely.)
>
>

Yeah.

Returning to the original point, I've come to the conclusion that "pure"
isn't the right way to go. The trouble with "leakproof" is that it
doesn't point to what it is that's not leaking, which is information
rather than memory, as many might imagine (and I did) without further
hints. I'm not sure any single English word would be as descriptive as
I'd like.

cheers

andrew

Andrew Dunstan <andrew(at)dunslane(dot)net> wrote:

> Returning to the original point, I've come to the conclusion that
> "pure" isn't the right way to go. The trouble with "leakproof" is
> that it doesn't point to what it is that's not leaking, which is
> information rather than memory, as many might imagine (and I did)
> without further hints. I'm not sure any single English word would
> be as descriptive as I'd like.

Discreet?

http://www.merriam-webster.com/dictionary/discreet

I guess the risk is that people would confuse it with "discrete".

-Kevin

On 02/22/2012 11:14 AM, Kevin Grittner wrote:
> Andrew Dunstan<andrew(at)dunslane(dot)net> wrote:
>
>> Returning to the original point, I've come to the conclusion that
>> "pure" isn't the right way to go. The trouble with "leakproof" is
>> that it doesn't point to what it is that's not leaking, which is
>> information rather than memory, as many might imagine (and I did)
>> without further hints. I'm not sure any single English word would
>> be as descriptive as I'd like.
>
> Discreet?
>
> http://www.merriam-webster.com/dictionary/discreet
>
> I guess the risk is that people would confuse it with "discrete".
>

Yes, too confusing.

"silent" might be better along those lines.

cheers

andrew

On Wed, Feb 22, 2012 at 10:21 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Robert Haas <robertmhaas(at)gmail(dot)com> writes:
>> Anyway, to your point, I suppose I might hesitate to mark factorial
>> leak-proof even if it didn't throw an error on overflow, because the
>> time it takes to return an answer for larger inputs does grow rather
>> rapidly.  But it's kind of a moot point because the error makes it not
>> leak-proof anyway.  So maybe we're just splitting hairs here, however
>> we decide to label this.
>
> Speaking of hair-splitting ...
>
> A strict interpretation of "no errors can be thrown" would, for example,
> rule out any function that either takes or returns a varlena datatype,
> since those are potentially going to throw out-of-memory errors if they
> can't palloc a result value or a temporary detoasted input value.
> I don't suppose that we want that, which means that this rule of thumb
> is wrong in detail, and there had better be some more subtle definition
> of what is okay or not, perhaps along the line of "must not throw any
> errors that reveal anything useful about the input value".  Have we got
> such a definition?  (I confess to not having followed this patch very
> closely.)

Not exactly; I've kind of been playing it by ear, but I agree that
out-of-memory errors based on the input value being huge are probably
not something we want to stress out about too much. In theory you
could probe for the approximate size of the value by using up nearly
all the memory on the system, leaving a varying amount behind, and
then see whether you get an out of memory error. But again, if people
are going to that kind of trouble to ferret out just the approximate
size of the data, it was probably a bad idea to let them log into the
database at all, in any way, in the first place.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

* Andrew Dunstan wrote:

> Returning to the original point, I've come to the conclusion that
> "pure" isn't the right way to go. The trouble with "leakproof" is that
> it doesn't point to what it is that's not leaking, which is
> information rather than memory, as many might imagine (and I did)
> without further hints. I'm not sure any single English word would be
> as descriptive as I'd like.

Jumping into the bikeshedding here, I'm not convinced that all that
many users would immediately jump to the wrong conclusion (that being
"free of memory leaks"). Rather the opposite, indeed.

IMHO, you may be looking at this through "C developer colored
glasses", where any "leak" must immediately and without doubt be a
resource leak of some kind. As Don Baccus pointed out, it would be a
highly unusual function that was not at least intended to be free of
memory leaks.

A DBA, on the other hand, might -- and, again, this is MHO only -- not
decide what the attribute must mean without consulting the
documentation. If she was especially concerned about information
security/data protection, she might even guess right about what kind
of "leak" is meant. There is no chance of that with terms like SILENT
or PURE.

Of all the suggestions I have seen in this thread, I think LEAKPROOF
is actually the best fit for the purpose. My favorite alternative,
just to suggest one, would be NONDISCLOSING/NOT DISCLOSING, but I
prefer LEAKPROOF even over that, not just because it's shorter.

--
Christian Ullrich

On ons, 2012-02-22 at 10:56 -0500, Andrew Dunstan wrote:
> The trouble with "leakproof" is that it
> doesn't point to what it is that's not leaking, which is information
> rather than memory, as many might imagine (and I did) without further
> hints. I'm not sure any single English word would be as descriptive as
> I'd like.

Well, we have RETURNS NULL ON NULL INPUT, so maybe DOES NOT LEAK
INFORMATION. ;-)

On Feb 26, 2012, at 10:39 AM, Peter Eisentraut wrote:

> On ons, 2012-02-22 at 10:56 -0500, Andrew Dunstan wrote:
>> The trouble with "leakproof" is that it
>> doesn't point to what it is that's not leaking, which is information
>> rather than memory, as many might imagine (and I did) without further
>> hints. I'm not sure any single English word would be as descriptive as
>> I'd like.
>
> Well, we have RETURNS NULL ON NULL INPUT, so maybe DOES NOT LEAK
> INFORMATION. ;-)

If you are willing to go full length, then the computer science term is "referential transparency", no?

http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)

So a function could be described as "REFERENTIALLY TRANSPARENT".

Cheers,
M

On Sun, Feb 26, 2012 at 6:44 PM, A.M. <agentm(at)themactionfaction(dot)com> wrote:
> If you are willing to go full length, then the computer science term is "referential transparency", no?
>
> http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)
>
> So a function could be described as "REFERENTIALLY TRANSPARENT".

Hmm, I think that's very close to what we're looking for. It might be
slightly stronger, in that it could conceivably be OK for a leakproof
function to read, but not modify, global variables... but I can't
think of any particular reason why we'd want to allow that case.
OTOH, it seems to imply that referential transparency is a property of
expressions built from pure functions, and since what we're labeling
here are functions, that brings us right back to PURE.

I'm thinking we should go with PURE. I still can't think of any real
use case for pushing down anything other than an immutable function,
and I think that immutable + no-side-effects = pure.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Sun, Feb 26, 2012 at 6:44 PM, A.M. <agentm(at)themactionfaction(dot)com> wrote:
>> http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)
>> So a function could be described as "REFERENTIALLY TRANSPARENT".

> Hmm, I think that's very close to what we're looking for. It might be
> slightly stronger, in that it could conceivably be OK for a leakproof
> function to read, but not modify, global variables... but I can't
> think of any particular reason why we'd want to allow that case.
> OTOH, it seems to imply that referential transparency is a property of
> expressions built from pure functions, and since what we're labeling
> here are functions, that brings us right back to PURE.

Yeah. Comparing that page to the one on pure functions, there doesn't
seem to be any difference that is relevant to what we're concerned
about. And neither page directly addresses the question of error
conditions, though if you hold your head at the proper angle you might
argue that that's implicit in the "no side effect" rule. But I think
we're going to have to clearly document that requirement no matter
what term we choose.

> I'm thinking we should go with PURE.

Works for me.

regards, tom lane

On 02/26/2012 08:23 PM, Tom Lane wrote:
> Robert Haas<robertmhaas(at)gmail(dot)com> writes:
>> On Sun, Feb 26, 2012 at 6:44 PM, A.M.<agentm(at)themactionfaction(dot)com> wrote:
>>> http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)
>>> So a function could be described as "REFERENTIALLY TRANSPARENT".
>> Hmm, I think that's very close to what we're looking for. It might be
>> slightly stronger, in that it could conceivably be OK for a leakproof
>> function to read, but not modify, global variables... but I can't
>> think of any particular reason why we'd want to allow that case.
>> OTOH, it seems to imply that referential transparency is a property of
>> expressions built from pure functions, and since what we're labeling
>> here are functions, that brings us right back to PURE.
> Yeah. Comparing that page to the one on pure functions, there doesn't
> seem to be any difference that is relevant to what we're concerned
> about. And neither page directly addresses the question of error
> conditions, though if you hold your head at the proper angle you might
> argue that that's implicit in the "no side effect" rule. But I think
> we're going to have to clearly document that requirement no matter
> what term we choose.
>
>> I'm thinking we should go with PURE.
> Works for me.
>
>

Not for me. My objection is the same as when I started this thread -
that the term doesn't convey to someone just looking at it the salient
point about the feature, any more then LEAKPROOF does. SILENT strikes me
as much closer to what is actually described.

cheers

andrew