靜態程式分析（一）—— 大綱思維導圖與內容介紹
本系列文章為，基於奧爾胡斯大學的Anders Møller 和 Michael I. Schwartzbach兩位教授於2022年2月1日所出版的《static program analysis》，的讀書筆記
關注微信公眾號 信安科研人，傳送「靜態分析1」獲取書籍英文原版pdf
目錄
三 TIP語言 tiny imperative programming language
一 大綱
關注公眾號信安科研人，傳送「靜態分析思維導圖」獲取導圖
二 靜態程式分析簡介
2.1 靜態分析的應用
- 程式優化分析：優化編譯器（包括直譯器中的即時編譯器），以便生成有效的程式碼。
- 程式正確性分析：設計用於檢測程式錯誤（或驗證是否存在錯誤）
- 程式開發分析：舉個例子，第117行可能呼叫哪些函數，或者相反，函數f可能從何處呼叫？函數內聯和其他重構依賴於這些資訊。
2.2 靜態分析是一種近似的結果，萊斯定理
一言以蔽之：「程式測試可以用來顯示錯誤的存在，但永遠不能顯示它們的不存在」。這一節的標題，說白了就是靜態分析與萊斯定理之間的關係，
具體的可以看熊英飛老師對這部分的講解：
就是說，萊斯定理描述了由圖靈機造出的程式的某種屬性是不可確定的，那麼，轉換到以分析安全漏洞的程式靜態分析的目的，就是確定程式或者屬性是否是「具備缺陷的」。（注意，萊斯定理限定為圖靈機做出的程式，非圖靈機是不適用的，什麼是圖靈機大家可以自行查閱）
然而，按照萊斯定理，我們無法判斷這個程式是否一定是具備缺陷的，使用靜態分析或理想的分析器，只能找到一個近似的判斷。這種判斷可以說是無限接近於理想分析。
例如，我要找到一個程式的所有緩衝區漏洞，這需要構建恰好所有符合觸發這個漏洞的測試用例，這可能嗎？我能找到所有觸發這個漏洞的用例嗎？答案是不能。
這就是我們這一節所謂的「靜態分析是一種近似的結果」，因此靜態分析就是儘可能的向著理想值去分析，對於安全領域就是儘可能找到更多的漏洞，但是我找不盡這個程式的漏洞。
如果還沒有理解，可以看下面倆橫線中的這個例子：
近似答案可能有助於發現程式中的錯誤，視為程式驗證的一種弱形式。例如，使用C語言中的指標進行程式設計到處都是危險，例如空的取消參照、指標懸空、記憶體洩露和意外別名。普通編譯器對指標錯誤幾乎沒有保護作用。考慮以下可能執行各種錯誤的小程式：
標準編譯器工具（如GCC-wall）不會檢測到此程式中的錯誤。通過軟體測試查詢錯誤可能會遺漏錯誤（對於此程式，除非我們碰巧有一個正好使用42個引數執行程式的測試用例，否則不會遇到錯誤）。然而，如果對有關空值、指標目標和分支條件的問題有近似的答案，那麼上述許多錯誤都可以靜態地捕獲，而無需實際執行程式。
三 TIP語言 tiny imperative programming language
在接下來的章節中，該書使用一種稱為 T(iny) I(mperative) P(rogramming) 的小型指令式程式設計語言。該語言具有最小型的語法，但包含使靜態分析變得有趣和具有挑戰性的所有指令結構。
這種自定義的語言表述對靜態分析工作有著啟示作用。原書是先說語法再講例子，這裡我先講例子再講語法。
3.1 TIP語言範例
原文給出了三種常見的函數程式，可以看到，基本上和C語言差不太多。除了幾個自定義的語法如「var」是定義引數，「alloc」是給指標分配記憶體。
迴圈程式：
遞迴程式：
超級複雜的程式：
3.2 TIP的語法
TIP是一個
下面來介紹一下TIP
（1）參數列達：
定義Int表示所有整數，Id表示所有的變數。
對於表示式Exp：
上面些文字所想表達的是：exp為表示式，「|」為或，那麼意思就是，Exp可以為Int整數、Id引數、或者多個表示式之間的運算、或者是輸入（就是最後一行的input，可以從輸入流中讀取一個整數）。
（2）陳述 statement
可以看到TIP中的陳述與大部分程式語言的陳述基本相同，但是相當於是一種簡化的規則。陳述可以為 Id =Exp，也就是類似 a = a+b這種，也可以輸出一個表達，等等。
圖中那個問號以及中括號，代表可選擇的分支。
（3）函數 functions
函數宣告 F 包含函數名稱、參數列、區域性變數宣告、主體語句和返回表示式，其中，函數名稱和引數是識別符號，就像變數一樣。var 塊宣告了一組未初始化的區域性變數。
函數呼叫是一種額外的表示式:
太抽象了，舉個例子: Exp->a+a,b+b | X(a+a,b+b,...)
(4) 作為值進行呼叫的函數
函數還可以作為一級值：函數的名稱可以用作一種參照函數的變數，並且可以將此類函數值分配給普通變數，作為引數傳遞給函數，並從函數返回。
與簡單的函數呼叫不同，被呼叫的函數現在是一個計算為函數值的表示式。函數值使我們能夠說明物件導向語言中的方法和函數語言中的高階函數所面臨的主要挑戰。
在main函數中，inc函數作為引數傳遞給twice函數，該函數兩次呼叫給定函數（inc函數）。
（5）指標
如下圖：
第一個表示式在使用給定表示式的值初始化的堆中分配一個新單元，併產生一個指向該單元的指標。具體的例子如下：
第一行分配一個初始值為null的單元格，在第二行y指向變數x後，第三行將值42分配給第一行中分配的單元格（從而覆蓋null值），第四行通過兩個指標解除參照讀取該單元格的新值（也就是Stm 那一行的指標操作對應的就是z的操作）。
（6）記錄
記錄是欄位的集合，每個欄位都有一個名稱和一個值。建立記錄和讀取欄位值的語法如下:
舉個例子，第一行建立一個包含兩個欄位的記錄：一個名稱為 f，值為 1，另一個名稱為 g，值為 2。第二行讀取 f 欄位的值：
可以看到，從第5小節開始，就是針對物件導向類語言的語法描述。
類似常見的幾種程式語言，對欄位的賦值操作如下：
具體例子如下：
（7） 程式
TIP語言定義，程式只是一個個函數的集合：（也就是說一個函數或語句也能作為程式）
對於一個完整的程式，名為 main 的函數是啟動執行的函數。它的引數從輸入流的開頭按順序提供，它返回的值被附加到輸出流中。
以上，語法介紹完畢。
3.3 正規化
編寫程式時，豐富靈活的語法或許很有用，但在描述和實現靜態分析時，使用語法更簡單的語言通常更方便。因此，靜態分析有時通過將程式轉換為等價但語法更簡單的程式來規範化程式。一個特別有用的規範化是展平巢狀的指標表示式，這樣指標解除參照總是採用*Id的形式而不是更一般的*Exp，類似地，函數呼叫總是採用形式 Id（Id，…，Id）而不是Exp（Exp，…，Exp）。它還可以用於展平算術表示式、直接呼叫的引數、分支條件和返回表示式。
舉個例子：
正規化化後變成：
上圖的規律就是：一個陳述只包含一個操作。