As developers are increasingly creating more sophisticated applications, software systems are growing in both their complexity and size. When source code is easy to understand, the system can be more maintainable, which leads to reduced costs. Better structured code can also lead to new requirements being introduced more efficiently with fewer issues. However, the maintenance and evolution of systems can be frustrating; it is difficult for developers to keep a fixed understanding of the system’s structure as the structure can change during maintenance. Software module clustering is the process of automatically partitioning the structure of the system using low-level dependencies in the source code, to improve the system’s structure. There have been a large number of studies using the Search Based Software Engineering approach to solve the software module clustering problem. A software clustering tool, Munch, was developed and employed in this study to modularise a unique dataset of sequential source code software versions. The tool is based on Search Based Software Engineering techniques. The tool constitutes of a number of components that includes the clustering algorithm, and a number of different fitness functions and metrics that are used for measuring and assessing the quality of the clustering decompositions. The tool will provide a framework for evaluating a number of clustering techniques and strategies. The dataset used in this study is provided by Quantel Limited, it is from processed source code of a product line architecture library that has delivered numerous products. The dataset analysed is the persistence engine used by all products, comprising of over 0.5 million lines of C++. It consists of 503 software versions. This study looks to investigate whether search-based software clustering approaches can help stakeholders to understand how inter-class dependencies of the software system change over time. It performs efficient modularisation on a time-series of source code relationships, taking advantage of the fact that the nearer the source code in time the more similar the modularisation is expected to be. This study introduces a seeding concept and highlights how it can be used to significantly reduce the runtime of the modularisation. The dataset is not treated as separate modularisation problems, but instead the result of the previous modularisation of the graph is used to give the next graph a head start. Code structure and sequence is used to obtain more effective modularisation and reduce the runtime of the process. To evaluate the efficiency of the modularisation numerous experiments were conducted on the dataset. The results of the experiments present strong evidence to support the seeding strategy. To reduce the runtime further, statistical techniques for controlling the number of iterations of the modularisation, based on the similarities between time adjacent graphs, is introduced. The convergence of the heuristic search technique is examined and a number of stopping criterions are estimated and evaluated. Extensive experiments were conducted on the time-series dataset and evidence are presented to support the proposed techniques. In addition, this thesis investigated and evaluated the starting clustering arrangement of Munch’s clustering algorithm, and introduced and experimented with a number of starting clustering arrangements that includes a uniformly random clustering arrangement strategy. Moreover, this study investigates whether the dataset used for the modularisation resembles a random graph by computing the probabilities of observing certain connectivity. This thesis demonstrates how modularisation is not possible with data that resembles random graphs, and demonstrates that the dataset being used does not resemble a random graph except for small sections where there were large maintenance activities. Furthermore, it explores and shows how the random graph metric can be used as a tool to indicate areas of interest in the dataset, without the need to run the modularisation. Last but not least, there is a huge amount of software code that has and will be developed, however very little has been learnt from how the code evolves over time. The intention of this study is also to help developers and stakeholders to model the internal software and to aid in modelling development trends and biases, and to try and predict the occurrence of large changes and potential refactorings. Thus, industrial feedback of the research was obtained. This thesis presents work on the detection of refactoring activities, and discusses the possible applications of the findings of this research in industrial settings.

abstract: The construction of many families of combinatorial objects remains a challenging problem. A t-restriction is an array where a predicate is satisfied for every t columns; an example is a perfect hash family (PHF). The composition of a PHF and any t-restriction satisfying predicate P yields another t-restriction also satisfying P with more columns than the original t-restriction had. This thesis concerns three approaches in determining the smallest size of PHFs. Firstly, hash families in which the associated property is satisfied at least some number lambda times are considered, called higher-index, which guarantees redundancy when constructing t-restrictions. Some direct and optimal constructions of hash families of higher index are given. A new recursive construction is established that generalizes previous results and generates higher-index PHFs with more columns. Probabilistic methods are employed to obtain an upper bound on the optimal size of higher-index PHFs when the number of columns is large. A new deterministic algorithm is developed that generates such PHFs meeting this bound, and computational results are reported. Secondly, a restriction on the structure of PHFs is introduced, called fractal, a method from Blackburn. His method is extended in several ways; from homogeneous hash families (every row has the same number of symbols) to heterogeneous ones; and to distributing hash families, a relaxation of the predicate for PHFs. Recursive constructions with fractal hash families as ingredients are given, and improve upon on the best-known sizes of many PHFs. Thirdly, a method of Colbourn and Lanus is extended in which they horizontally copied a given hash family and greedily applied transformations to each copy. Transformations of existential t-restrictions are introduced, which allow for the method to be applicable to any t-restriction having structure like those of hash families. A genetic algorithm is employed for finding the "best" such transformations. Computational results of the GA are reported using PHFs, as the number of transformations permitted is large compared to the number of symbols. Finally, an analysis is given of what trade-offs exist between computation time and the number of t-sets left not satisfying the predicate. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2019

The extended finite state machine (EFSM) is a powerful modelling approach that has been applied to represent a wide range of systems. Despite its popularity, testing from an EFSM is a substantial problem for two main reasons: path feasibility and path test case generation. The path feasibility problem concerns generating transition paths through an EFSM that are feasible and satisfy a given test criterion. In an EFSM, guards and assignments in a path‟s transitions may cause some selected paths to be infeasible. The problem of path test case generation is to find a sequence of inputs that can exercise the transitions in a given feasible path. However, the transitions‟ guards and assignments in a given path can impose difficulties when producing such data making the range of acceptable inputs narrowed down to a possibly tiny range. While search-based approaches have proven efficient in automating aspects of testing, these have received little attention when testing from EFSMs. This thesis proposes an integrated search-based approach to automatically test from an EFSM. The proposed approach generates paths through an EFSM that are potentially feasible and satisfy a test criterion. Then, it generates test cases that can exercise the generated feasible paths. The approach is evaluated by being used to test from five EFSM cases studies. The achieved experimental results demonstrate the value of the proposed approach.

No description available.

Les systèmes logiciels sont devenus de plus en plus répondus et importants dans notre société. Ainsi, il y a un besoin constant de logiciels de haute qualité. Pour améliorer la qualité de logiciels, l’une des techniques les plus utilisées est le refactoring qui sert à améliorer la structure d'un programme tout en préservant son comportement externe. Le refactoring promet, s'il est appliqué convenablement, à améliorer la compréhensibilité, la maintenabilité et l'extensibilité du logiciel tout en améliorant la productivité des programmeurs. En général, le refactoring pourra s’appliquer au niveau de spécification, conception ou code. Cette thèse porte sur l'automatisation de processus de recommandation de refactoring, au niveau code, s’appliquant en deux étapes principales: 1) la détection des fragments de code qui devraient être améliorés (e.g., les défauts de conception), et 2) l'identification des solutions de refactoring à appliquer. Pour la première étape, nous traduisons des régularités qui peuvent être trouvés dans des exemples de défauts de conception. Nous utilisons un algorithme génétique pour générer automatiquement des règles de détection à partir des exemples de défauts. Pour la deuxième étape, nous introduisons une approche se basant sur une recherche heuristique. Le processus consiste à trouver la séquence optimale d'opérations de refactoring permettant d'améliorer la qualité du logiciel en minimisant le nombre de défauts tout en priorisant les instances les plus critiques. De plus, nous explorons d'autres objectifs à optimiser: le nombre de changements requis pour appliquer la solution de refactoring, la préservation de la sémantique, et la consistance avec l’historique de changements. Ainsi, réduire le nombre de changements permets de garder autant que possible avec la conception initiale. La préservation de la sémantique assure que le programme restructuré est sémantiquement cohérent. De plus, nous utilisons l'historique de changement pour suggérer de nouveaux refactorings dans des contextes similaires. En outre, nous introduisons une approche multi-objective pour améliorer les attributs de qualité du logiciel (la flexibilité, la maintenabilité, etc.), fixer les « mauvaises » pratiques de conception (défauts de conception), tout en introduisant les « bonnes » pratiques de conception (patrons de conception). / Software systems have become prevalent and important in our society. There is a constant need for high-quality software. Hence, to improve software quality, one of the most-used techniques is the refactoring which improves design structure while preserving the external behavior. Refactoring has promised, if applied well, to improve software readability, maintainability and extendibility while increasing the speed at which programmers can write and maintain their code. In general, refactoring can be performed in various levels such as the requirement, design, or code level. In this thesis, we mainly focus on the source code level where automated refactoring recommendation can be performed through two main steps: 1) detection of code fragments that need to be improved/fixed (e.g., code-smells), and 2) identification of refactoring solutions to achieve this goal. For the code-smells identification step, we translate regularities that can be found in such code-smell examples into detection rules. To this end, we use genetic programming to automatically generate detection rules from examples of code-smells. For the refactoring identification step, a search-based approach is used. The process aims at finding the optimal sequence of refactoring operations that improve software quality by minimizing the number of detected code-smells while prioritizing the most critical ones. In addition, we explore other objectives to optimize using a multi-objective approach: the code changes needed to apply refactorings, semantics preservation, and the consistency with development change history. Hence, reducing code changes allows us to keep as much as possible the initial design. On the other hand, semantics preservation insures that the refactored program is semantically coherent, and that it models correctly the domain-semantics. Indeed, we use knowledge from historical code change to suggest new refactorings in similar contexts. Furthermore, we introduce a novel multi-objective approach to improve software quality attributes (i.e., flexibility, maintainability, etc.), fix “bad” design practices (i.e., code-smells) while promoting “good” design practices (i.e., design patterns).

Submitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2014-10-15T17:49:53Z No. of bitstreams: 2 Dissertacao - Ana Claudia Bastos Loureiro Monção - 2013.pdf: 4213405 bytes, checksum: 3bbe190ae0f4a45a2f8b4e71026f5d2e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2014-10-16T17:59:00Z (GMT) No. of bitstreams: 2 Dissertacao - Ana Claudia Bastos Loureiro Monção - 2013.pdf: 4213405 bytes, checksum: 3bbe190ae0f4a45a2f8b4e71026f5d2e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-16T17:59:00Z (GMT). No. of bitstreams: 2 Dissertacao - Ana Claudia Bastos Loureiro Monção - 2013.pdf: 4213405 bytes, checksum: 3bbe190ae0f4a45a2f8b4e71026f5d2e (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-08-02 / Software Testing is an important area of Software Engineering to ensuring the software quality. It consists of activities that involve long time and high costs, but need to be made throughout the process of building software. As in other areas of software engineering, there are problems in the activities of Software Testing whose solution is not trivial. For these problems, several techniques of optimization and search have been explored trying to find an optimal solution or near optimal, giving rise to lines of research textit Search-Based Software Engineering (SBSE) and textit Search-Based Software Testing (SBST). This work is part of this context and aims to solve the problem of selecting test data for test execution in SQL statements. Given the number of potential solutions to this problem, the proposed approach combines techniques Mutation Analysis for SQL with Evolutionary Computation to find a reduced data set, that be able to detect a large number of defects in SQL statements of a particular application. Based on a heuristic perspective, the proposal uses Genetic Algorithms (GA) to select tuples from a existing database (from production environment) trying to reduce it to a set of data relevant and effective. During the evolutionary process, Mutation Analysis is used to evaluate each set of test data selected by the AG. The results obtained from the experiments showed a good performance using meta-heuristic of Genetic Algorithms, and its variations. / Teste de Software é uma área da Engenharia de Software de fundamental importância para a garantia da qualidade do software. São atividades que envolvem tempo e custos elevados, mas que precisam ser realizadas durante todo o processo de construção de um software. Assim como em outra áreas da Engenharia de Software, existem problemas nas atividades de Teste de Software cuja solução não é trivial. Para esses problemas, têm sido exploradas várias técnicas de busca e otimização tentando encontrar uma solução ótima ou perto da ótima, dando origem às linhas de pesquisa Search-Based Software Engineering (SBSE) e Search-Based Software Testing (SBST). O presente trabalho está inserido neste contexto e tem como objetivo solucionar o problema de seleção de dados de teste para execução de testes em instruções SQL. Dada a quantidade de soluções possíveis para este problema, a abordagem proposta combina técnicas de Análise de Mutantes SQL com Computação Evolucionária para encontrar um conjunto de dados reduzido que seja capaz de detectar uma grande quantidade de defeitos em instruções SQL de uma determinada aplicação. Baseada em uma perspectiva heurística, a proposta utiliza Algoritmos Genéticos (AG) para selecionar tuplas de um banco de dados existente (de produção) tentando reduzi-lo em um conjunto de dados relevante e efetivo. Durante o processo evolucionário, a Análise de Mutantes é utilizada para avaliação de cada conjunto de dados de teste selecionado pelo AG. Os resultados obtidos com a realização dos experimentos revelaram um bom desempenho utilizando a metaheurística dos Algoritmos Genéticos e suas variações.

Context: Bug fixing is the process of ensuring correct source code and is done by developer. Automated debugging and bug fixing solutions minimize human intervention and hence minimize the chance of producing new bugs in the corrected program. Scope and Objectives: In this study we performed a detailed systematic literature review. The scope of work is to identify all those solutions that correct software automatically or semi-automatically. Solutions for automatic correction of software do not need human intervention while semi-automatic solutions facilitate a developer in fixing a bug. We aim to gather all such solutions to fix bugs in design, i.e., code, UML design, algorithms and software architecture. Automated detection, isolation and localization of bug are not in our scope. Moreover, we are only concerned with software bugs and excluding hardware and networking domains. Methods: A detailed systematic literature review (SLR) has been performed. A number of bibliographic sources are searched, including Inspec, IEEE Xplore, ACM digital library, Scopus, Springer Link and Google Scholar. Inclusion/exclusion, study quality assessment, data extraction and synthesis have been performed in depth according to guidelines provided for performing SLR. Grounded theory is used to analyze literature data. To check agreement level between two researchers, Kappa analysis is used. Results: Through SLR we identified 46 techniques. These techniques are classified in automated/semi-automated debugging and bug fixing. Strengths and weaknesses of each of them are identified, along with which types of bugs each can fix and in which language they can be implement. In the end, classification is performed which generate a list of approaches, techniques, tools, frameworks, methods and systems. Along, this classification and categorization we separated bug fixing and debugging on the bases of search algorithms. Conclusion: In conclusion achieved results are all automated/semi-automated debugging and bug fixing solutions that are available in literature. The strengths/benefits and weaknesses/limitations of these solutions are identified. We also recognize type of bugs that can be fixed using these solutions. And those programming languages in which these solutions can be implemented are discovered as well. In the end a detail classification is performed. / alla automatiska / halvautomatiska felsökning och felrättning lösningar som är tillgängliga i litteraturen. De styrkor / fördelar och svagheter / begränsningar av dessa lösningar identifieras. Vi erkänner också typ av fel som kan fastställas med hjälp av dessa lösningar. Och de programmeringsspråk där dessa lösningar kan genomföras upptäcks också. Till slut en detalj klassificering utförs / +46 763 23 93 87, +46 70 966 09 51

[pt] Sistemas impactados por Problemas de Projeto (PPs) podem se tornar difíceis de manter e evoluir. A identificação de PPs pode ocorrer por meio de múltiplos sintomas, tais como code smells. Após tal identificação, pode-se remover os PPs por meio de refatorações. No entanto, decidir onde e como refatorar é uma tarefa desafiadora. Assim, técnicas de recomendação de refatoração têm sido propostas. Apesar disso, ainda há pouco consenso sobre quais requisitos devem ser atendidos por elas. Nesta tese, estamos propondo quatro requisitos empiricamente identificados que tais técnicas devem seguir. Primeiro, cada PP geralmente está relacionado a vários tipos de sintomas no código-fonte e eles devem ser considerados juntos para gerar recomendações. Além disso, uma técnica de recomendação deve permitir a seleção de contextos específicos para refatoração. Quarto, também deve-se considerar as funcionalidades modificadas para criar recomendações úteis. Finalmente, os desenvolvedores nem sempre conduzem as refatorações mais eficazes na prática, muitas vezes inconscientemente, resultando na remoção incompleta de PPs. Assim, eles precisam de assistência para remover os PPs. Existem apenas técnicas que atendem parcialmente aos requisitos mencionados. Sendo assim, nós propomos a técnica OrganicRef. OrganicRef destina-se a ajudar os desenvolvedores na remoção de PPs em seus contextos de interesse. OrganicRef encontra as funcionalidades dos elementos de código usando um algoritmo de modelagem de tópicos. Em seguida, ele coleta múltiplos tipos de sintomas que afetam os elementos do código. Para recomendar refatorações, OrganicRef combina heurísticas baseadas em regras e baseadas em funcionalidades. OrganicRef também aplica otimização baseada em busca para derivar várias recomendações possíveis. Para avaliar o OrganicRef, realizamos um estudo experimental com seis projetos de software. Os resultados mostraram que as recomendações do OrganicRef melhoram significativamente a qualidade dos elementos refatorados. / [en] Software projects impacted by Design Problems (DPs) may become difficult to maintain and evolve. The identification of DPs may occur through symptoms such as code smells. After such identification, developers can remove the DPs through refactorings. However, deciding where and how to refactor is a challenging task. Thus, several refactoring recommendation techniques have been proposed. Nevertheless, there is still little consensus on which requirements must be satisfied by them. In this thesis, we are proposing four empirically identified requirements that any DP removal technique should follow. First, each single DP is usually related with multiple types of symptoms in the source code and they should be considered altogether for generating recommendations. Second, a recommendation technique should allow the selection of possible candidate contexts for refactoring. Fourth, the technique should consider the features of undergoing changes to create useful recommendations. Finally, developers do not always conduct the most effective refactorings in practice, quite often unconsciously, resulting in the incomplete removal of DPs. Thus, they need assistance to remove DPs. There are techniques partially fulfilling the aforementioned requirements, though none satisfactorily meets them all. Thus, we propose the OrganicRef technique. OrganicRef is intended to help developers in removing DPs in their contexts of interest. OrganicRef finds the contexts by capturing the features affecting relevant code elements using a topic modeling algorithm. Then, it collects multiple symptom types affecting the code elements. To recommend effective refactorings, OrganicRef combines rulebased and feature-driven heuristics. It also uses search-based optimization to derive multiple possible recommendations. To evaluate OrganicRef, we conducted an empirical study with six open source projects. Results showed that OrganicRef recommendations significantly improves the design of refactored elements.

La transformation de modèles consiste à transformer un modèle source en un modèle cible conformément à des méta-modèles source et cible. Nous distinguons deux types de transformations. La première est exogène où les méta-modèles source et cible représentent des formalismes différents et où tous les éléments du modèle source sont transformés. Quand elle concerne un même formalisme, la transformation est endogène. Ce type de transformation nécessite généralement deux étapes : l’identification des éléments du modèle source à transformer, puis la transformation de ces éléments. Dans le cadre de cette thèse, nous proposons trois principales contributions liées à ces problèmes de transformation. La première contribution est l’automatisation des transformations des modèles. Nous proposons de considérer le problème de transformation comme un problème d'optimisation combinatoire où un modèle cible peut être automatiquement généré à partir d'un nombre réduit d'exemples de transformations. Cette première contribution peut être appliquée aux transformations exogènes ou endogènes (après la détection des éléments à transformer). La deuxième contribution est liée à la transformation endogène où les éléments à transformer du modèle source doivent être détectés. Nous proposons une approche pour la détection des défauts de conception comme étape préalable au refactoring. Cette approche est inspirée du principe de la détection des virus par le système immunitaire humain, appelée sélection négative. L’idée consiste à utiliser de bonnes pratiques d’implémentation pour détecter les parties du code à risque. La troisième contribution vise à tester un mécanisme de transformation en utilisant une fonction oracle pour détecter les erreurs. Nous avons adapté le mécanisme de sélection négative qui consiste à considérer comme une erreur toute déviation entre les traces de transformation à évaluer et une base d’exemples contenant des traces de transformation de bonne qualité. La fonction oracle calcule cette dissimilarité et les erreurs sont ordonnées selon ce score. Les différentes contributions ont été évaluées sur d’importants projets et les résultats obtenus montrent leurs efficacités. / Model transformations take as input a source model and generate as output a target model. The source and target models conform to given meta-models. We distinguish between two transformation categories. Exogenous transformations are transformations between models expressed using different languages, and the whole source model is transformed. Endogenous transformations are transformations between models expressed in the same language. For endogenous transformations, two steps are needed: identifying the source model elements to transform and then applying the transformation on them. In this thesis, we propose three principal contributions. The first contribution aims to automate model transformations. The process is seen as an optimization problem where different transformation possibilities are evaluated and, for each possibility, a quality is associated depending on its conformity with a reference set of examples. This first contribution can be applied to exogenous as well as endogenous transformation (after determining the source model elements to transform). The second contribution is related precisely to the detection of elements concerned with endogenous transformations. In this context, we present a new technique for design defect detection. The detection is based on the notion that the more a code deviates from good practice, the more likely it is bad. Taking inspiration from artificial immune systems, we generate a set of detectors that characterize the ways in which a code can diverge from good practices. We then use these detectors to determine how far the code in the assessed systems deviates from normality. The third contribution concerns transformation mechanism testing. The proposed oracle function compares target test cases with a base of examples containing good quality transformation traces, and assigns a risk level based on the dissimilarity between the two. The traces help the tester understand the origin of an error. The three contributions are evaluated with real software projects and the obtained results confirm their efficiencies.

La génération de stratégies pour les solveurs en Satisfiabilité Modulo des Théories (SMT) nécessite des outils théoriques et pratiques qui permettent aux utilisateurs d’exercer un contrôle stratégique sur les aspects heuristiques fondamentaux des solveurs de SMT, tout en garantissant leur performance. Nous nous intéressons dans cette thèse au solveur Z3 , l’un des plus efficaces lors des compétitions SMT (SMT-COMP). Dans les solveurs SMT, la définition d’une stratégie repose sur un ensemble de composants et paramètres pouvant être agencés et configurés afin de guider la recherche d’une preuve de (in)satisfiabilité d’une instance donnée. Dans cette thèse, nous abordons ce défi en définissant un cadre pour la génération autonome de stratégies pour Z3, c’est-à-dire un algorithme qui permet de construire automatiquement des stratégies sans faire appel à des connaissances d’expertes. Ce cadre général utilise une approche évolutionnaire (programmation génétique), incluant un système à base de règles. Ces règles formalisent la modification de stratégies par des principes de réécriture, les algorithmes évolutionnaires servant de moteur pour les appliquer. Cette couche intermédiaire permettra d’appliquer n’importe quel algorithme ou opérateur sans qu’il soit nécessaire de modifier sa structure, afin d’introduire de nouvelles informations sur les stratégies. Des expérimentations sont menées sur les jeux classiques de la compétition SMT-COMP. / The Strategy Challenge in Satisfiability Modulo Theories (SMT) claims to build theoretical and practical tools allowing users to exert strategic control over core heuristic aspects of high-performance SMT solvers. In this work, we focus in Z3 Theorem Prover: one of the most efficient SMT solver according to the SMT Competition, SMT-COMP. In SMT solvers, the definition of a strategy relies on a set of tools that can be scheduled and configured in order to guide the search for a (un)satisfiability proof of a given instance. In this thesis, we address the Strategy Challenge in SMT defining a framework for the autonomous generation of strategies in Z3, i.e. a practical system to automatically generate SMT strategies without the use of expert knowledge. This framework is applied through an incremental evolutionary approach starting from basic algorithms to more complex genetic constructions. This framework formalise strategies modification as rewriting rules, where algorithms acts as enginess to apply them. This intermediate layer, will allow apply any algorithm or operator with no need to being structurally modified, in order to introduce new information in strategies. Validation is done through experiments on classic benchmarks of the SMT-COMP.