Crystal
A program analysis system for C
 

Overview

Crystal is a program analysis system for C written in Java. The system is aimed at making it easier to write program analyses by providing: a simple, canonical representation of the program; standard program analyses such as pointer analysis; and support for whole-program analysis. Java makes the system is portable, and allows analysis writers to benefit from existing IDE's and other Java software development tools. Current representations, analyses, and features include:

• AST: the original abstract syntax tree of the program;
• CFG: a simplified program representation in the form of a control-flow graph, where statements and expressions are represented in canonical form;
• Memory partitioning via unification-based, field-sensitive pointer analysis;
• Whole-program analysis: merge global symbol tables when analyzing multiple files.

Crystal currently supports the ISO C99 standard and several common GNU C extensions.

Download

Current version: crystal-1.1.tgz (July 2007)

Previous version: crystal-1.0.tgz (Nov 2006)

Installation and usage

Requirements: to build the system you will need Java 1.5 and Apache Ant. In Windows, we recommend you use Cygwin. The system uses JFlex and JavaCUP for the parser. The JFlex and JavaCUP jar files are included in the Crystal distribution (so they need not be downloaded).

To install the system: download the distribution and unzip the file. Then go to the newly created directory crystal and run ant:

> tar xzf crystal-1.X.tgz
> cd crystal-1.X
> ant

To run crystal, use the generated shell script "bin/crystal". To see the executed java command, run "bin/crystal -v". You can use a similar java command if you prefer to run Crystal without the wrapper script.

To run Crystal on larger C programs, use the "-h" option of this script to specify larger heap sizes (the default is 64Mb). For instance, "bin/crystal -h 256" runs Crystal with a heap of 256Mb.

You must supply preprocessed C files when running Crystal. If you are using the GNU C compiler, preprocessed C files can be generated using 'gcc -E' or 'cpp'.

Example: to build the CFG representation for all functions in preprocessed C files file1.c and file2.c, and then print out the CFG's in graphical form in dot format to file1.dot and file2.dot, run the following command:

> crystal -cfg -emit-dot file1.c file2.c

Create Your Own Project

New projects can be created in the $CRYSTAL/src/crystal/projects directory. Create a subdirectory with your project name, and place your code in that directory. To parse the input files and create the program representation, invoke the method crystal.Main.main. You may find it useful to use the sample project included in  $CRYSTAL/src/crystal/projects/sample as a starting point.

Crystal Projects

The following projects use Crystal:

• FastCheck: a static checker for source-sink safety properties, such as malloc-free, fopen-fclose, or lock-unlock.

• LC: a memory leak detector that identifies the lack of memory leaks by disproving their presence.

• Shape analysis: a shape analysis with local reasoning about single heap cells to identify heap shapes and find heap errors in C programs.

• Alias analysis: a demand-driven alias analysis project.

Contributors

The system is being developed at Cornell University. Contributors to the project include:

• Radu Rugina (rugina at cs cornell edu)
• Siggi Cherem (siggi at cs cornell edu)
• Xin Zheng (xinz at cs cornell edu)
• Maksim Orlovich (maksim at cs cornell edu)
• Lonnie Princehouse (lonnie at cs cornell edu)