Home Research Teaching Misc
 
 
Program Transformation Systems
Program Examination systems
Generic
Bug Finders
  Xform Stratego Cetus Rose AspectJ (abc) InjectJ ASTLog CodeQuest CodeSurfer JQuery PQL
PTQL
PMD CodeSonar Findbugs
Metal
System Description AST Rewriter (Generic) AST Rewriter (Generic) Compiler Infrastructure for Source to source optimisation
(C/C++)
Programmable Source code optimiser (C/C++)

AspectJ extension built on top of Polyglot

(Java)

Extends Java with Aspects (Java)
Query Language for examining ASTs (Generic) Datalog implementation for database of program facts. (Java) Generic whole program inspection system. (C/C++) Query based code browser. (Java) Static and dynamic program trace analysis tool (Java) Dynamic Program trace analysis tool. (Java) (Java) Bug detection tool built on top of the CodeSurfer program inspection system. (C++) Static bytecode analysis tool (Java)

State machine Language for specifying compiler extensions for code checking

(C/C++)

Dataflow Def-use: intraprocedural
No
No
Yes
Yes
?
?
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Def-use: interprocedural
No
No
Yes
Yes
?
?
Yes
Yes
Yes
?
Yes
Yes
Yes
Yes
Yes
Yes
Crossreferencing
No
No
?
?
?
?
Yes
?
?
?
No
No
No
No
No
?
Control flow Call graph
No
Yes
Yes
Yes
?
?
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Intraprocedural
No
No
Yes
Yes
?
?
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Dominator analysis
No
No
Yes
Yes
?
?
?
?
Yes
?
Yes
Yes
No
Yes
Yes
?
Loop detection
No
No
?
Yes
?
?
?
?
Yes
?
?
No
No
Yes
?
?
Reachability
No
No
?
Yes
?
?
Yes
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Control Dependence
No
Yes
?
Yes
?
?
Yes
Yes
Yes
?
Yes
No
Yes
Yes
?
No
CFG P. Matching
No
No
?
?
?
No
No
No
?
No
Yes
Yes
?
Yes?
Yes
Yes
Call graph P.Matching
No
No
?
?
?
No
No
No
Yes
No
?
?
?
Yes?
?
Yes?
Alias Analysis Interprocedural
No
No
Yes
No
?
?
Yes
?
Yes
No
Yes
?
?
Yes
Yes
No
Intraprocedural
No
No
Yes
Yes
?
?
Yes
?
Yes
?
Yes
?
?
Yes
Yes
No
AST Transformation and Analysis Creation/insertion/deletion
Yes
Yes
Yes
Yes
?
Yes
No
No
No
No
No
No
No
No
No
No
AST Pattern Matching
Yes
Yes
Yes
Yes
?
Yes
Yes
Yes
?
Yes
No
No
?
?
?
No
Generic Traversals
Yes
Yes
Yes
Yes
?
Yes
Yes
No
?
?
No
No
No
No
?
No
Source code P Matching
Yes
?
?
?
?
?
?
?
?
?
Yes
?
?
?
?
Yes
Symbol Table Block scope
Yes
Yes
?
?
?
Yes
Yes
Yes
Yes
Yes
?
?
Yes
Yes
Yes
?
Function scope
Yes
Yes
?
?
?
Yes
Yes
Yes
Yes
Yes
?
?
Yes
Yes
Yes
?
File scope
Yes
Yes
?
?
?
Yes
Yes
Yes
Yes
Yes
No
No
Yes
Yes
Yes
?
Namespace
No
No
?
?
?
Yes
Yes
No
Yes
Yes
No
No
No
Yes
?
?
Type information
No
No
?
?
?
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
?
?
Program Event Matching Control Flow Based
No
No
No
No
No
No
No
No
No
No
Yes
Yes
No
?
?
Yes
Prog. Trace Based
No
No
No
No
No
No
No
No
No
No
Yes
Yes
?
?
?
No
Line Information
Yes
No
?
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Extensibility Userside
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
?
Grammar based
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
?
                     
     

Dataflow

Def-use: intraprocedural: Track def-use chains within a function.

Def-use: interprocedural: Track def-use across function call boundaries

 

Control flow

Call graph: Control flow graph with functions as nodes and caller/callee relationship as edges.

Intraprocedural: Control flow graph consiting of basic blocks local to a function

Dominator analysis:

Loop detection: detect loops in control flow

Reachability: Does control reach form point A to point B

Control Dependence: Does execution of point B depend on the conditional execution of point A

CFG P. Matching: Match basic block execution sequences (or potential execution sequences)

Call graph Pattern Matching: Find subgraphs in a CFG that correspond to particular patterns.

Alias Analysis

Interprocedural: Track different pointers to the same resource across function call boundaries.

Intraprocedural: Track different pointers to the same resource within a function

AST Transformation and Analysis

Creation/insertion: Create and insert new nodes into an AST

Deletion: Remove nodes from an AST

Replacement: Replace AST nodes.

AST Pattern Matching: Match AST objects according to type and location.

Generic Traversals: New AST traversals can be defined in terms of existing ones.

Symbol Table

Block:

Function: Disciminate among items with identical names but belong to different functions.

File: Disriminate among elements from different files.

Namespace: Discriminate among elements with identical names but different namespaces

Type information: variable classification info. eg, int, Double.

Line Information: Matches program elements to source code lines

Crossreferencing: Locating references to an item. For example all calls to function foo(), or all writes to memory location bar

 

Extensibility

Userside: user can write routiens/modules that are referenceable from within the system.

Grammar based: User can easily extend the system by modifying the grammar.

 

Program Event Matching

Control Flow Based: Match occurences or sequence of events using control flow information. Eg. function a() is called after b().

Program Trace based: match occurences or sequences of events using program traces.