譚 森， 郭 捷

（上海交通大學(xué) 電子信息與電氣工程學(xué)院， 上海 200240）

基于日志分析的 MySQL 數(shù)據(jù)庫(kù)取證算法*

譚 森， 郭 捷

（上海交通大學(xué) 電子信息與電氣工程學(xué)院， 上海 200240）

MySQL 數(shù)據(jù)庫(kù)的使用越來(lái)越廣泛，MySQL 數(shù)據(jù)庫(kù)取證的問(wèn)題也變得越來(lái)越重要。日志是數(shù)據(jù)庫(kù)取證最重要的信息依據(jù)，MySQL 二進(jìn)制日志中記錄了用戶(hù)對(duì)數(shù)據(jù)庫(kù)數(shù)據(jù)所有的更改操作。 本文提出分析 MySQL 二進(jìn)制日志結(jié)構(gòu)，使用 KMP 算法對(duì) MySQL 二進(jìn)制日志進(jìn)行關(guān)鍵字匹配，檢索出我們所需要的信息，對(duì) MySQL 數(shù)據(jù)庫(kù)進(jìn)行取證的算法。 大量實(shí)驗(yàn)結(jié)果驗(yàn)證了本算法的有效性。

MySQL;二進(jìn)制日志;信息檢索;KMP 算法;數(shù)據(jù)庫(kù)取證

0 引言

MySQL 已成為世界上最流行和最成功的開(kāi)源數(shù)據(jù)庫(kù)系統(tǒng) ，MySQL 數(shù)據(jù)庫(kù)的取證問(wèn)題也變的越來(lái)越重要。Peter Fruhwirt，Markus Huber，等人曾提出 InnoDB 數(shù)據(jù)庫(kù)取 證[1］， 后來(lái)Peter Fruhwirt， Peter Kieseberg 等人提出通過(guò)分析 InnoDB 的redo log 更具體的取證方法[2］，但是這僅僅是針對(duì) InnoDB 的取證，如果 MySQL 數(shù)據(jù)庫(kù)使用其他數(shù)據(jù)庫(kù)引擎則難以取證了。每一種數(shù)據(jù)庫(kù)都會(huì)有自帶的工具或者功能幫助數(shù)據(jù)庫(kù)取證[3］，觸發(fā)器也可以用來(lái)幫助數(shù)據(jù)庫(kù)取證[4］。日志 是 數(shù) 據(jù) 庫(kù)取證最重要的依據(jù)，MySQL 數(shù)據(jù)庫(kù)的二進(jìn)制日志中記錄了用戶(hù)對(duì) MySQL 數(shù)據(jù)庫(kù)中數(shù)據(jù)的所有更改操作。 但是 MySQL 自身攜帶的 mysqlbinlog 工具[5-6］的功能很少也不完備，只有將二進(jìn)制日志轉(zhuǎn)換成文本文件和按時(shí)間段查看二進(jìn)制日志內(nèi)容等十分簡(jiǎn)單的功能。通過(guò)這些功能查詢(xún)出來(lái)的信息有很多對(duì)于用戶(hù)而言是不必要的信息，因此該工具不能提供很多對(duì)于數(shù)據(jù)庫(kù)取證有幫助的信息。如果需要關(guān)于某一個(gè)關(guān)鍵字的信息就只能通過(guò)用戶(hù)人工的去篩選 mysqlbinlog 查詢(xún)出來(lái)的信息，這樣會(huì)顯得十分繁瑣，而且會(huì)很容易遺漏信息。

為了快速，有效的檢索出 MySQL日志中我們想要的信息，對(duì)數(shù)據(jù)庫(kù)進(jìn)行取證。 本文提出通過(guò)分析 MySQL 二進(jìn)制日志的結(jié)構(gòu)，使用 KMP 算法檢索關(guān)鍵字，然后提取關(guān)鍵信息從而對(duì) MySQL數(shù)據(jù)庫(kù)進(jìn)行取證的方法。

1 分析 MySQL 二進(jìn)制日志結(jié)構(gòu)

目前對(duì) MySQL 二進(jìn)制日志結(jié)構(gòu)的分析幾乎沒(méi)有，如果要了解 MySQL 二進(jìn)制日志的結(jié)構(gòu)，我們就只能通過(guò)分析 MySQL 的源碼。 通過(guò)閱讀 MySQL 的部分源碼分析出了 MySQL 二進(jìn)制的結(jié)構(gòu)，下面進(jìn)行詳細(xì)敘述。

1.1 二進(jìn)制日志的總體結(jié)構(gòu)

每個(gè)二進(jìn)制文件的的開(kāi)始都是 4 個(gè)字節(jié)：fe 62 69 6e，該四個(gè)字節(jié)成為“ 魔數(shù)”;其中后面三個(gè)字節(jié) 就是 bin 的 ascii 碼。 然后接下來(lái)的就是一條一條的日志記錄，如圖 1，所示它的的內(nèi)容由三個(gè)部分組成：Common-Header，Post-Header( 不 是每條記 錄都有），Body。 Common-Header部分不同版本的大小不一樣，4.0 以上的都是 19 個(gè)字節(jié)。 在這個(gè)之后就是 Body，也就是記錄的內(nèi)容。

圖1 日志記錄的結(jié)構(gòu)(數(shù)字表示字段的字節(jié)數(shù))

Post-Header只有在 query 類(lèi)型的記錄中才有，如果是其它的記錄類(lèi)型則沒(méi)有 Post-Header。 記錄的類(lèi)型在 Common-Header中的一個(gè)字節(jié)標(biāo)注出來(lái)。

1.2 Common-Header結(jié)構(gòu)

Common-Header結(jié)構(gòu)一共有 19 個(gè)字節(jié)，如圖 2 所示，包括 6個(gè)部分，分別為：Timestamp，Type，Server-id，Total-size，End-logpos，F(xiàn)lag。

圖2 Common-Header的結(jié)構(gòu)

Timestamp：該字段代表該條記錄寫(xiě)入的時(shí)間，用4個(gè)字節(jié)表示;

Type：該字段代表記錄的類(lèi)型，比如 QUERY，LOAD-EVENT，F(xiàn)ORMAT-DESCRIPTION-EVENT 等類(lèi)型，其中每個(gè)二進(jìn)制文件的第一條記錄的類(lèi)型都是 FORMAT-DESCRIPTION-EVENT 類(lèi)型，它記錄了該日志文件的相關(guān)信息，這些信息對(duì)于后序分析日志記錄是有用的。 而對(duì)于后續(xù)的記錄，我們主要是對(duì)日志的刪除更改操作進(jìn)行查找，固我們只對(duì) QUERY 類(lèi)型的記錄進(jìn)行解析，QUERY 類(lèi)型的日志記錄主要是記錄用戶(hù)平時(shí)的刪除更改操作，如：insert，drop，delete， update 等。 Query 的類(lèi)型值為 2，在記錄中為00000010。 該字段用 1 個(gè)字節(jié)表示;

Server-id：創(chuàng)建這個(gè)日志記錄的服務(wù)器 ID，防止循環(huán)主從導(dǎo)致的主機(jī)被重寫(xiě)，該字段用4個(gè)字節(jié)表示;

Total-size：該條日志記錄的大小，該字段用 4 個(gè)字節(jié)表示;

End-log-pos：該條日志記錄結(jié)束的位置(相對(duì)于日志文件的開(kāi)頭位置偏移字節(jié)數(shù)的數(shù)目），也就是該條日志記錄最后一個(gè)字節(jié)的下一個(gè)字節(jié)的位置，該字段用4個(gè)字節(jié)表示;

Flag：標(biāo)志位，該字段用 2 個(gè)字節(jié)表示。

1.3 Post-Header結(jié)構(gòu)

QUERY 類(lèi)型的記錄除了開(kāi)始的 Common-Header 之外，在Body 的開(kāi)頭是一個(gè) Post-Header結(jié)構(gòu)，然后之后才是真正的 body內(nèi)容。 或者可以說(shuō) Post-Header就是 Body 的一部分，因?yàn)橹饕菍?duì) QUERY 類(lèi)型的記錄進(jìn)行解析，這里單獨(dú)拿 出來(lái)分析。 Post-Header結(jié)構(gòu)一共有 13 個(gè)字節(jié)，如圖 3 所示，包括 5 個(gè)部分，分別為：Thread-id，Exec-time，Db-len，Error-code，Status-var-len。

圖3 Post-Header的結(jié)構(gòu)

Thread-id：表示線程 ID，用來(lái)區(qū)分用戶(hù)的臨時(shí)表，用 4 個(gè)字節(jié)表示;

Exec-time：表示記錄所記錄的信息在數(shù)據(jù)庫(kù)中執(zhí)行的時(shí)間，用4個(gè)字節(jié)表示;

Db-len：表示該記錄所記錄的信息所在的數(shù)據(jù)庫(kù)的名字的長(zhǎng)度，用1個(gè)字節(jié)表示;

Error-code：執(zhí)行出錯(cuò)的錯(cuò)誤碼，用 2 個(gè)字節(jié)表示;Status-var-len：Status-var字段的長(zhǎng)度，該字段在 Body 結(jié)構(gòu)中，用 2 個(gè)字節(jié)表示。

1.4 Body 結(jié)構(gòu)

Body結(jié)構(gòu)是日志記錄中的實(shí)質(zhì)內(nèi)容，如圖4所示，包括 Status-var，Db，Query 三個(gè)部分。 Body 結(jié)構(gòu)中記錄了用戶(hù)對(duì)數(shù)據(jù)庫(kù)的操作，該結(jié)構(gòu)的長(zhǎng)度不是定長(zhǎng)的，該結(jié)構(gòu)的長(zhǎng)度由前面介紹的結(jié)構(gòu)中的字段決定。

圖4 Body的結(jié)構(gòu)

Status-var：表示 Status-var-len 個(gè)狀態(tài)。 一個(gè)狀態(tài)由一個(gè)字節(jié)表示。 該字段用 Status-var-len(其值大于等于零）個(gè)字節(jié)表示;

Db：表示用戶(hù)操作的數(shù)據(jù)庫(kù)的名字，用 Db-len+1 個(gè)字節(jié)表示，是一個(gè)以 null字符結(jié)尾的字符串;Query：表示一個(gè)查詢(xún)語(yǔ)句，是可變長(zhǎng)度的字符串沒(méi)有尾隨 0，延伸至記錄結(jié)尾(該部分的長(zhǎng)度可以通過(guò) Common-Header中的字段計(jì)算確定） ，在 MySQL5.0.4版本之后該部分會(huì)有4個(gè)字節(jié)用作校驗(yàn)。

1.5 驗(yàn)證MySQL日志記錄結(jié)構(gòu)

為了驗(yàn)證MySQL二進(jìn)制日志結(jié)構(gòu)分析的正確性，使用二進(jìn)制文件查看器選取一條記錄進(jìn)行分析，如圖 5 所示，小圖(a）(b）(c）分別為日志記錄(QUERY 類(lèi)型）中的 Common-Header，Post-Header，Body的三部分，在 MySQL 二進(jìn)制日志中的編碼模式是小端模式。

圖5 MySQL 二進(jìn)制日志記錄

1）a段一共19個(gè)字 節(jié)，E4 F3 2F 53 表示時(shí)間，因?yàn)槎M(jìn)制是用小尾數(shù)表示的所以上面四個(gè)字節(jié)表示0x532FF3E4=1395651556(十進(jìn)制），轉(zhuǎn)換成時(shí)間就是2014/3/2416：59：16。02表示類(lèi)型，就是QUERY類(lèi)型，01 00 00 00 表示server-id，0x00000001=1， 77 00 00 00 表示 total-size，就是 0x00000077= 119;3E 01 00 00 表示記錄結(jié)束的地方，就是離文件起始位置有0x0000013E=318個(gè)字節(jié);00 00 是標(biāo)識(shí)位。

2）b段一共13個(gè)字節(jié)，17 00 00 00 表示 thread-id， 大小為23;00 00 00 00 表示 exec-time，大小為零;04 表示數(shù)據(jù)庫(kù)名字的長(zhǎng)度，大小為 4;00 00 表示 error-code，大小為 0，表示無(wú)錯(cuò);21 00表示 status-var-len 的長(zhǎng)度大小為 33;

3） c 段一共 87 個(gè)字節(jié)，這個(gè)值可以有 total-size 減去 Common-Header和 Post-Header的長(zhǎng)度得出，119-19-23=87，該結(jié)果與記錄中實(shí)際的長(zhǎng)度是一樣的;00 00 00 00 00 01 00 00 20 50 00 00 00 00 06 03 73 74 64 04 08 00 08 00 21 00 0C 01 74 65 73 74 00這里一共 33 個(gè)字節(jié)，表示狀態(tài)的值;74 65 73 74 00 這里一共 5個(gè)字節(jié)表示，表示數(shù)據(jù)庫(kù)的名字，根據(jù) ascii碼的轉(zhuǎn)換可以得出該數(shù)據(jù)庫(kù)的名字為 test;75 70 64 61 74 65 20 74 73 65 74 20 73 65 74 20 6E 61 6D 65 3D 27 79 61 6C 69 63 65 73 68 69 27 20 77 68 65 72 65 20 69 64 20 3D 20 31 這里 45 個(gè)字節(jié)，該段二進(jìn)制內(nèi)容根據(jù)ascii碼轉(zhuǎn)換后可以得出字符串為：update tset set name= ＇yaliceshi＇where id=1，該字符串為 SQL 的命令語(yǔ)句，最后的四個(gè)字節(jié) 3A CC 18 EC 是校驗(yàn)碼，判斷整條記錄是否正確。

最后用mysqlbinlog[7］將該條記錄轉(zhuǎn)換成文本文件，通過(guò)比對(duì)顯示前文對(duì) MySQL 二進(jìn)制日志的結(jié)構(gòu)分析是正確的。

2 MySQL數(shù)據(jù)庫(kù)取證算法

在MySQ二進(jìn)制日志文件中根據(jù)關(guān)鍵字提取關(guān)鍵信息，主要是兩步：第一步是否可以匹配到關(guān)鍵字;第二步是在匹配到關(guān)鍵字的情況下提取該記錄中相關(guān)的信息，進(jìn)行MySQL數(shù)據(jù)庫(kù)取證。

2.1 KMP算法

KMP算法是一種線性時(shí)間字符串匹配算法，該算法是是由Knuth、Morris和Pratt三個(gè)人共同提出來(lái)的[8］。其實(shí)KMP算法與BF算法(Brute Force，普通的的模式匹配算法 ）的區(qū)別就在于KMP算法巧妙的消除了指針i(指在目標(biāo)串中標(biāo)記正在匹配的字符的位置）的回溯問(wèn)題，只需確定下次匹配j的位置即可，使得問(wèn)題的復(fù)雜度由O(mn）下降到O(m+n）。

在KMP算法中，為了確定在匹配不成功時(shí)，下次匹配時(shí)j的位置，引入了next數(shù)組，next[j］的值表示P[0，j-1］(P表示需要匹配的字符串）中最長(zhǎng)后綴的長(zhǎng)度等于相同字符序列的前綴。對(duì)于next數(shù)組的定義如下：

1）next[j］ =-1;j=0

2）next[j］ =max(k）;0＜k＜j，P[0，k-1］ =P[j-k，j-1］

3）next[j］ =0;其他

下面使用一個(gè)字符串 ababa 進(jìn)行說(shuō)明，由字符串推出next數(shù)組，如表1。

表 1 字符串P與next數(shù)組對(duì)應(yīng)表

即 next[j］ =k＞0 時(shí)，表示 P[0…k-1］ =P[j-k，j-1］

因此 KMP 算法的思想就是：在匹配過(guò)程稱(chēng)，若發(fā)生不匹配的情況，如果 next[j］ ＞ =0，則目標(biāo)串的指針 i不變，將模式串的指針j移動(dòng)到 next[j］ 的位置繼續(xù)進(jìn)行匹配;若 next[j］ =-1， 則 將 i 右移 1 位，并將 j置 0，繼續(xù)進(jìn)行比較。

2.2 MySQL 數(shù)據(jù)庫(kù)取證算法

首先我們要判斷提取信息的文件是不是 MySQL 二進(jìn)制日志文件，然后進(jìn)行關(guān)鍵字匹配，然后提取信息，最后輸出結(jié)果進(jìn)行取證，流程圖如圖 6。

1）判斷是否是二進(jìn)制日志文件是不是 MySQL 二進(jìn)制日志文件是則執(zhí)行第 2步，否則執(zhí)行第 8步;

2）讀取一條日志記錄的 Common-Header部分，也就是流程圖中的記錄的頭部;

3）根據(jù)記錄的頭部判斷是否是 QUERY 類(lèi)型，如果是則執(zhí)行第4步，否則執(zhí)行第 7步;

4）根據(jù) Common-Header和 Post-Header的信息定位 Body 部分中的內(nèi)容實(shí)質(zhì)，在 QUERY 類(lèi)型中就是 SQL 語(yǔ)句;

圖6 MySQL 數(shù)據(jù)庫(kù)取證算法流程圖

5）在 SQL 語(yǔ)句中使用 KMP 算法匹配關(guān)鍵字匹配成功則執(zhí)行第六步;否則執(zhí)行第7步;

6）輸出記錄的相關(guān)信息：時(shí)間、操作類(lèi)型、SQL 語(yǔ)句;

7）判斷文件是否讀完，是則執(zhí)行第 8 步，否則執(zhí)行第 2 步;

8）結(jié)束。

3 實(shí)驗(yàn)結(jié)果

通過(guò)使用上文所述的基于日志分析的 MySQL 數(shù)據(jù)庫(kù)取證算法，對(duì) MySQL 數(shù)據(jù)庫(kù)進(jìn)行了取證。 實(shí)驗(yàn)使用 VS2010、MySQL 5.6等開(kāi)發(fā) 軟 件 在 windows7 系 統(tǒng) (64bit） ， 內(nèi) 存 8GB， Intel(R） Core (TM） i7-4800MQ CPU@2.70GHz 的環(huán)境下對(duì)該方法進(jìn)行了實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果如圖 7。

圖7 實(shí)驗(yàn)結(jié)果

從圖 7 中可以看出在名為 binlog.000001 的 MySQL 二進(jìn)制日志文件中;檢索出了關(guān)于 binlog-test的相關(guān)信息，如 insert、create、update、delete 操作。 也可以從實(shí)驗(yàn)結(jié)果中看出我們的分析的二進(jìn)制日志記錄結(jié)構(gòu)和對(duì)數(shù)據(jù)庫(kù)取證的算法是正確的。

表 2 不同數(shù)量級(jí) MySQL 數(shù)據(jù)庫(kù)取證對(duì)比表

后續(xù)對(duì)多個(gè)有不同數(shù)量級(jí)數(shù)據(jù)的 MySQL 數(shù)據(jù)庫(kù)進(jìn)行了取證實(shí)驗(yàn)，得到了表2的對(duì)比數(shù)據(jù)。 這3個(gè)數(shù)據(jù)庫(kù)中分別有1 000、10 000、100 000條記錄，從這些數(shù)據(jù)庫(kù)中取證相同的信息。 可以從表中看出該算法對(duì)多個(gè)不同量級(jí)的數(shù)據(jù)庫(kù)取證時(shí)的正確率都是100%，而且時(shí)間上的增長(zhǎng)和數(shù)據(jù)數(shù)量的增長(zhǎng)基本一致，表 2 的數(shù)據(jù)驗(yàn)證了本文提出的算法可以對(duì) MySQL 數(shù)據(jù)庫(kù)進(jìn)行有效的取證。

4 結(jié)語(yǔ)

本文通過(guò)分析 MySQL 二進(jìn)制日志結(jié)構(gòu)，使用 KMP 算法進(jìn)行關(guān)鍵字匹配提取出與關(guān)鍵字相關(guān)的重要信息，能有效的對(duì)MySQL 數(shù)據(jù)庫(kù)進(jìn)行取證;但是目前分析的二進(jìn)制日志文件都是需要明確的路徑的，還不能自動(dòng)的尋找計(jì)算機(jī)中的 MySQL 二進(jìn)制日志文件。 如何自動(dòng)尋找計(jì)算機(jī)中所有的 MySQL 二進(jìn)制日志文件，高效檢索多個(gè)二進(jìn)制日志文件中的有效信息從而更全面的對(duì) MySQL 數(shù)據(jù)庫(kù)進(jìn)行取證將是下一步的研究重點(diǎn)。

[1］Peter Fruhwirt，Markus Huber，Martin Mulazzani， etc.InnoDB Database Forensics[C］ //Proceedings of the 2010 24th IEEE International Conference on Advanced Information Networking and Applications，Washington DC USA：IEEE Computer Society，2010：1028-1036.

[2］Peter Fruhwirt，Peter Kieseberg，Sebastian Schritwieser，etc.InnoDB Database Forensics： Enhanced reconstruction data manipulation queries from redo logs[J］ .Information Security Technical Report： 2013，17(4） ：227-238.

[3］Mario A.M.Guimaraes，Richard Austin，Huwida Said etc.Database forensics[C ］ //2010 Information Security Curriculum Development Conference.New York USA： Association for Computing Machinery(ACM） ， 2010：62-65.

[4］Werner K.，Haugerl，Martin S.The role of triggers in database forensics[C ］ //Information Security for South Africa(ISSA ）Conference.Washington DC USA：Institute of Electrical and E-lectronics Engineers(IEEE），2014： 1-7.

[5］祝定澤，張海，黃建昌.MySQL 核心內(nèi)幕[M］.清華大學(xué)出版社，2010.

[6］Stefan Hinz， Jonathan Stephens， Philip Olson， etc.Overview of MySQL Programs[DB/OL］ .2009-11-1[2014-10-13］ . http： //dev.mysql.com/doc/refman/5.6/en/programs-overview.html.

[7］Stefan Hinz， Jonathan Stephens， Philip Olson， etc.mysqlbinlog[DB/OL］.2009-11-1[2014-10-13 ］ .http： //dev. mysql.com/doc/refman/5.6/en/mysqlbinlog.html.

[8］Thomas H.Cormen， Charles E.Leiserson， Clifford Stein， etc.算法導(dǎo)論[M］.潘金貴，顧鐵成，李成法，等譯.機(jī)械工業(yè)出版社，2006.

MySQL Database Forensics Algorithm based on Log Analysis

TAN Sen， GUO Jie
(School of Electronic Information and Electrical Engineering， SJTU，Shanghai 200240， China）

With its wide use， MySQL database forensics issue becomes increasingly important.Log is the most essential information proof of database forensics， and MySQL binary log records all the data changing operations of database made by users.An analysis of MySQL binary log structure is proposed， and KMP algorithm is used to make keyword matching of MySQL binary log and retrieve the required information， then the forensics algorithm is conducted on MySQL database.Experimental results indicate the effectiveness of this forensics algorithm.

MySQL;binary log;information retrieval;KMP algorithm;database forensics

TP 309.2

A

1009-8054(2015)03-0081-04

譚 森(1990—），男，碩士，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)庫(kù)安全;

2014-11-25

司法部司法鑒定科學(xué)技術(shù)研究所科研院所公益研究專(zhuān)項(xiàng)(No.GY2013G-3)

郭 捷(1976—），女，博士，副研究員，主要研究方向?yàn)閿?shù)據(jù)庫(kù)安全和流媒體安全。■