Toward Full Elasticity in Distributed Static Analysis

  • Diego Garbervetsky ,
  • Edgardo Zoppi ,
  • ,
  • Ben Livshits

Microsoft Research Technical Report: MSR-TR-2015-88

In this paper we present the design and implementation of a distributed 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. Our reliance on a cloud cluster 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 in a distributed setting. The vision that motivates this work is that every large-scale software repository such as GitHub, BitBucket, or Visual Studio Online will be able to perform static analysis on a very large scale.

We experimentally validate our distributed analysis approach using a combination of both synthetic and real benchmarks. To show scalability, we demonstrate how the analysis presented in this paper is able to handle inputs that are almost 10 million LOC in size, without running out of memory.

Our results show that the analysis scales well in terms of memory pressure independently of the input size, as we add more VMs. As the number of analysis VMs increases, we observe that the analysis time generally improves as well. Lastly, we demonstrate that querying the results can be performed with a median latency of 15 ms.