We address in this paper the reverse engineering issue in the Web applications. The maintenance process of this kind of applications is often hardly performed due to the lack of documentation. In most cases, the documentation associated to the Web application does not exist or rarely complete and up-to-date. We aim to present a solution which describes the structure of Web application in order to gain their better understanding and so facilitate their maintenance. We describe a method to infer Web publishing programs, specifically defined as database-driven programs producing dynamic documents. We address a typical reverse engineering situation where the program is a “black box” that takes a database instance (the input) and produces a dynamic document (the output). Our method attempts to understand and describe the program.
1.1
The production of dynamic (X)HTML documents from relational databases is probably one of the most common techniques used in Web applications development. Such documents combine static parts that correspond to free text and (X)HTML rendering instructions (e.g., tags), and dynamic parts which are retrieved at run time from a relational instance. Many specialized languages (i.e., Java/JSP, PHP, ASP) and development frameworks (Struts, .NET, PHP/MVC) make the production of dynamic Web sites a relatively easy task, and this contributes to the richness and accessibility of the Web. A downside is that publishing programs are often poorly written, and tend to be quite difficult to understand and maintain. The situation even degrades as the application evolves through maintenance and evolutions.
In the present paper we describe the main aspects of a method to address this situation. Our goal is to derive useful information on the structure and behavior of publishing programs without having to delve into the source code. The main idea is that we can infer how a program P accesses the underlying
Data graph
Canonical instances
I1 I2 ...
In
Publishing Program P
Mapping Program description
Dynamic documents
D1 D2 ...
Dn
Analysis Document graph database and merges the dynamic and static parts by just examining the input and output. Moreover this re-ingeneering process needs only an access to the database schema and the right to run P on instances of this schema. We do not require an access to the actual database instance, nor do we need the code of the application. This preserves the privacy of business data, and allows to cope with situations where the source code is no longer available. 1.2
Basically our method produces carefully chosen instances of the database, runs P, and makes some inferences of the program behavior by analysing the dynamic document produced as output. Figure 1 illustrates the main components involved in the process. Let us briefly describe their role before entering into details.
We apply P to canonical instances of the database schema and obtain
dynamic documents. The concept of canonical instance denotes both complete and
unambiguous instances [
Next, dynamic documents are analysed in order to distinguish the static parts from the dynamic ones. This is done through an iteration of program executions that produce dynamic documents from as many canonical instances as necessary. The dynamic part is modeled as a graph of values, constructed from both the document structure and the database schema. This analysis process is described in Section 3.
Finally, we construct a mapping between the graph of values of a document Di and a subgraph of the canonical instance Ii. This mapping constitutes an interpretation of the program P that carries out a navigation in Ii, retrieves some values and merge these values with static text to create Di. We can then produce a description of P at a suitable abstraction level independent from specific details such as, for instance, the programming language. This final step is presented in Section 4.
The rest of the paper develops this brief overview, and discusses the
perspective of the approach, as well as related work (Section 5). Due to space limitations,
the presentation is mostly driven by examples based on a simple database that
represents movies with their (unique) director and their (many) actors
(Figure 2). The interested reader is referred to[
Movie id last_name first_name 20 Eastwood Clint 21 Hackman Gene 29 Pialat Maurice 30 Dutronc Jacques 68 Kurosawa Akira
Artist title id_actor character Unforgiven 20 William Munny Unforgiven 21 Little Bill Dagget Van Gogh 30 Van Gogh Absolute Power 21 President Allen Richmond
Cast
As mentioned previously, we model a database instance as a labeled directed graph GI , and rely on a query language on this graph which constitutes a syntaxneutral (declarative) specification of a publishing program written in Java/JSP or in any other programming framework.
Our reverse-engineering process operates on a view of the relational instance where tuples are seen as internal nodes, values as leaf nodes, and edges represent either tuple-to-tuple dependencies or tuple-to-attribute dependencies. Figure 3 shows the data graph of the instance of Figure 2. We distinguish functional dependencies between nodes (e.g., between a movie node and its director node)
Clint
first_name Eastwood last_name
id 20 (Artist)
Cast
Actor
(Cast) character
Director Direct Cast (Movie)
Movie Movie and multivalued dependencies (e.g., between a movie node and its actor nodes). The former are shown with white-headed arrows, the latter with black ones.
We associate to this model a query language, called DocQL, which combines navigation in the data graph with instantiation of the textual fragments that contribute to the final document. A DocQL query is essentially a tree of path expressions which denote the part of the graph that must be visited in order to retrieve the data to include in the final document. Path expressions use an XPath-like syntax. An expression p is interpreted with respect to an initial node Ni (unless it begins with db which plays the role of / in XPath), and delivers a set of nodes, called the terminal nodes of p (with respect to Ni). Each path is associated to a fragment which is instantiated for each terminal node. Path and fragments are syntactically organized in rules of the form @path[condition]{fragment}, with a path expression, a node condition and fragment is the fragment instantiated for each instance of path.
The following example shows a DocQL query over our Movies database. It produces a (rough) document showing the movie Unforgiven along with its director and actors. }
}
The semantics of the language corresponds to nested loops that explore the data graph, one loop per rule. Looking at the previous example, we first search for the node Movie with title Unforgiven. Taking this node as an initial one, the value of each (unique) path title, year, etc., is evaluated. The multiple path Cast leads to all the nodes that represent one of the characters of Unforgiven. Applied to the data graph of Figure 3, one obtains the following document as result of the previous example:
Unforgiven, 1992, directed by Clint Eastwood, Featuring: - Clint Eastwood as William Munny - Gene Hackman as Little Bill Dagget
Aggregation and negation cannot be directly expressed in DocQL, but aggregated values can be obtained via the mapping that transforms the relational instance to the virtual data graph (an even simpler solution is to define SQL views with group by clauses, which can then be exported in the data graph). We shall discuss these limitations in Section 5.
Our method relies on the creation of specific instances satisfying two conditions: completeness and non-ambiguity. In short, the first condition ensures that the program always finds query results during its navigation in the database. The second condition is meant to allow the identification of a unique subgraph of the instance, isomorphic to the set of values found in the dynamic document. Completeness. An instance is said complete if, for each one-to-many dependency E 1 →∗ E0 and each tuple e instance of E, there exists an instance e0 of E0 associated to e. Let us take the example of the dependency directed by that links a director and its movies. In terms of the relational schema, there is an integrity constraint that ensures that each movie refers to a director (see Figure 2). The completeness constraint states, in addition, that each tuple in table Artist is referred to by a tuple in table Movie.
Therefore, in a complete instance of our schema, each artist is the director of a movie. This is by no way a realistic constraint. It is only intended to ensure that a publishing program that wishes to show a film, its actors, and for each actor, the list of films possibly directed by this actor, will produce the most complete result document. In other words a complete instance allows to obtain complete documents, and thus a complete view of the program output.
The instance of Figure 3 is not complete. If we remove the node squared with dashed lines (and the corresponding Artist subgraph), the instance becomes complete, because the only remaining artist is Clint Eastwood who turns out to be both an actor and a director. Note the cycle in the data graph that corresponds to a cyclic dependency in the graph schema.
Non-ambiguity. The non-ambiguity condition can be informally stated as follows: if N and N 0 are two nodes in the data graph, then the path that links N to N 0 can be uniquely determined. The instance on Figure 3 is ambiguous, even after removal of the node that corresponds to Gene Hackman. Indeed, if
Unforgiven a. Minimal cycle (2 edges) Clint Eastwood Woody Allen Sidney Pollack Robert Redford
Husbands and Wives
Jeremiah Johnson
...
b. Cycle of size k*2 we are given the values ’Eastwood’ and ’Unforgiven’ found in a dynamic document, there is an ambiguity on the meaning of the Artist node, which can be interpreted either as the director or an actor of the film.
Ambiguity is a consequence either of two distinct nodes sharing the same value, or of cycles in the database instance. The first problem can easily be avoided by generating distinct values. The second problem is trickier because simply removing cycles would contradict the completeness property. As mentioned above, the database needs to represent by cycles in the instance the cycles of the schema in order to obtain a solution for any path chosen by the program from any node in the graph.
A trade-off is here necessary. Note first that the cycle size in the instance is proportional to the cycle size in the schema. Figure 4.a shows a minimal cycle in our sample instance, of size 2, and Figure 4.b its generalization to a cycle of length 2 × k, with k > 1. The value of k is a parameter of the instance construction which represents the upper-bound on the number of tables joined by a single SQL query of the program (or equivalently, k is the longuest path used by the program during its navigation in the data graph). k must be chosen large enough so that no ambiguity can arise when a link must be created between two values extracted from a dynamic document.
In the following we call a complete and non-ambiguous instance a canonical
instance. An algorithm to create canonical instances is given in[
Assume now that we obtain a document D from the execution of the program P on a canonical instance I. We need to distinguish static parts from dynamic parts. From the dynamic part we will be able to construct the mapping that associates the document structure to a database subgraph. For the sake of clarity, we illustrate the mechanism with the following document D, obtained by running P on a canonical instance I.
Unforgiven, 1992, directed by Clint Eastwood, Featuring: <ol>
<li> Gene Hackman, as Little Bill Dagget</li> </ol>
Some words (e.g., “Featuring”) are part of the static content, while others (e.g., “Eastwood”) come from the database. Let L(D) be the list of words constituting the document and L(I) be the list of words from the canonical instance. A first approximation is to consider that W = L(D) ∩ L(I) is the dynamic content of the document. We can then perform a full-text search in the canonical instance for each word in W , identifying the tuples which have been retrieved by the program, and the position of dynamic data in the document. Note however that the latter information may be a superset of the dynamic list, due to the presence of words in the static part which also appear in the instance. This would be the case for instance if the static content contains the word “little” which is found as well in our canonical instance.
This problem can be solved by using two canonical instances I and I0 such that L(I) ∩ L(I0) = ∅, i.e., the instances are fully distinct (recall that we control the content of our canonical instance). Assume for instance that I0 contains a description of the movie Husbands and Wives. The dynamic document D0, resulting from the execution of the program over the canonical instance I0, is: Husbands and Wives, 1991, directed by Woody Allen, Featuring: <ol>
<li> Sidney Pollack as Jack</li> </ol>
The list of words of the static content can be obtained as Y = (L(D) ∩ L(D0)). In our example, words like “directed”, ”by”, ”Featuring” are commons words between D and D0 and are parts of the static content of the publishing program.
Dynamic part of the program can be now inferred from instance I as L(D) − Y , whereas the list for I0 is L(D0) − Y . It remains to “mark” the dynamic part in one of the dynamic documents. Here is the marking for D:
Each word w enclosed in the @{} tag is known to come from the instance. Moreover, since this instance is complete, we can identify the nodes in the data graph and compute the subgraph that associates these nodes, as explained below. 4
Several algorithms for keyword-based searches in relational databases have been
proposed recently, like Discover[
Block 1
Movie Artist
N0
N1 id last_name first_name 20 Eastwood Clint
Title year id_director genre Unforgiven 1992 20 Western Cast
Block 2 N2 N3
Artist id last_name first_name 2& Hackman Gene keywords over a canonical instance. Banks actually represents the mapping that associates the structure of the dynamic document to the subgraph of the canonical instance. The result of this association is illustrated on Figure 5.
Four tuples have been found by the Banks algorithm, which correspond to four nodes N0, N1, N2, N3. N0 is a Movie tuple, N1 an Artist tuple representing the director of the movie, N2 and N3 are respectively the Cast and Artist representing an actor of the movie. Each edge in the graph is labeled by the table name. Recall that black-headed arrows represent one-to-many relations, whereas white-headed arrows represent one-to-one relation (i.e., a referential integrity constraint).
In order to produce the DocQL query, we group nodes in blocks. A block consists of a context node and of satellite nodes, containing all the nodes which have a one-to-one dependency with the context node. Figure 5 shows two blocks. The first one has for a context node N 0, and a satellite node, N1. The second block is composed of N2 (context node) and N3 (satellite node). The intuition behind the block structure is that, during its navigation in the database, the program “stops” on some node N , and produces a dynamic fragment whose dynamic part consists of all the values which are monovalued with respect to N . These values consist of (i) the attributes of the context node (e.g., the title of the movie N0) and (ii) attributes of the nodes which have a one-to-one dependency with N (e.g., the name of the director, attribute of N1).
A DocQL query is a tree of rules of the form @path[condition]{fragment}. One rule is constructed for each block, and the edge labels yields the structure of the query: }
This ends the part of the reingeneering process which can be carried out independently from human expertise. Running the query on the canonical instances I and I0 should produce documents D and D0, respectively. Although this works well on this simple example, in most cases the DocQL query produced by this process will be a more or less complete approximation of the program. In the next Section we discuss how this approximation can be refined and completed by an expert user. 5
We believe that the method constitutes a good basis for a further refinement of the program description. However it is limited in many respects. A first of these limits is the expressive power of the target language. It models conjunctive SQL queries with natural joins (i.e., joins that map primary keys with foreign keys). From our experience, it is extremely rare to express non-natural joins, so we claim that this is hardly a restriction.
A second limit is a small indeterminacy in the exact limit of the blocks fragments. Looking back at the example above, there is no well-founded reason to include or exclude the tags <ol>...</ol> from the fragment of the block 2. This limits seems harmless, since it appears quite easy for a user to see that the <ol> tag occurrences are independent from the number of tuples found in the Cast table. An automatic recognition is probably possible in that case.
A third limit is the inability of our method to cope with constant values used in the program queries. These values can be either hardcoded in the SQL expressions in the source code, or, equivalently, provided as parameters to the program which dynamically introduce them in query expressions. The only solution is to elaborate with an expert user a list of the database fields which are subject to selection predicates in the program.
Web engineering community proposed several languages, methods and
processes for the development of Web applications like WebML[
We outlined in this paper the main principles of a reverse-engineering method devoted to Web publishing applications. The method relies on a few concepts which help to construct an interpretation of publishing programs which is both precise and language-independent. As mentioned in the discussion part, a fully automatic analysis seems impossible to achieve, but we consider the ideas presented here as a sound and promising framework for building a semi-interactive analysis tool where an expert user drives the reconstitution of a program semantic. We are currently working on an implementation of such a tool.