2017年3月21日 星期二

用Python ctypes 建立與C的介面

故事是這樣子的,最近小弟接觸一項工作,主要是開發一套C 的API,實作大程式底層的介面,以前只有改過別人的介面,這次自己從頭到尾把介面建起來,git repository 提交100多個commit,說實在蠻有成就感的。
寫Project的過程中也發現自己對測試的經驗實在不夠,本來想說該把unit test set 建起來然後做個 regression test,結果unit test 寫一寫最後都變成behavior test 了,啊啊啊啊我根本不會寫測試啊,測試好難QQQQ

寫測試時也發現一個問題,用C 寫測試實在有點痛苦,陸續看了幾個例如 CMocka 的testing framework,實作起來還是挺麻煩的;有些要測試的功能,例如檔案parser,都需要另外找library來支援,而C 的library 卻未必合用,要放入project 的Makefile 系統也很麻煩;C 需要編譯也讓有彈性的測試較難達成。
這時我們的救星:Python 又出現了,是否能利用python上面豐富的模組跟套件,還有簡單易用的 testing framework,可以彈性修改的直譯執行來幫助測試呢?

一開始我看了一下Python C/C++ extension,這是將C的程式包成函式庫,並對它增加一層 Python 呼叫的介面,變成 Python 可以 import 的module。
但是這個方法有點太殺雞用牛刀了,這是要用在python 極需性能的部分,可以寫C 進行加速,而不是單純想 call C function 來測試。
比較好的解法是利用python 的ctypes,可以直接載入編譯好的 shared library,直接操作C 函式。引用參考資料<程式設計遇上小提琴>的話:與其做出pyd來給python使用這種多此一舉的事情,東西就在那裡,dll就在那裡,為何不能直接使用呢?
所以我們的救星:ctypes 登場了。

這篇先來談談 ctypes 的大致用法,下一篇我們來說明一下在 project 中利用到它們的地方。

首先是要引用的對象,使用ctypes 前要先把要引用的project 編成單一的動態函式庫,下面以 libcoffee.so 為例,如此一來,我們可以用下列的方式,將 .so 檔載入python 中:
filepath = os.path.dirname(os.path.abspath(__file__))
libname = "libcoffee.so"
libcoffee = ctypes.cdll.LoadLibrary(os.path.join(filepath, libname))
ctypes 有數種不同的載入方式,差別在於不同的 call convention,cdll 用的是cdecl,windll 跟oledll 則是 stdcall。載入之後就可以直接call 了,有沒有這麼猛(yay)

參數處理:

ctypes 中定義了幾乎所有 C 中出現的基本型別,請自行參考內容表格,None 則會直接對應 C 的NULL:
https://docs.python.org/2/library/ctypes.html#fundamental-data-types
所有產生出來的值都是可變的,可以透過 .value 去修改。
例外是利用Python string 來初始化 c_char_p(),再用 value 修改其值,原本的Python string 也不會被修改,這是因為Python string 本身就是不可修改的。
如果要初始化一塊記憶體,丟進C 函式中修改的話,上面的 c_char_p 就不能使用,要改用creat_string_buffer 來產生一塊記憶體,可以代入字串做初始化,並指定預留的大小,爾後可以用 .value 來取用NULL terminated string,.raw 來取用 memory block。
如果要傳入 reference ,除了 create_string_buffer 產生的資料型態本身就是 pointer 之外,可以用 byref() 函式將資料轉成 pointer。
使用 ctypes 呼叫C 函式,如果參數處理不好,會導致 Python 直接crash,所以這點上要格外小心。

我們可以為函式加一層 argtypes 的保護,任何不是正確參數的型態想進入都會被擋下,例如:
libcoffee.foo.argtypes = [c_int]
# 之前這樣會過,C function 也很高興的call 下去
libcoffee.foo(ctypes.c_float(0))
# 設定之後就會出現錯誤
ctypes.ArgumentError: argument 1: <type 'exceptions.TypeError'>: wrong type
這部分採 strict type check ,甚至比C 本身嚴格,如果設定argtypes 為:
POINTER(c_int)
那用 c_char_p 這種在C 中可以轉型過去的型態也無法被接受。

restype 則是定義 C 函式的 return type,因為我的函式都回傳預設的 c_int ,所以這部分不需要特別設定。比較令我驚豔的是,ctypes 另外有 errcheck 的屬性,這部分同restype 屬性,只是在檢查上比較建議使用errcheck。
errcheck 可以設定為 Python callable (可呼叫物件,無論class 或function ),這個callable 會接受以下參數:
callable(result, func, args)
result 會是從C 函式傳回來的結果;func 為 callable 函式本身;args 則是本來呼叫C 函式時代進去的參數,在這個callable 中我們就能進行進一步的檢查,在必要的時候發出例外事件。
def errcheck(result, func, args):
 if result != 0:
   raise Exception #最好自己定義 exception 別都用預設的
 return 0
libcoffee.errcheck = errcheck

衍生型別:

ctypes 另外提供四種衍生型別 Structure, Union, Array, Pointer 來對應C 的struct, union, array, pointer
每個繼承 Structure 跟Union 的 subclass 都要定義 _filed_,型態為 2-tuples 的 list,2-tuple 定義 field name 跟 field type,型態當然要是 ctypes 的基本型別或是衍生的 Structure, Union, Pointer 。
Struct 的align 跟byte order 請參考:
https://docs.python.org/2/library/ctypes.html#structure-union-alignment-and-byte-order

Array 就簡單多了,直接某個 ctypes 型態加上 * n 就是Array 型態,然後就能如class 般直接初始化:
TenInt = ctypes.c_int * 10
arr = TenInt()

Pointer 就如上面所說,利用 pointer() 將 ctypes 型別直接變成 pointer,它實際上是先呼叫 POINTER(c_int) 產生一個型別,然後代入參數值。
爾後可以用 .contents 來取用內容的副本(注意是副本,每次呼叫 .contents 的回傳值都不一樣)和 C 一樣,pointer 可以用 [n] slice,並且修改 [n] 的內容即會修改原本指向的內容,取用 slice 的時候也要注意out of range 的問題,任何會把C 炸掉的錯誤,通常也都會在執行時把 python 虛擬機炸了。
同樣惡名昭彰的Null pointer dereference:
null_ptr = POINTER(c_int)()
產生NULL pointer,對它 index 也會導致 Python crash。

Callback

ctypes 也可以產生一個 callback function,這裡一樣有兩個函式:CFUNCTYPE 跟 WINFUNCTYPE,分別對應 cdecl 跟 stdcall;以第一個參數為 callback 的return type,其餘參數為 callback 參數。
這部分我這裡沒有用到先跳過,不過下面的連結有示範怎麼用ctypes 寫一個可被 qsort 接受的 callback 函式,真的 sort 一個buffer 給你看:
https://docs.python.org/2/library/ctypes.html#callback-functions

實際案例

上面我們把ctypes 的文件整個看過了,現在我們來看看實際的使用案例。
這裡示範三個 C function,示範用ctypes 接上它們,前情提要一下project 的狀況,因為寫project 的時候消耗了太多咖啡了,所以project 的範例名稱就稱為 coffee,我們會實作下面這幾個函式的介面:
// 由int pointer回傳一個隨機的數字
int coffee_genNum(int *randnum, int numtype);
// 在buf 中填充API version string
int coffee_getAPIVersion (char *buf)
// 對src1, src2 作些處理之後,結果塞回到dest 裡面
int coffee_processBuf (char *src1, char *src2, char *dest, int len)
針對我要測試的 c header,就對它寫一個 class 把該包的函式都包進去,init 的部分先將 shared library 載入:
import ctypes
import os.path

class Coffee(object):
  """libcoffee function wrapper"""

  def __init__(self):
    filepath = os.path.dirname(os.path.abspath(__file__))
    libname = "libcoffeeapi.so"
    self.lib = ctypes.cdll.LoadLibrary(os.path.join(filepath, libname))
所有 header 檔裡面的自訂型別,都能很容易直接寫成 ctypes Structure,舉個例本來有個叫counter 的 Union,比對一下C 跟Python 版本:
C 版本:
typedef union Counter {
  unsigned char counter[16];
  unsigned int counter32[4];
} Counter;
Python ctypes 版本:
class Counter(Union):
  _fileds_ = [
    ("counter", c_uint8 * 16),
    ("counter32", c_uint32 * 4)]
針對 C 裡面的函式,我們把它們寫成各別的 Python 函式對應,同時為了保險起見,每個函式都設定 argstype,這樣在參數錯誤時就會直接丟出 exception;又因為函式都依照回傳非零為錯誤的規則,所以可以對它們設定 errcheck 函式,在return 非零時也會拋出例外事件。
這裡的作法是在class __init__ 裡面把該設定的都寫成一個dict,這樣有必要修改的時候只要改這裡就好了:
def errcheck(result, func, args):
    if result != 0:
        raise Exception
    return 0

# in __init__ function
argstable = [
  (self.lib.coffee_genNum,          [POINTER(c_int), c_int]),
  (self.lib.coffee_getAPIVersion,   [c_char_p]),
  (self.lib.coffee_processBuf,      [c_char_p, c_char_p, c_char_p, c_int])]

  for (foo, larg) in argstable:
    foo.argtypes = larg
    foo.errcheck = errcheck

然後就是實作各函式了,這部分就是苦力,想要測的函式都拉出來,介面的參數我就用Python 的物件,在內部轉成ctypes 的物件然後往下呼叫,所以如getNum 的轉化型式就會長這個樣子,pointer 的參數,可以使用 ctypes 的byref 。
# int coffee_genNum(int *randnum, int numtype);
def genNum(self, numtype):
  _arg = c_int(numtype)
  _ret = c_int(0)
  self.lib.coffee_genNum(byref(_ret), _arg)
  return _ret.value
getAPIVersion 是類似的,這次我們用 create_string_buffer 產生一個 char pointer,然後直接代入函式,就可以用value 取值了。
# int coffee_getAPIVersion (char *buf)
def getAPIVersion(self):
  buf = create_string_buffer(16)
  self.lib.coffee_getAPIVersion(buf)
  return buf.value
最後這個的概念其實是一樣的,我把它寫進來只是要火力展示XD,上面提到的processBuf,實際上可以把它們跟Python unittest 結合在一起,利用python os.urandom來產生完全隨機的string buffer,答案也可以從python 的函式中產生,再用unittest 的assertEqual 來比較buffer 內容:
l = 4096
src1 = create_string_buffer(os.urandom(l-1))
src2 = create_string_buffer(os.urandom(l-1))
dest = create_string_buffer(l)
ans  = generateAns(src1, src2)
self.lib.coffee_processBuf(src1, src2, dest, l)
self.assertEqual(dest.raw, ans)
一個本來在C 裡面要花一堆本事產生的測試函式就完成啦owo
如能將這個class 加以完善,等於要測哪些函式都能拉出來測試,搭配python unittest 更能顯得火力強大。

後記:
趁這個機會把ctype的文件整個看過一遍,覺得Python 的 ctypes 真的滿完整的,完全可以把 C 函式用 ctypes 開一個完整的 Python 介面,然後動態的用 Python 執行,真的是生命苦短,請用python。

參考資料:

https://docs.python.org/2/library/ctypes.html
http://blog.ez2learn.com/2009/03/21/python-evolution-ctypes/

2017年3月18日 星期六

使用"旁通道攻擊"攻擊腳踏車

Bob 和Alice 兩位都是T大的學生,Alice 暗戀Bob 已久,發現Bob 下課在校園間移動,都騎著他那台紅色小腳踏車。Alice 於是心生一計:如果她偷走Bob 的腳踏車,Bob 下課找不到腳踏車的時候,她就能騎著腳踏車出現在Bob 身邊,好心載他一程,以拉近兩人的關係
問題是Bob 的腳踏車用了密碼鎖,想要破解或試出密碼,或找到大剪剪斷塑膠的部分都不是那麼容易的事,那到底該如何解開密碼鎖,偷走腳踏車呢?

這時Alice 靈機一動,想起上週在聽密碼學導論時,教授提到有關旁通道攻擊(Side Channel Attack, SCA)的內容,為何不能利用旁通道攻擊來破解密碼鎖呢?
所謂旁通道攻擊,就是不正攻防禦系統中最強的部分,像是用暴力法直接試密碼鎖10,000 種不同的組合,或者拿大剪直接斷塑膠的部分,前者要試很久,後者有點太明目張膽了;反之旁通道攻擊從每次加解密時流出來的資訊,推敲出金鑰全部或部分,從1996年Kocher那篇 Timing attacks on implementations of Diffie-Hellman發表至今,無論從電源消耗、近場輻射,甚至聲音,旁通道攻擊攻破無數數學上完全的密碼系統,那麼腳踏車呢?

前情提要到此:
理論還滿簡單的,密碼鎖上有4個0-9的數字,上鎖之後要把數字撥亂,其他人才猜不到真正的密碼;可是,撥亂這件事-或稱亂數產生器-卻不一定有被認真對待。
Bob 上鎖時,可能大手一轉就以為鎖好了,很可能4個數字轉盤裡面有2到3個都是一起轉的,或者因為Bob 是右撇子,都用右手向右撥,也因此,只要持續記錄Bob 每次鎖車時轉盤上的數字,就可以推測出密碼的數值
這是Alice 努力不懈每天記下Bob 停腳踏車後密碼鎖的數值:
1752 4852 5941 5652 4869 4830 5941 4841
其實結果還滿明顯的,轉的數值真的跟習慣有關,甚至多次轉出一樣的數字,我光用看的都能看出來ABCD 四個數字間的關係,AB 差4 (B-A),CD差7 (D-C),BC 比較看不出來,但算眾數的話是差8,如果有更多筆資料就能更精準的看出關係,這可能是我習慣上會四個一起轉之後,CD兩位再轉一些,導致BC差值通常不固定。
由上猜測,腳踏車的密碼可能是 0429,以及四個數字一起轉的其他結果:1530, 2641……9318,很不巧,0429真的是Bob 的腳踏車鎖密碼。

試過其他解法,例如假設真正的密碼是ABCD,觀察到的數值是A’B’C’D’,個別數字的距離:X-X’ 應該會相當接近才對,我寫了個小程式去算 0000-9999 取 X-X’ 的標準差,然後算所有測試結果的標準差總合,愈小的愈可能是答案。
後來發現這招沒用,例如密碼0000 被轉成 6688,這樣比起正確的密碼0000,0011這個錯誤解在這個算法下就會勝過0000。

無論如何,記錄了8組數據就能把10,000組密碼組合縮減到10 組,旁通道攻擊果然有用啊。
可惜後來Bob 發現腳踏車不見了,就跑去借公共腳踏車(NT)Ubike,功敗垂成不禁讓Alice 感嘆:偷得走心上人的腳踏車,卻偷不走他的心。

反思:
* 人類其實不是一個很好的亂數產生器,就如上面的例子,轉盤轉的數字看似亂數,其實隱藏了內部規則,就像現在請人在1到100中選一個數,大家通常認為人腦選的數字是亂的,其實受限一些人腦的想法,我想結果應該也不是<真的>亂數;另外,依照人的習慣,轉出來的數字,通常也不會跟原有密碼重複,由這也會流出一些線索。
* 如果要比較安全的腳踏車鎖,請使用鑰匙鎖,密碼鎖上鎖都該用真的亂數產生器產生密碼,或者每次轉密碼不能偷懶,一格一個好好的亂轉。
其實,每次上鎖都把它轉成 0000 也是不錯防範方式XD
* 其實我不確定有沒有更好的攻擊方法,只能從數字的規則中推敲出密碼間的關係,但資料量一多關係就很明顯了,這也是統計的效應:資料的數量才是重點,就算裡面垃圾很多,透過大量資料也能篩出有意義的資訊,某種程度上來說,統計或Big Data 也是從垃圾裡淘出黃金,算是現代的回收業吧XD。

後記:
其實幾個月前,我鑰匙型的車鎖不見了,換了新的密碼鎖,多轉了幾次之後,想到這個點子。本篇文中的例子,都是這一個星期來,每次停腳踏車時就記錄一次,累積一個星期的資料就猜出密碼了。當然文中提到的密碼也是真的,只是我現在已經換了一個,所以大家要是看到我的小紅,就別用文中的密碼去試了。
也要提醒大家,如果看到有人在看你腳踏車密碼鎖,而且過幾天又看到他,很可能他就是要對你的腳踏車實施旁通道攻擊,腦袋中一定響個警鈴:「噹噹,你的腳踏車正遭受攻擊」,一定要記得換個密碼。

不過話說回來,我猜直接搬走腳踏車比這個方法容易多了。

2017年3月9日 星期四

使用 git patch 來搬移工作內容

前幾天在改一個專案,因為筆電的設備不夠強大,只能到桌電上開發,兩邊都是開發機,也就沒有用remote 的方式來同步專案。今天,要把那時候的commit 搬回筆電,只好使用git 的patch 移動工作內容,這裡記錄一下整體工作流程和解決衝突的方法。

首先是生成 patch,git 本身有兩種 patch 的功能,一種是使用常見的diff,一種則是 git 專屬的patch system。
常見的 diff 其實也就是git diff 生成的 patch,內容就是:這幾行刪掉,這幾行加上去,用 git diff > commit1.patch 就能輕鬆生成。git patch system 則是用 git format-patch 來產生,它提供比 diff 更豐富的資訊,他的使用有幾種方式:
git format-patch <commit>  從某一個 commit 開始往後生成patch
git format-patch -n <commit> 從某一個 commit 開始從前先成 n 個patch

使用format-patch的好處是,它可以一次對大量的commit 各產生一個patch,之後就能用git 把這些commit 訊息原封不重放到另一個 repository 裡面;我自己的習慣,是開發一個 features 就開一個新的branch,這樣在生成 patch的時候只要使用format-patch master,就會把這條分枝的 commit 都做成patch,git 會自動在檔案前綴 0001, 0002,這樣用 wildcard patch 時就會自動排序好。
你說如果 patch 的數量超過10000 個怎麼辦……好問題,我從來沒試過這麼多patch,搞不好我到目前為止的 commit 都沒這麼多呢,一般project 超過 10000 個commit ,結果要用patch system 來搬動工作內容也是滿悲劇的啦
細看 patch 的內容,開頭是這個commit 的概略訊息,修改的檔案小結,後面就是同樣的diff 內容。
From commit-hash Mon Sep 17 00:00:00 2001
From: author <email>
Date: Mon, 6 Mar 2017 14:07:42 +0800
Subject: [PATCH] fix getDates function

---
database.py  | 9 +++++----
viewer.py      | 5 +++++
2 files changed, 10 insertions(+), 4 deletions(-)

現在我們來使用 patch ,把這些patch檔拿到要apply 的repository裡
針對常見的diff,其實用shell 的patch 指令就能apply 上去,但它出問題的風險比較高,也不能把 commit 訊息帶上,所以我都不用這招。對format-patch產生的 patch,我們就能用 git apply 的指令來用這個 patch,首先先用
git apply --check patch
來檢查 patch 能不能無縫補上,只要打下去沒噴訊息就是正常。

接著就是用 git apply patch 把patch 補上,然後記得自己commit 檔案。
這樣還是太慢,我們可以用
git am *.patch
把所有的 patch 一口氣送上,運氣好的話,會看到一整排的 Applying: xxxxx,所有的commit 立即無縫接軌。

如果運氣不好,patch 有衝突的話,apply 就會什麼都不做。
衝突其實很常見,只要你產生patch 跟apply patch 的地方有些許不同就會發生,因為patch 裡只記載了刪掉哪些內容、加上哪些內容,一旦要刪掉的內容不同,apply就會判斷為衝突。這跟merge 的狀況不同,merge 的時候雙方有一個 base作為基準點,可以顯示 <<<<<< ====== >>>>>> 的差異比較,apply 的資訊就少很多。
在 apply patch 的時候,也可以使用 -3 來使用3方衍合,但若你的repository 中沒有patch 的祖先,這個apply 一樣會失效。
衝突時am 會跳出類似這樣的訊息:
Applying: <commit message>
error: xxxxxxxxxxxxxxxxxxx
Patch failed at 0001 <commit message>
The copy of the patch that failed is found in: .git/rebase-apply/patch
When you have resolved this problem, run "git am --continue".
If you prefer to skip this patch, run "git am --skip" instead.
To restore the original branch and stop patching, run "git am --abort".

這裡我們只能手動解決,在apply 的指令加上:
git apply --reject patch
這樣會補上那些沒有問題的patch, 然後把無法補上的地方寫入 .rej 檔案中。
下一步我們要用編輯器,打開原始檔跟 .rej 檔,把檔案編輯成應該變成的樣子,把該加的檔案變化都git add add 之後,使用 git am --continue 完成commit。
後悔了,直接用 git am --abort 停掉 am 即可。

以上是git patch system 的簡介,我的心得是,能用git remote 就用git remote,merge 起來資訊豐富很多,解決衝突也有git-mergetool 如vimdiff 可以用,省得在那邊 format-patch 然後apply 起來機機歪歪,每個commit 都要手動解衝突是會死人的。

參考資料:
https://git-scm.com/book/en/v2/Distributed-Git-Maintaining-a-Project
http://aknow-work.blogspot.tw/2013/08/patch-conflict.html