oss-verify-proofs README

项目的 README,来自 github.com/theorem-labs/oss-verify-proofs。合并为一个 markdown 文件:README.md。

OSS Verify: proofs about OSS-Fuzz fuzz targets

release-check

OSS-Fuzz runs the fuzz targets of open-source projects to search for inputs that make them fail. This repository holds Rocq proofs that, for some of these fuzz targets, no such input exists within stated limits. Each proof is about compiled binaries, not source code. It shows that, on every input within the limits, the build with a sanitizer behaves like the plain build and the sanitizer never detects an error, or that every execution of a build ends with a status the statement allows. OSS Verify is a Theorem program; a maintainer enrolls a project at theorem-labs/oss-verify.

90 entry points in 32 libraries have proofs. The proofs are checked with Rocq 9.2.0. They are stated in LPS, a formal model of a Linux process that runs a RISC-V binary.

LPS is best effort and not complete. It describes part of Linux, and it makes some assumptions that it does not check. A proof is only as good as LPS. docs/semantics.md gives the design principles of LPS and its limits.

What is proved

library entry point sanitizer builds proved
boost-beast http_request ASan, UBSan, ASan+UBSan
boost-json fuzz_parse ASan, UBSan, ASan+UBSan
bzip2 bzip2_compress_target ASan, UBSan, ASan+UBSan
cgif cgif_file_fuzzer ASan, UBSan, ASan+UBSan
cgif cgif_rgb_fuzzer ASan, UBSan, ASan+UBSan
cjson cjson_read_fuzzer ASan, UBSan, ASan+UBSan
coturn FuzzStunClient ASan, UBSan, ASan+UBSan
double-conversion string_to_double_fuzzer ASan, UBSan, ASan+UBSan
fast_float from_chars ASan, UBSan, ASan+UBSan
glaze binary_reflection ASan, UBSan, ASan+UBSan
json-c json_object_fuzzer ASan, UBSan, ASan+UBSan
jsoncons fuzz_bigint ASan, UBSan, ASan+UBSan
jsoncons fuzz_bson_parser_max ASan, UBSan, ASan+UBSan
jsoncons fuzz_json_cursor ASan, UBSan, ASan+UBSan
jsoncons fuzz_json_encoder ASan, UBSan, ASan+UBSan
jsoncons fuzz_msgpack_encoder ASan
jsoncons fuzz_ubjson_encoder ASan, UBSan, ASan+UBSan
jsoncons fuzz_ubjson_parser_max ASan, UBSan, ASan+UBSan
leptonica bilateral_fuzzer ASan, UBSan, ASan+UBSan
leptonica colorfill_fuzzer ASan, UBSan, ASan+UBSan
leptonica edge_fuzzer ASan, UBSan, ASan+UBSan
leptonica fhmtgen_fuzzer ASan, UBSan, ASan+UBSan
leptonica graymorph_fuzzer ASan, UBSan, ASan+UBSan
leptonica grayquant_fuzzer ASan, UBSan, ASan+UBSan
leptonica jpegiostub_fuzzer ASan, UBSan, ASan+UBSan
leptonica kernel_fuzzer ASan, UBSan, ASan+UBSan
leptonica paintcmap_fuzzer ASan, UBSan, ASan+UBSan
leptonica pix1_fuzzer ASan, UBSan, ASan+UBSan
leptonica pix_orient_fuzzer ASan, UBSan, ASan+UBSan
libdiginet fuzz_codec ASan, UBSan, ASan+UBSan
libdiginet fuzz_decode UBSan
libdiginet fuzz_frame UBSan
libdiginet fuzz_transport ASan, UBSan, ASan+UBSan
libpcap fuzz_pcap ASan, UBSan, ASan+UBSan
libreac fuzz_boxreg ASan, UBSan, ASan+UBSan
libreac fuzz_ctrl ASan, UBSan, ASan+UBSan
libreac fuzz_decode ASan, UBSan, ASan+UBSan
libreac fuzz_disco ASan, UBSan, ASan+UBSan
libreac fuzz_grant ASan, UBSan, ASan+UBSan
libreac fuzz_identity ASan, UBSan, ASan+UBSan
libreac fuzz_knock ASan, UBSan, ASan+UBSan
libreac fuzz_pcap ASan, UBSan, ASan+UBSan
libreac fuzz_scene ASan, UBSan, ASan+UBSan
mbedtls fuzz_pkcs7 ASan, UBSan, ASan+UBSan
msgpack-c unpack_pack_fuzzer ASan, UBSan, ASan+UBSan
omx-clap-core fuzz_manifest ASan, UBSan, ASan+UBSan
omx-clap-core fuzz_preset ASan, UBSan, ASan+UBSan
omx-clap-core fuzz_state ASan, UBSan, ASan+UBSan
openssl bignum ASan, UBSan, ASan+UBSan
openssl bndiv ASan, UBSan, ASan+UBSan
openssl ct ASan, UBSan, ASan+UBSan
openssl echconfiglist_parser ASan, UBSan, ASan+UBSan
openssl hashtable ASan, UBSan, ASan+UBSan
openssl pem ASan, UBSan, ASan+UBSan
openssl punycode ASan, UBSan, ASan+UBSan
plugin-hostd fuzz_command ASan, UBSan, ASan+UBSan
plugin-hostd fuzz_reply ASan, UBSan, ASan+UBSan
pupnp FuzzHttp ASan, UBSan, ASan+UBSan
reac-pw fuzz_headamp ASan, UBSan, ASan+UBSan
reac-pw fuzz_link ASan
reac-pw fuzz_pin ASan, UBSan, ASan+UBSan
reac-pw fuzz_qdisc ASan, UBSan, ASan+UBSan
reac-pw fuzz_rate ASan, UBSan, ASan+UBSan
reac-pw fuzz_role ASan, UBSan, ASan+UBSan
reac-pw fuzz_segconf ASan, UBSan, ASan+UBSan
reac-repacer fuzz_egress UBSan
reac-repacer fuzz_lock UBSan
reac-repacer fuzz_uci ASan, UBSan, ASan+UBSan
reac-repacer fuzz_wire ASan, UBSan, ASan+UBSan
simdjson fuzz_atpointer ASan, UBSan, ASan+UBSan
simdjson fuzz_dump ASan, UBSan, ASan+UBSan
simdjson fuzz_dump_raw_tape ASan, UBSan, ASan+UBSan
simdjson fuzz_element ASan, UBSan, ASan+UBSan
simdjson fuzz_implementations ASan, UBSan, ASan+UBSan
simdjson fuzz_minifyimpl ASan, UBSan, ASan+UBSan
simdjson fuzz_ondemand ASan, UBSan, ASan+UBSan
simdjson fuzz_parser ASan, UBSan, ASan+UBSan
simdjson fuzz_print_json ASan, UBSan, ASan+UBSan
simdjson fuzz_utf8 ASan, UBSan, ASan+UBSan
skcms iccprofile_info ASan, UBSan, ASan+UBSan
speex speex_decode_fuzzer_float ASan, UBSan, ASan+UBSan
spirv-tools spvtools_binary_parser_fuzzer ASan, UBSan, ASan+UBSan
tinyobjloader fuzz_tobj_c ASan, UBSan, ASan+UBSan
varnish esi_parse_fuzzer ASan, UBSan, ASan+UBSan
yajl-ruby json_fuzzer ASan, UBSan, ASan+UBSan
zlib checksum_fuzzer -
zstd fse_read_ncount ASan, UBSan, ASan+UBSan
zstd huf_decompress ASan, UBSan, ASan+UBSan
zstd simple_decompress ASan, UBSan, ASan+UBSan
zstd zstd_frame_info ASan, UBSan, ASan+UBSan

index/PROOFS.md has one row for each entry point: the statements proved, the system-call failures they allow, the binaries, and where the proof is.

Every proof is about the binaries of this release and the statements under projects/. All of them use one LPS version and one static AddressSanitizer (Versions). docs/origin.md says how the proofs were made: the proving task, its submissions and its checker, and how a proof enters this repository.

The theorem, in words

Every proof here proves one or more agreement statements, halts statements, or both. There is one agreement statement for each sanitizer build: AddressSanitizer (ASan), UndefinedBehaviorSanitizer (UBSan), or both (ASan+UBSan). An agreement statement says:

On every input on which the plain build stays within its memory budget, neither build reaches an error, and the plain build and the sanitizer build have the same set of observable behaviours.

So an agreement proof rules out every error that the sanitizer build detects, on every input that the statement covers.

A halts statement is about one build alone. It says that on every covered input, every execution of that build ends, and that it ends with a status the statement allows: status 0 or 2 for most harnesses, status 0, 2 or 78 for a harness that lists the inputs it turns away (rejects), and any status for espeak-ng's ssml-fuzzer. Its premises are its own: the build is never refused memory for exceeding 16 GiB, and the environment refuses nothing that the process's state does not force. A _halts_may_fail statement drops both premises and allows any status.

If the harness checks a property with assert(), abort() or a trap, and the check is in the binary, an agreement proof shows that the property holds on every covered input. A halts proof shows it only for the checks that the fuzz target's page names: a check seen in the binary, of a fuzz target whose linked code installs no handler that could end a failed check with a status of its own (failure_handlers: none). A failed check of these kinds then kills the process, which no halts statement allows. A check that ends the process with exit() instead is shown only when the call reaches the driver's exit guard (exit_reaches_guard: true), which ends the process with status 77 whatever status the source passes, and only by a halts statement whose allowed statuses leave out 77 (docs/facts.md, docs/exploring.md, docs/statements.md).

The Rocq definitions are in theories/Shapes.v. Each agreement and halts form is proved equal to its LPS definition: an agreement form to strong_universal_error_free_T_budgets or one of its variants, a halts form to halts_allowed_T_scfg_budgets or halts_allowed_T_scfg. docs/statements.md explains each form.

What a proof does not say

Versions

item version
Rocq 9.2.0, the official release (opam package rocq-core). The proofs load their libraries with plain Require.
checker image ghcr.io/theorem-labs/oss-fuzz-theorems-checker@sha256:063f93261f11ba449f1c3825884fadc65cf1fc836d4a3ee534633211abbdc3eb. It holds Rocq, LPS with its elf-snapshot tool, the Rocq libraries that the proofs use, dune and Python 3, and no proof automation (toolchain/checker.Dockerfile).
LPS rocq-linux-process-semantics commit f1006fe81783, for every statement and every proof (docs/semantics.md)
static AddressSanitizer static-asan commit b0506135: the published source of the static AddressSanitizer that built every ASan binary of this release (docs/building.md)
OSS-Fuzz bd2ce219
axioms only the axioms in toolchain/allowed-axioms.txt: the primitive integer, array and string types of Rocq with their specifications, and six axioms of the standard library (classic, functional_extensionality_dep, constructive_indefinite_description, propositional_extensionality, sig_forall_dec and sig_not_dec)

Check a proof

You need Docker, zstd, and Python 3 with the packages tools/oft/requirements.txt pins (PyYAML; for ./oft lint, also idna). The checker image holds Rocq and LPS, but not PyYAML, so the commands below mount it. On 16 cores, one proof check needs up to 20 GiB of memory. It compiles one file per core, so more cores need more memory; docker run --cpuset-cpus limits the cores. --ulimit stack=-1:-1 gives the container an unlimited stack hard limit, so the check gets the 2 GiB stack it asks for; under a lower limit it still runs, with less stack, and it prints the stack it got (docs/checking.md).

git clone https://github.com/theorem-labs/oss-verify-proofs && cd oss-verify-proofs
./oft fetch coturn                   # the project's binaries, each checked against its SHA-256
python3 -m pip install --require-hashes --target "$HOME/oft-pydeps" -r tools/oft/requirements.txt
docker run --rm --network none --ulimit stack=-1:-1 -u "$(id -u):$(id -g)" -e HOME=/tmp -e PYTHONPATH=/pydeps \
  -v "$HOME/oft-pydeps:/pydeps:ro" -v "$PWD:/work" -w /work ghcr.io/theorem-labs/oss-fuzz-theorems-checker@sha256:063f93261f11ba449f1c3825884fadc65cf1fc836d4a3ee534633211abbdc3eb \
  ./oft check coturn/FuzzStunClient --parts statements,proofs

oft check does these steps. It checks each binary against its SHA-256. It builds the memory images and the statements. It compiles each proof. It compiles a small wrapper that gives the proof's theorem the type of the statement. Then it reads what Print Assumptions prints for the wrapper, and it refuses every assumption that is not in the allowed list (docs/checking.md).

CI runs the same check. The release-check workflow checks what each push to main changes, and the badge at the top shows its result. The pr workflow checks what a pull request changes. A publication checks the parts whose content keys it changes. Every Monday the weekly workflow checks every statement and every proof, with no cache; after a release, it also checks the fuzz targets of the projects whose files that release attached (docs/checking.md).

How the binaries are built

Each binary is a static riscv64 Linux program, built with clang 20.1.8 against musl. An entry point has up to four builds: plain, ASan, UBSan and ASan+UBSan. docs/building.md gives the compiler flags and the sanitizer settings. docs/running.md tells you how to run a binary and what its input file holds.

Each proof has a build record in projects/<project>/<harness>/proofs/provenance/. The record gives the upstream repository and commit, the harness file, the recipe (for a port-built project, the OSS Verify port's build manifest and its files for the project), the compiler, the builder image, the static AddressSanitizer commit, the compiler and linker flags, the SHA-256 of each binary, and the licences. docs/reproducing.md tells you how to rebuild a binary and compare its SHA-256.

Each project's published binaries are attached to the release as one archive, and each binary is pinned by its SHA-256 in its harness.yaml. Where a recipe-built project's page names them, the project's upstream source trees are attached with the build recipe its binaries were built with, in the releases the page links (the source trees beside the binaries, or in a second release, v<release>-src, since a GitHub release holds at most 1,000 files); together they rebuild the binaries (docs/reproducing.md). A port-built project's page names its source trees and its port archive when it attaches them, as it must for a GPL or LGPL binary; the port archive holds the port's build scripts and the source of the driver in its binaries. The port's tools/check builds them again with Docker and fetches the source trees over the network, not from the attached archive (docs/reproducing.md).

Explore the proofs

docs/exploring.md points to what the proofs show beyond "no sanitizer error": properties that the harnesses check, and lemmas about what the library code computes. It also tells you how to find the machine-generated data in a proof.

Statements for OSS-Fuzz fuzz targets

This repository also states theorems about many OSS-Fuzz fuzz targets, proved or not. For each of the 1,381 projects in OSS-Fuzz there is a directory under projects/. It also has project directories for libdiginet, libreac, omx-clap-core, omx-dsp, plugin-hostd, reac-pw and reac-repacer; OSS-Fuzz has no project for them. We can build the fuzz targets of 427 of these projects. 2,148 of their 5,290 fuzz targets have statements in this release; index/STATUS.md says why the others do not. Each of these fuzz targets is compiled up to four ways (2,176 of the 2,183 harnesses have all four), and each build gets Rocq statements about those exact bytes. These are statements, not results: 526 are proved, some are known to be false, and proofs are added as they are found.

In this release: 20,421 statements: 526 proved, 63 known false (56 counterexamples, 7 false (witnessed)), 3 suspected false, 229 blocked by the model, 0 withheld (0 waiting for their source bundle, 0 not published yet), 19,600 open. analyses/known-issues.md lists every statement that is not open or proved, with the reason.

There are four kinds of statement: a build halts; a sanitizer build agrees with the plain build; the two builds disagree on at most a fraction b of a stated input distribution; and the inputs on which they agree are decidable (docs/statements.md). One example:

lzo/lzo_compress_target/plain_halts: on every input on which the plain build is never refused memory for exceeding 16 GiB, and when the environment refuses nothing that it is not forced to (both are premises), every execution exits with status 0 or 2. The harness lzo_compress_target asserts that for compressible input (compressed_len < size), lzo1x_decompress into size+1 bytes must return LZO_E_OK and produce exactly size bytes. ONLY THE LENGTH is compared: the decompressed content is never memcmp'd against the input, so a decoder that returned the right number of wrong bytes would pass, so a proof shows that these hold on every input it covers.

Definition plain_halts : Prop :=
  halts_within_budget Budgets.Standard.lim_source Exits.ok_or_refused Images.plain.
status projects
available 434
language pending 781
not yet built 97
needs model support 3
no compiler 3
no harness 32
excluded 6
held 32
all projects 1,388

The 434 available projects have 2,183 harnesses with statements and 20,421 statements; 8,718 binaries are attached to this release or an earlier one, and 0 more are withheld. index/STATUS.md lists every project; index/*.tsv has the same data for scripts.

To prove or refute a statement, see docs/proving.md and CONTRIBUTING.md. A counterexample that shows a bug in a library goes to that library first (SECURITY.md). To enroll your own project, see theorem-labs/oss-verify.

What you have to trust

docs/trust.md says what each of these covers.

Repository layout

path contents
projects/<project>/<harness>/ the facts (harness.yaml), the statements (Statements.v), the images (Images.v), the harness page, and, for most harnesses, a copy of the harness source (source/)
projects/<project>/<harness>/proofs/<statement>/ the proof of one statement, and its proof.yaml
projects/<project>/<harness>/proofs/provenance/ the build record of that harness's binaries
projects/<project>/<harness>/proofs/lib/ the lemmas that the proofs of that harness share
theories/ the statement forms (Shapes.v), the image library, and the input-file format (Driver.v)
index/ tables of every proof, project, harness, statement and binary
toolchain/ the Dockerfiles of the checker and runner images, which release.yaml pins by digest, the allowed axioms, and the list of LPS files
tools/oft/ the oft tool: fetch, generate, lint and check
tests/ a generator of toy binaries, and controls that the checker must accept or refuse
projects/<project>/<harness>/counterexamples/ inputs that make a binary break a statement, each with a control input
analyses/ the checks that the harnesses make (harness-checks/), and every statement that is not open or proved (known-issues.md)
LICENSES/ licence texts of proof files made from proofs under another licence
docs/ the documentation

Citing

CITATION.cff. A statement is cited as project/harness/statement@r<revision>, for example lzo/lzo_compress_target/plain_halts@r1. Until LPS is released, revisions are provisional (docs/versioning.md).

Licence

What we wrote is under the MIT licence (LICENSE): the statements, the tools, the documentation and our proofs. Proofs that we made from proofs that Anthropic licensed under the Apache License 2.0 or the MIT licence, at the recipient's option, keep those licences. The licence texts are LICENSES/anthropic-proofs-LICENSE and LICENSES/anthropic-proofs-LICENSE-MIT and the notices are LICENSES/anthropic-proofs-NOTICE; the build record of each such proof names these three files (docs/licensing.md). The binaries, the source archives and the harness copies keep their own licences (NOTICE). This project is not affiliated with or endorsed by Google or the OSS-Fuzz project.

oss-verify-proofs (theorem-labs/oss-verify-proofs)

正在搜索数据库…

这是什么?这是一个由机器检查的 Rocq 证明仓库。这些证明表明:在规定的输入限制内,OSS-Fuzz 模糊测试目标被编译为静态 RISC-V 二进制文件后,不会触发某些错误,或总是以允许的状态码结束。
这是可以导入的库,还是需要我检查的一组证明?这是一组关于已编译二进制文件的形式化陈述和 Rocq 证明,而不是源代码。没有可以导入到你自己代码库中的内容,只有可供阅读或重新验证的证明。
我该如何自己检查其中一个证明?克隆仓库,运行 './oft fetch ' 下载该项目经 SHA-256 校验的二进制文件,然后在所提供的 Docker 检查器镜像中运行 './oft check / --parts statements,proofs'。
验证证明需要安装哪些软件?Docker、zstd,以及 Python 3 和 tools/oft/requirements.txt 中固定版本的软件包(PyYAML,另外还有用于代码检查的 idna)。Docker 检查器镜像已内置 Rocq 9.2.0 和 LPS 语义模型。
这里的证明是否意味着底层库没有缺陷?不是。证明只排除了 sanitizer 能够检测到的错误,范围仅限于某个入口点可达的代码,并且仅针对这些确切的静态 riscv64/musl 二进制文件,且须在规定的内存预算内。错误结果、内存泄漏以及 x86-64 构建均不在覆盖范围内。
目前已覆盖多少个模糊测试目标和库?已有证明的入口点共 61 个,涉及 26 个库,包括 openssl、zlib、simdjson、leptonica、zstd 和 boost-beast。
要相信一个证明,我需要信任哪些内容?你需要信任 Rocq 的内核、Linux/RISC-V 进程的 LPS 模型、经 SHA-256 固定的二进制文件,以及 toolchain/allowed-axioms.txt 中列出的公理。这些公理包括 Rocq 的原始类型,外加六条标准库公理。
检查一个证明需要多少硬件资源?在 16 核机器上,单次证明检查最多可能需要 20 GiB 内存,因为它每个核心编译一个文件。容器还需要将栈的 ulimit 设为无限制,以供 Rocq 使用。
一致性陈述(agreement statement)与停机陈述(halts statement)有什么区别?一致性陈述证明普通构建与 sanitizer 构建的行为相同,并且在所有覆盖的输入上都不会出错。停机陈述则额外证明构建的每一次执行都会以允许的退出状态结束。
大小
4 GB
星标
220
时长
27天
提交 · 90 天