PostgreSQL: When a Timing Difference Becomes a Search Oracle
PostgreSQL row-level security is meant to make unauthorized rows unavailable to a user, but the relevant question is whether those rows can still affect the work performed for an allowed query. This chapter follows the timing mechanism behind that question and then shows why range predicates and conjunctions make it more serious than a one-value membership test. The practical judgment is conditional: the channel depends on optimizer behavior, query access, workload, and indexing, and a useful mitigation has to change that dependency rather than merely hope noise will hide it.
How optimizer work becomes a timing signal
Row-level security, or RLS, attaches a policy to a table. In a hospital-style example, a doctor may be allowed to see patients associated with their own clinic and not patients belonging to another clinic. The doctor can issue a permitted query against the table, but the policy should ensure that only authorized rows are returned.
The difficulty begins with the order in which the database evaluates conditions. A modern database does not necessarily execute a query in the textual order in which it was written. Its optimizer chooses a physical plan, often using indexes to avoid scanning every row. That flexibility is valuable for performance. It also means that a user-supplied condition can sometimes be evaluated before the RLS policy if the condition uses operators considered LEAKPROOF and can be handled by an index.
“Leakproof” here has a precise, limited meaning. It refers to operators that are not expected to expose observable side effects directly, so PostgreSQL can allow the optimizer to reorder them relative to the security policy. Equality and comparison operators are examples cited in the study. The designation does not mean that the entire query is incapable of leaking information. It means the planner is allowed to treat that predicate as safe to push down for execution. The performance optimization can therefore create the conditions for a different, indirect signal.
Suppose the user submits a predicate Q against table T, protected by policy P. If the database evaluates Q over the table first and applies P afterward, the time for the request contains at least two kinds of work: the work needed to find the matches and the work needed to apply the policy to those matches. The second part depends on the size of the intermediate result Q(T). A private row that will eventually be removed can still increase the amount of policy evaluation.
The visible distinction is between two cases that return the same content. A query that matches nothing produces an empty intermediate result. A query that matches a hidden row produces a nonempty intermediate result, which RLS then removes. If policy evaluation takes measurably longer for the second case, the caller can distinguish “no row matched” from “a row matched but I am not allowed to see it.” The caller has learned a membership fact without receiving the row.
The researchers describe a calibrated timing test rather than relying on an absolute duration. One calibration query is known to match zero rows. Another is known to match one row. The candidate query is run in the same general environment, and the observed times are compared with the gap between those reference cases. In their formulation, repeated trials and a threshold help separate the nonexistent distribution from the distributions for authorized and unauthorized matches. The signal comes from the extra policy work, not from a direct read of hidden contents.
Calibration matters because network timing is noisy. A database server may be handling other requests, a virtual machine may be contending for resources, and the route between client and server may vary. A single slow response proves little. The attack becomes meaningful only when the distributions remain distinguishable enough for repeated measurements to classify candidate predicates more often than chance. That is an empirical property of the deployment, not a theorem that every RLS query has a useful timing gap.
The same point explains why simply saying “the policy is correct” is insufficient. The policy can correctly remove the unauthorized row at the result boundary. The optimizer can also correctly choose an index plan according to its performance rules. The leak arises from their interaction: a predicate is evaluated over a shared table, and the cost of the later policy check depends on what the first step found. Correct local decisions can compose into an observable cross-boundary effect.
One obvious response is to force the policy to be evaluated before user-supplied predicates. That makes the query operate on authorized rows first and can remove this particular timing distinction. The cost is substantial: the optimizer loses freedom to push conditions into useful indexes, and the database may need a sequential scan of the table for each query. Security and performance are now competing properties of the same execution plan rather than independent settings.
From a timing bit to rows
An equality-based oracle answers a narrow question: does a chosen value occur in a hidden row? If the possible values are few and known, testing them one by one may be enough. High-entropy fields are different. An identifier or other sensitive attribute can have a large domain, and guessing every possible value is infeasible. The important escalation in the PostgreSQL study comes from asking questions about sets of values rather than one value at a time.
For an ordered attribute, a range predicate can divide the domain. The caller asks whether any hidden value lies below a chosen split point, or within one of two halves. If the timing test indicates that one half contains a match, that half becomes the next search interval. Repeating the process narrows the interval roughly as binary search does. A domain that would require an enormous number of equality guesses can be searched with a number of probes related to the logarithm of its size, multiplied by the number of values actually present.
The distinction between domain size and support size is useful. The domain is every value the field could contain. The support is the subset that actually appears in the table. When the domain is large but the support is sparse, the range strategy avoids spending time on empty portions. The study reports this advantage for high-entropy, sparse attributes such as an SSN-like field. It also reports the opposite case: when the domain is already densely populated, as with a dense ZIP-code-like field, linear probing may be practical and binary search can add overhead rather than remove it.
A range query is therefore more than a faster version of an equality query. It changes the information structure of the question. Equality asks whether one point is occupied. A range asks whether any point in an interval is occupied, which gives the caller a way to choose the next interval based on the previous answer. The side channel supplies the yes-or-no signal; the expressive predicate supplies the search strategy.
Recovering values independently is not yet the same as recovering records. Suppose the caller learns that several patient ages, locations, or identifiers occur somewhere in the hidden part of a table. Those values may belong to different rows. To assemble rows, the study uses conjunctions: predicates that require a particular combination of values to occur together. A partial candidate is extended one attribute at a time, and the timing oracle tests whether a set of possible next values co-occurs with the values already selected.
This step is where the database's physical plan affects both efficiency and reliability. With several single-column indexes, PostgreSQL may perform separate index scans and intersect their results. The cost of an empty conjunction can depend on the sizes of the intermediate scans, not only on whether the final intersection is empty. A predicate whose first condition matches many rows and whose second condition matches none can take more work than a predicate for which both conditions quickly find nothing.
The researchers therefore find that selectivity—the ability of a condition to reduce the candidate set—matters. Starting with a unique or near-unique attribute keeps later intermediate results small. Adding less selective attributes afterward makes the timing distinction more stable and reduces unnecessary work. The ordering is not a cosmetic optimization. It affects whether the oracle can reliably distinguish an empty candidate from a candidate that reaches policy evaluation, and it changes how many queries are needed to construct rows.
The combined process has two conceptual phases. First, enumerate the values present in each attribute by splitting ordered domains. Second, assemble compatible combinations with conjunctions. A brute-force Cartesian product would test every combination of recovered values and quickly become impractical. Adaptive partitioning of candidate sets reduces the work by asking whether either half can extend a surviving partial tuple, then recursing only into halves that appear viable. The result can be full candidate rows even though no unauthorized row was ever returned as a result.
The paper's measurements put boundaries around that claim. The authors use a controlled hospital electronic-medical-record-style schema with indexed patient attributes and a large synthetic table. They examine CPU load from other tenant activity, network distance, worker parallelism, and different attribute densities. Higher load and longer network paths reduce classification accuracy, while additional repetitions can partly compensate. Parallel workers can reduce elapsed time, but too many workers create their own database contention and degrade accuracy. The adaptive nature of the attack also means that small errors can compound: a false negative high in a range-search tree can discard an entire region of the domain.
Those qualifications do not make the result irrelevant. They explain what must be measured in a real deployment. A system with a noisy network, a narrow query interface, aggressive rate limits, or frequent workload changes may make the demonstrated strategy harder to use. A system with direct query access, stable indexes, exposed timing, and rich predicates presents a more favorable environment. The evidence supports a practical risk under the studied conditions, not a universal exploitability label for every RLS deployment.
The structural mitigation is correspondingly specific. For a policy that restricts rows by tenant or clinic, the authors combine a composite index with the tenant attribute first and a policy expression written so the optimizer can see the tenant constraint. The goal is to make tenant selection part of the same index access as the attacker-selected attribute. A query for an attribute value is then scoped to the caller's tenant before it evaluates that value against other tenants' rows. In the reported benchmark, the combined design removes the useful distinction; the oracle performs no better than random guessing. Changing only the index or only the policy expression is not enough in that scenario.
This is a stronger defense than adding random delay because it changes which records participate in the relevant access path. It is not a universal replacement for RLS. Policies that depend on complex per-row logic may not translate into a leading-index constraint. Maintaining tenant-leading composite indexes for many attributes can be expensive, and those indexes can make non-RLS queries less convenient or slower because an attribute is no longer contiguous by itself. Operators may have to choose which fields deserve the structural protection and which costs they can accept.
The durable lesson is not that time is always secret, nor that RLS is useless. It is that a policy can remove a row from the answer while the query plan still lets that row determine how much work the database performs. Rich predicates then turn that difference into a sequence of questions, and the sequence can be more revealing than any one response. To judge the risk, inspect the allowed query surface, the physical access path, the workload noise, and whether the mitigation removes hidden-data participation or merely makes it harder to measure.