基於路徑特徵的程序執行軌跡狀態自動獲取方法
2023-12-05 20:14:11 1
基於路徑特徵的程序執行軌跡狀態自動獲取方法
【專利摘要】本發明公開了一種基於路徑特徵的程序執行軌跡狀態自動獲取方法，通過靜態分析程序數據流和控制流結構定義程序路徑的特徵集合及相關的推理規則，並利用程序執行的路徑特徵自動地推理每個程序節點在該次執行中的(一個或多個)狀態；對於多條需要獲知節點狀態的路徑可以同時計算，過程簡便，成本低廉。
【專利說明】基於路徑特徵的程序執行軌跡狀態自動獲取方法
【技術領域】
[0001] 本發明涉及一種基於路徑特徵的程序執行軌跡狀態自動獲取方法，屬於軟體維護 中的故障定位領域。
【背景技術】
[0002] 故障定位是軟體維護過程中最重要的步驟之一，通過對測試中的程序正確執行和 失效執行的分析來對程序中故障可能存在的位置進行推測，主要有人工、自動化和半自動 化等幾類方法。人工定位方法依賴於軟體工程師的經驗及其對該程序的熟知程度，往往效 率較低，過程難以控制；自動化或半自動化方法通過比對程序執行中的各類信息對程序各 個位置可能存在故障的可能性進行計算，能夠處理大規模的程序和執行，效率較高，應用廣 泛，同時定位精度成為了每種方法的關鍵要素。
[0003] 節點狀態是概率化故障定位方法中普遍採用的一種信息，此類方法通過各個節點 在執行中的狀態來分析故障的產生可能由哪些節點的執行（或不執行）所引起。由於對程 序執行進行了具體、真實的分析，一般定位精度較高，效果較好。但是此類方法需要程序源 碼、執行路徑和節點狀態三項輸入，尤其是節點的狀態涉及複雜的變量定義和使用，較為難 以獲得。
[0004] 針對這一問題，目前普遍採用的方法較為簡單，一般通過插樁的方式使得目標程 序在執行過程中能夠記錄所有執行節點的狀態。由於程序中節點眾多，每個節點可能含有 多個狀態分量，所以這種處理方式效率很低。本發明考慮通過抽取路徑的實質特徵來精簡 插樁節點，並通過結合靜態分析的方法減免部分收集節點狀態分量的工作。
【發明內容】
[0005] 技術問題：本發明提供一種利用程序的執行路徑和源碼信息來自動計算執行中 各個節點每次出現的狀態，能夠根據源碼分析出靜態視圖中各個節點的變量定義和使用情 況，信息易於獲取、運行效率高的基於路徑特徵的程序執行軌跡狀態自動獲取方法。
[0006] 技術方案：本發明的基於路徑特徵的程序執行軌跡狀態自動獲取方法，包括如下 步驟：
[0007] 步驟1)通過靜態分析程序源碼獲知程序控制流圖和所述程序控制流圖中每個節 點N的定義變量集合{dN}、使用變量集合{%};
[0008] 步驟2)從所述程序控制流圖中抽取能作為程序特徵的邊，組成特徵集合{EJ，然 後用所述特徵的序列表示每條路徑；
[0009] 步驟3)通過程序控制流圖、{dN}、{%}和{Ex}推導出"特徵序列-節點狀態"推理 規則，所述推理規則由條件和結論兩部分組成，所述條件是特徵序列，所述結論是路徑中一 個節點的一項狀態分量，基於推理規則，能夠通過任一條路徑中的特徵序列計算該路徑中 每個節點的狀態分量；
[0010] 步驟4)針對待分析的每條執行路徑，通過推理規則和該路徑的特徵序列計算路 徑上每個節點的所有狀態分量，最終得到的每個節點的狀態；
[0011] 步驟5)對於所述步驟4)中計算得到的狀態分量為空的節點，即未涉及任何變量 的節點，將其狀態標記為T，符號T表示執行。
[0012] 本發明方法的優選方案中，步驟3)中推導出"特徵序列-節點狀態"理規則的具 體流程為：
[0013] (a)針對程序中涉及的每個變量，統計出每個變量Vi的定義節點集合{Ni}，i為變 量編號
[0014] (b)計算從{NJ中每個節點Na到每個使用變量Vi的節點N b之間的必經特徵集合 {Ed}和禁止特徵集合{Ef} = (E1, E2，…，EJ，m為集合{Ef}中元素的個數；
[0015] (c)按照如下規則將所述{Ed}和{Ef}組合為特徵序列：對於{E d}中的每個元素 Ex，從Ex到節點Nb的路徑不經過禁止特徵集合{Ef};
[0016] (d)以所述特徵序列為條件、Nb:da (Vi)為結論，構建得到"特徵序列-節點狀態"推 理規則 Ex (E1, E2,…，Em) = >Nb: da (Vi)。
[0017] 本發明方法中，步驟b)中，必要特徵集合為：從節點Na到節點Nb的不經過{NJ中 任意元素的路徑所必然經過的特徵組成的集合；禁止特徵集合為：從節點Na到節點Nb的不 經過{NJ中任意元素的路徑所必然不經過的特徵組成的集合。
[0018] 本發明方法的優選方案中，步驟4)中計算路徑上節點的狀態分量的具體流程為：
[0019] (a)以路徑中節點作為分割點，將路徑對應的特徵序列劃分為前後兩段；
[0020] (b)以該節點之前的特徵序列片段匹配每條"特徵序列-節點狀態"推理規則，在 符合規則的條件下推導出該節點的每個狀態分量；
[0021] (C)組合該節點的所有狀態分量，即得到該節點的狀態。
[0022] 本發明方法的優選方案中，步驟2)中抽取的能作為程序路徑的邊為程序控制流 圖中程序入口邊和所有不屬於最小生成樹的邊。
[0023] 本發明方法主要是利用程序的執行路徑結合靜態的源碼分析自動地統計程序執 行中各個節點的狀態，以降低基於節點狀態的故障定位技術的應用成本。
[0024] 有益效果：本發明方法通過結合路徑執行特徵和源碼分析結合的方式自動計算執 行中的節點轉臺，與現有技術相比，本發明具有以下優點：
[0025] (1)需要的信息易於獲取。概率化的故障定位技術（如PPDG，Probabilistic Program Dependency Graph) -般需要三項輸入：執行路徑、程序源碼和節點狀態，現有方 法對執行路徑和節點狀態這兩項的信息收集過程是獨立的，需要分別進行，而本發明方法 以路徑特徵序列和程序源碼作為輸入，進行節點狀態的計算，減少了對輸入信息的要求。
[0026] (2)計算成本低廉。現有方法收集執行路徑和計算節點狀態時分別需要在程序源 碼上進行插樁，記錄執行路徑以及每個變量的定義和使用情況。本發明方法通過定義路徑 特徵來簡化路徑表示，減少了插樁的數量（收集執行路徑和計算節點狀態時，僅需要在路 徑特徵處實施插樁），進而減少了插樁語句對程序執行效率的影響，與現有方法相比提高了 運行效率。
【專利附圖】
【附圖說明】
[0027] 圖1是本發明方法的流程圖。
[0028] 圖2是本發明的路徑特徵例圖，用於說明對執行路徑的特徵定義和實現。
[0029] 圖3是圖2中的最小生成樹。
[0030] 圖4是圖2中路徑特徵集合。
[0031] 圖5是本發明的推理規則例圖。表示本發明中對相關推理規則的設計和應用。
[0032] 圖6是本發明的實施例圖。表示實施例中相關內容。
【具體實施方式】
[0033] 下面結合附圖對發明的技術方案進行詳細說明：
[0034] 本發明利用程序執行的路徑信息和所執行語句的數據定義、使用信息，通過自動 化的路徑特徵提取和推理，對程序執行軌跡狀態進行計算，強調計算過程的簡單易行和計 算結果的精確性。
[0035] 一、體系結構
[0036] 圖1給出了基於路徑特徵的程序執行軌跡狀態自動獲取方法設計體系結構。下面 給出幾個主要部分的具體說明。
[0037] 1靜態分析組件
[0038] 本組件的功能為：通過分析目標程序的源碼，獲取相關的控制流信息和數據流信 息，進而通過分析控制流信息得出該程序執行的路徑特徵集合，並通過結合控制流和數據 流的信息構建路徑特徵與執行軌跡狀態之間的推理規則。。
[0039] 路徑特徵集合是程序控制流圖中所有邊的一個子集。本發明中使用的路徑特徵包 括程序入口邊和控制流圖中所有不屬於最小生成樹的邊。假設有如圖2的程序結構，其中 包含四個程序節點A、B、C和D，以及五條邊AB、BC、CB、⑶和DB。該程序的一個最小生成樹 如圖3所示，那麼可以得到路徑特徵為{AB，CB，DB}，如圖4中雙線所示。
[0040] 特徵所構成的序列與程序中所有的路徑--對應。如圖2中路徑ABCBCD，其特徵 序列為AB、CB，對比圖可知符合該特徵序列的路徑只有ABCB⑶。
[0041] 節點狀態的每個分量是一個該節點使用變量的定義情況，即在執行到該節點時， 所執行到的每個變量最後一個定義位置。這樣的位置與程序執行有關，可以從程序控制流 圖中歸納該位置對應的執行路徑的特點，將這一特點轉化為等價的特徵序列；那麼當一次 執行符合這一特徵序列時，即可判定該執行位置處的節點狀態包含相應的狀態分量。
[0042] 為說明推理規則，做如下定義：
[0043] 必經特徵：從節點A到節點B，必然經過的特徵。
[0044] 必要特徵：指的是在給定的路徑約束中，必然經過的特徵。
[0045] 禁止特徵：指的是在給定的路徑約束中，必然不經過的特徵。
[0046] 例如，在圖2的控制流圖中，假設路徑約束為"從節點C到節點D，中間不經過節點 B"，那麼必要特徵集合為空集，禁止特徵集合為{CB}。必經特徵可以使用類似必經節點的計 算方法進行計算，而必要特徵和禁止特徵需要使用必經特徵進行計算。
[0047] 本發明中的推理規則是以路徑特徵組成的條件為前提、以節點狀態分量為結論的 推理表達式。其前提條件由必要特徵和禁止特徵組合而成（必要特徵和禁止特徵均來自路 徑特徵集合），而結論由節點和狀態分量組成。
[0048] 推理規則的含義為：對於推理規則A，在程序執行到當前節點N時，已經執行的路 徑特徵邊的序列必須按照順序包含A前提條件中的每條必要特徵，且在相應的位置不包含 任何禁止特徵，那麼在對節點N的狀態進行推理時，可以使用規則A。
[0049] 例如，假設有程序局部結構為圖5,包含N1?N6六個節點，E 1?E6六條邊。假設 有三條針對節點N6的推理規則：
[0050] a) E1 (E2, E3) = > N6: dm (x)
[0051] WE3(E1) = > N6: dn (y)
[0052] c)E2 = > N6: dk (y)
[0053] 這些規則的含義為：
[0054] 1)推理規則中符號"=>"左側的是前提條件，右側的是結論；
[0055] 2)前提條件中括號內為禁止特徵，括號外為必要特徵，E1(E21E3)表示：執行到當 前節點時，E1必須執行過,且在E1執行之後,沒有執行E2或E 3。
[0056] 3)結論中冒號左側為節點，如N6表示使用推理規則時，N6為當前節點；結論中冒 號右側為狀態分量，如dm (X)表示N6在該處執行時使用的變量X定義來自於語句m，-T表示 N6的狀態為已執行。
[0057] 2插樁組件
[0058] 本組件的主要功能是在每個路徑特徵處插樁語句，以自動化地在目標程序執行過 程中收集相應的路徑特徵序列，作為獲取程序節點狀態的前提。
[0059] 目前已有很多種Program Tracing和Path Profiling領域中的技術可以完成這一 工作，如 Whole Program Paths、Profiling of All Paths 等。
[0060] 3執行和路徑特徵收集組件
[0061] 本組件的主要功能是使用給定的測試用例運行插樁後的目標程序，在程序的執行 過程中自動收集所執行的路徑特徵；並刪除重複的執行路徑，將剩餘的執行所對應的路徑 特徵存儲，作為進一步計算程序節點狀態的信息。
[0062] 4節點狀態獲取組件
[0063] 本組件的主要功能是基於已獲取的路徑特徵和推理規則，對該次執行中每個執行 位置的節點狀態進行推理，獲知節點狀態，為其他程序分析和故障定位技術提供幫助。
[0064] 二、具體過程
[0065] 本發明方法通過抽取程序特徵的方式簡化程序執行路徑，結合程序的靜態信息進 行執行路徑中的節點狀態計算，具體過程為：
[0066] 步驟1)抽取程序靜態信息。因為每個節點的狀態包括該節點處所使用的每個變 量的定義來源，所以節點狀態的計算和變量的"定義-使用"關係密不可分。通過現有的靜 態分析技術，可以自動地從程序源碼中獲取程序控制流圖和所述程序控制流圖中每個節點 N的定義變量集合{dN}、使用變量集合{%};
[0067] 步驟2)定義程序特徵。由於程序結構存在順序關係，由所執行的邊的序列所組成 的程序路徑中的信息存在冗餘，這增加了計算工作。為了刪除冗餘信息，從所述程序控制流 圖中抽取程序控制流圖中程序入口邊和所有不屬於最小生成樹的邊，以這些邊作為特徵， 組成特徵集合{EJ，然後用所述特徵的序列表示每條路徑，達到壓縮路徑長度、簡化計算的 效果；
[0068] 步驟3)構建推理規則。進而通過程序控制流圖、{dN}、{%}和{Ex}推導出"特徵 序列-節點狀態"推理規則，所述推理規則由條件和結論兩部分組成，所述條件是特徵序列， 所述結論是路徑中一個節點的一項狀態分量，基於推理規則，能夠通過任一條路徑中的特 徵序列計算該路徑中每個節點的狀態分量。推導步驟包括：
[0069] (a)針對程序中涉及的每個變量，統計出每個變量Vi的定義節點集合{NJ，i為變 量編號；
[0070] (b)計算從{NJ中每個節點Na到每個使用變量Vi的節點N b之間的必經特徵集合 {Ed}和禁止特徵集合{Ef} = (E1, E2，…，EJ，m為集合{Ef}中元素的個數；
[0071] (c)按照如下規則將所述{Ed}和{Ef}組合為特徵序列：對於{E d}中的每個元素 Ex，從Ex到節點Nb的路徑不經過禁止特徵集合{Ef};
[0072] (d)以所述特徵序列為條件、Nb:da (Vi)為結論，構建得到"特徵序列-節點狀態"推 理規則 Ex (E1, E2,…，Em) = >Nb: da (Vi)。
[0073] 步驟4)計算節點狀態。針對待分析的每條執行路徑，通過推理規則和該路徑的特 徵序列計算路徑上面每個節點的所有狀態分量，最終得到的每個節點的狀態。計算步驟包 括：
[0074] (a)以路徑中節點作為分割點，將路徑對應的特徵序列劃分為前後兩段；
[0075] (b)以該節點之前的特徵序列片段匹配每條"特徵序列-節點狀態"推理規則，在 符合規則的條件下推導出該節點的每個狀態分量；
[0076] (C)組合該節點的所有狀態分量，即得到該節點的狀態。
[0077] 步驟5)處理未計算節點。對於所述步驟4)中計算得到的狀態分量為空的節點， 即未涉及任何變量的節點，將其狀態標記為-T，符號-T表不執行。
[0078] 三、實施例
[0079] 為了方便描述，我們假定有如下簡化的應用實例：目標程序源碼如下所示，共有9 條語句。
[0080]
【權利要求】
1. 一種基於路徑特徵的程序執行軌跡狀態自動獲取方法，其特徵在於，該方法包括如 下步驟： 步驟1)通過靜態分析程序源碼獲知程序控制流圖和所述程序控制流圖中每個節點N 的定義變量集合{dN}、使用變量集合{uN}; 步驟2)從所述程序控制流圖中抽取能作為程序特徵的邊，組成特徵集合{Ex}，然後用 所述特徵的序列表示每條路徑； 步驟3)通過程序控制流圖、{dN}、{%}和{Ex}推導出"特徵序列-節點狀態"推理規 貝U，所述推理規則由條件和結論兩部分組成，所述條件是特徵序列，所述結論是路徑中一個 節點的一項狀態分量，基於推理規則，能夠通過任一條路徑中的特徵序列計算該路徑中每 個節點的狀態分量； 步驟4)針對待分析的每條執行路徑，通過推理規則和該路徑的特徵序列計算路徑上 每個節點的所有狀態分量，最終得到的每個節點的狀態； 步驟5)對於所述步驟4)中計算得到的狀態分量為空的節點，即未涉及任何變量的節 點，將其狀態標記為丁，符號丁表不執行。
2. 根據權利要求1所述的基於路徑特徵的程序執行軌跡狀態自動獲取方法，其特徵在 於，所述步驟3)中推導出"特徵序列-節點狀態"推理規則的具體流程為： (a) 針對程序中涉及的每個變量，統計出每個變量Vi的定義節點集合{Nj，i為變量編 號； (b) 計算從{NJ中每個節點凡到每個使用變量￥1的節點Nb之間的必經特徵集合{Ed} 和禁止特徵集合{Ef} = {Ed E2，…，Em}，m為集合{Ef}中元素的個數； (c) 按照如下規則將所述{Ed}和{Ef}組合為特徵序列：對於{Ed}中的每個元素E x，從 Ex到節點Nb的路徑不經過禁止特徵集合{Ef}; (d) 以所述特徵序列為條件、Nb:da(Vi)為結論，構建得到"特徵序列-節點狀態"推理 規則 Ex E2,…，Em) = >Nb: da (vD。
3. 根據權利要求1或2所述的基於路徑特徵的程序執行軌跡狀態自動獲取方法，其特 徵在於，所述步驟b)中，必要特徵集合為：從節點Na到節點Nb的不經過{NJ中任意元素 的路徑所必然經過的特徵組成的集合；所述禁止特徵集合為：從節點Na到節點Nb的不經過 {NJ中任意元素的路徑所必然不經過的特徵組成的集合。
4. 根據權利要求1或2所述的基於路徑特徵的程序執行軌跡狀態自動獲取方法，其特 徵在於，所述步驟4)中計算路徑上節點的狀態分量的具體流程為： (a) 以路徑中節點作為分割點，將路徑對應的特徵序列劃分為前後兩段； (b) 以該節點之前的特徵序列片段匹配每條"特徵序列-節點狀態"推理規則，在符合 規則的條件下推導出該節點的每個狀態分量； (c) 組合該節點的所有狀態分量，即得到該節點的狀態。
5. 根據權利要求4所述的基於路徑特徵的程序執行軌跡狀態自動獲取方法，其特徵在 於：所述步驟2)中抽取的能作為程序路徑的邊為程序控制流圖中程序入口邊和所有不屬 於最小生成樹的邊。
【文檔編號】G06F11/36GK104407969SQ201410609913
【公開日】2015年3月11日 申請日期:2014年11月3日 優先權日:2014年11月3日
【發明者】王璐璐, 李必信, 廖力, 周穎 申請人:東南大學