A Framework for Understanding Web Publishing Applications Sonia Guéhis Paris-Dauphine University, Place du Marechal de Lattre de Tassigny, 75775 Paris, France sonia.guehis@dauphine.fr Abstract. 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. Keywords: reverse engineering, Web publishing programs, dynamic doc- uments, canonical instances 1 Introduction 1.1 Context and motivations The production of dynamic (X)HTML documents from relational databases is probably one of the most common techniques used in Web applications devel- opment. Such documents combine static parts that correspond to free text and (X)HTML rendering instructions (e.g., tags), and dynamic parts which are re- trieved 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 con- tributes to the richness and accessibility of the Web. A downside is that pub- lishing programs are often poorly written, and tend to be quite difficult to un- derstand 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 Proceedings of WISM 2009 Canonical Dynamic instances documents Publishing Program P D1 111111 000000 I1 000000 111111 D2 I2 ... ... In Dn Data graph Analysis 10 0 01 1 0 1 Mapping 00 110 1 0 11 0 0 1 0 11 0 0 1 1 01 0 0 1 1 0 0 1 0 10 1 1 0 0 10 1 1 00 101 10 01 1 1 00 1 Document graph 0 01 1010 Program description Fig. 1. Overview of the reverse engineering process 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 Process overview 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 dy- namic documents. The concept of canonical instance denotes both complete and unambiguous instances [1]. Intuitively, a canonical instance enjoys suitable prop- erties for the analysis of the dynamic document produced by a program. For instance, given a set of values, one can determine without ambiguity the set of tuples (if such a set exists) of the instance that contain these values, as well as their dependencies. In order to model conveniently such structured sets of tu- ples, we view the relational instance as a data graph where tuples and values are nodes, and edges represent dependencies. The data graph model and canonical instances are presented in Section 2. 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. Proceedings of WISM 2009 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 perspec- tive 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 (Fig- ure 2). The interested reader is referred to[1] and [2] for formal definitions and technical details on the DocQL language and our concept of complete instance. (see http://www.lamsade.dauphine.fr/∼guehis/Protos.htm). id last_name first_name title year id_director genre 20 Eastwood Clint Unforgiven 1992 20 Western 21 Hackman Gene Van Gogh 1990 29 Drama 29 Pialat Maurice Kagemusha 1980 68 Drama 30 Dutronc Jacques Absolute Power 1997 20 Crime 68 Kurosawa Akira Movie 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 Fig. 2. An instance of the Movies database 2 Modeling the input: canonical instances 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 syntax- neutral (declarative) specification of a publishing program written in Java/JSP or in any other programming framework. Data model and query language. 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) Proceedings of WISM 2009 Unforgiven Clint 1992 first_name Eastwood title Western last_name year id Director genre 20 (Artist) Cast Direct Little Bill Dagget Actor Cast character Cast (Movie) Movie Cast Movie (Cast) (Artist) (Cast) id 21 Actor last_name character first_name Hackman William Munny Gene Fig. 3. A subset of the data graph of our sample instance 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 com- bines 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 termi- nal 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. @db.Movie[title=’Unforgiven’]{ @title{}, @year{}, directed by @director.first_name{} @director.last_name{} Featuring: @Cast{ - @artist.first_name{} @artist.last_name{}as @character{} } } Proceedings of WISM 2009 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 ag- gregated 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. Canonical instances. Our method relies on the creation of specific instances satisfying two condi- tions: 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 depen- dency E 1 →∗ E 0 and each tuple e instance of E, there exists an instance e0 of E 0 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 be- comes 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 fol- lows: 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 Proceedings of WISM 2009 Clint Eastwood Woody Allen Sidney Pollack Robert Redford Director Cast Cast Director Unforgiven Husbands and Wives Jeremiah Johnson ... a. Minimal cycle (2 edges) b. Cycle of size k*2 Fig. 4. Generating cycles in a canonical instance we are given the values ’Eastwood’ and ’Unforgiven’ found in a dynamic docu- ment, 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 men- tioned 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[1]. 3 Modeling the output: dynamic documents 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:
  1. Gene Hackman, as Little Bill Dagget
Proceedings of WISM 2009 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 consti- tuting 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 con- tent 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 how- ever 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 I 0 such that L(I) ∩ L(I 0 ) = ∅, i.e., the instances are fully distinct (recall that we control the content of our canonical instance). Assume for instance that I 0 contains a description of the movie Husbands and Wives. The dynamic document D0 , resulting from the execution of the program over the canonical instance I 0 , is: Husbands and Wives, 1991, directed by Woody Allen, Featuring:
  1. Sidney Pollack as Jack
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 I 0 is L(D0 ) − Y . It remains to “mark” the dynamic part in one of the dynamic documents. Here is the marking for D: @{Unforgiven}, @{1992}, directed by @{Clint} @{Eastwood}, Featuring:
  1. @{Gene} @{Hackman}, as @{Little} @{Bill} @{Dagget}
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 Producing the publishing program Several algorithms for keyword-based searches in relational databases have been proposed recently, like Discover[3], DBXplorer[4] and Banks[5]. Banks seems an appropriate choice. It relies on a graph representation of the instance similar to our data graph and returns, given a set of keywords, a set of tree of tuples. The root node is called an information node and the tree a connection tree. In our case, the Banks process returns a unique tree connection, since we search Proceedings of WISM 2009 Block 1 Movie Title year id_director genre N0 Unforgiven 1992 20 Western Artist Cast Block 2 N1 N2 id last_name first_name Artist 20 Eastwood Clint N3 id last_name first_name 2& Hackman Gene Fig. 5. Connection tree and its mapping to the associated DocQL query keywords over a canonical instance. Banks actually represents the mapping that associates the structure of the dynamic document to the subgraph of the canon- ical 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 represent- ing 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 in- tegrity 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: @Movie{ @title{}, @year{}, directed by @artist.first_name{} @artist.last_name{} Featuring:
    @Cast{ Proceedings of WISM 2009
  1. @artist.first_name{} @artist.last_name{} as @character{}
    2. }
} This ends the part of the reingeneering process which can be carried out inde- pendently from human expertise. Running the query on the canonical instances I and I 0 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 Discussion and related work 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
    ...
from the fragment of the block 2. This limits seems harmless, since it appears quite easy for a user to see that the
    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 expres- sions 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 pro- cesses for the development of Web applications like WebML[6], UWE[7], Hera[8] and OO-H[9]. But, all those solutions don’t address the problem of reverse en- gineering as we define it (namely: a known database, a known output, but an unknown program). Vaquista[10] proposes a solution to infer the presentation model of a Web page and considers only the modeling how the “static part”. A proposal of interest is WARE (Web Application Reverse Engineering) tool[11] which attempts to describe an application in terms of UML diagrams.These di- agrams are helpful to understand the Web application structure. Revangie[12] is oriented toward an analysis of the user interface model, through the exploration of the Web forms of an application. proposals deal are useful for high level struc- tures description, e.g., the graph of pages in a Web site. They can be considered as complementary of our framework which aims at giving a detailed description of a specific module. Proceedings of WISM 2009 6 Conclusion 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 pre- sented here as a sound and promising framework for building a semi-interactive analysis tool where an expert user drives the reconstitution of a program seman- tic. We are currently working on an implementation of such a tool. References 1. Guéhis, S., Gross-Amblard, D., Rigaux, P.: Publish By Example. In: 8th IEEE International Conference on Web Engineering, pp. 45–51. IEEE Computer Society Press, Los Alamitos, CA, USA (2008) 2. Guéhis, S., Rigaux, P., Waller, E.: Data-driven Publication of Relational Databases. In: 8th IEEE International Database Engineering & Applications Symposium, pp. 267–272. IEEE Computer Society Press, Delhi, India (2006) 3. Hristidis, V., Papakonstantinou, Y.: DISCOVER: Keyword Search in Relational Databases. In: 28th IEEE International Conference on Very Large Data Bases, pp. 670–681. Hong Kong, China (2002) 4. Agrawal, S., Chaudhuri, S., Das, G.: DBXplorer: A System for Keyword-Based Search over Relational Databases. In: 18th IEEE International Conference on Data Engineering, pp. 5–16. IEEE Computer Society Press, San Jose, CA (2002) 5. Bhalotia, G., Nakhe, C., Hulgeri, A., Chakrabarti, S., Sudarshan, S.: Keyword Searching and Browsing in databases using BANKS. In: 18th IEEE International Conference on Data Engineering, pp. 431–440. IEEE Computer Society Press, San Jose, CA (2002) 6. Ceri, S., Fraternali, P., Bongio, A., Brambilla, M., Comai, S., Matera, M.: Designing Data-Intensive Web Applications. Morgan Kaufmann, (2002) 7. Koch, N.: Transformation techniques in the model-driven development process of UWE. In: Workshop proceedings of the 6th IEEE International Conference on on Web Engineering, pp. 431–440. ACM, New York, USA (2006) 8. Frasincar, F., Jan.Houben, G., Vdovjak, R.: An RMM-based methodology for hy- permedia presentation design. In: 5th East European Conference on Advances in Databases and Information Systems, pp. 323–337. Springer, London, UK (2001) 9. Gomez, J., Cachero, C., Pastor, O., Spain, V.: Extending a Conceptual Modelling Approach to Web Application Design. In: In 12th International Conference on Ad- vanced Information Systems, pp. 79–93. Springer, Stockholm, Sweden (2000) 10. Vanderdonckt, J., Bouillon, L., Souchon, N.: Flexible Reverse Engineering of Web Pages with VAQUISTA. In: Working Conference on Reverse Engineering, pp. 241- 248. Springer, Stuttgart, Germany (2001) 11. Di Lucca, G., Di Penta, M., Antoniol, G., Casazza, G.: An Approach for Reverse Engineering of Web-Based Application. In: Working Conference on Reverse Engi- neering, pp. 231-240. Springer-Verlag, Stuttgart, Germany (2001) 12. Draheim, D., Lutteroth, C., Weber, G.: A Source Code Independent Reverse En- gineering Tool for Dynamic Web Sites. In: European Conference on Software Main- tenance and Reengineering, pp. 168-177. Springer, Manchester, UK (2005)