Context-sensitive Points-To Analysis: Comparing precision and scalability
Independent thesis Advanced level (degree of Master (Two Years)), 10 credits / 15 HE creditsStudent thesis
Points-to analysis is a static program analysis that tries to predict the dynamic behavior of programs without running them. It computes reference information by approximating for each pointer in the program a set of possible objects to which it could point to at runtime. In order to justify new analysis techniques, they need to be compared to the state of the art regarding their accuracy and efficiency. One of the main parameters influencing precision in points-to analysis is context-sensitivity that provides the analysis of each method separately for different contexts it was called on. The problem raised due to providing such a property to points-to analysis is decreasing of analysis scalability along with increasing memory consumption used during analysis process. The goal of this thesis is to present a comparison of precision and scalability of context-sensitive and context-insensitive analysis using three different points-to analysis techniques (Spark, Paddle, P2SSA) produced by two research groups.
This comparison provides basic trade-offs regarding scalability on the one hand and efficiency and accuracy on the other. This work was intended to involve previous research work in this field consequently to investigate and implement several specific metrics covering each type of analysis regardless context-sensitivity – Spark, Paddle and P2SSA. These three approaches for points-to analysis demonstrate the intended achievements of different research groups. Common output format enables to choose the most efficient type of analysis for particular purpose.
Place, publisher, year, edition, pages
2012. , 31 p.
Points-To Analysis, Context-sensitivity, Spark, Paddle, P2SSA, Simulated execution, Binary Decision Diagrams, JNI, Soot, Analysis Time, Call Edge, Heap Object, Analysis Memory.
IdentifiersURN: urn:nbn:se:lnu:diva-18225OAI: oai:DiVA.org:lnu-18225DiVA: diva2:514038
Subject / course
Software Technology Programme, Master Programme, 120 credits
2012-03-06, 15:00 (English)
Danylenko, Antonina, PhD student
Hedenborg, Mathias, Professor