Browsing by Subject "Formal verification"
Now showing 1 - 8 of 8
Results Per Page
Sort Options
Item Behavioral Model Equivalence Checking for Large Analog Mixed Signal Systems(2012-07-16) Singh, AmandeepThis thesis proposes a systematic, hierarchical, optimization based semi-formal equivalence checking methodology for large analog/mixed signal systems such as phase locked loops (PLL), analog to digital convertors (ADC) and input/output (I/O) circuits. I propose to verify the equivalence between a behavioral model and its electrical implementation over a limited, but highly likely, input space defined as the Constrained Behavioral Input Space. Furthermore, I clearly distinguish between the behavioral and electrical domains and define mapping functions between the two domains to allow for calculation of deviation between the behavioral and electrical implementation. The verification problem is then formulated as an optimization problem which is solved by interfacing a sequential quadratic programming (SQP) based optimizer with commercial circuit simulation tools, such as CADENCE SPECTRE. The proposed methodology is then applied for equivalence checking of a PLL as a test case and results are shown which prove the correctness of the proposed methodology.Item Correct low power design transformations for hardware systems(2013-08) Viswanath, Vinod; Abraham, Jacob A.We present a generic proof methodology to automatically prove correctness of design transformations introduced at the Register-Transfer Level (RTL) to achieve lower power dissipation in hardware systems. We also introduce a new algorithm to reduce switching activity power dissipation in microprocessors. We further apply our technique in a completely different domain of dynamic power management of Systems-on-Chip (SoCs). We demonstrate our methodology on real-life circuits. In this thesis, we address the dual problem of transforming hardware systems at higher levels of abstraction to achieve lower power dissipation, and a reliable way to verify the correctness of the afore-mentioned transformations. The thesis is in three parts. The first part introduces Instruction-driven Slicing, a new algorithm to automatically introduce RTL/System level annotations in microprocessors to achieve lower switching power dissipation. The second part introduces Dedicated Rewriting, a rewriting based generic proof methodology to automatically prove correctness of such high-level transformations for lowering power dissipation. The third part implements dedicated rewriting in the context of dynamically managing power dissipation of mobile and hand-held devices. We first present instruction-driven slicing, a new technique for annotating microprocessor descriptions at the Register Transfer Level in order to achieve lower power dissipation. Our technique automatically annotates existing RTL code to optimize the circuit for lowering power dissipated by switching activity. Our technique can be applied at the architectural level as well, achieving similar power gains. We first demonstrate our technique on architectural and RTL models of a 32-bit OpenRISC pipelined processor (OR1200), showing power gains for the SPEC2000 benchmarks. These annotations achieve reduction in power dissipation by changing the logic of the design. We further extend our technique to an out-of-order superscalar core and demonstrate power gains for the same SPEC2000 benchmarks on architectural and RTL models of PUMA, a fixed point out-of-order PowerPC microprocessor. We next present dedicated rewriting, a novel technique to automatically prove the correctness of low power transformations in hardware systems described at the Register Transfer Level. We guarantee the correctness of any low power transformation by providing a functional equivalence proof of the hardware design before and after the transformation. Dedicated rewriting is a highly automated deductive verification technique specially honed for proving correctness of low power transformations. We provide a notion of equivalence and establish the equivalence proof within our dedicated rewriting system. We demonstrate our technique on a non-trivial case study. We show equivalence of a Verilog RTL implementation of a Viterbi decoder, a component of the DRM System-On-Chip (SoC), before and after the application of multiple low power transformations. We next apply dedicated rewriting to a broader context of holistic power management of SoCs. This in turn creates a self-checking system and will automatically flag conflicting constraints or rules. Our system will manage power constraint rules using dedicated rewriting specially honed for dynamic power management of SoC designs. Together, this provides a common platform and representation to seamlessly cooperate between hardware and software constraints to achieve maximum platform power optimization dynamically during execution. We demonstrate our technique in multiple contexts on an SoC design of the state-of-the-art next generation Intel smartphone platform. Finally, we give a proof of instruction-driven slicing. We first prove that the annotations automatically introduced in the OR1200 processor preserve the original functionality of the machine using the ACL2 theorem prover. Then we establish the same proof within our dedicated rewriting system, and discuss the merits of such a technique and a framework. In the context of today's shrinking hardware and mobile internet devices, lowering power dissipation is a key problem. Verifying the correctness of transformations which achieve that is usually a time-consuming affair. Automatic and reliable methods of verification that are easy to use are extremely important. In this thesis we have presented one such transformation, and a generic framework to prove correctness of that and similar transformations. Our methodology is constructed in a manner that easily and seamlessly fits into the design cycle of creating complicated hardware systems. Our technique is also general enough to be applied in a completely different context of dynamic power management of mobile and hand-held devices.Item A demonstration of applying alloy to mechanical synthesis of electromechanical systems(2015-12) Liu, David Allen; Khurshid, Sarfraz; Garg, VijayFormal verification methods have traditionally been used in industry for proofs of functional correctness; more recent advances in their use have given rise to additional applications in new domains. Electromechanical systems such as automotive transmissions or robotics have relied heavily on software and mechanical modeling to operate and test the given design; modeling tools that support automated analysis such as Alloy allow formal analysis techniques to apply to this domain, and also enable synthesis. Specifically, Alloy provides a language and toolset that can abstractly represent and solve for real-world instances, which enable engineers to develop a deeper understanding of the systems they are building. This goal of the report is to demonstrate the potential of applying the Alloy toolset for modeling and analysis to assist in the synthesis and operational correctness of software-driven mechanical designs. A survey of literature has been included to demonstrate the foundation of concepts and previous research done in the area, spanning both formal verification and electromechanical design fields. The report also includes two small but illustrative case studies that attempt at mechanical synthesis (or design seeding) using Alloy, and report the abstraction methods and techniques that succeeded in demonstrating design synthesis efforts.Item Efficient, mechanically-verified validation of satisfiability solvers(2015-05) Wetzler, Nathan David; Hunt, Warren A., 1958-; Heule, Marijn J. H.; Biere, Armin; Lifschitz, Vladimir; Moore, J Strother; Ramachandran, VijayaSatisfiability (SAT) solvers are commonly used for a variety of applications, including hardware verification, software verification, theorem proving, debugging, and hard combinatorial problems. These applications rely on the efficiency and correctness of SAT solvers. When a problem is determined to be unsatisfiable, how can one be confident that a SAT solver has fully exhausted the search space? Traditionally, unsatisfiability results have been expressed using resolution or clausal proof systems. Resolution-based proofs contain perfect reconstruction information, but these proofs are extremely large and difficult to emit from a solver. Clausal proofs rely on rediscovery of inferences using a limited number of techniques, which typically takes several orders of magnitude longer than the solving time. Moreover, neither of these proof systems has been able to express contemporary solving techniques such as bounded variable addition. This combination of issues has left SAT solver authors unmotivated to produce proofs of unsatisfiability. The work from this dissertation focuses on validating satisfiability solver output in the unsatisfiability case. We developed a new clausal proof format called DRAT that facilitates compact proofs that are easier to emit and capable of expressing all contemporary solving and preprocessing techniques. Furthermore, we implemented a validation utility called DRAT-trim that is able to validate proofs in a time similar to that of the discovery time. The DRAT format has seen widespread adoption in the SAT community and the DRAT-trim utility was used to validate the results of the 2014 SAT Competition. DRAT-trim uses many advanced techniques to realize its performance gains, so why should the results of DRAT-trim be trusted? Mechanical verification enables users to model programs and algorithms and then prove their correctness with a proof assistant, such as ACL2. We designed a new modeling technique for ACL2 that combines efficient model execution with an agile and convenient theory. Finally, we used this new technique to construct a fast, mechanically-verified validation tool for proofs of unsatisfiability. This research allows SAT solver authors and users to have greater confidence in their results and applications by ensuring the validity of unsatisfiability results.Item Formal verification of application and system programs based on a validated x86 ISA model(2016-12) Goel, Shilpi; Hunt, Warren A., 1958-; Alvisi, Lorenzo; Kaufmann, Matt; Lin, Calvin; Moore, J S; Watson, RobertTwo main kinds of tools available for formal software verification are point tools and general-purpose tools. Point tools are targeted towards bug-hunting or proving a fixed set of properties, such as establishing the absence of buffer overflows. These tools have become a practical choice in the development and analysis of serious software systems, largely because they are easy to use. However, point tools are limited in their scope because they are pre-programmed to reason about a fixed set of behaviors. In contrast, general-purpose tools,like theorem provers, have a wider scope. Unfortunately, they also have a higher user overhead. These tools often use incomplete and/or unrealistic software models, in part to reduce this overhead. Formal verification based on such a model can be restrictive because it does not account for program behaviors that rely on missing features in the model. The results of such formal verification undertakings may be unreliable --- consequently, they can offer a false sense of security. This dissertation demonstrates that formal verification of complex program properties can be made practical, without any loss of accuracy or expressiveness, by employing a machine-code analysis framework implemented using a mechanical theorem prover. To this end, we constructed a formal and executable model of the x86 Instruction-Set Architecture using the ACL2 theorem-proving system. This model includes a specification of 400+ x86 opcodes and architectural features like segmentation and paging. The model's high execution speed allows it to be validated routinely by performing co-simulations against a physical x86 processor --- thus, formal analysis based on this model is reliable. We also developed a general framework for x86 machine-code analysis that can lower the overhead associated with the verification of a broad range of program properties, including correctness with respect to behavior, security, and resource requirements. We illustrate the capabilities of our framework by describing the verification of two application programs, population count and word count, and one system program, zero copy.Item Modeling and formal verification of gaming storylines(2016-05) Holloway, Lane Thomas; Fussell, Donald S., 1951; Elster, Anne C.; Abraham, Jacob; Chase, Craig; Miikkulainen, RistoVideo games are becoming more and more interactive with increasingly complex plots. These plots typically involve multiple parallel storylines that may converge and diverge based on player actions. This may lead to situations that are inconsistent or impassable. Current techniques for planning and testing game plots involve naive means such as text documents, spreadsheets, and critical path testing. Recent academic research [1] [2] [3] examines the design planning problems, but neglect testing and verification of the possible plot lines. These complex plots have thus until now been handled inadequately due to a lack of a formal methodology and tools to support them. In this dissertation, we describe how we develop methods to 1) characterize storylines (SChar), 2) define a storyline description language (SDL), and 3) create a storyline verification tool based in formal verification techniques (StoCk) that use our SDL as input. SChar (Storyline Characterization) help game developers characterize the category of story line they are working on (e.g. linear, branching and plot) through a tool that give a set of guided questions. Our SDL allows its users to describe storylines in a consistent format similar to how they reason about storylines, but in such a way that it can be used for formal verification. StoCk accepts storylines, described in SDL, to be formally verified using SPIN for errors. StoCk is also examined in three common use cases found in the gaming industry used as a tool 1) during storyline creation 2) during quality assurance and 3) during storyline implementation. The combination of SChar, SDL, and StoCk provides designers, writers, and developers a novel methodology and tools to verify consistency in large and complex game plots.Item Physically informed runtime verification for cyber physical systems(2015-08) Zheng, Xi, Ph. D.; Julien, Christine; Perry, Dewayne; Kim, Miryung; Longoria, Raul; Khurshid, SarfrazCyber-physical systems (CPS) are an integration of computation with physical processes. CPS have gained popularity both in industry and the research community and are represented by many varied mission critical applications. Debugging CPS is important, but the intertwining of the cyber and physical worlds makes it very difficult. Formal methods, simulation, and testing are not sufficient in guarantee required correctness. Runtime Verification (RV) provides a perfect complement. However the state of the art in RV lacks either efficiency or expressiveness, and very few RV technologies are specifically designed for CPS. The CPS community requires an intuitive, expressive, and practical RV middleware toolset to improve the state of the art. In this proposal, I take an incremental and realistic approach to identify and address the research challenges in CPS verification and validation. Firstly, I carry out a systematic analysis of the state of the art and state of the practice in verifying and validating CPS using a structured on-line survey, semi-structured interviews, and an exhaustive literature review. From the findings obtained, I identify the key research gaps and propose research directions to address these research gaps. My second work is to work on the most pertinent research direction proposed, which is to provide a practical and physically informed runtime verification tool-sets specifically designed for CPS as a sound foundation to the trial and error practice identified as the state of the art in verifying and validating CPS. I create an expressive yet intuitive language (BraceAssertion) to specify CPS properties. I develop a framework (BraceBind) to supplement CPS runtime verification with a real time simulation environment which is able to integrate physical models from various simulation platform. Based on BraceAssertion and BraceBind, which collectively captures the combination of logical content and physical environment, I develop a practical runtime verification framework (Brace), which is efficient, effective, expressive in capturing both local and global properties, and guarantee predictable runtime monitors behavior even with unpredictable surge of events. I evaluate the tool-set with increasingly complex real CPS applications of smart agent systems.Item A verified framework for symbolic execution in the ACL2 theorem prover(2010-12) Swords, Sol Otis; Hunt, Warren A., 1958-; Baumgartner, Jason R.; Boyer, Robert S.; Cook, William; Moore, J S.Mechanized theorem proving is a promising means of formally establishing facts about complex systems. However, in applying theorem proving methodologies to industrial-scale hardware and software systems, a large amount of user interaction is required in order to prove useful properties. In practice, the human user tasked with such a verification must gain a deep understanding of the system to be verified, and prove numerous lemmas in order to allow the theorem proving program to approach a proof of the desired fact. Furthermore, proofs that fail during this process are a source of confusion: the proof may either fail because the conjecture was false, or because the prover required more help from the user in order to reach the desired conclusion. We have implemented a symbolic execution framework inside the ACL2 theorem prover in order to help address these issues on certain problem domains. Our framework introduces a proof strategy that applies bit-level symbolic execution using BDDs to finite-domain problems. This proof strategy is a fully verified decision procedure for such problems, and on many useful problem domains its capacity vastly exceeds that of exhaustive testing. Our framework also produces counterexamples for conjectures that it determines to be false. Our framework seeks to reduce the amount of necessary user interaction in proving theorems about industrial-scale hardware and software systems. By increasing the automation available in the prover, we allow the user to complete useful proofs while understanding less of the detailed implementation of the system. Furthermore, by producing counterexamples for falsified conjectures, our framework reduces the time spent by the user in trying to determine why a proof failed.