CO4206 / CO7206 / CO7506 (This assignment carries 25% of the final mark)

Assignment 1: Building Your Own Code Slice Deadline: 23:59 GMT, Sunday 11th of November 2018 Challenge

The task is to build a program slicer, that you can use to slice methods in Java programs. The

assignment will be carried out via GitHub classroom. Your assignment repository will be populated with a few Java classes (that use the ASM  bytecode  analysis  library).  This  will  also  provide  you with  one class that you will have to complete, by inserting and committing your own code. Please clone your own repository for the assignment by following this link:

https://classroom.github.com/a/PaLK_6xa

You    are    encouraged    to    commit    your    work   to    this    repository    regularly.   Within    the

dependenceAnalysis.Analysis package, you will find the following classes:

1. The Analysis class is an abstract class that contains the code to produce a control flow graph for a given method (stored as the controlFlowGraph data member). This is available to any sub-classes.
2. There are three classes that inherit from this Analysis class, each of which is intended to carry out some form of
3. The ControlDependenceTree class should produce a Control Dependence Tree from the control flow
4. The PostDominatorTree should produce a post dominator tree from the control flow graph.
5. The ProgramDependenceGraph class should produce a program dependence graph, compute slices over the graph, and compute some slice-based

6. The PostDominatorTree and ControlDependenceTree classes have already been completed. If you instantiate the PostDominatorTree class with a ClassNode and a

MethodNode object, and call the computeResult() method, it will return a post-dominator tree. If you go to ControlDependenceTreeTest and PostDominatorTreeTest classes, you will be able to run them.

This provides you with an idea of how you should go about providing the code for the ControProgramDependenceGraph class. You are free to call any of the code in the PostDominatorTree and ControlDependenceTree class as you see fit. You are encouraged to write (and continuously execute) your own tests, to check that the code is behaving correctly.

To start with, you will be given a small set of classes. The specific tasks are as to produce code that can achieve the following:

1. Compute the Program Dependence Graph for any given method. Add the necessary code into the analysis.ProgramDependenceGraph.computeResult() method.
2. Compute a backward slice for a given node in a method. Add the necessary code into the analysis.ProgramDependenceGraph.backwardSlice(No de) method.
3. Compute a slice-based metric (detailed below) for a given method. Add the necessary code into the analysis.ProgramDependenceGraph.computeTightness () method.

Computing Tightness

The slice-based metrics offer a detailed means by which to quantify, for example, how cohesive a piece of source code is. Tightness is computed as follows:

The number of nodes that occur in every possible slice of a method divided by the total number of nodes in that method.

Computing Overlap

Overlap is computed by, first of all, computing every possible “output slice” — a slice taken from a point in the code that represents the end-point for a data-flow path through the method.

1. Identify each output point by identifying those nodes with incoming data-dependence edges, but that do not have any outgoing data dependence
2. For each slice, count the number of nodes in that slice that belong to all other output slices.
3. Take the total number, and divide that by the number of

Implementation Notes

When implementing your solutions, you are free to add additional classes and methods as you see fit. However, you must not change any of the code that is given. Do not change the code belonging to the Analysis class, and do not change any of the interfaces (e.g. by adding parameters to methods). This point is important, because the implementation you submit (by

committing to GitHub) will be tested by test harnesses that will expect the interface to have remained as it is.

All of the analyses you implement must be carried out with respect to the controlFlowGraph object that is a data member of the respective ControlDependenceTree and ProgramDependenceGraph classes (inherited from the Analysis class).

Make sure that you include lots of comments in your source code. Include a small sentence or two to state what each method does and how it achieves this. The comments must demonstrate that you understand how the code is working. If the method is particularly large (try to avoid this), include in-line comments as well. It is vital that we are able to understand what you have submitted.

All of the code you submit must be your own. You may not import any additional frameworks or libraries. This work is assessed, and will be subject to extensive checks for plagiarism. If plagiarism is suspected, the suspected cases will be passed on to the departmental plagiarism officer, and will be subject to routine departmental plagiarism procedures. Ultimately confirmed cases of plagiarism will be given a mark of zero, and may contribute to follow-on penalties in accordance with University guidelines (ttps://www2.le.ac.uk/offices/sas2/assessments/plagiarism/penalties).

It goes without saying that you should not share your repositories, or any of the code that will count as your submission, with your fellow students.

How Will My Code be Assessed?

We will check your code out of your GitHub repository, and will run some tests on it. Feel free to include your own test code to convince yourself that it is behaving correctly. You can see an example of a completed test case in: dependenceAnalysis.analysis.PostDominatorTreeTest (stored in the test subdirectory)

Submission

The work is to be submitted by pushing to GitHub (using git push). The submission will count as the last submission made before the deadline. Be sure to commit and push your work regularly, to avoid any confusion on submission day. Submissions via email or other means will not be accepted. You must submit via Github.

In the event where no pushes have been made, and the student eventually does push something, these late submissions will be subject to standard university penalties: https://www2.le.ac.uk/offices/sas2/assessments/late-submission

Questions

If you have any questions about this assignment, please use the dedicated forum on Blackboard (“Questions about Assignment 1”). To ensure fairness, and that you all receive the same information and assistance, please use this forum only.

Assessment Guidelines

1. Distinction
   1. Your solution contains implementations for all of the components, can compute slices on methods, and can compute the slice metrics
   2. Your code is well-structured and
   3. Your code is easily executable, and has followed the above guidelines exactly (none of the interfaces or given code has been changed)

2. Merit
   1. Your solution contains code to compute tightness and overlap and combines them into a program dependence graph (failing to produce the program dependence graph could still result in a borderline merit, depending on other factors)
   2. Your code is well-structured and
   3. Your code is easily executable, and has followed the above guidelines exactly (none of the interfaces or given code has been changed).
3. Pass
   1. Your solution computes either compute tightness or
   2. Your code is readable and can be understood, even if there are design
   3. Your code is executable, even if it fails to adhere to the implementation guidelines
   4. Fail
      1. Your solution fails to adhere to the basic requirements for a pass