To realize reliable quantum software, techniques to automatically ensure the quantum software's correctness have recently been investigated. However, they primarily focus on fixed quantum circuits rather than the ...
详细信息
ISBN:
(纸本)9798350301809
To realize reliable quantum software, techniques to automatically ensure the quantum software's correctness have recently been investigated. However, they primarily focus on fixed quantum circuits rather than the procedure of building quantum circuits. Despite being a common approach, the correctness of building circuits using different parameters following the same procedure is not guaranteed. To this end, we propose a designby-contract framework for quantum software. Our framework provides a python-embedded language to write assertions on the input and output states of all quantum circuits built by certain procedures. Additionally, it provides a method to write assertions about the statistical processing of measurement results to ensure the procedure's correctness for obtaining the final result. These assertions are automatically checked using a quantum computer simulator. For evaluation, we implemented our framework and wrote assertions for some widely used quantum algorithms. Consequently, we found that our framework has sufficient expressive power to verify the whole procedure of quantum software.
Program correctness is central to computing, with instructors striving to convey the importance of "getting it right" starting in CS1. Teaching this material carefully demands a uniform framework to specify,...
详细信息
ISBN:
(纸本)9781450326056
Program correctness is central to computing, with instructors striving to convey the importance of "getting it right" starting in CS1. Teaching this material carefully demands a uniform framework to specify, implement, and reason about software correctness. To make these ideas accessible to educators and students, the tutorial will use RESOLVE, an integrated specification and programming language with a toolset especially designed for building verified components. The tutorial will also discuss how to get students involved through hands-on activities with software construction and modular verification using a web-integrated environment that requires no software installation and that features a prototype "push-button" verifying compiler. The proposers have taught the ideas contained here using engaging pedagogical methods in introductory and advanced CS courses to thousands of students and dozens of educators over the past 20 years, and this SIGCSE tutorial will leverage that experience.
At SIGCSE 2013 this special session [1] provided attendees interested in math thinking a place where engaging math reasoning examples and assignments that help connect mathematics and software development could be sha...
详细信息
ISBN:
(纸本)9781450326056
At SIGCSE 2013 this special session [1] provided attendees interested in math thinking a place where engaging math reasoning examples and assignments that help connect mathematics and software development could be shared and discussed. The exercises and assignments presented last year were well received by the audience who indicated immediately that they would find ways to incorporate them in classes such as CS1, CS2, data structures and algorithms, discrete math, and software engineering courses. Feedback from our own surveys showed that even as there was much interest in using engaging math reasoning examples, there was also considerable interest in developing new engaging math reasoning assignments for future sessions. Based on these expressions of interest and the general interest of the approximately 100 attendees of last year's special session, we feel compelled to continue the momentum by proposing a second round of this forum for SIGCSE 2014. We have contact information for these potential presenters and we expect to have no difficulty in attracting suitable presenters if the session is accepted. The remainder of this proposal is nearly identical to last year's proposal except for the example that appears in Section 2. That example is drawn directly from one of the engaging reasoning assignments presented at last year's special session. All exercises are available at [2].
Using logical assertions for program verification is a basic research subject in software engineering. This paper analyzes current approaches and proposes three rules that an assertion testing framework should sat...
详细信息
Using logical assertions for program verification is a basic research subject in software engineering. This paper analyzes current approaches and proposes three rules that an assertion testing framework should satisfy. That is, after adding contracts using a framework, the contracts in a tested project should be able to satisfy consistency, transitivity and completeness. By satisfying these three rules, the contracts can perform as a solid foundation for automatic test case generation. This paper also brings forward a practical approach to writing contracts, the Java Test Oracle Creator (jtoc), which uses Java annotations and Java inner class to construct intelligible contracts for programmers. Finally, a proof is given that jtoc-generated test projects satisfy the three rules proposed above.
Using logical assertions for program verification is a basic research subject in software engineering. This paper analyzes current approaches and proposes three rules that an assertion testing framework should satisfy...
详细信息
Using logical assertions for program verification is a basic research subject in software engineering. This paper analyzes current approaches and proposes three rules that an assertion testing framework should satisfy. That is, after adding contracts using a framework, the contracts in a tested project should be able to satisfy consistency, transitivity and completeness. By satisfy- ing these three rules, the contracts can perform as a solid foundation for automatic test case generation. This pa- per also brings forward a practical approach to writing contracts, the Java Test Oracle Creator (jtoc), which uses Java annotations and Java inner class to construct intelligible contracts for programmers. Finally, a proof is given that jtoc-generated test projects satisfy the three rules proposed above.
The Verifying Compiler ( VC) project is a core component of the Dependable Systems Evolution Grand Challenge. The VC offers the promise of automatically proving that a program or component is correct, where correctnes...
详细信息
The Verifying Compiler ( VC) project is a core component of the Dependable Systems Evolution Grand Challenge. The VC offers the promise of automatically proving that a program or component is correct, where correctness is defined by program assertions. While several VC prototypes exist, all adopt a semantics for assertions that is unsound. This paper presents a consolidation of VC requirements analysis ( RA) activities that, in particular, brought us to ask targeted VC customers what kind of semantics they wanted. Taking into account both practitioners' needs and current technological factors, we offer recovery of soundness through an adjusted definition of assertion validity that matches user expectations and can be implemented practically using current prover technology. For decades, there have been debates concerning the most appropriate semantics for program assertions. Our contribution here is unique in that we have applied fundamental software engineering techniques by asking primary stakeholders what they want and, based on this, proposed a means of efficiently realizing the semantics stakeholders want using standard tools and techniques. We describe how support for the new semantics has been added to ESC/Java2, one of the most fully developed VC prototypes. Case studies demonstrate the effectiveness of the new semantics at uncovering previously indiscernible specification errors.
contracts and specifications have long been used in object-oriented design, programming and testing to enhance reliability before software deployment. However, the use of specifications in deployed software is commonl...
详细信息
ISBN:
(纸本)9783642141065
contracts and specifications have long been used in object-oriented design, programming and testing to enhance reliability before software deployment. However, the use of specifications in deployed software is commonly limited to runtime checking where assertions form a basis for detecting incorrect program states to terminate the erroneous executions. This paper presents a contract-based approach for data structure repair, which allows repairing erroneous executions in deployed software by repairing erroneous states. The key novelty is the support for rich behavioral specifications, such as those that relate pre-states with post-states of the method to accurately specify expected behavior and hence to enable precise repair. The approach is based on the view of a specification as a nondeterministic implementation, which may permit a high degree of non-determinism. The key insight is to use any correct state mutations by an otherwise erroneous execution to prune the non-determinism in the specification, thereby transmuting the specification to an implementation that does not incur a prohibitively high performance penalty. While invariants, pre-conditions and post-conditions could be provided in different modeling languages, we leverage the Alloy tool-set, specifically the Alloy language and the Alloy Analyzer for systematically repairing erroneous states. Four different algorithms are presented and implemented in our data structure repair framework. Experiments using complex specifications show the approach holds much promise in increasing software reliability.
In model-driven development, requirements are captured as a specification model, from which a conforming implementation is automatically generated. Model consistency, with respect to requirements, is a primary concern...
详细信息
ISBN:
(纸本)9780769539096
In model-driven development, requirements are captured as a specification model, from which a conforming implementation is automatically generated. Model consistency, with respect to requirements, is a primary concern. If the various structural and integrity constraints are inconsistent, then either the model will admit no implementation, or the implementation produced will not behave according to the intended requirements. We present an approach, based upon data-How testing, to helping developers inspect their models for inconsistency. System models contain classes, attributes, invariants, and methods specified as first-order predicates. We identify for every attribute its intra-method usages. We construct accordingly call sequences demonstrating its inter-method usages. We derive from each call sequence a Boolean constraint, as a test case, ensuring both the execution of the corresponding inter-method usage and the maintenance of invariants. Developers may examine this test suite and compare against their original understandings about the requirements.
A number of tools can statically check program code to identify commonly encountered bug patterns. At the same time, programs are increasingly relying on external APIS for performing the bulk of their work: the bug-pr...
详细信息
A number of tools can statically check program code to identify commonly encountered bug patterns. At the same time, programs are increasingly relying on external APIS for performing the bulk of their work: the bug-prone program logic is being fleshed-out, and many errors involve tricky subroutine calls to the constantly growing set of external libraries. Extending the static analysis tools to cover the available APIS is an approach that replicates scarce human effort across different tools and does not scale. Instead, we propose moving the static API call verification code into the API implementation, and distributing the verification code together with the library proper. We have designed a framework for providing static verification code together with Java classes, and have extended the FindBugs static analysis tool to check the corresponding method invocations. To validate our approach we wrote verification tests for 100 different methods, and ran FindBugs on 6.9 million method invocations on what amounts to about 13 million lines of production-quality code. In the set of 55 thousand method invocations that could potentially be statically verified our approach identified 800 probable errors. (C) 2006 Elsevier Inc. All rights reserved.
暂无评论