SELFS: Region-Based Selective Flow-Sensitive Pointer Analysis
Authors
Yulei Sui    Sen Ye    Jingling Xue   
School of Computer Science and Engineering , The University of New South Wales
Description

SELFS is a region-based SELective Flow-Sensitive approach to inter-procedural pointer analysis for C that operates on the regions partitioned from a program. Flow-sensitivity is maintained between the regions but not inside, making traditional flow-insensitive and flow-sensitive as well as recent sparse flow-sensitive analyses all special instances of our SELFS framework.

SELFS separates region partitioning as an independent concern from the rest of the pointer analysis. It facilitates the development of flow-sensitive variations with desired efficiency and precision tradeoffs by reusing existing pointer resolution algorithms.

Paper and Artifact

Region-based Selective Flow-Sensitive Pointer Analysis 21th International Static Analysis Symposium (SAS' 14)

Virtual Image of SELFS Framework: selfs.zip(2.2GB)

The artifact, which is a virtual machine image, contains SELFS implementation on top of LLVM compiler (version 3.3) as well as SPEC2000/2006 benchmarks and several micro-benchmarks.

The OS in the virtual machine image is Ubuntu 12.04 (an account is created with both its name and password "sas14"). We recommend you to allocate at least 16GB memory to the virtual machine. A VirtualBox with version 4.1.12 or newer is required to run the image.

Quick Guidelines

The SELFS project is located in the "pta" directory under the HOME directory of the user named "sas14". To run the tests as we did for in our paper, open a terminal and do:

cd /home/sas14/pta/ # Go to the SELFS project directory
. ./setup.sh # Set up environment variables
cd sas_exp # Go to the test directory

To reproduce our results in Figures 6 -- 8 for both SFS and SELFS across the 14 benchmarks, execute the script "run_all.sh":

./run_all.sh

Please note all the results related to analysis times in our paper are obtained on a 2.00GHz Intel Xeon 32-core CPU running Ubuntu Linux with 64GB memory, as described in Section 4. Obtaining all results this way takes about 40 mins on this platform.

You can also analyze a single program, say, "ammp.orig", as follows:

./run_single.sh ammp.orig

This will produce the results in Figures 6 -- 8 for "ammp.orig" under both the analyses evaluated, SFS and SELFS.

If you want to try SFS or SELFS separately for an individual program, say, "ammp.orig", the commends to use are:

./run_single.sh SFS ammp.orig # SFS on ammp.orig
or
./run_single.sh SELFS ammp.orig # SELFS on ammp.orig
Benchmarks

The benchmarks used in our paper are stored under "sas_exp" directory. There are 14 programs from both SPEC2000 and SPEC2006:

SPEC2000: ammp, crafty, gcc, mesa, parser, perlbmk, twolf, vortex, vpr.
SPEC2006: h264ref, hmmer, milc, sjeng, sphinx3.

We have also provided a few other benchmarks:

SPEC2000: art, bzip2, equake, gzip, mcf
SPEC2006: lbm, libquantum

All these programs have been compiled into the LLVM bitcode file format by "clang" and linked together by "llvm-link".

Some small C programs have been provided in the directory "/home/sas14/pta/sas_exp/micro_benchmarks/", you can compile them into LLVM bitcode files by

./compile_all.sh # Compile all C files
or
./compile_single.sh one_program.c # Compile one C file

For each bitcode file (.opt file) generated, you can try to analyze it by using the script "run_single.sh" as before.

To run your own C programs, please compile them with "compile_single.sh" as mentioned above. Then you can run SFS/SELFS with the "run_single.sh" over the bitcode files generated. For large programs with multiple bitcode files, please refer to

for details on how to link several bitcode files into one.

Contacts
Feel free to contact : ysui AT cse.unsw.edu.au if you have any question.

This web site is hosted by the Programming Languages and Compiler Group at the University of New South Wales.