2017年4月25日 星期二

Effective Modern C++: 42 Specific Ways to Improve Your Use of C++11 and C++14

中譯書名是「Effective Modern C++ 中文版:提昇C++11與C++14技術的42個具體作法」

包括前兩本 effective C++ 跟 more effective C++,其實這已經是作者第三本關於 C++ 的書了,我真的滿好奇作者哪來對 C++ 這樣無比熱情,因為我已經很久很久沒有寫 C++ 了,有關底層的東西大部分還是用C,雖然有時候遇到沒有STL 支援的資料結構還是會哀一下,其他程式大多用Python 來寫;寫最多 C++ 的地方大概是 leetcode XD,想練演算法又想貪圖 C++ STL 提供的好處;大型 C++ 的譔寫經驗好像也沒多少,所以說我到底為什麼要看這本書呢……(思

扯遠了,先拉回來。

總而言之,C++ 在 11 跟 14 加入了許多新的語法和功能,這本 Effective Modern C++ 包含42個C++ 的使用項目,分佈在下面7個主題當中:
  • Deducing Types:C++ 的template 是如何推導型別 
  • auto:何時該用 auto ,何時又會出錯 
  • Moving to Modern C++:C++ 11,14 引入的新的寫法 = deleted, = override, 自動產生的物件方法
  • Smart Pointers:推薦使用smart pointer 代替 raw pointer ,以及 smart pointer 背後的實作 
  • Rvalue References, Move Semantics, and Perfect Forwarding:C++ 右值的 move, forward 的使用。 
  • Lambda Expressions:如何正確使用 C++ lambda 語法 
  • The Concurrency API:C++ 提供的 thread 跟 future 要在哪些情況才能正確使用 
  • Miscellaneous:其他兩個,介紹 emplace 何時要用 copy-by-value 
我是覺得到了 concurrency API 就已經看不太懂,平常大概也不會用到這樣,不然請大家回想一下你上次用 C++ 寫非同步的程式是什麼時候XD,但前面幾章就還看得滿有感覺的。

整體來說,C++ 從開始發跡到 C++11, 14,零零總總經歷各種不同的設計,無論是文法上或執行效率的考量,新增了很多全新的建議寫法或者關鍵字,每個關鍵字的背後可能都是一段故事,就例如存在已久的 typename :
http://feihu.me/blog/2014/the-origin-and-usage-of-typename/

書裡每個項目都包含從C++98或 C++11 開始到C++14最新的設計範例,作者還會告訴你為什麼C++11和C++14要這樣設計這些標準,哪些用法會在造成不預期的結果,或者直接了當的編譯錯誤,我認為,學習 C++ 而不去了解這些故事,等於是錯過一段精彩的設計思辯,非常可惜。

所以,還是回到那些話:學習C/C++的問題並不是學不會什麼生猛功能,而是要在各種實作的方法中學習:「哪些方法是比較<適合>的方法,避免哪些有問題的寫法,比較好的方法和概念是什麼?以及為何如此」

還在感嘆自己不懂C++ 11 跟C++ 14?趕快到書店買本 effective modern C++ 吧

不過告訴你一個悲慘的事實,今年C++又要推出更新的C++17了,希望今年Scott Meyers 也能再出本新書(More effective modern C++ (誤))幫大家指點迷津。

末語只能說:人生很難,可是C++,更難

2017年4月8日 星期六

Makefile header 檔的相依性檢查

Makefile 使用 make depend 進行相依性檢查
在寫Makefile 的時候,一般的規則是這樣的:
Target: Dependency
  Command (Makefile文件是寫 recipe,不過我這邊就寫command)
如果是C 程式,通常也會把 header 檔寫在 dependency 內,否則header 檔改了結果程式沒有重新編譯就奇怪了,如果每次改了header 都要 make -B 也不是辦法。
project 長大的時候,手填 header dependency 變得愈來愈不可行,特別是Makefile 大多是寫 wildcard match,例如這樣把object files 都填入變數 OBJS 之後,直接用代換規則將 .c 編譯成 .o:
SRCS = file1.c file2.c
OBJS = $(SRCS: .c=.o)

target: $(OBJS)
  $(CC) $(LDFLAGS) -o $@ $^

%.o: %.c
  $(CC) -c $(CFLAGS) -o $@ $<
在這裡翻譯了這篇文章,裡面給出一個針對大型專案完整的解決方法,重要的是它有把為何這麼寫的理由講出來:
http://make.mad-scientist.net/papers/advanced-auto-dependency-generation/

最簡單的方法,是在Makefile 裡面加上一個depend 的目標,在這個目標利用一些分析工具,例如makedepend建立 dependency,但這樣等於是把 make depend 跟真正的編譯分開了,缺點有兩個,一是需要使用者下make depend 才會重建 dependency,第二是如果有子資料夾也要依序下 make depend,我們需要更好的方法。

首先我們可以利用 makefile 的include 功能,直接 include 一個含有 dependency 的makefile ,把所有source file 設為 include file 的dependency,這樣只要有source 檔更新,make 時就會自動更新dependency到最新,完全不用使用者介入;但這樣也有缺點,只要有檔案更新就要更新的dependency,我們可以做得更好。

首先是 gnu make 推薦的方法:
https://www.gnu.org/software/make/manual/html_node/Automatic-Prerequisites.html
對每一個原始碼檔,產生一個.d 的相依性資訊
%.d: %.c
  @set -e; \
  rm -f $@; \
  $(CC) -M $(CPPFLAGS) $< > $@.Td; \
  sed 's,\($*\)\.o[ :]*,\1.o $@ : ,g' < $@.Td > $@; \
  rm -f $@.Td
先開 set -e 設定只要後面的command 出問題就直接結束,然後把 name.d 檔案刪掉;接著使用gcc 的 -M 參數(或者用 -MM ,如果不想要產生的dependency 包含system library的header),會讀入 name.c 之後,產生如下的dependency,寫到 name.d.Td 檔案中。
name.o: name.c aaa.h
之後用sed將上想 gcc -M 產生的內容,加上name.d 這個target:
name.o name.d: name.c aaa.h
對每個.c 檔都產生過 .d 檔之後,就能直接include所有.d 檔案了。
include $(sources: .c=.d)

因為 .d 的dependency 包括對應的 .c 檔,這樣只要.c 檔更新了,makefile 也會重build .d 檔,保持相依資訊在最新,同時只更新需要的 .d ,不會浪費build 的時間。
這個做法有幾個問題,首先是re-invocation 的問題,使用include的問題在於Makefile 本身的設計,因為include 可能帶入新的變數定義,目標等等,一但include 的目標有更新,它就會強制重跑一次本體的Makefile (參考這一篇:http://make.mad-scientist.net/constructed-include-files/ ),這在大型的專案上會帶來可觀的成本;更嚴重的是,如果我們把 .h 檔給刪除或更名,在編譯的時候會出現錯誤:
make: *** No rule to make target 'name.h', needed by 'name.d'. Stop.
這是因為name.d 相依於 .h ,.h 已經不存在而且又沒有產生 .h 的rule,Makefile 就會回傳錯誤;雖然改 .h 的狀況不常見,一但遇到就只能手動刪掉所有 .d 檔重新產生。

為了解決上述兩個問題,首先是Makefile 每次都會重新make 的問題,問題是這樣:如果有個source 更新了要重新編譯,那我們知不知道新的dependency 也沒差--反正它鐵定要重編譯的,該做的是為下一次的編譯產生新的 dependency 資訊;所以我們可以把產生 .d 檔這步,移到編譯 .c 檔的時候,大略如下:
OBJS = $(SRCS: .c=.o)
%.o : %.c
  # 產生 .d 檔的位置
  $(CC) -o $@ $<
include $(SRCS:.c=.d)
第二個問題比較棘手,這次用的招式是:Makefile 中如果有目標但沒有command 或dependency,這個目標又不是個已存在的檔案,那Makefile 無論command有沒有執行,會預設這個目標已經「被更新到最新」,注意它是有更新的,所以相依於這個目標的目標,也會依序更新下去。
http://www.gnu.org/software/make/manual/html_node/Force-Targets.html
例如下面這個例子,因為FORCE 每次執行都會被更新,所以clean 也一定會更新而執行
clean: FORCE
  rm $(objects)
FORCE:
所以這裡用的技巧就是,把那團相依的.h 檔變成無dependency/command 的目標,產生.Td之後,下面我是分成多行的結果,實際上可以寫得緊密一點,所做的工作包括:用 sed 依序移除comment;移除 : 前的target;移除行尾接下一行的反斜線;移除空白行;把行尾變成 : ,這樣本來的dependency 通通變成目標了。
  cp $*.Td $*.d; \
  sed -e 's/#.*//' \
  -e 's/^[^:]*: *//' \
  -e 's/ *\\$$//' \
  -e '/^$$/ d' \
  -e 's/$$/ :/' < $*.Td >> $*.d; \
  rm -f $*.Td
最後的問題是,如果我們移除 .d 檔, .c .h 檔又沒有更新則Makefile 也不會重新產生 .d 檔,因為 .d 檔並不是編譯時相依的target;但 .d 檔又不能是個真的target ,否則又有老問題:include 的時候它會產生 .d 檔,然後整個Makefile 會重跑一次;這裡的解法是把 .d 加到 .o 的dependency ,然後加一個空的target,這樣一來,.d 檔如果存在,因為commands 是空的所以什麼事都不做;如果 .d 被刪除,在make 時 .o 會觸發 .d 的更新,在空的target 更新之後, .o 也跟著更新的時候,一併產生全新的 .d 檔。
%.o: %.c %.d
  command
%.d:
最後是一些針對 dependency file 的處理,完整的Makefile 會長這個樣子:
DEPDIR = .depend
DEPFLAGS = -MT $@ -MMD -MP -MF $(DEPDIR)/$*.Td
POSTCOMPILE = mv -f $(DEPDIR)/$*.Td $(DEPDIR)/$*.d

%.o : %.c $(DEPDIR)/%.d
  $(CC) $(DEPFLAGS) $(CFLAGS) -c $<
  $(POSTCOMPILE)

$(DEPDIR)/%.d: ;
.PRECIOUS: $(DEPDIR)/%.d
include $(patsubst %,$(DEPDIR)/%.d,$(basename $(SRCS)))
第一段定義depend file 的存取地點,然後定義 DEPFLAGS,利用編譯時插入 DEPFLAGS 把編譯跟產生 dependency 一併做完;相關的 flags 都是 -M 開頭,可參考:
https://gcc.gnu.org/onlinedocs/gcc-5.2.0/gcc/Preprocessor-Options.html
  • -MT 定義產生出來的目標名稱,預設是 source 檔的suffix 換成 .o 後綴,並去掉前綴的任何路徑,例如 -MT www 則生成的相依資訊就變成 www: name.h,所以這個選項不一定要加。
  • -MM or -M 要求產生 dependency 資訊
  • -MP 直接幫忙對 header file 產生空的 dependency target (顯然gcc 開發者有注意到 .h 並非目標產生的問題),上面提到那一大串 sed ,如果是用 gcc 加上這個選項就不需要了
  • -MF 設定輸出到的檔案,相當於 redirect >
POSTCOMPILE 則把暫時的dependency file .Td 改名為.d,如果沒有要對 .Td 做什麼,拿掉這行,指定 -MF 直接寫到 .d 檔也是不錯的選擇。

第二段在.o 的dependency 加上 .d,command 編譯 .o 檔,同時gcc 產生.d 檔。
第三段寫入空的 .d 檔目標,以便處理 .d 檔被刪掉的狀況,.precious 讓 .d 檔在Makefile 當掉或被砍掉的時候不會被刪掉;最後 include 產生出來的 .d 檔。

大概的解法就是這樣,其實,如果project 很小的話,根本就不用這麼大費周章,像下面這個解法,直接把所有SRC送給gcc 產生dependency ,寫到 .depend 檔案,然後每次都include .depend,對 99.9%的project 來說應該都足夠了:
http://stackoverflow.com/questions/2394609/makefile-header-dependencies

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