Project 1

Project Overview

This project involves implementing the construction algorithm for the FDT (Frame Document Tree), a hierarchial structure representation between the frames and pages in a web program, and gathering
and evaluating statistics on the characteristics of FDT's for real web applications. The open ended part of this project is the generalization to the various languages available for web programming.

Tasks involved:

  1. First you have to understand the concept of a web application [2], and what we are trying to do. Sections 1 and 2  of [1] will give you a pretty good idea of what we are trying to do.  You also have to understand the purpose of testing and why testing is done. A good reading would be [7, 6].
  2. Then you have to learn the languages in which web applications have been written, since we are trying to model them, based on the code. Understanding characterisitics of the language that the web applciations are written in will help you follow if the implementation that you are coming up with is doing the correct required thing. We have looked at web applications written in html, javascript. A good understanding of javascript would help a lot[8]. You can learn it as you go along. Try to familiarize yourself with terms such as frame, document, page with respect to html and javascript. The syntax and the semantics of the languages you can learn as you go along.
  3. The implementation that you will develop is of the FDT[1]. Once you have a good understading of  the languages used and what we are trying to do, it is time to jump into the algorithm that we have come up with. Your goal is to follow the algorithm to come up with a structure that looks similar to what we have. We will discuss design decisions for the actual implementation, but the overall process involves 2 steps
    • You have to parse the web application to get the fields that you want. For eg: in the FDT, you are looking for a keyword <frameset>. You have to be ableto read in the web page and pick out occurences of these terms. These terms denote the nodes and edges of your graph, as you will understand once youknow what the FDT does. A language that recognizes tokens and makes it easy to read them is Perl.
    • Once you have all your nodes and edges, you will code in a language (C, C++, Java ?? ) to generate a data structure and also print the FDT as shown in the paper.
  4. Generalize the FDT to other web programming languages. Run code from web applications that are written in various web programming language through your implementation and see if the FDT is  generated as desired.
  5. Extend the implementation to also generate statistics on characteristics of FDT's (eg. #nodes, #edges of different types).
  • Perl
  • Language(C, C++, Java??)
  • Understanding of Javascript and HTML (for now)
  • Data structures

Background reading

  1. Modelling Web applications for static analysis. Sreedevi Sampath,Amie Souter, Laura McGlade, Margarita Golod, Lori Pollock.
  2. Characterisitics of web applications, Sreedevi Sampath.
  3. Modeling web applications with UML, Jim Conallen
  4. Modeling web applications architecture with UML, Jim Conallen.
  5. Untangling the woven web: testing web based software. Gary McGraw, David Hovemeyer
  6. Website testing. Edward Miller
  7. Testing of object-oriented software, excerpt from Amie's dissertation.
  8. Book: Java script. Gosselin.
Additional reading
  1. Object-based data flow testing of web applications. Chien Hung Liu, David C. Kung, Pei Hsia, Chih-Tung Hsu. IEEE 2000.
  2. Structural Testing of Web Applications. Chien Hung Liu, David C. Kung, Pei Hsia, Chih-Tung Hsu. IEEE 2000.
  3. Building a tool for analysis and testing of web applications. Problems and Solutions. Filippo Ricca and Paolo Tonella.


Project 2

Project Overview

This project will focus on design and implementation of an initial prototype of the Web Program Frame Graph (WPFG) - program representation for web programs.

Tasks involved:

  1. By now if you have implemented the FDT, you are probably very familiar with the concept of web applications and testing web applications. You are also probably familiar with the main entities of the FDT that you have modelled.
  2. The next step is to design and build an initial prototype implementation of the WPFG. For this, you will have to read the section of [1] related to buliding the WPFG. The WPFG is more complex than the FDT, in that it contains many more things to look out for when building it. The WPFG captures the control flow of web applications. There are various types of edges and nodes, that have to be represented in your implementation.

  3. Before we go into the details of implementing the construction algorithm for the the WPFG, you need to have an idea of the basics of a compiler/interpreter and how it works. (Reading:  [1])

    Lets see how we go about recognizing the features of a web application that have to be captured and modelled for implementing the WPFG. We need control flow within the web application to be modelled.That is the essence of the WPFG.

  4. Do some research, go out and check on the web, for interpreters for javascript and html. A good place to start searching would be at the developers site for javascript(developer: netscape). An interpreter for javascript that I found is at It might be a reference point to start looking or to guide you in what you have to look for when searching elsewhere.
  5. Investigate and design implementation of the WPFG with local cfg's (control flow graphs) for each unit. Can we use Perl or do we need a parser? Find a parser for javascript and HTML by searching on the web (open source code is what we are looking for, so an open source development web site would be a good place to start looking).
  6. Design implementation of the local cfg's


  • Web searching
  • Perl
  • Building data structures.
  • Parser and making changes to parser to generate desired information for the WPFG.
  1. Book: Compilers: Principles, Techniques and Tools. Aho, Sethi and Ullman. Chapter 1
  2. Rest are the same as for Project 1