Show simple item record

dc.contributor.advisorRamanathan, Murali Krishna
dc.contributor.authorSridhar, G
dc.date.accessioned2018-06-14T07:31:35Z
dc.date.accessioned2018-07-31T04:39:16Z
dc.date.available2018-06-14T07:31:35Z
dc.date.available2018-07-31T04:39:16Z
dc.date.issued2018-06-14
dc.date.submitted2017
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/3708
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/4578/G28296-Abs.pdfen_US
dc.description.abstractObtaining an accurate whole program path (WPP) that captures a program’s runtime behaviour in terms of a control-flow trace has a number of well-known benefits, including opportunities for code optimization, bug detection, program analysis refinement, etc. Existing techniques to compute WPPs perform sub-optimal instrumentation resulting in significant space and time overheads. Our goal in this thesis is to minimize these overheads without losing precision. To do so, we design a novel and scalable whole program analysis to determine instrumentation points used to obtain WPPs. Our approach is divided into three components: (a) an efficient summarization technique for inter-procedural path reconstruction, (b) specialized data structures called conflict sets that serve to effectively distinguish between pairs of paths, and (c) an instrumentation algorithm that computes the minimum number of edges to describe a path based on these conflict sets. We show that the overall problem is a variant of the minimum hitting set problem, which is NP-hard, and employ various sound approximation strategies to yield a practical solution. We have implemented our approach and performed elaborate experimentation on Java programs from the DaCapo benchmark suite to demonstrate the efficacy of our approach across multiple dimensions. On average, our approach necessitates instrumenting only 9% of the total number of CFG edges in the program. The average runtime overhead incurred by our approach to collect WPPs is 1.97x, which is only 26% greater than the overhead induced by only instrumenting edges guaranteed to exist in an optimal solution. Furthermore, compared to the state-of-the-art, we observe a reduction in runtime overhead by an average and maximum factor of 2.8 and 5.4, respectively.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG28296en_US
dc.subjectProgram Tracingen_US
dc.subjectPerformance Analysisen_US
dc.subjectDynamic Control Flowen_US
dc.subjectWhole Program Path (WPP)en_US
dc.subjectProgram Path Tracingen_US
dc.subjectPath Profilingen_US
dc.subjectSoftware Testingen_US
dc.subject.classificationComputer Scienceen_US
dc.titleEfficient Whole Program Path Tracingen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record