The size and complexity of software systems is rapidly increasing. Meanwhile, the ability to understand and maintain such systems is decreasing almost as fast. Model Driven Engineering (MDE) promotes the notion of modeling to cope with software complexity; in this paper we report on our research that utilizes ontological modeling for understanding complex software systems. We focus the discussion on recovering design pattern information from source code. We thus argue that an e ective recovery approach needs to utilize semantic reasoning to properly match an ontological representation of both: conceptual source code knowledge and design pattern descriptions. Since design patterns can take di erent forms when implemented in code, we argue that hardcoding their descriptions limits the exibility and usability of a detection mechanism.
of studying software to mentally conceptualizing its behavior and inner working structure. Unfortunately, understanding voluminous and complex software is widely regarded as the most time consuming and resource intensive activity during both reverse and forward engineering practices. In order to cope with software complexity and consequently enable better understanding of software,
pline. MDE emphasizes the systematic use of models and modeling principles throughout the software development lifecycle. In fact, software design and design best practices (i.e., design patterns) are of particular relevance to MDE due to the heavy reliance on modeling techniques and principles.
oriented design problems. The classic book [
Central to all reverse engineering activities is the accurate identi cation of
interrelationships among the components of a subject system as well as a true
representation of the system at a higher level of abstraction [
In our further exploration of this hypothesis, we take into account modeling principles and techniques from Model Driven Engineering. MDE promises full support for reverse engineering activities through modeling and model transformations at di erent levels of abstractions. Due to the formal and built-in reasoning foundations of ontologies, our methodology is solely reliant on ontologybased modeling. Therefore, we provide an OWL1 ontology model that includes a software representation ontology; this ontology is automatically populated through text-to-model transformation with ontological instances representing various program elements of a subject system. Furthermore, each design pattern's structure including its participants' behaviors and collaborations are represented by a separate OWL ontology; this ontology also encodes the rules needed to detect this particular pattern.
The rest of the paper is organized as follows: In Section 2, we describe our approach for structuring and populating the knowledge base. We discuss the details of design pattern detection in Section 3. Implementation and evaluation case studies are discussed in Section 4. Finally, a discussion of the current stateof-the-art followed by future work directions are discussed in Section 5 and 6, respectively. 2
ontologies are being used as the knowledge representation component of the
eas. In our work, we utilize the Web Ontology Language (OWL), the Resource
1 http://www.w3.org/TR/owl-guide/ 2 http://www.w3.org/TR/rdf-primer 3 http://www.w3.org/Submission/SWRL 4 http://www.w3.org/TR/rdf-sparql-query allows for inferring additional knowledge and computing the classi cation hierarchy (subsumption reasoning). RDF is used as a exible data representation model. RDF is suitable for describing resources and provides a data model for representing machine-processable semantics of data. SWRL is used for writing rules that can be combined with OWL knowledge bases for reasoning and computing entailments. Finally, SPARQL is an RDF query language and protocol for ontological querying of RDF graphs.
methodology; in particular, we show how OWL-DL and RDF are used to obtain a precise formal representation of source code knowledge and design patterns.
tation of design patterns to handle features that cannot be expressed using OWL alone. Collectively, these representations form the base for semantic reasoning and inference of additional facts that can be retrieved using SPARQL semantic queries. 2.1
(referred to afterwards as SCRO). This ontology is created to provide an explicit representation of the conceptual knowledge structure found in source code.
stand the relationships and dependencies among source code artifacts.
SCRO's knowledge is represented using the OWL-DL ontology language and
veri ed using the Pellet OWL-DL reasoner [
de nes a group of individuals (instances) sharing some properties. Disjoint subclasses are also modeled to de ne di erent sets of individuals. For example, all individuals that are members of class InstanceMethod are necessarily members of class Method but none of them can simultaneously be a member of another subclass of Method. Currently SCRO de nes 56 OWL classes and subclasses.
ned within SCRO to represent relationships among concepts by linking individuals from di erent OWL classes. For example, hasOutputType is a functional property de ned for the return type of a method and hasSuperType is a transitive object property de ned with two transitive sub-properties for inheritance and interface implementation. Inverse properties are also used to de ne the inverse relation. For example, isLocalVariableOf is the inverse property of hasLocalVariable. This is in particular useful in many situations such as traversing the resulted RDF graph in both directions and making the ontology useful for applications that do not depend on a reasoner system. Currently,
2.2
participating classes, their instances, roles, and collaborations is indeed essential.
terns. An ontology is created for each design pattern describing its essential participants and their properties, collaborations, restrictions, and the corresponding
Design-Pattern Singleton tology reuse, thus allowing SCRO to be used with various maintenance related activities and certainly with reasoners that do not support SWRL rules. Having the ontology structure created, the next natural step is to populate the knowledge base with ontological instances of various concepts in the ontology. This process is described next.
tion with the ontology to create instances of ontological concepts. These instances are the building blocks of the knowledge base that can be used for browsing and querying. When dealing with large source code repositories, a large number of instances is usually created, this is why automatic text-to-model transformation and knowledge population is essential.
Inspired by the Java RDFizer idea from the Simile5 project, we have built a subsystem that automatically extracts knowledge from Java binaries. The original RDFizer was able to distinguish only class types, super types, and basic use relations represented in a class le. Currently, our subsystem performs a comprehensive parsing of the class le format speci ed by the Java Virtual Machine. It captures every ontology concept that represents a source code element and e ectively generates instances of all ontological properties de ned in our ontologies for those program elements. Our knowledge generator subsystem distinguishes itself as not being relied on the existence of source code to extract knowledge.
software system in which the source code is unavailable.
triples; a separate RDF ontology in Notation36 syntax is generated for each application framework parsed, this amounts to instantiating an OWL knowledge base for that framework. This arrangement provides a clean separation of explicit
5 http://simile.mit.edu 6 http://www.w3.org/DesignIssues/Notation3 can be naturally linked to the OWL design pattern ontologies via OWL reuse mechanisms. A sample output of our knowledge extractor subsystem for the
3
Due to their abstract nature and the varying responsibilities and interactions of their participants, design patterns can generally be implemented in di erent ways and using di erent techniques or language-speci c constructs. Examples of such implementation variations are plenty. Consider object composition for example, some systems do not use a built-in collections framework component for maintaining an aggregate collection of objects. Instead, they use a user-de ned data structure. Other systems favor some delegation techniques over the others when implementing design patterns such as Visitor, State, and Strategy. We thus believe that pattern detection tools should be exible and easily extensible to improve usability and e ectiveness, that is, the roles and interactions of participants should not be hard-coded. In fact, users of the detection tool often need to change those hard-coded role restrictions but nd it extremely di cult because it requires code modi cation and rebuilding the entire tool.
In our approach, we aim at providing exibility and transparency such that
design patterns are speci ed externally using ontology formalisms and
participant's responsibilities are depicted using ontology rules that can be easily
understood and modi ed. We thus use the expressivity of OWL-DL and SWRL
rules to formally represent each design pattern using a set of intent-preserving
conditions. When these conditions are collectively met, an instance of the design
pattern is detected. This approach relies solely on the de nitions found in our
ontologies and on an OWL-DL reasoner that is capable of computing inferences
from the set of facts and SWRL rules de ned in the ontologies. To test the
validity of our approach, we authored SWRL rules for ve well-known design
patterns, namely, Visitor, Observer, Composite, Template-Method, and
Singleton. In the next subsections, we illustrate our detection mechanism for Visitor
and Observer. Since SWRL rules are part of the OWL ontology representing a
particular design pattern, the reader can examine the rules for the other three
patterns by downloading the corresponding ontology [
7 http://www.jhotdraw.org structure intact by de ning new structures of visitors representing the new behaviors of interest. This pattern de nes two separate class hierarchies: Host and Visitor. The following are three sample conditions for detecting this pattern: 1. At the root of the Visitor hierarchy is a Visitor interface common to all concrete visitors; this interface declares the invariant abstract behaviors (visit methods) that should be implemented by each ConcreteVisitor, since each visit method is designed for a ConcreteHost, the concrete host must be present as an argument (input type) in the corresponding visit method. 2. A ConcreteVisitor is a concrete class type that implements the Visitor interface and overrides each visit method to implement visitor-speci c behavior for the corresponding ConcreteHost.
as an argument. This method implements the double dispatching technique by calling the matching visit method and passing the host object into the visitor.
Intuitively, we should take advantage of OWL-DL expressivity to formalize
the above restrictions. However, these restrictions require more expressive power
than what Description Logic provides. OWL can only handle descriptions of
in nite number of unstructured objects connected in a tree-like manner [
reasoner will carry out the actions speci ed in the consequent only if all the atoms in the antecedent are known to be true.
Listing 1 shows a sample SWRL rule that depicts the above conditions for
the visitor design pattern. Please refer to SCRO and the visitor ontology found
online [
=) visitor : Visitor (? visitor ) ^ visitor : hasConcreteVisitor (? visitor , ? concrete - visitor ) ^ visitor : hasConcreteHost (? visitor , ? concrete - host ) ^ visitor : hasVisitMethod (? concrete - visitor , ?c - visit ) ^ visitor : hasAcceptMethod (? concrete - host , ? accept )
For the sake of argument, one might want to retrieve only pattern instances that declare a super type for all concrete hosts in the Host hierarchy. This can be accomplished by modifying the third condition and introducing a fourth condition as shown below. The result is a new rule depicted in Listing 2. 3. A ConcreteHost is a subtype of Host. It de nes the accept instance method that overrides the hook method found in Host. This method implements double dispatching by calling the matching visit method and passes the host in to the visitor. 4. At the root of the Host hierarchy is an interface or abstract class type. It represents the super type of all concrete hosts. It declares the abstract hook method; this method takes Visitor as an argument. scro : InterfaceType (? visitor ) ^ scro : hasAbstractMethod (? visitor , ? visit ) ^ scro : hasInputType (? visit , ? concrete - host ) ^ scro : hasSuperType (? concrete - visitor , ? visitor ) ^ scro : hasInstanceMethod (? concrete - visitor , ?c - visit ) ^ scro : methodOverrides (?c - visit , ? visit ) ^ scro : hasSuperType (? concrete - host , ? host ) ^ scro : hasAbstractMethod (? host , ? hook ) ^ scro : hasInputType (? hook , ? visitor ) ^ scro : hasInstanceMethod (? concrete - host , ? accept ) ^ scro : methodOverrides (? accept , ? hook ) ^ scro : invokesMethod (? accept , ? visit )
=) visitor : Visitor (? visitor ) ^ visitor : hasHost (? visitor , ? host ) ....................
such that when the subject object changes its state, it sends a noti cation message to all its listeners to be updated accordingly. Unlike the Composite pattern, Observer is implemented in two separate hierarchies of participants. An interface for all listeners sits at the root of the listener's hierarchy; it identi es a common behavior for all listeners interested in observing a particular subject such that each concrete listener maintains a reference to that particular subject. On the other hand, the subject knows its listeners, it provides means to establishing the relationship with them, and it is responsible for communicating the behavior change to all those registered listeners.
Listing 3 shows sample rule representations of this pattern. The rst rule identi es candidates for potential listeners, their concrete listeners and the corresponding update methods. scro : hasSuperType (?c- listener , ? listener ) ^ scro : hasMethod (? listener , ? update ) ^ scro : methodOverriddenBy (? update , ?c- update ) ^ scro : isMethodOf (?c- update , ?c- listener )
=) observer : hasCListenerCandidate (? listener , ?c- listener ) ^ observer : hasCUpdate (?c- listener , ?c- update ) ^ observer : hasUpdate (? listener , ? update ) ------------------------------------------------------------scro : hasField (?c- subject , ? container ) ^ scro : hasStructuredDataType (? container , ? containerDT ) ^ scro : hasMethod (? containerDT , ? insert ) ^ scro : methodInvokedBy (? insert , ?add - listener ) ^ scro : isMethodOf (? add - listener , ?c- subject )
=) observer : hasAddListener (?c- subject , ?add - listener ) ------------------------------------------------------------observer : hasCListenerCandidate (? listener , ?c- listener ) ^ observer : hasUpdate (? listener , ? update ) ^ observer : hasAddListener (?c- subject , ?add - listener ) ^ scro : hasInputType (? add - listener , ? listener ) ^ scro : hasPart (?c- listener , ?c- subject ) ^ scro : hasMethod (?c- subject , ? notify ) ^ scro : invokesMethod (? notify , ? update )
=) observer : hasConcreteListener (? listener , ?c- listener ) ^ observer : listensTo (?c- listener , ?c- subject ) ^ observer : Observer (? notify )
soner can infer all direct or indirect super types of a given class. The update method speci ed in the listener interface should be implemented by all concrete listeners. Recall that the object property methodOverrides works for both classes and interfaces.
jects and the method used for establishing the relationship between this subject and its listeners. The subject class maintains a collection of its listeners, typically stored in a eld that has a structured data type. In SCRO, StructuredDataType represent arrays or collections of elements; it is a sub-class of ComplexDataType which also includes UnstructuredDataType such as user-de ned data structures.
The third rule builds on the other two rules and e ectively ensures the conditions needed for detecting this pattern. The hasPart property ensures that a concrete listener must maintain a reference to the observable; the hasInputType property ensures that the candidate add-listener method accepts only listener objects, and nally the noti cation behavior is speci ed using method invocation. 4
services over the ontological representation of source code elements. This tool currently accepts the Java byte code and the ontologies (Sections 2.1 and 2.2) as input; the knowledge generator module parses the byte code and generates the
[
4.1
including JUnit8, JHotDraw, and Java AWT. The chosen frameworks vary in size, they represent di erent domains, and most importantly, they were built with design patterns in mind; this makes them a good t for evaluating our approach. Instance detection is shown in Table 1.
8 http://www.junit.org class, and a Template-method instance represents the template method itself. In our manual evaluation of the obtained results, we adopted precision measures { The number of correctly inferred pattern instances (True Positives) over the total number of inferred instances. In order to accept an instance as truly positive, this instance needs to be explicitly stated in the framework's documentation or there have to be strong indications found by inspecting source code and available comments. In all the tests performed, none of the inferred pattern instances violates any of the structural or behavioral restrictions put forward for that pattern in the axioms and rules; this means that the knowledge base accurately represents the source code and the reasoner acted accordingly. However, as noted in Table 1, there are a few cases in which precision su ers since the identi ed instances were considered by our standards as false positives { falsely inferred instances that were not designed as such. In all these cases, neither documentation nor source code comments strongly certi ed those instances as true positives.
Recall statistics, however, are usually harder to come up with since they require the identi cation of all false negatives { occurrences that were intended as actual pattern instances but were not inferred by the reasoner. Most framework documentations do not explicitly report on all actual number of pattern instances, thus manual identi cation through source code inspection is subject to one's interpretations of what constitutes an actual instance. Nevertheless, we found some evidence of false negatives. Some of the instances were missed due to our parser's inability to capture the complete picture of the running code; others are due to the restrictions speci ed in OWL axioms and SWRL rules. For example, the current rule for Template Method requires the primitive operation that is called by the template method to be declared protected, however, this is not a requirement; we found evidence of that on both JHotDraw and JUnit.
soner to detect the missed instances. Generally speaking, relaxation reduces false negatives; it does, however, increase the risk of false positives.
It was evident in some cases that better capturing of behavior speci ed in method bodies through more e ective parsing is indeed helpful, an appropriate parsing provides more exibility when relaxing the requirements and certainly improves both precision and recall. Nevertheless, our approach to pattern detection distinguishes itself as being exible and usable such that users can relax or restrict pattern descriptions as they wish. In Singleton, for example, accounting for another form of lazy instantiation or perhaps disputing the way the static reference is being declared, can be readily obtained by slightly modifying the rule.
A more comprehensive case study is currently being conducted. In this study we are investigating the e ect of rule relaxation, applying our approach to other frameworks, comparing our results to other non-model driven approaches, and nally attempting to come up with recall statistics for selective well documented frameworks. Preliminary results are extremely encouraging and show an improvement However, a systematic study can uncover the overlap between different approaches and most fundamentally show the value of ontology-based modeling in software engineering.
Table 2 shows statistics related to the software frameworks used in our study as well as running time analysis.
JUnit 3.7 JHotDraw 6.0 Java AWT 1.6 Statistics
No. of Classes
No. of OWL Individuals Processing Time Parsing + Processing Reasoner Time
Visitor Observer Composite Template Method Singleton 99 1411 3 1.6 2.9 2.5 1.6 1.7 377 6254 6.5 18 33.3 29.1 14.7 14 549 11853 13 49.7 95.2 76 46 48
gies, executing the queries, etc. is in most cases minimal when compared to the time required by the reasoner to classify the ontologies and execute SWRL rules. Furthermore, since rules allow for reasoning with all available individuals, rule execution time is susceptible to increase as the number of OWL individuals in the ABox (assertions that represent ground facts for individual descriptions) as well as the complexity of the rules increase. In fact, Pellet, our experimentation reasoner, does not claim optimal performance. However, it does have an integrated rule engine that provides a complete and sound support for SWRL; that de nitely adds to the cost of memory consumption and computational speed.
On surveying the state of the art in design pattern recovery, we found numerous
non-semantic based approaches. Most existing approaches di er in the
detection technique utilized as well as the mechanism used for obtaining source code
knowledge and formalizing pattern descriptions. PINOT [
it is our belief, however, that using a semantic-based formalism ensures consistent and accurate functional representation of design patterns, their participants, and the system under study. Furthermore, semantic representation allow for computing inferences of knowledge that was not explicitly stated, yielding an inference-based detection of design pattern instances.
[13] in which declarative meta-programming techniques were utilized. In particular, design patterns are described using variations of Prolog predicates and limited information about program elements and their roles are represented as
notion of utilizing OWL ontologies to structure the source code knowledge. However, these approaches provide template ontology descriptions or at best rudimentary ontologies that must be extended to become more expressive. The full potential of semantic-based modeling was yet to be explored. The primary focus of the work presented in [14] is basically to facilitate exchanging and sharing knowledge about patterns, anti-patterns, and refactoring. Our aim, however, is to provide a true semantic-based approach for design pattern detection and provide an aid for understanding, reasoning, and conceptualizing source code. 6
In this paper, we proposed a semantic-based approach for software understanding. In particular, we illustrated our approach for recovering design patterns from source code. The proposed approach is fully automatic and distinguishes itself as being extensible and extremely usable. Moreover, the proposed approach is purely semantic-based that describes knowledge using a set of ontologies. SCRO, our main ontology, provides a consistent and complete functional description of program elements and allows for semantic inference of knowledge that was not explicitly stated.
The tool described in Section 4 is currently a work in progress. Our ultimate goal is to provide a more comprehensive program comprehension environment for conceptualizing, understanding, and recovering software knowledge to aid both reverse and forward engineering activities. Notably the generated knowledge by the bytecode parser may not provide the full picture of the running code; in particular, method bodies need to be e ectively parsed to capture more detailed behavioral aspects of programs. We are currently investigating the use of other means to augment the current knowledge, the more knowledge captured, the more exibility is given to the user in authoring the rules for detecting design patterns. We also investigating our approach on other design patterns found in literature and conducting more case studies as described in Section 4.1. 12. Kramer, C., Prechelt, L.: Design Recovery by Automated Search for Structural Design Patterns in Object Oriented Software. In: 21st IEEE/ACM International Conference on Automated Software Engineering, pp. 123{132. (2006) 13. Wuyts, R.: Declarative reasoning about the structure of object-oriented systems.
In: Proceedings of TOOLS USA '98, pp. 112{124. (1998) 14. Dietrich, J., Elgar, C.: A Formal Description of Design Patterns Using OWL. In: Proceedings of the 2005 Australian Software Engineering Conference, pp. 243{250. (2005) 15. Kirasic, D., Basch, D.: Ontology-Based Design Pattern Recognition. In: 12th International Conference on Knowledge-Based and Intelligent Information and Engineering Systems (KES'08), pp. 384-393. (2008)