RNA biomarkers enable early and precise disease diagnosis, monitoring, and prognosis, facilitating personalized medicine and targeted therapeutic strategies. However, identification of RNA biomarkers is hindered by the challenge of analyzing relatively small yet high-dimensional transcriptomics datasets, typically comprising fewer than 1000 biospecimens but encompassing hundreds of thousands of RNAs, especially noncoding RNAs. This complexity leads to several limitations in existing methods, such as poor reproducibility on independent datasets, inability to directly process omics data, and difficulty in identifying noncoding RNAs as biomarkers. Additionally, these methods often yield results that lack biological interpretation and clinical utility. To overcome these challenges, we present BAMBI (Biostatistical and Artificial-intelligence Methods for Biomarker Identification), a computational tool integrating biostatistical approaches and machine-learning algorithms. By initially reducing high dimensionality through biologically informed statistical methods followed by machine learning-based feature selection, BAMBI significantly enhances the accuracy and clinical utility of identified RNA biomarkers and also includes noncoding RNA biomarkers that existing methods may overlook. BAMBI outperformed existing methods on both real and simulated datasets by identifying individual and panel biomarkers with fewer RNAs while still ensuring superior prediction accuracy. BAMBI was benchmarked on multiple transcriptomics datasets across diseases, including breast cancer, psoriasis, and leukemia. The prognostic biomarkers for acute myeloid leukemia discovered by BAMBI showed significant correlations with patient survival rates in an independent cohort, highlighting its potential for enhancing clinical outcomes. The software is available on GitHub (https://github.com/CZhouLab/BAMBI).

We present systematic and efficient solutions for both observability enhancement and root-cause diagnosis of postsilicon System-on-Chips (SoCs) validation with diverse usage scenarios. We model specification of interacting flows in typical applications for message selection. Our method for message selection optimizes flow specification coverage and trace buffer utilization. We define the diagnosis problem as identifying buggy traces as outliers and bug-free traces as normal behaviors, for which we use unsupervised learning algorithms for outlier detection. Instead of direct application of machine-learning (ML) algorithms over trace data using the signals as raw features, we use feature engineering to transform raw features into more sophisticated features using domain-specific transformations. The engineered features are highly relevant to the diagnosis task and are generic to be applied across any hardware designs.We present debugging and root cause analysis of subtle post-silicon bugs in industry-scale OpenSPARC T2 SoC. We achieve a trace buffer utilization of 98.96% with a flow specification coverage of 94.3% (average). Our diagnosis method was able to diagnose up to 66.7% more bugs and took up to 847W less diagnosis time as compared to the manual debugging with a diagnosis precision of 0.769.

Verification is a serious bottleneck in the industrial hardware design cycle, routinely requiring person-years of effort. Practical verification relies on a "best effort" process that simulates the design on test inputs. This suggests a new research question: Can this simulation data be exploited to learn a continuous representation of a hardware design that allows us to predict its functionality? As a first approach to this new problem, we introduce Design2Vec, a deep architecture that learns semantic abstractions of hardware designs. The key idea is to work at a higher level of abstraction than the gate or the bit level, namely the Register Transfer Level (RTL), which is somewhat analogous to software source code, and can be represented by a graph that incorporates control and data flow. This allows us to learn representations of RTL syntax and semantics using a graph neural network. We apply these representations to several tasks within verification, including predicting what cover points of the design will be exercised by a test, and generating new tests that will exercise desired cover points. We evaluate Design2Vec on three real-world hardware designs, including an industrial chip used in commercial data centers. Our results demonstrate that Design2Vec dramatically outperforms baseline approaches that do not incorporate the RTL semantics, scales to industrial designs, and can generate tests that exercise design points that are currently hard to cover with manually written tests by design verification experts.

The state restoration ratio (SRR) has been a de facto standard for evaluating the quality of signals selected for post-silicon tracing and debug. In this paper, we establish that SRR is intrinsically unsuitable as a metric for evaluating trace signal quality, as it captures neither the higher-level functionality of the design nor the constraints and requirements on trace signals. We present an algorithm, based on PageRank [PageRank on Netlist (PRoN)], for post-silicon trace signal selection. PageRank is not designed to maximize SRR and is applied to the circuit netlist. We demonstrate that optimizing for SRR typically generates signals that are functionally irrelevant to the design and unusable for debug, for a comprehensive set of SRR-based techniques. We assess the scalability of different signal selection algorithms by applying them to an industrial scale OpenSPARC T2 design. Our results show that our PRoN algorithm consistently outperformed other techniques with respect to scalability and functional relevance of signals selected. It also has higher restorability than the other algorithms, despite not being optimized for that metric.

We present a systematic and efficient ranking method to quantify the goodness of an assertion. We model dependencies among design variables as a directed graph called a variable dependency graph. We define assertion importance and assertion complexity metrics and use the dependency graph to algorithmically compute those two metrics. We repurpose an assertion coverage algorithm from the literature to form a statement-coverage-based ranking as our baseline. We compare our assertion ranking both qualitatively and quantitatively to this baseline. We demonstrate that our ranking is computationally more efficient than statement-coverage-based ranking and takes up to 4366× less computation time. We identify the potential design intents that each ranking prioritizes. We also discuss at length the effect of those prioritizations on the rank agreement and the bug detection ability of the top-ranked assertions according to the two rankings. Finally, we provide a comprehensive ranking for a set of assertions by combining our ranking and the statement-coverage-based ranking.

Assertion quality is critical to the confidence and claims in a design's verification. In current practice, there is no metric to evaluate assertions. We introduce a methodology to rank register transfer level (RTL) assertions. We define assertion importance and assertion complexity and present efficient algorithms to compute them. Our method ranks each assertion according to its importance and complexity. We demonstrate the effectiveness of our ranking for pre-silicon verification on a detailed case study. For completeness, we study the relevance of our highly ranked assertions in a post-silicon validation context, using traced and restored signal values from the design's netlist.

Electrostatic discharge (ESD) has been shown to cause severe reliability hazards at the physical level, resulting in permanent and transient errors. We present the first analysis of the effects of ESD-induced errors on instruction-level computation. Our data were measured on a microcontroller test chip fabricated for this study, with discharges from a controlled ESD gun. cosmic-ray-induced soft errors have been widely researched, and modeled as single event upsets (SEUs). Our observations across multiple trials on 3 test chips show that in contrast to radiation-induced errors, ESD can cause much more widespread errors than SEUs. In our trials, we observed system hangs and clock glitches which are serious errors. We also observed errors in the following categories: multiple-bit corruptions across multiple registers, multiple-bit corruptions in the same register, and single-bit corruptions across multiple registers. At the instruction level, these errors manifest as system hangs or serious malfunctioning of I/O operations, interrupt operations, and data/program memory. We demonstrate that ESD-induced errors form a significant reliability threat to higher-level functionality, warranting modeling and mitigation techniques.

We present an effective machine learning method for malicious activity detection in enterprise security logs. Our method involves feature engineering, or generating new features by applying operators on features of the raw data. We generate DNF formulas from raw features, extract Boolean functions from them, and leverage Fourier analysis to generate new parity features and rank them based on their highest Fourier coefficients. We demonstrate on real enterprise data sets that the engineered features enhance the performance of a wide range of classifiers and clustering algorithms. As compared to classification of raw data features, the engineered features achieve up to 50.6% improvement in malicious recall, while sacrificing no more than 0.47% in accuracy. We also observe better isolation of malicious clusters, when performing clustering on engineered features. In general, a small number of engineered features achieve higher performance than raw data features according to our metrics of interest. Our feature engineering method also retains interpretability, an important consideration in cyber security applications.

We present a method for selecting trace messages for post-silicon validation of Systems-on-a-Chips (SoCs) with diverse usage scenarios. We model specifications of interacting flows in typical applications. Our method optimizes trace buffer utilization and flow specification coverage. We present debugging and root cause analysis of subtle bugs in the industry scale OpenSPARC T2 processor. We demonstrate that this scale is beyond the capacity of current tracing approaches. We achieve trace buffer utilization of 98.96% with a flow specification coverage of 94.3% (average). We localize bugs to 21.11% (average) of the potential root causes in our large-scale debugging effort.

We introduce a methodology for automated test compression during electrical stress testing of analog and mixed signal circuits. This methodology optimally extracts only portions of a functional test that electrically stress the nets and devices of an analog circuit. We model test compression as a problem of optimizing functional of the transient response. We present a random tree based approach to find optimal solutions for these computationally hard integrals. We demonstrate with an op-amp, VCO and CMOS inverter that the method consistently reduces the length of each test by an average of 93%.

We present Duplex random tree search, an algorithm to optimize performance metrics of analog and mixed signal circuits. Duplex determines the optimal design, the Pareto set and the sensitivity of circuit's performance metrics to its parameters. We demonstrate that Duplex is 5× faster than the state-of-the-art and finds the global optimum for a design whose previously published result was a local optimum. We show our algorithm's scalability by optimizing a system-level post-layout charged-pump PLL circuit.

We present an automated directed random input stimulus generation algorithm with high coverage for nonlinear analog circuits. Our methodology is able to generate input stimuli to meet two kinds of objectives: 1) to reach user-defined goal regions and 2) increased coverage of state space. The principal benefit of our approach is that it can provide directed input stimulus generation, as opposed to the randomly generated input stimulus by Monte Carlo-based methods. The methodology introduces multiobjective rapidly-exploring random trees (MORRTs), which add a bias and a feedback loop to the standard rapidly-exploring random trees algorithm. The biasing is provided by a statistical inference algorithm. Simultaneous biasing toward goal regions and coverage is possible in MORRT to a user-defined extent. Our methodology generates several input stimuli that are concentrated in the goals or relevant operating regions, while providing high coverage of the state space. We demonstrate the efficiency and scalability of our approach on high-dimensional analog case studies.

State Restoration Ratio (SRR) has been the de facto standard for evaluating quality of signals selected for post-silicon tracing and debug. Given a set S of selected signals, SRR measures the fraction of (gate-level) design states that can be inferred from observing signals in S at each cycle. Unfortunately, in spite of its widespread use, we found that SRR is intrinsically unsuitable as a metric for evaluating trace signal quality, as it captures neither the higher-level functionality of the design nor the constraints and requirements on trace signals imposed by architectural, physical, or security requirements. In this paper, we argue with strong empirical evidence that SRR must be replaced by a metric that closely models high-level behavioral coverage. We propose assertion coverage as a first step in this direction. We also present a new algorithm, based on Pagerank, for post-silicon trace selection. Pagerank is not designed to maximize SRR. We found that Pagerank has upto 70% higher behavioral coverage than SRR optimizing methods, and the RTL PageRank has upto 30% higher behavioral coverage than the netlist PageRank algorithm. Assertion coverage of PageRank RTL is upto 50% while SRR based methods have less than 5% assertion coverage.

Assertions are gaining importance in pre-silicon hardware verification to ensure expected design behavior. Coverage of an assertion in terms of statements of a Register Transfer Level (RTL) source code is a very accessible metric for understanding the scope of assertions and for debug. However, few methods to report it currently exist. We present a methodology to define and compute code coverage of an assertion. Our method is based on static and dynamic analysis of the RTL source code. We demonstrate the scalability and effectiveness of our approach with experimental results on real designs for both manual and automatically generated assertions.

Statistical model checking (SMC) is a simulation-based approach for verifying the statistical properties of large, complex systems. If a large number of low-probability events (rare events) is required to be simulated, SMC is extremely time-consuming. In this paper, we present a methodology to accelerate the SMC of hardware circuits by generating rare events with a higher frequency. Unlike existing techniques, our methodology can be applied to circuits with multiple rare-event regions. We first sample the circuit uniformly to quickly generate a set of rare events. We employ variational Bayes, a variational inference technique used in machine learning, to infer the distribution of the rare events in the circuit. We then bias the statistical distribution toward these rare event regions. Finally, we employ the SMC using the biased distribution and adjust for the bias that we introduce. The use of variational Bayes enables our methodology to distinguish between multiple rare event regions in the circuit. We demonstrate the effectiveness of our biasing approach on two real-world hardware circuits. We consider the analog (i.e., continuous-time) behavior of these circuits. For an SRAM memory cell, which has a single failure region, we show that our approach provides around 31× speedup over regular SMC while verifying whether the failure rate is less than 10-4. For a successive approximation ADC circuit, which has multiple failure regions, we demonstrate a speedup of 42× while verifying whether the failure rate is less than 10-5.

We enhance STAR, an automatic technique for functional input vector generation for design validation. STAR statically analyzes the source code of the Register-Transfer Level (RTL) design. The STAR approach is a hybrid between RTL symbolic execution and concrete simulation that offsets the disadvantages of both. The symbolic execution, which follows the concrete simulation path, extracts constraints for that path. The guard in the path constraints is then mutated and passed to an SMT solver. A satisfiable assignment generates a valid input vector. However, STAR suffers the problem of path explosion during symbolic execution. In this article, we present an explored symbolic state caching method to attack path explosion. Explored symbolic states are states starting from which all subpaths have been explored. Each explored symbolic state is stored in the form of bitmap encoding of branches to ease comparison. When the explored symbolic state is reached again in the following symbolic execution, all subpaths can be pruned. In addition, we use two types of optimizations: (a) dynamic UD chain slicing; and (b) local conflict resolution to improve the running efficiency of STAR. We demonstrate that the results of the enhanced STAR are promising in showing high coverage on benchmark RTL designs, and the runtime of the test generation process is reduced from several hours to less than 20 minutes.

Because of complexity of analog circuits, their verification presents many challenges. We propose a runtime verification algorithm to verify design properties of nonlinear analog circuits. Our algorithm is based on performing exploratory simulations in the state-time space using the Time-augmented Rapidly Exploring Random Tree (TRRT) algorithm. The proposed runtime verification methodology consists of i) incremental construction of the TRRT to explore the state-time space and ii) use of an incremental online monitoring algorithm to check whether or not the incremented TRRT satisfies or violates specification properties at each iteration. In comparison to the Monte Carlo simulations, for providing the same state-space coverage, we utilize a logarithmic order of memory and time.

We propose a methodology for reachability analysis of nonlinear analog circuits to verify safety properties. Our iterative reachable set reduction algorithm initially considers the entire state space as reachable. Our algorithm iteratively determines which regions in the state space are unreachable and removes those unreachable regions from the over approximated reachable set. We use the State Partitioning Tree (SPT) algorithm to recursively partition the reachable set into convex polytopes. We determine the reachability of adjacent neighbor polytopes by analyzing the direction of state space trajectories at the common faces between two adjacent polytopes. We model the direction of the trajectories as a reachability decision function that we solve using a sound root counting method. We are faithful to the nonlinearities of the system. We demonstrate the memory efficiency of our algorithm through computation of the reachable set of Van der Pol oscillation circuit.

Assertions are valuable and commonly applied to formal verification and simulation-based verification in IC design flow. Unfortunately, assertion generation is a time-consuming process that depends heavily on human efforts. Some dynamic methods based on simulation and static methods based on structure analysis are proposed to automate assertion generation process. However, dynamic methods cannot guarantee the quality of assertions due to incomplete simulation while static methods might have scalability limits. With the significant advances in Boolean satisfiability (SAT) solving, SAT solving becomes a promising technique to overcome these methods' weaknesses. In this paper, we successfully formulate assertion generation to a SAT problem and use unit assumption to generate concise assertions. Furthermore, we consider input constraints and word level features to generate meaningful and high-readability assertions. Experimental results on SpaceWire, Ethernet, and Floating Point designs show that the generated assertions can always achieve 100% input space coverage.

Property checking at the Register Transfer Level (RTL) is a critical problem for verifying complex digital design. In this paper, we present a scalable solution for property checking at RTL. We check the properties of the form G(A=>X=tB), which means that once A is valid, B should be valid t cycles later. We introduce a decomposition strategy to scale high level bounded property checking. This decomposition strategy partitions the monolithic SMT based BMC problem into multiple smaller, independent subproblems. Every path in the RTL program is analyzed for feasibility/relevance using (a) a hybrid of concrete and symbolic execution and (b) property based pruning using the antecedent condition A. The partitions of the RTL source code that correspond to the feasible paths are then checked with respect to the property of interest using an SMT solver. We manage to prune a large percentage of the RTL design paths using feasibility check, such that the decomposed subproblems are small and easily verifiable.

Diagnosing performance violations is one of the biggest challenges in transaction level modeling of systems. In this paper, we propose a methodology to localize root causes of latency or throughput violations. We present a concurrent pattern mining approach to infer frequent patterns from transaction traces to localize root causes. We apply three categories of domain knowledge from the violation and models to filter the irrelevant transaction traces and increase the effectiveness of the mining results. We provide three culprit scenarios to mining algorithm by including transaction traces relevant to the corresponding culprit scenario. The mined concurrent patterns then belong to that culprit scenario. We provide a case study for diagnosing performance violations of an experimental platform and show that our domain knowledge can reduce the number of transaction traces by up to 92.8%. The concurrent pattern mining pinpoints the root cause to one of fewer than 10 patterns among 100000 transaction traces.

We present Preambl, an approach that applies automatically generated invariants to regression testing and bug localization. Our invariant generation methodology is Precis, an automatic and scalable engine that uses program predicates to guide clustering of dynamically obtained path information. In this paper, we apply it for regression testing and for capturing program predicates information to guide statistical analysis based bug localization. We present a technique to localize bugs in paths of variable lengths. We are able to map the localized post-deployment bugs on a path to pre-release invariants generated along that path. Our experimental results demonstrate the efficacy of the use of PRECIS for regression testing, as well as the ability of Preambl to zone in on relevant segments of program paths.

We present GoldMine, a methodology for generating assertions automatically in hardware. Our method involves a combination of data mining and static analysis of the register transfer level (RTL) design. The RTL design is first simulated to generate data about the design's dynamic behavior. The generated data is then mined for “candidate assertions” that are likely to be invariants. The data mining algorithm is a decision-tree-based supervised learning algorithm. These candidate assertions are then passed through a formal verification engine to filter out the spurious candidates. The assertions that are attested as true by the formal engine are system invariants. These are then evaluated by a process of designer ranking that is provided as feedback to the data mining engine. We demonstrate the scalability of GoldMine by showing assertion generation of the RTL of Sun's OpenSparc T2 many-threaded processor. Our results show that GoldMine can generate complex, high coverage assertions for sequential as well as combinational designs in RTL, thereby minimizing human effort in this process. GoldMine assertions distill the random input stimulus space and can be used for calibrating directed tests. They can be used in a regression test suite of an evolving RTL. They are also useful in providing differing perspectives from the designer, as well as hints to designers for manually writing assertions.

Variations in timing can occur due to multiple sources on a chip such as process variations and variations in input patterns. It is desirable to have variation awareness at the register transfer level (RTL), and estimate block level delay distributions early in the design cycle, to evaluate design choices quickly and minimize postsynthesis simulation costs. In previous work, we introduced statistical high-level analysis and rigorous performance estimation (SHARPE), a rigorous, systematic methodology to verify design correctness in RTL in the presence of variations. We described SHARPE in the context of computing statistical delay invariants with respect to input variations. We treated the RTL source code as a program and used static program analysis techniques to compute probabilities. We modeled the probabilistic RTL modules as discrete time Markov chains that are then checked formally for probabilistic invariants using PRISM, a probabilistic model checker. In this paper, we extend SHARPE to perform timing verification in RTL in the context of process variations. We achieved this by obtaining a set of process variation-aware RTL delay models and correspondingly modifying the existing steps in SHARPE. We illustrate SHARPE on the RTL description of the datapath of OR1200, an open source embedded processor. We also apply SHARPE to other data-intensive RTL designs such as nontrivial components of communication systems and a few benchmark designs.

Dynamic power management (DPM) schemes, such as power gating, are important runtime strategies for saving power in multicore architectures. Safety and efficiency are probabilistic properties which need to be verified in order to evaluate a DPM scheme. In this work, we employ statistical model checking to verify probabilistic properties on Register Transfer Level (RTL) descriptions of multicores. Statistical model checking performs a system-level verification of the DPM scheme by simulating several sample paths of the entire RTL design until the verification results lie within tolerable bounds of error. We illustrate our approach on the RTL of OpenSPARC T2, a publicly available industry-strength multicore processor. We verify the safety and efficiency properties of several power gating schemes by considering the power manageable blocks in the floating-point graphics unit.

We present a methodology to generate goal-oriented test cases for verifying nonlinear analog circuits. We use a learning-based approach to identify the goal regions in circuit's state space. We use the information that we learn to guide the growth of Rapidly-exploring Random Trees (RRTs) towards these goal regions. Compared to previous approaches for test generation, our methodology generates several test cases of the circuit that are more concentrated in the relevant operating regions. We demonstrate the effectiveness of our approach on typical case studies. We show that our methodology can be used to generate test cases for undesirable behavior that was previously hard to detect.

In present day technology, the design of reliable systems must factor in temporal degradation due to aging effects such as Negative Bias Temperature Instability (NBTI). In this paper, we present a methodology to estimate delay degradation early at the Register Transfer Level (RTL). We statically analyze the RTL source code to determine signal correlations. We then determine probability distributions of RTL signals formally by using probabilistic model checking. Finally, we propagate these signal probabilities through delay macromodels and estimate the delay degradation. We demonstrate our methodology on several benchmarks RTL designs. We estimate the degradation with <10% error and up to 18.2x speedup in runtime as compared to estimation using gate-level simulations.

Automatic assertion generation methodologies based on machine learning generate assertions at bit level. These bit level assertions are numerous, making them unreadable and frequently unusable. We propose a methodology to discover word level features using static and dynamic analysis of the RTL source code. We use discovered word level features for the underlying learning algorithms to generate word level assertions. A post processing of assertions is employed to remove redundant propositions. Experimental results on Ethernet MAC, I2C, and OpenRISC designs show that the generated word level assertions have higher expressiveness and readability than their corresponding bit level assertions.

We propose a methodology to generate input stimulus to achieve coverage closure using GoldMine, an automatic assertion generation engine that uses data mining and formal verification. GoldMine mines the simulation traces of a behavioral register transfer level (RTL) design using a decision tree based learning algorithm to produce candidate assertions. These candidate assertions are passed to a formal verification engine. If a candidate assertion is false, a counterexample trace is generated. In this paper, we feed these counterexample traces to iteratively refine the original simulation trace data. We introduce an incremental decision tree to mine the new traces in each iteration. The algorithm converges when all the candidate assertions are true. We formally prove that our algorithm will always converge and capture the complete functionality of each output of a sequential design on convergence. We show that our method always results in a monotonic increase in simulation coverage. We also present an output-centric notion of coverage, and argue that we can attain coverage closure with respect to this notion of coverage. We elaborate the technique step by step using a nontrivial arbiter design. Experimental results to validate our arguments are presented on several designs from Rigel, OpenRisc, and SpaceWire. Some practical limitations to achieve 100% coverage and the differences between final decision tree and binary decision diagram are discussed.

Sources of noise such as quantization, introduce randomness into register transfer level (RTL) designs of complex systems. In previous work, we introduced a formal approach to compute the performance metrics for these designs with high confidence. We defined the performance metrics as properties in a probabilistic temporal logic. We then used probabilistic model checking to verify these properties for RTL and thereby guarantee the statistical performance. In this work, we enhance our previous approach in order to include the effects of permanent and transient faults that may be present in the lower levels of hardware implementation. We then formally analyze the vulnerability of performance of RTL designs to faults that are present at different locations. If a performance requirement is not met, we employ probabilistic model checking with a diagnostic property that can be used to identify the broad cause of performance degradation. In this work, we describe our entire approach by considering RTL designs corresponding to multiple-input-multiple-output (MIMO) communication systems. We illustrate our enhanced approach on the Viterbi decoder which is a nontrivial component of MIMO system designs.

We present a methodology to generate input stimulus for design validation using GoldMine, an automatic assertion generation engine that uses data mining and formal verification. GoldMine mines the simulation traces of a behavioral Register Transfer Level (RTL) design using a decision tree based learning algorithm to produce candidate assertions. These candidate assertions are passed to a formal verification engine. If a candidate assertion is false, a counterexample trace is generated. In this work, we feed these counterexample traces to iteratively refine the original simulation trace data. We introduce an incremental decision tree to mine the new traces in each iteration. The algorithm converges when all the candidate assertions are true. We prove that our algorithm will always converge and capture the complete functionality of an output on convergence. We show that our method always results in a monotonic increase in simulation coverage. We also present an output-centric notion of coverage, and argue that we can attain coverage closure with respect to this notion of coverage. Experimental results to validate our arguments are presented on several designs from Rigel, OpenRisc and SpaceWire.

We present HYBRO, an automatic methodology to generate high coverage input vectors for Register Transfer Level (RTL) designs based on branch-coverage directed approach. HYBRO uses dynamic simulation data and static analysis of RTL control flow graphs (CFGs). A concrete simulation is applied over a fixed number of cycles. Instrumented code records the branches covered. The corresponding symbolic trace is extracted from the CFG with an RTL symbolic execution engine. A guard in the symbolic expression is mutated. If the mutated guard has dependent branches that have not already been covered, it is mutated and passed to an SMT solver. A satisfiable assignment generates a valid input vector. We implement the Verilog RTL symbolic execution engine and show that the notion of branch-coverage directed exploration can avoid path explosion caused by previous path-based approach to input vector generation and achieve full branch and more than 90% functional (assertion) coverage quickly on ITC99 benchmark and several Openrisc designs. We also describe two types of optimizations a) dynamic UD chain slicing b) local conflict resolution to speed up HYBRO by 1.6-12 times on different benchmarks.

Pattern mining is a fundamental problem that has a wide range of applications. In this paper, we study the problem of finding a minimum set of signature patterns that explain all data. In the problem, we are given objects where each object has an item set and a label. A pattern is called a signature pattern if all objects with the pattern have the same label. This problem has many interesting applications such as assertion mining in hardware design and identifying failure causes from various log data. We show that the previous pattern mining methods are not suitable for mining signature patterns and identify the problems. Then we propose a novel pattern enumeration method which we call Pattern Shrink. Our method is strongly coupled with another novel method that is very similar to finding a local optimum with a negligible loss in performance. Our proposed methods show a speedup of more than ten times over the previous methods. Our methods are flexible enough to be extended to mining high confidence patterns, instead of signature patterns.

We propose PRECIS, a methodology for automatically generating invariants at function and loop boundaries through program path guided clustering. We instrument function inputs and outputs together with predicates for branch conditions and record their values during each execution. Program runs that share the same path are grouped together based on predicate words. For each group with sufficient data we use linear regression to express the output as a function of the inputs. Groups with insufficient data are examined as candidates for clustering with neighboring groups. Candidates that share the same output function are merged into a cluster. For each cluster, we write an invariant that summarizes the behavior of the corresponding set of paths. We evaluate our technique using Siemens benchmarks. When compared to Daikon, we find that our method has significant advantages.

System level modeling is widely employed at early stages of system development for simplifying design verification and architectural exploration. Assertion based verification has become a well established part of RTL verification methodology. In the traditional assertion based verification flow, assertions are manually written. In this paper, we generate assertions from system level designs using GoldMine, an automatic assertion generation engine that uses data mining and static analysis. Candidate assertions are mined in the form of frequent patterns in the simulation traces of the system level designs. We consider both cycle accurate and transaction level designs and develop a methodology for the mining of each. For cycle accurate designs, we use both a decision tree based supervised learning algorithms as well as a coverage guided association mining algorithm to search for correlations in the simulation trace. For transaction level designs, sequential pattern mining is applied to generate frequent sequences of function calls and events from traces. We also use a symbolic execution engine to generalize the parameters and return values of the functions to help the data miner find relevant behavior. We show that our technique generates meaningful assertions on both a cycle accurate RISC CPU design and a transaction level AMBA-based DMA controller.

With over 78% of designs being heterogeneous integrations of diverse components, SoCs are ubiquitous. This integration, though, brings with it the malaise of challenges in verification and validation. SoC verification has a number of unique challenges beyond traditional ASIC type of designs. The typical SoC flow consists of the following development phases: System Design, Software Design, HW/SW Integration, SoC HW Integration and HW IP design.

We present GOLDMINE, a methodology for generating assertions automatically. Our method involves a combination of data mining and static analysis of the Register Transfer Level (RTL) design. We present results of using GoldMine for assertion generation of the RTL of a 1000-core processor design that is still in an evolving stage. Our results show that GoldMine can generate complex, high coverage assertions in RTL, thereby minimizing human effort in this process.

Sources of noise such as quantization, introduce randomness into Register Transfer Level (RTL) designs of Multiple Input Multiple Output (MIMO) systems. Performance of these MIMO RTL designs is typically quantified by metrics averaged over simulations. In this paper, we introduce a formal approach to compute these metrics with high confidence. We define best, bounded and average case performance metrics as properties in a probabilistic temporal logic. We then use probabilistic model checking to verify these properties for MIMO RTL and thereby guarantee the statistical performance. If a property fails, we show a characterization of error. However, probabilistic model checking is known to encounter the problem of state space explosion. With respect to the properties of interest, we show sound and efficient reductions that significantly improve the scalability of our approach. We illustrate our approach on different non-trivial components of MIMO system designs.

This paper presents a novel technique for proving the correctness of arithmetic circuit designs described at the register transfer level (RTL). The technique begins with the automatic translation of circuits from a Verilog RTL description into a term rewriting system (TRS). We prove the correctness of the designs via an equivalence proof between TRSs for the implementation circuit design and a much simpler specification circuit design. We present this notion of equivalence between the TRSs and a stepwise refinement method for its decomposition, which we leverage in our tool Verifire. We demonstrate the effectiveness of our technique by using the tool for the verification of several multiplier designs that have hitherto been impossible to verify with existing approaches and tools.

Testing a processor in native mode by executing instructions from cache has been shown to be very effective in discovering defective chips. In previous work, we showed an efficient technique for generating instruction sequences targeting specific faults. We generated tests using traditional techniques at the module level and then mapped them to instruction sequences using novel methods. However, in that technique, the propagation of module test responses to primary outputs was not automated. In this paper, we present the algorithm and experimental results for a technique which automates the functional propagation of module level test responses. This technique models the propagation requirement as a Boolean difference problem and uses a bounded model checking engine to perform the instruction mapping. We use a register transfer level (RT-Level) abstraction which makes it possible to express Boolean difference as a succinct linear time logic (LTL) formula that can be passed to a bounded model checking engine. This technique fully automates the process of mapping module level test sequences to instruction sequences

Sequential equivalence checking between system level descriptions of designs and their register transfer level (RTL) implementations is a very challenging and important problem in the context of systems on a chip (SoCs). We propose a technique to alleviate the complexity of the equivalence checking problem, by efficiently decomposing it using compare points. Traditionally, equivalence checking techniques use nominal or functional mapping of latches as compare points. Since we operate at a level where design descriptions are in system level languages or hardware description languages, we leverage the information available to us at this level in deducing sequential compare points. Sequential compare points encapsulate the sequential behavior of designs and are obtained by statically analyzing the design descriptions. We decompose the design using sequential compare points and represent the design behavior at these compare points by symbolic expressions. We use a SAT solver to check the equivalence of the symbolic expressions. In order to demonstrate our technique, we present results on a non-trivial case study. We show an equivalence check between a SystemC description and two different Verilog RTL implementations of a Viterbi decoder, that is a component of the DRM SoC.

Executing instructions from the cache has been shown to improve the defect coverage of real chips. However, although the faults detected by such tests can be determined, there has been no technique to target test generation for an undetected fault. This paper presents a novel technique to map pre-computed test sequences at the module level of a processor, to sequences of instructions. The module level pre-computed test sequence is translated into a temporal logic property and the negation of the property is passed to a bounded model checker. The model checker produces a counter-example for the temporal logic property. This counter-example trace contains the instruction sequence that can be applied at the primary inputs to produce the pre-computed test sequence at the module inputs. This technique has no restrictions on the type of test sequences, so it can be used to map test sequences for any kind of fault to processor instructions. It can also be used in the design phase to produce validation tests.