CS Paper Radar

Bootstrapping Mutual Attestation with Kleene's Second Recursion Theorem

Takuma Imamura

cs.CR math.LO ·submitted 2026-08-21 02:02 UTC · v3
theory

Abstract

Remote attestation is a procedure by which a system (such as a Trusted Execution Environment) proves its own configuration to a remote peer. Here, the configuration includes the measurements (hash digests) of software components. When multiple nodes perform mutual attestation, each node must maintain the reference values for its peers' measurements. We refer to this as the reference-value bootstrapping problem for mutual attestation. In this paper, we formulate the problem as a fixed-point equation and solve it directly using Kleene's second recursion theorem. In our approach, nodes can reconstruct one another's source code, thereby allowing each node to derive the reference values at runtime. When a source code itself is deployed, as with a Python script, a node derives the peer's reference value directly from its reconstructed source. When a build artifact is deployed, as with AWS Nitro Enclaves, a node instead reproducibly builds the peer's artifact from its reconstructed source and derives the reference value from it. As a proof of concept, we develop transpilers in Python and Nix to generate mutually referencing programs. Using these transpilers, we demonstrate the mutual derivation of reference values for the two deployment models mentioned above. Our solution is architecture-independent, requires no trusted third party, and works with existing attestation stacks without modification.

Comment
Revised

Closest papers

Nearest neighbours by meaning across the whole index.

Attestable Audit: Property-Based Attestation for Proprietary Workloads without Artifact Disclosure

cs.CR ·2026-10-03 ·Takuma Imamura
published similarity 0.69
Abstract · Accepted at the International Workshop on Hardware and Architectural Support for Security and Privacy 2026 (HASP 2026), held in conjunction …

Trusted Execution Environments (TEEs) prove the integrity of code and data to a remote peer through remote attestation: the TEE issues an attestation report by signing, with a hardware-bound key, its configuration information, including measurements (cryptographic digests) of the code loaded inside it. A verifier appraises the report by matching these measurements against reference values. When the measured artifact is proprietary, however, the verifier cannot derive the reference values itself: it can only confirm that something with a given measurement is running inside the TEE---not that the program behaves as expected---forcing full trust in the reference value provider. We propose an architecture that closes this gap without disclosing the artifact, composing two TEE workloads: attestable build (Hugenroth et al., 2025), which binds a source code digest to a build artifact measurement, and attestable audit (proposed in this paper), which binds the same source code digest to the verdicts of automated audits---fuzzing, static analysis, AI code auditing, formal methods---executed inside a TEE. Both are instances of Confidential Computing Proofs: TEE attestation viewed as a hardware-backed zero-knowledge proof. Chaining the two certificates lets the verifier conclude that the running artifact was built from source code satisfying the audited properties, without disclosing either the source code or the build artifact. A proof-of-concept implementation on Intel SGX with the Gramine Library OS, running the Bandit security analyzer on Python code, demonstrates the practicality of the approach.

0.26

Synthesizing Proofs Using Proof Sharding and Exploration

cs.PL cs.SE ·2026-09-22 ·Seyed Armin Vakil Ghahani, Manos Kapritsos
theory similarity 0.62
Abstract

Distributed systems are hard to implement correctly, and subtle bugs can go undetected using traditional testing. Formal verification offers an alternative for proving the correctness of complex distributed systems. Despite previous efforts to automate and facilitate formal verification, it is still hard to integrate formal verification in software development. Programmers need to query the theorem prover repeatedly to find the correct proof of their system. This cycle of going back and forth with the theorem prover involves a lot of human intervention and is a barrier to adopting formal verification in software development. In this paper, we address the challenges of scaling formal verification in practice by reducing the human intervention required to find the correctness proof of a distributed system. We propose ProofSaX, an automated tool that shards large verification tasks and explores the proof search space for each shard independently to synthesize correctness proofs. We use controlled exploration when adding possible proof annotations to handle the search-space explosion problem. We evaluate ProofSaX on a variety of safety proofs for distributed systems. We show that ProofSaX can find the last proof annotation in 86 out of 103 proof-completion tasks, with runtimes ranging from one minute to two hours.

0.20

Vero: Can AI Agents Build Formally Verified Software Repositories?

cs.LG cs.AIcs.LOcs.PL+1 ·2026-08-13 ·Zhe Ye, Hantao Lou, Yuechun Sun, Peiyang Song, Zhengxu Yan +6 more
benchmarkcode/data similarity 0.62
Abstract

AI agents are increasingly used for programming, but do not provide any guarantee on the correctness of generated code. Verified code generation, in which an agent produces both an implementation and a machine-checked proof of its specification, offers a stronger path toward trustworthy AI-generated software. Existing benchmarks in this direction either focus on individual functions or only evaluate proof generation with provided implementations. It is still an open question whether agents can make coherent implementation and proof choices across real multi-module codebases. To bridge this gap, we introduce Vero, the first benchmark to evaluate joint implementation and proof synthesis at the repository level. Vero contains 43 multi-module instances sourced from real-world repositories spanning Python, Dafny, Verus, and Coq, and covering diverse domains from cryptographic protocols to distributed systems. Each instance consists of a multi-module Lean 4 repository with predetermined API interfaces, manually curated formal specifications, and reference implementations, supporting both proof-only and code-and-proof evaluation modes. To improve benchmark reliability, Vero also includes an audit mechanism where agents are allowed to formally prove unsatisfiability of provided specification or incorrectness of reference code, which surfaces and corrects latent code and specification errors during curation. We evaluate frontier coding-agent configurations with Lean toolchain access. The strongest agent fully solves only 27 of 43 instances and closes no specifications on the hardest repositories. Vero provides a concrete testbed for measuring progress toward repository-scale verified software synthesis, where current agents still fall short. We release the benchmark, curation pipeline, and evaluation harness at https://github.com/sunblaze-ucb/vero.

0.54

Blame-aware Recomposition for Secure Compilation Proofs of Low-Level Compartment Isolation

cs.PL cs.CR ·2026-10-19 ·Basile Schlosser, Jérémy Thibault, Catalin Hritcu
similarity 0.61
Abstract

The security guarantees of existing formally verified compilers for compartmentalized programs in unsafe languages like C stop at a rather high level, assuming a built-in protection mechanism and a block-based memory model. Verifying a concrete, low-level enforcement mechanism for compartment isolation is still a major challenge for current proof techniques. In particular, Abate et al.'s proof technique fails because one of their proof steps, recomposition, essentially requires hiding all information about the code of each compartment, which is not practically achievable at a low level. We propose an extension of their proof technique to a low-level setting where compartments can fully observe each other's code. To do so, we introduce an overlay semantics that allows us to characterize these observations as a form of undefined behaviour, and we use a novel variant of recomposition that we call blame-aware recomposition, which essentially allows recomposing executions as needed in the original high-level proof technique, even if the low-level context observes the code, because this context is ultimately going to be discarded. We apply this new proof to a compartment isolation mechanism that uses a programmable tag-based reference monitor.

0.26

Behavioral Containment: Source-to-Binary Function Matching for 1-Day Vulnerability Detection

cs.SE ·2026-11-19 ·Yifei Yang, Xuejiao Luo, Penghui Li
code/data similarity 0.61
Abstract

Vulnerabilities in reused open-source code often propagate into deployed binaries. Detecting them requires source-to-binary function matching, which locates the affected source function in a binary. Applying prior binary-to-binary approaches to this task would require compiling the source code with the same build configuration as the target binary, which is usually unavailable. Decompiling the binary does not make prior source-to-source approaches work either, because decompiled code differs substantially from the original source code. We observe that compilation transforms the code of a function but largely preserves its behavior. A binary function that implements a source function therefore contains its behavior, a property we call behavioral containment. Building on this, we present SBIND, which decompiles the binary and checks behavioral containment instead of comparing code. SBIND represents each function by behavioral paths, sequences of normalized operations from its entry to its exits, and aligns source paths with binary paths in order. To detect 1-day vulnerabilities, SBIND compares the binary with the vulnerable and the patched source only on the paths through the changed lines. On stripped binaries built with two compilers, two optimization levels, and four architectures, SBIND ranks the correct function first in 77.87% of 32,008 searches, against 45.69% for the state-of-the-art approach SBridge. On 26 1-day CVEs, SBIND reaches an F1 score of 0.70 on stripped binaries, against 0.51 for SBridge. Our replication of SBridge also revealed several issues in its implementation and evaluation, and its authors have acknowledged them.

0.17

PRA-TLS: Attestation of a Client Application for TEE

cs.CR cs.OS ·2026-10-05 ·Reina Sasaki, Yutaka Ishikawa, Atsuko Takefusa, Masato Oguchi
similarity 0.60
Abstract · 12 pages, 2 figures

Trusted Execution Environments (TEEs) are secure foundations for protecting sensitive information and executing computations over confidential data. Processing in an isolated execution environment (enclave) is invoked by an untrusted application in the Rich Execution Environment (REE). Then the enclave returns the execution results to the untrusted application. Even if the enclave has been attested, the boundary between the enclave and the untrusted application poses risks, such as tampering with input arguments or return values and manipulating the order in which the application invokes functions. Therefore, it is necessary to establish the authenticity and integrity of not only the enclave itself but also the application and its execution environment. In this study, we propose an attestation protocol, Portable Remote Attestation TLS (PRA-TLS), for a client application that invokes an enclave. We introduce a daemon that acts as an attester. PRA-TLS uses a trusted Attester Daemon to measure the state of the host environment and application code at runtime, providing these measurements as attestation evidence for verification by a remote Verifier. This mechanism allows the enclave to proceed only when the software environment is in the expected state and the application code is verified as legitimate. We define attack models and security requirements for the proposed protocol and formally evaluate its security using the Tamarin Prover. Furthermore, we implement a prototype of PRA-TLS using Intel SGX and evaluate its performance.

0.14

SpecTrum: Specification-Guided Differential Fuzzing for Ethereum Consensus Clients

cs.SE cs.CRcs.PL ·2026-08-18 ·Seokhun Jeong, Gyeongmin Dan, Sukyoung Ryu, Sungjae Hwang
top venue similarity 0.59
Abstract · 12 pages. Accepted at the 41st IEEE/ACM International Conference on Automated Software Engineering (ASE 2026)

Ethereum's consensus safety relies on independent consensus client implementations agreeing on every state transition. When they diverge due to implementation errors, the network can fork, finality can stall, and severe attacks are possible. To prevent such consensus divergences, Ethereum provides a Python reference implementation (consensus-spec), which acts as a specification, and a hand-crafted official test suite (spectests). However, as an executable implementation, Ethereum's specification defines validity implicitly through runtime behavior. As a result, it lacks a systematic way to ensure that all validity conditions are thoroughly evaluated. We present SpecTrum, a framework that addresses this problem in three stages. First, we introduce Consensus-SpecTec, a mechanized specification of the Ethereum consensus algorithm, which makes validity conditions explicit as if-premises. Second, we define premise coverage, a metric that measures which if-premises are evaluated to true and false across spectests. Third, we develop a specification-based test generator that extracts constraints on premises not evaluated to false by spectests and generates inputs to evaluate them. Applying SpecTrum to five major Ethereum consensus clients, we identify 27 cross-client divergence cases, 22 of which cannot be found without the premises inserted in our mechanization. All 27 cases reproduce across fork versions, and extending the mechanized specification to a new fork takes modest effort proportional to the specification difference.

0.42

Pre-QED: Environment Specifications for Agentic Verification

cs.SE ·2026-11-11 ·Tristan Lim, Haoxin Tu, Mehtab Zafar, Zhengxiong Luo, Abhik Roychoudhury
positiontheorycode/data similarity 0.58
Abstract · 8 pages, 4 figures. Website: https://pre-qed.github.io/

LLM agents are making formal verification practical at scale. Recently, many attempts have raised this as an enticing possibility. However, formal verification at scale is only meaningful if deep formal specifications capturing functionality are available for checking. Unfortunately, recent works seek to bypass this issue by using shallow specifications devised for purposes other than verification. OSS-Verify from Anthropic and Theorem, for example, reuses the fuzz harnesses of open-source libraries as specifications and has an agent prove that each harness never crashes. However, a fuzz harness follows a single sequence of API calls under a single calling context, so the resulting proof covers one usage scenario rather than the library. We argue that the bottleneck of agentic verification has shifted from how to prove to what to prove. Before zooming into verification at scale, we need deep environment specifications to prove, which is why we call our effort Pre-QED. We propose verification harnesses, executable harnesses that model all legal usages of an API, so that a proof about the harness is a proof about every well-behaved client. To construct them, we use an agentic workflow that extracts the API's usage contract from code / documentation, and uses Linear-time Temporal Logic (LTL) to rule out illegal call orders. We identify the challenges in proving verification harnesses and release our harnesses open-source as challenges for the community. The overarching vision is that verifying an open-source library should become as routine as fuzzing it, with a guarantee that covers every well-behaved client rather than a single scenario like a fuzzing harness.

0.42