lnu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A Framework for Call Graph Construction
Linnaeus University, Faculty of Science and Engineering, School of Computer Science, Physics and Mathematics.
Linnaeus University, Faculty of Science and Engineering, School of Computer Science, Physics and Mathematics.
2010 (English)Independent thesis Advanced level (degree of Master (One Year)), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

In object oriented programming, a Call Graph represents the calling relationships between the program’s methods. To be more precise, a Call Graph is a rooted directed graph where each node of the graph represents a method and each edge (u, v) represents a method call from method u to method v.

Focus of this thesis is on building a framework for Call Graph construction algorithms which can be used in program analysis. Our framework is able to be initialized by different front-ends and constructs various Call Graph algorithms. Here, we instantiate framework with two bytecode readers (ASM and Soot) as front-ends and implement three Call Graph construction algorithms (CHA, RTA and CTA).

At first, we used two above mentioned bytecode readers to read the bytecode of a specific Java program, then we found reachable methods for each invoked method; meanwhile we kept obtained details on our own data structures.  Creating data structures for storing required information about Classes, Methods, Fields and Statements, gives us a great opportunity to implement an independent framework for applying well known Call Graph algorithms. As a result of these data structures, Call Graph construction will not depend on bytecode readers; since, whenever we read the bytecode of a program, we accumulate all necessary points in pre-defined data structures and implement our Call Graphs based on this accumulated data.

Finally, the result is a framework for different Call Graph construction algorithms which is the goal of this thesis. We tested and evaluated the algorithms with a variety of programs as the benchmark and compared the bytecode readers besides the three Call Graph algorithms in different aspects.

Place, publisher, year, edition, pages
2010. , p. 48
Keywords [en]
Call Graph, Program Analysis, Intrprocedural Analysis, Framework, Soot, ASM, Class Hierarchy Analysis, CHA, Rapid Type Analysis, RTA, Class Type Analysis, CTA
National Category
Computer Sciences Software Engineering
Identifiers
URN: urn:nbn:se:lnu:diva-6629OAI: oai:DiVA.org:lnu-6629DiVA, id: diva2:327859
Uppsok
Technology
Supervisors
Examiners
Available from: 2010-07-01 Created: 2010-06-30 Last updated: 2018-01-12Bibliographically approved

Open Access in DiVA

fulltext(1445 kB)3185 downloads
File information
File name FULLTEXT01.pdfFile size 1445 kBChecksum SHA-512
1b3990959bb0dba14199adbf422e574deddddf99f63bc71109dbb2215b5de9606fb2c0305973763b0a425f64d1e2d3519d019c90555ba8772ec5e8504c0f3457
Type fulltextMimetype application/pdf

By organisation
School of Computer Science, Physics and Mathematics
Computer SciencesSoftware Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 3185 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 864 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf