Amazon technologies, inc. (20240202545). AN EAGER SAT-BASED SOLVER FOR A QUANTIFIER-FREE THEORY OF STRINGS AND BIT VECTORS simplified abstract

AN EAGER SAT-BASED SOLVER FOR A QUANTIFIER-FREE THEORY OF STRINGS AND BIT VECTORS

Organization Name

amazon technologies, inc.

Inventor(s)

Kevin Lotz of Kiel (DE)

Bruno Dutertre of Mountain View CA (US)

John Byron Cook of Brooklyn NY (US)

Amit Goel of Portland OR (US)

Robert Jones of Beaverton OR (US)

Benjamin Kiesl-reiter of Munich (DE)

Soon Ho Kong of Cupertino CA (US)

Rupak Majumdar of Krickenbach (DE)

AN EAGER SAT-BASED SOLVER FOR A QUANTIFIER-FREE THEORY OF STRINGS AND BIT VECTORS - A simplified explanation of the abstract

This abstract first appeared for US patent application 20240202545 titled 'AN EAGER SAT-BASED SOLVER FOR A QUANTIFIER-FREE THEORY OF STRINGS AND BIT VECTORS

Abstract: Techniques are described for providing a SAT-based solver for a quantifier-free theory of strings and bit vectors. The solver can be used by an automated reasoning service of a cloud provider network to analyze policies and the consequences of policies. The solver reduces an input formula to a boolean satisfiability problem by encoding the input formula into an equisatisfiable propositional formula, where the satisfiability of the equisatisfiable propositional formula is determined by a SAT solver. Rather than using a traditional DPLL(t) style algorithm, the solver described herein bounds the length of variables in an input formula and reduces the problem to a single formula, which can then be solved using incremental SAT solving. The solver can be used independently or as part of a portfolio of solvers used to determine the satisfiability or unsatisfiability of certain formula corresponding, e.g., to questions about users' policies within a cloud provider network.

Key Features and Innovation:

• Provides a SAT-based solver for a quantifier-free theory of strings and bit vectors.
• Enables automated reasoning services in cloud provider networks to analyze policies effectively.
• Reduces input formulas to boolean satisfiability problems for efficient solving.
• Utilizes incremental SAT solving instead of traditional DPLL(t) algorithms for improved performance.

Potential Applications:

• Cloud computing security analysis
• Policy compliance checking
• Network configuration verification

Problems Solved:

• Efficiently analyzing policies and their consequences in cloud provider networks
• Simplifying complex input formulas for SAT solving
• Improving performance of SAT solvers in automated reasoning services

Benefits:

• Enhanced policy analysis capabilities
• Faster and more accurate SAT solving
• Improved network security and compliance

Commercial Applications: Cloud Security Policy Analysis Tool: Utilize the solver to offer cloud security policy analysis services to businesses, ensuring compliance and security within their networks.

Prior Art: Readers interested in prior art related to this technology can explore research papers on SAT solving algorithms and theories of strings and bit vectors.

Frequently Updated Research: Stay updated on advancements in SAT solving algorithms and theories of strings and bit vectors to enhance the performance and capabilities of the solver.

Questions about SAT-Based Solver for Quantifier-Free Theory of Strings and Bit Vectors:

1. How does the solver improve the analysis of policies in cloud provider networks? 2. What sets incremental SAT solving apart from traditional DPLL(t) algorithms?

Original Abstract Submitted

techniques are described for providing a sat-based solver for a quantifier-free theory of strings and bit vectors. the solver can be used by an automated reasoning service of a cloud provider network to analyze policies and the consequences of policies. the solver reduces an input formula to a boolean satisfiability problem by encoding the input formula into an equisatisfiable propositional formula, where the satisfiability of the equisatisfiable propositional formula is determined by a sat solver. rather than using a traditional dpll(t) style algorithm, the solver described herein bounds the length of variables in an input formula and reduces the problem to a single formula, which can then be solved using incremental sat solving. the solver can be used independently or as part of a portfolio of solvers used to determine the satisfiability or unsatisfiability of certain formula corresponding, e.g., to questions about users' policies within a cloud provider network.