- So computers and networks and hardware are
incredibly valuable and they make our lives wonderful,
and they allow us to do tremendous things.
But we have to be cognizant
of where that information is going,
what that information can do.
And this technology allows us to talk,
to peer into the future, and to look
into what behaviors these systems are capable of,
and then allows us to fix those unwanted behaviors
in the system ahead of time.
So it allows us to proactively look at possible behaviors
of hardware or software.
- Byron Cook is a distinguished scientist
and Vice President at AWS.
Byron has been working in the field of formal verification
for over 20 years and has made several
major research contributions over his career.
He's also developed influential tools
which have been applied to a wide range of topics,
from programming language and operating systems,
to reasoning about biological systems,
and genetic regulatory paraphrase.
This work has been used to answer some fundamental questions
that no other tool was able to solve before it.
For example, pharmaceutical companies use this technology
to better understand leukemia
and find new treatment options for the disease.
At AWS, Byron leads a team of domain experts,
developing formal verification tools
for a wide variety of problems,
helping to keep the cloud safe and secure,
and to protect our customers.
Even though Byron has been working
in the field since the late '90s,
automated reasoning is still considered
to be an emerging technology.
I was curious to learn more, so I met with Byron
to dive deeper on the kinds of applications that he
and his teams are exploring today.
Now, you might be wondering what is formal verification
and how does it work?
- Formal verification, generally speaking, is
automated reasoning applied to problems back in computers.
So automated reasoning is the algorithmic search
for proofs in mathematical logic.
And then when we apply automated reasoning
back to algorithms, to hardware, to software systems,
then that's typically called formal verification.
- To put it in simple terms, formal verification is the use
of mathematical logic to prove property subsystems.
We use formal verification to prove things
about all the possible configurations
a computer program might reach.
Byron's ambition, at the AWS Automated Reasoning Group is
to automate all of the reasoning performed
during formal verification.
- Imagine you wanted to prove that zero is less than one
across the entire Linux kernel.
Super easy to do.
You go to every line of the code and you say,
"Is zero less than one?"
Yes, it is true.
It's true, it's Tsology.
So it's true, so I can now, in a very scalable way,
prove that zero is less than one
across all the world's code, no problem.
Now, let me just take a slightly more interesting question.
Is X less than Y?
So now what you need to do is you look
for all the places where the stack variables X and Y are
in scope, and typically, X and Y won't be in scope
in the Linus kernel.
So now it's only gonna be a few places
you have variables named X and Y, and both X and Y.
And now you need to do a little bit of reasoning
of that code to do it.
So this is an example of, if you're asking a simple question
of sophisticated, large amounts of code,
it's actually quite easy.
And so then the question of what is it you're asking
of the model that's been either developed
by a developer or that's been synthesized
via a method such as machine learning,
that it's really the question you're asking of the system
that drives how challenging that is.
So the idea is we encode the system as a set
of constraints in mathematical logic
and then you use the same techniques that have been around
for hundreds of years.
For example, we might reason about the validity
of the Pythagorean Theorem.
You know, you just find a finite argument
in mathematical logic about what is true
about an infinite set.
So we can use those same techniques to reason
about the intractably large or infinite set
of states of a system, so a microprocessor design
or a piece of software, for example.
So we reuse, the sort of the key idea is then
to use the idea of mathematical induction
where you reason about all possible time
and all possible states that a system could enter
via a couple of steps.
- When we're talking about mathematical logic,
some folks might think about some obscure theory,
not necessarily of practical applications.
But Byron has managed to balance the tension
between theory and the practical problems
our industry faces.
- So there's this great quote by Strachey
who founded the Oxford Computer Science Department
and I'm gonna get the quote,
although I don't have it memorized.
But it's something to the effect of the division
between theory and practice in computing is injurious
to our field, that theoreticians don't know what
to work on and practitioners don't know what they're doing.
And so the real magic is when you combine,
when you're working at the intersection
of theory and practice.
And so what I found in my career is that coming
from a theoretical perspective, I've realized that,
for example, termination was of a very practical concern
and there were very practical techniques
that I could bring to the tools to answer questions
that developers had about their systems.
- So let's talk about termination.
What does that mean in this context?
Well, termination is program analysis that attempts
to determine whether the evaluation
of a given program holds for each input.
- Basically, termination is,
it uses the word eventually.
So will the program eventually terminate?
Will the program eventually release the lock?
So will the device driver eventually give control
back to the operating system?
Will the biological system of wind perturbed
eventually stabilize back to a good, known state?
So that's termination.
Systems are usually developed within an event loop
and whenever you press a key, you touch your screen,
a network packet comes in.
There's event handling code designed to handle that event
and one would hope, eventually stop handling the event.
So typically, there's an action to be taken.
You go through some data structures, you look something up.
You put something, you remove something,
and then the job of that event handling code is to exit.
And typically when you don't exit, that hangs the system
or doesn't respond.
And so that turns out to be a common pattern
that, for all kinds of reasons,
that we wanna show of systems.
- Byron joined AWS in 2015 with a mission
to draw his theoretical work out of his research papers
and develop real world, practical applications
for automated reasoning.
So how is this being applied today?
- So basically, I wanted, in 2015 timeframe,
to walk away a couple of years later
with a couple of successes
where automated reasoning really moved the needle
in some way for customers and for AWS.
So we basically made four bets.
So one of them was to apply to take policies
and the semantics of resource, the resource policy language
and encode that into mathematical logic.
And then use off-the-shelf open source
automated theorem provers to answer questions about them.
So that's Zelkova.
And Zelkova has gone on to power
S3 Block Public Access.
It's gone on to power IMx ACCESS Analyzer,
IoT Device Defender.
There are config managed rules that use Zelkova.
Macie uses Zelkova.
Guard Duty uses Zelkova.
The list goes on.
So that was one of the bets.
The next one was let's do the same thing
but for networks the customer built
or our customers are building on top of EC2,
so VPCs, for example.
So all of this, so let's say,
I'm not sure of the exact number,
but let's say 50 to 100 networking concepts,
virtualized networking concepts that customers use
and put together to build virtual networks.
And then there's questions often around reachability
of can this instance connect to this database,
can this instance connect to this other instance.
Under what conditions can it connect?
Or how often do you want instances
to not be able to connect?
So we take the customer network design,
essentially using describe API calls.
We have in mathematical logic, the semantics
of EC2 networking that we've written.
And then we have a question we wanna ask
about the network about reachability.
So those three things together, we combined.
We asked the automated theorem prover
and the automated theorem prover gives us the answer.
And that has gone on to power Amazon Inspector
and VPC Reachability Analyzer, externally,
and then we're using that internally
in a number of use cases.
- But there are other tools as well, that the team are
developing in the security space that recategorize
on the machine learning.
What's the relationship between machine learning
and automated reasoning?
- There's two pieces to that, two answers to that.
So Guard Duty and Macie are using automated reasoning
in an interesting way.
When you have an intractably large space,
so the set of all configurations of policies or networks,
et cetera, well, you wanna now ask are there routes
through this complex network such that
certain conditions can occur.
And automated reasoning is a great way of doing that
because it reduces that to a proof.
What we attempt to do is we try and prove it's not possible
and when the proof fails, we find a path.
And so Guard Duty and Macie, and a number
of internal tools are using it, really, as a way
of querying the semantics of policies of networks.
- As I mentioned earlier, Byron has been working
in this field for over 20 years.
Yet, it is still emerging.
So what is it about being at AWS and using the cloud
that is not enabling innovation
in the automatic reasoning field?
- The scale of the cloud and the number
of customers operating on the cloud was real exciting
because the other thing that I saw in the history
of automated reasoning is that there was a little bit
of a chicken and egg problem going on
where people weren't using the tools
because the tools weren't available.
But then the tools weren't available
because people weren't realizing they needed the tools.
And so I needed to go to an organization that was operating
at scale and also had the APIs at the right level
of abstraction that we could sort of kick off things
and take things to the next level.
One of the things that really stuck me early on was that
the interaction between Amazon's customer obsession
and the space of automated reasoning
work super well together.
And the reason is that, so automated reasoning is typically
solving undecidable or intractable problems
for which there can be no general solution.
You have to make solutions that work for certain domains
and in that reality, you need to work as closely as possible
with the customer that has the problem.
And so in the university setting or other places I've been,
the level of customer obsession wasn't there
and at Amazon, I, right away was talking to customers
and they began asking for tools
and we began supplying them with the tools.
So within, I think, eight weeks, 16 weeks,
we had a couple of prototype tools in the hands
of some close customers that were
near by the office I was working in,
and they began using those tools, liking them,
asking for features, and actually working
with other customers to make sure that Amazon understood
the value of what we were doing.
So that was real exciting.
- As we continue to work with our customers
to innovate and develop these new applications
for automated reasoning, what kind of things
could customers be thinking about implementing?
What's on the horizon?
- So, I think an area where we're headed is that
reasoning to show that controls hold can be performed
with advanced, sophisticated, hard to understand
automated reasoning tools that are operated
in a difficult cloud stack, et cetera,
but then the proofs that are produced are
in a standard format, easily checkable
with easy to understand tools that the world has agreed
on as a source of truth, that then we check.
And so that the auditor can run the simple tools
and the customer can produce the proofs,
or an independent provider can run the advanced tools
to find this truth.
I mean, there's a continuum of things
that customers should be doing.
So for sure, customers should turn on IMx's Analyzer
and they should go to the console,
the IMx's Analyzer console and look at their resources
and what the resource policies are
allowing or disallowing.
They should take a look at VPC Reachability Analyzer,
they should turn S3 Block Public Access on.
Those are three things.
And then customers are already benefiting
from the work we're doing underneath the stack
in EC2 and S3, et cetera.
Forthcoming are, I believe, will be more advanced tools.
So advanced customers are customers that are curious.
It's probably worthwhile investigating
what these techniques are and what these tools are
because I think some familiarity with the concepts
of those tools will allow you to use them,
the power user features, of them.
So for example, with IMx's Analyzer,
if you get it into the APIs, there's extra things you can do
that you can't do with the console,
but to use those features, you need to understand
a little bit more about some of the techniques.
And I think that will be a trend in the future
that we release features that are super easy to use
and help everyone.
But for folks that have a little deeper understanding
of symbolic reasoning, or concepts of environments, models,
that they'll be able to do more and they'll be able
to go deeper with the tools.
- I'd like to join Byron for joining us,
feeding my curiosity and digging into some
of the truly fascinating under the hood mechanics
and applications of automated reasoning.
If you like to learn more about our guest,
you can follow Byron on Twitter at @ByronCook.
And if you'd like to learn more
about the automated reasoning work
at AWS, we've included links in the description below.
We'll see you next time.
Now, go build.