Intersection and Rotation of Assumption Literals Boosts Bug-Finding

No Thumbnail Available
Date
2020-03-14
Authors
Dureja, Rohit
Li, Jianwen
Pu, Geguang
Vardi, Moshe
Rozier, Kristin Yvonne
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Aerospace Engineering

The Department of Aerospace Engineering seeks to instruct the design, analysis, testing, and operation of vehicles which operate in air, water, or space, including studies of aerodynamics, structure mechanics, propulsion, and the like.

History
The Department of Aerospace Engineering was organized as the Department of Aeronautical Engineering in 1942. Its name was changed to the Department of Aerospace Engineering in 1961. In 1990, the department absorbed the Department of Engineering Science and Mechanics and became the Department of Aerospace Engineering and Engineering Mechanics. In 2003 the name was changed back to the Department of Aerospace Engineering.

Dates of Existence
1942-present

Historical Names

  • Department of Aerospace Engineering and Engineering Mechanics (1990-2003)

Related Units

Organizational Unit
Computer Science

Computer Science—the theory, representation, processing, communication and use of information—is fundamentally transforming every aspect of human endeavor. The Department of Computer Science at Iowa State University advances computational and information sciences through; 1. educational and research programs within and beyond the university; 2. active engagement to help define national and international research, and 3. educational agendas, and sustained commitment to graduating leaders for academia, industry and government.

History
The Computer Science Department was officially established in 1969, with Robert Stewart serving as the founding Department Chair. Faculty were composed of joint appointments with Mathematics, Statistics, and Electrical Engineering. In 1969, the building which now houses the Computer Science department, then simply called the Computer Science building, was completed. Later it was named Atanasoff Hall. Throughout the 1980s to present, the department expanded and developed its teaching and research agendas to cover many areas of computing.

Dates of Existence
1969-present

Related Units

Organizational Unit
Virtual Reality Applications Center
At VRAC, our mission is clear: “To elevate the synergy between humans and complex interdisciplinary systems to unprecedented levels of performance”. Through our exceptional Human Computer Interaction (HCI) graduate program, we nurture the next generation of visionaries and leaders in the field, providing them with a comprehensive understanding of the intricate relationship between humans and technology. This empowers our students to create intuitive and transformative user experiences that bridge the gap between innovation and practical application.
Organizational Unit
Electrical and Computer Engineering

The Department of Electrical and Computer Engineering (ECpE) contains two focuses. The focus on Electrical Engineering teaches students in the fields of control systems, electromagnetics and non-destructive evaluation, microelectronics, electric power & energy systems, and the like. The Computer Engineering focus teaches in the fields of software systems, embedded systems, networking, information security, computer architecture, etc.

History
The Department of Electrical Engineering was formed in 1909 from the division of the Department of Physics and Electrical Engineering. In 1985 its name changed to Department of Electrical Engineering and Computer Engineering. In 1995 it became the Department of Electrical and Computer Engineering.

Dates of Existence
1909-present

Historical Names

  • Department of Electrical Engineering (1909-1985)
  • Department of Electrical Engineering and Computer Engineering (1985-1995)

Related Units

Organizational Unit
Mathematics
Welcome to the exciting world of mathematics at Iowa State University. From cracking codes to modeling the spread of diseases, our program offers something for everyone. With a wide range of courses and research opportunities, you will have the chance to delve deep into the world of mathematics and discover your own unique talents and interests. Whether you dream of working for a top tech company, teaching at a prestigious university, or pursuing cutting-edge research, join us and discover the limitless potential of mathematics at Iowa State University!
Journal Issue
Is Version Of
Versions
Series
Abstract

SAT-based techniques comprise the state-of-the-art in functional verification of safety-critical hardware and software, including IC3/PDR-based model checking and Bounded Model Checking (BMC). BMC is the incontrovertible best method for unsafety checking, aka bug-finding. Complementary Approximate Reachability (CAR) and IC3/PDR complement BMC for bug-finding by detecting different sets of bugs. To boost the efficiency of formal verification, we introduce heuristics involving intersection and rotation of the assumption literals used in the SAT encodings of these techniques. The heuristics generate smaller unsat cores and diverse satisfying assignments that help in faster convergence of these techniques, and have negligible runtime overhead. We detail these heuristics, incorporate them in CAR, and perform an extensive experimental evaluation of their performance, showing a 25% boost in bug-finding efficiency of CAR. We contribute a detailed analysis of the effectiveness of these heuristics: their influence on SAT-based bug-finding enables detection of different bugs from BMC-based checking. We find the new heuristics are applicable to IC3/PDR-based algorithms as well, and contribute a modified clause generalization procedure.

Comments

This is a post-peer-review, pre-copyedit version of a conference proceeding published as Dureja, Rohit, Jianwen Li, Geguang Pu, Moshe Y. Vardi, and Kristin Y. Rozier. "Intersection and Rotation of Assumption Literals Boosts Bug-Finding." In Verified Software. Theories, Tools, and Experiments 11th International Conference, VSTTE 2019, New York City, NY, USA, July 13–14, 2019, Revised Selected Papers. Supratik Chakraborty and Jorge A. Navas, editors. Lecture Notes in Computer Science 12031 (2020): 180-192. The final authenticated version is available online at DOI: 10.1007/978-3-030-41600-3_12. Posted with permission.

Description
Keywords
Citation
DOI
Copyright
Wed Jan 01 00:00:00 UTC 2020