• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 25
  • 9
  • 8
  • 5
  • 4
  • 1
  • 1
  • Tagged with
  • 65
  • 65
  • 27
  • 16
  • 15
  • 15
  • 14
  • 13
  • 12
  • 11
  • 10
  • 10
  • 10
  • 9
  • 8
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.

Improving Bio-Inspired Frameworks

Varadarajan, Aravind Krishnan 05 October 2018 (has links)
In this thesis, we provide solutions to two different bio-inspired algorithms. The first is enhancing the performance of bio-inspired test generation for circuits described in RTL Verilog, specifically for branch coverage. We seek to improve upon an existing framework, BEACON, in terms of performance. BEACON is an Ant Colony Optimization (ACO) based test generation framework. Similar to other ACO frameworks, BEACON also has a good scope in improving performance using parallel computing. We try to exploit the available parallelism using both multi-core Central Processing Units (CPUs) and Graphics Processing Units(GPUs). Using our new multithreaded approach we can reduce test generation time by a factor of 25 — compared to the original implementation for a wide variety of circuits. We also provide a 2-dimensional factoring method for BEACON to improve available parallelism to yield some additional speedup. The second bio-inspired algorithm we address is for Deep Neural Networks. With the increasing prevalence of Neural Nets in artificial intelligence and mission-critical applications such as self-driving cars, questions arise about its reliability and robustness. We have developed a test-generation based technique and metric to evaluate the robustness of a Neural Nets outputs based on its sensitivity to its inputs. This is done by generating inputs which the neural nets find difficult to classify but at the same time is relatively apparent to human perception. We measure the degree of difficulty for generating such inputs to calculate our metric. / MS / High-level Hardware Design Languages (HDLs) has allowed designers to implement complicated hardware designs with considerably lesser effort. Unfortunately, design verification for the same circuits has failed to scale gracefully in terms of time and effort. Not only has it become more difficult for formal methods due to exponential complexity from increasing path explosion, but concrete test generation frameworks also face new issues such as the increased requirement in the volume of simulations. The advent of parallel computing using General Purpose Graphics Processing Units (GPGPUs) has led to improved performance for various applications. We propose to leverage both the multi-core CPU and the GPGPU for RTL test generation. This is achieved by implementing a test generation framework that can utilize the SIMD type parallelism available in GPGPUs and task level parallelism available on CPUs. The speedup achieved is extracted from both the test generation framework itself and also from refactoring the hardware model for multi-threaded test generation. For this purpose, we translate the RTL Verilog to a C++ and a CUDA compilable program. Experimental results show that considerable speedup can be achieved for test generation without loss of coverage. In recent years, machine learning and artificial intelligence have taken a substantial leap forward with the discovery of Deep Neural Networks(DNN). Unfortunately, apart from Accuracy and FTest numbers, there exist very few metrics to qualify a DNN. This becomes a reliability issue as DNNs are quite frequently used in safety-critical applications. It is difficult to interpret how the parameters of a trained DNN help store the knowledge from the training inputs. Therefore it is also difficult to infer whether a DNN has learned parameters which might cause an output neuron to misfire wrongly, a bug. An exhaustive search of the input space of the DNN is not only infeasible but is also misleading. Thus, in our work, we try to apply test generation techniques to generate new test inputs based on existing training and testing set to qualify the underlying robustness. Attempts to generate these inputs are guided only by the prediction probability values at the final output layer. We observe that depending on the amount of perturbation and time needed to generate these inputs we can differentiate between DNNs of varying quality.

Search State Extensibility based Learning Framework for Model Checking and Test Generation

Chandrasekar, Maheshwar 20 September 2010 (has links)
The increasing design complexity and shrinking feature size of hardware designs have created resource intensive design verification and manufacturing test phases in the product life-cycle of a digital system. On the contrary, time-to-market constraints require faster verification and test phases; otherwise it may result in a buggy design or a defective product. This trend in the semiconductor industry has considerably increased the complexity and importance of Design Verification, Manufacturing Test and Silicon Diagnosis phases of a digital system production life-cycle. In this dissertation, we present a generalized learning framework, which can be customized to the common solving technique for problems in these three phases. During Design Verification, the conformance of the final design to its specifications is verified. Simulation-based and Formal verification are the two widely known techniques for design verification. Although the former technique can increase confidence in the design, only the latter can ensure the correctness of a design with respect to a given specification. Originally, Design Verification techniques were based on Binary Decision Diagram (BDD) but now such techniques are based on branch-and-bound procedures to avoid space explosion. However, branch-and-bound procedures may explode in time; thus efficient heuristics and intelligent learning techniques are essential. In this dissertation, we propose a novel extensibility relation between search states and a learning framework that aids in identifying non-trivial redundant search states during the branch-and-bound search procedure. Further, we also propose a probability based heuristic to guide our learning technique. First, we utilize this framework in a branch-and-bound based preimage computation engine. Next, we show that it can be used to perform an upper-approximation based state space traversal, which is essential to handle industrial-scale hardware designs. Finally, we propose a simple but elegant image extraction technique that utilizes our learning framework to compute over-approximate image space. This image computation is later leveraged to create an abstraction-refinement based model checking framework. During Manufacturing Test, test patterns are applied to the fabricated system, in a test environment, to check for the existence of fabrication defects. Such patterns are usually generated by Automatic Test Pattern Generation (ATPG) techniques, which assume certain fault types to model arbitrary defects. The size of fault list and test set has a major impact on the economics of manufacturing test. Towards this end, we propose a fault col lapsing approach to compact the size of target fault list for ATPG techniques. Further, from the very beginning, ATPG techniques were based on branch-and-bound procedures that model the problem in a Boolean domain. However, ATPG is a problem in the multi-valued domain; thus we propose a multi-valued ATPG framework to utilize this underlying nature. We also employ our learning technique for branch-and-bound procedures in this multi-valued framework. To improve the yield for high-volume manufacturing, silicon diagnosis identifies a set of candidate defect locations in a faulty chip. Subsequently physical failure analysis - an extremely time consuming step - utilizes these candidates as an aid to locate the defects. To reduce the number of candidates returned to the physical failure analysis step, efficient diagnostic patterns are essential. Towards this objective, we propose an incremental framework that utilizes our learning technique for a branch-and-bound procedure. Further, it learns from the ATPG phase where detection-patterns are generated and utilizes this information during diagnostic-pattern generation. Finally, we present a probability based heuristic for X-filling of detection-patterns with the objective of enhancing the diagnostic resolution of such patterns. We unify these techniques into a framework for test pattern generation with good detection and diagnostic ability. Overall, we propose a learning framework that can speed up design verification, test and diagnosis steps in the life cycle of a hardware system. / Ph. D.

Test generation and animation based on object-oriented specifications.

Krieger, Matthias 09 December 2011 (has links) (PDF)
The goal of this thesis is the development of support for test generation and animation based on object-oriented specifications. We aim particularly to take advantage of state-of-the-art satisfiability solving techniques by using an appropriate representation of object-oriented data. While automated test generation seeks a large set of data to execute an implementation on, animation performs computations that comply with a specification based on user-provided input data. Animation is a valuable technique for validating specifications.As a foundation of this work, we present clarifications and a partial formalization of the Object Constraint Language (OCL) as well as some extensions in order to allow for test generation and animation based on OCL specifications.For test generation, we have implemented several enhancements to HOL-TestGen, a tool built on top of the Isabelle theorem proving system that generates tests from specifications in Higher-Order Logic (HOL). We show how SMT solvers can be used to solve various types of constraints in HOL and present a modular approach to case splitting for deriving test cases. The latter facilitates the introduction of splitting rules that are tailored to object-oriented specifications.For animation, we implemented the tool OCLexec for animating OCL specifications. OCLexec generates from operation contracts corresponding Java implementations that call an SMT-based constraint solver at runtime.

Evaluation of Model-Based Testing on a Base Station Controller

Trimmel, Stefan January 2008 (has links)
<p>This master thesis investigates how well suited the model-based testing process is for testing a new feature of a Base Station Controller. In model-based testing the tester designs a behavioral model of the system under test, or some part of the system. This model is then given to a test generation tool that will analyze the model and produce interesting test cases. These test cases can either be run on the system in an automatic or manual way depending on what type of setup there is.</p><p>In this report it is suggested that the behavioral model should be produced in as early a stage as possible and that it should be a collaboration between the test team and the design team.</p><p>The advantages with the model-based testing process are a better overview of the test cases, the test cases are always up to date, it helps in finding errors or contradictions in requirements and it performs closer collaboration between the test team and the design team. The disadvantages with model-based testing process are that it introduces more sources where an error can occur. The behavioral model can have errors, the layer between the model and the generated test cases can have errors and the layer between the test cases and the system under test can have errors. This report also indicates that the time needed for testing will be longer compared with manual testing.</p><p>During the pilot, when a part of a new feature was tested, of this master thesis a test generation tool called Qtronic was used. This tool solves a very challenging task which is generating test cases from a general behavioral model and with a good result. This tool provides many good things but it also has its shortages. One of the biggest shortages is the debugging of the model for finding errors. This step is very time consuming because it requires that a test case generation is performed on the whole model. When there is a fault in the model then this test generation can take very long time, before the tool decides that it is impossible to cover the model.</p><p>Under the circumstances that the Qtronic tool is improved on varies issues suggested in the thesis, one of the most important issues is to do something about the long debugging time needed, then the next step can be to use model-based testing in a larger evaluation project at BSC Design, Ericsson.</p>

Alternate Test Generation for Detection of Parametric Faults

Gomes, Alfred Vincent 26 November 2003 (has links)
Tests for detecting faults in analog and mixed-signal circuits have been traditionally derived from the datasheet speci and #64257;cations. Although these speci and #64257;cations describe important aspects of the device, in many cases these application oriented tests are costly to implement and are inefficient in determining product quality. Increasingly, the gap between speci and #64257;cation test requirements and the capabilities of test equipment has been widening. In this work, a systematic method to generate and evaluate alternate tests for detecting parametric faults is proposed. We recognize that certain aspects of analog test generation problem are not amenable to automation. Additionally, functional features of analog circuits are widely varied and cannot be assumed by the test generator. To overcome these problems, an extended device under test (DUT) model is developed that encapsulates the DUT and the DUT speci and #64257;c tasks. The interface of this model provides a well de and #64257;ned and uniform view of a large class of devices. This permits several simpli and #64257;cations in the test generator. The test generator is uses a search-based procedure that requires evaluation of a large number of candidate tests. Test evaluation is expensive because of complex fault models and slow fault simulation techniques. A tester-resident test evaluation technique is developed to address this issue. This method is not limited by simulation complexity nor does it require an explicit fault model. Making use of these two developments, an efficient and automated test generation method is developed. Theoretical development and a number of examples are used to illustrate various concepts that are presented in this thesis.

Classification de menaces d’erreurs par analyse statique, simplification syntaxique et test structurel de programmes / Classification of errors threats by static analysis, program sclicing and structural testing of programs

Chebaro, Omar 13 December 2011 (has links)
La validation des logiciels est une partie cruciale dans le cycle de leur développement. Deux techniques de vérification et de validation se sont démarquées au cours de ces dernières années : l’analyse statique et l’analyse dynamique. Les points forts et faibles des deux techniques sont complémentaires. Nous présentons dans cette thèse une combinaison originale de ces deux techniques. Dans cette combinaison, l’analyse statique signale les instructions risquant de provoquer des erreurs à l’exécution, par des alarmes dont certaines peuvent être de fausses alarmes, puis l’analyse dynamique (génération de tests) est utilisée pour confirmer ou rejeter ces alarmes. L’objectif de cette thèse est de rendre la recherche d’erreurs automatique, plus précise, et plus efficace en temps. Appliquée à des programmes de grande taille, la génération de tests, peut manquer de temps ou d’espace mémoire avant de confirmer certaines alarmes comme de vraies erreurs ou conclure qu’aucun chemin d’exécution ne peut atteindre l’état d’erreur de certaines alarmes et donc rejeter ces alarmes. Pour surmonter ce problème, nous proposons de réduire la taille du code source par le slicing avant de lancer la génération de tests. Le slicing transforme un programme en un autre programme plus simple, appelé slice, qui est équivalent au programme initial par rapport à certains critères. Quatre utilisations du slicing sont étudiées. La première utilisation est nommée all. Elle consiste à appliquer le slicing une seule fois, le critère de simplification étant l’ensemble de toutes les alarmes du programme qui ont été détectées par l’analyse statique. L’inconvénient de cette utilisation est que la génération de tests peut manquer de temps ou d’espace et les alarmes les plus faciles à classer sont pénalisées par l’analyse d’autres alarmes plus complexes. Dans la deuxième utilisation, nommée each, le slicing est effectué séparément par rapport à chaque alarme. Cependant, la génération de tests est exécutée pour chaque programme et il y a un risque de redondance d’analyse si des alarmes sont incluses dans d’autres slices. Pour pallier ces inconvénients, nous avons étudié les dépendances entre les alarmes et nous avons introduit deux utilisations avancées du slicing, nommées min et smart, qui exploitent ces dépendances. Dans l’utilisation min, le slicing est effectué par rapport à un ensemble minimal de sous-ensembles d’alarmes. Ces sous-ensembles sont choisis en fonction de dépendances entre les alarmes et l’union de ces sous-ensembles couvre l’ensemble de toutes les alarmes. Avec cette utilisation, on a moins de slices qu’avec each, et des slices plus simples qu’avec all. Cependant, l’analyse dynamique de certaines slices peut manquer de temps ou d’espace avant de classer certaines alarmes, tandis que l’analyse dynamique d’une slice éventuellement plus simple permettrait de les classer. L’utilisation smart consiste à appliquer l’utilisation précédente itérativement en réduisant la taille des sous-ensembles quand c’est nécessaire. Lorsqu’une alarme ne peut pas être classée par l’analyse dynamique d’une slice, des slices plus simples sont calculées. Nous prouvons la correction de la méthode proposée. Ces travaux sont implantés dans sante, notre outil qui relie l’outil de génération de tests PathCrawler et la plate-forme d’analyse statique Frama-C. Des expérimentations ont montré, d’une part, que notre combinaison est plus performante que chaque technique utilisée indépendamment et, d’autre part, que la vérification devient plus rapide avec l’utilisation du slicing. De plus, la simplification du programme par le slicing rend les erreurs détectées et les alarmes restantes plus faciles à analyser / Software validation remains a crucial part in software development process. Two major techniques have improved in recent years, dynamic and static analysis. They have complementary strengths and weaknesses. We present in this thesis a new original combination of these methods to make the research of runtime errors more accurate, automatic and reduce the number of false alarms. We prove as well the correction of the method. In this combination, static analysis reports alarms of runtime errors some of which may be false alarms, and test generation is used to confirm or reject these alarms. When applied on large programs, test generation may lack time or space before confirming out certain alarms as real bugs or finding that some alarms are unreachable. To overcome this problem, we propose to reduce the source code by program slicing before running test generation. Program slicing transforms a program into another simpler program, which is equivalent to the original program with respect to certain criterion. Four usages of program slicing were studied. The first usage is called all. It applies the slicing only once, the simplification criterion is the set of all alarms in the program. The disadvantage of this usage is that test generation may lack time or space and alarms that are easier to classify are penalized by the analysis of other more complex alarms. In the second usage, called each, program slicing is performed with respect to each alarm separately. However, test generation is executed for each sliced program and there is a risk of redundancy if some alarms are included in many slices. To overcome these drawbacks, we studied dependencies between alarms on which we base to introduce two advanced usages of program slicing : min and smart. In the min usage, the slicing is performed with respect to subsets of alarms. These subsets are selected based on dependencies between alarms and the union of these subsets cover the whole set of alarms. With this usage, we analyze less slices than with each, and simpler slices than with all. However, the dynamic analysis of some slices may lack time or space before classifying some alarms, while the dynamic analysis of a simpler slice could possibly classify some. Usage smart applies previous usage iteratively by reducing the size of the subsets when necessary. When an alarm cannot be classified by the dynamic analysis of a slice, simpler slices are calculated. These works are implemented in sante, our tool that combines the test generation tool PathCrawler and the platform of static analysis Frama-C. Experiments have shown, firstly, that our combination is more effective than each technique used separately and, secondly, that the verification is faster after reducing the code with program slicing. Simplifying the program by program slicing also makes the detected errors and the remaining alarms easier to analyze

Vienetų testų generavimo metodo Android aplikacijoms testuoti realizavimas ir tyrimas / Implementation and research of unit tests generation method for testing Android applications

Babenskas, Egidijus 31 October 2013 (has links)
Tobulėjant išmaniesiems telefonams ir jų techninėms galimybėms bei didėjant jų pardavimams Lietuvoje ir pasaulyje, kuriamos aplikacijos tampa sudėtingesnės ir funkcionalesnės, tačiau kokybės problema vis dar išlieka skaudžia programinės įrangos kūrimo dalimi. Šiuo metu iš visų parduodamų išmaniųjų telefonų apie 50% parduodami su Android operacine sistema. Matant Android OS programų vis didėjantį poreikį rinkoje ir jų populiarumą bei panagrinėjus esamą rinką ir pamačius, jog testavimo įrankių, skirtų testuoti Android aplikacijas, beveik nėra, buvo nuspręsta, jog reikalingas vienetų testų generavimo sprendimas pritaikytas testuoti Android aplikacijas. Šio darbo pagrindinis tikslas ir yra pateikti vienetų testų generavimo sprendimą skirtą Android OS aplikacijos testuoti, jį realizuoti bei pagrįsti eksperimentiškai. Darbe siūlomas vienetų testų generavimo metodas, kuris remiasi atsitiktiniu generavimu, naudoja OCL apribojimus bei regresinio testavimo principus. Taip pat yra suderinamas su Google kompanijos teikiamu ADT įskiepiu ir Android SDK priemonėmis. Įrankis sukurtas kaip Eclipse programavimo aplinkos įskiepis. Pasiūlyto vienetų testų generavimo sprendimo efektyvumas įrodomas eksperimentiniu tyrimu. Šio eksperimento metu buvo testuojamos 4 aplikacijos. Naudojantis įrankiu vidutiniškai sugautų mutantų skaičius yra 75%. Mažiausia reikšmė yra 69%, o didžiausia – 88%. Vidutiniškai pasiekiamas 85% kodo eilučių padengimas. Mažiausia reikšmė yra 72%, o didžiausia padengimo... [toliau žr. visą tekstą] / With the development of smart phones and their technical capabilities and increase of their sales in Lithuania and the world applications become more complex and have more functionality, but the issue of quality remains a painful part of the development of software. Currently 50% out of all smart phones are sold with Android operating system. Having an increasing demand and popularity of Android OS applications in the market, as well as having researched the current market and seen that there is a lack of testing tools to test Android applications, it has been decided that a solution generating unit tests is needed to test Android applications. The main goal of this work is to provide unit test generation solution for the Android OS application testing, implementation and validate it experimentally. This work proposes a method generating unit tests based on random generation, using OCL constraints and regression testing principles. It is compatible with Google plug-in ADT and Android SDK tools. The tool is designed as a plugin in Eclipse development environment. Efficiency of the proposed decision of generating unit tests is proved by experimental study. During this study four applications were tested. Using the tool the average of catched mutants is 75%. The minimum value is 69%, while the highest - 88%. On average coverage of code lines is achieved by 85%. The minimum value is 72% and the maximum value of coverage - 97%.

Pseudofunctional Delay Tests For High Quality Small Delay Defect Testing

Lahiri, Shayak 2011 December 1900 (has links)
Testing integrated circuits to verify their operating frequency, known as delay testing, is essential to achieve acceptable product quality. The high cost of functional testing has driven the industry to automatically-generated structural tests, applied by low-cost testers taking advantage of design-for-test (DFT) circuitry on the chip. Traditional at-speed functional testing of digital circuits is increasingly challenged by new defect types and the high cost of functional test development. This research addressed the problems of accurate delay testing in DSM circuits by targeting resistive open and short circuits, while taking into account manufacturing process variation, power dissipation and power supply noise. In this work, we developed a class of structural delay tests in which we extended traditional launch-on-capture delay testing to additional launch and capture cycles. We call these Pseudofunctional Tests (PFT). A test pattern is scanned into the circuit, and then multiple functional clock cycles are applied to it with at-speed launch and capture for the last two cycles. The circuit switching activity over an extended period allows the off-chip power supply noise transient to die down prior to the at-speed launch and capture, achieving better timing correlation with the functional mode of operation. In addition, we also proposed advanced compaction methodologies to compact the generated test patterns into a smaller test set in order to reduce the test application time. We modified our CodGen K longest paths per gate automatic test pattern generator to implement PFT pattern generation. Experimental results show that PFT test generation is practical in terms of test generation time.

Efficient state space exploration for parallel test generation

Ramasamy Kandasamy, Manimozhian 03 September 2009 (has links)
Automating the generation of test cases for software is an active area of research. Specification based test generation is an approach in which a formal representation of a method is analyzed to generate valid test cases. Constraint solving and state space exploration are important aspects of the specification based test generation. One problem with specification based testing is that the size of the state space explodes when we apply this approach to a code of practical size. Hence finding ways to reduce the number of candidates to explore within the state space is important to make this approach practical in industry. Korat is a tool which generates test cases for Java programs based on predicates that validate the inputs to the method. Various ongoing researches intend to increase the tools effectiveness in handling large state space. Parallelizing Korat and minimizing the exploration of invalid candidates are the active research directions. This report surveys the basic algorithms of Korat, PKorat, and Fast Korat. PKorat is a parallel version of Korat and aims to take advantage of multi-processor and multicore systems available. Fast Korat implements four optimizations which reduce the number of candidate explored to generate validate candidates and reduce the amount of time required to explore each candidate. This report also presents the execution time results for generating test candidates for binary tree, doubly linked list, and sorted singly linked list, from their respective predicates. / text

Génération automatique de tests unitaires avec Praspel, un langage de spécification pour PHP / The art of contract-based testiong in PHP with Praspel

Enderlin, Ivan 16 July 2014 (has links)
Les travaux présentés dans ce mémoire portent sur la validation de programmes PHP à travers un nouveau langage de spécification, accompagné de ses outils. Ces travaux s’articulent selon trois axes : langage de spécification, génération automatique de données de test et génération automatique de tests unitaires.La première contribution est Praspel, un nouveau langage de spécification pour PHP, basé sur la programmation par contrat. Praspel spécifie les données avec des domaines réalistes, qui sont des nouvelles structures permettant de valider etgénérer des données. À partir d’un contrat écrit en Praspel, nous pouvons faire du Contract-based Testing, c’est à dire exploiter les contrats pour générer automatiquement des tests unitaires. La deuxième contribution concerne la génération de données de test. Pour les booléens, les entiers et les réels, une génération aléatoire uniforme est employée. Pour les tableaux, un solveur de contraintes a été implémenté et utilisé. Pour les chaînes de caractères, un langage de description de grammaires avec un compilateur de compilateurs LL(⋆) et plusieurs algorithmes de génération de données sont employés. Enfin, la génération d’objets est traitée.La troisième contribution définit des critères de couverture sur les contrats.Ces derniers fournissent des objectifs de test. Toutes ces contributions ont été implémentées et expérimentées dans des outils distribués à la communauté PHP. / The works presented in this memoir are about the validation of PHPprograms through a new specification language, along with its tools. These works follow three axes: specification language, automatic test data generation and automatic unit test generation. The first contribution is Praspel, a new specification language for PHP, based on the Design by Contract. Praspel specifies data with realistic domains, which are new structures allowing to validate and generate data. Based on a contract, we are able to perform Contract-based Testing, i.e.using contracts to automatically generate unit tests. The second contribution isabout test data generation. For booleans, integers and floating point numbers, auniform random generation is used. For arrays, a dedicated constraint solver has been implemented and used. For strings, a grammar description language along with an LL(⋆) compiler compiler and several algorithms for data generation are used. Finally, the object generation is supported. The third contribution defines contract coverage criteria. These latters provide test objectives. All these contributions are implemented and experimented into tools distributed to the PHP community.

Page generated in 0.1573 seconds