ESP Wiki is looking for moderators and active contributors!

Rapid Type Analysis

Rapid Type Analysis (RTA) is a standard algorithm used for call graph construction. Its main advantage is speed, and it is often considered to have the best cost/accuracy tradeoff. It is a simple but clever algorithm: entire description of the algorithm in the paper literally fits in a single paragraph, but prior works missed the crucial enhancement.

RTA was patented by IBM. Thankfully, IBM let the patent expire by not paying maintenance fee.

Soot is a widely used open source library to analyze JVM bytecode, licensed under LGPL. As you can see from this note dated 2000, Soot implemented RTA while the IBM patent was in effect. It seems that the patent was widely ignored in practice.

Related pages on ESP Wiki

References