This thesis presents a novel concolic testing methodology and CORT, a test generation framework that uses it for high-level functional test generation. The test generation effort is visualized as the systematic unraveling of the control-flow response of the design over multiple (factored) explorations. We begin by transforming the Register Transfer Level (RTL) source for the design into a high-performance C++ compiled functional simulator which is instrumented for branch coverage. An exploration begins by simulating the design with concrete stimuli. Then, we perform an interleaved cycle-by-cycle symbolic evaluation over the concrete execution trace extracted from the Control Flow Graph (CFG) of the design. The purpose of this task is to dynamically discover means to divert the control flow of the system, by mutating primary-input stimulated control statements in this trace. We record the control-flow response as a Test Decision Tree (TDT), a new representation for the test generation effort. Successive explorations begin at system states heuristically selected from a global TDT, onto which each new decision tree resultant from an exploration is stitched. CORT succeeds at constructing functional tests for ITC99 and IWLS-2005 benchmarks that achieve high branch coverage using the fewest number of input vectors, faster than existing methods. Furthermore, we achieve orders of magnitude speedup compared to previous hybrid concrete and symbolic simulation based techniques. / Master of Science / In recent years, the cost of verifying digital designs has outpaced the cost of development, in terms of both resources and time. The scale and complexity of modern designs have made it increasingly impractical to manually verify the design. In the process of circuit design, designers use Hardware Descriptive Languages (HDL) to abstract the design in a manner similar to software programming languages. This thesis presents a novel methodology for the automation of testing functional level hardware description with the aim of maximizing branch coverage. Branches indicate decision points in the design, and tests with high branch coverage are able to thoroughly exercise the design in a manner that randomly generated tests cannot. In our work, the design is simulated concretely with a random test (a sequence of input or stimulus). During simulation, we analyze the flow of behavioral statements and decisions executed to construct a formulaic interpretation of the design execution in terms of syntactical elements, to uncover differentiating input that could have diverted the flow of execution to unstimulated parts of the design. This process is formally known as Concolic Execution. The techniques described in this thesis tightly interleaves concrete and symbolic simulation (concolic execution) of hardware designs to generate tests with high branch coverage, orders of magnitude faster than previous similar work.

With the increasing complexity of modern day processors and system-on-a-chip (SOCs), designers invest a lot of time and resources into testing and validating these designs. To reduce the time-to-market and cost, the techniques used to validate these designs have to constantly improve. Since most of the design activity has moved to the register transfer level (RTL), test methodologies at the RTL have been gaining momentum. We present a novel functional test generation framework for functional test generation at RTL. A popular software-based metric for measuring the effectiveness of an RTL test suite is branch coverage. But exercising hard-to-reach branches is still a challenge and requires good understanding of the design semantics. The proposed framework uses static analysis to extract certain semantics of the circuit and uses several data structures to model these semantics. Using these data structures, we assist the branch-guided search to exercise these hard-to-reach branches. Since the correlation between high branch coverage and detecting defects and bugs is not clear, we present a new metric at the RTL which augments the RTL branch coverage with state values. Vectors which have higher scores on the new metric achieve higher branch and state coverages, and therefore can be applied at different levels of abstraction such as post-silicon validation. Experimental results show that use of the new metric in our test generation framework can achieve a high level of branch and fault coverage for several benchmark circuits, while reducing the length of the vector sequence. This work was supported in part by the NSF grant 1016675. / Master of Science

Projekto tikslas – sukurti sistemą, skirtą schemų testinių atvejų atrinkimui naudojant „juodos dėžės“ modelius ir jiems pritaikytus gedimų modelius. Vykdant projektą buvo atlikta kūrino būdų ir technologijų analizė. Sistemos architektūra buvo kuriama atsižvelgiant į reikalavimą, naudoti schemų modelius, kurie yra parašyti c programavimo kalba. Buvo atlikta schemų failų integravimo efektyvumo analizė, tiriamos atsitiktinio testinių atvejų generavimo sekos patobulinimo galimybės, "1" pasiskirstymo 5taka atsitiktinai generuojam7 testini7 atvej7 kokybei. Tyrim7 rezultatai: • Schemų modelių integracijos tipas mažai įtakoja sistemos darbą. • Pusiau deterministinių metodų taikymas parodė, jog atskirų žingsnių optimizacija nepagerina galutinio rezultato. • "1" pasiskirstymas atsitiktinai generuojamose sekose turi įtaką testo kokybei ir gali būti naudojamas testų procesų pagerinimui. / Project objective – to develop a system, which generates functional tests for non-scan synchronous sequential circuits based on functional delay models. During project execution, the analysis of design and technology solutions was performed. The architecture of the developed software is based on the requirement to be able to use the models of the benchmark circuits that are written in C programming language. Analysis of the effectiveness of the model file integration, possibilities of improving random test sequence generation and the influence of distribution of „1“ in randomly generated test patterns was performed. The results of the analysis were: • Type of the model file integration has little effect when using large circuit models. • The implementation of semi deterministic algorithms showed that the optimisation of separate steps by construction of test subsequences doesn’t improve the final outcome. • The distribution of „1“ in randomly generated test patterns has effect on the fault coverage and can be used to improve test generation process.