Erschienen in:

2021 | OriginalPaper | Buchkapitel

Hash Consed Points-To Sets

verfasst von : Mohamad Barbar, Yulei Sui

Erschienen in: Static Analysis

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Das Kapitel behandelt die grundlegende Rolle der Point-to-Analysis bei der Erkennung von Speicherfehlern und Parallelitätsfehlern in der statischen Analyse. Es führt das Konzept der Hash-Konformität ein, um das Problem doppelter Point-to-Sets und Operationen anzugehen, die in realen Programmen weit verbreitet sind. Durch die Aufrechterhaltung einzigartiger Point-to-Sets und die effiziente Erfassung von Vorgängen verbessert die Hash-Konformität die Leistung und Speichereffizienz von Point-to-Analysen erheblich. Der Ansatz wird anhand von 16 realen Open-Source-Programmen evaluiert, die erhebliche Verbesserungen sowohl in der zeitlichen als auch in der räumlichen Komplexität aufweisen. In diesem Kapitel werden auch Optimierungen untersucht, die Eigenschaften wirksam nutzen, um die Leistung weiter zu verbessern, und das Potenzial präventiver Memoiren diskutiert. Die Evaluierungsergebnisse zeigen den praktischen Nutzen dieser innovativen Lösung auf Datenstrukturebene für die Punkt-zu-Analyse.

KI-Generiert

Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Fast and Efficient Bit-Level Precision Tuning

Nächstes Kapitel Backward Symbolic Execution with Loop Folding

Due to the large number of points-to sets and unions flow-sensitive analysis produces.

For our SVF-based implementation we use sparse bit-vectors (Sect. 4.1).

Andersen, L.O.: Program analysis and specialization for the C programming language. Ph.D. thesis, University of Copenhagen, Denmark (1994)

Balatsouras, G., Smaragdakis, Y.: Structure-sensitive points-to analysis for C and C++. In: Rival, X. (ed.) SAS 2016. LNCS, vol. 9837, pp. 84–104. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53413-7_5CrossRef

Ball, T., Rajamani, S.K.: Bebop: a path-sensitive interprocedural dataflow engine. In: Proceedings of the 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE 2001, pp. 97–103. ACM, USA (2001). https://doi.org/10.1145/379605.379690

Barbar, M., Sui, Y., Chen, S.: Object versioning for flow-sensitive pointer analysis. In: 2021 IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2021, pp. 222–235. IEEE Computer Society, USA (2021). https://doi.org/10.1109/CGO51591.2021.9370334

Berndl, M., Lhoták, O., Qian, F., Hendren, L., Umanee, N.: Points-to analysis using BDDs. In: Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, PLDI 2003, pp. 103–114. ACM, USA (2003). https://doi.org/10.1145/781131.781144

Blackshear, S., Chang, B.-Y.E., Sankaranarayanan, S., Sridharan, M.: The flow-insensitive precision of Andersen’s analysis in practice. In: Yahav, E. (ed.) SAS 2011. LNCS, vol. 6887, pp. 60–76. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23702-7_9CrossRef

Braibant, T., Jourdan, J.H., Monniaux, D.: Implementing and reasoning about hash-consed data structures in Coq. J. Autom. Reason. 53(3), 271–304 (2014). https://doi.org/10.1007/s10817-014-9306-0MathSciNetCrossRefMATH

Bravenboer, M., Smaragdakis, Y.: Strictly declarative specification of sophisticated points-to analyses. In: Proceedings of the 24th ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA 2009, pp. 243–262. ACM, USA (2009). https://doi.org/10.1145/1640089.1640108

Chen, H., et al.: MUZZ: thread-aware grey-box fuzzing for effective bug hunting in multithreaded programs. In: 29th USENIX Security Symposium, USENIX Security 2020, pp. 2325–2342 (2020)

10.

Cheng, X., Wang, H., Hua, J., Xu, G., Sui, Y.: DeepWukong: statically detecting software vulnerabilities using deep graph neural network. ACM Trans. Softw. Eng. Methodol. (TOSEM) 30(3), 1–33 (2021). https://doi.org/10.1145/3436877CrossRef

11.

Choi, W., Choe, K.M.: Cycle elimination for invocation graph-based context-sensitive pointer analysis. Inf. Softw. Technol. 53(8), 818–833 (2011). https://doi.org/10.1016/j.infsof.2011.03.003CrossRef

12.

Cuoq, P., Kirchner, F., Kosmatov, N., Prevosto, V., Signoles, J., Yakobowski, B.: Frama-C. In: Eleftherakis, G., Hinchey, M., Holcombe, M. (eds.) SEFM 2012. LNCS, vol. 7504, pp. 233–247. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33826-7_16CrossRef

13.

Fähndrich, M., Foster, J.S., Su, Z., Aiken, A.: Partial online cycle elimination in inclusion constraint graphs. In: Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation, PLDI 1998, pp. 85–96. ACM, USA (1998). https://doi.org/10.1145/277650.277667

14.

Fan, X., Sui, Y., Liao, X., Xue, J.: Boosting the precision of virtual call integrity protection with partial pointer analysis for C++. In: Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2017, pp. 329–340. ACM, USA (2017). https://doi.org/10.1145/3092703.3092729

15.

Farkhani, R.M., Jafari, S., Arshad, S., Robertson, W., Kirda, E., Okhravi, H.: On the effectiveness of type-based control flow integrity. In: Proceedings of the 34th Annual Computer Security Applications Conference, ACSAC 2018, pp. 28–39. ACM, USA (2018). https://doi.org/10.1145/3274694.3274739

16.

Filliâtre, J.C., Conchon, S.: Type-safe modular hash-consing. In: Proceedings of the 2006 Workshop on ML, ML 2006, pp. 12–19. ACM, USA (2006). https://doi.org/10.1145/1159876.1159880

17.

Fink, S.J., Yahav, E., Dor, N., Ramalingam, G., Geay, E.: Effective typestate verification in the presence of aliasing. ACM Trans. Softw. Eng. Methodol. 17(2) (2008). https://doi.org/10.1145/1348250.1348255

18.

Gosling, J., Joy, B., Steele, G.L., Bracha, G., Buckley, A.: The Java Language Specification, Java SE 8 Edition, 1st edn. Addison-Wesley Professional (2014)

19.

Goubault, J.: Implementing functional languages with fast equality, sets and maps: an exercise in hash consing. Journées Francophones des Langages Applicatifs, 222–238 (1994)

20.

Hardekopf, B., Lin, C.: The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In: Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2007, pp. 290–299. ACM, USA (2007). https://doi.org/10.1145/1250734.1250767

21.

Hardekopf, B., Lin, C.: Exploiting pointer and location equivalence to optimize pointer analysis. In: Nielson, H.R., Filé, G. (eds.) SAS 2007. LNCS, vol. 4634, pp. 265–280. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74061-2_17CrossRef

22.

Hardekopf, B., Lin, C.: Semi-sparse flow-sensitive pointer analysis. In: Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2009, pp. 226–238. ACM, USA (2009). https://doi.org/10.1145/1480881.1480911

23.

Hardekopf, B., Lin, C.: Flow-sensitive pointer analysis for millions of lines of code. In: Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2011, pp. 289–298. IEEE Computer Society, USA (2011). https://doi.org/10.1109/CGO.2011.5764696

24.

Hash consing (2020). https://en.wikipedia.org/wiki/Hash_consing

25.

Heintze, N.: Analysis of large code bases: the compile-link-analyze model (1999, unpublished). http://web.archive.org/web/20050513012825/cm.bell-labs.com/cm/cs/who/nch/cla.ps

26.

Heintze, N., Tardieu, O.: Ultra-fast aliasing analysis using CLA: a million lines of C code in a second. In: Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, PLDI 2001, pp. 254–263. ACM, USA (2001). https://doi.org/10.1145/378795.378855

27.

Hubert, L., et al.: Sawja: static analysis workshop for Java. In: Beckert, B., Marché, C. (eds.) FoVeOOS 2010. LNCS, vol. 6528, pp. 92–106. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-18070-5_7CrossRef

28.

Lattner, C., Adve, V.: LLVM: a compilation framework for lifelong program analysis & transformation. In: Proceedings of the International Symposium on Code Generation and Optimization: Feedback-Directed and Runtime Optimization, CGO 2004, p. 75. IEEE Computer Society, USA (2004). https://doi.org/10.1109/CGO.2004.1281665

29.

Lei, Y., Sui, Y.: Fast and precise handling of positive weight cycles for field-sensitive pointer analysis. In: Chang, B.-Y.E. (ed.) SAS 2019. LNCS, vol. 11822, pp. 27–47. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-32304-2_3CrossRef

30.

Lhoták, O., Chung, K.C.A.: Points-to analysis with efficient strong updates. In: Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, pp. 3–16. ACM, USA (2011). https://doi.org/10.1145/1926385.1926389

31.

Lhoták, O., Hendren, L.: Scaling Java points-to analysis using Spark. In: Hedin, G. (ed.) CC 2003. LNCS, vol. 2622, pp. 153–169. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36579-6_12CrossRef

32.

Livshits, V.B., Lam, M.S.: Tracking pointers with path and context sensitivity for bug detection in C programs. In: Proceedings of the 9th European Software Engineering Conference Held Jointly with 11th ACM SIGSOFT International Symposium on Foundations of Software Engineering, ESEC/FSE 2011, pp. 317–326. ACM, USA (2003). https://doi.org/10.1145/940071.940114

33.

Manevich, R., Ramalingam, G., Field, J., Goyal, D., Sagiv, M.: Compactly representing first-order structures for static analysis. In: Hermenegildo, M.V., Puebla, G. (eds.) SAS 2002. LNCS, vol. 2477, pp. 196–212. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45789-5_16CrossRefMATH

34.

Pearce, D.J., Kelly, P.H., Hankin, C.: Online cycle detection and difference propagation for pointer analysis. In: Proceedings of the Third IEEE International Workshop on Source Code Analysis and Manipulation, SCAM 2003, pp. 3–12. IEEE Computer Society, USA (2003). https://doi.org/10.1109/SCAM.2003.1238026

35.

Pearce, D.J., Kelly, P.H., Hankin, C.: Efficient field-sensitive pointer analysis of C. ACM Trans. Program. Lang. Syst. 30(1), 4:1–4:42 (2007). https://doi.org/10.1145/1290520.1290524

36.

Pereira, F.M.Q., Berlin, D.: Wave propagation and deep propagation for pointer analysis. In: Proceedings of the 7th Annual IEEE/ACM International Symposium on Code Generation and Optimization, CGO 2009, pp. 126–135. IEEE Computer Society, USA (2009). https://doi.org/10.1109/CGO.2009.9

37.

Pratikakis, P., Foster, J.S., Hicks, M.: LOCKSMITH: context-sensitive correlation analysis for race detection. In: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2006, pp. 320–331. ACM, USA (2006). https://doi.org/10.1145/1133981.1134019

38.

What is Referential Transparency? (2017). https://www.sitepoint.com/what-is-referential-transparency

39.

Rountev, A., Chandra, S.: Off-line variable substitution for scaling points-to analysis. In: Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, PLDI 2000, pp. 47–56. ACM, USA (2000). https://doi.org/10.1145/349299.349310

40.

Schubert, P.D., Hermann, B., Bodden, E.: PhASAR: an inter-procedural static analysis framework for C/C++. In: Vojnar, T., Zhang, L. (eds.) TACAS 2019. LNCS, vol. 11428, pp. 393–410. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17465-1_22CrossRef

41.

Smaragdakis, Y., Bravenboer, M., Lhoták, O.: Pick your contexts well: understanding object-sensitivity. In: Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, pp. 17–30. ACM, USA (2011)

42.

Sondergaard, H., Sestoft, P.: Referential transparency, definiteness and unfoldability. Acta Informatica 27(6), 505–517 (1990)MathSciNetCrossRef

43.

Soot (2021). https://github.com/soot-oss/soot

44.

Sridharan, M., Fink, S.J.: The complexity of Andersen’s analysis in practice. In: Palsberg, J., Su, Z. (eds.) SAS 2009. LNCS, vol. 5673, pp. 205–221. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03237-0_15CrossRefMATH

45.

Sui, Y., Cheng, X., Zhang, G., Wang, H.: Flow2Vec: value-flow-based precise code embedding. Proc. ACM Program. Lang. 4(OOPSLA), 1–27 (2020). https://doi.org/10.1145/3428301

46.

Sui, Y., Xue, J.: On-demand strong update analysis via value-flow refinement. In: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2016, pp. 460–473. ACM, USA (2016). https://doi.org/10.1145/2950290.2950296

47.

Sui, Y., Xue, J.: SVF: Interprocedural static value-flow analysis in LLVM. In: Proceedings of the 25th International Conference on Compiler Construction, CC 2016, pp. 265–266. ACM, USA (2016). https://doi.org/10.1145/2892208.2892235

48.

Trabish, D., Kapus, T., Rinetzky, N., Cadar, C.: Past-sensitive pointer analysis for symbolic execution. In: Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, ESEC/FSE 2020, pp. 197–208. ACM, USA (2020). https://doi.org/10.1145/3368089.3409698

49.

Trabish, D., Mattavelli, A., Rinetzky, N., Cadar, C.: Chopped symbolic execution. In: Proceedings of the 40th International Conference on Software Engineering, ICSE 2018, pp. 350–360. ACM, USA (2018). https://doi.org/10.1145/3180155.3180251

50.

The T. J. Watson libraries for analysis (WALA) (2021). http://wala.sf.net/

51.

Wang, H., et al.: Typestate-guided fuzzer for discovering use-after-free vulnerabilities. In: Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering, ICSE 2020, pp. 999–1010. ACM, USA (2020). https://doi.org/10.1145/3377811.3380386

52.

Whaley, J.: Context-sensitive pointer analysis using binary decision diagrams. Ph.D. thesis, Stanford University, USA (2007)

53.

Yan, H., Sui, Y., Chen, S., Xue, J.: Spatio-temporal context reduction: a pointer-analysis-based static approach for detecting use-after-free vulnerabilities. In: Proceedings of the 40th International Conference on Software Engineering, ICSE 2018, pp. 327–337. ACM, USA (2018). https://doi.org/10.1145/3180155.3180178

54.

Zhu, J., Calman, S.: Symbolic pointer analysis revisited. In: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI 2004, pp. 145–157. ACM, USA (2004). https://doi.org/10.1145/996841.996860

Titel: Hash Consed Points-To Sets
verfasst von: Mohamad Barbar
Yulei Sui
Verlag: Springer International Publishing
Buch: Static Analysis
Print ISBN: 978-3-030-88805-3

Electronic ISBN: 978-3-030-88806-0

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-88806-0_2

Premium Partner

Bildnachweise

Rittal/© Rittal, NTT Data/© NTT Data, Wildix/© Wildix, Ceyoniq Technology GmbH/© Ceyoniq Technology GmbH, arvato Systems GmbH/© arvato Systems GmbH, Ninox Software GmbH/© Ninox Software GmbH, Everyday Software S.L./© Everyday Software S.L., Redgate/© Redgate, CELONIS Labs GmbH, DC-Datacenter-Group GmbH/© DC-Datacenter-Group GmbH, all for one/© all for one, G Data CyberDefense/© G Data CyberDefense, FAST LTA/© FAST LTA, Vendosoft/© Vendosoft, Kumavision/© Kumavision, Noriis Network AG/© Noriis Network AG, WSW Software GmbH/© WSW Software GmbH, tts GmbH/© tts GmbH

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"