Search

Your search keyword '"Qin, Shengchao"' showing total 21 results
Start Over Author "Qin, Shengchao" Topic separation logic

Refine your results

more »

more »

21 results on '"Qin, Shengchao"'

1. Automated Modular Verification for Relaxed Communication Protocols

Author

Costea, Andreea, Chin, Wei-Ngan, Qin, Shengchao, Craciun, Florin, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, and Ryu, Sukyoung, editor

Published
2018
Full Text
View/download PDF

3. Shape Analysis via Second-Order Bi-Abduction

Author

Le, Quang Loc, Gherghina, Cristian, Qin, Shengchao, Chin, Wei-Ngan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Biere, Armin, editor, and Bloem, Roderick, editor

Published
2014
Full Text
View/download PDF

4. Automated Specification Discovery via User-Defined Predicates

Author

He, Guanhua, Qin, Shengchao, Chin, Wei-Ngan, Craciun, Florin, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Groves, Lindsay, editor, and Sun, Jing, editor

Published
2013
Full Text
View/download PDF

5. Invariants Synthesis over a Combined Domain for Automated Program Verification

Author

Qin, Shengchao, He, Guanhua, Chin, Wei-Ngan, Yang, Hongli, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Liu, Zhiming, editor, Woodcock, Jim, editor, and Zhu, Huibiao, editor

Published
2013
Full Text
View/download PDF

6. A Specialization Calculus for Pruning Disjunctive Predicates to Support Verification

Author

Chin, Wei-Ngan, Gherghina, Cristian, Voicu, Răzvan, Le, Quang Loc, Craciun, Florin, Qin, Shengchao, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Gopalakrishnan, Ganesh, editor, and Qadeer, Shaz, editor

Published
2011
Full Text
View/download PDF

7. Structured Specifications for Better Verification of Heap-Manipulating Programs

Author

Gherghina, Cristian, David, Cristina, Qin, Shengchao, Chin, Wei-Ngan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Butler, Michael, editor, and Schulte, Wolfram, editor

Published
2011
Full Text
View/download PDF

8. Automatically Refining Partial Specifications for Program Verification

Author

Qin, Shengchao, Luo, Chenguang, Chin, Wei-Ngan, He, Guanhua, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Butler, Michael, editor, and Schulte, Wolfram, editor

Published
2011
Full Text
View/download PDF

9. Verifying Heap-Manipulating Programs with Unknown Procedure Calls

Author

Qin, Shengchao, Luo, Chenguang, He, Guanhua, Craciun, Florin, Chin, Wei-Ngan, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Dong, Jin Song, editor, and Zhu, Huibiao, editor

Published
2010
Full Text
View/download PDF

10. Memory Usage Verification Using Hip/Sleek

Author

He, Guanhua, Qin, Shengchao, Luo, Chenguang, Chin, Wei-Ngan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Liu, Zhiming, editor, and Ravn, Anders P., editor

Published
2009
Full Text
View/download PDF

11. Automated Verification of Shape and Size Properties Via Separation Logic

Author

Nguyen, Huu Hai, David, Cristina, Qin, Shengchao, Chin, Wei-Ngan, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Cook, Byron, editor, and Podelski, Andreas, editor

Published
2007
Full Text
View/download PDF

14. Automated Verification of the FreeRTOS Scheduler in HIP/SLEEK.

Author

Ferreira, Joao F., He, Guanhua, and Qin, Shengchao

Abstract

Automated verification of operating system kernels is a challenging problem, partly due to the use of shared mutable data structures. In this paper, we show how we can automatically verify memory safety and functional correctness of the task scheduler component of the Free RTOS kernel using the verification system Hip Sleek. We show how some of Hip Sleek features like user-defined predicates and lemmas make the specifications highly expressive and the verification process viable. To the best of our knowledge, this is the first code-level verification of memory safety and functional correctness properties of the Free RTOS scheduler. The outcome of our experiment confirms that Hip Sleek can indeed be used to verify code that is used in production. Moreover, since the properties that we verify are quite general, we envisage that the same approach can be adopted to verify the scheduler of other operating systems. [ABSTRACT FROM PUBLISHER]

Published
2012
Full Text
View/download PDF

15. Automatically refining partial specifications for heap-manipulating programs.

Author

Qin, Shengchao, He, Guanhua, Luo, Chenguang, Chin, Wei-Ngan, and Yang, Hongli

Subjects
*TECHNICAL specifications, *DATA structures, *ANNOTATIONS, *NUMERICAL analysis, *INFORMATION theory
Abstract

Abstract: Automatically verifying heap-manipulating programs is a challenging task, especially when dealing with complex data structures with strong invariants, such as sorted lists and AVL/red–black trees. The verification process can greatly benefit from human assistance through specification annotations, but this process requires intellectual effort from users and is error-prone. In this paper, we propose a new approach to program verification that allows users to provide only partial specification to methods. Our approach will then refine the given annotation into a more complete specification by discovering missing constraints. The discovered constraints may involve both numerical and multi-set properties that could be later confirmed or revised by users. We further augment our approach by requiring partial specification to be given only for primary methods. Specifications for loops and auxiliary methods can then be systematically discovered by our augmented mechanism, with the help of information propagated from the primary methods. Our work is aimed at verifying beyond shape properties, with the eventual goal of analysing full functional properties for pointer-based data structures. Initial experiments have confirmed that we can automatically refine partial specifications with non-trivial constraints, thus making it easier for users to handle specifications with richer properties. [Copyright &y& Elsevier]

Published
2014
Full Text
View/download PDF

16. Loop invariant synthesis in a combined abstract domain

Author

Qin, Shengchao, He, Guanhua, Luo, Chenguang, Chin, Wei-Ngan, and Chen, Xin

Subjects
*LOOPS (Group theory), *INVARIANTS (Mathematics), *ABSTRACT algebra, *SHAPE analysis (Computational geometry), *FIXED point theory, *OPERATOR theory
Abstract

Abstract: Automated verification of memory safety and functional correctness for heap-manipulating programs has been a challenging task, especially when dealing with complex data structures with strong invariants involving both shape and numerical properties. Existing verification systems usually rely on users to supply annotations to guide the verification, which can be cumbersome and error-prone by hand and can significantly restrict the usability of the verification system. In this paper, we reduce the need for some user annotations by automatically inferring loop invariants over an abstract domain with both shape and numerical information. Our loop invariant synthesis is conducted automatically by a fixed-point iteration process, equipped with newly designed abstraction mechanism, together with join and widening operators over the combined domain. We have also proven the soundness and termination of our approach. Initial experiments confirm that we can synthesise loop invariants with non-trivial constraints. [Copyright &y& Elsevier]

Published
2013
Full Text
View/download PDF

17. Separation Logic for Multiple Inheritance.

Author

Luo, Chenguang and Qin, Shengchao

Subjects
MATHEMATICAL logic, COMPUTER logic, JAVA programming language, PROGRAMMING languages, COMPUTER science
Abstract

Abstract: As an extension to Floyd-Hoare logic, separation logic has been used to facilitate reasoning about imperative programs manipulating shared mutable data structures. Recently, it has also been extended to support modular reasoning in Java-like object-oriented languages where only single inheritance is allowed. In this paper we propose an extension of separation logic to support also the reasoning for multiple inheritance in C++ -like languages. To cater for multiple inheritance, we modified the standard storage model for separation logic in a way that the correct reference to a field or a method can be easily determined. On top of this storage model, a set of proof rules are proposed. Our verification system also provides basic support for behavioral subtyping. [Copyright &y& Elsevier]

Published
2008
Full Text
View/download PDF

18. Testing heap-based programs with Java StarFinder.

Author

Pham, Long H., Le, Quang Loc, Phan, Quoc-Sang, Sun, Jun, and Qin, Shengchao

Subjects
JAVA programming language, ERROR detection (Information theory), DATA structures, COMPUTER software execution, SOFTWARE engineering
Abstract

We present Java StarFinder (JSF), a tool for automated test case generation and error detection for Java programs having inputs in the form of complex heap-manipulating data structures. The core of JSF is a symbolic execution engine that uses separation logic with existential quantifiers and inductively-defined predicates to precisely represent the (unbounded) symbolic heap. The feasibility of a heap configuration is checked by a satisfiability solver for separation logic. At the end of each feasible path, a concrete model of the symbolic heap (returned by the solver) is used to generate a test case, e.g., a linked list or an AVL tree, that exercises that path. We show the effectiveness of JSF by applying it on non-trivial heap-manipulating programs and evaluated it against JBSE, a state-of-the-art symbolic execution engine for heap-based programs. Experimental results show that our tool significantly reduces the number of invalid test inputs and improves the test coverage. [ABSTRACT FROM AUTHOR]

Published
2018
Full Text
View/download PDF

19. Verifying pointer safety for programs with unknown calls

Author

Luo, Chenguang, Craciun, Florin, Qin, Shengchao, He, Guanhua, and Chin, Wei-Ngan

Subjects
*CONFIRMATION (Logic), *INFERENCE (Logic), *ABDUCTION (Logic), *INTELLECT, *REASONING, *IMPERATIVE programming, *HOARE logic
Abstract

Abstract: We study the automated verification of pointer safety for heap-manipulating imperative programs with unknown procedure calls. Given a Hoare-style partial correctness specification in separation logic, where the program contains calls to some unknown procedure , we infer a specification for the unknown procedure from the calling contexts. We show that the problem of verifying the program against the specification can be safely reduced to the problem of proving that the procedure (once its code is available) meets the derived specification . The expected specification for the unknown procedure is automatically calculated using an abduction-based shape analysis. We have also implemented a prototype system to validate the viability of our approach. Preliminary results show that the specifications derived by our tool fully capture the behaviors of the unknown code in many cases. [Copyright &y& Elsevier]

Published
2010
Full Text
View/download PDF

20. Mutation in Linked Data Structures

Author

Maclean, Ewen, Ireland, Andrew, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Qin, Shengchao, editor, and Qiu, Zongyan, editor

Published
2011
Full Text
View/download PDF

21. Automated verification of shape, size and bag properties via user-defined predicates in separation logic

Author

Chin, Wei-Ngan, David, Cristina, Nguyen, Huu Hai, and Qin, Shengchao

Subjects
*SOFTWARE verification, *DATA structures, *FEASIBILITY studies, *PROTOTYPES, *PREDICATE (Logic), *AUTOMATION
Abstract

Abstract: Despite their popularity and importance, pointer-based programs remain a major challenge for program verification. In recent years, separation logic has emerged as a contender for formal reasoning of pointer-based programs. Recent works have focused on specialized provers that are mostly based on fixed sets of predicates. In this paper, we propose an automated verification system for ensuring the safety of pointer-based programs, where specifications handled are concise, precise and expressive. Our approach uses user-definable predicates to allow programmers to describe a wide range of data structures with their associated shape, size and bag (multi-set) properties. To support automatic verification, we design a new entailment checking procedure that can handle well-founded predicates (that may be recursively defined) using unfold/fold reasoning. We have proven the soundness and termination of our verification system and built a prototype system to demonstrate the viability of our approach. [Copyright &y& Elsevier]

Published
2012
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results