Conferencia

Garbervetsky, D.; Zoppi, E.; Livshits, B.; Zisman A.; Bodden E.; Schafer W.; van Deursen A.; Special Interest Group on Software Engineering (ACM SIGSOFT) "Toward full elasticity in distributed static analysis: The case of callgraph analysis" (2017) 11th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2017. Part F130154:442-453
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor

Abstract:

In this paper we present the design and implementation of a distributed, whole-program 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 large scale. We experimentally validate our implementation of the distributed call graph analysis 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 lines of code (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 virtual machines (VMs). As the number of worker 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. © 2017 Association for Computing Machinery.

Registro:

Documento: Conferencia
Título:Toward full elasticity in distributed static analysis: The case of callgraph analysis
Autor:Garbervetsky, D.; Zoppi, E.; Livshits, B.; Zisman A.; Bodden E.; Schafer W.; van Deursen A.; Special Interest Group on Software Engineering (ACM SIGSOFT)
Filiación:Universidad de Buenos Aires, FCEyN, DC ICC, CONICET, Argentina
Imperial College London, United Kingdom
Palabras clave:Development environments and tools; Distributed and concurrent systems; Parallel; Performance and scalability; Program analysis; Program comprehension and visualization; Elasticity; Scalability; Software engineering; Concurrent systems; Development environment; Parallel; Performance and scalabilities; Program analysis; Program comprehension; Static analysis
Año:2017
Volumen:Part F130154
Página de inicio:442
Página de fin:453
DOI: http://dx.doi.org/10.1145/3106237.3106261
Título revista:11th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2017
Título revista abreviado:Proc ACM SIGSOFT Symp Found Software Eng
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97814503_vPartF130154_n_p442_Garbervetsky

Referencias:

  • (2015) Representational State Transfer, , https://en.wikipedia.org/wiki/Representational_state_transfer
  • Agha, G., (1986) Actors: A Model of Concurrent Computation in Distributed Systems, , MIT Press
  • Albarghouthi, A., Kumar, R., Nori, A.V., Rajamani, S.K., Parallelizing topdown interprocedural analyses (2012) Proceedings of the Conference on Programming Language Design and Implementation
  • Andersen, L.O., (1994) Program Analysis and Specialization for the C Programming Language, , PhD thesis, University of Cophenhagen
  • Bacon, D.F., Sweeney, P.F., Fast static analysis of C++ virtual function calls (1996) Proceedings of the Conference on Object-oriented Programming, Systems, Languages, and Applications
  • Bernstein, P.A., Bykov, S., Geller, A., Kliot, G., Thelin, J., Orleans: Distributed virtual actors for programmability and scalability (2014) Technical Report MSR-TR-2014-41, , Microsoft Research
  • Bornholt, J., Torlak, E., Scaling program synthesis by exploiting existing code (2015) Machine Learning for Programming Languages
  • Calcagno, C., Distefano, D., Dubreil, J., Gabi, D., Hooimeijer, P., Luca, M., Oâǎz-Hearn, P., Rodriguez, D., Moving fast with software veriication (2015) NASA Formal Methods Symposium, pp. 3-11. , Springer
  • Cousot, P., Asynchronous iterative methods for solving a ixed point system of monotone equations in a complete lattice (1977) Technical Report, Laboratoire IMAG, , Université scientiique et médicale de Grenoble
  • Dyer, R., Nguyen, H.A., Rajan, H., Nguyen, T.N., Boa: A language and infrastructure for analyzing ultra-large-scale software repositories (2013) Proceedings of the International Conference on Software Engineering, , IEEE Press
  • Dyer, R., Rajan, H., Nguyen, H.A., Nguyen, T.N., Nguyen. Mining billions of ast nodes to study actual and potential usage of Java language features (2014) Proceedings of the International Conference on Software Engineering
  • Dyer, R., Rajan, H., Nguyen, T.N., Declarative visitors to ease ine-grained source code mining with full history on billions of ast nodes (2013) ACM SIGPLAN Notices, , ACM
  • Grove, D., Chambers, C., A framework for call graph construction algorithms (2001) ACM Transactions on Programming Languages and Systems
  • Grove, D., DeFouw, G., Dean, J., Chambers, C., Call graph construction in object-oriented languages (1997) ACM SIGPLAN Notices
  • Hardekopf, B., Lin, C., The ant and the grasshopper: Fast and accurate pointer analysis for millions of lines of code (2007) Proceedings of the Conference on Programming Language Design and Implementation
  • Hardekopf, B., Lin, C., Flow-sensitive pointer analysis for millions of lines of code (2011) Proceedings of the International Symposium on Code Generation and Optimization
  • Lam, M.S., Whaley, J., Livshits, B., Martin, M.C., Avots, D., Carbin, M., Unkel, C., Context-sensitive program analysis as database queries (2005) Proceedings of the Symposium on Principles of Database Systems, , June
  • Lassez, J.-L., Nguyen, V., Sonenberg, E., Fixed point theorems and semantics: A folk tale (1982) Information Processing Letters
  • Lee, Y.Y., Harwell, S., Khurshid, S., Marinov, D., Temporal code completion and navigation (2013) Proceedings of the International Conference on Software Engineering
  • Lhoták, O., Hendren, L., Context-sensitive points-to analysis: Is it worth it? (2006) Proceedings of the International Conference on Compiler Construction
  • Livshits, B., Sridharan, M., Smaragdakis, Y., Lhoták, O., Amaral, J.N., Chang, B.-Y.E., Guyer, S.Z., Vardoulakis, D., In defense of soundiness: A manifesto (2015) Communications of the ACM
  • Lopes, N.P., Rybalchenko, A., Distributed and predictable software model checking (2011) Proceedings of the International Conference on Veriication, Model Checking, and Abstract Interpretation
  • Madsen, M., Livshits, B., Fanning, M., Practical static analysis of JavaScript applications in the presence of frameworks and libraries (2013) Proceedings of the International Symposium on the Foundations of Software Engineering
  • Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G., Pregel: A system for large-scale graph processing (2010) Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD
  • McPeak, S., Gros, C.-H., Ramanathan, M.K., Ramanathan. Scalable and incremental software bug detection (2013) Proceedings of the Symposium on the Foundations of Software Engineering
  • Mendez-Lojo, M., Mathew, A., Pingali, K., Parallel inclusion-based points-to analysis (2010) Conference on Object Oriented Programming Systems Languages and Applications
  • (2015) NET Compiler Platform ("Roslyn"), , https://roslyn.codeplex.com/, Microsoft Corporation
  • (2015) Mozilla. LXR, , https://en.wikipedia.org/wiki/LXR_Cross_Referencer
  • Murray, K., Bigham, J.P., Beyond autocomplete: Automatic function deinition (2011) Proceedings of the Visual Languages and Human-Centric Computing Symposium
  • Nguyen, A.T., Nguyen, T.T., Nguyen, H.A., Tamrawi, A., Nguyen, H.V., Al-Kofahi, J., Nguyen, T.N., Graph-based pattern-oriented, context-sensitive source code completion Proceedings of the International Conference on Software Engineering
  • Omar, C., Yoon, Y., LaToza, T.D., Myers, B.A., Active code completion (2012) Proceedings of the International Conference on Software Engineering
  • Rodriguez, J., Lhoták, O., (2011) Actor-Based Parallel Datalow Analysis
  • Sadowski, C., Van Gogh, J., Jaspan, C., Soederberg, E., Winter, C., Tricorder: Building a program analysis ecosystem (2015) International Conference on Software Engineering (ICSE)
  • Sridharan, M., Gopan, D., Shan, L., Bodík, R., Demand-driven points-to analysis for Java (2005) Proceedings of the 20th Annual ACM SIGPLAN Conference on Objectoriented Programming, Systems, Languages, and Applications, OOPSLA '05, pp. 59-76. , New York, NY, USA ACM
  • Steensgaard, B., Points-to analysis in almost linear time (1996) Proceedings of the Symposium on Principles of Programming Languages, , ACM
  • Sundaresan, V., Hendren, L., Razaimahefa, C., Vallée-Rai, R., Lam, P., Gagnon, E., Godin, C., Practical virtual method call resolution for Java (2000) Proceedings of the Conference on Object-oriented Programming, Systems, Languages, and Applications
  • Tip, F., Palsberg, J., Scalable propagation-based call graph construction algorithms (2000) Proceedings of the Conference on Object-oriented Programming, Systems, Languages, and Applications
  • Voung, J.W., Jhala, R., Lerner, S., Relay: Static race detection on millions of lines of code (2007) Proceedings of the Symposium on the Foundations of Software Engineering
  • Wang, K., Hussain, A., Zuo, Z., Xu, G., Sani, A.A., Graspan: A single-machine disk-based graph system for interprocedural static analyses of large-scale systems code (2017) Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems
  • Whaley, J., Lam, M.S., Cloning-based context-sensitive pointer alias analysis using binary decision diagrams (2004) ACM SIGPLAN Notices, 39
  • Xie, Y., Aiken, A., Saturn: A scalable framework for error detection using boolean satisiability (2007) ACM Trans. Program. Lang. Syst, 29 (3). , May
  • Yu, H., Xue, J., Huo, W., Feng, X., Zhang, Z., Level by level: Making lowand context-sensitive pointer analysis scalable for millions of lines of code (2010) Proceedings of the International Symposium on Code Generation and OptimizationA4 - Special Interest Group on Software Engineering (ACM SIGSOFT)

Citas:

---------- APA ----------
Garbervetsky, D., Zoppi, E., Livshits, B., Zisman A., Bodden E., Schafer W., van Deursen A.,..., Special Interest Group on Software Engineering (ACM SIGSOFT) (2017) . Toward full elasticity in distributed static analysis: The case of callgraph analysis. 11th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2017, Part F130154, 442-453.
http://dx.doi.org/10.1145/3106237.3106261
---------- CHICAGO ----------
Garbervetsky, D., Zoppi, E., Livshits, B., Zisman A., Bodden E., Schafer W., et al. "Toward full elasticity in distributed static analysis: The case of callgraph analysis" . 11th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2017 Part F130154 (2017) : 442-453.
http://dx.doi.org/10.1145/3106237.3106261
---------- MLA ----------
Garbervetsky, D., Zoppi, E., Livshits, B., Zisman A., Bodden E., Schafer W., et al. "Toward full elasticity in distributed static analysis: The case of callgraph analysis" . 11th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE 2017, vol. Part F130154, 2017, pp. 442-453.
http://dx.doi.org/10.1145/3106237.3106261
---------- VANCOUVER ----------
Garbervetsky, D., Zoppi, E., Livshits, B., Zisman A., Bodden E., Schafer W., et al. Toward full elasticity in distributed static analysis: The case of callgraph analysis. Proc ACM SIGSOFT Symp Found Software Eng. 2017;Part F130154:442-453.
http://dx.doi.org/10.1145/3106237.3106261