Generación de Casos de Prueba en Programación Orientada a Objetos = Test Case Generation in Object-Oriented Programming

Las pruebas de software (Testing) son en la actualidad la técnica más utilizada para la validación y la evaluación de la calidad de un programa. El testing está integrado en todas las metodologías prácticas de desarrollo de software y juega un papel crucial en el éxito de cualquier proyecto de software. Desde las unidades de código más pequeñas a los componentes más complejos, su integración en un sistema de software y su despliegue a producción, todas las piezas de un producto de software deben ser probadas a fondo antes de que el producto de software pueda ser liberado a un entorno de producción. La mayor limitación del testing de software es que continúa siendo un conjunto de tareas manuales, representando una buena parte del coste total de desarrollo. En este escenario, la automatización resulta fundamental para aliviar estos altos costes. La generación automática de casos de pruebas (TCG, del inglés test case generation) es el proceso de generar automáticamente casos de prueba que logren un alto recubrimiento del programa. Entre la gran variedad de enfoques hacia la TCG, esta tesis se centra en un enfoque estructural de caja blanca, y más concretamente en una de las técnicas más utilizadas actualmente, la ejecución simbólica. En ejecución simbólica, el programa bajo pruebas es ejecutado con expresiones simbólicas como argumentos de entrada en lugar de valores concretos. Esta tesis se basa en un marco general para la generación automática de casos de prueba dirigido a programas imperativos orientados a objetos (Java, por ejemplo) y basado en programación lógica con restricciones (CLP, del inglés constraint logic programming). En este marco general, el programa imperativo bajo pruebas es primeramente traducido a un programa CLP equivalente, y luego dicho programa CLP es ejecutado simbólicamente utilizando los mecanismos de evaluación estándar de CLP, extendidos con operaciones especiales para el tratamiento de estructuras de datos dinámicas. Mejorar la escalabilidad y la eficiencia de la ejecución simbólica constituye un reto muy importante. Es bien sabido que la ejecución simbólica resulta impracticable debido al gran número de caminos de ejecución que deben ser explorados y a tamaño de las restricciones que se deben manipular. Además, la generación de casos de prueba mediante ejecución simbólica tiende a producir un número innecesariamente grande de casos de prueba cuando es aplicada a programas de tamaño medio o grande. Las contribuciones de esta tesis pueden ser resumidas como sigue. (1) Se desarrolla un enfoque composicional basado en CLP para la generación de casos de prueba, el cual busca aliviar el problema de la explosión de caminos interprocedimiento analizando de forma separada cada componente (p.ej. método) del programa bajo pruebas, almacenando los resultados y reutilizándolos incrementalmente hasta obtener resultados para el programa completo. También se ha desarrollado un enfoque composicional basado en especialización de programas (evaluación parcial) para la herramienta de ejecución simbólica Symbolic PathFinder (SPF). (2) Se propone una metodología para usar información del consumo de recursos del programa bajo pruebas para guiar la ejecución simbólica hacia aquellas partes del programa que satisfacen una determinada política de recursos, evitando la exploración de aquellas partes del programa que violan dicha política. (3) Se propone una metodología genérica para guiar la ejecución simbólica hacia las partes más interesantes del programa, la cual utiliza abstracciones como generadores de trazas para guiar la ejecución de acuerdo a criterios de selección estructurales. (4) Se propone un nuevo resolutor de restricciones, el cual maneja eficientemente restricciones sobre el uso de la memoria dinámica global (heap) durante ejecución simbólica, el cual mejora considerablemente el rendimiento de la técnica estándar utilizada para este propósito, la \lazy initialization". (5) Todas las técnicas propuestas han sido implementadas en el sistema PET (el enfoque composicional ha sido también implementado en la herramienta SPF). Mediante evaluación experimental se ha confirmado que todas ellas mejoran considerablemente la escalabilidad y eficiencia de la ejecución simbólica y la generación de casos de prueba. ABSTRACT Testing is nowadays the most used technique to validate software and assess its quality. It is integrated into all practical software development methodologies and plays a crucial role towards the success of any software project. From the smallest units of code to the most complex components and their integration into a software system and later deployment; all pieces of a software product must be tested thoroughly before a software product can be released. The main limitation of software testing is that it remains a mostly manual task, representing a large fraction of the total development cost. In this scenario, test automation is paramount to alleviate such high costs. Test case generation (TCG) is the process of automatically generating test inputs that achieve high coverage of the system under test. Among a wide variety of approaches to TCG, this thesis focuses on structural (white-box) TCG, where one of the most successful enabling techniques is symbolic execution. In symbolic execution, the program under test is executed with its input arguments being symbolic expressions rather than concrete values. This thesis relies on a previously developed constraint-based TCG framework for imperative object-oriented programs (e.g., Java), in which the imperative program under test is first translated into an equivalent constraint logic program, and then such translated program is symbolically executed by relying on standard evaluation mechanisms of Constraint Logic Programming (CLP), extended with special treatment for dynamically allocated data structures. Improving the scalability and efficiency of symbolic execution constitutes a major challenge. It is well known that symbolic execution quickly becomes impractical due to the large number of paths that must be explored and the size of the constraints that must be handled. Moreover, symbolic execution-based TCG tends to produce an unnecessarily large number of test cases when applied to medium or large programs. The contributions of this dissertation can be summarized as follows. (1) A compositional approach to CLP-based TCG is developed which overcomes the inter-procedural path explosion by separately analyzing each component (method) in a program under test, stowing the results as method summaries and incrementally reusing them to obtain whole-program results. A similar compositional strategy that relies on program specialization is also developed for the state-of-the-art symbolic execution tool Symbolic PathFinder (SPF). (2) Resource-driven TCG is proposed as a methodology to use resource consumption information to drive symbolic execution towards those parts of the program under test that comply with a user-provided resource policy, avoiding the exploration of those parts of the program that violate such policy. (3) A generic methodology to guide symbolic execution towards the most interesting parts of a program is proposed, which uses abstractions as oracles to steer symbolic execution through those parts of the program under test that interest the programmer/tester most. (4) A new heap-constraint solver is proposed, which efficiently handles heap-related constraints and aliasing of references during symbolic execution and greatly outperforms the state-of-the-art standard technique known as lazy initialization. (5) All techniques above have been implemented in the PET system (and some of them in the SPF tool). Experimental evaluation has confirmed that they considerably help towards a more scalable and efficient symbolic execution and TCG.

MODEL PARTITIONS AND COMPACT TEST CASE SUITES

We present a generalized test case generation method, called the G method. Although inspired by the W method, the G method, in contrast, allows for test case suite generation even in the absence of characterization sets for the specification models. Instead, the G method relies on knowledge about the index of certain equivalences induced at the implementation models. We show that the W method can be derived from the G method as a particular case. Moreover, we discuss some naturally occurring infinite classes of FSM models over which the G method generates test suites that are exponentially more compact than those produced by the W method.

Integrating testcase generator into Eclipse environment

Tämädiplomityö tutkii kuinka Eclipse -ympäristöä voidaan käyttää testitapausten generoinnissa. Eräs diplomityön pääaiheista on tutkia voidaanko olemassa olevilla Eclipsen komponenteilla parantaa symboolitietoutta, jotta testitapausten generointiin saataisiin lisää tietoa. Aluksi diplomityö antaa lyhyen katsauksen ohjelmistojentestaukseen, jotta lukija ymmärtää mitä ohjelmistotekniikan osa-aluetta diplomityö käsittelee. Tämän jälkeen kerrotaan lisää tietoa itse testitapausten generointiprosessista. Kun perusteet on käsitelty, tutustetaan lukija Eclipse -ympäristöön, mikä se on, mistä se koostuu ja mitä sillä voidaan tehdä. Tarkempaa tietoa kerrotaan Eclipsen komponenteista joita voidaan käyttää apuna testitapausten generoinnissa. Integrointi esimerkkinä diplomityössä esitellään valmiin testitapausgeneraattorin integrointi Eclipse -ympäristöön. Lopuksi Eclipse -pohjaista ratkaisua verrataan symboolitietouden sekä ajoajan kannalta aikaisempaan ratkaisuun. Diplomityön tuloksena syntyi prototyyppi jonka avulla todistettiin, että Eclipse - ympäristöön on mahdollista integroida testitapausgeneraattori ja että se voi lisätä symboolitietoutta. Tämätietouden lisäys kuitenkin lisäsi myös tarvittavaa ajoaikaa, joissakintapauksissa jopa merkittävästi. Samalla todettiin, että tällä hetkellä on menossa projekteja joiden tarkoituksena on parantaa käytettyjen Eclipse komponenttien suorituskykyä ja että tämä voi parantaa tuloksia tulevaisuudessa.

Automated Software Debugging Using Hybrid Static/Dynamic Analysis

With the increasing complexity of today's software, the software development process is becoming highly time and resource consuming. The increasing number of software configurations, input parameters, usage scenarios, supporting platforms, external dependencies, and versions plays an important role in expanding the costs of maintaining and repairing unforeseeable software faults. To repair software faults, developers spend considerable time in identifying the scenarios leading to those faults and root-causing the problems. While software debugging remains largely manual, it is not the case with software testing and verification. The goal of this research is to improve the software development process in general, and software debugging process in particular, by devising techniques and methods for automated software debugging, which leverage the advances in automatic test case generation and replay. In this research, novel algorithms are devised to discover faulty execution paths in programs by utilizing already existing software test cases, which can be either automatically or manually generated. The execution traces, or alternatively, the sequence covers of the failing test cases are extracted. Afterwards, commonalities between these test case sequence covers are extracted, processed, analyzed, and then presented to the developers in the form of subsequences that may be causing the fault. The hypothesis is that code sequences that are shared between a number of faulty test cases for the same reason resemble the faulty execution path, and hence, the search space for the faulty execution path can be narrowed down by using a large number of test cases. To achieve this goal, an efficient algorithm is implemented for finding common subsequences among a set of code sequence covers. Optimization techniques are devised to generate shorter and more logical sequence covers, and to select subsequences with high likelihood of containing the root cause among the set of all possible common subsequences. A hybrid static/dynamic analysis approach is designed to trace back the common subsequences from the end to the root cause. A debugging tool is created to enable developers to use the approach, and integrate it with an existing Integrated Development Environment. The tool is also integrated with the environment's program editors so that developers can benefit from both the tool suggestions, and their source code counterparts. Finally, a comparison between the developed approach and the state-of-the-art techniques shows that developers need only to inspect a small number of lines in order to find the root cause of the fault. Furthermore, experimental evaluation shows that the algorithm optimizations lead to better results in terms of both the algorithm running time and the output subsequence length.

Early modes of exegesis : ideal figures in Malachi as a test case

Antikens judiska bibeltolkare hade ett annorlunda sätt att läsa Bibeln än den som moderna läsare är vana vid. Dessa tidiga exegeter tänkte att texten som nu finns i den hebreiska Bibeln, de kristnas Gamla Testamente, är helig ordagrant i den form som den fanns i under deras tid, att den inte innehåller några fel, och att Gud har en övergripande plan gällande helheten, så att man vid behov kan förklara ett Bibelställe med hjälp av ett annat. Dessa antaganden reflekteras i det sätt på vilket antikens exegeter läste och tolkade sin Bibel. Det här ser man då man läser deras texter, från 400-talet före vår tideräknings början till de första århundradena enligt vår tideräkning. Ett verktyg som antikens skrifttolkare ofta använde var den så kallade gezera shava -metoden, där de jämförde identiska ord och fraser i Bibeln för att skänka belysning åt oklara textställen. Hebreiskan, särskilt den ovokaliserade konsonanttexten, innehåller många homonyma ord, alltså ord som ser likadana ut men har olika betydelser. De tidiga exegeterna utnyttjade ofta de möjligheter till alternativa tolkningar som uppstår ur denna tvetydighet. Ibland kunde de dock tvärtom också dra paralleller ur kontextuella likheter, alltid efter behov. I denna avhandling står dessa tidiga anonyma bibeltolkare och deras tolkningar i fokus. Malakis bok, som härstammar från ca år 475 f.v.t., kan ses som ett viktigt tidigt exempel på denna tendens till nytolkning av traditioner. Boken själv har dock också blivit föremål till nytolkningar, redan i de tilläggsverser som finns i dess slut, men särskilt i senare judisk litteratur och i Nya Testamentet. I avhandlingen granskas de fem bibliska gestalter som nämns i Malaki: Jakob, Esau, Levi, Mose och Elia. Hur används de i boken och hur har senare traditioner som anknyter till dem influerats av Malaki? ------------------------------------------------ Antiikin juutalaiset raamatunselittäjät lukivat Raamattua eri tavoin kuin moderni lukija. Heidän näkemyksensä mukaan se teksti, joka nykyään löytyy heprealaisesta Raamatusta eli kristittyjen Vanhasta testamentista, oli pyhä juuri sellaisessa muodossa, jossa se oli heille välittynyt. Se oli virheetön, ja Jumalalla oli siitä kokonaisnäkemys, joka voisi selvitä myös tulkitsijalle, kun tämä vain tutkisi tekstiä riittävän tarkkaan. Nämä perusoletukset näkyvät tavassa, jolla antiikin eksegeetit lukivat ja tulkitsivat Raamattuaan. Se voidaan huomata heidän jälkeensä jättämistään teksteistä, alkaen noin 400-luvulta ennen ajanlaskumme alkua ja jatkuen ajanlaskumme ensimmäisiin vuosisatoihin. Antiikin raamatunselittäjät käyttivät yleisesti muun muassa metodia, joka rabbiinisessa kirjallisuudessa tunnetaan nimellä gezera shava. Raamatussa kahdessa tai useammassa kohtaa esiintyviä samoja sanoja ja ilmauksia verrattiin tällöin toisiinsa ja pyrittiin siten saamaan valaistusta epäselvinä pidettyihin tekstinkohtiin. Heprealle, etenkin sen vokalisoimattomassa muodossa, on tyypillistä homonyymisyys. Samannäköiset sanat voivat eri yhteyksissä tarkoittaa eri asioita. Varhaiset eksegeetit päätyivät usein tästä ilmiöstä nouseviin, keskenään vaihtoehtoisiin tulkintoihin. Toisaalta he saattoivat myös tarvittaessa selittää tekstinkohtaa toisella tekstinkohdalla ainoastaan näiden sisällöllisenkin yhtäläisyyden perusteella. Tässä väitöstutkimuksessa tarkastellaan näitä varhaisia, meille nimettömiksi jääneitä raamatunselittäjiä ja heidän tulkintojaan käyttämällä tutkimuksen lähtökohtana Malakian kirjaa. Malakiaa, joka on peräisin noin vuodelta 475 ennen ajanlaskumme alkua, voidaan pitää yhtenä tärkeimmistä ja varhaisimmista teksteistä, joissa traditioita yhdistellään ja kerrotaan uudelleen edellä mainittuihin perusajatuksiin nojaten ja niihin pohjautuvia menetelmiä käyttäen. Toisaalta Malakian kirjaa on myös tulkittu samojen periaatteiden mukaisesti jo sen myöhemmältä ajalta peräisin olevissa loppujakeissa, ja sittemmin muussa varhaisessa juutalaisessa kirjallisuudessa sekä Uudessa testamentissa. Väitöstutkimuksessa tarkastellaan erityisesti niitä viittä henkilöä, jotka mainitaan Malakian kirjassa: Jaakobia, Esauta, Leeviä, Moosesta ja Eliaa. Kirjoittaja tutkii, miten heidän hahmojaan on käytetty Malakian kirjassa, millaisiin heitä koskeviin traditioihin tämä käyttötapa perustuu, ja missä määrin Malakian kirjan vaikutus on havaittavissa myöhemmässä näihin henkilöihin liitetyssä perinteessä.

(PDF, 406 KB) On L3 acquisition and phonological permeability: a new test case for debates on the mental representation of non-native phonological systems

The goal of this article is to make an epistemological and theoretical contribution to the nascent field of third language (L3) acquisition and show how examining L3 development can offer a unique view into longstanding debates within L2 acquisition theory. We offer the Phonological Permeability Hypothesis (PPH), which maintains that examining the development of an L3/Ln phonological system and its effects on a previously acquired L2 phonological system can inform contemporary debates regarding the mental constitution of postcritical period adult phonological acquisition. We discuss the predictions and functional significance of the PPH for adult SLA and multilingualism studies, detailing a methodology that examines the effects of acquiring Brazilian Portuguese on the Spanish phonological systems learned before and after the so-called critical period (i.e., comparing simultaneous versus successive adult English-Spanish bilinguals learning Brazilian Portuguese as an L3).

DEMO models based automatic workflow process generation

Nowadays, more than half of the computer development projects fail to meet the final users' expectations. One of the main causes is insufficient knowledge about the organization of the enterprise to be supported by the respective information system. The DEMO methodology (Design and Engineering Methodology for Organizations) has been proved as a well-defined method to specify, through models and diagrams, the essence of any organization at a high level of abstraction. However, this methodology is platform implementation independent, lacking the possibility of saving and propagating possible changes from the organization models to the implemented software, in a runtime environment. The Universal Enterprise Adaptive Object Model (UEAOM) is a conceptual schema being used as a basis for a wiki system, to allow the modeling of any organization, independent of its implementation, as well as the previously mentioned change propagation in a runtime environment. Based on DEMO and UEAOM, this project aims to develop efficient and standardized methods, to enable an automatic conversion of DEMO Ontological Models, based on UEAOM specification into BPMN (Business Process Model and Notation) models of processes, using clear semantics, without ambiguities, in order to facilitate the creation of processes, almost ready for being executed on workflow systems that support BPMN.