Toward Full Elasticity in Distributed Static Analysis

  • Diego Garbevetsky ,
  • Edgardo Zoppi ,
  • Thomas Ball ,
  • Benjamin Livshits ,
  • ,
  • Ben Livshits

MSR-TR-2015-88 |

In this paper we present the design and implementation of an elastic static analysis framework that is designed to scale with the size of the input. Our approach is based on the actor programming model and is deployed in the cloud. This provides a degree of elasticity for CPU, memory and storage resources.

To demonstrate the potential of our technique, we show how a typical call graph analysis can be implemented. We experimentally validate the analysis using a combination of both synthetic and real benchmarks.

The results show that our analysis scales well in terms of memory pressure independently of the input size, as we add more machines. Despite using stock hardware and incurring a non-trivial communication overhead, our processing time for projects of close to 1M LOC is about 15 minutes. As the number of machines increases, we show that the analysis time does not suffer. Lastly, we demonstrate that querying the results can be performed with a median latency of well under 20 ms.