Description if the algorithm


The algorithm detect information flows for a set of classes. The classes to be analyzed must be passed as parameters.

Information flow

If the value of b can be detected through a, we say that a points to b (a -> b)

Context

We are in the context of small safe objects that accept mobile code. So we perform the analysis in two steps:
  1. external phase : compute the information flow before loading
  2. internal phase : the external results are only verified at loading time
Beeing in an open world, we do not dispose of a call graph. So the analysis will focus on each method as an independed module. So each method, an annotation is computed. The set of all annotations forms the dictionary.

Policy

Beeing in the context of small safe objects, all attributes of entities in annotations can not be followed. This will be time and space consuming. So, for each entity will follow two subentities: The policy must be specified in a separate file in this manner: on each line, a confidential (secret) attribute (package.class.attibute).

Annotations

The annotation of a method m contains the information flows in m. An annotation has the form of a matrix: the lines and colons of the matrix are the entities that can flow in m, and the elements of the matrix are the possible flows between these entities in m.
An annotation is represented as a matrix, containing detected information flows between the following entities:
 
    R    E     S     F    P(-1)    P(0)    P(1) ...
 
where
    R  = the return of the method (if method is void, nothing will be linked to R)
    E  = the exceptions' world
    S  = the static world
    F  = the external flow (files, network, etc.)
    P(-1) = this, if the method is not static [OPTIONAL]
    P(0)   = the first parameter of the method
    P(1)   = the second parameter of the method
    etc ....
 
This is an example of annotation for method m :

int m(int i) {

       return i;

}

 
R E S F P(-1) P(0)
R null null null null null 16
E null null null null null null
S null null null null null null
F null null null null null null
P(-1) null null null null null null
P(0) null null null null null null
 
the value 16 indicates that there is a link between the return and the first parameter.
(we will see later what 16 means exactly ...)

Type of links

As we have seen in the previous section, annotations contain links between entities of a method. Depending on the operation that linked two entities, we can have a reference link or a value link.
So, for two entities a and b we suppose we have a link l. This link must contain all possible relations between a and b : value/reference link from secret/public part of a to secret/public part of b.
We encoded a link on 8 bits in this manner:

bit 7 6 5 4 3 2 1 0
entity a (from) S S P P S S P P
entity b (to) S P S P S P S P
type of link (value/ref) V V V V R R R R


Global annotation

To correctly handle virtual methods, we introduced the notion of global annotation for a method m.

etc .. etc ... Global annotation is a union of all exact annotations for classes in a hierarchy. So , when the exact type of a classe on which we invoke a method is not known, thw global annotation is used. This global annotation beeing the union of all possible annotations, the result will be correct for all possible future utilisations of the method.