[v9.2] Fix leaky-view problem, part 1

From: Kohei Kaigai <Kohei(dot)Kaigai(at)EMEA(dot)NEC(dot)COM>
To: Robert Haas <robert(dot)haas(at)enterprisedb(dot)com>, Stephen Frost <sfrost(at)snowman(dot)net>, Heikki Linnakangas <heikki(dot)linnakangas(at)enterprisedb(dot)com>, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: pgsql-hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: [v9.2] Fix leaky-view problem, part 1
Date: 2011-06-06 12:37:11
Message-ID: A9F5079BABDEE646AEBDB6831725762C556026245A@EUEXCLU01.EU.NEC.COM
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

This patch enables to fix up leaky-view problem using functions with tiny cost estimation scenario.

The point of this scenario is criteria to reorder qualifiers of scanning plan in order_qual_clauses(). The optimizer may pull up simple subqueries into upper level, then its qualifier will get merged with ones in the upper level. When executor scans a relation, qualifiers with smaller cost shall be executed earlier to minimize cost to filter out invisible tuples. However, we know unpreferable side-effects when we use a view for row-level security.
Even if a certain subquery rewritten from a view is defined for row-level security, a function with tiny cost appended from outside of the view may executed earlier than qualifiers to perform as security policy of the view, as long as the view is enough simple and the supplied function has tiny cost. In the result, this function can see the arguments come from invisible tuples, and leak them into somewhere.

The solution is quite simple. This patch enables to track original depth of qualifiers and modify criteria to sort qualifiers in order_qual_clauses().
Even if a function with tiny cost is supplied from outside of views, the patched optimizer does not prioritize cost estimation more than the depth.

It fixes up the scenario [1] in the bellow descriprions.

--------
The background of the leaky-view problem is well summarized at:
http://wiki.postgresql.org/wiki/RLS

We had discussed several scenarios in v9.1 development cycle, and the last developer meeting. We almost concluded the following criteria to characterize whether a leak-view scenario is problematic to be fixed, or not.
* If unprived user can directly reference contents of invisible tuples, it is a problem to be fixed.
* As long as contents of invisible tuples are consumed by internal stuff (eg, index-access method), it is not a problem to be fixed.

Thus, the scenario [1] and [2] are problematic to be fixed, but [3] and [4] are not. So, I'll try to fix up these two scenario with the patch part-1 amd part-2.

[1] unexpected reorder of functions with tiny-cost and side-effects

Qualifiers of WHERE or JOIN ... IN clause shall be sorted by estimated cost, not depth of nest level. Thus, this logic can make order reversal when user-given qualifier has smaller cost than qualifiers to perform as security policy inside of view.
In the result, these qualifiers can reference both of visible and invisible tuples prior to the filtering by row-level security policy of the view. Thus, this behavior can be used to leak contents of invisible tuples.

[2] unexpected push-down of functions with side-effect into join-loop

If arguments of qualifier being appended on outside of join-loop references only one-side of the join-loop, it is a good strategy to distribute this qualifier into inside of the join-loop to minimize number of tuples to be joined, from the viewpoint of performance.
However, it also makes order reversal when the join-loop is a part of view definition that should perform row-level security policy. Then, these exogenetic qualifiers may be executed prior to the filtering by row-level security policy of the view. Thus, this behavior can be used to leak contents of invisible tuple.

[3] estimation of hidden value using iteration of PK/FK proves

Due to the nature of PK/FK constraints, we can infer existence of key values being stored within invisible tuple, even if we never allows users to reference contents of invisible tuples.
We commonly call this type of information leaks "covert-channel", and it is basically impossible to prevent according to the previous security research, however, its risk is also relatively small because of slow bandwidth to leak.
We already made consensus this scenario is not a problem to be fixed.

[4] estimation of hidden value using statistics

One example was selectivity-estimator function; that may reference statistical information delivered from the tables have invisible tuples for optimization. Here are two points to be considered. The one is purely internal stuff may be able to reference invisible tuples, however, it is not a problem as long as it does not leak them into end-users; such as index access methods. The second is statistical or other form of date delivered from invisible tuples. We can set up a table that contains data delivered from invisible tuples using row-level triggers, however, it is quite a matter of database administration. Unless owner of tables set up such a leakable configuration, other users cannot reference them.

Thanks,
--
NEC Europe Ltd, SAP Global Competence Center
KaiGai Kohei <kohei(dot)kaigai(at)emea(dot)nec(dot)com>

Attachment Content-Type Size
pgsql-fix-leaky-view-part-1.patch application/octet-stream 29.7 KB

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Kohei Kaigai 2011-06-06 12:37:13 [v9.2] Fix leaky-view problem, part 2
Previous Message Heikki Linnakangas 2011-06-06 12:18:20 Re: reducing the overhead of frequent table locks - now, with WIP patch