Shinji Kawaguchi †, Pankaj K. Garg †† Makoto Matsushita † and Katsuro Inoue † † Graduate School of Information Science and Technology, Osaka University 1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan {s-kawagt, matusita, inoue}@ist.osaka-u.ac.jp †† Zee Source 1684 Nightingale Avenue Sunnyvale, California, 94807, USA garg@zeesource.net
Abstract
The number of software systems is increasing at a rapid rate.  For example, SourceForge currently has about sixty thousand software systems registered, twenty-two thousand of which were added in the past twelve months. It is impor- tant for software evolution to search and use existing sim- ilar software systems from software archive.  An evolution history of an existing similar software system is useful.  We may even evolve a software system based on an existing one instead of creating it from scratch. In this paper, we propose automatic software categorization algorithm to help finding similar software systems in software archive.  At present, we leave open the issue about the nature of the categoriza- tion, and explore several known approaches including code clones-based similarity metric, decision trees, and latent se- mantic analysis. The results from applying each of the ap- proaches gives us some insights into the problem space, and sets some directions for further work. 1
Introduction
Recently, software archiving services are widely used. SourceForge [13] is one of a software archiving service. It provides network storages for open source software prod- ucts.  Over sixty thousand software projects use Source- Forge, and twenty-two thousand of which begin to use in the last twelve months. For such huge software archives, categorizing their con- tents for browsing and searching is essential for the evo- lution of the software archive.  Automatic categorization would be helpful in several ways for software archives that are evolving rapidly as stated above: ● Several similar software can be grouped together in a category for ease of browsing.  For example, Source- Forge [13] categorizes software according to their function (editors, databases, etc.), and also has the no- tion of software foundries for related software. ● Developers working on a software system may be in- formed about related software.  Finding related soft- ware systems has the following advantage. 1. Developers can learn from experience with such software systems.  From related software sys- tems, they can get strategies or hints for software evolution. They can even evolve a software sys- tems based on related software systems, not cre- ate it from scratch. 2. They can avoid duplicate work and promote more reuse. This becomes specially useful in situations like Corporate Source [5], where global groups in companies may not be aware of the relationship among their work [6]. In the past, such relationships have been determined man- ually.  Manual categorization generally requires deep un- derstanding of not only the target software system, but also other software systems and their classification policy. With the increase in the number of software systems, e.g., SourceForge now has over fifty-five thousand software sys- tems registered and continues to evolve, such manual iden- tification is not enough. Automatic categorization of software systems is a novel and intriguing challenge on software archive evolution. Past work in software engineering (e.g., see [2, 12]), has focused on determining intra-component relations of one 1
given software system. We, however, propose finding inter- component relations of many software systems. We have experimented with following three approaches for automatic categorization of evolvable software archive: 1. We use a similarity measure based on code-clone de- tection [7, 14].  Replicated code portions existing at different location in the source code are called code clones. The ratio of the total lines of code clones to the total lines of software is defined as the similarity of two software systems. This similarity measure has previously been useful in characterizing the evolution history of software sys- tems, i.e., tracing ancestors and descendants of a soft- ware versions. In this paper, we investigate the use of this measure for software categorization. 2. Generating decision trees from example classes is a common approach in supervised machine learning. In this approach, an example category set of software and their features is fed to a learning algorithm. From this example category set, the rule learner determines rules (or a decision tree) that helps categorize any future software system. 3. Latent Semantic Analysis(LSA) is a method for ex- tracting and representing the contextual-usage mean- ing of words by statistical computations applied to a large corpus of text [8].  LSA has found a variety of uses ranging from understanding human cognition [8] to data mining [3].  Also, it is used for clustering components in a software system [9] and recovering document-to-source links [10]. We apply LSA for de- termining categories of software systems. The rest of the paper is structured as follows: in sec- tions 2, 3, and 4, we describe the application and use of SMAT, C4.5, and LSA, respectively.  We conclude with a discussion of current and future work in section 5.
2
Similarity Measure by SMAT
SMAT is a tool to measure a similarity between two large software systems based on correspondence of each source- code line of the systems [14]. SMAT calculates a similarity of software from code clones.  To get the correspondence efficiently, a fast code-clone detection tool CCFinder [7] is employed to detect file pairs sharing common clones.  The detail line-by-line correspondence is then computed using file difference detection tool diff [4]. Similarity is defined as the ratio between LOC (lines of code) in the correspondence and the total LOC of two soft- ware systems. Thus, by counting the number of lines in the correspondence, the similarity of two software systems can be obtained. This similarity measure characterizes evolution history of software systems.  For example, by applying it to BSD unix operating systems, we automatically classified ver- sions of released operating systems into FreeBSD, NetBSD, and OpenBSD [14]. We applied this measure to classify several software sys- tems in SourceForge. Table 1 shows the resulting similarity between each pairs of systems. As seen from the table, all the similarity values between different category software systems are zero. This indicates that SMAT can identify whether given two software systems are in different categories or not. However, the similarity values are generally low or zero even for software systems that belong to the same manu- ally determined category.  This shows that although sys- tems in the same category provide similar features, they do not share much code. This obviously raises the question of why these developers have chosen to provide different im- plementations for similar features? 3
Decision Trees
Decision trees are a machine learning approach for au- tomatic classification of a data set. The decisions trees are based on certain features of the data points.  Initially, an example set of data points with known classification and features is fed to a rule-learner. The rule-learner uses the example set to develop a set of rules.  These rules operate on the features of the data points to classify any future data. C4.5 [11] is a commonly available tool that can be used for classifying a set of data points.  The schema of input consists of some Attribute Name, Range of Attribute and List of Categories.  An example data contains values for each attribute and its classification. Here is a simple example. Table 2 shows sample input data. “AGE”, “COMPETITION” and “TYPE” are attributes of input data.  “PROFIT” is a category of each input data. The data in first row means if "AGE" is old, "COMPETI- TION" is yes and "TYPE" is software, he is categorized down “PROFIT”. C4.5 generate a decision tree satisfying such input data.  Figure 1 shows a decision tree that C4.5 generated for above example.
This decision tree includes 2 questions. First, if a value of an “Age” attribute is new, this data is classified “Up”. If down, it is classified "Down".  If an "Age" attribute is mid, get through to next question.  Second question is about a "Competition" attribute.  The classification result depends on a value of a "Competition" attribute.  This decision tree is suitable for all sample data.  C4.5 can extract implicit pattern from example data set. We used C4.5 on 41 software systems from SourceForge. Table 3 is the detailed list of 41 software systems. They are classified into 6 groups (board game, compiler, database, editor, video conversion, and xterm) at SourceForge. This classification has been made by the developers decision. For attributes, we used 3-gram representation of filenames used in the software source code.  This is similar in principle to the approach used by Anquetil and Lethbridge [1] for their approach for clustering of software components. Instead of deriving concepts, however, we directly used 3-grams. The 41 software resulted in 6977 attributes (3-gram representa- tion of filenames). A range of each attributes is "t" or "f". If software systems has a file contains its attributes 3-gram, the value equals "t", otherwise it equals "f". The resulting decision tree is shown in Figure 2. As shown in Figure 2, the results of this classification are encouraging.  The training data set recorded an error of less than 5%.  The only drawback of this approach is that it requires up-front a set of example categories how- ever, we would like to discover categories or classifications that we don't even know exist. The latent semantic analy- sis approach presented in the next section provides such a capability.
Latent Semantic Analysis (LSA)
4
Latent Semantic Analysis, LSA, is a practical method for the characterization of word meaning. LSA produces mea-

Table 3. A detailed list of 41 software systems
sures of word-word, and passage-passage relations which are well correlated with semantic similarity [8]. The method creates a vector description of documents. This represen- tation is used for comparing and indexing documents, and various similarity measures can be defined using it. LSA is based on a single value decomposition (SVD) of a matrix derived from a word set of target documents. SVD is a form of factor analysis and acts as a method for reducing the dimensionality of the matrices. Consider a simple documents in Figure 3. In LSA, these documents are represented by a matrix shown in Table 4. Each column means a document and each row represents a word which may appear in the documents.  Cell entries show the occurrence of the word in the document. c1: Human machine interface for ABC computer applications c2: A survey of user opinion of computer system response time c3: Relation of user perceived response time to error measurement m1: The generation of random, binary, ordered trees m2:  Graph minors IV: Widths of trees and well-quasi-ordering m3:   Graph minors: A survey
Figure 3. An Example Input Document of LSA

c2 1 1 1 1 0
1 0 0
LSA Each column vector of this matrix indicates the char- acteristics of the document through the word occurrences. This column vector can be used to determine the similarity of two documents. A simple similarity definition used here is cosine of two vectors [8]. In LSA, SVD has been applied to the matrix in Table 4. The result we obtain is the two-dimensionally reconstructed matrix shown in Table 5.
Table 5. Resulting Two Dimensionally Recon- structed Matrix Why does LSA apply such translation? This is because A simple term-by-document matrix doesn't capture rela- tionship of terms.  Two documents show high similarity only when the documents have some same words, however, there are many synonyms. Thus similar documents don't always share completely same words. They may contain many syn- onyms. Using SVD, LSA can retrieve such undirectional rela- tionship among documents.  We calculate cosine of each column vectors in Table 4 and Table 5. Table 6 is result of Table 4 and Table 7 is result of Table 5. In Table 7, undirec- tional related documents c1 and c3 have shows high simi- larity value.
4.1
Applying LSA to Classification of
Software Systems
We applied LSA to classification of software systems. One key factor of this application is selection of words. We might be able to get the input word list for LSA from the documentation associated with target software systems.
Also, we could obtain meaningful word lists from com- ments embedded into the source code. The former approach would work if the documentation of each software systems are rich enough.  Many software systems, however, do not have sufficient documentation, es- pecially when a project is in its early phases. Also the gran- ularity of description would be unstable over documents. Some documents focus only on usage of the systems, while others only describe the details of implementation. Using words from program comments is more closely re- lated to the implementation of the target software systems, and the granularity would be more stable. In many soft- ware systems, however, comments in the source code con- tains a lot of sentences for their license policy and system evolution, which are very important for the developers of software, but which may not be relevant for classification purpose and would have to be removed. Identifying the li- cense policy and evolution history automatically would not be so easy. For the work reported in this paper, we deleted all com- ments and used only identifiers (variables, constants, and function names) found in the source code as words. A soft- ware system is composed of many source code files, and each source code file is made up of a sequence of tokens in a particular programming language. The tokens can be cat- egorized into two sets: keywords specified by the program- ming language, and identifiers given by the developers. The keywords generally are common over many software sys- tems, hence we use identifiers for the input of LSA. The following process overviews the process of classifi- cation using LSA. 1. Collect source code files of software systems. 2. Remove comments and extract tokens. Keywords in the programming language are discarded and only identifiers are obtained. 3. Count the occurrence of each identifier and create the word matrix for the input of LSA. 4. Remove meaningless words (identifiers) from the ma- trix.  Unique words appearing only in a software sys- tem are removed.  Also, common words appearing in more than half of those systems are removed.  These removed words would not contribute the classification. 5.  Perform LSA. 6. Compute cosine of each pair of the column vectors of the resulting matrix of LSA, and obtain the similarity value of two software systems.
Experiments
4.2
We applied LSA method on the softwares in Table 3. The total number of different kinds of identifiers extracted from these 41 software systems are 164,102, and meaning- less words mentioned above are removed from them.  The remaining are 22,048 different identifiers. So a 41 x 22,048 matrix is the input of LSA. The resulting similarity between the software systems is presented in Figure 4. As you can see from Figure 4, the software systems in the manual classification groups of editor, video conver- sion, and xterm showed very high similarity each other. On the other hand, systems in board game, compiler, and database did not show high similarity.  This is because in board game, compiler, or database, there are little common concept which characterize overall systems. Editor, video conversion, and xterm contain a lot of characterizing sys- tem call names and variable names among systems. There are two systems in board game which show high similarity with editors.  This is because it share the same GUI framework.
5
Conclusion
We have reported some preliminary work on automatic categorization of a evolvable software archive.  Such cat- egorization can be useful for reification of a multitude of relationships among software systems.  To understand the nature of the problem and its parameters, we have reported on several experiments to applied well-known approaches to classification.  Wherever possible, we have build-upon the results of previous work in the area of determining rela- tionships among components of a software system. We ap- plied a code-clone based similarity metric, a decision tree based approach, and a latent semantic analysis approach. In each of the cases, we have limited success with the pa- rameters that we chose. Hence, further work is required to understand the appropriate automated techniques that can be applied for this purpose.  We are actively pursuing this research direction.