# A Novel TLS-Based Fingerprinting Approach That Combines Feature Expansion and Similarity Mapping
## 3 Methodology
### Similarity Mapping  
Similarity mapping is a core element of the presented approach, and it enabled us to map the high-dimensional feature spaces of TLS and HTTP fingerprints on to a lower-dimensional structure whilst preserving the local similarity structure. The main challenge in this mapping lies in being able to efficiently calculate similarities without losing any of the fine-grain details. This is more critical for TLS features where the quantity of the exposed data is limited to that which is exposed during the handshake. In our approach, we used the Jaccard similarity coefficient to compare two fingerprints represented as binary feature vectors, \(A\) and \(B\). This method is defined as \(J(A,B)=\frac{|A\cap B|}{|A\cup B|}\), and it provided a reliable measure of their similarity. However, directly computing Jaccard similarities has \(O(n^{2})\) complexity for \(n\) fingerprints, making it computationally expensive, especially for the large datasets used in active scanning. To address the challenge of scalability, we used a two-phase similarity approach involving MinHash signatures and Locality-Sensitive Hashing (LSH). Using MinHash specifically exploits the relationship between Jaccard similarity and the probability of hash collisions, enabling the compression of binary feature vectors into fixed-size signatures that preserve the expected Jaccard similarities. Figure 4: A screenshot of a typical set of HTTP headers received in response to a HEAD request during the header enrichment process. The HEAD request is seen in red, the HTTP response is blue. For a fingerprint's binary feature vector, \(x\in 0,1^{|F|}\), the MinHash signature \(M(x)\) was generated, using \(k\) independent hash functions, \(h_{1},...,h_{k}\), as  
\[M(x)=[\min(h_{1}(i):x[i]=1),...,\min(h_{k}(i):x[i]=1)].\]  
This reduced the dimensionality from \(|F|\) to \(k\), while still preserving the expected similarities between fingerprints [28; 29]. The probability of a match between MinHash signatures was related to the Jaccard similarity:  
\[P(\min(h(A))=\min(h(B)))=J(A,B).\]  
The most appropriate values for \(k\) and \(l\) were established through iterative testing. Once the LSH Forest was produced, it could be queried via linear scan and LSH traversal. This enabled the nearest neighbours for any given node to be determined. As established in Section 3.5, the original fingerprints were retained alongside their binary representations, enabling confirmation that domains with the same fingerprint or those with small vector differences were located on branches or in clusters. Through this iterative process, we were able to determine that \(k=1024\) hash functions struck an optimal balance between computational efficiency and similarity preservation, with a theoretical error bound of \(O\Big{(}\frac{1}{\sqrt{k}}\Big{)}\). The LSH forest data structure facilitated fast, approximate nearest-neighbour searches with \(O(\log n)\) complexity. For each fingerprint, \(x\), its MinHash signature was split \(M(x)\) into \(l\) bands (signature partitions) of \(r\) values, where \(l\times r=k\). Two fingerprints were considered candidate pairs if they matched in at least one band, with the collision probability given by  
\[P(\text{candidates})=1-(1-J(A,B)^{r})^{l}.\]  
The LSH forest was initialised with 1024 hash functions (matching the MinHash encoding) and 1 = 128 prefix trees. Increasing these values improved accuracy [30] but also increased memory usage. Using \(l=128\) prefix trees and \(r=8\) values per band, we achieved a high probability of detecting fingerprint pairs with \(J(A,B)>0.7\), while keeping the false positive rate under 0.1%. We then constructed the final c-k-NNG graph \(G=(V,E)\) in stages: 1. We computed the MinHash signatures for all fingerprints; 2. We built the LSH forest index, using \(l\) prefix trees; 3. We found \(k=100\) approximate nearest neighbours for each vertex; 4. We added edges weighted by estimated Jaccard similarity.