Locality-preserving hash function turns a file into a short code such that similar files get similar codes. This hashing can also be used for malware detection, where the fixed-size hash output is what feeds the classifier. The intuition is that locality preservation places variants of the same malware family close to each other in the hash's output space. If these clusters are also sufficiently far from benign files, even a simple linear classifier can separate the two in this "embedded space". Moreover, no matter how long the file is, the hash output has a fixed size, which makes the approach scale to files of any size.
There are two families of these hashes.
Learnt hashes are trained. A neural network, typically a Siamese or contrastive architecture, is trained on pairs of files known to be related or unrelated, and learns to map each file to a compact code such that related files land close together. 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 retraining as the threat landscape changes), and needs enough compute to run that network.
Static hashes are not trained at all. TLSH, ssdeep and sdhash are fixed procedures: a deterministic pass over the bytes, with no parameters to fit and no training data. That is why they are the choice for detectors that run 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 because 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?
Can an attacker take a working piece of malware and modify some of its bytes, strategically, so that the file still runs and still functions as malware, but its digest lands on the benign side of the classifier's decision boundary?
Where the attacker is allowed to modify bytes matters, because it determines both how hard the attack is and how easy it is to defend against.
Appended bytes are the easiest to attack: bytes added to the end of the file that the loader never executes. They are just as easy to defend against. Stripping the binary, or hashing only the part of the file that the ELF headers declare as loaded, removes the whole attack surface.
Bytes anywhere in the code or data sections are the hardest to defend against, but also the most expensive to attack. Every edit there risks changing what the program does, so the attacker needs semantics-preserving transformations (dead-code insertion, instruction substitution, register reallocation) rather than an arbitrary byte flip, and verifying that the binary still behaves correctly is itself expensive.
ELF gap bytes sit in the middle. Every ELF binary has padding regions: bytes covered by neither the ELF header, the program header table, nor any PT_LOAD segment. The loader never maps or interprets these bytes, so an attacker can set them to whatever they like and the program still runs as before, with no semantic analysis required. In real ELF binaries these gaps typically amount to 5–20% of the file size, which is enough room to move a digest meaningfully. This middle ground, easy to exploit but not as trivially removed as appended bytes, is why we focus on it. The attacker simply reads the gap intervals off the ELF and program headers and edits the bytes there.
How TLSH actually works
TLSH belongs to the same family as other counting sketches: 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 into a bucket. The table produces 256 possible buckets, but TLSH only keeps the first 128 triplets.
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 moves.
The raw histogram is not, however, what the classifier sees. TLSH quantizes each bucket count into a 2-bit code using three thresholds, the quartiles of the histogram itself. A count at or below gets code 0, a count up to gets code 1, a count up to gets code 2, and anything above gets code 3. Together with three header values (the file length and two quartile ratios), this yields the 131-dimensional feature vector that SIMBIoTA-ML feeds to its random forest.
The thresholding is the step that matters for an attacker. In the figure above, , , . 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: the thresholding means that most candidate moves produce exactly zero change in the objective function of the attacker.
Formalizing the evasion problem
Write the file as a vector of bytes , with original bytes . Let be the set of modifiable gap positions, and let each modified byte stay within an -ball of its original value, . The feasible set is
Let 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 for any candidate . 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 be the target classifier, which outputs a malware score. The attacker observes it only through its decision , where means "malware". The attacker's goal is to find a feasible file that the target calls benign:
This is a constrained discrete optimization over an exponentially large ( candidates) but bounded neighborhood of . 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 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 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 independent reasons:
The input is discrete. 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, is piecewise constant almost everywhere because of the quantization step, so its "gradient" is zero wherever it is even defined.
The target is a black box. We could not backpropagate through even if the rest were smooth.
The textbook remedy for the second problem is to relax the pipeline into a smooth, differentiable approximation and attack that with gradient methods such as PGD. In our experience this route proved ineffective, and it would leave the first and third problems untouched anyway. We therefore stay zeroth-order: we always evaluate candidate byte values and compare the results, and never differentiate.
What we can remove is the flat loss caused by quantization. We build a surrogate that shares TLSH's construction exactly, right up to the point of quantization, and stops there: a second classifier , trained on the normalized, un-thresholded histogram
instead of the quantized codes ( is the count in bucket , and both sums run over the 128 kept buckets). Nearly every byte edit moves several triplets between buckets, so , and the surrogate's loss on it, changes with essentially every move. We are still doing zeroth-order search, since there was never a derivative to be had, but now every query returns informative feedback about whether that move helped, instead of the flat non-answer the real quantized target would give.
Why normalize the histogram?
Raw bucket counts scale with the size of the file. A file of bytes produces triplets, so every count grows roughly linearly with : 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, because its thresholds are the histogram's own quartiles. A code says where a count sits relative to the other counts in the same histogram, not how large it is in absolute terms. Multiplying all counts by a common factor multiplies by the same factor and leaves every code unchanged. (File size enters TLSH only through the separate length value in the header, which gap edits cannot change.)
The surrogate should see the same thing. Fed raw counts, a linear model would run into three problems:
it would partly learn file size instead of byte statistics, because the counts differ by orders of magnitude between small and large files;
for large files its logit would saturate, so the loss would barely react to an edit, while for small files the same edit would look huge;
weights fitted on one corpus of files would not carry over to files of another size, which hurts exactly the transfer from surrogate to target that the attack relies on.
Dividing by the total turns 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 for the surrogate the role that the quartiles play for TLSH: it removes the file size and keeps the shape. It does not reproduce the quantization, and that is the point, since keeping it smooth is what gives the search a direction.
Why greedy is the right search here
Given that we can only query, not differentiate, the question becomes how to spend those queries. A greedy coordinate-wise search does the following: at each step, take one byte position, try every legal value for it, and keep whichever value minimizes the surrogate loss. It is the same accept-the-best-candidate loop as in GCG for LLM jailbreaks, minus the gradient that GCG uses to shortlist candidates, because here the candidate set is small enough to enumerate exhaustively.
Greedy is particularly efficient here because evaluating every candidate value at a position is cheap and exact, not an approximation. If we change a single byte we do not need to recompute the whole TLSH digest from scratch. The digest can be updated incrementally: we know which histogram buckets a byte participates in, so we can remove its old contribution and add its new one. A byte at position only takes part in the sliding windows that contain it, which is at most five windows of six triplets each, so at most 30 of the file's triplets change when that byte changes. (Strictly, only 18 of the 30 contain the byte: as the newest byte of a window it is part of all six triplets, and as an older byte in the other four windows it is part of three each. The bound of 30 is a safe, simple one to implement.) We maintain the bucket histogram incrementally rather than recomputing TLSH from scratch, so an update costs instead of .
Evaluating all candidate values at one position then costs roughly operations. For (, so 51 candidates) that is about 1,500, against , about 50 million operations on a 1 MB file done naively. The full 131-dimensional feature vector is derived from the maintained histogram in (sort for the quartiles, encode 128 buckets), so the real target score can be read off without ever re-hashing the file.
By contrast, methods that change many bytes at once, such as the crossover step of a genetic algorithm, cannot use this cheap update: each offspring differs from its parent in many places and needs an rebuild of the histogram.
The only approximation left in the greedy algorithm is which positions get updated in each round. Checking all positions in every iteration would be very slow, so we sample a random subset. Favouring particular positions did not help much: random selection performs almost equally well, and the randomness also helps the search avoid getting stuck in local minima.
Putting it together:
repeat up to num_iters:
sample k positions uniformly at random from the gap positions G
for each sampled position p:
for every legal value v within the ε-ball of x0[p]:
evaluate the surrogate loss via the incremental histogram # O(30)
commit whichever v minimizes that surrogate loss # O(30)
query the target once (decision only); stop if it now says "benign"
The search itself never touches the target: all candidate evaluations run against the surrogate. The target is queried once per iteration, only to read a decision and stop early. Since the surrogate drives the search, those intermediate queries can also be skipped, and the attack can be run for a fixed number of iterations with the target queried only on the final file.
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 (30% 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. Pushing the histogram into the region that any competent classifier over these features would call benign is not a property of one particular model's weights. It is a property of where the histogram sits relative to the two populations the task is defined over. So an attack developed against a logistic-regression surrogate should transfer to a random forest or a neural network reading the real TLSH features.
How far it transfers plausibly depends on how much each model type relies on the same regions of the feature space. The current results, where both target and surrogate are logistic regressions, do not test this yet. It is a natural next experiment, and the random forest in SIMBIoTA-ML would be a good real target to run it against.
Results
On 50 held-out malware samples with (), the attack evaded every sample: none needed more than 1,500 of the 2,000-iteration budget, at roughly a minute per sample on an RTX 5090. In practice the number of target queries needed is close to one: run enough iterations against the surrogate alone and 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 depends on how much of the corpus the attacker used to train it. We expect a smaller or less representative surrogate corpus to transfer less reliably, so that the attack falls back on more frequent target queries to find a working candidate.
TODO: insert the sweep of evasion rate / iterations-to-evade against the surrogate's corpus share (--surrogate-frac).
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 suffix 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.
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), 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 getting cheap to run. 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.