這篇文章的前文為論文解讀: IFDS開山之作:Precise Interprocedual Dataflow Analysis via Graph Reachability
這裡文章接上文,以一個污點分析的例子來說明IFDS論文中的Tabulation算法(IFDS Solver求解器)是怎麼工作的。
1.
這裡給定兩個函數,它們之間有一條從source到sink的污染路徑
2.
最終的有效的污點傳播相關的邊如下所示;
其中紅色邊對應于FlowFunction,也叫TransferFunction或者TransferRelation等術語。表示資料流經過一條語句後的流向。綠色邊PathEdge為論文中描述的PathEdge,藍色SummaryEdge為摘要邊,避免重複計算。
3.
整個算法就是個動态規劃算法,不斷地累積Same Level(同一函數内的) PathEdge;同時把已經一個函數内傳播的資料流計算的結果用call-to-return上的SummaryEdge記錄下來,防止重複計算。
整個算法就是計算圖的傳遞閉包:
如果圖上a -> b, 且b -> c,那麼a -> c
4.
5
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.