Document Open Access Logo

Efficient Reflection String Analysis via Graph Coloring

Authors Neville Grech, George Kastrinis, Yannis Smaragdakis

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2018.26.pdf
  • Filesize: 0.55 MB
  • 25 pages

Document Identifiers

Author Details

Neville Grech
  • Dept. of Informatics and Telecommunications, University of Athens, Greece , and Dept. of Computer Science, University of Malta, Malta
George Kastrinis
  • Dept. of Informatics and Telecommunications, University of Athens, Greece
Yannis Smaragdakis
  • Dept. of Informatics and Telecommunications, University of Athens, Greece

Cite As Get BibTex

Neville Grech, George Kastrinis, and Yannis Smaragdakis. Efficient Reflection String Analysis via Graph Coloring. In 32nd European Conference on Object-Oriented Programming (ECOOP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 109, pp. 26:1-26:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ECOOP.2018.26

Abstract

Static analyses for reflection and other dynamic language features have recently increased in number and advanced in sophistication. Most such analyses rely on a whole-program model of the flow of strings, through the stack and heap. We show that this global modeling of strings remains a major bottleneck of static analyses and propose a compact encoding, in order to battle unnecessary complexity. In our encoding, strings are maximally merged if they can never serve to differentiate class members in reflection operations. We formulate the problem as an instance of graph coloring and propose a fast polynomial-time algorithm that exploits the unique features of the setting (esp. large cliques, leading to hundreds of colors for realistic programs). The encoding is applied to two different frameworks for string-guided Java reflection analysis from past literature and leads to significant optimization (e.g., a ~2x reduction in the number of string-flow inferences), for a whole-program points-to analysis that uses strings.

Subject Classification

ACM Subject Classification
  • Software and its engineering → Compilers
  • Theory of computation → Program analysis
  • Software and its engineering → General programming languages
Keywords
  • reflection
  • static analysis
  • graph coloring

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Abdulbaki Aydin, Lucas Bang, and Tevfik Bultan. Automata-based model counting for string constraints. In Daniel Kroening and Corina S. Păsăreanu, editors, Computer Aided Verification: 27th International Conference, CAV 2015, San Francisco, CA, USA, July 18-24, 2015, Proceedings, Part I, pages 255-272, Cham, 2015. Springer International Publishing. URL: http://dx.doi.org/10.1007/978-3-319-21690-4_15.
  2. Stephen M. Blackburn, Robin Garner, Chris Hoffmann, Asjad M. Khang, Kathryn S. McKinley, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z. Guyer, Martin Hirzel, Antony Hosking, Maria Jump, Han Lee, J. Eliot B. Moss, Aashish Phansalkar, Darko Stefanović, Thomas VanDrunen, Daniel von Dincklage, and Ben Wiedermann. The DaCapo benchmarks: Java benchmarking development and analysis. In Proceedings of the 21th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2006, October 22-26, 2006, Portland, Oregon, USA, OOPSLA '06, pages 169-190, New York, NY, USA, 2006. ACM. URL: http://dx.doi.org/10.1145/1167473.1167488.
  3. Eric Bodden, Andreas Sewe, Jan Sinschek, Hela Oueslati, and Mira Mezini. Taming reflection: Aiding static analysis in the presence of reflection and custom class loaders. In Proceedings of the 33rd International Conference on Software Engineering, ICSE 2011, Waikiki, Honolulu , HI, USA, May 21-28, 2011, ICSE '11, pages 241-250, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1985793.1985827.
  4. Martin Bravenboer and Yannis Smaragdakis. Strictly declarative specification of sophisticated points-to analyses. In Proc. of the 24th Annual ACM SIGPLAN Conf. on Object Oriented Programming, Systems, Languages, and Applications, OOPSLA '09, New York, NY, USA, 2009. ACM. Google Scholar
  5. Tevfik Bultan. String analysis for vulnerability detection and repair. In Proceedings of the 22Nd International Symposium on Model Checking Software - Volume 9232, SPIN 2015, pages 3-9, New York, NY, USA, 2015. Springer-Verlag New York, Inc. URL: http://dx.doi.org/10.1007/978-3-319-23404-5_1.
  6. Aske Simon Christensen, Anders Møller, and Michael I. Schwartzbach. Precise analysis of string expressions. In Static Analysis, 10th International Symposium, SAS 2003, San Diego, CA, USA, June 11-13, 2003, Proceedings, SAS '03, pages 1-18. Springer, 2003. URL: http://dx.doi.org/10.1007/3-540-44898-5_1.
  7. Stephen J. Fink et al. WALA UserGuide: PointerAnalysis. http://wala.sourceforge.net/wiki/index.php/UserGuide:PointerAnalysis#Contexts_for_Reflection, 2013.
  8. Michael I. Gordon, Deokhwan Kim, Jeff H. Perkins, Limei Gilham, Nguyen Nguyen, and Martin C. Rinard. Information flow analysis of android applications in droidsafe. In 22nd Annual Network and Distributed System Security Symposium, NDSS 2015, San Diego, California, USA, February 8-11, 2015. The Internet Society, 2015. URL: http://www.internetsociety.org/doc/information-flow-analysis-android-applications-droidsafe.
  9. Neville Grech, George Fourtounis, Adrian Francalanza, and Yannis Smaragdakis. Heaps don't lie: Countering unsoundness with heap snapshots. Proc. ACM Program. Lang., 1:1-27, 2017. URL: http://dx.doi.org/10.1145/3133892.
  10. Neville Grech, George Fourtounis, Adrian Francalanza, and Yannis Smaragdakis. Shooting from the heap: Ultra-scalable static analysis with heap snapshots. In International Symposium on Software Testing and Analysis (ISSTA), ISSTA '18, New York, NY, USA, 2018. ACM. URL: http://dx.doi.org/10.1145/3213846.3213860.
  11. Salvatore Guarnieri and Benjamin Livshits. GateKeeper: mostly static enforcement of security and reliability policies for Javascript code. In Proc. of the 18th USENIX Security Symposium, SSYM' 09, pages 151-168, Berkeley, CA, USA, 2009. USENIX Association. URL: http://dl.acm.org/citation.cfm?id=1855768.1855778.
  12. R. Gupta, M. L. Soffa, and T. Steele. Register allocation via clique separators. In Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation, PLDI '89, pages 264-274, New York, NY, USA, 1989. ACM. URL: http://dx.doi.org/10.1145/73141.74842.
  13. Sebastian Hack and Gerhard Goos. Optimal register allocation for ssa-form programs in polynomial time. Inf. Process. Lett., 98(4):150-155, may 2006. URL: http://dx.doi.org/10.1016/j.ipl.2006.01.008.
  14. George Kastrinis and Yannis Smaragdakis. Efficient and effective handling of exceptions in Java points-to analysis. In Compiler Construction - 22nd International Conference, CC 2013, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2013, Rome, Italy, March 16-24, 2013. Proceedings, CC '13, pages 41-60. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-37051-9_3.
  15. George Kastrinis and Yannis Smaragdakis. Hybrid context-sensitivity for points-to analysis. In Proc. of the 2013 ACM SIGPLAN Conf. on Programming Language Design and Implementation, PLDI '13, New York, NY, USA, 2013. ACM. Google Scholar
  16. Monica S. Lam, John Whaley, V. Benjamin Livshits, Michael C. Martin, Dzintars Avots, Michael Carbin, and Christopher Unkel. Context-sensitive program analysis as database queries. In Proceedings of the Twenty-fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 13-15, 2005, Baltimore, Maryland, USA, PODS '05, pages 1-12, New York, NY, USA, 2005. ACM. URL: http://dl.acm.org/citation.cfm?id=1065167, URL: http://dx.doi.org/10.1145/1065167.1065169.
  17. Davy Landman, Alexander Serebrenik, and Jurgen J. Vinju. Challenges for static analysis of Java reflection - literature review and empirical study. In Proceedings of the 39th International Conference on Software Engineering, ICSE 2017, Buenos Aires, Argentina, May 20-28, 2017, 2017. Google Scholar
  18. Yue Li, Tian Tan, Yulei Sui, and Jingling Xue. Self-inferencing reflection resolution for Java. In Proc. of the 28th European Conf. on Object-Oriented Programming, ECOOP '14, pages 27-53. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44202-9.
  19. Yue Li, Tian Tan, and Jingling Xue. Effective soundness-guided reflection analysis. In Sandrine Blazy and Thomas Jensen, editors, Static Analysis - 22nd International Symposium, SAS 2015, Saint-Malo, France, September 9-11, 2015, Proceedings, SAS '15, pages 162-180. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48288-9_10.
  20. Percy Liang and Mayur Naik. Scaling abstraction refinement via pruning. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2011, San Jose, CA, USA, June 4-8, 2011, PLDI '11, pages 590-601, New York, NY, USA, 2011. ACM. URL: http://dx.doi.org/10.1145/1993498.1993567.
  21. Benjamin Livshits. Improving Software Security with Precise Static and Runtime Analysis. PhD thesis, Stanford University, December 2006. Google Scholar
  22. Benjamin Livshits, Manu Sridharan, Yannis Smaragdakis, Ondřej Lhoták, J. Nelson Amaral, Bor-Yuh Evan Chang, Samuel Z. Guyer, Uday P. Khedker, Anders Møller, and Dimitrios Vardoulakis. In defense of soundiness: A manifesto. Commun. ACM, 58(2):44-46, jan 2015. URL: http://dx.doi.org/10.1145/2644805.
  23. Benjamin Livshits, John Whaley, and Monica S. Lam. Reflection analysis for Java. In Proc. of the 3rd Asian Symp. on Programming Languages and Systems, pages 139-160. Springer, 2005. URL: http://dx.doi.org/10.1007/11575467_11.
  24. Magnus Madsen, Benjamin Livshits, and Michael Fanning. Practical static analysis of JavaScript applications in the presence of frameworks and libraries. In Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering, ESEC/FSE'13, Saint Petersburg, Russian Federation, August 18-26, 2013, FSE '13, pages 499-509. ACM, 2013. URL: http://dl.acm.org/citation.cfm?id=2491411, URL: http://dx.doi.org/10.1145/2491411.2491417.
  25. Mayur Naik, Alex Aiken, and John Whaley. Effective static race detection for java. In Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation, Ottawa, Ontario, Canada, June 11-14, 2006, PLDI '06, pages 308-319, New York, NY, USA, 2006. ACM. URL: http://dx.doi.org/10.1145/1133981.1134018.
  26. Oracle. Proxy (Java Platform SE 8), 2016. URL: http://docs.oracle.com/javase/8/docs/api/java/lang/reflect/Proxy.html.
  27. Thomas W. Reps. Demand interprocedural program analysis using logic databases. In R. Ramakrishnan, editor, Applications of Logic Databases, pages 163-196. Kluwer Academic Publishers, 1994. Google Scholar
  28. Olin Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, Carnegie Mellon University, may 1991. Google Scholar
  29. Yannis Smaragdakis and George Balatsouras. Pointer analysis. Foundations and Trends® in Programming Languages, 2(1):1-69, 2015. URL: http://dx.doi.org/10.1561/2500000014.
  30. Yannis Smaragdakis, George Balatsouras, George Kastrinis, and Martin Bravenboer. More sound static handling of Java reflection. In Proc. of the Asian Symp. on Programming Languages and Systems, APLAS '15. Springer, 2015. Google Scholar
  31. Yannis Smaragdakis, Martin Bravenboer, and Ondřej Lhoták. Pick your contexts well: Understanding object-sensitivity. In Proc. of the 38th ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, POPL '11, pages 17-30, New York, NY, USA, 2011. ACM. Google Scholar
  32. John Whaley, Dzintars Avots, Michael Carbin, and Monica S. Lam. Using Datalog with binary decision diagrams for program analysis. In Proc. of the 3rd Asian Symp. on Programming Languages and Systems, pages 97-118. Springer, 2005. URL: http://dx.doi.org/10.1007/11575467_8.
  33. John Whaley and Monica S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation 2004, Washington, DC, USA, June 9-11, 2004, PLDI '04, pages 131-144, New York, NY, USA, 2004. ACM. URL: http://dx.doi.org/10.1145/996841.996859.
  34. Yifei Zhang, Tian Tan, Yue Li, and Jingling Xue. Ripple: Reflection analysis for android apps in incomplete information environments. In Gail-Joon Ahn, Alexander Pretschner, and Gabriel Ghinita, editors, Proceedings of the Seventh ACM on Conference on Data and Application Security and Privacy, CODASPY 2017, Scottsdale, AZ, USA, March 22-24, 2017, pages 281-288. ACM, 2017. URL: http://dl.acm.org/citation.cfm?id=3029806, URL: http://dx.doi.org/10.1145/3029806.3029814.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact