What is Automated Reasoning?

Automated reasoning is the field of computer science that attempts to provide assurance about what a system or program will do or will never do. This assurance is based on mathematical proof. People solve many logical problems in mathematics, science, and computation by using logical strategies like theorems and deductions. Automated reasoning uses computers that use the same tools to solve complex challenges. Automated reasoning tools attempt to answer questions about a program (or a logic formula) by using known techniques from mathematics. The tools help you check what’s true about a statement or expression.

What problems can automated reasoning solve?

Scientists and software developers use automated reasoning to prove two things. First, they prove that a system design or implementation obeys its specification. Second, they prove it works the way it was intended to.

Automated reasoning does this by producing proofs in formal logic supported by mathematical theorems, or known truths. Automated reasoning uses mathematical, logic-based algorithmic verification methods to produce proofs of security or correctness for all possible behaviors.

Automated reasoning can also be used to prove that systems used to configure networks, allow network access or grant permissions, or to keep data private and secure work as intended.

When you use automated reasoning, you first present the system with a problem statement. Then the automated reasoning system calculates and validates the assumptions with the problem statement. The software does this until it exhausts all options.

Example problem for automated reasoning

To understand automated reasoning better, consider the problem statement Do cats live on land? and the following assertions:

  • Cats are mammals
  • Mammals live on land

The automated reasoning system evaluates if the problem statement is true.  Specifically, it uses logical deduction. In this case, cats are mammals and mammals live on land. So, it would verify that cats live on land.

Limitations of automated reasoning

Automated reasoning does not make predictions or generalizations. For example, we can use automated reasoning to make an argument like this:

  1. Cats have hair
  2. Fluffy is a cat
  3. So, Fluffy has hair

We cannot use automated reasoning to make arguments like this:

  1. Cats are mammals
  2. Cats live on land
  3. So, all mammals live on land

Such applications are common in a theorem prover, which requires human guidance when performing deductive reasoning tasks.

What are some automated reasoning use cases?

Automated reasoning’s ability to make logic inferences step-by-step is helpful in several areas. By using automated reasoning, you can prove security, compliance, availability, durability, and safety properties of large-scale architectures.

Here are some other use cases for automated reasoning.

Mathematical modeling

Scientists, engineers, and mathematicians solve problems and verify mathematical proofs by applying algebraic formulas in scientific applications. In such practices, they use mathematical models that rely on several variables to deduce probable solutions to a problem.

Hardware verification

Automated reasoning helps hardware engineers build reliable products. It allows them to discover potential flaws overlooked by conventional testing methods.

For example, electronics design engineers use rigorous mathematical automated reasoning analyses to get conclusive proof that a particular hardware design meets its specification, such as the systems behaviors or executions.

Verification shows that all of the system’s possible behaviors satisfy the temporal properties that comprise the specification. It could also show that each possible behavior of the system’s implementation is consistent with some behavior of its high-level specification.

Software validation

Software developers use automated reasoning to help ensure applications are robust against undesired security issues and that software works as intended or designed. Like hardware verification, automated reasoning allows developers to validate software security measures against various policies.

For example, engineers at Amazon Web Services (AWS) prove that the boot code is secure for every boot configuration with automated reasoning. Another example is that they prove the data stored and processed on Amazon Simple Storage Service (Amazon S3) is safeguarded. In this example, they rely on automated reasoning for replication, consistency, auto scaling, load balancing, and other coordination tasks.


Human reasoning modeling

Computer scientists use automated reasoning technologies to configure access. To do this, they write policies that describe when to allow and deny user requests to access a resource. This verifies that only the intended users have access to the resource, which is important for the security and privacy of the resource.

For example, computer scientists use satisfiability modulo theories (SMT) formulas and SMT solvers to prove security properties.

What are some automated reasoning tools and techniques?

Next, we share several automated deduction methods that enable computing systems to perform human deduction.

Classical logic

Classical logic is a mathematical philosophy that provides basic reasoning models for automated logical reasoning programs. This logic is based on the principle that each proposition has a truth value of either true or false but not both.

It primarily focuses on first-order logic, which allows mathematicians to represent unknown variables like x with quantifiers like there exists in a sentence. For example, scientists apply classical logic in logic programming to find x in this sentence: There exists x such that x lives on land, and x is a mammal.

Propositional logic

Propositional logic is a logic system in which there are propositions that can be either true or false and the construction of relationships between them, called arguments.

The classic statement of an argument in propositional logic is If P, then Q. For example, if it’s Saturday, then it’s the weekend.

Automated reasoning uses a technique called SAT solving. It uses tools called SAT solvers to search for satisfying assignments to arguments in propositional logic. This means variables that make the argument true.

What’s the difference between automated reasoning and artificial intelligence?

Automated reasoning is a specific discipline of artificial intelligence (AI) that applies logical deduction to computer systems.

AI is a science that teaches computers to think like people when the computers solve problems. Recent developments in AI have led to the advancement of various subdisciplines, including deep learning, data analytics, and machine learning.

Automated reasoning differs from other AI technologies, such as natural language processing (NLP), which focuses on training computers to understand written or verbal speeches. Instead, automated reasoning uses logical models and proofs to reason about the possible behaviors of a system or program, including states it can or will never reach.

What’s the difference between automated reasoning and deep learning?

Automated reasoning proves properties of a program or system. It uses the program or system itself, as well as a model or specification of the system in formal logic.

Deep learning makes predictions based on applying statistical models to large datasets.

Deep learning is an advanced machine learning technology that simulates how the human brain works. It uses different neural network models that consist of multiple layers of neurons that extract, compare, and analyze relevant information. Data scientists use deep learning for complex applications, such as processing camera and sensor data in self-driving cars.

Is automated reasoning machine learning?

Automated reasoning and machine learning aren’t the same thing. In short, machine learning makes predictions and inferences. Automated reasoning provides proof.

Machine learning is a subset of AI that trains computers to make decisions with large data samples. For example, data scientists use machine learning to train banking software to identify fraudulent activities. They use large samples of financial data to ensure the software identifies abnormal patterns easily based on previously learned results.

Instead of training the model with data, automated reasoning allows the model to deduce an outcome based on mathematical truth and proof.

How does AWS use automated reasoning to improve service offerings?

AWS uses automated reasoning to improve several service offerings. We give some examples below:

Visit Provable Security for more information on automated reasoning across AWS services. We use mathematical reasoning to provide strong security assurances for your security workloads.

Get started with security on AWS by creating an account today.