數據流分析方法和裝置製造方法

2023-05-26 06:19:16

數據流分析方法和裝置製造方法
【專利摘要】本發明涉及一種數據流分析方法和裝置。公開一種方法，所述方法包括：使用適合於程序汙染分析的程序數據流模型，利用基於所述程序的堆模型從汙染源到所述堆中的實體來跟蹤信息。執行所述跟蹤以便所述信息與汙染傳播相關，並且針對所述堆中的所述實體以欄位敏感的方式執行所述跟蹤。所述方法包括：基於所述跟蹤的輸出，執行數據流分析以便確定從所述汙染源通過數據流路逕到使用所述汙染的匯的汙染流。
【專利說明】數據流分析方法和裝置
【技術領域】
[0001]本發明一般地涉及程序代碼的靜態分析，更具體地說，涉及數據流分析。
【背景技術】
[0002]本節旨在為下面公開的本發明提供背景或上下文。此處的描述可以包括概念，這些概念可以被貫徹，但不一定是先前構想、實現或描述的概念。因此，除非在此另外明確指明，否則本節中描述的內容不是本申請中的描述的現有技術，並且不認為通過包括在本節中而成為現有技術。
[0003]汙染分析包括搜索從不可信輸入點(源)到敏感消費者(匯(sink))的數據流。在靜態版本的汙染分析中，檢查程序而不執行構成程序的代碼。相反，創建程序的模型。這種模型可以包括通常使用流圖表示的數據流，該流圖是在程序執行期間可能遍歷程序的所有路徑的表示。這些數據流是潛在的安全問題，除非每個數據流經過致使數據安全的操作(例如殺毒器)。給定調用圖G，靜態汙染分析算法典型地包括兩個階段:
[0004]I)遍歷G以便在代碼中查找源、匯和殺毒器:
[0005]?源是通過欄位讀取指令獲得的值，或者是從調用返回到某些方法(稱為源方法)的值；
[0006]?匯可以是 某些對象的欄位或者是給定方法(稱為匯方法)的參數；以及
[0007]?殺毒器只是方法。
[0008]2)從源開始執行過程間數據流分析，以便判定是否具有到達匯而未由殺毒器攔截的汙染流。該分析以源結構定義的變量為種子。即，欄位讀取指令和源方法使用汙染值設置種子，並且通過數據流分析遵循汙染值以便確定汙染流。
[0009]儘管這種分析是有利的，但這些常規分析仍然具有問題。可以出現的一個問題包括混淆(aliasing)，其中在一個實例中，多個對象的多個欄位引用同一值。混淆還可以涉及堆中的關係，即，同一對象的多個本地名稱。眾所周知，堆是程序用於動態存儲器分配的存儲器區域。就汙染分析而言，用於仿真正在運行的程序的模型還仿真該程序的堆。堆中的混淆將存在問題，因為如果具有多個本地名稱的對象被汙染，則所有的多個本地名稱也應該標記為被汙染。但是，許多汙染分析工具沒有考慮或者不能處理堆中的混淆。

【發明內容】

[0010]在一個示例性實施例中，公開一種方法，所述方法包括:使用適合於程序汙染分析的程序數據流模型，利用基於所述程序的堆模型從汙染源到所述堆中的實體來跟蹤信息。執行所述跟蹤以便所述信息與汙染傳播相關，並且針對所述堆中的所述實體以欄位敏感的方式執行所述跟蹤。所述方法包括:基於所述跟蹤的輸出，執行數據流分析以便確定從所述汙染源通過數據流路逕到使用所述汙染的匯的汙染流。
[0011]在另一示例性實施例中，一種裝置包括:被配置為使用適合於程序汙染分析的程序數據流模型，利用基於所述程序的堆模型從汙染源到所述堆中的實體來跟蹤信息的模塊，其中執行所述跟蹤以便所述信息與汙染傳播相關，並且針對所述堆中的所述實體以欄位敏感的方式執行所述跟蹤；以及被配置為基於所述跟蹤的輸出，執行數據流分析以便確定從所述汙染源通過數據流路逕到使用所述汙染的匯的汙染流的模塊。
【專利附圖】

【附圖說明】
[0012]圖1是示出跟蹤被汙染訪問路徑的代碼段；
[0013]圖2是沒有堆問題的代碼段；
[0014]圖3是具有堆問題的代碼段；
[0015]圖4是圖3的代碼段的堆圖的可視化；
[0016]圖5是根據本發明的示例性實施例的示例性邏輯流程圖的框圖，其示出示例性方法的操作、包含在計算機可讀存儲器中的電腦程式指令的執行結果和/或在硬體中實現的邏輯執行的功能；
[0017]圖6是根據本發明的示例性實施例的示例性邏輯流程圖的框圖，其示出圖5中的方框的示例性操作，並且進一步示出示例性方法、包含在計算機可讀存儲器中的電腦程式指令的執行結果和/或在硬體中實現的邏輯執行的功能；以及
[0018]圖7是適合於執行本發明的示例性實施例的系統的框圖。
【具體實施方式】
[0019]通過參考圖1-7描述此處的示例性實施例。具體地說，對圖5和6的某些方框的描述參考其它附圖。圖5是根據本發明的示例性實施例的示例性邏輯流程圖的框圖，其示出示例性方法的操作、包含在計算機可讀存儲器中的電腦程式指令的執行結果和/或在硬體中實現的邏輯執行的功能，圖6是圖5中的一個方框執行的操作的類似框圖。
[0020]首先，通過對程序進行靜態建模(S卩，不執行程序)，執行汙染分析以便確定被汙染數據流。可以執行汙染分析以便輸出通過程序的被汙染路徑集合。可以進一步執行汙染分析以便例如檢查被汙染路徑集合，並且例如通過判定任何被汙染路徑是否具有針對被汙染數據執行的正確操作(例如，在正確位置)，針對被汙染路徑執行額外分析以致使數據安全。這種額外分析將減少被汙染路徑的數量。
[0021]如上所述，無論是否執行汙染分析，必須以某種方式從汙染源到使用汙染的匯來跟蹤汙染。本公開的其餘部分假設已經創建(圖5的方框510)程序的數據流模型，該模型適合於汙染分析並且包含數據流路徑。此類數據流模型包括有向圖，例如調用圖或超圖。注意，方框515在下面描述。
[0022]堆中的實體和調用圖中的數據流之間具有關係。具體地說，堆中的實體(例如局部變量和引用對象的欄位)可能是數據流的一部分，因此可以傳遞被汙染信息。但是，因為堆中的混淆，其中混淆包括同一對象在堆中的多個本地名稱，除非以欄位敏感方式跟蹤和管理混淆，否則可能無法找到所有受影響的數據流。例如，變量P和r可以引用同一對象，但在典型的堆分析中，它們可以具有相同的本地名稱，因此汙染可能僅與變量之一關聯。
[0023]因此，在圖5的方框520中，使用堆模型從汙染源到堆中的實體(例如，局部變量和引用對象的欄位)來執行信息跟蹤。執行跟蹤以便信息與汙染傳播相關，並且以欄位敏感的方式執行跟蹤。本公開的下一部分提供有關該方框的其它詳細信息。[0024]一種處理汙染的方式是通過訪問路徑。為了發現易受攻擊的數據流路徑，汙染分析應維護程序的存儲不可信值的所有堆位置集合。一種執行該操作的單純方式是對整個堆(包括所有有利位置)進行顯式建模，然後在分析期間的每個點處跟蹤堆的哪些部分被汙染。通常，該解決方案極其昂貴，因此也不可擴展，例如0.Tripp、M-Pistoia, S.J.Fink、M.Sridharan 和 0.Weisman 的 TAJ:Effective Taint Analysis of Web Applications(TAJ:ffeb應用的有效汙染分析)(2009年ACM SIGPLAN程式語言設計和實現會議的會議記錄，2009年)中所述。此處的示例性解決方案使用堆的無存儲視圖(參見A.Deutsch的AStoreless Model of Aliasing and Its Abstractions Using Finite Representationsof Right-regular Equivalence Relations (使用右正則等價關係的有限表示的混淆及其抽象的無存儲模型)(1992年國際計算機語言會議的會議記錄，1992年))，該視圖不是顯式表示堆，而是僅跟蹤與汙染傳播相關的信息；即，哪些序列的局部變量和欄位解引用可能導致不可信數據。為了描述示例性分析如何跟蹤汙染，首先介紹如何在具體設置中應用無存儲表示:針對汙染分析問題採取標準具體語義，其中定義程序狀態和程序狀態下的表達式計算。使用以下語義域:
[0025]L∈ objects
[0026]V∈ Val=objects U {null}
[0027]pEnv=VarId — Val
[0028]h∈ Heap=objectsXFieldId — Val
[0029]o = ∈States=2obj0Cts X Env X Heap
[0030]其中objects表示動態分配的對象的無界集合,VarId和FieldId分別是局部變量和欄位標識符的集合。此外，e表示「是其元素」，U表示併集，一表示「映射到」，X表示笛卡爾乘積，它包括通過採取第一集合中的元素和第二集合中的元素獲得的所有對的集合:AXB={(a，b):a e A，b e B。因此，程序狀態σ維護被分配對象的集合L、將局部變量映射到值的環境P，以及從被分配對象的欄位到值的映射h。
[0031]如上所述，示例性分析執行的數據流分析基於「訪問路徑」的概念(參見S.Fink、E.Yahav> N.Dor、G.Ramalingam 和 Ε.Geay 的 Effective Typestate Verification in thePresence of Aliasing(當存在混淆時的有效類型狀態驗證)(ACM軟體測試和分析國際研討會，2006年)。形式上，訪問路徑是一個對〈V，>，其中V是局部變量，fI,..., fn是欄位標識符(它們標識對象中的欄位，其中欄位存儲對象的狀態)。使用環境P和堆h在具體狀態σ下計算訪問路徑〈^〈€1，...，^1?將產生滿足以下條件的唯一堆分配的對象ο:
[0032]
Bol.....011-O1 =p(v)ao2 = Λ (ο, , / I) λ...λ a = h (ο.,, fn)
[0033]使得ο, O1,...，οη e L，其中L是σ中的被分配對象的集合。此外，3表示「存在」，「.」表示「使得」，Λ表示「與」。如果不存在此類對象O，則計算結果失敗丄。
[0034]在狀態σ下計算為對象O的所有訪問路徑的集合是對象O的合理表示，因為訪問路徑之間的混淆變得顯式，因此可以以合理方式處理通過堆的流。遺憾的是，通常即使在具體設置中也不能保證該集合是有限的，這是由於堆中的循環所致(例如，遞歸結構和反向指針導致)。即使集合是有限的，深層嵌套的對象也可以產生非常長的鏈。[0035]這在示例性實施例中針對被跟蹤訪問路徑的長度強制界限k，以便可以處理靜態分析。然後對於長度大於k的訪問路徑，通過以特殊符號*替換其後綴(在前k個欄位標識符之後)，合理地接近(或放寬)訪問路徑。在具體狀態σ下計算放寬後的訪問路徑〈V，，fl，...，fk, *?將產生L中可從對象〈V，<fl,...，fk?通過(零個或多個)堆邊到達的所有對象。實際上，已經發現設置k=5非常適合。
[0036]訪問路徑是表示汙染流的自然方式。例如，考慮圖1中的程序段。第I行處的源語句產生種子訪問路徑〈P，ε>，其中ε表示空的欄位標識符序列(空的原因是document.URL最初未知，並且將被設置為種子)。注意，語句「var q= 」指示變量q被初始化為空集合。接下來，第3行處的賦值產生另一個被汙染訪問路徑〈!，ε>。第4行處的語句(寫入欄位f)導致出現第三訪問路徑<q，>其在第5行處使賦值到達匯欄位「location」，並且導致標記漏洞。
[0037]為了傳播被汙染訪問路徑，建議的示例性分析採用Reps-Horwitz-Sagiv (RHS)算法的新穎擴展。參見T.Reps、S.Horwitz和Μ.Sagiv 的Precise Interprocedural DataflowAnalysis via Graph Reachability (通過圖可達性進行精確的過程間數據流分析)(第22屆ACM SIGPLAN-SIGACT程式語言原理研討會的會議記錄，1995年)。RHS算法提供高度精確的靜態分析框架，以便將大量數據流問題轉變為圖可達性問題。具體地說，汙染傳播以源為種子。每次在指令中使用被汙染訪問路徑時，分析相應地汙染在該指令中定義的訪問路徑。
[0038]汙染傳播過程需要驅動，因為僅當汙染到達訪問路徑時才實例化訪問路徑，這使得該算法非常高效。該算法的另一個重要特性是算法對上下文敏感:每個方法可以採取多個汙染行為，具體取決於調用算法的上下文一精確度的關鍵要求。
[0039]此外，此處的示例性分析增強了 RHS，因為示例性分析可以處理涉及堆中的混淆關係(即，同一對象的多個本地名稱)的問題。原始RHS算法中沒有該特性，原始算法不適用於對涉及在不同過程中建立的混淆關係的問題進行建模。
[0040]首先，在沒有混淆問題的簡單實例中示出示例性算法如何工作，然後提供關於如何處理堆的討論。
[0041]關於基本汙染分析算法，如果沒有任何堆混淆問題，則汙染分析很簡單:可以使用標準Reps-Horwitz-Sagiv (RHS)求解器計算精確的滿足所有可行路徑的解決方案。參見上面引用的T.Reps等人的文章。在圖2中使用實例示出該分析如何工作。
[0042]第7行處的「document.URL」的讀取是汙染源，其生成被汙染訪問路徑 (例如，在該簡單實例中，為汙染分配P)。P的值流到第9行處的「id」的調用。對「id」的分析(行1-3)揭示該函數僅從其參數到其返回值傳播汙染，因此針對「id」函數建立關係摘要{X，ε}—〈ret，ε >(其中ret是表示方法的返回值的特權符號)，並且將該關係摘要傳播到「id」的調用方。注意，該關係摘要是模塊化的，因為針對函數確定關係摘要之後，可以針對函數的每個調用簡單地重用關係摘要。還應注意，該關係摘要是本發明的一個方面。將該摘要應用於第9行處的主方法將生成訪問路徑〈r，ε >被汙染的事實。
[0043]摘要{X，ε } —〈ret，ε >被稱為是關係的，因為如果程序中具有另一個「id」調用以便傳遞到「id」的參數未被汙染，則在這種情況下返回值完全不會被汙染。因此，當在被調用方處生成摘要並將其傳播到調用方時，僅當相關先決條件適用於調用方時才將摘要應用於該調用方。從這個意義上說，該分析是上下文敏感的:根據調用上下文執行汙染傳播。下面將介紹具有對「id」方法的兩個調用的實例一一個調用具有被汙染參數，另一個調用具有未被汙染參數。還應注意，關係摘要還提供欄位敏感性，因為關係摘要還根據上下文敏感性來修改欄位。
[0044]繼續圖2的實例，在第10行將變量r的值傳遞到「set」函數。「set」函數(行4-6)包含欄位寫入指令，該指令將汙染從其第一參數傳播到其第二參數的欄位f ;即，函數創建非空訪問路徑。在這種情況下，函數的關係摘要是{y，ε}—>。向「set」的調用方應用該摘要將添加<q，>被汙染的事實。這將為真，因為將關係摘要應用於「set (r，q) 」的調用語句將產生Ir，ε} — >。訪問路徑已經被確定為被汙染，但訪問路徑<q, >先前未被確定為被汙染。當分析結束時，將獲知訪問路徑〈P, ε >、和<q, <f?被汙染，這是精確的結果。
[0045]關於可以處理混淆的完整汙染分析算法，圖2中的程序是無混淆程序:同一堆位置從來沒有多個名稱。即，>是給定位置的唯一名稱。但是，假設某個其它變量指向同一位置；在這種情況下，上面的規則可能使我們漏掉變量的欄位f也被汙染的事實。例如，考慮圖3中的非常類似的程序中的變量q和s ;變量q和變量s均引用同一對象(對象g，其最初被設置為空集合)，因此由其中一個變量產生的任何汙染一定傳送到另一個變量。因此，示例性汙染分析算法擴展RHS算法，以便還根據在調用圖構造期間計算的指針分析模型考慮堆混淆。即，在圖5的方框510中，創建適合於汙染分析的程序數據流模型。該數據流模型例如可以是有向圖(例如調用圖或超圖)，並且將包含數據流路徑(例如其表示)。創建數據流模型還可以包括針對程序使用的變量計算指針分析模型，例如作為數據流模型的一部分或其附件(圖5的方框515)。指針分析模型(其可以是指向圖)是堆的數學表示，通常表示為二分圖，其中節點可以是兩種類型之一:實例鍵(表示對象抽象)和指針鍵(表示欄位標識符)。從實例鍵到指針鍵的邊表示以下事實:實例鍵表示的對象的類具有指針鍵表示的欄位標識符。從指針鍵到實例鍵的邊表示以下事實:在程序執行期間，指針鍵表示的欄位標識符可以指向實例鍵表示的對象。
[0046]作為圖5的方框520的一個實例，例如在圖5的方框525中示出從汙染源到實體來執行信息跟蹤，其中以欄位敏感的方式執行跟蹤。在方框525，執行指針分析模型的欄位敏感分析，以便將抽象對象的欄位彼此區分開，並將不同抽象對象的欄位彼此區分開。圖6是使用指針分析模型執行欄位敏感分析的一個實例的框圖。即，在另一示例性實施例中，為了解析混淆關係，構造指針分析模型的抽象，即「堆圖」。這在圖6的方框605中進行。堆圖是二分圖H=〈B U Δ，Χ>，其中B是程序中的環境和堆指針一即，局部變量和引用對象的欄位(例如，通過欄位指針鍵)的集合，Δ是參與指針分析解決方案的對象抽象的集合，X是圖中的邊集合。從指針P到抽象對象O的邊P — O表示欄位P可以指向對象O。從抽象對象O到欄位P的邊O — P表示O擁有欄位(例如，在這種情況下為欄位指針)Ρ。該抽象允許構造這種堆圖，因為抽象是欄位敏感的，意味著抽象將抽象對象的欄位彼此區分開以及將不同抽象對象的欄位彼此區分開。參見B.G.Ryder的Dimensions of Precision in ReferenceAnalysis of Object-Oriented Languages (面向對象的語言的引用分析中的精確度維度)(第12屆國際編譯器構造會議，2003年，特邀論文)。圖4示出圖3中的程序的堆圖的一種可視化。在圖4中，矩形內部具有「q」(作為實例)的矩形指示局部變量「q」的指針；三角形內部具有「g」(作為實例)的三角形指示欄位「g」的指針；以及圓形指示抽象對象。
[0047]在圖3的程序中，與圖2相比具有兩個更改。第一更改是對「id」的額外調用(第11行)，其定義變量S，第二更改是更複雜的「set」函數(行4-7)。首先按照如上所述繼續分析，針對〈P，ε >和查找汙染。
[0048]對「set」的調用示出堆問題。賦值「X.f=y」建立摘要{y, ε } — >，但這明顯不夠:「x.f」與「z.g.f」引用同一位置，並且分析需要捕獲此類汙染。有關欄位寫入語句的影響的合理推理需要查找與「set」的詞法範圍中的〈X，>混淆的訪問路徑集合(的保守近似)。原始RHS算法未對此進行處理。另一方面，本示例性分析發現〈X，>的混淆，如下所述。
[0049]每次汙染流入訪問路徑(圖6的方框610)時，本示例性分析執行在此稱為Aliases的函數以便確定局部混淆(例如，方框630)，然後繼續基於RHS的汙染傳播(圖5的方框530)。基於RHS的汙染傳播在上面引用的T.R印s等人的文章中描述。通過方框620和625示出圖6的方框610的一個實例。具體地說，在方框620中，針對程序中被首次分析的函數，確定將函數的輸入參數(多個)映射到函數的返回值(多個)的關係摘要。示例性關係摘要已經在上面描述，並且還在下面描述。在方框625中，使用一個/多個關係摘要以欄位敏感方式確定汙染流入給定訪問路徑。注意，針對那些已經具有關係摘要的函數，將跳過方框620。
[0050]針對以局部變量為根的給定訪問路徑，可以定義函數Aliases (方框630)，該函數返回滿足以下條件的所有訪問路徑:
[0051]I)訪問路徑以局部變量為根(方框635)。這相當於測試將isL0Cal(v)計算為true ο
[0052]2)這些局部變量屬於同一方法(方框640)。這相當於測試methodOf (v)=method0f(w)。
[0053]3)訪問路徑與給定訪問路徑混淆(方框650)。這相當於測試使用對函數(在此稱為PathTo)的兩個調用獲得的抽象對象集合具有非空交集。
[0054]除了三個條件(I) - (3)之外，可以在方框650中將訪問路徑(4)截斷為長度k。
[0055]在數學上，Aliases函數可以使用某些非常直觀的輔助函數，包括將訪問路徑長度限制為給定界限(例如，方框650中的k)的Truncate，以及計算可通過給定訪問路逕到達的抽象對象集合(方框650)的PathTo。為了計算可通過給定訪問路逕到達的抽象對象集合(方框650)，可以使用函數(在此稱為FieldName)。如果給出B中的欄位指針，則函數FieldName返回FieldId (即，欄位標識符集合，如上所述)中的對應欄位標識符。這是有用的，因為如上面解釋的，本示例性分析依賴欄位敏感算法，並且因此區分不同抽象對象的欄位指針鍵，即使當此類欄位指針鍵表示具有相同名稱的欄位時也是如此。從某種意義上說，針對方框630，可以通過執行圖形遍歷計算可通過給定路逕到達的當前抽象對象。上面提供的實例是用於通過給定路徑執行圖形遍歷的一種技術，但還可以使用其它技術。
[0056]在方框660中，輸出(例如，返回)在方框630中確定的訪問路徑。在圖5的方框530中，根據在方框520中執行的跟蹤的輸出，執行數據流分析以便確定從汙染源通過數據流路逕到使用汙染的匯的汙染流。數據流分析可以是上面引用的T.Reps等人的文章中描述的基於RHS的汙染傳播。即，訪問路徑可以與數據流模型中的對應數據流路徑關聯，以便確定哪些數據流路徑可以被汙染。在圖5的方框535中，使用被汙染數據流路徑，根據這些路徑執行一個或多個操作。例如，在方框540中，可以輸出被汙染數據流路徑的指示。作為另一個實例，在方框545中，可以執行額外分析。此類分析可以包括判定任何被汙染數據流路徑是否具有致使數據安全的正確操作。一旦發現被汙染的數據流路徑，存在許多為所屬【技術領域】的技術人員已知的不同選項，並且方框540和545隻是此類選項的兩個實例。
[0057]為了返回到圖3和4的實例，在該實例中，z實際上是同一方法的局部變量(例如，參見圖3 )，並且全局指針分析記錄g欄位可以命名的對象的g欄位可以與X指向同一對象；因此，將z的堆路徑解析為與X的相同的抽象對象。路徑足夠短，不需要截斷路徑。這在圖4中示出，其中從「set.X」通過f的路徑與從「set.z」通過欄位g和f的路徑導向同一抽象對象。
[0058]因此，示例性分析針對「set」函數計算關係摘要{y，ε} — <z，>。在調用方位置(第12行)應用該摘要將添加訪問路徑<s，>。再次地，這是不完整的，因為s和q表示同一對象，因此再次地，在圖6的方框630中執行的操作發現額外訪問路徑。
[0059]注意，對「id」的額外調用(圖3的第11行)不添加汙染信息，因為變量q最初未被汙染。上面討論的示例性上下文敏感汙染傳播分析避免了將〈S，ε>添加到被汙染訪問路徑集合，該添加將使分析非常粗略並生成大量虛假肯定。實際上，使用本實例針對變量s計算的被汙染訪問路徑〈S，精確得多。
[0060]該用於解析混淆關係的示例性算法就欄位而言是流不敏感的，意味著該算法不考慮針對欄位的強大更新；即，如果在兩個不同程序點處為對象O的欄位f分配值V和值W，則分析保守地認為欄位f指向值集合{V，w}。流不敏感性可以在構建調用圖和指向圖(分別為圖5中的方框510和圖5中的方框515)時執行，並且可以在構建堆圖(圖6的方框605)時進一步完善。相反，流敏感分析嘗試確定首先和最後執行哪個寫入指令，並且根據該信息，所述分析報告欄位f指向值V或`值W。
[0061]儘管流敏感分析可能看似更精確，但使用該分析並非始終合理。例如對於JavaScript而言如此。在JavaScript中，程序的執行通常是事件驅動的一例如基於點擊按鈕或者與用戶界面(UI)小部件的交互一無法始終確定某些例程的執行順序。嘗試斷言執行順序可能導致不合理的結果。因此，為了保證合理性，在一個示例性實施例中，選擇保守地使分析針對欄位而言是流不敏感的。
[0062]但是，在過程內部，分析可以針對局部變量而言是流敏感的，因此如果使用SSA(靜態單一賦值)形式，則考慮針對局部變量的強大更新。這是因為SSA創建變量版本以便確保每個變量僅被賦值一次，這間接地提供將訪問路徑限制為長度k的措施。
[0063]轉到圖7，示出適合於執行本發明的示例性實施例的示例性系統。該系統包括計算機系統700，計算機系統700包括一個或多個處理器705、一個或多個存儲器710、一個或多個用戶輸入接口 720 (例如，觸控螢幕接口、滑鼠接口、鍵盤接口等)以及一個或多個網絡接口 725。一個或多個存儲器710包括計算機可讀代碼715 (其包括應用接口 717，例如Web瀏覽器)和程序780。計算機系統700的用戶(未示出)使用應用接口 717將程序780發送到計算機系統750，計算機系統750針對程序780執行汙染分析並發回結果797。計算機系統700包括(如圖7中所示)或者耦合到具有用戶界面735的顯示器730，用戶(未示出)可以通過顯示器730例如查看結果797。還可以通過用戶界面735查看程序780。[0064]該實例是網絡實例，其中計算機系統700與另一個計算機系統750通信，計算機系統750包括一個或多個處理器755、一個或多個存儲器760以及一個或多個網絡接口 785。一個或多個存儲器760包括包含汙染分析程序770的計算機可讀代碼765，汙染分析程序770針對程序780執行上述部分或全部操作以便生成結果797。一個或多個存儲器760還包括程序780、堆圖790、數據流模型795和結果797。在該實例中，數據流模型795包括指針分析模型796，然而兩個模型795、796可以分離。計算機系統700、750通過網絡740 (例如，網際網路)通信。在該實例中，計算機系統700是客戶端，計算機系統750是伺服器。應用接口 717可以如同汙染分析程序770的Web接口那樣簡單，或者可以更複雜，例如小程序或客戶端程序。
[0065]在非網絡實例中，計算機750的用戶將程序780提供給計算機系統750，並且例如通過計算機系統750中的或者連接到計算機系統750的顯示器(未示出)接收結果797。
[0066]所屬【技術領域】的技術人員知道，本發明的各個方面可以實現為系統、方法或電腦程式產品。因此，本發明的各個方面可以具體實現為以下形式，即:完全的硬體實施方式、完全的軟體實施方式(包括固件、駐留軟體、微代碼等)，或硬體和軟體方面結合的實施方式，這裡可以統稱為「電路」、「模塊」或「系統」。此外，本發明的各個方面還可以實現為在一個或多個計算機可讀介質中的電腦程式產品的形式，該計算機可讀介質中包含計算機可讀的程序代碼。
[0067]可以採用一個或多個計算機可讀介質的任意組合。計算機可讀介質可以是計算機可讀信號介質或者計算機可讀存儲介質。計算機可讀存儲介質例如可以是一但不限於一電、磁、光、電磁、紅外線、或半導體的系統、裝置或器件，或者上述的任意合適的組合。計算機可讀存儲介質的更具體的例子(非窮舉的列表)包括:具有一個或多個導線的電連接、可攜式計算機盤、硬碟、隨機存取存儲器(RAM)、只讀存儲器(ROM)、可擦式可編程只讀存儲器(EPROM或快閃記憶體)、光纖、可攜式緊湊盤只讀存儲器(CD-ROM)、光存儲器件、磁存儲器件、或者上述的任意合適的組合。在本文件中，計算機可讀存儲介質可以是任何包含或存儲程序的有形介質，該程序可以被指令執行系統、裝置或者器件使用或者與其結合使用。
[0068]計算機可讀的信號介質可以包括例如在基帶中或者作為載波一部分傳播的數據信號，其中承載了計算機可讀的程序代碼。這種傳播的數據信號可以採用多種形式，包括一但不限於一電磁信號、光信號或上述的任意合適的組合。計算機可讀的信號介質可以是計算機可讀存儲介質以外的任何計算機可讀介質，該計算機可讀介質可以發送、傳播或者傳輸用於由指令執行系統、裝置或者器件使用或者與其結合使用的程序。
[0069]計算機可讀介質上包含的程序代碼可以用任何適當的介質傳輸，包括一但不限於一無線、有線、光纜、RF等等，或者上述的任意合適的組合。
[0070]可以以一種或多種程序設計語言的任意組合來編寫用於執行本發明的各個方面的操作的電腦程式代碼，所述程序設計語言包括面向對象的程序設計語言一諸如Java、Smalltalk、C++等，還包括常規的過程式程序設計語言一諸如「C」語言或類似的程序設計語言。程序代碼可以完全地在用戶計算機上執行、部分地在用戶計算機上執行、作為一個獨立的軟體包執行、部分在用戶計算機上部分在遠程計算機上執行、或者完全在遠程計算機或伺服器上執行。在涉及遠程計算機的情形中，遠程計算機可以通過任意種類的網絡一包括區域網(LAN)或廣域網(WAN) —連接到用戶計算機，或者，可以連接到外部計算機(例如利用網際網路服務提供商來通過網際網路連接)。
[0071]上面參照根據本發明實施例的方法、裝置(系統)和電腦程式產品的流程圖和/或框圖描述了本發明的各個方面。應當理解，流程圖和/或框圖的每個方框以及流程圖和/或框圖中各方框的組合，都可以由電腦程式指令實現。這些電腦程式指令可以提供給通用計算機、專用計算機或其它可編程數據處理裝置的處理器，從而生產出一種機器，使得這些指令在通過計算機或其它可編程數據處理裝置的處理器執行時，產生了實現流程圖和/或框圖中的一個或多個方框中規定的功能/動作的裝置。
[0072]也可以把這些電腦程式指令存儲在計算機可讀介質中，這些指令使得計算機、其它可編程數據處理裝置、或其它設備以特定方式工作，從而，存儲在計算機可讀介質中的指令就產生出包括實現流程圖和/或框圖中的一個或多個方框中規定的功能/動作的指令的製造品(article of manufacture)0
[0073]也可以把電腦程式指令加載到計算機、其它可編程數據處理裝置、或其它設備上，使得在計算機、其它可編程裝置或其它設備上執行一系列操作步驟，以產生計算機實現的過程，從而使得在計算機或其它可編程裝置上執行的指令提供實現流程圖和/或框圖中的一個或多個方框中規定的功能/動作的過程。
[0074]在此使用的術語只是為了描述特定的實施例並且並非旨在作為本發明的限制。如在此所使用的，單數形式「一」、「一個」和「該」旨在同樣包括複數形式，除非上下文明確地另有所指。還將理解，當在此說明書中使用時，術語「包括」和/或「包含」指定了聲明的特性、整數、步驟、操作、元素和/或組件的存在，但是並不排除一個或多個其它特性、整數、步驟、操作、元素、組件和/或其組的存在或增加。
[0075]下面權利要求中的對應結構、材料、操作以及所有功能性限定的裝置或步驟的等同替換，旨在包括任何用於與在權利要求中具體指出的其它元件相組合地執行該功能的結構、材料或操作。出於示例和說明目的給出了對本發明的描述，但所述描述並非旨在是窮舉的或是將本發明限於所公開的形式。在不偏離本發明的範圍和精神的情況下，對於所屬【技術領域】的普通技術人員來說許多修改和變化都將是顯而易見的。實施例的選擇和描述是為了最佳地解釋本發明的原理和實際應用，並且當適合於所構想的特定使用時，使得所屬【技術領域】的其它普通技術人員能夠理解本發明的具有各種修改的各種實施例。
【權利要求】
1.一種數據流分析方法，包括: 使用適合於程序汙染分析的程序數據流模型，利用基於所述程序的堆模型從汙染源到所述堆中的實體來跟蹤信息，其中執行所述跟蹤以便所述信息與汙染傳播相關，並且針對所述堆中的所述實體以欄位敏感的方式執行所述跟蹤；以及 基於所述跟蹤的輸出，執行數據流分析以便確定從所述汙染源通過數據流路逕到使用所述汙染的匯的汙染流。
2.根據權利要求1的方法，其中跟蹤信息進一步包括使用指針分析模型執行欄位敏感分析，以便將所述堆中的抽象對象的欄位彼此區分開並將所述堆中的不同抽象對象的欄位彼此區分開。
3.根據權利要求2的方法，其中所述欄位敏感分析區分不同抽象對象的欄位指針鍵，即使當此類欄位指針鍵表示具有相同名稱的欄位時也是如此。
4.根據權利要求2的方法，其中所述指針分析模型包括指向圖。
5.根據權利要求2的方法，還包括通過分析所述程序確定所述數據流模型，並且通過分析所述程序確定所述指針分析模型。
6.根據權利要求2的方法，其中使用指針分析模型執行欄位敏感分析進一步包括創建堆圖，所述堆圖包括具有所述程序中的環境和堆指針的第一集合與具有參與所述指針分析模型的所述抽象對象的第二集合的交集，並且還包括連接所述第一和第二集合的元素的邊
口 O
7.根據權利要求6的方法，其中具有所述程序中的環境和堆指針的第一集合包括所述堆中的局部變量和引用所述堆中的對象的欄位。
8.根據權利要求6的方法，其中跟蹤信息進一步包括: 確定汙染流入給定訪問路徑，其中每個訪問路徑是將變量與欄位標識符集合相連結的對，並且其中可以評估訪問路徑以便產生在所述堆中分配的唯一對象； 確定與所述給定訪問路徑對應的滿足條件集合的所有訪問路徑，所述確定所有訪問路徑的步驟使用所述堆圖；以及 輸出所確定的滿足所述條件集合的訪問路徑。
9.根據權利要求8的方法，其中使用特定環境和給定堆在所述程序的特定具體狀態下執行訪問路徑評估，以便在所述給定堆中產生所述唯一對象。
10.根據權利要求8的方法，其中確定汙染流入給定訪問路徑進一步包括使用所述程序中的函數的關係摘要映射來確定汙染流入所述給定訪問路徑。
11.根據權利要求10的方法，其中確定汙染流入給定訪問路徑進一步包括針對所述程序中被首次分析的函數，確定將所述函數的一個或多個輸入參數映射到所述函數的一個或多個返回值的關係摘要。
12.根據權利要求8的方法，其中所述條件集合包括: 所有訪問路徑中的所述訪問路徑以局部變量為根； 所述局部變量屬於同一方法；以及 所有所述訪問路徑均與所述給定訪問路徑混淆。
13.根據權利要求12的方法，其中所述條件集合進一步包括:可以將所有所述訪問路徑截斷為特定長度。
14.根據權利要求1的方法，其中以針對欄位而言還為流不敏感的方式執行所述跟蹤信息的步驟，其中響應於在兩個不同程序點為所述堆中的對象ο的欄位f分配值V和值W，所述欄位f被視為指向值集合Iv, w}。
15.根據權利要求14的方法，其中所述跟蹤信息進一步包括構建調用圖和指向圖，並且其中當構建至少所述調用圖和指向圖時，執行流不敏感性。
16.根據權利要求1的方法，還包括輸出通過執行所述數據流分析而確定為被汙染的所述數據流路徑的指示。
17.一種數據流分析裝置，包括: 被配置為使用適合於程序汙染分析的程序數據流模型，利用基於所述程序的堆模型從汙染源到所述堆中的實體來跟蹤信息的模塊，其中執行所述跟蹤以便所述信息與汙染傳播相關，並且針對所述堆中的所述實體以欄位敏感的方式執行所述跟蹤；以及 被配置為基於所述跟蹤的輸出，執行數據流分析以便確定從所述汙染源通過數據流路逕到使用所述汙染的匯的汙染流的模塊。
18.根據權利要求17的裝置，其中被配置為跟蹤信息的模塊進一步包括被配置為使用指針分析模型執行欄位敏感分析，以便將所述堆中的抽象對象的欄位彼此區分開並將所述堆中的不同抽象對象的欄位彼此區分開的模塊。
19.根據權利要求18的裝置，其中所述欄位敏感分析區分不同抽象對象的欄位指針鍵，即使當此類欄位指針鍵表示具有相同名稱的欄位時也是如此。
20.根據權利要求18的裝置，其中所述指針分析模型包括指向圖。
21.根據權利要求18的裝置，還包括被配置為通過分析所述程序確定所述數據流模型並且通過分析所述程序確定所述指針分析模型的模塊。
22.根據權利要求18的裝置，其中被配置為使用指針分析模型執行欄位敏感分析的模塊進一步包括被配置為創建堆圖的模塊，所述堆圖包括具有所述程序中的環境和堆指針的第一集合與具有參與所述指針分析模型的所述抽象對象的第二集合的交集，並且還包括連接所述第一和第二集合的元素的邊集合。
23.根據權利要求22的裝置，其中具有所述程序中的環境和堆指針的第一集合包括所述堆中的局部變量和引用所述堆中的對象的欄位。
24.根據權利要求22的裝置，其中被配置為跟蹤信息的模塊進一步包括: 被配置為確定汙染流入給定訪問路徑的模塊，其中每個訪問路徑是將變量與欄位標識符集合相連結的對，並且其中可以評估訪問路徑以便產生在所述堆中分配的唯一對象； 被配置為確定與所述給定訪問路徑對應的滿足條件集合的所有訪問路徑的模塊，所述確定所有訪問路徑使用所述堆圖；以及 被配置為輸出所確定的滿足所述條件集合的訪問路徑的模塊。
25.根據權利要求24的裝置，其中使用特定環境和給定堆在所述程序的特定具體狀態下執行訪問路徑評估，以便在所述給定堆中產生所述唯一對象。
26.根據權利要求2 4的裝置，其中被配置為確定汙染流入給定訪問路徑的模塊進一步包括被配置為使用所述程序中的函數的關係摘要映射來確定汙染流入所述給定訪問路徑的模塊。
27.根據權利要求26的裝置，其中被配置為確定汙染流入給定訪問路徑的模塊進一步包括被配置為針對所述程序中被首次分析的函數，確定將所述函數的一個或多個輸入參數映射到所述函數的一個或多個返回值的關係摘要的模塊。
28.根據權利要求24的裝置，其中所述條件集合包括: 所有訪問路徑中的所述訪問路徑以局部變量為根； 所述局部變量屬於同一裝置；以及 所有所述訪問路徑均與所述給定訪問路徑混淆。
29.根據權利要求28的裝置，其中所述條件集合進一步包括:可以將所有所述訪問路徑截斷為特定長度。
30.根據權利要求17的裝置，其中以針對欄位而言還為流不敏感的方式執行被配置為跟蹤信息的模塊，其中響應於在兩個不同程序點為所述堆中的對象ο的欄位f分配值V和值W,所述欄位f被視為指向值集合{v, w}。
31.根據權利要求30的裝置，其中被配置為確定汙染流入給定訪問路徑的模塊進一步包括被配置為構建調用圖和指向圖的模塊，並且其中當構建至少所述調用圖和指向圖時，執行流不敏感性。
32.根據權利要求17的裝置，還包括被配置為輸出通過執行所述數據流分析而確定為被汙染的所述數據流路徑的指示的模塊。
【文檔編號】G06F9/44GK103809966SQ201310548222
【公開日】2014年5月21日 申請日期:2013年11月7日 優先權日:2012年11月8日
【發明者】J·杜比, S·A·瓜爾涅裡, M·皮斯託亞, O·特裡普 申請人:國際商業機器公司