NVIDIA-Cubin-Binaries per Data Clustering und AI rueckengineered
Ein Experiment untersuchte, ob sich NVIDIA-Cubin-Binaercode mit Data-Clustering-Methoden auswerten laesst. Die Motivation stammte aus einer Abschlussarbeit zum Thema Data Clustering, erste Annahmen ueber die Analyse von Binaries werden vorgestellt.

Veröffentlicht am 9. Oktober • Zuerst erschienen auf poljak-engineering.com
Ich bin kein Data Scientist bzw. Data Engineer, aber ich wollte ein kleines Experiment mit NVIDIA Cubin Binärcode durchführen. Dabei fiel mir die Abschlussarbeit eines Kollegen über Data Clustering ein, und ich fragte mich, was eigentlich passieren würde, wenn wir so etwas mit einer NVIDIA-Binärdatei versuchen würden?
Meine Annahme war, dass wir, wenn es uns gelänge, eine gute Distanzmetrik zu finden, Anweisungen kategorisieren und dadurch einen höherwertigen Einblick darin gewinnen könnten, wie NVIDIA CUDA-Binärdateien aufgebaut sind.
Die Hamming-Distanz zwischen zwei Binärworten fester Länge ist die Anzahl der Bitpositionen, an denen sie sich unterscheiden. Für unsere 64-Bit-Wörter können wir sie mit einem XOR gefolgt von einer Population Count Berechnung ermitteln:
dist = ( insn1 ^ insn2 ). bit_count () Enter fullscreen mode Exit fullscreen mode Das XOR identifiziert die unterschiedlichen Bits, und bit_count() zählt sie. Je weniger Bits sich zwei Wörter unterscheiden, desto näher sind sie sich unter dieser Metrik.
Mathematisch betrachtet können wir unsere Daten als Teilmenge der 64-Bit-Binärwörter auffassen, mit der Hamming-Distanz als Metrik. Mit anderen Worten: Unsere beiden Anweisungen sind umso näher beieinander, je mehr Bits sie gemeinsam haben. Je mehr Bits sie unterscheiden, desto weiter sind sie voneinander entfernt.
Mein eigener CUDA-Kernel-Code konnte nur sehr wenig Daten liefern. Er umfasste etwa 24 Anweisungen, und anstatt zufälligen Code hinzuzufügen, entschied ich mich, mir das cuda-samples Repository anzusehen:
Meine Zielarchitektur, sm_50, war zu alt, um diese Beispiele mit den dokumentierten Anweisungen zu kompilieren, also wählte ich einfach ein Beispiel aus und kompilierte es manuell:
cd./cpp/5_Domain_Specific/recursiveGaussian nvcc -arch = sm_50 -cubin recursiveGaussian_cuda.cu -I /home/stjepan/Develop/cuda-samples/Common/ -o kernel.cubin Enter fullscreen mode Exit fullscreen mode Damit erhielt ich die Cubin ELF Datei, musste aber noch den rohen Binärcode extrahieren. Dafür verwendete ich die von NVIDIA bereitgestellten Tools:
$ cuobjdump -ltext../kernel.cubin SASS text section 1: kernel-_Z24d_recursiveGaussian_rgbaPjS_iiffffffff.sm_50.elf.bin SASS text section 2: kernel-_Z22d_simpleRecursive_rgbaPjS_iif.sm_50.elf.bin SASS text section 3: kernel-_Z11d_transposePjS_ii.sm_50.elf.bin Enter fullscreen mode Exit fullscreen mode Um diese Abschnitte zu extrahieren, ändert man -ltext in -xtext. Meine kleine Datenbank mit NVIDIA-Binärdaten war damit deutlich vielversprechender (und statistisch signifikanter):
$ ls *.bin | xargs -I{} xxd -e -g 8 -c 8 {} | wc -l 2280 Enter fullscreen mode Exit fullscreen mode Anschließend kompilierte ich deutlich mehr CUDA-Binärdateien und fügte mehr als 40000 Anweisungen hinzu. Aus Performancegründen entschied ich mich, den Datensatz auf 12000 Anweisungen zu begrenzen.
Für mein erstes Experiment war ich keineswegs enttäuscht. Ich installierte die Pakete scikit-learn und numpy für mein Python-Skript. Scikit-learn stellt den DBSCAN Clustering-Algorithmus bereit, und mein erster Versuch sah in etwa so einfach aus wie:
import numpy as np from sklearn.cluster import DBSCAN from pathlib import Path import struct def cluster ( insns ): dist = np. zeros (( len ( insns ), len ( insns )), dtype = np. float64 ) for i in range ( len ( insns )): for j in range ( i + 1, len ( insns )): d = ( insns [ i ] ^ insns [ j ]). bit_count () dist [ i, j ] = d dist [ j, i ] = d clusters = DBSCAN ( eps = 5, # epsilon (how far points in a cluster can be) min_samples = 10, # minimum number of samples a cluster must have metric = " precomputed " ). fit_predict ( dist ) c_dict = {} for i in range ( 0, len ( clusters )): c = clusters [ i ] if not c in c_dict: c_dict [ c ] = [ insns [ i ]] else: c_dict [ c ] += [ insns [ i ]] return c_dict Enter fullscreen mode Exit fullscreen mode Beispielausgabe Bereits das lieferte nützliche Daten. Die folgende Ausgabe zeigt fünf Beispiele pro Cluster (der ursprüngliche Datensatz enthält 12000 erfasste Anweisungen):
_______[ 0 ]_______ _______[ 9 ]_______ _______[ 18 ]_______ _______[ 29 ]_______ 0x001cc400e22007f6 0xe2400ffff400000f 0x5c403200026720ff 0x1e03fb8aa3b7170c 0x001fd801fec0075d 0xe2400fffe408000f 0x4c413008001722ff 0x1e03fb8aa3b71a08 0x089fec02fc2007f1 0xe2400fffff87000f 0x4c413008001723ff 0x1e03fb8aa3b7120b 0x001ff400ffa007f0 0xe2400fffff87000f 0x5c423200017714ff 0x1e03fb8aa3b7190a 0x003fd800e3a007fd 0xe2400fffc889000f 0x5c423200019718ff 0x1e03fb8aa3b7140c _______[ 1 ]_______ _______[ 32 ]_______ _______[ 16 ]_______ _______[ 30 ]_______ 0x4c98078000870001 0x32807fdf80070303 0x30cd83ff800722ff 0x37be03c2fc070c1f 0x4cb8000005472a03 0x32807fdf80082222 0x30cd83ff80070eff 0x37be03c2fc070817 0xf0c8000002570002 0x32807fdf80092323 0x30cd83ff800704ff 0x37be03c2fc070b07 0xf0c8000002170004 0x32807fdf80080e0e 0x30cd83ff80070dff 0x37be03c2fc070a0f 0x1c00180000070300 0x32807fdf80091010 0x30cd83ff800707ff 0x37be03c2fc070c27 _______[ 2 ]_______ _______[ 10 ]_______ _______[ 17 ]_______ _______[ 38 ]_______ 0x0407f80000070000 0x040007fffff7030a 0x36bd83ff80072397 0x5bdf7f81f0670506 0x0423f80000070a05 0x040007fffff70806 0x36bd83ff80072287 0x5bdf7f81c0770705 0x0427f80000072121 0x040007fffff72020 0x36bd83ff8007108f 0x5bdf7f81c0470404 0x0427f80000072121 0x040007fffff70a0c 0x36bd83ff80070e87 0x5bdf7f81c0770705 0x0407f80000070404 0x040007fffff70604 0x36bd83ff80070597 0x5bdf7f81c0470404 _______[ 3 ]_______ _______[ 36 ]_______ _______[ 19 ]_______ _______[ 33 ]_______ 0x4b68038800070007 0x38423000002709ff 0x3659038000a71514 0x537104080007060a 0x4b6d038005470007 0x38403000001709ff 0x3659038000a70517 0x537104080007060a 0x5b6403800ff70317 0x38423000002709ff 0x3659038000aa1617 0x5b710a000087060c 0x5b20030800970605 0x38403000001709ff 0x3659038000a71618 0x5371020800070608 0x5b28038000970607 0x38403000007700ff 0x3659038000a71519 0x5371020800070616 _______[ 4 ]_______ _______[ 11 ]_______ _______[ 20 ]_______ _______[ 34 ]_______ 0xe260000052000040 0xda1005affff70202 0x36b403c080071317 0x386800437f070404 0xe29000002a000000 0xda1005affff70404 0x36b403c080071307 0x386800437f070505 0xe290000020000000 0xda1005affff70202 0x36b403c080071707 0x386800437f070606 0xe2600000fc800040 0xda1005affff70404 0x36b403c080071707 0x386800437f070707 0xe290000015000000 0xda0006effff70303 0x36b403c080071707 0x386800437f070206 _______[ 7 ]_______ _______[ 12 ]_______ _______[ 21 ]_______ _______[ 35 ]_______ 0x1c00ffffffe70506 0x3868003f00070a12 0x328002c000071414 0x5be70b0780d70c0c 0x1c0ffffffff70606 0x3868003f00070f0f 0x328002c000071313 0x5be7098780e70c0c 0x1c0ffffffff7050d 0x3868003f0007060a 0x328002c000071313 0x5be7070780f70c0f 0x1c0ffffffff70003 0x3868003f00070709 0x328002c000071313 0x5be7068780870f08 0x1c0ffffffff70603 0x3858003f00070000 0x328002c000071313 0x5be70b0780970808 _______[ 28 ]_______ _______[ 13 ]_______ _______[ 22 ]_______ _______[ 37 ]_______ 0x5c4707000047ff04 0x0103f8000007f007 0x368403c010071e17 0x1e03f3504f370303 0x5c6007800027ff03 0x0103f8000007f018 0x368403c010071e07 0x1e03f3504f370b0b 0x5c2107800037ff03 0x0103f8000007ff03 0x368403c010071e07 0x1e03f3504f370e0e 0x5c60078001a7ff17 0x0103f8000007f021 0x368403c010071e07 0x1e03f3504f370d0d 0x5c6007800127ff09 0x0103f8000007f027 0x368403c010071e07 0x1e03f3504f370d0d _______[ -1 ]_______ _______[ 14 ]_______ _______[ 23 ]_______ _______[ 39 ]_______ 0x4cc0018005470404 0x4801038006670310 0x002c4800eee00711 0x36b403c37f070a17 0x5cc002a000870705 0x4801038006670414 0x002c4800eee00711 0x36b403c37f071f07 0x5b28030000470505 0x4801038006670515 0x002c4800eee00711 0x36b403c37f070b1f 0x5c4707000032ff05 0x4801038006670615 0x002c4800eee00711 0x36b403c37f07090f 0x32807fdf80070202 0x480103800667070e 0x002c4800eee00711 0x36b403c37f072607 _______[ 5 ]_______ _______[ 24 ]_______ _______[ 25 ]_______ _______[ 40 ]_______ 0x366c03800037050f 0x36f0058010171410 0x011c7801e2404776 0x5bae05000ff7200a 0x3668038000170407 0x3670054000071416 0x011c7801e2404776 0x5bae0f800ff70808 0x366803800fd72707 0x3670054000071416 0x011c7801e2404776 0x5bae05800ff7200b 0x366820000fd72407 0x3670054000071416 0x011c7801e2404776 0x5bae04800ff71f09 0x366c03800fe72007 0x3670054000071416 0x011c7801e2404776 0x5bae13000ff70808 _______[ 6 ]_______ _______[ 15 ]_______ _______[ 26 ]_______ _______[ 41 ]_______ 0xeed4200000070407 0xf0a81b8000070000 0x003ff401e3a00f06 0x338001437f070302 0xeed4200000070408 0xf0a81b8000070000 0x003ff401e3a00f06 0x338003437f070c0a 0xeedc200000070407 0xf0a81b8000070000 0x003ff401e3a00f06 0x338003437f070006 0xeed4200000070805 0xf0a81b8000070000 0x003ff401e3a00f06 0x338003c37f070006 0xeed4200000070c0b 0xf0a81b8000070000 0x003ff401e3a00f06 0x338003437f070006 _______[ 8 ]_______ _______[ 31 ]_______ _______[ 27 ]_______ _______[ 42 ]_______ 0xf0f0000034170000 0x30cc03ff80072326 0xd820056ff0470606 0x010437f00007f025 0xf0f0000034670000 0x30cc03ff80070e0c 0xd82005aff0570b08 0x010437f00007f025 0xf0f0000034470000 0x30cc03ff80071011 0xd82005aff0570609 0x010437f00007f025 0xf0f0000034270000 0x30cc03ff80070406 0xd82005aff057070d 0x010437f00007f025 0xf0f0000034670000 0x30cc03ff80070507 0xd82005aff0570a0e 0x010437f00007f025 Enter fullscreen mode Exit fullscreen mode DBSCAN hat Gruppen von Binärwörtern mit ähnlichen Bitmustern hervorgebracht. Die einzige Ausnahme ist der Cluster -1, was im Wesentlichen "nicht zugewiesen" bedeutet oder, wie ich es lieber nenne, "Rauschen". DBSCAN legt Daten dort ab, wenn es sie keinem Cluster zuordnen kann.
In den Clustern 13 und 42 erkennen wir die MOV-ähnliche Instruktion aus unserer vorherigen Reverse-Engineering-Übung:
_______[ 13 ]_______ _______[ 42 ]_______ 0x0103f8000007f007 0x010437f00007f025 0x0103f8000007f018 0x010437f00007f025 0x0103f8000007f01d 0x010437f00007f025 0x0103f8000007f021 0x010437f00007f025 0x0103f8000007f027 0x010437f00007f025 Enter fullscreen mode Exit fullscreen mode Ebenso handelt es hier um die zweite Instruktion, mit der wir im vorherigen Artikel experimentiert haben:
_______[ 6 ]_______ 0xeed4200000070407 0xeed4200000070408 0xeedc200000070407 0xeed4200000070805 0xeed4200000070c0b Enter fullscreen mode Exit fullscreen mode Wie könnten wir diese Instruktionen weiter aufschlüsseln? Eine Möglichkeit besteht darin, Instruktionen wie die aus den Bins 13 und 42 bitweise mit AND zu verknüpfen, um herauszufinden, was sie gemeinsam haben:
TEST = [ 0x0103b8080817f003, 0x0103f8000007f002, 0x0103b8080817f000, 0x0103f8000007f006, 0x0103b8080817f000, 0x010437f00007f025 ] and_val = TEST [ 0 ] for each in TEST: and_val &= each print ( f " { and_val: 016 x } " ) Enter fullscreen mode Exit fullscreen mode Zum Beispiel erhalten wir damit das folgende Ergebnis:
010030000007f000 Enter fullscreen mode Exit fullscreen mode Abgesehen von der Ziffer 3 scheinen wir uns also der Struktur der Instruktion zu nähern. Wenn wir dies mit unserem Clustering-Ansatz kombinieren könnten, wären wir möglicherweise in der Lage, mehr Informationen über das Format zu gewinnen.
Eine kleine Recherche führte mich zu HDBSCAN, das mir mehr Kontrolle über die Clustering-Ergebnisse zu geben schien:
clusters = hdbscan. HDBSCAN ( min_cluster_size = min_size, min_samples = samples, cluster_selection_method = " eom ", metric = " precomputed " ). fit_predict ( dist ) Enter fullscreen mode Exit fullscreen mode Es schien spezifischere Cluster zu erzeugen, aber viele Samples landeten dennoch im "Rauschen"-Cluster.
Ich hatte bereits beschrieben, wie wir mit bitweisem AND das gemeinsame Bitmuster eines Clusters erhalten können. Bitweises OR kann ebenfalls nützliche Informationen darüber liefern, welche Bits sich innerhalb der Daten unterscheiden. Mein Code kombinierte diese beiden Operationen und bewahrte dabei die Informationen zur Clustergröße:
c_dict = {} noise = [] for i in range ( 0, len ( clusters )): c = clusters [ i ] if c == - 1: noise. append ( insns [ i ]) elif c not in c_dict: c_dict [ c ] = [ insns [ i ]] else: c_dict [ c ] += [ insns [ i ]] res = {} for ( key, val ) in c_dict. items (): first = val [ 0 ] orval = val [ 0 ] for each in val [ 1:]: first &= each orval |= each orval ^= first if first not in res: res [ first ] = ( orval, val ) else: ( old_orval, old_val ) = res [ first ] res [ first ] = ( old_orval | orval, old_val + val ) Enter fullscreen mode Exit fullscreen mode Später habe ich zudem bitweise Frequenzen und einen Rauschen-Prozentsatz ergänzt:
total = 0 for ( key, val ) in res. items (): total += len ( val [ 1 ]) print ( f " { key: 016 x } { val [ 0 ]: 016 x } ( { len ( val [ 1 ]): 4 } ) " ) freqs = bit_frequencies ( val [ 1 ]) print_frequencies ( freqs ) count = 0 for each in val [ 1 ]: if count > 5: break else: print ( f " { each: 016 x } " ) count += 1 print ( "" ) print ( f " TOTAL: { total } " ) noise_len = len ( noise ) print ( f " NOISE: { noise_len: 4 } { ( noise_len / ( total + noise_len )) * 100 } % " ) Enter fullscreen mode Exit fullscreen mode Die Ergebnisse waren in Ordnung, aber nicht ganz zufriedenstellend. Hier ist ein Beispiel:
5c9807800ff00000 00000000000f003f ( 85) * 01011100100110000000011110000000000011111111____00000000000_____ 5c9807800ff7001e 5c9807800ff7001b 5c9807800ff70017 5c9807800ff7000b 5c9807800ff80020 5c9807800ff00020 308c03ff80070000 0671800000003fff ( 45) * 00110__01___110__000001111111111100000000000011100______________ 30cc03ff80072220 30cc03ff80072326 30cd83ff800722ff 36bd83ff80072397 36bd83ff80072287 30cc03ff80070e0c e34000000007000f 0000000000000000 ( 125) * 1110001101000000000000000000000000000000000001110000000000001111 e34000000007000f e34000000007000f e34000000007000f e34000000007000f e34000000007000f e34000000007000f 3280004000070000 0102078140001f1f ( 75) * 0011001_100000_000000____100000_0_00000000000111000_____000_____ 328002c000071414 328002c000071313 328002c000071313 328002c000071313 328002c000071313 328002c000071313 5c47000000000000 0000060001f70f0f ( 90) * 010111000100011100000100000000000000000_____0___00000___00000___ 5c47040000a70505 5c47040000870202 5c47040000870b0b 5c47040000870f0f 5c47000000c70e0e 5c47000000470505 4880000800070000 05201f8000303f3f ( 57) * 01001_0_10_0000000000____00010000000000000__011100______00______ 4980060800270909 4980040800270b0b 4ca004080027140c 4ca0008800070f09 4ca0008800070b0e 4ca0000800070b0f 300000427c070000 0ffe1f8183003f3f ( 164) * 0011___________0000______100001__11111__0000011100______000_____ 37be03c2fc070c1f 37be03c2fc070817 37be03c2fc070b07 37be03c2fc070a0f 37be03c2fc070c27 37be03c2fc071437 TOTAL: 6921 NOISE: 5079 42.325% Vollbildmodus aktivieren Vollbildmodus verlassen Die Bitfelder geben die Häufigkeiten pro Bit an. Liegt die Häufigkeit eines bestimmten Bits im Cluster über oder unter einem Schwellenwert, wird es als 1 beziehungsweise 0 dargestellt. Variiert es innerhalb des Clusters, wird es als _ dargestellt.
Das größte Problem war jedoch die Menge des Rauschens. Ich konnte es reduzieren, doch dann wuchs Cluster 0:
0000000000000000 7ffbbf9017ff3f3f (1406) * 010_1100_____000000000000000000000000_0_____0111000_____000_____ 4cb8000005472a03 1c00180000070300 4e00020000270204 5cb8010000370a05 5cb0118000670a06 5c10000000370004 Vollbildmodus aktivieren Vollbildmodus verlassen Viele Instruktionen landeten in diesem Cluster, weil alle Bits gleich gewichtet waren. Bits, die die Struktur der Instruktion repräsentieren, konnten durch Immediate-Werte oder Adressen überlagert werden. Ich verbrachte viel Zeit mit dem Feintuning der DBSCAN- und HDBSCAN-Parameter, um eine bessere Darstellung zu finden, hatte aber schließlich genug davon.
Ich hatte Bedenken, dass das vorhandene Wissen des KI-Agenten über NVIDIA und Maxwell ein Experiment beeinflussen könnte, das mir helfen sollte, das Binärformat zu verstehen. Ich wollte seine Schlussfolgerungen mit bestehenden Ergebnissen vergleichen, daher wies ich den Agenten an, sich den Daten zu nähern, ohne sich auf NVIDIA-spezifische Erklärungen zu stützen.
Ich bat den Agenten auch nicht darum, das Binärformat selbstständig zu entschlüsseln. Ich wollte meine Clustering-Idee weiterhin selbst verfolgen. Deshalb ließ ich den Agenten über Nacht laufen mit der Aufgabe, mit DBSCAN- und HDBSCAN-Parametern zu experimentieren, Erkenntnisse zu dokumentieren und das Rauschen so weit wie möglich zu reduzieren.
Außerdem wies ich ihn an, meinen Python-Code bei Bedarf zu optimieren und eine gewichtete Hamming-Distanz auszuprobieren.
Der Bericht des KI-Agenten zur ungewichteten Hamming-Distanz deutete darauf hin, dass der Clustering-Ansatz nicht unbedingt falsch angewendet wurde; vielmehr waren Teile der Daten zu verstreut, um nützliche Cluster zu bilden:
| data | best | clusters | noise | |-------------|------------------------------|----------|-------| | all words | HDBSCAN `mcs=5, ms=1, eom` | 572 | 28 % | | all words | DBSCAN `eps=2, ms=2` | 1886 | 14 % | | type A only | DBSCAN `eps=1, ms=2` | 407 | 12 % | | type B only | HDBSCAN `mcs=3, ms=1, eom` | 1318 | 27 % | | type B only | DBSCAN `eps=2, ms=3` | 789 | 25 % | Bei gleicher Gewichtung schnitten beide Algorithmen in den getesteten Konfigurationen bei relativ feinkörnigen Einstellungen am besten ab. Bits mit hoher Entropie in den Operanden schienen die Distanz zu dominieren und potenzielle Gruppen aufzubrechen. Größere Werte für `min_samples` oder `min_cluster_size` führten tendenziell dazu, dass mehr Wörter als Rauschen eingestuft wurden.
HDBSCAN mit `eom` schnitt in diesen Tests besser ab als `leaf`, und `min_samples=1` lieferte in den verglichenen Konfigurationen die besten Ergebnisse. Vollbildmodus aktivieren Vollbildmodus verlassen Der große Durchbruch Ein Ergebnis des KI-Agenten zog sofort meine Aufmerksamkeit auf sich: Ich hatte die Möglichkeit übersehen, dass die Position des Wortes eine Rolle spielen könnte.
Alle Dateigrößen sind Vielfache von 32 Bytes. Ein Vergleich der Wörter an den Offsets 0 mod 4 (Typ A) mit den Wörtern an den Offsets 1 und 3 mod 4 (Typ B) zeigte unterschiedliche Statistiken: etwa 3.258 gegenüber 5.300 verschiedenen Werten pro Slot und mittlere Popcounts von 24,8 gegenüber 18,6. Vollbildmodus aktivieren Vollbildmodus verlassen Ich war davon ausgegangen, dass das Binärformat nur echte Instruktionen enthielt und nicht möglicherweise periodische Daten, die keine Instruktionen sind. Ich prüfte die Beobachtung gegen die Daten:
$ xxd -e -g8 -c8 kernel-_Z9dwtHaar1DPfS_S_jji.sm_50.elf.bin | awk '{ if (NR % 4 == 1) { print $2 } }' | head -n20 001c4400fe0007f6 081fc401fec0073f 001f8400fec217f6 081fc400fea207f1 001fc000fec007f1 0002c440fe0007b2 081fcc00fe2007e1 003fd440fe2007f2 081fc400fea007e1 041fc400fee007f6 001fd400ffe007f1 001ffc00fcc00711 001fbc00feaa0ff1 001ffc00fe0007e1 0003d000fe0007f5 001fbc00fde007f1 001fd400ffe007e9 001fbc00fde007ef 083fc400ffa007e8 001fc400fe2007f1 Vollbildmodus aktivieren Vollbildmodus verlassen Die Wörter an den durch vier teilbaren Offsets schienen ein anderes Muster aufzuweisen als die Wörter an den Offsets 1 und 3 modulo vier. Die Analyse des KI-Agenten half mir, diesen Unterschied zu erkennen, den ich anschließend gegen die Daten prüfte. Ich habe noch nicht herausgefunden, was das Muster, falls überhaupt etwas, über das zugrunde liegende Binärformat aussagt.
Dies war mein erstes Experiment mit Data Clustering für Reverse Engineering. Aunque die Clustering-Ergebnisse unvollkommen waren, zeigte mir das Experiment, dass die Hamming-Distanz Struktur in Binärdaten offenbaren kann.
Das nützlichste Ergebnis war eine Beobachtung, die ich übersehen hatte: Wörter an unterschiedlichen Positionen im Binärformat schienen unterschiedliche statistische Eigenschaften zu haben. Ein KI-Agent half mir, dieses Muster zu erkennen, das ich anschließend gegen die Daten prüfte.
Was dieses positionale Muster bedeutet, habe ich noch nicht herausgefunden. Im Moment ist es einfach eine Beobachtung, die eine weitere Untersuchung wert ist.
Ein KI-Agent kann auch dann nützlich sein, wenn er das Problem nicht direkt löst: Er kann Experimente durchführen, Ergebnisse vergleichen und helfen, Muster zu identifizieren, die eine genauere Betrachtung verdienen.
Einige Kommentare sind möglicherweise nur für angemeldete Besucher sichtbar. Melde dich an, um alle Kommentare zu sehen.
Automatisch übersetzt. Das Original auf Englisch ist unten aufklappbar.
Original (Englisch) anzeigen
Posted on Oct 9 • Originally published at poljak-engineering.com
I am not a data scientist/engineer, but I wanted to do a little experiment on NVIDIA Cubin binary code. I recalled my colleague's thesis on Data Clustering and wondered what would actually happen if we tried something like that on an NVIDIA binary?
My assumption was that, if we managed to find a good distance metric, we could categorize instructions and gain a higher-level insight into how NVIDIA CUDA binaries are constructed.
The Hamming distance between two fixed-length binary words is the number of bit positions at which they differ. For our 64-bit words, we can calculate it using XOR followed by a population count:
dist = ( insn1 ^ insn2 ). bit_count () Enter fullscreen mode Exit fullscreen mode The XOR identifies the differing bits, and bit_count() counts them. The fewer bits two words differ in, the closer they are under this metric.
Mathematically, we can view our data as a subset of the 64-bit binary words, with the Hamming distance as the metric. In other words, our two instructions are closer the more bits they have in common. They are further apart the more bits they differ in.
My own CUDA kernel code could provide very little data. It was about 24 instructions in length, and rather than adding random code, I decided to check out the cuda-samples repository:
My target architecture, sm_50, was too old to compile these samples using the documented instructions, so I simply picked one sample and compiled it manually:
cd./cpp/5_Domain_Specific/recursiveGaussian nvcc -arch = sm_50 -cubin recursiveGaussian_cuda.cu -I /home/stjepan/Develop/cuda-samples/Common/ -o kernel.cubin Enter fullscreen mode Exit fullscreen mode This gave me the Cubin ELF, but I still needed to extract the raw binary code. I used the NVIDIA-provided tools for this:
$ cuobjdump -ltext../kernel.cubin SASS text section 1: kernel-_Z24d_recursiveGaussian_rgbaPjS_iiffffffff.sm_50.elf.bin SASS text section 2: kernel-_Z22d_simpleRecursive_rgbaPjS_iif.sm_50.elf.bin SASS text section 3: kernel-_Z11d_transposePjS_ii.sm_50.elf.bin Enter fullscreen mode Exit fullscreen mode To extract these sections, change -ltext to -xtext. My small database of NVIDIA binary data was now much more promising (and more statistically significant):
$ ls *.bin | xargs -I{} xxd -e -g 8 -c 8 {} | wc -l 2280 Enter fullscreen mode Exit fullscreen mode Subsequently, I compiled a lot more CUDA binaries and added more than 40000 instructions. Due to performance constraints, I opted to limit the dataset to 12000 instructions.
For my first experiment, I was not at all disappointed. I installed the scikit-learn and numpy packages for my Python script. Scikit-learn provides the DBSCAN clustering algorithm, and my first attempt was something as simple as:
import numpy as np from sklearn.cluster import DBSCAN from pathlib import Path import struct def cluster ( insns ): dist = np. zeros (( len ( insns ), len ( insns )), dtype = np. float64 ) for i in range ( len ( insns )): for j in range ( i + 1, len ( insns )): d = ( insns [ i ] ^ insns [ j ]). bit_count () dist [ i, j ] = d dist [ j, i ] = d clusters = DBSCAN ( eps = 5, # epsilon (how far points in a cluster can be) min_samples = 10, # minimum number of samples a cluster must have metric = " precomputed " ). fit_predict ( dist ) c_dict = {} for i in range ( 0, len ( clusters )): c = clusters [ i ] if not c in c_dict: c_dict [ c ] = [ insns [ i ]] else: c_dict [ c ] += [ insns [ i ]] return c_dict Enter fullscreen mode Exit fullscreen mode Sample output This already provided useful data. The following is output showing five samples per cluster (the original dataset contains 12000 sampled instructions):
_______[ 0 ]_______ _______[ 9 ]_______ _______[ 18 ]_______ _______[ 29 ]_______ 0x001cc400e22007f6 0xe2400ffff400000f 0x5c403200026720ff 0x1e03fb8aa3b7170c 0x001fd801fec0075d 0xe2400fffe408000f 0x4c413008001722ff 0x1e03fb8aa3b71a08 0x089fec02fc2007f1 0xe2400fffff87000f 0x4c413008001723ff 0x1e03fb8aa3b7120b 0x001ff400ffa007f0 0xe2400fffff87000f 0x5c423200017714ff 0x1e03fb8aa3b7190a 0x003fd800e3a007fd 0xe2400fffc889000f 0x5c423200019718ff 0x1e03fb8aa3b7140c _______[ 1 ]_______ _______[ 32 ]_______ _______[ 16 ]_______ _______[ 30 ]_______ 0x4c98078000870001 0x32807fdf80070303 0x30cd83ff800722ff 0x37be03c2fc070c1f 0x4cb8000005472a03 0x32807fdf80082222 0x30cd83ff80070eff 0x37be03c2fc070817 0xf0c8000002570002 0x32807fdf80092323 0x30cd83ff800704ff 0x37be03c2fc070b07 0xf0c8000002170004 0x32807fdf80080e0e 0x30cd83ff80070dff 0x37be03c2fc070a0f 0x1c00180000070300 0x32807fdf80091010 0x30cd83ff800707ff 0x37be03c2fc070c27 _______[ 2 ]_______ _______[ 10 ]_______ _______[ 17 ]_______ _______[ 38 ]_______ 0x0407f80000070000 0x040007fffff7030a 0x36bd83ff80072397 0x5bdf7f81f0670506 0x0423f80000070a05 0x040007fffff70806 0x36bd83ff80072287 0x5bdf7f81c0770705 0x0427f80000072121 0x040007fffff72020 0x36bd83ff8007108f 0x5bdf7f81c0470404 0x0427f80000072121 0x040007fffff70a0c 0x36bd83ff80070e87 0x5bdf7f81c0770705 0x0407f80000070404 0x040007fffff70604 0x36bd83ff80070597 0x5bdf7f81c0470404 _______[ 3 ]_______ _______[ 36 ]_______ _______[ 19 ]_______ _______[ 33 ]_______ 0x4b68038800070007 0x38423000002709ff 0x3659038000a71514 0x537104080007060a 0x4b6d038005470007 0x38403000001709ff 0x3659038000a70517 0x537104080007060a 0x5b6403800ff70317 0x38423000002709ff 0x3659038000aa1617 0x5b710a000087060c 0x5b20030800970605 0x38403000001709ff 0x3659038000a71618 0x5371020800070608 0x5b28038000970607 0x38403000007700ff 0x3659038000a71519 0x5371020800070616 _______[ 4 ]_______ _______[ 11 ]_______ _______[ 20 ]_______ _______[ 34 ]_______ 0xe260000052000040 0xda1005affff70202 0x36b403c080071317 0x386800437f070404 0xe29000002a000000 0xda1005affff70404 0x36b403c080071307 0x386800437f070505 0xe290000020000000 0xda1005affff70202 0x36b403c080071707 0x386800437f070606 0xe2600000fc800040 0xda1005affff70404 0x36b403c080071707 0x386800437f070707 0xe290000015000000 0xda0006effff70303 0x36b403c080071707 0x386800437f070206 _______[ 7 ]_______ _______[ 12 ]_______ _______[ 21 ]_______ _______[ 35 ]_______ 0x1c00ffffffe70506 0x3868003f00070a12 0x328002c000071414 0x5be70b0780d70c0c 0x1c0ffffffff70606 0x3868003f00070f0f 0x328002c000071313 0x5be7098780e70c0c 0x1c0ffffffff7050d 0x3868003f0007060a 0x328002c000071313 0x5be7070780f70c0f 0x1c0ffffffff70003 0x3868003f00070709 0x328002c000071313 0x5be7068780870f08 0x1c0ffffffff70603 0x3858003f00070000 0x328002c000071313 0x5be70b0780970808 _______[ 28 ]_______ _______[ 13 ]_______ _______[ 22 ]_______ _______[ 37 ]_______ 0x5c4707000047ff04 0x0103f8000007f007 0x368403c010071e17 0x1e03f3504f370303 0x5c6007800027ff03 0x0103f8000007f018 0x368403c010071e07 0x1e03f3504f370b0b 0x5c2107800037ff03 0x0103f8000007ff03 0x368403c010071e07 0x1e03f3504f370e0e 0x5c60078001a7ff17 0x0103f8000007f021 0x368403c010071e07 0x1e03f3504f370d0d 0x5c6007800127ff09 0x0103f8000007f027 0x368403c010071e07 0x1e03f3504f370d0d _______[ -1 ]_______ _______[ 14 ]_______ _______[ 23 ]_______ _______[ 39 ]_______ 0x4cc0018005470404 0x4801038006670310 0x002c4800eee00711 0x36b403c37f070a17 0x5cc002a000870705 0x4801038006670414 0x002c4800eee00711 0x36b403c37f071f07 0x5b28030000470505 0x4801038006670515 0x002c4800eee00711 0x36b403c37f070b1f 0x5c4707000032ff05 0x4801038006670615 0x002c4800eee00711 0x36b403c37f07090f 0x32807fdf80070202 0x480103800667070e 0x002c4800eee00711 0x36b403c37f072607 _______[ 5 ]_______ _______[ 24 ]_______ _______[ 25 ]_______ _______[ 40 ]_______ 0x366c03800037050f 0x36f0058010171410 0x011c7801e2404776 0x5bae05000ff7200a 0x3668038000170407 0x3670054000071416 0x011c7801e2404776 0x5bae0f800ff70808 0x366803800fd72707 0x3670054000071416 0x011c7801e2404776 0x5bae05800ff7200b 0x366820000fd72407 0x3670054000071416 0x011c7801e2404776 0x5bae04800ff71f09 0x366c03800fe72007 0x3670054000071416 0x011c7801e2404776 0x5bae13000ff70808 _______[ 6 ]_______ _______[ 15 ]_______ _______[ 26 ]_______ _______[ 41 ]_______ 0xeed4200000070407 0xf0a81b8000070000 0x003ff401e3a00f06 0x338001437f070302 0xeed4200000070408 0xf0a81b8000070000 0x003ff401e3a00f06 0x338003437f070c0a 0xeedc200000070407 0xf0a81b8000070000 0x003ff401e3a00f06 0x338003437f070006 0xeed4200000070805 0xf0a81b8000070000 0x003ff401e3a00f06 0x338003c37f070006 0xeed4200000070c0b 0xf0a81b8000070000 0x003ff401e3a00f06 0x338003437f070006 _______[ 8 ]_______ _______[ 31 ]_______ _______[ 27 ]_______ _______[ 42 ]_______ 0xf0f0000034170000 0x30cc03ff80072326 0xd820056ff0470606 0x010437f00007f025 0xf0f0000034670000 0x30cc03ff80070e0c 0xd82005aff0570b08 0x010437f00007f025 0xf0f0000034470000 0x30cc03ff80071011 0xd82005aff0570609 0x010437f00007f025 0xf0f0000034270000 0x30cc03ff80070406 0xd82005aff057070d 0x010437f00007f025 0xf0f0000034670000 0x30cc03ff80070507 0xd82005aff0570a0e 0x010437f00007f025 Enter fullscreen mode Exit fullscreen mode DBSCAN has produced groups of binary words with similar bit patterns. The only exception is the -1 cluster, which essentially means "unassigned" or, as I prefer to call it, "noise". DBSCAN puts data there when it cannot assign it to a cluster.
In clusters 13 and 42, we can see the MOV-like instruction from our previous reverse-engineering exercise:
_______[ 13 ]_______ _______[ 42 ]_______ 0x0103f8000007f007 0x010437f00007f025 0x0103f8000007f018 0x010437f00007f025 0x0103f8000007f01d 0x010437f00007f025 0x0103f8000007f021 0x010437f00007f025 0x0103f8000007f027 0x010437f00007f025 Enter fullscreen mode Exit fullscreen mode Similarly, here is the second instruction we tinkered with in the previous article:
_______[ 6 ]_______ 0xeed4200000070407 0xeed4200000070408 0xeedc200000070407 0xeed4200000070805 0xeed4200000070c0b Enter fullscreen mode Exit fullscreen mode How could we sort these instructions out further? One thing we can do is apply bitwise AND to instructions like the ones in bins 13 and 42 to find out what they have in common:
TEST = [ 0x0103b8080817f003, 0x0103f8000007f002, 0x0103b8080817f000, 0x0103f8000007f006, 0x0103b8080817f000, 0x010437f00007f025 ] and_val = TEST [ 0 ] for each in TEST: and_val &= each print ( f " { and_val: 016 x } " ) Enter fullscreen mode Exit fullscreen mode For example, this gives us the following:
010030000007f000 Enter fullscreen mode Exit fullscreen mode So, except for the digit 3, we seem to be getting closer to the instruction's structure. If we could combine this with our clustering approach, we might be able to extract more information about the format.
A little investigation led me to HDBSCAN, which seemed to give me more control over the clustering results:
clusters = hdbscan. HDBSCAN ( min_cluster_size = min_size, min_samples = samples, cluster_selection_method = " eom ", metric = " precomputed " ). fit_predict ( dist ) Enter fullscreen mode Exit fullscreen mode It seemed to produce more specific clusters, but many samples still ended up in the "noise" cluster.
I had already described how we can use bitwise AND to get the common bit pattern of a cluster. Bitwise OR can also provide useful information about which bits vary across the data. My code combined these two operations while preserving cluster-size information:
c_dict = {} noise = [] for i in range ( 0, len ( clusters )): c = clusters [ i ] if c == - 1: noise. append ( insns [ i ]) elif c not in c_dict: c_dict [ c ] = [ insns [ i ]] else: c_dict [ c ] += [ insns [ i ]] res = {} for ( key, val ) in c_dict. items (): first = val [ 0 ] orval = val [ 0 ] for each in val [ 1:]: first &= each orval |= each orval ^= first if first not in res: res [ first ] = ( orval, val ) else: ( old_orval, old_val ) = res [ first ] res [ first ] = ( old_orval | orval, old_val + val ) Enter fullscreen mode Exit fullscreen mode Later, I also added per-bit frequencies and a noise percentage:
total = 0 for ( key, val ) in res. items (): total += len ( val [ 1 ]) print ( f " { key: 016 x } { val [ 0 ]: 016 x } ( { len ( val [ 1 ]): 4 } ) " ) freqs = bit_frequencies ( val [ 1 ]) print_frequencies ( freqs ) count = 0 for each in val [ 1 ]: if count > 5: break else: print ( f " { each: 016 x } " ) count += 1 print ( "" ) print ( f " TOTAL: { total } " ) noise_len = len ( noise ) print ( f " NOISE: { noise_len: 4 } { ( noise_len / ( total + noise_len )) * 100 } % " ) Enter fullscreen mode Exit fullscreen mode The results were OK, but not entirely satisfying. Here is one example:
5c9807800ff00000 00000000000f003f ( 85) * 01011100100110000000011110000000000011111111____00000000000_____ 5c9807800ff7001e 5c9807800ff7001b 5c9807800ff70017 5c9807800ff7000b 5c9807800ff80020 5c9807800ff00020 308c03ff80070000 0671800000003fff ( 45) * 00110__01___110__000001111111111100000000000011100______________ 30cc03ff80072220 30cc03ff80072326 30cd83ff800722ff 36bd83ff80072397 36bd83ff80072287 30cc03ff80070e0c e34000000007000f 0000000000000000 ( 125) * 1110001101000000000000000000000000000000000001110000000000001111 e34000000007000f e34000000007000f e34000000007000f e34000000007000f e34000000007000f e34000000007000f 3280004000070000 0102078140001f1f ( 75) * 0011001_100000_000000____100000_0_00000000000111000_____000_____ 328002c000071414 328002c000071313 328002c000071313 328002c000071313 328002c000071313 328002c000071313 5c47000000000000 0000060001f70f0f ( 90) * 010111000100011100000100000000000000000_____0___00000___00000___ 5c47040000a70505 5c47040000870202 5c47040000870b0b 5c47040000870f0f 5c47000000c70e0e 5c47000000470505 4880000800070000 05201f8000303f3f ( 57) * 01001_0_10_0000000000____00010000000000000__011100______00______ 4980060800270909 4980040800270b0b 4ca004080027140c 4ca0008800070f09 4ca0008800070b0e 4ca0000800070b0f 300000427c070000 0ffe1f8183003f3f ( 164) * 0011___________0000______100001__11111__0000011100______000_____ 37be03c2fc070c1f 37be03c2fc070817 37be03c2fc070b07 37be03c2fc070a0f 37be03c2fc070c27 37be03c2fc071437 TOTAL: 6921 NOISE: 5079 42.325% Enter fullscreen mode Exit fullscreen mode The bit fields indicate the per-bit frequencies. If the frequency of a particular bit in the cluster exceeds or falls below a threshold, it is represented as 1 or 0, respectively. If it varies across the cluster, it is represented as _.
The biggest problem, however, was the amount of noise. I could reduce it, but then cluster 0 grew:
0000000000000000 7ffbbf9017ff3f3f (1406) * 010_1100_____000000000000000000000000_0_____0111000_____000_____ 4cb8000005472a03 1c00180000070300 4e00020000270204 5cb8010000370a05 5cb0118000670a06 5c10000000370004 Enter fullscreen mode Exit fullscreen mode Many instructions ended up in this cluster because all bits had equal weights. Bits representing instruction structure could be outweighed by immediate values or addresses. I spent a lot of time tinkering with DBSCAN and HDBSCAN parameters, trying to find a better representation, but eventually I got tired of it.
I was concerned that the AI agent's existing knowledge of NVIDIA and Maxwell might influence an experiment intended to help me understand the binary format. I wanted to compare its conclusions with existing results, so I instructed the agent to approach the data without relying on NVIDIA-specific explanations.
I didn't ask the agent to decipher the binary independently, either. I still wanted to explore my clustering idea. So I left the agent running overnight, asking it to experiment with DBSCAN and HDBSCAN parameters, document any insights, and reduce the noise as much as possible.
I also instructed it to optimize my Python code if necessary and to try weighted Hamming distance.
The AI agent's report on unweighted Hamming distance suggested that the clustering approach was not necessarily being used incorrectly; rather, some of the data was too dispersed to form useful clusters:
| data | best | clusters | noise | |-------------|------------------------------|----------|-------| | all words | HDBSCAN `mcs=5, ms=1, eom` | 572 | 28 % | | all words | DBSCAN `eps=2, ms=2` | 1886 | 14 % | | type A only | DBSCAN `eps=1, ms=2` | 407 | 12 % | | type B only | HDBSCAN `mcs=3, ms=1, eom` | 1318 | 27 % | | type B only | DBSCAN `eps=2, ms=3` | 789 | 25 % | With equal weights, both algorithms performed best at relatively fine-grained settings in the configurations tested. High-entropy operand bits appeared to dominate the distance and break potential groups apart. Larger `min_samples` or `min_cluster_size` values tended to push more words into noise.
HDBSCAN `eom` performed better than `leaf` in these tests, and `min_samples=1` gave the best results in the configurations compared. Enter fullscreen mode Exit fullscreen mode The big breakthrough One finding from the AI agent immediately caught my attention: I had overlooked the possibility that word position might matter.
All file sizes are multiples of 32 bytes. A comparison of words at offset 0 mod 4 (type A) with words at offsets 1 and 3 mod 4 (type B) showed different statistics: about 3,258 versus 5,300 distinct values per slot, and mean popcounts of 24.8 versus 18.6. Enter fullscreen mode Exit fullscreen mode I had assumed that the binary contained only real instructions, rather than potentially including periodic non-instruction data. I checked the observation against the data:
$ xxd -e -g8 -c8 kernel-_Z9dwtHaar1DPfS_S_jji.sm_50.elf.bin | awk '{ if (NR % 4 == 1) { print $2 } }' | head -n20 001c4400fe0007f6 081fc401fec0073f 001f8400fec217f6 081fc400fea207f1 001fc000fec007f1 0002c440fe0007b2 081fcc00fe2007e1 003fd440fe2007f2 081fc400fea007e1 041fc400fee007f6 001fd400ffe007f1 001ffc00fcc00711 001fbc00feaa0ff1 001ffc00fe0007e1 0003d000fe0007f5 001fbc00fde007f1 001fd400ffe007e9 001fbc00fde007ef 083fc400ffa007e8 001fc400fe2007f1 Enter fullscreen mode Exit fullscreen mode The words at offsets divisible by four appeared to have a different pattern from the words at offsets 1 and 3 modulo four. The AI agent's analysis helped me notice this difference, which I then checked against the data. I haven't established what, if anything, the pattern tells us about the underlying binary format.
This was my first experiment with data clustering for reverse-engineering. Although the clustering results were imperfect, the experiment showed me that Hamming distance can reveal structure in binary data.
The most useful outcome was an observation I had overlooked: words at different positions in the binary appeared to have different statistical properties. An AI agent helped me notice this pattern, which I then checked against the data.
I haven't established what this positional pattern means yet. For now, it's simply an observation worth investigating further.
An AI agent can be useful even when it doesn't solve the problem outright: it can run experiments, compare results, and help identify patterns that deserve a closer look.
Some comments may only be visible to logged-in visitors. Sign in to view all comments.