Lattice Model of Information Flow

Posted on Mon 24 January 2011 in Rumination

I am caught in a maelstrom of work and so I decide to play.

I have an excellent textbook on discrete mathematics on my shelf from a course I took as a student a few years ago [1]. Its always useful to review such books to remind oneself of certain foundational principles used in computer science [2]. My thesis work concerns, among other things, the study of information flow and in the course of my work I found myself consulting this book to review the mathematical concept of a lattice [3]. Looking through the index of this text I found an entry reading 'Information flow, lattice model of, 525'. Naturally, I was intrigued.

Funnily enough, the three paragraph section on the lattice model of information flow is only of tangential relevance to my thesis work; yet it was interesting enough. It discussed the uses of lattices to model security policies of information dissemination. Rosen presented a simple model of a multi-level security policy in which a collection data (the authors use the word information) is assigned an authority level A, and a category C. The security class of a collection of data is modeled as the pair \( (A,C)\). Rosen defines a partial order on security classes as follows: \( (A_{1},C_{1})\preceq (A_{2},C_{2})\) if and only if \( A_{1} \leq A_{2}\) and \( S_{1} \subseteq S_{2}\). This is easily illustrated by an example.

Let \( A = \{A_{1}, A_{2}\}\) where \( A_{1} \leq A_{2}\) and \( A_{1}\) is the authority level secret and \( A_{2}\) is the authority level top secret. Let \( S=\{diplomacy, combat ops \}\) [4][5]. This forms the lattice depicted in figure 1.

Figure 1: example security classification
lattice

The objective of such a security policy is to govern flows of sensitive information. Thus, if we assign individuals security clearances in the same way that information is assigned security classes, then we can set up a policy such that an item of information i assigned a security class \( (A_{1},C_{1})\) can only be disseminated to an individual a having security clearance \( (A_{2},C_{2})\) if and only if \( (A_{1},C_{1})\preceq (A_{2},C_{2})\).

Without looking at the literature [6], it seems that the obvious next step is to embed this into a network model. Supposing that one has a network model in which each node is classified by a security clearance there are a variety of useful and potentially interesting questions that can be asked. For example, one might want to look for connected components where every node in the connected component has a security clearance \( (A,C)\) such that \( (A,C)\succeq (A_{j},C_{k})\) for some j and k. Or if one were interested in simulating the propagation of information in that social network such that the probability of a node communicating certain security classes of information to another node is a function of the security class of the information and the security clearances of those two nodes.

So far this discussion has limited itself to information flow as dissemination of information vehicles, contrary to the direction I suggested in my last post should be pursued. One easy remedy might be to have minimally cognitive nodes with knowledge bases and primitive inference rules by which new knowledge can be inferred from existing or newly received items of information. This would have several consequences. Relevant items of novel information might disseminate through the network (and global knowledge grows), and items of information not originally disseminated, for example because it is top secret, may yet be guessed or inferred from existing information by nodes with security clearances too low to have received it normally.

Moving away from issues of security policy, we can generalize this to classify nodes in social networks in other systematic ways. In particular, we may be interested in epistemic communities. We might classify beliefs and/or knowledge using formal tools like formal concept analysis, as I believe Camille Roth has been doing (e.g. see his paper Towards concise representation for taxonomies of epistemic communities).

Fun stuff.

[1] Rosen, Kenneth H. Discrete mathematics and its applications. 5th edition. McGraw Hill. 2003.

[2] Some undergraduates joked that if they mastered everything in Rosen's book, they would pretty much have mastered the foundations of computer science. An exaggeration, but not far off.

[3] A lattice is a partially ordered set (poset) such that for any pair of elements of that set there exists a least upper bound and a greatest lower bound.

[4] According to Wikipedia such the US uses classifications like the following:

1.4(a) military plans, weapons systems, or operations;

1.4(b) foreign government information;

1.4(c ) intelligence activities, sources, or methods, or cryptology;

1.4(d) foreign relations or foreign activities of the United States, including confidential sources;

1.4(e) scientific, technological or economic matters relating to national security; which includes defense against transnational terrorism;

1.4(f)USG programs for safeguarding nuclear materials or facilities;

1.4(g) vulnerabilities or capabilities of systems, installations, infrastructures, projects or plans, or protection services relating to the national security, which includes defense against transnational terrorism; and

1.4(h) weapons of mass destruction.

[5] An interesting category of information is information about who has what security clearance.

[6] Where fun and often good ideas go to die.