DALEQ - Explainable Equivalence for Java Bytecode

Jens Dietrich, Behnaz Hassanshahi · 2025

Read DALEQ - Explainable Equivalence for Java Bytecode by Jens Dietrich, Behnaz Hassanshahi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01530.txt.

Introduction

Jens Dietrich and Behnaz Hassanshahi check whether rebuilt Java code truly matches the shipped code, with proof attached, in a paper from two thousand twenty-five. Secure rebuilds by big firms rarely match bit for bit. Hand checks of the gaps are slow and slip-prone.

Their tool turns bytecode into a fact base and smooths it with logic rules. Match calls then carry a written proof of the smoothing path. On near three thousand jar pairs, the tool cut hand work hard. It also found more true matches than two rival tools. Readers in supply chain safety get equivalence with receipts.

Catalog record

CREATORJens Dietrich, Behnaz Hassanshahi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-01530

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

DALEQ - Explainable Equivalence for Java Bytecode Jens Dietrich, Behnaz Hassanshahi Abstract The security of software builds has attracted increased attention in recent years in response to incidents like solarwinds and xz . Now, several companies including Oracle and Google rebuild open source projects in a secure environment and publish the resulting binaries through dedicated repositories. This practice enables direct comparison between these rebuilt binaries and the original ones produced by developers and published in repositories such as Maven Central. These binaries are often not bitwise identical; however, in most cases, the differences can be attributed to variations in the build environment, and the binaries can still be considered equivalent. Establishing such equivalence, however, is a labor-intensive and error-prone process. While there are some tools that can be used for this purpose, they all fall short of providing provenance, i.e. readable explanation of why two binaries are equivalent, or not. To address this issue, we present daleq , a tool that disassembles Java byte code into a relational database, and can normalise this database by applying datalog rules. Those databases can then be used to infer equivalence between two classes. Notably, equivalence statements are accompanied with datalog proofs recording the normalisation process. We demonstrate the impact of daleq in an industrial context through a large-scale evaluation involving 2,714 pairs of jars, comprising 265,690 class pairs. In this evaluation, daleq is compared to two existing bytecode transformation tools. Our findings reveal a significant reduction in the manual effort required to assess non-bitwise equivalent artifacts, which would otherwise demand intensive human inspection. Furthermore, the results show that daleq outperforms existing tools by identifying more artifacts rebuilt from the same code as equivalent, even when no behavioral differences are present. I Introduction Software is the foundation of modern digital infrastructure. Modern software systems are assembled from existing components, using automated processes like continuous integration and deployment. This has created new security problems as both components and processes can inject vulnerabilities into systems. Examples include solarwinds , codecov , equifax and log4shell [ 16 , 28 , 17 ] for compromised component, and xcodeghost , ccleaner , shadowpad , shadowhammer and xz [ 28 , 3 , 2 , 30 ] for compromised processes. Initiatives like reproducible builds [ 1 , 25 , 17 , 8 , 18 ] aim to enhance software supply chain security by rebuilding packages from source code independently and comparing the resulting binaries. The objective is to produce identical, bitwise equivalent binaries. Achieving this is not straightforward and often requires significant engineering effort [ 27 , 39 , 29 , 34 , 15 , 32 , 24 ] . Industry initiatives such as Google Assured Open Source ( gaoss ) and Oracle Build-From-Source ( obfs ), among others, also focus on rebuilding open-source artifacts from source on secure and hardened build services. While the goal is not necessarily to achieve bit-by-bit equality with the reference binaries built and released by the open-source developers (referred to as reference binaries ), substitutability remains a key requirement. I.e. a binary should be replaceable by the alternatively built binary without changing the behaviour of downstream programs. Substitutability is trivially achieved if the binaries are identical. If not, this becomes more complex, since behavioural equality is undecidable. However, it is still possible to under-approximate behavioural equality by devising an equivalence relation \simeq between binaries (i.e. in Java) where b_{1}\simeq b_{2} implies that b_{1} and b_{2} have the same behaviour. This idea was introduced in our previous work [ 12 ] , where we evaluated how equivalences based on existing tools, such as decompilers, disassemblers, and bytecode normalization tools, performed across various datasets. In this paper, we build upon that work and present daleq , a novel approach that not only establishes equivalence between Java binaries but also provides a provenance, i.e., an explanation of why two binaries are either equivalent or not. Conceptually, daleq is similar to normalization tools like jnorm [ 37 ] and JavaBEPEnv [ 43 ] , but with the added benefit of explainability features that help users gain confidence in the results. The technique presented here has been successfully applied to evaluate open-source artifacts used and built from source in Oracle’s Graal Development Kit for Micronaut (GDK) 1 1 1 https://www.oracle.com/developer/gdk-developers/ . This application underscores its practical impact on enhancing software supply chain security, addressing the critical need for product teams to verify that binaries remain uncompromised while maintaining functional equivalence. This paper presents the following contributions: 1. daleq provides provenance information supporting both equivalence and non-equivalence statements that can be used by security engineers to assess, validate and trust its outputs. 2. daleq is based on datalog, following a widely used approach in static program analysis. The rule-based constructions assures its high correctness, i.e., while there is no formal proof of soundness, it is highly unlikely that daleq will flag pairs of binaries with different behaviour as equivalent. 3. the comparative evaluation suggests that daleq significantly outperforms the state-of-the-art tool jnorm . This directly translates into significant cost savings of engineering time required to assess alternative build outputs. Since JavaBEPEnv is not available to us, we have not been able to evaluate daleq against this tool. This paper is organised as follows. We briefly review related work including publications and tools in Section II . This is followed by a detailed discussion of the design and implementation of daleq in Sections III and IV , respectively. We then evaluate daleq against two similar tools on a dataset consisting of jars from Maven Central, compared with jars built by gaoss and obfs in Section V . This is followed by a conclusion. II Related Work II-A Diff Tools Diffoscope 2 2 2 https://diffoscope.org/ is a general-purpose diff tool that can also be applied to (the content) of jar files. It directly uses bytecode, without applying abstractions. This makes it sensitive to even minor changes, and creates noise, e.g. it reports changes caused by platform specific new line separators in metadata files. It also reports file attributes. In contrast, daleq focuses on differences that influence program behaviour, and on minimising noise (i.e. differences that do not influence program behaviour). JarDiff 3 3 3 https://github.com/lightbend-labs/jardiff/ is a specialized tool designed to show differences in jar files built from Java programs . It shares some conceptual similarities with daleq , as both tools generate differences in bytecode abstractions through transformations, specifically using scalap and the asm textifier . However, daleq goes a step further by offering a more comprehensive approach, including detailed equivalence checks and advanced normalization techniques. While JarDiff focuses on establishing some equivalences (e.g., resolving constant pool ordering issues) without applying normalization, daleq ’s equivalence analysis involves additional steps, including the application of rules after extracting the EDBs. This makes daleq a more robust solution for analyzing and comparing Java binaries. There are several specialised diff tools available to check for changes in jars corresponding to different versions of the same program, including revapi 4 4 4 https://revapi.org/ , japicmp 5 5 5 https://siom79.github.io/japicmp/ , and clirr 6 6 6 https://github.com/ebourg/clirr . Those tools focus on detecting API changes violating Java source and binary compatibility rules that can lead to compile-

Read the complete text