Similarity Hashes Suggestions (TLSH improvement or replacement with CTPH)

[chris-ha458]

MinHash and SimHash are other widely known dedup methods, they each require multiple hyperparameters (shingle size, permutation count, Jaccard thresholds etc) that might be difficult to pin down for a multilingual corpus like OSCAR. Further they do not produce per sample (whether sample is sentence or document) digests that could be used offline.
Implementing those would be a major effort requiring a lot of engineering and validation efforts.

In the meantime, we could improve Ungoliant's current similarity hash based on TLSH or implement a new one.

My research indicates that TLSH (Trend Micro Locality Sensitive Hash) is part of a group of hashes called context triggered piecewise hashes (CTPHs). These are often utilized by antivirus software to find hidden or mutated viruses.

Currently, Ungoliant is using a bugfixed version of rust crate version of TLSH called tlsh-fixed. If I am correct @Uinelj is the maintainer of that. Unfortunately it is hamstrung in having to support the python TLSH library.
One way to break free from this is to use another well maintained rust TLSH crate tlsh2 that also supports new internal constructions. Change the internal tlsh construction (such as changing the pearson hash to xxhash) for Ungoliant's purposes and name it something else so there is no confusion.

Another state of the art CTPH is ssdeep.
There is a well maintained rust crate ffuzy for this as well that also support customized constructions. This crate also has the benefit of supporting the Dual Fuzzy Hash construction that would be useful for many to many comparisons, which would be helpful for the massive dedups that Ungoliant will need to conduct.

I will look into how we could implement in ungoliant

1. A new TLSH based on tlsh2
2. ssdeep based on ffuzzy

[chris-ha458]

Update regarding ssdeep,ssdeeper and sdhash.

• Classification of hashes
  Bringing order to approximate matching: Classification and attacks on similarity digest algorithms classifies ssdeep as a Feature Sequence Hashing while providing many alternatives as well.
  SimHash, and I assume minHash is categorized as Byte Sequence Existence functions. (edit: they are not even similar)
  TLSH is classed as Locality-Sensitive Hashing method and saHash and FbHash is provided as recent alternatives.

• Options such as ssdeep and other CTPHs, seem to be inferior to TLSH.
  Independent research seem to indicate that when TLSH fails, so does ssdeep.

• Comparison between MinHash,SimHash, TLSH and ssdeep is found here.
  Minhash has the best AUC followed by simhash and TLSH. (This paper proposes BCD but again it does not seem to be widely available.)

• There seems to be a lot of literature regarding TLSH including its hierarchical agglomerative clustering based variant (HAC-T).

• TLSH itself seems to be well designed with well documented parameter and architecture choices
  The only nitpick i would have is the choice of pearson hash. The reason it was chosen is that it was a well established hash at the time. Now we have much better hashing algorithms that are faster and better hash characteristics (mainly around the xxh family).

My current plan is to look into

• ways to improve and integrate TLSH into Ungoliant
• HAC - T which seems to be a scalable way to use TLSH to implement actual dedup process
• FbHash as a potential alternative.

[chris-ha458]

HAC-T info

HAC-T and Fast Search for Similarity in Security
Scalable Malware Clustering using Multi-Stage Tree Parallelization
Fast Clustering of High Dimensional Data Clustering the Malware Bazaar Dataset

[chris-ha458]

TLSH Info

The most current tlsh implementations in rust is TLSH2 and tlsh-fixed the latter one is by @Uinelj and from discord discussions it seemed that there was a hope to move to TLSH2. tlsh-fixed is derived from a rust ported tlsh which deviates in many ways from the original implementation. This might be the cause of certain compatibility issues @Uinelj has been encountering.

Most things lacking in the current iteration of tlsh2 are threading and faster hash supports, but it is understandable since it is a no_std crate that strives to stay as close as possible to the original c++ implementation. Although lack of such features are unfortunate, they will hardly be any kind of rate limiting step for the purposes of ungoliant. Also the way tlsh would likely be used is that it would be part of a massively parallel approach (per document hashes).

• If ungoliant does not need anything more than the original c++ implementation it would be wise to use tlsh2.
• If ungoliant wants to extend and modify the tlsh approach with rust style parallelism, faster hashes etc, i think we can just aggressively fork tlsh-fixed and not worry about anything about compatibility.

Upon further investigation I have found out that
default values for tlsh2 and py-tlsh is 128 buckets and onebyte checksums.
for ungoliant it is 256 buckets and 3 byte checksums.
Considering the datasize and purposes of tlsh, i understand this choice and I feel like there is no reason not to use it.

The problem, now I understand, is that people usually use python libraries to interact with OSCAR datasets (load from huggingface datasets) and to change from the default values provided by py-tlsh you need to adjust the values in the CMAKE and compile it from source.

As it stands there are the following paths visible :

1. Fork py-tlsh that changes the default CMAKE values. Uploading it into pypi and maintaining it might be difficult. Especially when we are trying to support diverse environments it might be difficult to support and address build issues.
2. Fork or modify either tlsh-fixed, tlsh2 to add python bindings and upload that version into pypi. I'll try clarify the bare minimum engineering effort required to achieve this with tlsh-fixed.
3. Change into default tlsh settings. This is the easiest but it is unclear how deduplication is impacted. It would be worth looking into that part as well.
4. Move to MinHash or SimHash entirely.