天天看點

IFDS論文算法精解:應用于污點分析的例子

這篇文章的前文為論文解讀: IFDS開山之作:Precise Interprocedual Dataflow Analysis via Graph Reachability

這裡文章接上文,以一個污點分析的例子來說明IFDS論文中的Tabulation算法(IFDS Solver求解器)是怎麼工作的。

1.

這裡給定兩個函數,它們之間有一條從source到sink的污染路徑

IFDS論文算法精解:應用于污點分析的例子

2.

最終的有效的污點傳播相關的邊如下所示;

其中紅色邊對應于FlowFunction,也叫TransferFunction或者TransferRelation等術語。表示資料流經過一條語句後的流向。綠色邊PathEdge為論文中描述的PathEdge,藍色SummaryEdge為摘要邊,避免重複計算。

IFDS論文算法精解:應用于污點分析的例子

3.

整個算法就是個動态規劃算法,不斷地累積Same Level(同一函數内的) PathEdge;同時把已經一個函數内傳播的資料流計算的結果用call-to-return上的SummaryEdge記錄下來,防止重複計算。

整個算法就是計算圖的傳遞閉包:

如果圖上a -> b, 且b -> c,那麼a -> c

IFDS論文算法精解:應用于污點分析的例子

4.

IFDS論文算法精解:應用于污點分析的例子

5

IFDS論文算法精解:應用于污點分析的例子

6.

IFDS論文算法精解:應用于污點分析的例子

7.

IFDS論文算法精解:應用于污點分析的例子

8.

IFDS論文算法精解:應用于污點分析的例子

9.

IFDS論文算法精解:應用于污點分析的例子

10.

IFDS論文算法精解:應用于污點分析的例子

11.

IFDS論文算法精解:應用于污點分析的例子

12.

IFDS論文算法精解:應用于污點分析的例子

13.

IFDS論文算法精解:應用于污點分析的例子

14.

IFDS論文算法精解:應用于污點分析的例子

15.

IFDS論文算法精解:應用于污點分析的例子

16

IFDS論文算法精解:應用于污點分析的例子

17.

IFDS論文算法精解:應用于污點分析的例子

18.

IFDS論文算法精解:應用于污點分析的例子

19.

IFDS論文算法精解:應用于污點分析的例子

20.

IFDS論文算法精解:應用于污點分析的例子

21.

IFDS論文算法精解:應用于污點分析的例子

22.

IFDS論文算法精解:應用于污點分析的例子

23.

IFDS論文算法精解:應用于污點分析的例子

24.

IFDS論文算法精解:應用于污點分析的例子

25.

IFDS論文算法精解:應用于污點分析的例子

26.

IFDS論文算法精解:應用于污點分析的例子

27.

IFDS論文算法精解:應用于污點分析的例子

28.

IFDS論文算法精解:應用于污點分析的例子

29.

IFDS論文算法精解:應用于污點分析的例子

30.

IFDS論文算法精解:應用于污點分析的例子

31.

IFDS論文算法精解:應用于污點分析的例子