Recovering software layers from object oriented systems : a formalization as an optimization problem

Software architecture recovery is a bottom-up process that aims at building high-level views that support the understanding of existing software applications. Many existing software systems lack documentation or have often drifted from their initial design due to multiple maintenance operations. To support their evolution and maintenance, it is therefore mandatory to reconstruct and document their architectures. Our focus in this thesis is the recovery of layered architectures as the layered style is a widely used pattern to structure large software systems. In this context, some approaches were proposed to reconstruct the architecture. However, most of these approaches propose algorithms that partition elements of the analyzed system into layers using some heuristics (e.g., heuristics to resolve cyclic dependencies). This may result in partitions with very few layers or too many layers which may be too permissive with violations of the style’s constraints. In this thesis, we propose an approach that aims at recovering the layered architecture of object oriented systems while relying on: 1) a set of constraints that convey the essence of the layered architectures and 2) the input which reveals how strictly the layering rules were enforced when designing a given system. To do so, we studied the layered style and extracted a set of rules that a layered system must comply with during its lifecycle. We used these rules to derive a set of layers’ dependency attributes and factors from structural and lexical information. These attributes and factors correspond to possible types of assignments of dependent packages to the layers of a given system. This enabled us to formulate the layering recovery problem as an optimization problem that is a specific case of the quadratic assignment problem (QAP). We solved this problem using search-based metaheuristics (i.e. hill climbing and tabu search). We evaluated the proposed approach through experimentations performed on five open source software systems. The main contributions of this thesis are: 1) the definition of a set of constraints and layers’ dependency attributes that reflect a minimal set of the layering rules and that can guide the layering recovery process; 2) the translation of the layering recovery problem into an optimization problem; 3) a tool that implements this approach and that is available for the software engineering community in the form of an Eclipse plugin; and 4) a layering recovery approach that is language and platform independent since it relies on the OMG’s KDM (Knowledge Discovery Metamodel) standard for representing software systems