AAL

AAL (Alias Analysis Library) is based on an intermediate representation in SSA form using basic blocks (control flow graph) and may not be used to represent the whole program but only an abstraction. By supporting only a small set of instructions the possibilities for erroneous usage is reduced and extension of the library is simplified. Furthermore, the language knows only one type, references, and, finally, the intermediate representation contains a single special function called "_rootFunction" which must be set up to model the environments behavior correctly.
A more extensive description can be found in the thesis itself.

The source of the library is available for download.

Usage example

We'd like to perform alias analysis on the following piece of C code:
1: struct S { int *ptr1; int *ptr2; }; 2: 3: int global; 4: 5: void initStruct(struct S *sPtr) { 6: sPtr->ptr1 = &global; 7: sPtr->ptr2 = 0; 8: } 9: 10: int main() { 11: struct S s; 12: 13: initStruct(&s); 14: *(s.ptr1) = 42; 15: 16: return 0; 17: }

The first step is to translate this code into AALSSA, the intermediate representation used by AAL. A possible result would be:
1: @NULL = new Object(2); 2: @global = new Object(2); 3: 4: void initStruct(sPtr) { 5: 0xa91730 (entry): 6: | *sPtr = @global; 7: | tmp = sPtr + 1; 8: | *tmp = @NULL; 9: | return; 10: } 11: 12: void main() { 13: 0xa8f580 (entry): 14: | s = new Object(2); 15: | @initStruct(s); 16: | tmp2 = *s; 17: | return; 18: } 19: 20: void _rootFunction() { 21: 0xa912c0 (entry): 22: | @main(); 23: | return; 24: }

Lines 1-2 show the globals, which can easily be recognized throughout the source by their prepended @-character. AALSSA doesn't support a NULL value specifically, instead, a user creates a global reference which he then uses as such. The integer argument specifies the amount of fields the created object should contain. As C is not type-safe and unexpected casts could occur a conservative approach has been chosen in this example: The biggest struct in the input has two fields, so all created objects are assumed to have to fields.
Lines 12-18 contain the definition of @main(). After the local object is created the call to @initStruct() occurs, giving the local object as an argument. After the call load happens, loading the value of the first field of s, which would be @global. Then the function returns. Note that the store of 42 is not reflected in any way, as this is of no importance to model the behavior concerning pointers. Of course a user may decide to include this store as well.
Lines 4-10 represent the definition of @initStruct(). The first instruction stores the reference @global in the first field of sPtr. The second instruction calculates the reference pointing to the second field, which is then used as base for the store of @NULL. Finally, the function returns.
Lines 20-24 show the definition of @_rootFunction which is used to model the environment. In this case this is just a call to @main(). However, if AAL were to be used to analyze some library code the correct solution might be to construct a non-deterministic loop calling all external functions with unknown arguments.

After this the user chooses the type of analysis she wants, based on the time and precision requirements, and may then execute the actual analysis. Once the analysis is complete, the user may query the set of targets for a given reference and check for aliasing by intersecting two of those.