
Zellic's and V12's Work on x86 Binary Formal Verification
Oct 30, 2026 #FV Announcing Zellic's and V12's Work on x86 Binary Formal Verification
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
Oct 30, 2026 #FV Announcing Zellic's and V12's Work on x86 Binary Formal Verification
A machine-checked proof that covers the behavior of a Linux process executing a statically linked x86 glibc binary end to end
Malte Leip, V12 We are excited to share what we believe to be the first published machine-checked proof that covers the behavior of a Linux process executing a statically linked 64-bit x86 glibc binary end to end.
This result is part of an ongoing internal collaboration between Zellic and V12 aiming to enable scalable formal verification of x86 programs at the binary level. Targeting the binary level helps dramatically reduce the required trusted base compared to formalizing source code (due to a smaller model at full coverage, as well as not relying on e.g. compilers being bug-free) and allows us to cover binaries produced by many different compilers and programming languages, including directly written optimized machine code.
While the x86 instruction set is notably more difficult to model than architectures such as RISC-V, it is much more widely used in real-world deployments. Since its conception, the goal of this project has been to combine frontier models with expert human guidance to build a framework to achieve a scalable, reusable workflow for glibc and x86 machine-code verification.
This will be the first in a series of blog posts on this project.
Recent leaps in AI ability have led not only to a dramatic rise in the amount of software that needs to be secured but also to a critical increase in the level of confidence needed that this software is in fact free of security vulnerabilities. Methods to gain confidence in software being secure are thus needed that are able to provide stronger guarantees of bug-freeness than merely “our method failed to find a bug”, shrinking the trusted base of code to allow efficient coverage by the limited resources of (AI-assisted) human security expertise.
Formal verification is the big unlock that allows us to minimize the trusted base requiring security analysis. The proofs of software are large and scale with size and complexity of the code, but they are automatically checked; no human needs to look at them. There are still some elements left we need to trust and validate, such as the checker and statements, but these are either one-time costs that amortize (like the checker and execution model) or much smaller than the proofs (like the program-specific statements).
This is why we at Zellic and V12 have been developing a project to enable scalable formal verification of userspace software on x86 under Linux, at the binary level.
Targeting the binary level increases the scale of the individual proof effort but in turn rules out more bugs than formalizing the source code level (e.g., compiler bugs), while also having a simpler model1 and thus smaller trusted base. It covers binaries produced by various compilers and programming languages, including directly written machine code that wouldn’t be amenable to higher-level–only formalization anyway. We believe that based on the first two goals, verifying at the binary level is the desirable choice — as long as it is actually possible to prove the desired statements in practice, at scale and efficiently.
Recent work by Anthropic and Theorem has also followed this approach, making significant strides in verifying security properties of RISC-V binaries linked against musl libc. However, as they note, “most people run these libraries on x86 or ARM and dynamically link them against glibc”.23 Compared with RISC-V, x86 requires reasoning about a substantially more complex instruction set.
Furthermore, glibc, unlike musl, brings an elaborate initialization before main, and dispatches subroutines that could have simple implementations to CPU-dependent, highly optimized assembly, causing even very simple programs to become highly complex. For example, glibc on x86 for plain C programs tends to execute around ten times as many distinct instructions (as in distinct addresses) before reaching main compared to RISC-V musl. As the glibc start-up calls strcmp, we had to reason about its behavior in the EVEX variant that glibc chooses for the CPU we targeted, which consists of optimized assembly using AVX-512 instructions and contains 45 jumps and 12 rets in 316 instructions, while the musl implementation compiled for RISC-V has 4 jumps (branches) and one ret in 14 instructions.
This project started mid-September 2026 with the aim to not just formalize the x86 execution model but to develop a scalable framework allowing efficient proving of relevant security properties in this model, in the real-world setting of glibc-linked x86 binaries. We have built a model in Lean of the execution of single-threaded, statically linked non-PIE programs running under Linux in 64-bit x86 userspace, together with vocabulary for formulating statements and substantial proof machinery to aid in proving them in this model. We have validated that it is possible to prove substantial results using this framework.
Over the coming weeks, we plan to release a series of blog posts sharing the results we have achieved so far. What we are releasing with this post is a research preview4 of the model and statement vocabulary, together with proofs for some statements about binaries in it. This includes a proof of a meaningful security property, covering full runs of an ELF binary statically compiled against glibc. To the best of our knowledge, this is the first published machine-checked proof that covers the behavior of a Linux process executing a statically linked x86 glibc binary end to end.
This covers from execve, through the glibc start-up (which includes, for example, IFUNC resolution and TLS setup), memory allocation on the heap, I/O on stdin/stdout, all the way to exit_group. The proof covers every run, and the statement specifies that every run that reaches main ends in a specified way. The run may also get stuck or crash in glibc’s start-up without reaching main, which the statement also allows, while constraining what the process might do (e.g., what may be written to stdout).
The proven statement has some assumptions; for example, we assume the processor matches the specific CPU of our development VM, that the vDSO image is the specific one on our test system or none, that the kernel doesn’t refuse brk or mmap, that nothing from outside interferes with the process,5 that there are no glibc tunables, and a couple of other such conditions.
As an aside of independent interest, we encountered multiple cases where our intended statements had to be modified to account for edge-case bugs within glibc itself. These bugs are being reported and will be the topic of an upcoming blog post.
We end-to-end verified execution of a binary compiled (against glibc, compiled with GCC) with the following source code:
1
#include <stdlib.h>
2
#include <unistd.h>
3
4
#define NAME_SIZE 32
5
#ifndef READ_LEN
6
#define READ_LEN NAME_SIZE
7
#endif
8
9
int main(void) {
10
char *name = malloc(NAME_SIZE);
11
volatile char *admin = malloc(1);
12
if (name == NULL || admin == NULL) return 2;
13
*admin = 0;
14
ssize_t n = read(0, name, READ_LEN);
15
if (n < 0) return 1;
16
if (write(1, "Hello, ", 7) != 7) return 1;
17
if (write(1, name, n) != n) return 1;
18
if (*admin) {
19
if (write(1, "! admin: yes\n", 13) != 13) return 1;
20
} else {
21
if (write(1, "! admin: no\n", 12) != 12) return 1;
22
}
23
return 0;
24
}
#include #define NAME_SIZE 32#ifndef READ_LEN#define READ_LEN NAME_SIZE#endifint main(void) { char *name = malloc(NAME_SIZE); volatile char *admin = malloc(1); if (name == NULL || admin == NULL) return 2; *admin = 0; ssize_t n = read(0, name, READ_LEN); if (n
This is a simple program that reads a name into an allocated buffer and prints out at the end whether an admin flag is set. If READ_LEN is set to a higher value than the allocated buffer size NAME_SIZE, and the binary is compiled without overflow protection, then the read overflows the buffer and can (if the read is sufficiently long) overwrite the admin buffer and result in the program printing “admin: yes”. That would be a classic memory-safety bug, a very common bug class. In this simple program, it is easy to see that the read is at most the length of the buffer, and that, assuming that malloc works as expected to return buffers that are disjoint and also don’t overlap with the stack and so on, and assuming that the compiler doesn’t mess things up, this should not happen.
What we proved about the compiled binary is this statement:
1
def holds : Prop :=
2
Exe.HasData Clients.Admin.file.blob
3
["__libc_single_threaded"] ∧
4
∀ l : Launch,
5
l.Of Clients.Admin.file.img Clients.Admin.file.size →
6
l.prof.Consistent → l.prof.linux.Modest →
7
StackRoom l.args (startStack + 32) →
8
DemoArgs l.args → DemoLimits l.args →
9
ThisProcessor l.prof → ThisVdso l.prof.linux →
10
Always l.prof DemoEnv l.s₀ (fun _ evs => SoFar evs)
11
(fun out evs =>
12
(out.Modelled ∧ ∀ ev ∈ evs, C.Event.IsStartup ev) ∨
13
Done out evs) ∧
14
EndsIf l.prof DemoEnv l.s₀
15
(fun s _ =>
16
s.cpu.rip = Exe.entry Clients.Admin.file.blob "main")
17
Done
SoFar evs) (fun out evs => (out.Modelled ∧ ∀ ev ∈ evs, C.Event.IsStartup ev) ∨ Done out evs) ∧ EndsIf l.prof DemoEnv l.s₀ (fun s _ => s.cpu.rip = Exe.entry Clients.Admin.file.blob "main") Done">
We will unpack more how our statement vocabulary works in an upcoming blog post. One part of the statement we wish to highlight here is the last line, which says that if execution reaches main, then the program will end,6 satisfying Done:
1
def Done (out : Outcome) (evs : List Event) : Prop :=
2
(Input 0 evs).length ≤ nameMax ∧
3
((out = .exited .exitGroup 0 ∧
4
Output 1 evs = line (Input 0 evs)) ∨
5
(out = .exited .exitGroup 1 ∧
6
Output 1 evs <+: line (Input 0 evs) ∧ LastShort evs) ∨
7
(out = .exited .exitGroup 2 ∧
8
Output 1 evs = [] ∧ Input 0 evs = []) ∨
9
(out.KilledInWrite ∧
10
Output 1 evs <+: line (Input 0 evs)))
For those that end with exit code zero, this says that the program outputted on stdout exactly the expected string:
1
def line (name : List Byte) : List Byte :=
2
utf8 "Hello, " ++ name ++ utf8 "! admin: no\n"
This nails down that there is no way that a run that reaches main and ends with exit code zero could ever print something ending with “admin: yes”. As mentioned above, the statement is proven under some reasonable assumptions on the run, such as that the program is not running in a debugger that modifies the memory during the run — in that case, the conclusion would of course not be correct. Note that unlike the manual inspection, there is no assumption that the malloc calls behave as expected and return buffers that are disjoint from each other and disjoint from other memory that is in use — that is proven from the binary instead.
The following graphic shows which parts of the full binary are argued about in the proof.7 Most instructions can (provably) never be reached, so we don’t need to prove anything further about them.
It took weeks of effort to prove the above statement about the “admin” program. How much effort does it take to prove a second program, such as this “admin2” program, which, while similar, has an additional for loop to reject names with newlines, and also splits up the writes differently?
1
#include <stdlib.h>
2
#include <unistd.h>
3
4
#define NAME_SIZE 32
5
6
int main(void) {
7
char *name = malloc(NAME_SIZE);
8
volatile char *admin = malloc(1);
9
if (name == NULL || admin == NULL) return 2;
10
*admin = 0;
11
ssize_t n = read(0, name, NAME_SIZE);
12
if (n < 0) return 1;
13
for (ssize_t i = 0; i < n; i++) {
14
if (name[i] == '\n') {
15
write(2, "admin2: bad name\n", 17);
16
return 3;
17
}
18
}
19
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。