Nesta tese, introduzimos o conceito de sequência convergente de permutações e provamos a existência de um objeto limite para tais sequências. Introduzimos ainda um novo modelo de permutação aleatória baseado em tais objetos e introduzimos um conceito novo de distância entre permutações. Provamos então que sequências de permutações aleatórias são convergentes e provamos a equivalência entre esta noção de convergência e convergência nesta nova distância. Obtemos ainda resultados de amostragem e quase-aleatoriedade para permutações. Provamos também uma caracterização para parâmetros testáveis de permutações. / We introduce the concept of convergent sequence of permutations and we prove the existence of a limit object for these sequences. We also introduce a new and more general model of random permutation based on these limit objects and we introduce a new metric for permutations. We also prove that sequences of random permutations are convergent and we prove the equivalence between this notion of convergence and convergence in this new metric. We also show some applications for samplig and quasirandomness. We also prove a characterization for testable parameters of permutations.

Teste de Software tem o objetivo de executar um programa sob teste com o objetivo de revelar suas falhas, portanto é uma das fases mais importante do ciclo de vida do desenvolvimento de um software. A testabilidade é um atributo de qualidade fundamental para o sucesso da atividade de teste, pois ela pode ser entendida como o esforço necessário para criar, executar e avaliar os casos de teste em um software. Este atributo não é uma qualidade intrínseca do software, portanto não pode ser medido diretamente como a quantidade de linhas de código, por exemplo. Entretanto, ela pode ser inferida por meio das características ou métricas internas e externas de um software. Entre as características comumente utilizadas na análise da testabilidade estão as métricas CK, que foram propostas por Chidamber e Kemerer com objetivo de analisar software orientado a objetos. A maioria dos trabalhos nesta linha, entretanto, relaciona o tamanho e a quantidade de casos testes com a testabilidade de um software. Entretanto, é fundamental analisar a qualidade dos testes para saber se eles atingem os objetivos para os quais foram propostos, independente de quantidade e tamanho. Portanto, este trabalho de mestrado apresenta um estudo empírico sobre a relação entre as métricas CK e a testabilidade de um software com base na análise da adequação de seus casos de teste unitários, critérios de teste estrutural e de mutação. Inicialmente foi realizada uma Revisão Sistemática cujo objetivo foi avaliar o estado da arte da testabilidade e as métricas CK. Os resultados mostraram que apesar de existirem várias pesquisas relacionadas ao tema, existem lacunas que motivam novas pesquisas no que concerne a análise da qualidade dos testes e identificação das características das métricas que podem ser inferidas para medir e analisar a testabilidade. Em seguida, foram realizadas duas análises empíricas. Na primeira análise, as métricas foram analisadas por meio da correlação das métricas CK com a cobertura de linha de código, cobertura de \\textit (arestas, ramos ou desvio de fluxo) e escore de mutação. Os resultados desta análise demonstraram a importância de cada métrica dentro do contexto da testabilidade. Na segunda análise, foi realizada uma proposta de clusterização das métricas para tentar identificar grupos de classes com características semelhantes relacionadas à testabilidade. Além das análises empíricas, foi desenvolvida e apresentada uma ferramenta de coleta e análise de métricas CK com objetivo de contribuir com novas pesquisas relacionados a proposta deste projeto. Apesar das limitações das análises, os resultados deste trabalho mostraram a importância de cada métrica CK dentro do contexto da testabilidade e fornece aos desenvolvedores e projetistas uma ferramenta de apoio e dados empíricos para melhor desenvolverem e projetarem seus sistemas com o objetivo de facilitar a atividade de teste de software / Software testing have aim to run a program under test with the aim of revealing its failures, so it is one of the most important phases of the software development lifecycle. Testability is a key quality attribute for the success of the test activity, because it can be understood as the effort required to create, execute and evaluate test cases in software. This attribute is not an intrinsic quality of the software, so it can not be measured directly as the number of lines code, for example. However, it can be inferred through the or internal and external metrics of a software. Among the features commonly used in testability analysis are CK metrics, which were proposed by Chidamber and Kemerer in order to analyze object-oriented software. Most of the works in this line, however, relate the size and quantity of test cases with software testability. However, it\'s critical to analyze the quality of the tests to see if they achieve the objectives for which they were proposed, independent of quantity and size. Therefore, this Master\'s degree work presents an empirical study on the relationship between CK metrics and software testability based on the analysis of the adequacy of its unit test cases, structural test criteria and mutation. Initially, a Systematic Review was carried out to evaluate the state of the art of testability and CK metrics. The results showed that although there are several researches related to the subject, there are gaps that motivate new research in what concerns the analysis of the quality of the tests and identification of the features of the metrics that can be inferred to measure and analyze the testability. Two empirical analyzes were performed. In the first analysis, the metrics were analyzed through the correlation of the CK metrics with the code line coverage, branch coverage or mutation score. The results of this analysis showed the importance of each metric within the context of testability. In the second analysis, a metric clustering proposal was made to try to identify groups of classes with similar features related to testability. In addition to the empirical analysis, a tool for the collection and analysis of CK metrics was developed and presented, with aim to contribute with new researches related to the proposal of this project. Despite the limitations of the analyzes, the results of this work showed the importance of each CK metric within the context of testability and provides developers and designers with a support tool and empirical data to better develop and design their systems with the aim of facilitate the activity of software testing

Nesta tese, introduzimos o conceito de sequência convergente de permutações e provamos a existência de um objeto limite para tais sequências. Introduzimos ainda um novo modelo de permutação aleatória baseado em tais objetos e introduzimos um conceito novo de distância entre permutações. Provamos então que sequências de permutações aleatórias são convergentes e provamos a equivalência entre esta noção de convergência e convergência nesta nova distância. Obtemos ainda resultados de amostragem e quase-aleatoriedade para permutações. Provamos também uma caracterização para parâmetros testáveis de permutações. / We introduce the concept of convergent sequence of permutations and we prove the existence of a limit object for these sequences. We also introduce a new and more general model of random permutation based on these limit objects and we introduce a new metric for permutations. We also prove that sequences of random permutations are convergent and we prove the equivalence between this notion of convergence and convergence in this new metric. We also show some applications for samplig and quasirandomness. We also prove a characterization for testable parameters of permutations.

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-05-21T13:19:36Z No. of bitstreams: 1 FELIPE_AUGUSTO_KUENTZER_TES.pdf: 3277301 bytes, checksum: 7e77c5eb72299302d091329bde56b953 (MD5) / Approved for entry into archive by Sheila Dias (sheila.dias@pucrs.br) on 2018-06-01T12:13:22Z (GMT) No. of bitstreams: 1 FELIPE_AUGUSTO_KUENTZER_TES.pdf: 3277301 bytes, checksum: 7e77c5eb72299302d091329bde56b953 (MD5) / Made available in DSpace on 2018-06-01T12:33:57Z (GMT). No. of bitstreams: 1 FELIPE_AUGUSTO_KUENTZER_TES.pdf: 3277301 bytes, checksum: 7e77c5eb72299302d091329bde56b953 (MD5) Previous issue date: 2018-03-28 / ? medida que o projeto de VLSI avan?a para tecnologias ultra submicron, as margens de atraso adicionadas para compensar variabilidades de processo de fabrica??o, temperatura de opera??o e tens?o de alimenta??o, tornam-se uma parte significativa do per?odo de rel?gio em circuitos s?ncronos tradicionais. As arquiteturas resilientes a varia??es de atraso surgiram como uma solu??o promissora para aliviar essas margens de tempo projetadas para o pior caso, melhorando o desempenho do sistema e reduzindo o consumo de energia. Essas arquiteturas incorporam circuitos adicionais para detec??o e recupera??o de viola??es de atraso que podem surgir ao projetar o circuito com margens de tempo menores. Os sistemas ass?ncronos apresentam potencial para melhorar a efici?ncia energ?tica e o desempenho devido ? aus?ncia de um sinal de rel?gio global. Al?m disso, os circuitos ass?ncronos s?o conhecidos por serem robustos a varia??es de processo, tens?o e temperatura. Blade ? um modelo que incorpora as vantagens de projeto ass?ncrono e resilientes a varia??es de atraso. No entanto, o Blade ainda apresenta desafios em rela??o ? sua testabilidade, o que dificulta sua aplica??o comercial ou em larga escala. Embora o projeto visando testabilidade com Scan seja amplamente utilizado na ind?stria, os altos custos de sil?cio associados com o seu uso no Blade podem ser proibitivos. Por outro lado, os circuitos ass?ncronos podem apresentar vantagens para testes funcionais, enquanto o circuito resiliente fornece feedback cont?nuo durante o funcionamento normal do circuito, uma caracter?stica que pode ser aplicada para testes concorrentes. Nesta Tese, a testabilidade do Blade ? avaliada sob uma perspectiva diferente, onde o circuito implementado com o Blade apresenta propriedades de confiabilidade que podem ser exploradas para testes. Inicialmente, um m?todo de classifica??o de falhas que relaciona padr?es comportamentais com falhas estruturais dentro da l?gica de detec??o de erro e uma nova implementa??o orientada para teste desse m?dulo de detec??o s?o propostos. A parte de controle ? analisada para falhas internas, e um novo projeto ? proposto, onde o teste ? melhorado e o circuito pode ser otimizado pelo fluxo de projeto. Um m?todo original de medi??o de tempo das linhas de atraso tamb?m ? abordado. Finalmente, o teste de falhas de atrasos em caminhos cr?ticos do caminho de dados ? explorado como uma consequ?ncia natural de um circuito implementado com Blade, onde o monitoramento cont?nuo para detec??o de viola??es de atraso fornece a informa??o necess?ria para a detec??o concorrente de viola??es que extrapolam a capacidade de recupera??o do circuito resiliente. A integra??o de todas as contribui??es fornece uma cobertura de falha satisfat?ria para um custo de ?rea que, para os circuitos avaliados nesta Tese, pode variar de 4,24% a 6,87%, enquanto que a abordagem Scan para os mesmos circuitos apresenta custo que varia de 50,19% a 112,70% em ?rea, respectivamente. As contribui??es desta Tese demonstraram que, com algumas melhorias na arquitetura do Blade, ? poss?vel expandir sua confiabilidade para al?m de um sistema de toler?ncia a viola??es de atraso no caminho de dados, e tamb?m um avan?o para teste de falhas (inclusive falhas online) de todo o circuito, bem como melhorar seu rendimento, e lidar com quest?es de envelhecimento. / As the VLSI design moves into ultra-deep-submicron technologies, timing margins added due to variabilities in the manufacturing process, operation temperature and supply voltage become a significant part of the clock period in traditional synchronous circuits. Timing resilient architectures emerged as a promising solution to alleviate these worst-case timing margins, improving system performance and/or reducing energy consumption. These architectures embed additional circuits for detecting and recovering from timing violations that may arise after designing the circuit with reduced time margins. Asynchronous systems, on the other hand, have a potential to improve energy efficiency and performance due to the absence of a global clock. Moreover, asynchronous circuits are known to be robust to process, voltage and temperature variations. Blade is an asynchronous timing resilient template that leverages the advantages of both asynchronous and timing resilient techniques. However, Blade still presents challenges regarding its testability, which hinders its commercial or large-scale application. Although the design for testability with scan chains is widely applied in the industry, the high silicon costs associated with its use in Blade can be prohibitive. Asynchronous circuits can also present advantages for functional testing, and the timing resilient characteristic provides continuous feedback during normal circuit operation, which can be applied for concurrent testing. In this Thesis, Blade?s testability is evaluated from a different perspective, where circuits implemented with Blade present reliability properties that can be explored for stuck-at and delay faults testing. Initially, a fault classification method that relates behavioral patterns with structural faults inside the error detection logic and a new test-driven implementation of this detection module are proposed. The control part is analyzed for internal faults, and a new design is proposed, where the test coverage is improved and the circuit can be further optimized by the design flow. An original method for time measuring delay lines is also addressed. Finally, delay fault testing of critical paths in the data path is explored as a natural consequence of a Blade circuit, where the continuous monitoring for detecting timing violations provide the necessary feedback for online detection of these delay faults. The integration of all the contributions provides a satisfactory fault coverage for an area overhead that, for the evaluated circuits in this thesis, can vary from 4.24% to 6.87%, while the scan approach for the same circuits implies an area overhead varying from 50.19% to 112.70%, respectively. The contributions of this Thesis demonstrated that with a few improvements in the Blade architecture it is possible to expand its reliability beyond a timing resilient system to delay violations in the data path, but also advances for fault testing (including online faults) of the entire circuit, yield, and aging.