『壹』 【課程筆記】南大軟體分析課程4——數據流分析基礎（課時5/6）
關於這一節 zcc 的筆記已經夠完美了，我就直接在他基礎上記錄了。
上節課是介紹了3種數據流分析迭代演算法，本節課將從數學理論的角度來討論數據流分析，加深對數據流分析演算法的理解。
本質 ：常見的數據流迭代演算法，目的是通過迭代計算，最終得到一個穩定的不變的解。
定義1 ：給定有k個節點（基本塊）的CFG，迭代演算法就是在每次迭代時，更新每個節點n的OUT[n]。
定義2 ：設數據流分析的值域是V，可定義一個 k-元組 ： (OUT[n 1 ], OUT[n 2 ], ... , OUT[n k ])。是集合 (V 1 V 2 ... V k ) （冪集，記為V k ）的一個元素，表示每次迭代後k個節點整體的值。
定義3 ：每一次迭代可看作是V k 映射到新的V k ，通過轉換規則和控制流來映射，記作函數F：V k V k 。
迭代演算法本質 ：通過不斷迭代，直到相鄰兩次迭代的 k-元組 值一樣，演算法結束。
不動點 ：當X i = F(X i )時，就是不動點。
問題 ：
定義 ：給定偏序集(P, )， 是集合P上的二元關系，若滿足以下性質則為偏序集：
例子 ：
定義 ：給定偏序集(P, )，且有P的子集S⊆P：
最小上界 ：least upper bound（lub 或者稱為join），用⊔S表示。上確界？
定義：對於子集S的任何一個上界u，均有⊔S⊑u。
最大下界 ：greatest lower bound（glb 或者稱為meet），用⊓S表示。下確界？
定義：對於子集S的任何一個下界l，均有l⊑⊓S。
若S只包含兩個元素，a、b（S = {a, b}）那麼上界可以表示為a⊔b，下界可以表示為a⊓b。
都是基於上下確界來定義的。
定義 ：給定一個偏序集(P,⊑)，∀a,b∈P，如果存在a⊔b和a⊓b，那麼就稱該偏序集為格。偏序集中的 任意兩個元素 構成的集合均 存在最小上界和最大下界 ，那麼該偏序集就是格。
例子 ：
定義 ：給定一個偏序集(P,⊑)，∀a,b∈P：
當且僅當a⊔b存在（上確界），該偏序集叫做 join semilatice；
當且僅當a⊓b存在（下確界），該偏序集叫做 meet semilatice
定義 ：對於格點 (S, ) （前提是格點）的任意子集S，⊔ S 上確界和⊓S下確界都存在，則為全格complete lattice。
例子 ：
符號 ： = P ，叫做top； = P，叫做bottom。
性質 ：有窮的格點必然是complete lattice。全格一定有窮嗎？ 不一定，如實數界[0, 1]。
定義 ：給定一組格，L 1 =(P 1 , 1 )，L 2 =(P 2 , 2 )，... ，L n =(P n , n )，都有上確界 i 和下確界 i ，則定義格點積 L n = (P, )：
性質 ：格點積也是格點；格點都是全格，則格點積也是全格。
數據流分析框架(D, L, F) ：
數據流分析可以看做是 迭代演算法 對 格點 利用 轉換規則 和 meet/join操作 。
目標問題：迭代演算法一定會停止（到達不動點）嗎？
（1）單調性
定義 ：函數f: L L，滿足∀x,y∈L，x⊑y⇒f(x)⊑f(y)，則為單調的。
（2）不動點理論
定義 ：給定一個 完全lattice(L,⊑) ，如果f:L→L是 單調 的，並且 L有限
那麼我們能得到最小不動點，通過迭代：f(⊥),f(f(⊥)),...,f k (⊥)直到找到最小的一個不動點。
同理 我們能得到最大不動點，通過迭代：f(⊤),f(f(⊤)),...,fk(⊤)直到找到最大的一個不動點。
（3）證明
不動點的存在性；
最小不動點證明。
問題 ：我們如何在理論上證明 迭代演算法有解 、 有最優解 、 何時到達不動點 ？那就是將迭代演算法轉化為 不動點理論 。因為不動點理論已經證明了，單調、有限的完全lattice，存在不動點，且從⊤開始能找到最大不動點，從⊥開始能找到最小不動點。
目標 ：證明迭代演算法是一個 完全lattice(L, ) ，是 有限 的， 單調 的。
根據第5小節，迭代演算法每個 節點（基本塊）的值域 相當於一個 lattice ，每次迭代的 k個基本塊的值域 就是一個 k-元組 。k-元組可看作 lattice積 ，根據格點積性質：若L k 中每一個lattice都是完全的，則L k 也是 完全 的。
迭代演算法中，值域是0/1，是有限的，則lattice有限，則L k 也有限。
函數F：BB中轉換函數f i ：L → L + BB分支之間的控制流影響（匯聚是join / meet 操作，分叉是拷貝操作）。
總結 ：迭代演算法是完全lattice，且是有限、單調的，所以一定有解、有最優解。
定義 ： lattice高度 —從lattice的top到bottom之間最長的路徑。
最壞情況迭代次數 ：設有n個塊，每次迭代只有1個BB的OUT/IN值的其中1位發生變化（則從top→bottom這1位都變化），則最多迭 ( n × h ) 次。
說明 ：may 和 must 分析演算法都是從不安全到安全（是否安全取決於safe-aprroximate過程），從准確到不準確。
以 Reaching Definitions分析為例：
以available expressions分析為例：
迭代演算法轉化到lattice上，may/must分析分別初始化為最小值 和最大值 ，最後求最小上界/最大下界。
目的 ：MOP（meet-over-all-paths）衡量迭代演算法的精度。
定義 ：最終將所有的路徑一起來進行join/meet操作。
路徑P = 在cfg圖上從entry到基本塊s i 的一條路徑（P = Entry → s 1 → s 2 → ... → s~i ）。
路徑P上的轉移函數F p ：該路徑上所有語句的轉移函數的組合f s1 ，f s2 ，... ，f si-1 ，從而構成F P 。
MOP ：從entry到s i 所有路徑的F P 的meet操作。本質—求這些值的最小上界/最大下界。
MOP准確性 ：有些路徑不會被執行，所以不準確；若路徑包含循環，或者路徑爆炸，所以實操性不高，只能作為理論的一種衡量方式。
對於以上的CFG，抽象出itter和MOP公式。
證明 ：
結論 ：所以，MOP更准確。若F滿足分配律，則迭代演算法和MOP精確度一樣 F ( x ⊔ y )= F ( x )⊔ F ( y )。一般，對於控制流的join/meet，是進行集合的交或並操作，則滿足分配律。
問題描述 ：在程序點p處的變數x，判斷x是否一定指向常量值。
類別 ： must分析 ，因為要考慮經過p點所有路徑上，x的值必須都一樣，才算作一定指向常量。
表示 ：CFG每個節點的OUT是pair（x, v）的集合，表示變數x是否指向常數v。
（1）D：forward更直觀
（2）L：lattice
變數值域 ：所有實數。must分析，所以 是UNDEF未定義（unsafe）， 是NAC非常量（safe）。
meet操作 ：must分析， 。在每個路徑匯聚點PC，對流入的所有變數進行meet操作，但並非常見的交和並，所以 不滿足分配律 。
（3） F轉換函數
OUT[s] = gen U (IN[s] - {(x, _})
輸出 = BB中新被賦值的 U 輸入 - BB中相關變數值已經不是f常量的部分。
對所有的賦值語句進行分析（不是賦值語句則不管，用val(x)表示x指向的值）：
（4） 性質 ：不滿足分配律
可以發現，MOP更准確。F(X Y) F(X) F(Y)，但是是單調的。
本質 ：對迭代演算法進行優化，採用隊列來存儲需要處理的基本塊，減少大量的冗餘的計算。
軟體分析——數據流分析2
『貳』 數據流是什麼怎麼弄
您好，數據流計算機
【解釋】： 由數據來驅動操作的電子計算機。機內所存儲的程序指令不需順序執行，當所需的操作數據完備時就立即執行。當多個操作同時滿足條件時，它們可並行執行而不受程序指令順序的限制，從而大大提高了計算機的運行速度。
1、確定系統的輸入輸出
由於系統究竟包括哪些功能可能一時難於弄清楚，可使范圍盡量大一些，把可能有的內容全部都包括進去。此時，應該向用戶了解「系統從外界接受什麼數據」、「系統向外界送出什麼數據」等信息，然後，根據用戶的答復畫出數據流圖的外圍。
2、由外向里畫系統的頂層數據流圖
首先，將系統的輸人數據和輸出數據用一連串的加工連接起來。在數據流的值發生變化的地方就是一個加工。接著，給各個加工命名。然後，給加工之間的數據命名。最後，給文件命名。
3、自頂向下逐層分解，繪出分層數據流圖
對於大型的系統，為了控制復雜性，便於理解，需要採用自頂向下逐層分解的方法進行，即用分層的方法將一個數據流圖分解成幾個數據流圖來分別表示。