On reducing test length for FSMs with extra states

A long-standing problem when testing from a deterministic finite state machine is to guarantee full fault coverage even if the faults introduce extra states in the implementations. It is well known that such tests should include the sequences in a traversal set which contains all input sequences of length defined by the number of extra states. This paper suggests the SPY method, which helps reduce the length of tests by distributing sequences of the traversal set and reducing test branching. It is also demonstrated that an additional assumption about the implementation under test relaxes the requirement of the complete traversal set. The results of the experimental comparison of the proposed method with an existing method indicate that the resulting reduction can reach 40%. Experimental results suggest that the additional assumption about the implementation can help in further reducing the test suite length. Copyright (C) 2011 John Wiley & Sons, Ltd.

Conceptualización de requerimientos: Propuesta de proceso y técnicas asociadas

El proceso de captura de requisitos constituye un proceso con connotaciones sociales relacionadas con diferentes personas (stakeholders), una circunstancia que hace que ciertos problemas se presenten cuando se lleva adelante el proceso de conceptualización de requisitos. Se propone un proceso de conceptualización de requisitos que se estructura en dos fases: (a) Análisis Orientado a al Problema: cuyo objetivo es comprender el problema dado por el usuario en el dominio en el que este se lleva a cabo, y (b) Análisis de Orientado al Producto: cuyo objetivo es obtener las funcionalidades que el usuario espera del producto de software a desarrollar, teniendo en cuenta la relación de estas con la realidad expresada por el usuario en su discurso. Se proponen seis técnicas que articulan cada una de las tareas que componen las fases de proceso propuesto.

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.

Extração de casos de teste utilizando Redes de Petri hierárquicas e validação de resultados utilizando OWL.

Este trabalho propõe dois métodos para teste de sistemas de software: o primeiro extrai ideias de teste de um modelo desenvolvido em rede de Petri hierárquica e o segundo valida os resultados após a realização dos testes utilizando um modelo em OWL-S. Estes processos aumentam a qualidade do sistema desenvolvido ao reduzir o risco de uma cobertura insuficiente ou teste incompleto de uma funcionalidade. A primeira técnica apresentada consiste de cinco etapas: i) avaliação do sistema e identificação dos módulos e entidades separáveis, ii) levantamento dos estados e transições, iii) modelagem do sistema (bottom-up), iv) validação do modelo criado avaliando o fluxo de cada funcionalidade e v) extração dos casos de teste usando uma das três coberturas de teste apresentada. O segundo método deve ser aplicado após a realização dos testes e possui cinco passos: i) primeiro constrói-se um modelo em OWL (Web Ontology Language) do sistema contendo todas as informações significativas sobre as regras de negócio da aplicação, identificando as classes, propriedades e axiomas que o regem; ii) em seguida o status inicial antes da execução é representado no modelo através da inserção das instâncias (indivíduos) presentes; iii) após a execução dos casos de testes, a situação do modelo deve ser atualizada inserindo (sem apagar as instâncias já existentes) as instâncias que representam a nova situação da aplicação; iv) próximo passo consiste em utilizar um reasoner para fazer as inferências do modelo OWL verificando se o modelo mantém a consistência, ou seja, se não existem erros na aplicação; v) finalmente, as instâncias do status inicial são comparadas com as instâncias do status final, verificando se os elementos foram alterados, criados ou apagados corretamente. O processo proposto é indicado principalmente para testes funcionais de caixa-preta, mas pode ser facilmente adaptado para testes em caixa branca. Obtiveram-se casos de testes semelhantes aos que seriam obtidos em uma análise manual mantendo a mesma cobertura do sistema. A validação provou-se condizente com os resultados esperados, bem como o modelo ontológico mostrouse bem fácil e intuitivo para aplicar manutenções.

Aplicação de modelos de defeitos na geração de conjuntos de teste completos a partir de Sistemas de Transição com Entrada/Saída

O Teste Baseado em Modelos (TBM) emergiu como uma estratégia promissora para minimizar problemas relacionados à falta de tempo e recursos em teste de software e visa verificar se a implementação sob teste está em conformidade com sua especificação. Casos de teste são gerados automaticamente a partir de modelos comportamentais produzidos durante o ciclo de desenvolvimento de software. Entre as técnicas de modelagem existentes, Sistemas de Transição com Entrada/Saída (do inglês, Input/Output Transition Systems - IOTSs), são modelos amplamente utilizados no TBM por serem mais expressivos do que Máquinas de Estado Finito (MEFs). Apesar dos métodos existentes para geração de testes a partir de IOTSs, o problema da seleção de casos de testes é um tópico difícil e importante. Os métodos existentes para IOTS são não-determinísticos, ao contrário da teoria existente para MEFs, que fornece garantia de cobertura completa com base em um modelo de defeitos. Esta tese investiga a aplicação de modelos de defeitos em métodos determinísticos de geração de testes a partir de IOTSs. Foi proposto um método para geração de conjuntos de teste com base no método W para MEFs. O método gera conjuntos de teste de forma determinística além de satisfazer condições de suficiência de cobertura da especificação e de todos os defeitos do domínio de defeitos definido. Estudos empíricos avaliaram a aplicabilidade e eficácia do método proposto: resultados experimentais para analisar o custo de geração de conjuntos de teste utilizando IOTSs gerados aleatoriamente e um estudo de caso com especificações da indústria mostram a efetividade dos conjuntos gerados em relação ao método tradicional de Tretmans.

Effects of leukapheresis protocol, cell processing and cryopreservation on the generation of monocyte-derived DC for immune therapy

Background Many clinical trials of DC-based immunotherapy involve administration of monocyte-derived DCs (Mo-DC) on multiple occasions. We aimed to determine the optimal cell processing procedures and timing (leukapheresis, RBC depletion and cryopreservation) for generation of Mo-DC for clinical purposes. Methods Leukapheresis was undertaken using a COBE Spectra. Two instrument settings were compared - the standard semi-automated software (Version 4.7) (n = 10) and the fully automated software (Version 6.0) (n = 40). Density gradient centrifugation using Ficoll, Percoll, a combination of these methods or neither for RBC depletion were compared. Outcomes (including cell yield and purity) were compared for cryopreserved unmanipulated monocytes and cryopreserved Mo-DC. Results Software Version 6.0 provided significantly better enrichment for monocytes (P

Towards requirements aware systems:run-time resolution of design-time assumptions

In earlier work we proposed the idea of requirements-aware systems that could introspect about the extent to which their goals were being satisfied at runtime. When combined with requirements monitoring and self adaptive capabilities, requirements awareness should help optimize goal satisfaction even in the presence of changing run-time context. In this paper we describe initial progress towards the realization of requirements-aware systems with REAssuRE. REAssuRE focuses on explicit representation of assumptions made at design time. When such assumptions are shown not to hold, REAssuRE can trigger system adaptations to alternative goal realization strategies.

Optical and structural ocular changes during incipient presbyopia

The primary aim of this thesis was to investigate the in vivo ocular morphological and contractile changes occurring within the accommodative apparatus prior to the onset of presbyopia, with particular reference to ciliary muscle changes with age and the origin of a myopic shift in refraction during incipient presbyopia. Commissioned semi-automated software proved capable of extracting accurate and repeatable measurements from crystalline lens and ciliary muscle Anterior Segment Optical Coherence Tomography (AS-OCT) images and reduced the subjectivity of AS-OCT image analysis. AS-OCT was utilised to document longitudinal changes in ciliary muscle morphology within an incipient presbyopic population (n=51). A significant antero-inwards shift of ciliary muscle mass was observed after 2.5 years. Furthermore, in a subgroup study (n=20), an accommodative antero-inwards movement of ciliary muscle mass was evident. After 2.5 years, the centripetal response of the ciliary muscle significantly attenuated during accommodation, whereas the antero-posterior mobility of the ciliary muscle remained invariant. Additionally, longitudinal measurement of ocular biometry revealed a significant increase in crystalline lens thickness and a corresponding decrease in anterior chamber depth after 2.5 years (n=51). Lenticular changes appear to be determinant of changes in refraction during incipient presbyopia. During accommodation, a significant increase in crystalline lens thickness and axial length was observed, whereas anterior chamber depth decreased (n=20). The change in ocular biometry per dioptre of accommodation exerted remained invariant after 2.5 years. Cross-sectional ocular biometric data were collected to quantify accommodative axial length changes from early adulthood to advanced presbyopia (n=72). Accommodative axial length elongation significantly attenuated during presbyopia, which was consistent with a significant increase in ocular rigidity during presbyopia. The studies presented in this thesis support the Helmholtz theory of accommodation and despite the reduction in centripetal ciliary muscle contractile response with age, primarily implicate lenticular changes in the development of presbyopia.

Reliability of retinal vessel calibre measurements using a retinal oximeter

Background: Summarised retinal vessel diameters are linked to systemic vascular pathology. Monochromatic images provide best contrast to measure vessel calibres. However, when obtaining images with a dual wavelength oximeter the red-free image can be extracted as the green channel information only which in turn will reduce the number of photographs taken at a given time. This will reduce patient exposure to the camera flash and could provide sufficient quality images to reliably measure vessel calibres. Methods: We obtained retinal images of one eye of 45 healthy participants. Central retinal arteriolar and central retinal venular equivalents (CRAE and CRVE, respectively) were measured using semi-automated software from two monochromatic images: one taken with a red-free filter and one extracted from the green channel of a dual wavelength oximetry image. Results: Participants were aged between 21 and 62 years, all were normotensive (SBP: 115 (12) mmHg; DBP: 72 (10) mmHg) and had normal intra-ocular pressures (12 (3) mmHg). Bland-Altman analysis revealed good agreement of CRAE and CRVE as obtained from both images (mean bias CRAE = 0.88; CRVE = 2.82). Conclusions: Summarised retinal vessel calibre measurements obtained from oximetry images are in good agreement to those obtained using red-free photographs.

Effektivisering av mjukvaruinstallationer : Genom automatiserad mjukvarudistribution

Software deployment, eller mjukvarudistribution översatt till svenska kan ses som processen där alla aktiviteter ingår för att göra en mjukvara tillgänglig för användare utan en manuell installation på användarens dator eller annan maskin. Det finns ett flertal software deployment-verktyg, som hanterar automatiska installationer, tillgängliga för företag på marknaden idag.  Avdelningen HVDC på ABB i Ludvika har behov att börja använda ett verktyg för automatiserade installationer av mjukvaror då installationer idag utförs manuellt och är tidsödande. Som Microsoftpartners vill ABB se hur Microsofts verktyg för mjukvarudistribution skulle kunna hjälpa för detta behov.  Vår studie syftade till att undersöka hur arbetet med installationer av mjukvara ser ut idag, samt hitta förbättringsmöjligheter för installationer som inte kan automatiseras i nuläget. I studien ingick även att ta fram ett generellt ramverk för hur verksamheter kan gå tillväga när de vill börja använda sig utav software deployment-verktyg. I ramverket ingår en utformad kravspecifikation som ska utvärderas mot Microsofts verktyg.  För att skapa en uppfattning om hur arbetet i verksamheten ser ut idag har vi utfört enkätundersökning och intervjuer med personal på HVDC. För att utveckla ett ramverk har vi använt oss av insamlade data från de intervjuer, enkätundersökning och gruppintervju som utförts, detta för att identifiera krav och önskemål från personalen hos ett software deployment-verktyg. Litteraturstudier utfördes för att skapa en teoretisk referensram att utgå ifrån vid utvecklande av ramverket och kravspecifikationen.  Studien har resulterat i en beskrivning av software deployment, förbättringsmöjligheter i arbetet med installationer av mjukvara samt ett generellt ramverk som beskriver hur verksamheter kan gå tillväga när de ska börja använda ett software deployment-verktyg. Ramverket innehåller också en kravspecifikation som använts för att utvärdera Microsofts verktyg för mjukvarudistribution. I vår studie har vi inte sett att någon tidigare har tagit fram ett generellt ramverk och kravspecifikation som verksamheter kan använda sig av som underlag när de ska börja använda ett software deployment-verktyg. Vårt resultat av studien kan täcka upp detta kunskapsgap.    

Morphogenesis of the Arabidopsis Shoot Apical Meristem

Phyllotaxis patterns in plants, or the arrangement of leaves and flowers radially around the shoot, have fascinated both biologists and mathematicians for centuries. The current model of this process involves the lateral transport of the hormone auxin through the first layer of cells in the shoot apical meristem via the auxin efflux carrier protein PIN1. Locations around the meristem with high auxin concentration are sites of organ formation and differentiation. Many of the molecular players in this process are well known and characterized. Computer models composed of all these components are able to produce many of the observed phyllotaxis patterns. To understand which parts of this model have a large effect on the phenotype I automated parameter testing and tried many different parameter combinations. Results of this showed that cell size and meristem size should have the largest effect on phyllotaxis. This lead to three questions: (1) How is cell geometry regulated? (2) Does cell size affect auxin distribution? (3) Does meristem size affect phyllotaxis? To answer the first question I tracked cell divisions in live meristems and quantified the geometry of the cells and the division planes using advanced image processing techniques. The results show that cell shape is maintained by minimizing the length of the new wall and by minimizing the difference in area of the daughter cells. To answer the second question I observed auxin patterning in the meristem, shoot, leaves, and roots of Arabidopsis mutants with larger and smaller cell sizes. In the meristem and shoot, cell size plays an important role in determining the distribution of auxin. Observations of auxin in the root and leaves are less definitive. To answer the third question I measured meristem sizes and phyllotaxis patterns in mutants with altered meristem sizes. These results show that there is no correlation between meristem size and average divergence angle. But in an extreme case, making the meristem very small does lead to a switch on observed phyllotaxis in accordance with the model.

Safe and Collaborative Navigation & Interaction With Mobile Manipulators in Domestic Appliance Test Labs

Safe collaboration between a robot and human operator forms a critical requirement for deploying a robotic system into a manufacturing and testing environment. In this dissertation, the safety requirement for is developed and implemented for the navigation system of the mobile manipulators. A methodology for human-robot co-existence through a 3d scene analysis is also investigated. The proposed approach exploits the advance in computing capability by relying on graphic processing units (GPU’s) for volumetric predictive human-robot contact checking. Apart from guaranteeing safety of operators, human-robot collaboration is also fundamental when cooperative activities are required, as in appliance test automation floor. To achieve this, a generalized hierarchical task controller scheme for collision avoidance is developed. This allows the robotic arm to safely approach and inspect the interior of the appliance without collision during the testing procedure. The unpredictable presence of the operators also forms dynamic obstacle that changes very fast, thereby requiring a quick reaction from the robot side. In this aspect, a GPU-accelarated distance field is computed to speed up reaction time to avoid collision between human operator and the robot. An automated appliance testing also involves robotized laundry loading and unloading during life cycle testing. This task involves Laundry detection, grasp pose estimation and manipulation in a container, inside the drum and during recovery grasping. A wrinkle and blob detection algorithms for grasp pose estimation are developed and grasp poses are calculated along the wrinkle and blobs to efficiently perform grasping task. By ranking the estimated laundry grasp poses according to a predefined cost function, the robotic arm attempt to grasp poses that are more comfortable from the robot kinematic side as well as collision free on the appliance side. This is achieved through appliance detection and full-model registration and collision free trajectory execution using online collision avoidance.

TTCN testing of WCDMA base station operation and maintenance software

TTCN-kieltä käytetään testitapausten määrittelemiseen tietoliikennejärjestelmissä. Nykyään TTCN:stä on tullut yhä suositumpi tapa toteuttaa testitapauksia. TTCN tarjoaa hyvän ja yksinkertaisen tavan muuntaa käsin testattavat testitapaukset automatisoiduiksi. Tämän diplomityön yhteydessä toteutettiin TTCN testitapaukset WCDMA -tukiaseman käyttö- ja kunnossapito- (O&M) ohjelmistolle. Ohjelmistoa on käytetty myös toisen sukupolven tukiasemissa, mutta kolmannen sukupolven tukiasemissa sillä on huomattavasti isompi rooli. WCDMA -tukiasemassa O&M käsittelee muun muassa tukiaseman käynnistyksen, virhetilanteet ja valvoo tukiaseman komponentteja. Ensimmäisiä tehtäviä diplomityötä tehdessä oli valita ne testitapaukset, jotka olisivat mahdollisia ja hyödyllisiä toteuttaa TTCN:n avulla. Testitapaukset valittiin valmiina olleista testitapausten kuvauksista. Valitut testitapaukset toteutettiin käyttäen rinnakkaista ja modulaarista TTCN-kieltä ja testattiin WCDMA -tukiasemaa vasten käyttäen TTCN Tester ohjelmistoa. Tämän diplomityön yhteydessä toteutettuja testitapauksia käytetään varmistamaan, että tukiasema voi toipua erilaisista virhetilanteista O&M ohjelmiston avulla. Testitapauksia WCDMA -tukiasemaa vasten ajettaessa varmistetaan myös, että O&M ohjelmisto toimii määrittelyn mukaisesti eri tilanteissa. Toteutetut testi tapaukset korvaavat nykyään käsin testatut O&M testi tapaukset tukiaseman O&M ohjelmistoa testatessa. Automatisoidut testi tapaukset tekevät O&M ohjelmiston testaamisen merkittävästi nopeammaksi ja helpommaksi.

A self -testing approach for autonomic software

As researchers and practitioners move towards a vision of software systems that configure, optimize, protect, and heal themselves, they must also consider the implications of such self-management activities on software reliability. Autonomic computing (AC) describes a new generation of software systems that are characterized by dynamically adaptive self-management features. During dynamic adaptation, autonomic systems modify their own structure and/or behavior in response to environmental changes. Adaptation can result in new system configurations and capabilities, which need to be validated at runtime to prevent costly system failures. However, although the pioneers of AC recognize that validating autonomic systems is critical to the success of the paradigm, the architectural blueprint for AC does not provide a workflow or supporting design models for runtime testing. ^ This dissertation presents a novel approach for seamlessly integrating runtime testing into autonomic software. The approach introduces an implicit self-test feature into autonomic software by tailoring the existing self-management infrastructure to runtime testing. Autonomic self-testing facilitates activities such as test execution, code coverage analysis, timed test performance, and post-test evaluation. In addition, the approach is supported by automated testing tools, and a detailed design methodology. A case study that incorporates self-testing into three autonomic applications is also presented. The findings of the study reveal that autonomic self-testing provides a flexible approach for building safe, reliable autonomic software, while limiting the development and performance overhead through software reuse. ^