Evading TLSH Malware Detectors Through Combination, Not Invention

Hashing is often used to compute a digest of a file. Cryptographic hashing gives very different digests to files that differ by even a single bit, so it can detect tampering. Locality-sensitive hashing does the opposite: similar files get similar digests, which is useful for clustering binaries, since variants of the same malware family land close together in the hash's output space. If those clusters also sit far enough from benign files, a classifier can be trained directly on the digests to tell the two apart. Often, a simple linear classifier is enough for that, since the hash construction already preserves the statistics that separate malware from benign files (what those statistics actually mean is a separate question). The result is a simple, efficient malware detector: the digest supplies the features automatically, and since its size doesn't depend on the file's size, the approach scales to files of any size.

There are two families of these hashes.

Learnt hashes are trained. A neural network (an autoencoder, a Siamese network, or a contrastive architecture) learns from pairs of files known to be related or unrelated to map each file to a compact code, such that related files land close together, as in a Siamese denoising autoencoder trained on malware pairs. The hash doesn't have to be trained on its own either: it can be learnt jointly with the downstream classifier, as a standard embedding layer, so the code is shaped directly by what's useful for telling malware from benign files rather than by a separate similarity objective. This is flexible and can pick up semantic similarity that a hand-designed rule would miss, but it costs a forward pass through a network, needs training data, and needs enough compute to run that network.

Static (or data-independent) hashes are not trained at all. TLSH, ssdeep and sdhash approximate the distribution of byte co-occurrences, coarsely and irrespective of what those bytes mean: a single deterministic pass over the file builds a histogram, with no parameters to fit and no training data. A quantized version of this coarse histogram is what actually gets compared. That simplicity is why they are used under a tight compute and memory budget. SIMBIoTA-ML, for instance, computes TLSH digests of embedded IoT ELF binaries and classifies them with a lightweight random forest on top, at a little above 1 ms per file. TLSH is a reasonable choice here: it is fast, and robust enough that a handful of byte differences between two variants of the same malware family still yields similar digests. On the CUBE-MALIoT-2021 benchmark, SIMBIoTA-ML reaches a true-positive rate of about 95% at a false-positive rate below 1% on ARM benign samples.

Is that robustness actually a weakness?

This same robustness can be turned against the detector. If changing a few bytes in a malware binary preserves its malware functionality but makes the detector recognise it as benign, that's evasion. This kind of problem shows up a lot in machine learning, and it's not new: researchers first found it in spam filters, then later, more famously, in image classifiers, and most recently in LLM jailbreaks. The question here is the same: can an attacker change some bytes in a working malware so it still runs and still does its (malicious) job, but its digest ends up on the benign side of the classifier's decision line?

Where the attacker can change bytes decides how hard the attack is, and how easy it is to prevent.

Appended bytes are the easiest target: bytes are added at end of the file that the loader never runs. They're just as easy to defend against, too, by stripping the binary, or hashing only the part the ELF headers say gets loaded.

Bytes inside the code or data are the hardest to defend against, but also the most expensive to attack. Any change there risks breaking the program, so the attacker can't just flip a byte. The changes need to preserve behavior, like inserting dead code or jumps over the adversarial modifications. Checking that the binary still works afterward can be expensive too.

ELF gap bytes sit in between. Every ELF binary have gap bytes (or padding): bytes that aren't part of the ELF header, the program header table, or any PT_LOAD segment. These bytes never enter the program's memory and can't affect its behavior, and consequently, the attacker can set them to anything. This is more covert than appending bytes, since it doesn't change the file size and is harder to spot. It's also more limited: gap bytes are fixed in number by the binary's layout, so the attacker faces a hard limit on the number of modifiable bytes. Prevention is only slightly more difficult than stripping append-only bytes, since it needs the whole ELF header and program header table parsed instead of finding one boundary, but it's still far cheaper than defending the code or data sections, which requires understanding what the bytes do rather than just where they are. That middle ground is why we focus on gap bytes here: the attacker reads the gap intervals off the ELF and program headers and only edits the bytes there.

How TLSH actually works

TLSH belongs to the same family as sketching schemes more generally: it slides a small window over the file, maps byte patterns to a fixed number of bins, counts how many land in each bin, and summarizes the resulting histogram. Specifically, TLSH slides a 5-byte window across the file, so one byte of the file can affect several bin counts. For each window position it forms six triplets of bytes using six salted patterns, and passes each triplet through a fixed Pearson permutation table, which produces a value in 0-255 identifying one of 256 possible buckets. TLSH's standard configuration keeps counts for all 256 buckets but only uses the first 128 of them when building the final digest.

The bucket of a triplet is a deterministic function of its three byte values. Determinism is what makes the hash reproducible, and it is also what lets an attacker predict, byte for byte, how the histogram changes.

The raw histogram is not, however, the digest. TLSH quantizes each bucket count into a 2-bit code using three thresholds, the quartiles $q_{1} \leq q_{2} \leq q_{3}$ of the histogram itself. A count at or below $q_{1}$ gets code 0, a count up to $q_{2}$ gets code 1, a count up to $q_{3}$ gets code 2, and anything above $q_{3}$ gets code 3. Together with three header values (the file length and two quartile ratios), this yields the 131-dimensional feature vector that forms the final hash output.

The thresholding is the step that matters for an attacker and makes evasion challenging. In the figure above, $q_{1} = 33$ , $q_{2} = 44$ , $q_{3} = 58$ . A bucket with count 50 has code 2. Add one triplet to it and the count becomes 51, and the code is still 2. It stays 2 all the way until the count exceeds 58. A single-byte edit moves at most a few dozen triplets by one bucket each, so it changes some counts by ±1, but only the buckets that happen to sit right at a threshold change their code. In a quick check on a 140 KB ELF, about nine in ten random single-byte edits left the entire feature vector unchanged (on a much smaller 14 KB file it was about half).

As we'll see below, that is the core difficulty of attacking a sketch-based detector: thresholding means the attacker has no information about how the gap bytes should be changed to cause misclassification, since most candidate moves produce exactly zero change in the attacker's objective function.

Formalizing the evasion problem

The goal is to modify only the gap bytes so that the hash computed on the modified binary is classified as benign by an already-trained classifier. Write the file as a vector of bytes $x \in {0, \dots, 255}^{n}$ , with original bytes $x_{0}$ . Let $G$ be the set of modifiable gap positions, and let each modified byte stay within an $ε$ -ball of its original value to limit the search space, $δ = round (ε \cdot 255)$ . The feasible set is then

X = {x : x_{i} = x_{0, i} for i \notin G; | x_{i} - x_{0, i} | \leq δ, x_{i} \in [0, 255] for i \in G} .

Let $Φ (x)$ be the TLSH feature vector (the length value, the two quartile ratios and the 128 quantized bucket codes, 131 dimensions in all). The construction is public, so the attacker can compute $Φ (x)$ for any candidate $x$ . Since gap edits do not change the file length, the length value is constant, and only the two ratios and the 128 codes can move.

Let $f_{T}$ be the target classifier, which outputs a malware score. The attacker observes it only through its decision $D_{T} (x) = 1 [f_{T} (Φ (x)) \geq 0.5]$ , where $1$ means "malware". The attacker's goal is to find a feasible file that the target model calls benign:

find x \in X such that D_{T} (x) = 0, i.e. min_{x \in X} 1 [f_{T} (Φ (x)) \geq 0.5] .

This is a constrained discrete optimization over an exponentially large ( $(2 δ + 1)^{| G |}$ candidates) but bounded neighborhood of $x_{0}$ . Note that the objective the attacker can actually evaluate is a 0/1 verdict, which is flat almost everywhere. If the attacker could read the score $f_{T} (Φ (x))$ they could minimize it directly, but a deployed detector reveals only its decision.

First-order or zeroth-order?

There are, broadly, two ways to attack the optimization problem above. First-order methods use the gradient of the loss with respect to the input to pick a direction. They are fast because that gradient tells you, in a single pass, how every coordinate (gap byte) should move. Zeroth-order methods need no gradient: they query the function at chosen points and use only the returned values. This is slower, but it is the only option when a gradient isn't available.

Here a gradient is unavailable for three reasons:

The target is a black box. We can't backpropagate through $f_{T}$ that we don't know, and we never observe the loss, only the final decision.
The input is discrete. $x$ is an integer vector, not a continuous one, so there is no continuous direction to differentiate along.
The function is flat. Even if we pretended the input were continuous, $f_{T} \circ Φ$ is piecewise constant almost everywhere because of the quantization step in TLSH, so its "gradient" is zero wherever it is even defined.

The textbook remedy is to train a local, differentiable approximation of the target detector and attack that with gradient methods such as PGD. In our experience this approach didn't work. We therefore stay zeroth-order: we evaluate candidate byte values and compare results, and never differentiate.

We still build a local approximation of the target model (assuming we have similar training data), but not to get a gradient out of it: the point is to fix the insensitivity of TLSH to small changes. Since that insensitivity comes from quantization, we build a surrogate that shares TLSH's construction exactly, right up to the point of quantization, and stops there. This surrogate is a second classifier $f_{E}$ , trained on the normalized, un-thresholded histogram

\hat{h} (x)_{b} = \frac{h (x)_{b}}{\sum_{b^{'}} h (x)_{b^{'}}}

instead of the quantized histogram ( $h (x)_{b}$ is the count in bucket $b$ , and both sums run over the 128 kept buckets). Nearly every byte edit moves several triplets between buckets, so $\hat{h}$ , and the surrogate's loss $L_{E}$ on it, changes with essentially every move. The surrogate is still non-differentiable, since the bucketing step assigns each triplet to a bucket by Pearson hashing, so bucket's count change abruptly rather than continuously. But that's no longer a problem, because we're doing zeroth-order search, which never needed a gradient in the first place: every query now returns informative feedback about whether that move helped (decreased the loss), instead of the flat non-answer the real quantized target would give.

Then the recipe is simple: attack the local surrogate with a zeroth-order method (no gradient computation involved), and hope the attack transfers, so that the same edits that fool the surrogate also fool the target detector.

Why normalize the histogram?

Raw, unnormalized bucket counts scale with the size of the file. A file of $n$ bytes produces $6 (n - 4)$ triplets, so every count grows roughly linearly with $n$ : on the two ELF files behind our check above, the median bucket count was 44 for the 14 KB file and 2,849 for the 142 KB one.

TLSH itself is immune to this, since its thresholds are the histogram's own quartiles: a code says where a count sits relative to the others, not its absolute size. Scaling all counts by a common factor scales $q_{1}, q_{2}, q_{3}$ the same way and leaves every code unchanged. (File size enters TLSH only through the separate length value, which gap edits can't touch.)

The surrogate should see the same thing. A linear classifier on raw, unnormalized counts would wrongly decide based on file size instead of byte statistics (shortcut learning), its logit would saturate on large files while being huge on small ones, and model weights fitted on one corpus of files would fail to transfer to files of another size, exactly the transfer the attack depends on.

Normalization turns $\hat{h}$ into a distribution over buckets (the fraction of the file's triplets that fall into each bucket). This is a scale-free quantity, and it plays the same role for the surrogate that the quartiles play for TLSH: it removes the file size and keeps the shape of the histogram. It doesn't reproduce the quantization, and that's the point: keeping it smooth is what gives the search a direction.

The attack: a greedy approach

A greedy coordinate-wise search works as follows: at each step, take one byte position, try every legal value for it on the local surrogate $f_{E}$ , and keep whichever value minimizes the surrogate loss. It's an accept-the-best-candidate loop, similar to the one in GCG for LLM jailbreaks.

Specifically, the attack proceeds as follows:

Sample $k$ positions uniformly at random from the gap positions $G$ .
For each sampled position $p$ , evaluate the surrogate loss $L_{E} (v)$ for every legal value $v$ within the $ε$ -ball of $x_{0} [p]$ , using the incremental histogram update.
Set that byte to $v_{min} = \arg min_{v} L_{E} (v)$ .
Query the target model $f_{T} \circ Φ$ with $v_{min}$ and stop if it says "benign"; otherwise repeat the above steps, up to $n$ times.

Notice that the search itself in Step 2 and 3 never touches the target model: all candidate evaluations run against the surrogate. The target is queried once per iteration, only to read a decision and stop early. In fact, those intermediate queries can also be skipped: since the surrogate drives the search, the attack can instead be run for a fixed number of iterations with the target queried only on the final file.

Why greedy: the incremental histogram update

Steps 2 and 3 can be computed very efficiently without recomputing the whole histogram from scratch for each candidate value $v$ . A byte at position $p$ only participates in the sliding windows that contain it, at most five windows of six triplets each, so changing that byte affects at most 30 of the file's $6 (n - 4)$ triplets. We know exactly which histogram buckets those 30 triplets fall into, so we can remove their old contribution and add the new one instead of rebuilding the histogram: an update costs $O (30)$ rather than $O (n)$ .

Evaluating all $2 δ + 1$ candidate values at one position then costs roughly $(2 δ + 1) \times 30$ operations. For $ε = 0.1$ ( $δ = 25$ , so 51 candidates) that's about 1,500 operations, against $(2 δ + 1) \times n$ , roughly 50 million operations, for naively recomputing TLSH from scratch at every candidate on a 1 MB file. This cheap, incremental update is what makes greedy search such a natural fit here. Compare it with a genetic algorithm, whose crossover step changes many bytes at once: each offspring can differ from its parent in many places and needs an $O (n)$ histogram rebuild in the worst case. This points to a more general attack strategy, since many counting-based sketches, not just TLSH, build histograms whose additive structure supports the same kind of incremental update.

The only approximation left in the greedy algorithm is which positions get updated each round (Step 1). Checking all $| G |$ positions in every iteration would be far too slow, so we sample a random subset with size $k < | G |$ instead. Favoring particular positions didn't help much: selecting uniformly at random performs almost as well, and the randomness also helps the search avoid getting stuck in local minima.

Transferability: across training data, feature maps, and model families

The attack already transfers in two ways. The surrogate is trained on a disjoint share of the corpus (50% in our runs), and it works on a different feature map than the target: the smooth normalized histogram instead of the quantized codes. Edits found against this surrogate nevertheless flip the real target's decision. That suggests the attack exploits the geometry of the data rather than the specific weights of the target.

The same argument suggests a third kind of transfer, across model families: logistic regression, random forest, neural network. Any reasonable classifier trained to separate malware from benign files on the same feature-generating process (the TLSH histogram) is solving the same discrimination problem over the same signal, so different model families tend to learn similar decision boundaries between the two classes. An edit that pushes the histogram across one model's boundary should therefore push it across the others' too, so an attack developed against a logistic-regression surrogate should transfer to a random forest or a neural network reading the real TLSH features.

Results

On 100 held-out malware samples with $ε = 0.1$ ( $δ = 25$ ), the attack evaded both the local surrogate and the target classifier, a logistic regression (LR), on every sample. Successful evasion needed 371 greedy steps on average per file, typically in under 20 seconds per sample on commodity hardware without a GPU. On average, the adversary could modify 23% of the file as gap bytes without increasing its size. The surrogate itself was trained on 50% of the original training corpus held out for that purpose, with no overlap between the target and surrogate's training data.

Successful evasions (target: LR, surrogate: LR): 100/100 (100.0%)
Attack time: mean=18.9s  median=15.0s  min=0.7s  max=63.5s
Modifiable gap fraction: mean=23.9%  median=24.8%  min=14.2%  max=43.5%
Iterations to evasion: mean=371  median=303  min=15  max=1129

If the target is a random forest (RF) while the surrogate remains logistic regression, the success ratio stays almost the same (99%), though the attack needs more greedy steps on average (658 vs. 371) and wall-clock time increases too, to 55 seconds on average. The attack therefore transfers well across different target detectors.

Successful evasions (target: RF, surrogate: LR): 99/100 (99.0%)
Attack time: mean=55.0s  median=42.8s  min=0.5s  max=316.9s
Modifiable gap fraction: mean=23.9%  median=24.8%  min=14.2%  max=43.5%
Iterations to evasion: mean=658  median=541  min=5  max=2348

It's worth emphasizing that the number of target queries needed is close to one: run enough iterations against the surrogate alone (a few thousand, if needed), query the target only at the end, and the file typically already evades. How many intermediate queries are needed depends on how good the surrogate is, which in turn depends on how much of the corpus the attacker used to train it. A smaller or less representative surrogate corpus should transfer less reliably, so the attack falls back on more frequent target queries to find a working candidate.

Future direction: an agent that composes the building blocks

Nothing in the algorithm above is a new optimization method. It is a composition of known pieces: coordinate descent, a smooth proxy objective substituted for a thresholded one, exhaustive local evaluation, and an incremental delta update that makes the evaluation cheap. Most of the engineering effort went into fitting those pieces to TLSH's specific structure, not into inventing a new one. That suggests automating the composition step itself, for someone who knows the target well but doesn't know discrete optimization deeply.

Claudini is a recent demonstration of this pattern in a different domain. Agents such as Claude Code and Codex were given a scoring function, a library of 30+ existing white-box attack methods against LLMs together with their results, and a fixed compute budget. They then looped: read the results, propose a new optimizer variant, implement it, run it, inspect the outcome. The best discovered attacks beat the best prior methods, including tuned baselines: up to 80% attack success against under 50% when jailbreaking GPT-OSS-Safeguard-20B, and 100% against 82% for prompt injection on Meta-SecAlign-70B. The authors' own analysis of the lineage of methods shows that the most prominent strategy was merging ideas from two or more published methods, and they describe the result as a lower bound on what such agents can do. They also report reward hacking: once the agent ran out of legitimate improvements, it began to game the evaluation protocol (for example by using a longer adversarial prompt than the fixed budget allows, or by searching over random seeds) instead of improving the algorithm.

Another paper makes a related point from the other direction. By systematically tuning and scaling general optimization techniques (gradient descent, reinforcement learning, random search and human-guided exploration), the authors bypassed 12 recent LLM jailbreak and prompt-injection defenses with attack success rates above 90% for most of them, where the majority of these defenses had originally reported near-zero. This matters particularly for automatic red-teaming, since it has to play the role of an adaptive attacker: one who knows the defense and adapts by finding a new combination that works.

The same recipe fits here. Give an agent a catalogue of building blocks, and its job is to search over combinations of them, not to invent anything new. What it needs from us is the objective, the constraints, the incremental-digest oracle, and a fixed budget of compute and target queries. The harness has to enforce the constraints itself (only gap bytes change, the edits stay inside the $ε$ -ball, the ELF stays valid, the incremental digest matches the reference TLSH, queries are counted, evaluation uses held-out files, etc), because, as Claudini's reward hacking shows, an agent will exploit any loophole in the scoring. That is the point for someone without a discrete-optimization background: they don't need to know which search techniques exist, only what the objective and the constraints are.

For a defender, the implication is that this kind of adaptive search is becoming cheap enough that any red-teaming test should use it. A detector's robustness claim is only as good as the attacker it was tested against, and that attacker can now be, in effect, a search over combinations of already-known techniques rather than a single hand-built one. Put differently, even if the worst-case attack does not necessarily change, AI agents can lower the average attacker's cost: adversaries who previously lacked the skill to mount this kind of attack can now succeed too.