Commutative Filters for Reducing Inference Threats in Multilevel Database Systems

Disclosure of classified data in multilevel database systems is threatened by direct user access, user inference, Trojan Horse release, and Trojan Horse leaks. Earlier work showed how the problems of direct user access and Trojan Horse release can be solved by using a trusted filter and cryptographic checksums, but left the problems of inference and leaks open. We now show how the problem of user inference can be solved with the concept of a commutative filter that ensures that the result returned to a user is equivalent to one that would have been obtained had the query been posed against an authorized view of the database. The technique allows query selections, some projections, query optimization, and subquery handling to be performed by the database system. It does not solve the Trojan Horse leakage problem.