AI News

DeepMind uses AlphaProof Code to generate 6.5 million lines of Lean proofs for the Signal protocol

36Kr · AIUpdated Nov 11 21:13

AI summary

DeepMind's AlphaProof Code generated approximately 6.5 million lines of Lean proof code for the Signal core protocol implementation within 4 weeks, covering about 140,000 machine instructions, with only about 1% of the code ultimately requiring further expert inspection. The research team also reinstalled two real bugs previously fixed by Signal into an isolated test version, and AlphaProof Code detected both and provided proofs that passed Lean checking. The relevant specifications and approximately 6.5 million lines of proof code have been open-sourced, but the verification scope is limited to a specific version of the Signal core protocol implementation and designated security properties, and does not cover the entire Signal App or all attack scenarios.

Why read this

AI score 78

The original text provides concrete figures: 6.5 million lines of Lean proofs produced in four weeks, with only about 1% requiring expert review, which can be used to assess changes in the cost structure of formal verification.

Topics

Tags

Body · AI translation

It took 4 weeks and 6.5 million lines of proof, and the problem that has plagued software security researchers for years has finally been cracked—thanks to AI.

The encryption protocol that billions of users worldwide rely on for chatting has finally been mathematically proven to have reliable code.

Pushmeet Kohli, the DeepMind vice president who led the research, could hardly contain his excitement:

Signal CTO Ehren Kret also couldn't help but give it a thumbs-up, saying that an AI Agent being able to turn actually running code into valid Lean theorems is a landmark breakthrough.

Netizens also marveled:

This is the ultimate demonstration of AI Agent engineering in practice! Compressing decades of work into one month—automated verification is just too powerful.

Wow, this time AI Agents have even started using rigorous mathematical proofs for code security.

How did they do it?

AI frantically writes 6.5 million lines of mathematical proofs, completing years of verification work in four weeks

You see, in the past, doing formal verification of software was generally a "noble" task that only mathematicians and formal verification experts could handle;

Ordinary security testing just finds a bug and fixes it, and that's the end of it;

But formal verification requires experts to write rigorous mathematical proofs to ensure that software won't go wrong under specific conditions.

So this work is not only costly and mentally demanding, but also extremely time-consuming—typically starting at three to five years, and for more complex systems it can even take ten or eight years.

(For example, as early as 2004, an Australian NICTA research team began doing mathematical verification for the seL4 operating system kernel; the cumulative workload over 5 years was enough for one person to work continuously for 20 years.)

Now, AlphaProof Code has taken over this arduous proof work.

In this case, first, 5 DeepMind experts worked with AI to write the security requirements that Signal needs to satisfy into mathematical specifications that Lean can understand, and then the experts reviewed them one by one.

After the review passed, the Agent workers driven by Gemini Carbon got to work.

Some were responsible for tackling the mathematical proofs of different parts, and some were responsible for checking the proof results.

They tracked the machine code actually compiled from Signal all the way, step by step implementing the security properties that needed to be proven into Lean code item by item.

△AlphaProof Code workflow diagram, image source: DeepMind

In just four short weeks, the Agents wrote about 6.5 million lines of Lean proof code in one go, bringing about 140,000 machine instructions underlying Signal into mathematical verification.

Google revealed in its blog that in the end, only about 1% of the code required further expert review. (Whoa, 1%?!)

But does writing 6.5 million lines of proof really prove that these Agents have real skills?

The researchers decided to test it again.

So they dug out two real bugs that Signal had previously fixed and quietly reinstalled them into an isolated test version to see whether AlphaProof Code could detect them.

(One involved key state handling between old and new sessions, and the other involved a missing necessary check during key exchange.)

As a result, both trap questions were caught red-handed by AlphaProof Code!

AI not only discovered the problems, but also produced mathematical proofs that passed Lean checking for each, demonstrating with solid reasoning that the versions containing these bugs did indeed violate the security requirements.

Now, the Agent can not only truly prove that the code meets security requirements, but even old vulnerabilities deliberately inserted can't slip past it.

More importantly, DeepMind has open-sourced all the specifications from this research and the roughly 6.5 million lines of Lean proof code, so interested folks can directly take them to check, reproduce, and continue further research:

Anyway, this new method of course has its boundaries, and Google's blog also mentions them:

This verification targets a specific version of Signal's core protocol implementation and specified security properties, and does not yet cover the entire Signal App and all attack scenarios.

But for the software security industry, the significance of AlphaProof Code is already quite intuitive—

It has cut down the threshold of mathematical verification that previously required experts to invest a great deal of time, energy, and money to complete.

And this approach can continue to be extended outward.

From banking systems to medical device firmware to power grid software, those critical programs where a single error could cause serious consequences will in the future all have the opportunity to undergo the same rigorous mathematical testing.

And standing behind this AlphaProof Code is a guardian who has persisted for more than 20 years.

A scientific dream fulfilled across two decades

For me personally, this moment is extraordinarily meaningful.

More than twenty years ago, I was just an intern who had just set foot on the path of research, studying how to check the consistency of complex software systems.

The person who wrote these words is Pushmeet Kohli, Chief Scientist at Google Cloud and Vice President of DeepMind, who is in charge of the AlphaProof Code research.

△

His story begins more than twenty years ago.

In 2004, Pushmeet was still an undergraduate in computer science at the National Institute of Technology Warangal in India, when a sudden email gave him the opportunity to intern at Microsoft Research's Redmond lab in the United States.

There, he followed the team in researching how to verify the reliability of complex software systems, and thus formally embarked on the path of scientific research.

After graduating with his bachelor's degree, he went to Oxford Brookes University in the UK to pursue a doctorate and obtained his PhD in 2007.

After that, Pushmeet joined Microsoft Research and stayed for ten years, eventually rising to head of the cognition research team.

△

In 2017, he moved again to join DeepMind and began leading a team to explore how to use AI to solve scientific problems.

From AlphaFold to AlphaEvolve and AI Co-Scientist, in recent years he has participated in and driven more and more projects, and his research territory has expanded from life sciences all the way to mathematics, software, and cybersecurity.

Now, more than twenty years later, that inexperienced intern from back then has become a research leader in his own right at Google DeepMind.

Besides Pushmeet, there is also a group of big names standing behind AlphaProof Code.

For example, Swarat Chaudhuri, who is both a professor of computer science at the University of Texas at Austin and a researcher at Google DeepMind, and has long studied how to combine AI with formal verification.

△

There is also Jonathan Katz, a veteran in the field of cryptography.

He taught at the University of Maryland for more than twenty years, served as director of the university's cybersecurity center, and is a dual Fellow of the ACM and the International Association for Cryptologic Research (IACR).

△

And in the post announcing the AlphaProof Code breakthrough, Pushmeet also deliberately wrote a sentence:

In short, I am immensely proud of my team members.

Yes, more than twenty years later, that young man who once buried himself in studying solutions has finally waited for the answer.

How wonderful.

English text is being prepared.

Source

36Kr · AI