[langsec-discuss] Is computation half the story?

Taylor Hornby havoc at defuse.ca
Fri Mar 27 00:22:59 UTC 2015

I wrote a blog post...


...wherein I make the distinction between a machine's computational
abilities (i.e. which languages can it decide?) and a machine's
"informational" abilities (i.e. how can the machine influence the
outside world? what APIs is it allowed to call?).

I chose the the term "informational" for lack of a better word because
it is about information entering and exiting the machine, or moving
between "parts" of the machine.

I concluded the post by claiming computer science has no general theory*
of this property. We understand computation well from computability and
complexity theory, but "informational" capabilities are only understood
through limited models like ACLs, Bell-LaPaudula, noninterference, etc.

Those models are properties systems should have in order to be called
secure. I'm thinking more along the lines of starting with a given
system then quantifying its its "power" and proving theorems about what
it can and can't do. Most importantly, relating the power of one given
system to another given system.

The models we have lack completeness and generality. There is no
equivalent to the Church-Turing thesis for informational capabilities.
There are no theorems about what happens when we "nest" systems. (Think
about questions like: If System B is a process running on System A, is
System A free of covert channels if-and-only-if System B is?).

So: Am I right about this? Are we really missing half of the picture? Or
do the models we have satisfy our needs? Has it been proven that no such
theory can exist, or if it did it couldn't be useful?

I would appreciate references to the literature.

If what I am saying makes any sense at all, I propose we stop thinking
of "access control"-type notions as part of information security.
Instead, they should be studied as a fundamental part of computer
science, in complete generality (not an easy task!).

- Taylor

* By "theory" I mean a general system of knowledge and understanding.
Think "theory of evolution", not "theorems."

More information about the langsec-discuss mailing list