[發明專利]數據流分析方法和裝置

有效

• 申請號: 201310548222.2
• 申請日: 2013-11-07
• 公開（公告）號: CN103809966A
• 公開（公告）日: 2014-05-21
• 發明（設計）人: J·杜比;S·A·瓜爾涅里;M·皮斯托亞;O·特里普
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 北京市中咨律師事務所 11247
• 代理人: 于靜;張亞非

1.一種數據流分析方法，包括：

使用適合于程序污染分析的程序數據流模型，利用基于所述程序的堆模型從污染源到所述堆中的實體來跟蹤信息，其中執行所述跟蹤以便所述信息與污染傳播相關，并且針對所述堆中的所述實體以字段敏感的方式執行所述跟蹤；以及

基于所述跟蹤的輸出，執行數據流分析以便確定從所述污染源通過數據流路徑到使用所述污染的匯的污染流。

2.根據權利要求1的方法，其中跟蹤信息進一步包括使用指針分析模型執行字段敏感分析，以便將所述堆中的抽象對象的字段彼此區分開并將所述堆中的不同抽象對象的字段彼此區分開。

3.根據權利要求2的方法，其中所述字段敏感分析區分不同抽象對象的字段指針鍵，即使當此類字段指針鍵表示具有相同名稱的字段時也是如此。

4.根據權利要求2的方法，其中所述指針分析模型包括指向圖。

5.根據權利要求2的方法，還包括通過分析所述程序確定所述數據流模型，并且通過分析所述程序確定所述指針分析模型。

6.根據權利要求2的方法，其中使用指針分析模型執行字段敏感分析進一步包括創建堆圖，所述堆圖包括具有所述程序中的環境和堆指針的第一集合與具有參與所述指針分析模型的所述抽象對象的第二集合的交集，并且還包括連接所述第一和第二集合的元素的邊集合。

7.根據權利要求6的方法，其中具有所述程序中的環境和堆指針的第一集合包括所述堆中的局部變量和引用所述堆中的對象的字段。

8.根據權利要求6的方法，其中跟蹤信息進一步包括：

確定污染流入給定訪問路徑，其中每個訪問路徑是將變量與字段標識符集合相鏈接的對，并且其中可以評估訪問路徑以便產生在所述堆中分配的唯一對象；

確定與所述給定訪問路徑對應的滿足條件集合的所有訪問路徑，所述確定所有訪問路徑的步驟使用所述堆圖；以及

輸出所確定的滿足所述條件集合的訪問路徑。

9.根據權利要求8的方法，其中使用特定環境和給定堆在所述程序的特定具體狀態下執行訪問路徑評估，以便在所述給定堆中產生所述唯一對象。

10.根據權利要求8的方法，其中確定污染流入給定訪問路徑進一步包括使用所述程序中的函數的關系摘要映射來確定污染流入所述給定訪問路徑。

11.根據權利要求10的方法，其中確定污染流入給定訪問路徑進一步包括針對所述程序中被首次分析的函數，確定將所述函數的一個或多個輸入參數映射到所述函數的一個或多個返回值的關系摘要。

12.根據權利要求8的方法，其中所述條件集合包括：

所有訪問路徑中的所述訪問路徑以局部變量為根；

所述局部變量屬于同一方法；以及

所有所述訪問路徑均與所述給定訪問路徑混淆。

13.根據權利要求12的方法，其中所述條件集合進一步包括：可以將所有所述訪問路徑截斷為特定長度。

14.根據權利要求1的方法，其中以針對字段而言還為流不敏感的方式執行所述跟蹤信息的步驟，其中響應于在兩個不同程序點為所述堆中的對象o的字段f分配值v和值w，所述字段f被視為指向值集合{v,w}。

15.根據權利要求14的方法，其中所述跟蹤信息進一步包括構建調用圖和指向圖，并且其中當構建至少所述調用圖和指向圖時，執行流不敏感性。

16.根據權利要求1的方法，還包括輸出通過執行所述數據流分析而確定為被污染的所述數據流路徑的指示。

17.一種數據流分析裝置，包括：

被配置為使用適合于程序污染分析的程序數據流模型，利用基于所述程序的堆模型從污染源到所述堆中的實體來跟蹤信息的模塊，其中執行所述跟蹤以便所述信息與污染傳播相關，并且針對所述堆中的所述實體以字段敏感的方式執行所述跟蹤；以及

被配置為基于所述跟蹤的輸出，執行數據流分析以便確定從所述污染源通過數據流路徑到使用所述污染的匯的污染流的模塊。

18.根據權利要求17的裝置，其中被配置為跟蹤信息的模塊進一步包括被配置為使用指針分析模型執行字段敏感分析，以便將所述堆中的抽象對象的字段彼此區分開并將所述堆中的不同抽象對象的字段彼此區分開的模塊。