Show simple item record

dc.contributor.authorGharat, PMen
dc.contributor.authorKhedker, UPen
dc.contributor.authorMycroft, Alanen
dc.date.accessioned2018-09-05T11:05:30Z
dc.date.available2018-09-05T11:05:30Z
dc.date.issued2016-01-01en
dc.identifier.issn0302-9743
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/279111
dc.description.abstract© Springer-Verlag GmbH Germany 2016. Bottom-up interprocedural methods of program analysis construct summary flow functions for procedures to capture the effect of their calls and have been used effectively for many analyses. However, these methods seem computationally expensive for flow- and context- sensitive points-to analysis (FCPA) which requires modelling unknown locations accessed indirectly through pointers. Such accesses are com- monly handled by using placeholders to explicate unknown locations or by using multiple call-specific summary flow functions. We generalize the concept of points-to relations by using the counts of indirection levels leaving the unknown locations implicit. This allows us to create sum- mary flow functions in the form of generalized points-to graphs (GPGs) without the need of placeholders. By design, GPGs represent both mem- ory (in terms of classical points-to facts) and memory transformers (in terms of generalized points-to facts). We perform FCPA by progressively reducing generalized points-to facts to classical points-to facts. GPGs distinguish between may and must pointer updates thereby facilitating strong updates within calling contexts. The size of GPGs is linearly bounded by the number of variables and is independent of the number of statements. Empirical measurements on SPEC benchmarks show that GPGs are indeed compact in spite of large procedure sizes. This allows us to scale FCPA to 158 kLoC using GPGs (compared to 35 kLoC reported by liveness-based FCPA). Thus GPGs hold a promise of efficiency and scalability for FCPA without compro- mising precision.
dc.titleFlow- and context-sensitive points-to analysis using generalized points-to graphsen
dc.typeConference Object
prism.endingPage236
prism.publicationDate2016en
prism.publicationNameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en
prism.startingPage212
prism.volume9837 LNCSen
dc.identifier.doi10.17863/CAM.26491
rioxxterms.versionofrecord10.1007/978-3-662-53413-7_11en
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2016-01-01en
dc.contributor.orcidMycroft, Alan [0000-0001-7013-8572]
dc.identifier.eissn1611-3349
rioxxterms.typeConference Paper/Proceeding/Abstracten
pubs.conference-nameInternational Static Analysis Symposiumen
rioxxterms.freetoread.startdate2017-01-01


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record