本發明公開了一種基于序列模式挖掘的并發程序剖析方法，通過對并發程序的源代碼進行分析，獲取其中的線程信息以及線程之前的依賴關系，以插樁的方式來捕獲程序運行過程中所執行的依賴關系序列，最后通過基于序列模式挖掘的方法獲知所執行的并發程序中父子線程交互的剖析結果。

技術領域

本發明屬于動態程序分析的技術領域，涉及一種基于序列模式挖掘的并發程序剖析方法。

背景技術

程序剖析技術是針對軟件執行中發生的控制流信息和數據流信息，統計每種信息的執行頻率，以輔助分析程序行為，決定優化方向，已經廣泛應用于編譯優化、程序理解等領域。

目前主要的剖析方法有：

1996年T.Ball和J.Larus提出的Efficient Path Profiling方法。該方法首次提出通過在目標軟件中插樁探針語句的方式來實現路徑的唯一編碼，能夠以低廉的耗費處理一個軟件中所有的非循環路徑，但是不能處理循環路徑，其中的路徑編碼和插樁方式為后續的路徑剖析研究奠定了基礎；

2007年K.Vaswani等人提出的Preferential Path Profiling方法。該方法能夠針對用戶所指定的目標軟件中一部分非循環路徑(稱為“興趣路徑集合”)進行剖析，不區分或處理興趣路徑集合之外的任何路徑，該方法耗費較Efficient Path Profiling更低，依然不能處理循環路徑；

2012年B.Li和L.Wang等人提出的Profiling ofAll Paths方法。這一方法能夠處理帶有循環的軟件路徑，獲得精確的剖析結果，耗費高于前兩種方法。

現有的剖析技術均不適用于并發程序。并發程序的執行過程包含多個線程的創建、睡眠、喚醒和終止等交互序列，比普通單線程程序的執行過程更加復雜，多個線程的糾纏執行為理解并發程序執行過程帶來了困難。針對線程交互序列進行剖析，可以獲知并發程序執行過程中主流的線程執行操作，有助于揭示并發程序線程操作的邏輯鏈條，幫助軟件相關人員理解并發程序的行為。

序列模式挖掘技術可以用于從程序執行軌跡中抽取線程交互序列信息，形成剖析結果。目前主要的序列模式挖掘算法，如Apriori、GSP(generalized sequentialpattern)、FreeSpan等，均屬于通用的挖掘算法。針對并發程序剖析這一具體應用場景，需要在應用挖掘算法時進行相應的調整，以達成剖析的目標。

發明內容

技術問題：本發明提供一種能夠分析并發程序交互關系，記錄執行軌跡，并通過挖掘軌跡中的序列模式獲取信息，完成剖析的基于序列模式挖掘的并發程序剖析方法。

技術方案：本發明的一種基于序列模式挖掘的并發程序剖析方法，包括如下步驟：

步驟1)通過并發程序源碼的靜態分析方法，獲得并發程序中存在的所有線程信息集合S_thread＝{T_x}，所有線程位置集合S_location＝{L_y}，以及線程之間各種類型的依賴關系集合S_dependence＝{Type，L_a，L_b}，所述所有線程信息集合S_thread＝{T_x}包括T_a，T_b兩個線程，L_a是T_a的一個代碼位置，L_b是T_b的一個代碼位置，Type是從L_a指向L_b的依賴關系類型；

步驟2)按照所述步驟1中所得信息進行代碼插樁，并通過執行插樁后的并發程序來獲取依賴軌跡，具體方法為：