Learning the secret from the rows you are allowed to see

The attack in which nothing is ever denied

Inference is performing authorized queries and deducing unauthorized information from the legitimate answers. The route from one to the other is called an inference channel, and the two classic techniques are analysing functional dependencies between attributes and merging views that share a constraint.

What makes inference hard to defend is not that the attacker is clever. It is that every individual query is permitted. Access control answers the question "may this subject read this row?", and inference is a question about the rows that are not there. Removing a row from a result set is itself an act of communication.

Worked example — a row-level restriction on a air-freight manifest

You administer the database of a defence air-freight operation. A table named manifest records what is loaded aboard each outbound aircraft. Each row is a single shipment; it names the hold it occupies, the contents, a classification, and a flight identification number that cross-references other tables holding the aircraft type, origin, destination and flight time. One structural fact matters enormously: only one shipment per hold is allowed.

Flight 3308 is loaded as follows:

Two roles exist. Role A has full rights over the table. Role B has full rights over only those rows whose Classification is Unclassified — a content-dependent, row-level restriction, implemented as a view or a row-level policy.

Now put yourself in Role B and try to establish whether a classified shipment is aboard.

Step 1 — the permitted query.

SELECT hold, contents FROM manifest WHERE flight_id = 3308;

The restriction silently filters the result. Three rows come back: holds A, C and D.

Step 2 — external knowledge, from tables you are allowed to read. The flight identification number cross-references the aircraft record, which gives the airframe type, which gives the number of cargo holds: four, lettered A to D. Nothing about that lookup is restricted.

Step 3 — the inference. Take the difference. You can see three of the four holds. Hold B is missing from your result. Because only one shipment is allowed per hold, and because the table records shipments rather than holds, the absence of hold B means one of two things: either hold B is empty, or hold B contains a shipment whose row is being withheld. And a row is withheld only when its classification is not Unclassified. If you can establish that the aircraft departed loaded — which the flight record itself will tell you — then hold B is occupied by a shipment you are not cleared to see. A classified shipment is aboard.

No restricted row was ever accessed. Every query returned exactly what policy said it should. The disclosure is in the shape of the gap.

Step 4 — two more probes that leak the same fact. A SELECT COUNT(*) FROM manifest WHERE flight_id = 3308 may well be evaluated against the whole table rather than the filtered view, in which case it answers 4 while a SELECT of the rows answers with three — the discrepancy alone is the disclosure. Aggregates are metadata about rows you cannot see, and SUM(weight) leaks the same way.

Better still, and this is the sharpest form: try to insert a row.

INSERT INTO manifest (flight_id, hold, contents, classification)
     VALUES (3308, 'B', 'test crate', 'Unclassified');

The primary key is (flight_id, hold). If the insert is rejected as a duplicate key, a row exists at (3308, 'B') that you cannot see — and the constraint engine has told you so. If it is accepted, the hold was genuinely empty. The integrity subsystem must enforce uniqueness against the whole table, not against your view, or the table would stop being a table. The classification hides the data; it cannot hide the key.

Why the obvious fixes fail

"Hide the hold letters." Take the hold column out of Role B's view and the counting attack still works: three visible rows against a known four-hold airframe gives the same conclusion without ever naming a hold.

"Split the table." The classic remedy for inference is to break the sensitive linkage into a separate, administrator-only table. It works — until somebody adds a harmless-looking attribute, a load date or a handling code, to the wrong side. An easily discoverable value then re-establishes the forbidden association, and the DBMS cannot detect this from its own metadata, because nothing in the schema records that one attribute is inferable from another.

The two real countermeasure families are inference detection at design time — split tables, finer-grained roles, at the cost of unnecessarily strict controls and reduced availability — and at query time, denying or altering a query that would open a channel. Both need a detection algorithm, and detecting inference channels in general is an open research problem.

Polyinstantiation is the mechanism built for exactly this gap: the database stores two rows with the same key at different classification levels — a cover story at the low level and the truth at the high one. Role B sees hold B occupied by spare pallets, Unclassified; Role A sees the real load. The counting attack now returns four rows and finds no gap, and the insert probe collides with a row Role B can actually see. The cost is exactly what it looks like: the low-level view of the database is deliberately false. Every application, report and downstream system reading at that level is being lied to by design, and somebody has to maintain the lie. That is a real price, and an answer that recommends polyinstantiation without naming it has not finished the argument.

The honest third option is to accept that the schema itself leaks — that a table keyed on a physical resource with a fixed, publicly known cardinality cannot hide the occupancy of that resource from anyone who can count — and to classify the whole flight rather than individual shipments.