[發明專利]一種基于有限自動機的行為自動建模方法

無效

• 申請號: 201110102612.8
• 申請日: 2011-04-22
• 公開（公告）號: CN102135940A
• 公開（公告）日: 2011-07-27
• 發明（設計）人: 胡昌振;周銀;王崑聲;趙小林;薛靜鋒
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 張利萍;高燕燕

技術領域

本發明屬于軟件行為領域，涉及一種基于有限自動機的行為自動建模方法。

背景技術

軟件行為的動態模型用來動態的檢測反常行為，靜態和動態的檢查軟件組件、驗證協議、生成測試案例、獲取異常事件序列和驗證程序屬性之間的兼容性。有限狀態自動機(Finite?State?Automata)是一種用于研究系統狀態的數學模型，也是有限計算的基本模型，是許多形式化規格、驗證方法的基礎模型，它常用于行為建模中。功能行為建模的主要技術或者生成限制數據的模型，通常是以布爾表達式的形式；或者組件之間的互動模式，通常是以有限狀態機的形式。數據和交互建模都對分析和驗證系統執行的特殊方面有用：Daikon描述檢測變量的重要屬性，有限狀態推理機捕捉和推廣交互模式。然而，這些模型中沒有一個能捕捉數據值和組件交互之間的復雜的相互作用，所以最近的分析和測試技術會錯失重要的信息。數據值和交互序列間復雜的相互作用，或者更多的事件序列可能依賴數據值，可以通過擴展有限狀態機有效的建模，它標示在不同狀態下捕捉約束數據值的調用特征。從執行樣例中自動生成EFSMs是一個具有挑戰的問題，Berg?et?al.曾在一定程度上做過描述。他提出的方法由于強制的要求限制了其應用，如執行成員的可能性，等價查詢和僅支持布爾參數。

一種軟件行為自動建模算法——GK-tail，關注數據值和組件交互之間關系的模型生成，這是一種從交互軌跡自動生成擴展的有限狀態機(EFSMs)的技術。GK-tail處理交互軌跡集合，產生一個處理過所有交互軌跡的EFSM。它分為四個步驟：(1)合并輸入-等價軌跡。這一部分是對記錄軌跡的初步處理，合并僅僅是不同數據值的調用序列。也就是說，一個輸入-等價軌跡集合表示一個行為樣式。(2)生成相關軌跡的謂詞。這一步同樣是對記錄軌跡的處理，主要是指從多重數據值集合中產生相關轉換謂詞。(3)產生一個初始的擴展有限自動機模型。在這一步，增加一個公共初始狀態，從標注謂詞的交互軌跡生成一個初始的EFSM模型。(4)合并等價狀態，得到最終的擴展有限自動機模型。最后一步也是比較重要的，合并的規則是kTail算法主要規則的擴展，當不同的EFSM狀態生成等價的行為集合，則有一個唯一的邏輯狀態的多重表達，同時可以安全的合并。

現有的動態模型無法捕捉完整的信息，限制了分析和驗證相關技術的精準性。

關于行為建模的動態分析技術主要有以下三類，數據值的相互關系，生成交互樣式的模型，或者生成同時捕獲數據和交互的模型。

(1)檢測數據值的相互關系。在特殊的程序點給變量賦值可以提供重要的信息來理解和分析系統執行情況。一些動態分析技術已經在不同應用領域進行了實驗，來自動的提取關于數據相互關系的信息。

(2)交互式樣的生成模型。存在一些技術從軌跡集合中自動生成有限狀態機(FSM)。其中有些推理引擎僅從確定樣例集合中生成模型。大多數依賴確定樣例運行的技術是k-tail算法的擴展和變種。

(3)生成整合模型。EFSMs已經廣泛的應用到狀態行為的規格說明中，但是目前為止，從程序行為自動生成EFSMs的方法很少的被研究學習。Berg?et?al.提出了一種技術來生成EFSMs。這項技術僅支持布爾參數的謂詞，同時在嚴格條件下運行：要求查詢成員的概率，就是來一個未知序列是否是模型的一部分，并要求查詢等價，就是來決定一個局部推理模型和被推理的模型之間的等價。

這些技術都無法捕捉完整的信息，特別是數據屬性值和組件交互軌跡之間的作用的信息。本發明的目的就是為了獲得更多更精確的信息，生成更好的軟件行為模型。

發明內容

本發明的目的在于針對現有技術的不足，提出一種基于有限自動機的行為自動建模方法，目的就是為了獲得更多更精確的信息，生成更好的軟件行為模型。

該種基于有限自動機的行為自動建模方法，包括以下步驟：

第一步：獲取交互軌跡：獲取樣例執行情況的交互軌跡使得交互軌跡執行順序唯一；

第二步：合并輸入-等價軌跡：將生成的樣例交互軌跡按輸入等價的原則進行合并；

第三步：獲得謂詞；

第四步：通過第三步得到行為模型的擴展有限自動機EFA，增加一個公共的初始狀態得到初始的EFA，再根據等價原則合并獲得最終的EFA。