CS Paper Radar

Neuro-Symbolic Indirect-Call Analysis under Opaque Pointers

Kaixuan Li, Bozhi Wu, Jian Zhang, Peixin Wang, Ting Su, Yang Liu

cs.SE cs.PL ·submitted 2026-09-27 13:14 UTC · v4

Abstract

Resolving indirect calls is central to call-graph construction for C. Scalable type-based analyses such as MLTA use type information in LLVM IR to associate indirect calls with functions assigned to the corresponding structure fields. However, a single pointee type often misrepresents the memory a pointer addresses, and LLVM 17 removed pointee types in favor of opaque pointers. Therefore, field-sensitive analyses lose their matching key. Recovering the erased types restores the matching key but still misses the relation that the type encoded: which functions the program assigns to the field. We present Facet, to our knowledge the first analysis that reconstructs this dispatch relation over opaque IR. Facet identifies the structure field from which an indirect call loads its function pointer. It separately recovers the functions assigned to that field through initializers, stores, and aggregate copies. It then joins the two by field identity, without requiring an end-to-end value-flow path. Facet classifies proposed call-graph changes under distinct evidence rules for edge addition and removal and records the assumption behind each refinement. An LLM decides only the residual cases among symbolically bounded candidates. One analysis yields both a recall-preserving call graph and a refined call graph. On 14 C programs, Facet reduces the mean target-set size from 25.9 to 5.2 and raises observed recall from 0.79 to 0.99. Its recovered field identities agree with typed IR at 98.1% of jointly resolved sites. Applied to bug detection, the refined call graph found 17 deep bugs in C software from nginx to the Linux kernel, three of them latent for over a decade; 12 are confirmed.

Comment
Revised version with corrected formatting

Closest papers

Nearest neighbours by meaning across the whole index.

STILL: Recovering Lowered STL Semantics for LLM-assisted C++ Decompilation

cs.SE ·2026-08-26 ·Xiaohan Wang, Kevin Leach
top venue similarity 0.65
Abstract

LLM-assisted decompilation improves readability and re-executability, but still underperforms on stripped C++ functions that use the Standard Template Library (STL). Compilation, optimization, and symbol stripping remove or obscure source-level semantics such as container types and library-call structure, while traditional decompiler output often fails to recover them. We present STILL, a structured semantic interface that predicts function-level STL container semantics from stripped control-flow graphs and renders them as compact hints for LLM refinement. On StlBench, STILL predicts common container-level STL semantics, with the strongest cross-dataset results for stable string and vector slices. On stripped HumanEval decompilation, these hints enable DeepSeek-chat refinement to reach 28.4% executability, compared with 17.4% for no-hint refinement and 8.9% for raw Ghidra decompilation; hint utility is downstream-backbone-dependent, with decompilation-specialized models requiring lightweight adaptation to benefit from the same interface.

0.41

LOHRE: Execution-Grounded Type Recovery via LLM-Orchestrated Hybrid Analysis

cs.SE ·2026-11-11 ·Hao Jiang, Yujie Yang, Tao Li, Chenhui Cui, Liangfeng Xu +4 more
similarity 0.64
Abstract

Documenting stripped binary functions for security analysis requires recovering function interfaces and user-defined type (UDT) layouts from machine code. Existing large language model (LLM)-based methods face two limitations: they lack execution-based validation to detect inferred UDTs inconsistent with actual memory layouts, and may overlook evidence about shared UDTs across functions without direct call relationships. We present LLM-Orchestrated Hybrid Reverse Engineering (LOHRE), a framework that treats inferred UDTs as falsifiable hypotheses and tests them against program execution. LOHRE uses a hypothesize-validate-refine loop to test candidate layouts through paired dynamic slice emulation of baseline and mutated inputs. To reduce the cost of processing lengthy execution histories, the Execution-Depth Heuristic (EDH) compresses paired traces into an execution-depth difference and a summary of the tested field's observed uses. A cross-function knowledge base aggregates compatible UDT hypotheses and field-level confidence scores to guide testing and hypothesis refinement. We evaluate LOHRE on RealType at four optimization levels and a Windows remote procedure call (RPC) dataset. LOHRE achieves an average UDT Structural accuracy of 57.85% across RealType's four optimization levels and 35.6% on Windows RPC, outperforming the evaluated static baselines. Disabling dynamic validation reduces accuracy to 19.28% on RealType and 9.2% on Windows RPC. Removing the cross-function knowledge base reduces accuracy to 41.03% on RealType and 10.0% on Windows RPC. Replacing EDH's compressed feedback with full execution traces reduces recovery accuracy while increasing token use by 3.7 times and runtime by 3.0 times. These results indicate that execution-based validation, compact feedback, and cross-function evidence contribute to accurate and efficient UDT recovery.

0.30

RPyForth: Exposing a Call-Shared Data Stack to a Meta-Tracing JIT Compiler

cs.PL ·2026-09-20 ·Yusuke Izawa, Kota Hakamada
similarity 0.64
Abstract · 33 pages, 15 figures

Forth is a concatenative language whose words share one data stack across calls, with a depth and call effects that need not be known before execution. That leaves a meta-tracing JIT compiler with no stack location it can name: a cell is reached through the stack pointer, so its accesses stay in the compiled code, and declaring every cell of the stack array instead ties what the compiler carries to the capacity the array reserves rather than to the depth a program uses. We answer with a fixed-width window over the top of the stack, a shared spill holding every deeper cell, and a decoding function that joins the two, on top of which call-entry normalization and adaptive entry are policies. Decoding shows that all of them preserve the logical stack and that a trace exit rebuilds data-stack state bounded by the window's width, not by the stack's depth. RPyForth realizes this in an RPython interpreter covering Forth's Core word set, with two scalar fields and eight frame positions and no static stack-effect analysis, and RPyFactor realizes the same window for a subset of Factor. Exposing the window to the compiler, rather than merely caching cells in it, is what pays. With the layout and the call policy held fixed, annotating the window's fields makes eighteen Shootout kernels 1.44-1.45x faster and six Appbench applications about 1.60x faster on two x86-64 machines, and 1.42-1.56x in RPyFactor. How the window is shaped and whether calls normalize it matter much less, varying by program with no setting winning everywhere. As a complete system, RPyForth is faster than gforth-fast and SwiftForth on both suites and reaches 1.90-2.36x the speed of VFX Forth on the kernels, while the applications, whose stacks are deeper and whose calls are far more frequent, remain its weak point at 0.68-0.76x. All timings measure repeated execution of an already-loaded program.

0.30

Partial Borrows in Rust

cs.PL ·2026-11-16 ·Sasha Pak, Richard Willie, Umang Mathur, Fabian Muehlboeck, Alex Potanin
similarity 0.63
Abstract

Rust ensures memory safety by requiring exclusive access to mutably borrowed data. However, a borrow can prevent access to more data than necessary. For example, a method with an &mut self parameter borrows the entire struct, even when the method uses only some of its fields. Calling the method can therefore conflict with an existing borrow of a field the method never uses, causing Rust to reject the program. Resolving such conflicts can require programmers to compromise useful abstractions, make non-local changes to their programs, or worse, resort to unsafe code. We introduce view types, a backward-compatible refinement of reference types that specifies which fields a reference may access. This allows methods to partially borrow a struct, accessing only the fields they need without blocking access to the rest. We establish the first fully mechanized foundation for Aeneas in Rocq. Along the way, we uncover and fix gaps in the original semantics and proofs. Building on this foundation, we formalize partial borrows and prove the extended borrow checking sound. We implement view types in rustc and extend the Aeneas interpreter to support partial borrows. Our evaluation shows how view types systematically resolve borrowing conflicts across method boundaries at no runtime cost.

0.18

Taint Analysis via Heap-Aware Propagation

cs.LO cs.CRcs.PL ·2026-11-16 ·Yusen Su, Jorge A. Navas, Arie Gurfinkel
code/data similarity 0.62
Abstract · This is an extended version of the VMCAI 2027 paper, consisting of 31 pages. The artifact is available at https://doi.org/10.5281/zenodo.198…

Taint analysis for C depends on how precisely the analysis tracks tainted values as they flow through memory objects. Without field sensitivity, a tainted object field can spuriously taint an entire object, producing significant false alarms. In this paper, we present a field-sensitive taint analysis that combines Data Structure Analysis (DSA) for field-sensitive points-to information with a data-flow analysis for tracking explicit dependencies. We identify that existing DSA-style analyses lose precision on a common object pattern: a C struct object that mixes scalar fields with a flexible array member. When such an array is accessed with symbolic indices, DSA loses points-to field sensitivity for the entire object, inflating false alarms in the data-flow analysis. To address this, we propose I-DSA, which extends DSA by representing field positions as intervals, so that a pointer with symbolic bounds merges only the fields within those bounds. We further develop a sound data-flow analysis based on abstract interpretation. We implement I-DSA on top of SeaDSA and the data-flow analysis inside Crab. Our tool targets LLVM IR and supports configurable taint policies by instrumenting the IR with taint intrinsics. Our experiments show that I-DSA reduces the false alarms caused by this pattern at little cost in the pointer analysis, that SVF, an inclusion-based pointer analysis, shows a similar field-sensitivity loss, and that our taint analysis scales better than PhASAR on real-world programs.

0.46

Composable Rewrites for Layouts of Algebraic Data Types

cs.PL ·2026-11-14 ·Christophe Gyurgyik, Alexander J Root, Benjamin Driscoll, Gabriel Radanne, Fredrik Kjolstad +1 more
similarity 0.62
Abstract

Algebraic data types (ADTs) decouple the logical structure of data from physical layout choices that affect performance. For example, packing small fields into a word improves spatial locality, while storing co-accessed fields contiguously can enable vectorization. Such choices reinforce or undermine one another, with ramifications for compiler optimizations and memory management. Their interplay creates a combinatorial space of layouts with different runtime costs and memory footprints. The most favorable layout depends on the program's construction and destruction patterns, the characteristics of input data, and the target machine. Exploring this space requires control over layout decisions and a way to compose them while preserving program semantics. We provide both through rewrite rules over layouts, independent of any particular source language or bit-level encoding. Starting from a canonical layout derived from the ADT, these rules transform its representation while leaving the source program intact. We identify a local refinement criterion for proving each rewrite rule correct, so that layouts continue to represent every value and keep distinct values apart. Adding a new rule therefore only requires a proof satisfying this local criterion. We realize these rules in Isomer, a new pure functional programming language whose compiler specializes construction, pattern matching, and memory management to the chosen layouts. Using a default layout for all ADTs, Isomer achieves competitive performance against established functional compilers that automatically select layouts. Our rewrites further improve performance by tailoring layouts to each workload, permitting representations that prior work cannot attain or can only achieve through explicit changes to the source code.

0.44

Strict Capabilities with a PNVI Escape Hatch

cs.PL ·2026-11-16 ·Yihe Li, Sai Dhawal Phaye, Roland H. C. Yap, Trevor E. Carlson, Gregory J. Duck
position similarity 0.62
Abstract · 22 pages, 1 figure, 2 tables

Capability systems enforce memory safety by tying pointers to their originating allocations, preventing forgery, use-after-free, and out-of-bounds accesses. Yet conventional capabilities are simultaneously too strict and not strict enough for C: they reject common low-level idioms involving integer casts or raw pointer bytes, while failing to enforce type correctness and sub-object bounds. Proposed Provenance Not Via Integers (PNVI) semantics expose this tension by permitting representation-level manipulation while retaining strict rules for ordinary pointer operations. We argue that these requirements call for two interoperable abstractions rather than a compromise within one. Strict capabilities enforce provenance, liveness, type correctness, and (sub-)object bounds; ordinary capability operations preserve these invariants. Exposed representations are non-dereferenceable, integer-like values that support arbitrary integer and byte-level manipulation under PNVI semantics while retaining unforgeability guarantees. They carry no directly usable memory-access authority: converting an exposed representation back to a strict capability reconstructs provenance under PNVI rules and validates type and bounds before access. Thus, low-level C idioms can use an explicit escape hatch without weakening ordinary capability derivation. We realize this design using Fully Randomized Pointers (FRP) and dynamic type metadata. Evaluation on low-level pointer idioms, Juliet tests, and existing C benchmarks shows that strict type and sub-object safety can coexist with low-level pointer manipulation.

0.22

A Quantitative Interpretation of Useful Call-by-Value

cs.LO ·2026-10-29 ·Pablo Barenbaum, Delia Kesner, Mariana Milicich
similarity 0.61
Abstract

In this work, we present the first semantic interpretation of useful call-by-value evaluation through a non-idempotent intersection type system called U. One first contribution of this paper is a characterisation of termination of useful call-by-value evaluation via U-typability. That is, a term is typable in system U if and only if it terminates in the useful call-by-value strategy. As a second contribution, we show that system U provides a quantitative interpretation for useful call-by-value evaluation, offering exact step-count information for program evaluation. Even though the specification of the operational semantics of useful evaluation is highly complex, system U is notably simple. As far as we know, system U is one of the scarce quantitative type systems capturing exactly the substitution step-count for variables and abstractions in an open call-by-value strategy. Our third contribution is a termination-equivalence result between standard call-by-value, which may perform erasing reductions, and useful call-by-value, which is non-erasing. To establish this result, we introduce a non-erasing restriction of standard call-by-value, a refinement that serves as an intermediate calculus bridging standard and useful call-by-value. We show that all three calculi have the same termination behaviour, and hence induce the same observational equivalence.

0.29