概要
fuzzyhashを使って、次の2点を試してみました。使ったはssdeepコマンドです。
- ①csvファイルの類似性を算出する
- ②多数のcsvファイルを類似性でクラスタリングする
目的は、多数あるcsvファイル群から似たファイルを探すことです。
結論
①csvファイルの類似性算出
ざっくりいうと、比較的大きな部分一致が存在するケースを検出できました。
検出できるケース
- ファイルの一部がまるっと削除された場合
- ファイルに共通部分（同一の行・同一の列が同じ順序で並んでいる）が多い場合
検出できないケース
- 行の順序が変わった場合
- 列が削除されたり、列が交換された場合
- ファイルに共通部分（同一の行・同一の列が同じ順序で並んでいる）が少ない場合
②多数のcsvファイルを類似性でクラスタリングする
- 多数のファイルをクラスタリングしようとすると不安定(coredump）→いったん断念。
fuzzyhashとは
ざっくりで言うと，ファイルの内容が似ていれば似た値を出力するハッシュの一種です。理論的なことはよくわからないので参考文献を参照してください。論文で使われていたりマルウェア検出にも使われているので、実績のある技術と考えています。
ファイルの内容を比較するために，md5sum,sha1sum,sha256sumコマンドなどでファイルのハッシュ値の一致で判断することはよくあるユースケースです。ただ，これらのコマンドの出力はファイル内容が1ビットでも異なっていれば異なる値を出力します。ですので，完全一致を確かめるにはよいのですが，ファイル同士が似ているかという判断には使えません。
一方でFuzzyhashは，ファイル内容が似ていれば似た値を算出してくれます。このハッシュ値を活用すると、ファイル内容がだいたい同じで一部違っている場合に類似性を数値で評価してくれます。
fussyhashをバイナリファイル（特にマルウェア）に適用する事例は多く見つかったのですが，テキストファイルやcsvファイルに適用した事例があまり見当たらなかったので試してみました。
fuzzyhashを出力するコマンド
fuzzyhash算出の実装としてssdeepコマンドがあります。(manの日本語訳を作りました)
ubuntu標準パッケージでもssdeepコマンドが提供されており，以下のコマンドでインストールできます。
$ sudo apt install ssdeep
ssdeepの使い方
類似度を計算する
使い方ですが、ざっくり2段階です。
1段階目：全ファイルのfuzzyhash値を計算してファイル(hashes.txt)に出力する
$ ssdeep * > hashes.txt
2段階目：1段階目で出力したハッシュ値の集合(hashes.txt)を、対象ファイルと比較する
$ ssdeep -m hashes.txt *
類似スコアは0-100で計算され、上記のコマンドではスコア1～100のファイルが表示されます。なお同一ファイルも比較対象になるため、スコア100の組み合わせとして表示されます。もし同一ファイルの表示が不要な場合には、（多少乱暴ですが）結果から"(100)"を省きます。
$ ssdeep -m hashes.txt * | grep -v -e '(100)'
クラスタリング（分類）する
試したこと
個人情報テストデータジェネレーターで1万レコードのCSVファイルを2種類(1-00_base1.csvと2-00_base2.csv)作成し，それをベースに加工したファイルのfuzzyhashを取得してみました。この元データのサブセットを作成して，ssdeepでfuzzyhashを算出します。
加工したcsvデータは，以下の通りです。加工内容はファイル名から察してください。細かい説明は端折ります。ファイルサイズが違うので，sha256sumを実行しても異なる値が出てきます。（当たり前すぎるのでsha256sumの出力結果は省略）
$ ls -l
合計 30696
-rw-rw-r-- 1 testdb testdb 1905786 11月 4 18:07 1-00_base1.csv
-rw-rw-r-- 1 testdb testdb 1905786 11月 3 00:52 1-01-1.base1を携帯電話番号でソート.csv
-rw-rw-r-- 1 testdb testdb 1905786 11月 3 00:53 1-01-2.base1を誕生日でソート.csv
-rw-rw-r-- 1 testdb testdb 1905786 11月 3 00:51 1-01-3.base1を郵便番号でソート.csv
-rw-rw-r-- 1 testdb testdb 1500576 11月 3 00:57 1-02-1.base1から住所列を削除.csv
-rw-rw-r-- 1 testdb testdb 1775773 11月 3 00:59 1-02-2.base1から電話番号を削除.csv
-rw-rw-r-- 1 testdb testdb 380873 11月 3 01:02 1-03_base1の上位8000件を削除.csv
-rw-rw-r-- 1 testdb testdb 299874 11月 3 01:04 '1-04_(1-3_base1)から住所情報を削除.csv'
-rw-rw-r-- 1 testdb testdb 299874 11月 3 01:07 '1-05_(1-4_base1)を携帯電話番号でソート.csv'
-rw-rw-r-- 1 testdb testdb 922596 11月 3 01:10 1-06_base1から氏名と住所を削除.csv
-rw-rw-r-- 1 testdb testdb 822488 11月 3 01:17 '1-07_(1-6_base1をランダムに半分削除_A.csv'
-rw-rw-r-- 1 testdb testdb 952196 11月 3 01:21 1-08-1_base1の上位5000件を削除.csv
-rw-rw-r-- 1 testdb testdb 953567 11月 3 02:23 1-08-2_base1の下位5000件を削除.csv
-rw-rw-r-- 1 testdb testdb 1715405 11月 3 01:24 1-08-3_base1の上位1000件を削除.csv
-rw-rw-r-- 1 testdb testdb 1905786 11月 3 01:27 1-09_base1の列を適当に入れ替え.csv
-rw-rw-r-- 1 testdb testdb 14538 11月 3 01:33 '1-10-1_(1-9_base1)から沖縄だけ抽出.csv'
-rw-rw-r-- 1 testdb testdb 674412 11月 3 01:34 '1-10-2_(1-9_base1)から東京だけ抽出.csv'
-rw-rw-r-- 1 testdb testdb 140017 11月 3 01:36 1-11-1_base1から電話番号だけを残す.csv
-rw-rw-r-- 1 testdb testdb 280036 11月 3 01:38 1-11-2_base1から電話番号と携帯番号だけを残す.csv
-rw-rw-r-- 1 testdb testdb 1904197 11月 4 18:07 2-00_base2.csv
-rw-rw-r-- 1 testdb testdb 1499384 11月 4 18:00 2-01-1_base2の住所列を削除.csv
-rw-rw-r-- 1 testdb testdb 280036 11月 4 18:01 2-01-2_base2を電話番号だけ残す.csv
-rw-rw-r-- 1 testdb testdb 677974 11月 4 18:02 2-02-1.base2の東京だけ残す.csv
-rw-rw-r-- 1 testdb testdb 14901 11月 4 18:03 2-02-2_base2の沖縄だけ残す.csv
-rw-rw-r-- 1 testdb testdb 952212 11月 4 18:06 2-03_base2の下位5000件を残す.csv
-rw-rw-r-- 1 testdb testdb 1017157 11月 4 18:04 2-03_base2の上位5000件を残す.csv
-rw-rw-r-- 1 testdb testdb 950997 11月 5 08:56 2-03_base2の真ん中付近を5000件削除.csv
-rw-rw-r-- 1 testdb testdb 1904197 11月 4 18:06 2-04_base2を携帯電話番号でソート.csv
-rw-rw-r-- 1 testdb testdb 1905802 11月 5 09:01 9-00_base1上位5000件とbase2下位5000件をマージ.csv
①類似度を算出
これらのファイルに対して、ファイル間の類似度を計算してみます。なお、そのままではファイル名がフルパス表示になるので-bオプションでファイル名だけ表示するようにします。
$ ssdeep -b * > hashes.txt
$ ssdeep -b -m hashes.txt * | grep -v -e '(100)'
1-00_base1.csv matches hashes.txt:1-08-1_base1の上位5000件を削除.csv (61)
1-00_base1.csv matches hashes.txt:1-08-2_base1の下位5000件を削除.csv (69)
1-00_base1.csv matches hashes.txt:1-08-3_base1の上位1000件を削除.csv (96)
1-00_base1.csv matches hashes.txt:9-00_base1上位5000件とbase2下位5000件をマージ.csv (55)
1-08-1_base1の上位5000件を削除.csv matches hashes.txt:1-00_base1.csv (61)
1-08-1_base1の上位5000件を削除.csv matches hashes.txt:1-08-3_base1の上位1000件を削除.csv (63)
1-08-2_base1の下位5000件を削除.csv matches hashes.txt:1-00_base1.csv (69)
1-08-2_base1の下位5000件を削除.csv matches hashes.txt:1-08-3_base1の上位1000件を削除.csv (63)
1-08-2_base1の下位5000件を削除.csv matches hashes.txt:9-00_base1上位5000件とbase2下位5000件をマージ.csv (65)
1-08-3_base1の上位1000件を削除.csv matches hashes.txt:1-00_base1.csv (96)
1-08-3_base1の上位1000件を削除.csv matches hashes.txt:1-08-1_base1の上位5000件を削除.csv (63)
1-08-3_base1の上位1000件を削除.csv matches hashes.txt:1-08-2_base1の下位5000件を削除.csv (63)
1-08-3_base1の上位1000件を削除.csv matches hashes.txt:9-00_base1上位5000件とbase2下位5000件をマージ.csv (49)
2-00_base2.csv matches hashes.txt:2-03_base2の下位5000件を残す.csv (77)
2-00_base2.csv matches hashes.txt:2-03_base2の上位5000件を残す.csv (50)
2-00_base2.csv matches hashes.txt:2-03_base2の真ん中付近を5000件削除.csv (66)
2-00_base2.csv matches hashes.txt:9-00_base1上位5000件とbase2下位5000件をマージ.csv (68)
2-03_base2の下位5000件を残す.csv matches hashes.txt:2-00_base2.csv (77)
2-03_base2の下位5000件を残す.csv matches hashes.txt:2-03_base2の真ん中付近を5000件削除.csv (52)
2-03_base2の下位5000件を残す.csv matches hashes.txt:9-00_base1上位5000件とbase2下位5000件をマージ.csv (69)
2-03_base2の上位5000件を残す.csv matches hashes.txt:2-00_base2.csv (50)
2-03_base2の上位5000件を残す.csv matches hashes.txt:2-03_base2の真ん中付近を5000件削除.csv (99)
2-03_base2の真ん中付近を5000件削除.csv matches hashes.txt:2-00_base2.csv (66)
2-03_base2の真ん中付近を5000件削除.csv matches hashes.txt:2-03_base2の下位5000件を残す.csv (52)
2-03_base2の真ん中付近を5000件削除.csv matches hashes.txt:2-03_base2の上位5000件を残す.csv (99)
2-03_base2の真ん中付近を5000件削除.csv matches hashes.txt:9-00_base1上位5000件とbase2下位5000件をマージ.csv (44)
9-00_base1上位5000件とbase2下位5000件をマージ.csv matches hashes.txt:1-00_base1.csv (55)
9-00_base1上位5000件とbase2下位5000件をマージ.csv matches hashes.txt:1-08-2_base1の下位5000件を削除.csv (65)
9-00_base1上位5000件とbase2下位5000件をマージ.csv matches hashes.txt:1-08-3_base1の上位1000件を削除.csv (49)
9-00_base1上位5000件とbase2下位5000件をマージ.csv matches hashes.txt:2-00_base2.csv (68)
9-00_base1上位5000件とbase2下位5000件をマージ.csv matches hashes.txt:2-03_base2の下位5000件を残す.csv (69)
9-00_base1上位5000件とbase2下位5000件をマージ.csv matches hashes.txt:2-03_base2の真ん中付近を5000件削除.csv (44)
結果をざっくりいうと、比較的大きな部分一致が存在するケースのみを検出できています。
列単位での削除や、ソート、特定条件の未抽出など、部分一致の範囲が小さくなるケースは類似と判断できないようです。
②クラスタリング
$ ssdeep -g -b -m hashes.txt *
** Cluster size 2
Segmentation fault (コアダンプ)
おえん(岡山弁で「ダメだ」の意)、coredump吐きおった。
参考文献
類似度を用いたファイル追跡に関する一手法の提案
類似度の高いファイル構造に基づくマルウェア情報提供システムの提案
Import APIとFuzzy Hashingでマルウエアを分類する ～impfuzzy～(2016-05-09)
Fuzzyhashとは？検証してみた
Fuzzy hashingの利用に関する検討及び評価
fuzzyhashについて