Computer Security Art and Science, 2nd Edition

Chapter 3

Foundational Results

MARIA: Ay, but you must confine yourself within the modest limits of order.

— Twelfth Night, I, iii, 8–9.

In 1976, Harrison, Ruzzo, and Ullman [874] proved that the security of computer systems was undecidable in the general case and explored some of the limits of this result. In that same year, Jones, Lipton, and Snyder [972] presented a specific system in which security was not only decidable, but decidable in time linear with the size of the system. Minsky [1354] suggested a third model to examine what made the general, abstract case undecidable but at least one specific case decidable. Sandhu [1657] devised a related model extending the decidability results to a large class of systems.

These models explore ...