趣味でやるマルウェア解析
はじめに
これはセキュリティキャンプ 修了生進捗 #seccamp OB/OG Advent Calendar 2018 の22日目の記事です
今夏のセキュリティキャンプのチューターをやったときあたりから、本格的にマルウェア解析に興味が湧いてきたので、色々調べたことを公開するエントリを書くことにしました。マルウェア解析というものは独学でやるには敷居もリスクも高く、企業や研究機関に所属していないと本格的に行うことは難しいと思います。そこで、ここでは趣味でやるマルウェア解析と称して、出来るだけ敷居を下げられるように色々とマルウェア解析関連の資料をまとめました。
ただ、私はマルウェア解析については全くの初心者で、このエントリで私がマルウェア解析について指南することは基本的にありませんし、載せているリンクも質を保証するものではありません。ここでまとめているものは私がぱっと見で良さそうと思ったものであり、私自身に対するこれからの課題でもあります。
環境構築
マルウェア解析をするにあたって環境構築は重要な項目になります。間違っても（少なくとも趣味の範囲では）実機でマルウェアを動作させるのはいけませんし、仮想環境上でも適切な設定を行わなければなりません。この辺りの注意事項については暗黙の了解なのか詳しく書いてあるところはあまりなく、私がみた中ではこちらの書籍の環境構築の部分に詳しく書いてあります。
Practical Malware Analysis: The Hands-On Guide to Dissecting Malicious Software
- 作者: Michael Sikorski,Andrew Honig
- 出版社/メーカー: No Starch Press
- 発売日: 2012/02/01
- メディア: ペーパーバック
- 購入: 1人 クリック: 21回
- この商品を含むブログ (2件) を見る
アナライジング・マルウェア ―フリーツールを使った感染事案対処 (Art Of Reversing)
- 作者: 新井悠,岩村誠,川古谷裕平,青木一史,星澤裕二
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/12/20
- メディア: 単行本（ソフトカバー）
- 購入: 8人 クリック: 315回
- この商品を含むブログ (22件) を見る
マルウェア解析の環境は主にwindowsになると思います。そのほかのOSのマルウェアももちろん存在しますが、一般的なwindowsのシェアからか、マルウェアも主にwindows上で動作するものが多い印象です。これから始めるならwindowsの用意が必須になります。しかしwindowsは有料で安くはないので私はこちらのサービスを使いました。
developer.microsoft.com 前はmodern.IEと呼ばれていたものですが、名前だけ変わっています。windowsのバージョンも選べるので便利。
マルウェア解析では非常に多様なツールを使用します。
ツールなどの用意はこのツールで簡単にできてしまいます。簡単な手順で主要なツールを導入してくれます。インストール方法など詳細はこちらにも書いてありますが、インストールはgithubのREADMEに従ってやるのが良いと思います。動画でも紹介されていますが、この動画と同じようにできるかどうかは保証できません(実際私は失敗した)ので、実際にやるときには公式のサイトを参考にすると良いです。でも、ツールの紹介などをしてくれるので一度見ておくと良いと思います。
https://www.fireeye.com/blog/threat-research/2018/11/flare-vm-update.html
Fastest Malware Analysis Lab Setup With FREE VM and Tools
しかし、解析系のツールは非常に多く、似たようなものもいろいろあります。その中で選ぶのは本当に好みに左右されることもあり、FLAREVMではその全てを導入してくれるわけではありません。慣れてきたらいろいろ使ってみて自分の環境を揃えて行くと良いかもしれません。
PEフォーマット
windowsのマルウェアを解析する際、windowsの実行可能ファイルの形式であるPEフォーマットについての知識は必須です。日本語の資料だと、上記のアナライジングマルウェアや、以下のものが良いと思います。
マルウェア解析系の記事や資料には冒頭にPEの解説が入ることがよくありますので、これだけをずっと読むよりは色々見ていく方が良いと思います。 またこれはよく言われていることなのですが、PEフォーマットはかなり複雑なものになっていて、全てを暗記して理解している人は少ないらしいです。なので全体をざっと理解して、よく参照される部分（インポートテーブルなど）の繋がりを理解しておけば、良いと思います。
ちなみに、PEフォーマットの全体像を一枚にまとめたPDFがあります。
眺める程度に一度見ておくと面白いです。
解析
マルウェアを解析するには表層解析、静的解析、動的解析があると言われていますが、基本的に何をするにしてもアセンブリ言語の知識は必須だと思っています。また、私がフォレンジックツールなどを用いて解析するよりもアセンブリ言語を読んだりする方が好きなことから、リバースエンジニアリングの方をまとめていくことにしました。 まず、マルウェアのリバースエンジニアリングの入門にはこちらの書籍が良かったです。ソフトウェアの実行の仕組みからアセンブリ言語の解説、簡易デバッガの作成やシリアルコード抽出まで色々とやっているので結構楽しんで読めると思います。
- 作者: Digital Travesia管理人うさぴょん
- 出版社/メーカー: 秀和システム
- 発売日: 2018/09/14
- メディア: Kindle版
- この商品を含むブログを見る
また直接マルウェア解析と関係はないですが、著者のサイトも面白いです。
他にはこちらがかなり参考になると思います。上記の書籍よりもアンチデバッグや難読化についての記述が多く、C++やDLLの解析についても書かれています。
- 作者: 姜秉卓,金輝剛,金凡峻
- 出版社/メーカー: インプレス
- 発売日: 2013/09/20
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (5件) を見る
次に、マルウェア解析全般的に解説してくれているサイトです。
このサイトはかなり読みやすくて、絵やGIFも多用されていてわかりやすいと思います。
また、海外では動画でマルウェア解析関連の動画がよく上がっています。チャンネルをいくつか載せておきます。
マルウェア解析というよりはライブアンパッキングという感じですが面白いです。その他マルウェア解析系の様々な技術の紹介をしてくれたりします。
最後に、結構有名なものだとは思いますが、OPEN SECURITY TRANINGがあります。こちらはコンピュータセキュリティに関する様々な技術の資料や講義がフリーで公開されています。マルウェア解析だと以下のようなものが良いと思います。
IntroductionToReverseEngineering
資料も講義の動画も全部英語の上、ボリュームもすごいことになっているので全部すぐに理解するのは難しいとは思いますが、いろんなところからリンクを貼られているので、質はお墨付きではないかと思います。
また、OpenSecurityのトレーニングに載っているこちらの画像によると、マルウェア解析のスキルツリーはこのようになっているらしく、この通りに技術をつけていきたいですね。
解析は実際に手を動かして経験を積むのが一番なのですが、いきなりマルウェアを読み始めたりするのは億劫になる人もいると思うので、こういうCrackMeと呼ばれるようなトレーニングで色々触ってみると良いと思います。
あとは、CTFのbinaryやreversingといったカテゴリーの問題を解くのも良いと思います。
検体
マルウェアを解析しようと思っても肝心のマルウェアがなければ話になりません。ハニーポットを建てて自分で集めるのも良いですが、すでに公開されている検体をもらってくるのが最も簡単な方法です。こちらで色々公開されています。普通にマルウェアなので取り扱いには重々注意してください。
VirusTotalです。ファイルをアップロードしたら色々解析してくれるサービスですが、課金ユーザーになるとアップロードされたファイルをダウンロードできるようになります。 VirusTotal
こちらも同じようなサービスですが、無料でもアップロードされたファイルをダウンロードできます。
https://www.hybrid-analysis.com/
以下、マルウェアがまとめられているサイトなどです。 malshare.com
https://83.133.184.251/virensimulation.org/
If you are a Malware researcher/analyst and need access to samples you can visit my malware samples library at https://t.co/Xl0N51Rq66 (Without Tor Browser) or https://t.co/l8PIEZDM1d (With Tor Browser). I mainly collect APT variants among other malware types. #malware #infosec pic.twitter.com/JjNiclrLg8
— 0xffff0800 (@0xffff0800) 2018年12月2日
news
マルウェアなどの動向は絶えず変化し続けていくので、最新の情報を常に取得することが大切だと思います。プロの方々は人それぞれ情報網を持っていたり、選別したサイトなどを見てキャッチアップしていると思います。この辺りは僕も本当に知りたいところなのですが、個人的に良いなと思ったニュースサイトを上げていきます。
この辺りは有名ですし、日本語で書いてあって読みやすいし良いと思います。
英語ですが、マルウェア関連のニュースを多く扱っているサイトです。
redditのセキュリティ系のチャンネルです。
その他、自分はここを見ている、こうやって情報収拾しているというものあれば、コメントなどで教えていただけると嬉しいです！
おわりに
本来は全く別の技術的な記事を書くつもりだったのですが進捗が全然間に合わず、急遽別の候補であるこの記事を書きました。まともな文章も書かず、ムラだらけのリンク集みたいな記事になってしまい すみません。
はじめにでも書いたようにこれは私自身への課題という側面があるのですが、こういう記事を見てマルウェア解析に興味を持って、一緒に勉強してくれる人が出てきてくれたら嬉しいなという思いもあります。
来年の今頃にはもっと技術的に面白い記事が書けるように頑張ります。
明日は tmyk_kym さんの記事です。
パッカーを自作した -コードを書く-
前回，パッカーを作るための前知識を説明しました．今回からコードを書いて，作っていこうと思います．前回にも言いましたが，コードの内容は「アナライジング・マルウェア」という書籍を大いに参考にしていますが，こちらはWindowsように書かれており，今回はLinuxで書くことでかなり違ったものになりました．
ファイルの読み込み
まずは，パックする対象のファイルを読み込みます．
target_filename = argv[1]; packed_filename = argv[2]; fd = open(target_filename, O_RDONLY); target_bin = fdopen(fd, "rb"); fstat(fd, &stbuf); unsigned char target_bin_buffer[stbuf.st_size]; fread(target_bin_buffer, 1, sizeof(target_bin_buffer), target_bin); fclose(target_bin);
fopenで読み込んでも良いのですが，読み込むファイルのサイズなどを取得しなければいけないことから，openを使ってファイルディスクリプターを取得するところからやっています．
ファイルのサイズと同サイズの領域を用意し，そこに読み込んでいます．
各ヘッダの読み込み
ファイルを読み込んだら，次に各ヘッダの値を読み込んでいきます．
ehdr = (Elf32_Ehdr *)target_bin_buffer; shdr = (Elf32_Shdr *)(&target_bin_buffer[ehdr->e_shoff]); phdr = (Elf32_Phdr *)(&target_bin_buffer[ehdr->e_phoff]);
ehdr, shdr, phdrがそれぞれ，elf header, section header, program headerとなっています． コードは少し読みにくくなってしまいましたが，先頭にあるelf headerを読み込んでから，オフセットを指定して，他のヘッダのポインタを読み込むようにしています．
コードセクションの検索
今回作るパッカーでは，エントリポイントを含むコードセクションのみエンコードを行います．UPXなどのパッカーでは，全てのセクションを圧縮することができるらしいのですが，何も考えずに全てのセクションをエンコードするものを作ってしまうと，おそらく，プログラム実行に必要な情報(シンボル情報や，plt,gotなど関数のリンク作業)まで失われてしまってデコードしても正しく実行できなくなってしまいます． ということで，エントリポイントを含むセクションの検索を行います．セクションの検索を行う関数は次のようになります．
Elf32_Shdr *search_oep_include_section_header(
Elf32_Shdr *shdr, unsigned int oep, unsigned int shnum){
Elf32_Shdr *oep_shdr = NULL;
unsigned int section_addr;
unsigned int section_size;
printf("search oep include section header\n");
for(int i=0; i < shnum; i++, shdr++){
section_addr = shdr->sh_addr;
section_size = shdr->sh_size;
//printf("addr:0x%08X size:0x%08X oep:0x%08x\n", shdr->p_vaddr, shdr->p_memsz, oep);
if(section_addr <= oep &&
oep <= section_addr + section_size){
printf("oep section found!\n");
oep_shdr = shdr;
break;
}
}
return oep_shdr;
}
ヘッダーテーブルの中を先頭から一つずつ見ていって，アドレスがエントリポイントを含んでいるかどうかを調べているだけです．見つけたらそのヘッダを返すということをしています．
見つけたら，そのセクションから必要な情報を取り出します．
//oep include section search oep_shdr = search_oep_include_section_header(shdr, ehdr->e_entry, ehdr->e_shnum); //get oep include section values section_vaddr = oep_shdr->sh_addr; section_vsize = oep_shdr->sh_size; section_raddr = oep_shdr->sh_offset;
また，直接エンコードと関係はないのですが，後半で説明するとある事情により，エントリポイントを含むセグメントも検索しないといけません．なので，同じ要領で検索します．
Elf32_Phdr *search_oep_include_segment_header(
Elf32_Phdr *phdr, unsigned int oep, unsigned int phnum){
Elf32_Phdr *oep_phdr = NULL;
unsigned int section_vaddr;
unsigned int section_vsize;
printf("search oep include section header\n");
for(int i=0; i < phnum; i++, phdr++){
section_vaddr = phdr->p_vaddr;
section_vsize = phdr->p_memsz;
printf("addr:0x%08X size:0x%08X oep:0x%08x\n", section_vaddr, section_vsize, oep);
if(section_vaddr <= oep &&
oep <= section_vaddr + section_vsize){
printf("oep section found!\n");
oep_phdr = phdr;
break;
}
}
return oep_phdr;
}
エンコード
次に，該当セクションをエンコードしていきます．エンコードする関数が次になります．
void xor_encoder(unsigned char *start, unsigned int size, unsigned char encoder) { unsigned int cnt=0; printf("Start Xor Encode by '0x%X'\n", encoder); for(cnt=0; cnt<size; cnt++){ start[cnt] ^= encoder; } printf("Encode Done\n"); }
開始アドレスとサイズ，エンコードする値を指定して，開始アドレスから１バイトずつ取ってきて順次エンコードしています． 使うときはこんな感じ
encoder = 0xFF; xor_encoder((unsigned char *)(oep_shdr->sh_offset + target_bin_buffer), oep_shdr->sh_size, encoder);
展開コードの生成
エンコードしたコードをデコードするルーチンを生成して追加します．生成する関数が次になります．
unsigned char decode_stub[] = { 0x60, // pushad 0xBE,0xFF,0xFF,0xFF,0xFF, // mov esi, decode_start 0xB9,0xFF,0xFF,0xFF,0xFF, // mov ecx, decode_size 0xB0,0xFF, // mov al, decoder 0x30,0x06, // xor byte ptr [esi], al (LOOP) 0x46, // inc esi 0x49, // dec ecx 0x75,0xFA, // jnz LOOP 0x61, // popad 0xE9,0xFF,0xFF,0xFF,0xFF // jmp OEP }; unsigned int decode_start_offset = 2; unsigned int decode_size_offset = 7; unsigned int decoder_offset = 12; unsigned int jmp_oep_addr_offset = 21; void create_decode_stub(unsigned int code_vaddr, unsigned int code_vsize, unsigned char decoder, unsigned int oep) { int cnt=0; int jmp_len_to_oep=0; jmp_len_to_oep = oep - (code_vaddr + code_vsize + sizeof(decode_stub)); printf("start : 0x%08X\n", code_vaddr); printf("size : 0x%08X\n", code_vsize); printf("decoder : 0x%02X\n", decoder); printf("oep : 0x%08X\n", oep); printf("jmp len : 0x%08X\n", jmp_len_to_oep); memcpy(&decode_stub[decode_start_offset], &code_vaddr, sizeof(DWORD)); memcpy(&decode_stub[decode_size_offset], &code_vsize, sizeof(DWORD)); memcpy(&decode_stub[decoder_offset], &decoder, sizeof(unsigned char)); memcpy(&decode_stub[jmp_oep_addr_offset], &jmp_len_to_oep, sizeof(DWORD)); return; }
decode_stubという展開コードのテンプレートのようなものを書いて，具体的な値をcreate_decode_stub関数で与えています．decode_stubで0xFFとなっているところは大体何かが代入されるところです． decode_stubの内容はコメントにつけたアセンブリコードのとおりなのですが，やっていることはxorでデコードしているだけです． このコードは参考書籍に載っているものをほんの少しだけLinux用に改造して転用させていただきました．ハフマン符号などでエンコードした場合，ハフマン符号のデコードも機械語で記述しなければならず，それが私にはできなかったため断念しました．
なにはともあれとりあえず作ったのでこんな感じで生成して，生成したコードを読み込んだファイルの後ろにくっつけます．
create_decode_stub(section_vaddr, section_vsize, encoder, ehdr->e_entry); memcpy((unsigned char *)(section_raddr + section_vsize + target_bin_buffer), decode_stub, sizeof(decode_stub));
情報の書き換え
当初読み込んだファイルから色々と変更しているため，元々の情報を書き換える必要があります．
ehdr->e_entry = section_vaddr + section_vsize; oep_phdr->p_flags |= PF_W;
一行目は，展開コードをまず実行してもらいたいので，エントリポイントを変更しています． 二行目は，展開コード内で，エンコードされているコードを書き換える必要があるため，本来持っていない書き込み権限を付与しています． 今まで，領域を操作するときはセクション単位で行ってきていたのですが，この権限の部分だけセグメントの単位で行わないとなぜかうまくいかなくて悩みました．そのため．エントリポイントを含むセグメントも同時に検索していました．
書き出し
最後は，出来上がったコードをファイルに書き出して，パッキング終了となります．
packed_bin = fopen(packed_filename, "wb"); fwrite(target_bin_buffer, sizeof(target_bin_buffer), 1, packed_bin);
実行
さてここまでで，一連のパッカーの処理を作り終えたので，実行してみます． まず，適当なプログラムを書き，testという名前で実行ファイルを作ります．
#include <stdio.h> int main(){ printf("Hello, World!\n"); return 0; }
パッキングします．
$ ./a.out test packed search oep include section header oep section found! search oep include section header addr:0x08048034 size:0x00000120 oep:0x08048310 addr:0x08048154 size:0x00000013 oep:0x08048310 addr:0x08048000 size:0x000005C8 oep:0x08048310 oep section found! Start Xor Encode by '0xFF' Encode Done start : 0x08048310 size : 0x00000192 decoder : 0xFF oep : 0x08048310 jmp len : 0xFFFFFE55
実行します．
$ ./packed Hello, World! Segmentation fault (core dumped)
なんかいらんもんがくっついてしまっとりますが，とりあえず出来たということにしてくださいm(＿)m
検証
実際にパッキングできているのかどうか少し調べます． objdumpで逆アセンブルすると，
0804840b <main>: 804840b: 72 b3 jb 80483c0 <__do_global_dtors_aux> 804840d: db fb (bad) 804840f: 7c 1b jl 804842c <main+0x21> 8048411: 0f 00 8e 03 aa 76 1a str WORD PTR [esi+0x1a76aa03] 8048418: ae scas al,BYTE PTR es:[edi] 8048419: 7c 13 jl 804842e <main+0x23> 804841b: fb sti 804841c: 7c 13 jl 8048431 <main+0x26> 804841e: f3 97 repz xchg edi,eax 8048420: 3f aas 8048421: 7b fb jnp 804841e <main+0x13> 8048423: f7 17 not DWORD PTR [edi] 8048425: 48 dec eax 8048426: 01 00 add DWORD PTR [eax],eax 8048428: 00 7c 3b ef add BYTE PTR [ebx+edi*1-0x11],bh 804842c: 47 inc edi 804842d: ff (bad) 804842e: ff (bad) 804842f: ff (bad) 8048430: ff 74 b2 03 push DWORD PTR [edx+esi*4+0x3] 8048434: 36 72 9e ss jb 80483d5 <__do_global_dtors_aux+0x15> 8048437: 03 3c 99 add edi,DWORD PTR [ecx+ebx*4] 804843a: 6f outs dx,DWORD PTR ds:[esi] 804843b: 99 cdq 804843c: 6f outs dx,DWORD PTR ds:[esi] 804843d: 99 cdq 804843e: 6f outs dx,DWORD PTR ds:[esi] 804843f: 6f outs dx,DWORD PTR ds:[esi]
意味のわからないコードになっていることがわかると思います．
ただ，エンコードしているのはテキストセグメントだけなので，シンボル情報などは全てそのままになっているので，gdbでmainまで実行させると
$ b main Breakpoint 1 at 0x804840b $ run .... $ disas main Dump of assembler code for function main: 0x0804840b <+0>: jb 0x8048459 <__libc_csu_init+25> 0x0804840d <+2>: and al,0x4 0x0804840f <+4>: and esp,0xfffffff0 => 0x08048412 <+7>: push DWORD PTR [ecx-0x4] 0x08048415 <+10>: push ebp 0x08048416 <+11>: mov ebp,esp 0x08048418 <+13>: push ecx 0x08048419 <+14>: sub esp,0x4 0x0804841c <+17>: sub esp,0xc 0x0804841f <+20>: push 0x80484c0 0x08048424 <+25>: call 0x80482e0 <puts@plt> 0x08048429 <+30>: add esp,0x10 0x0804842c <+33>: mov eax,0x0 0x08048431 <+38>: mov ecx,DWORD PTR [ebp-0x4] 0x08048434 <+41>: leave 0x08048435 <+42>: lea esp,[ecx-0x4] 0x08048438 <+45>: ret End of assembler dump.
よく見る形のコードになっていますね．
ここに問題がないことがわかるので，あのSegmentation fault (core dumped)はretの後に起こってるんでしょうね．おそらく，単純に読み込んだバッファの後ろにそのまま展開コードをくっつけたのが悪かったんだと思うのですが，直すのはまた今度にします．
まとめ
今回は，前回解説した知識をもとに実際にパッカーのコードを書きました．書きましたと言っても，書籍のコードを書き換えただけなのですが，これが意外と大変だった．また，改めて見直すとめちゃくちゃ汚いコードを書いていることに気づきました．もうちょっと直したり改造して，また投稿したいと思います．
参考文献
アナライジング・マルウェア ―フリーツールを使った感染事案対処 (Art Of Reversing)
- 作者: 新井悠,岩村誠,川古谷裕平,青木一史,星澤裕二
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/12/20
- メディア: 単行本（ソフトカバー）
- 購入: 8人 クリック: 315回
- この商品を含むブログ (22件) を見る
パッカーを自作した -elfの勉強-
今まで普通に圧縮のアルゴリズムを学んでたのですが，今回少し趣向を変えて，パッカーというものを作りました．パッカーやその周辺の技術について詳しく解説されている文献が非常に少なかったため，「アナライジング・マルウェア」という書籍を大いに参考にさせていただいてます．丸写しなどは全く行なっておりません．また，この書籍にて解説されているパッカーのコードはwindowsで動くように書かれているのですが，勉強のためLinux(32bit)で動くよう書き換えていきます．
パッカーとは
パッカーは実行ファイル圧縮と呼ばれるもので，wikipediaには
実行ファイル圧縮（英: Executable compression）とは、実行ファイルを何らかの手段で圧縮し、それをデータとして伸張（解凍）用コードと共に1つの実行ファイルとすること。
圧縮された実行ファイルを実行する場合には、まず伸張（解凍）して本来の実行コードを取り出し、それを自動的に実行する。圧縮していないオリジナルの実行ファイルを実行したのと同じ効果が得られるので、一般ユーザーには区別がつかない。 "wikipedia 実行ファイル圧縮"
とあります．実行形式のファイルをパッカーで圧縮すると，圧縮したまま実行できるというものです．基本的には実行時にメモリに展開されるのですが，ハードディスクなどに小さいまま保存できるという利点があります．有名なオープンソースのパッカーにはUPXなどがあります．
本来，データ量を削減するために開発されたツールであると思うのですが，現在パッカーというと主にマルウェアを圧縮するために用いられるものとなっています．圧縮されるということは，保存されているコードが読める状態になっていないため，難読化する目的で利用されています．
パッカーの仕組み
圧縮されたコードと一緒にそれを展開するコードが埋め込荒れており，実行時にまず展開コードが実行されます．展開コードが実行されると，圧縮されたコードが展開され，展開先に実行が移ります．
パッカーの作り方
今回作るパッカーの作り方の手順を説明します．パッカーにも様々な種類がありますし，私自身初心者であるため，今回のものが全てではないことをご容赦ください．
xorエンコードは参考書籍で解説されていたコードがそうなっていたので，本当はせっかく学んだハフマン符号とかで実際に圧縮するところまでやりたかったのですが，力が及ばずできませんでした．なので，厳密にパッカーではないのですが，この辺をこんな感じで改造したら圧縮できそうだなーみたいな感じで読んでください．
実行ファイル
ここから実際に作っていきたいのですが，とにかく実行ファイルがどういう構造をしているかわからないと何もできないため，実行ファイルの解説をしたいと思います．
Linuxの実行ファイルは現在では，COFFというものを少し改造したELFというフォーマットで構築されています．ELFの構造を図にすると以下のようになります．
elf headerというヘッダが先頭に配置されており，program header tableがその次に配置され，コード領域が続いていき，一番下に，section header tableが配置される，という構造になっています．配置されている順序はこうなっていますが，実際にアクセスする場合は各ヘッダに保存されている値を用いてアクセスします．
program header table, section header tabeleは文字通り，各ヘッダのテーブルとなっており，ここに各領域の数だけヘッダが並べられています．
program headerの指す領域はセグメントと呼ばれ，section headerの指す領域はセクションと呼ばれています．
次に各ヘッダの解説をします．今回主に使うものだけにコメントをつけて軽く説明しています．
elf headerの中身は次のようになっています．
#define EI_NIDENT 16 typedef struct { unsigned char e_ident[EI_NIDENT]; //マジックナンバーなど uint16_t e_type; uint16_t e_machine; uint32_t e_version; Elf32_Addr e_entry; //エントリポイントのアドレス Elf32_Off e_phoff; //program headerのアドレスのオフセット Elf32_Off e_shoff; //section headerのアドレスのオフセット uint32_t e_flags; uint16_t e_ehsize; //elf header(このヘッダ)のサイズ uint16_t e_phentsize; //一つのprogram headerのサイズ uint16_t e_phnum; //program header の数 uint16_t e_shentsize; //一つのsection headerのサイズ uint16_t e_shnum; //section headerの数 uint16_t e_shstrndx; } Elf32_Ehdr;
このヘッダでは，プログラム全体の管理をしている感じですね．おそらく一番よく見ることになるのがe_entryです．プログラムが実行される際にどのアドレスから始めるのかが記録されています．
次にprogram headerです
typedef struct { uint32_t p_type; Elf32_Off p_offset; //セグメントのアドレスのオフセット Elf32_Addr p_vaddr; //セグメントの仮想アドレス Elf32_Addr p_paddr; //セグメントの物理アドレス uint32_t p_filesz; //セグメントのファイルイメージのサイズ uint32_t p_memsz; //セグメントのメモリ上のサイズ uint32_t p_flags; //セグメントの属性 uint32_t p_align; } Elf32_Phdr;
program headerは各セグメントに対する情報が保存されています． セグメントの属性は次のようなものがあります． - PF_X 実行可能セグメント - PF_R 読み取り可能セグメント - PF_W 書き込み可能セグメント
最後にsection headerです
typedef struct { uint32_t sh_name; uint32_t sh_type; uint32_t sh_flags; Elf32_Addr sh_addr; //セクションのアドレス Elf32_Off sh_offset; //セクションのアドレスのオフセット uint32_t sh_size; //セクションのサイズ uint32_t sh_link; uint32_t sh_info; uint32_t sh_addralign; uint32_t sh_entsize; } Elf32_Shdr;
このヘッダではアドレスとオフセットが重要です．
だいぶ雑ではありますが，このようにelfは出来上がっています．
まとめ
パッカーの自作というタイトルですが，いったん色々解説したタイミングで今回は終了します．私がパッカーを作った際に使用した部分のみの解説になってしまったので，詳しくは参考文献にあげた記事などを参考にしてもらいたいです．非常にわかりやすいです． また，section headerとprogram headerの違いが正直まだよくわかっていません．詳しくは次回以降に書きますが，よくわかっていないせいで，非常に悩んだ部分もありました．詳しい人がいたら教えてください．．． 次回，実際にコードを書いていきます．
参考文献
アナライジング・マルウェア ―フリーツールを使った感染事案対処 (Art Of Reversing)
- 作者: 新井悠,岩村誠,川古谷裕平,青木一史,星澤裕二
- 出版社/メーカー: オライリージャパン
- 発売日: 2010/12/20
- メディア: 単行本（ソフトカバー）
- 購入: 8人 クリック: 315回
- この商品を含むブログ (22件) を見る
Huffman符号
ハフマン符号とは，1952年にデビッド・ハフマンによって考案された符号化手法です．対象のデータの出現する値の偏りによって割り当てるビット数を変更することで冗長性を排除する手法です．ハフマン木と呼ばれる木構造のデータを構築することでエンコードし，根から葉へ辿ることでデコードできる仕組みになっています．
非常に古い手法ですが，今でもバリバリ現役で使用されている手法です．
ハフマン木
ハフマン符号化において重要かつ，難しいのは木を構築する部分です．これを説明します． ハフマン木を構築する流れは以下のようになっています．
対象データから，各値の出現頻度を求め，出現テーブルを作る ↓ 出現テーブルの中から最も出現頻度の低い２つの値を取り出し，その二つをまとめて一つの木にする． ↓ 二つの合計値を新たに対象データの出現テーブルに加える ↓ 出現テーブルのデータが全て取り出されるまで繰り返す
というようになっています．
例えばテキストデータを対象に A:8 B:2 C:7 というような出現テーブルが作れた場合，まず出現頻度の最も低いB,Cが取り出されて木になります．
二つを合計したデータとして一時的にαという記号を使用しています．
これにより，テーブルは次のように更新されます． A:8 α:9
同じように取り出して木を作ると
このようになり，ハフマン木の完成です．
デコードは，rootからノードをたどっていくのですが，例えば，右のノードに１，左のノードに０を追加していくように設定すると(これはどちらでも良いがエンコードとデコードで合わせる必要がある)
このように割り当てられて，各値は次のようにエンコードされたことがわかります．
A:1 B:00 C:01
三文字しかないデータで例を表してしまったため，いまいち効果を実感しにくいですが，一番多く出ている値Aに一番小さいビットが当てられています．
ハフマン符号の理論的な部分はこのように非常に簡単なものになっています．
実装
ハフマン符号はの実装方法には色々とあるのですが，今回は理論通りに実際に木構造を生成してエンコードする方法をやっていこうと思います． まずは，各値を表すノードの宣言を行います．pythonにおいて構造体を表すには，ディクショナリでよいみたいなことを聞いたのですが，色々都合がいいのでメソッドを持たないオブジェクトを作ることにします．
class Node: def __init__(self, code, count=0, left=None, right=None, parent=None): self.key = count self.code = code self.count = count self.left = left self.right = right self.parent = parent self.bitcode = ''
ハフマン木の生成は一つのオブジェクトにします．
class HuffTree: def __init__(self): self.histgram = {} self.leaf = {} self.root = None def makeHistgram(self, f): data = f.read() for c in data: if c not in self.histgram.keys(): self.histgram[c] = 1 else: self.histgram[c] += 1 def makeTree(self): pq = nodepq.PriorityQueue() for k in self.histgram.keys(): pq.push(Node(k, self.histgram[k])) while True: x = pq.pop() if x.left == None and x.right == None: self.leaf[x.code] = x if pq.empty(): break y = pq.pop() if y.left == None and y.right == None: self.leaf[y.code] = y node = Node(None, x.count+y.count, x, y, None) x.parent = y.parent = node pq.push(node) self.root = x def encode(self, node, bitcode=''): if node.code != None: node.bitcode = bitcode else: self.encode(node=node.left, bitcode=bitcode+'0') self.encode(node=node.right, bitcode=bitcode+'1') def decode(self, node, bitcode): if bitcode == '' and node.code == None: return -1 elif bitcode == '' and node.code != None: return node.code else: if bitcode[0] == '1': return self.decode(node.right, bitcode[1:]) elif bitcode[0] == '0': return self.decode(node.left, bitcode[1:])
makeHistgramメソッドはファイルのデータを読み込んで，出現したデータがテーブルの中に存在していなかったら追加し，存在していたらデータの数を増やしていく処理をしています．
makeTreeメソッドが一番キモになっているメソッドで，ハフマン木を実際に構築しています．まずプライオリティーキューを用意します．これは具体的なアルゴリズムはここでは説明しませんが，キューに追加したデータから，一番小さいものを取り出すことができます．今回の場合，追加するデータは複数のデータを持つ構造体であるため，出現回数をキーとしてキューの中でソートするように少し改造しています．あとは単純で，取り出して枝を設定して，再度キューに追加する，ということをデータが最後の一つになるまで繰り返しています．
encode,decodeは再帰処理を行って，上記理論で説明したようなことをそのまま行っています．
tree = HuffTree()
with open(<符号化の対象ファイル>, 'rb') as f:
tree.makeHistgram(f)
tree.makeTree()
tree.encode(tree.root)
print(tree.histgram)
for k in tree.leaf:
print('{} -> {}'.format(chr(k), tree.leaf[k].bitcode))
こんな感じでmainをかくと符号化されたコードが出てきます． 対象ファイルデータ AAAAAAAAABBBBBBCCCCCCCCAAAAAAABCBC AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABCBABC
-> 010 B -> 011 C -> 00 A -> 1
一つ目は改行コードです．いい感じに符号化されていると思います．
まとめ
ハフマン符号は理論こそ単純なもののあまりコードを書くことに慣れていなかった僕は，実装方法に色々悩みました．こういたアルゴリズムはプログラミングのいい練習になるのでとても良かったです．
参考文献
- 作者: 昌達慶仁
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2010/10/26
- メディア: 単行本
- 購入: 1人 クリック: 171回
- この商品を含むブログ (3件) を見る
RunLength圧縮を学ぶ -PackBits-
RunLength -PackBits-
前回，圧縮技術の第一歩としてランレングス圧縮を学んだのですが，そのままでは使い勝手の悪いものなので今回少し応用を学びます．
ランレングスのデメリットとして，データの内容によっては圧縮どころか膨張してしまう可能性があることがありました．これは，データのラン長が１の時にも1という符号を記録してしまうために起こるものでした．解決策は様々なものが提案されていて，簡単なものですと，ラン長が３以上の時にだけ記録するように組んだりするなどがあります．その中でも実際にも使用されている有名なものを今回やっていこうと思います．
PackBits
PackBitsとは，連続したデータと，それ以外の二つに分けて，それぞれでラン長を記録していく方法です．例えば
- 元データ： AAAAAAABCBCACCCCC
- PackBtis : | AAAAAAA | BCBCA | CCCCC |
というように分けて，それぞれのブロックでラン長を記録していくことになります．ラン長の記録の仕方に少し工夫があります．全てのブロックに自然数値で記録してしまうと，どれが連続したデータとそれ以外なのかの判断ができなくなってしまいます．そこで，連続したデータブロックには正の整数，それ以外のブロックには負の整数で記録するようにすれば判断ができます．
- 圧縮：7A-5BCBCA5C
これで，ばらけているデータが入ってきても，無駄にラン長を記録することなく，連続したデータを圧縮できるというわけです．
しかし，記録する乱調に符号付整数を使用しているために，一度にまとめて記録できる数が半分に減ります．
Switched RunLength Encoding
一度にまとめて記録できる数を元に戻す方法として，Switched RunLength Encodingというものがあります．PackBitsと同じようにデータをまとめるのですが，ラン長を記録する際に，正負で判断するのではなく，まとまったデータと，それ以外のデータが交互にくるものと仮定して記録していく方法です．例えば，まとまったデータが最初にくると決めておいて符号化すると，
- 7A5BCBCA5C
というように記録でき，デコード側でもまとまったデータが最初にくるというように合わせておくことで，復号できます．問題は，上記の例ではなかったのですが，違う記号が連続でまとまった時の対処です．
- AAAABBBBBCDCB
というようなデータがあると，まとまったデータが交互ではないので記録できないように思えてしまうのですが，交互にならなかった場合は間に0を入れて，無理やり交互にします．
- 4A05B4CDCB
少し処理が複雑になるのですが，問題なく復号できます．
また，インターネットでSwitched RunLength Encodingについて調べていると，PackBitsとは別物として扱われているのですが，私の参考にしている文献では，PackBitsとはデータをまとまったものとばらけているものの二つに区別することであるとのことなので，PackBitsのうちにこの符号化方法が含まれているようになっています．
実装
Pythonを使って実装していきます．バイナリデータを扱うためにstructモジュールをインポートしています． getPackbitsという関数でデータを分ける作業をして，そのデータを使ってそれぞれエンコードしています．
PackBits get
def getPacBits(data, processPtr): run = 0 code = data[processPtr] processPtr += 1 run += 1 if code == data[processPtr]: en_mode = 0 while processPtr < len(data) and code == data[processPtr] and run < RUN_LIMIT: code = data[processPtr] processPtr += 1 run += 1 else: en_mode = 1 while processPtr < len(data) and code != data[processPtr] and run < RUN_LIMIT: code = data[processPtr] processPtr += 1 run += 1 if processPtr != len(data): processPtr -= 1 run -= 1 return (run, processPtr, en_mode)
PackBits encode
def encode_PackBits(data): encode_data = b'' processPtr = 0 while processPtr < len(data) - 1: codePtr = processPtr run, processPtr, mode = getPacBits(data, processPtr) if mode: encode_data += pack('b', -run) + pack('>'+str(run)+'s',data[codePtr:processPtr]) else: encode_data += pack('b', run) + pack('B', data[codePtr]) return encode_data
PackBits decode
def decode_PackBits(data): decode_data = b'' processPtr = 0 while processPtr < len(data) - 1: run = unpack_from('b', data, processPtr)[0] processPtr += 1 if run < 0: run = abs(run) decode_data += pack('>' + str(run) + 's', data[processPtr:processPtr+run]) processPtr += run else: decode_data += pack('B', data[processPtr]) * run processPtr += 1 return decode_data
Switched RunLengthEncoding encode
def encode_srle(data): encode_data = b'' processPtr = 0 mode = 0 while processPtr < len(data) - 1: basePtr = processPtr run, processPtr, en_mode = getPacBits(data,processPtr) if mode == 0: mode = 1 if en_mode == 1: encode_data += pack('B', 0) processPtr = basePtr continue encode_data += pack('B', run) + pack('B', data[basePtr]) else: mode = 0 if en_mode == 0: encode_data += pack('B', 0) processPtr = basePtr continue encode_data += pack('B', run) + pack('>'+str(run)+'s',data[basePtr:processPtr]) return encode_data
Switched RunLengthEncoding decode
def decode_srle(data): decode_data = b'' processPtr = 0 mode = 0 while processPtr < len(data) - 1: run = unpack_from('B', data, processPtr)[0] processPtr += 1 if run == 0: mode ^= 1 continue if mode == 1: decode_data += pack('>' + str(run) + 's', data[processPtr:processPtr+run]) processPtr += run mode = 0 else: decode_data += pack('B', data[processPtr]) * run processPtr += 1 mode = 1 return decode_data
まとめ
今回でランレングスについては一通り実装した気がします．基礎なので丁寧にやりましたが，正直ランレングスはアルゴリズム的にも実装的にもあまり面白いものではありませんし，用途も微妙な感じです．
ということで，次からはいよいよハフマン符号についてやっていきたいと思います．
参考文献
- 作者: 昌達慶仁
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2010/10/26
- メディア: 単行本
- 購入: 1人 クリック: 171回
- この商品を含むブログ (3件) を見る
RunLength圧縮を学ぶ
最近圧縮技術について学んでいるので，学んだことを随時ブログに書いていこうと思っています． 初回記事ですが早速，今回はランレングス圧縮について学んでいきます．
ランレングス圧縮とは
ランレングス圧縮を大雑把に説明すると，連続した同じデータをひとまとめにする圧縮技術のことです．例えば
AAAAABBBBBBCCCCC
というようなデータ列があると，Aが5個，Bが6個，Cが5個というように数えていくことがあると思いますが，これをそのまま
A5B6C5
と符号化して情報量を圧縮する方式です．ここで，データがいくつ並んでいるかを表す数値をラン長と呼びます．
メリット
ランレングス圧縮のメリットとしては以下のようなものが挙げられます．
- 処理が単純
- 圧縮するデータが２値など，少ないデータ種類で構成されている場合圧縮率が良い
上記で説明したように連続したデータをまとめるだけの処理なので簡単に実装でき，扱いやすいです．また，連続すればするほど一気に圧縮できるので，例えば黒と白のみで構成された画像を圧縮する際などはデータが連続する確率が高いので圧縮率が良くなります．
デメリット
単純であるが故にデメリットもあります．
- データの並びによってはデータが膨張する場合がある．
これは致命的なデメリットです．データをまとめて記述するとは言えラン長というデータを追加するため，例えば，
ABCABCABC
というデータの場合，
A1B1C1A1B1C1A1B1C1
というようにわざわざ与えなくてもいいようなところまでラン長を追加してしまって，データが２倍になります．が，これについては後述するランレングスの応用でなんとかなったりします．
ランレングスの実装
解説を踏まえて実装していきます．使用言語はPythonです．
def getRunLength(data, processPtr, code): run = 0 while processPtr < len(data) and code == data[processPtr] and run < 0xff : processPtr += 1 run += 1 return (run,processPtr)
受け取ったデータの処理開始点(processPtr)から続くラン長を取得します．そして，次に処理すべき点を返すようにします．ラン長は1バイトに納めたいので256バイト以上同じデータが続くようであればそこで終了し，次につなげます．
これを用いてエンコードします．
from struct import pack, unpack_from def encode_RLE(data): encode_data = b'' processPtr = 0 while processPtr < len(data) - 1: code = data[processPtr] run,processPtr = getRunLength(data, processPtr, code ) encode_data += pack('B',code) + pack('B',run) return encode_data
バイナリデータを扱うので，structモジュールをインポートしています．
データの最後までループを回し，ラン長を取得するたびにデータ値 + ラン長の形式で書き込んでいきます．特に複雑な部分はありません．
デコードはその逆をそのままやる感じです．
def decode_RLE(data): decode_data = b'' it = iter(data) for code, run in zip(it, it): decode_data += pack('B',code) * run return decode_data
エンコードされたデータを受け取り，イテレータを作成して，zipという関数を用いて二つずつ取り出すようにしています．このイテレータを扱うのがスクリプト言語っぽくていいですね．もっと使いこなしていきたいです．
ランレングス圧縮の応用
上でも述べたように，このままだとデータにばらつきがある場合処理後のデータが膨張してしまう可能性があります．これについて，ラン長が１の場合にはラン長を記録しないといったような応用方法が考案されています．名前がついているものであればPackBitsという方法があったりします．これについては次回勉強していきたいと思います．
まとめ
圧縮入門ということで基本的なランレングス圧縮を学びました．このランレングス，非常に単純なものなんですが画像分野では今でもちゃんと使われているらしいです．
初回記事なので稚拙な部分もあったりしたと思いますが，これからもこのように理論を学んで実装するという形式で進めていこうと思います．
参考文献
- 作者: 昌達慶仁
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2010/10/26
- メディア: 単行本
- 購入: 1人 クリック: 171回
- この商品を含むブログ (3件) を見る
