給定某并發(fā)程序執(zhí)行軌跡,基于約束求解的并發(fā)測試方法將并發(fā)錯誤模式和執(zhí)行軌跡的可行性要求轉(zhuǎn)化為一組約束條件,通過約束求解生成暴露并發(fā)錯誤的并發(fā)執(zhí)行交織。該方法具有無誤報、低漏報率等諸多優(yōu)勢。并發(fā)程序在開發(fā)過程中會經(jīng)歷多次修改,產(chǎn)生多個程序版本。在并發(fā)程序的演化過程中,直接對各個版本的基于約束求解的并發(fā)程序測試,由于未有效利用版本變化信息,而造成重復測試,致使并發(fā)程序回歸測試面臨效率較低等問題。為了提高并發(fā)程序的回歸測試效率,本文提出了一種基于約束求解的并發(fā)程序回歸測試方法。該方法首先分析收集的兩個并發(fā)程序版本的執(zhí)行軌跡,計算兩個軌跡中每個內(nèi)存訪問事件的并發(fā)上下文;然后使用修改影響分析得到所有受修改語句影響的內(nèi)存訪問事件,組成影響集;最后采用考慮控制流的最大因果模型,將并發(fā)錯誤探測問題轉(zhuǎn)換為約束求解問題,對至少包含一個影響集事件的交織空間進行并發(fā)錯誤探測。該方法基于約束求解,可保證得到的并發(fā)錯誤一定是真實的,不會產(chǎn)生誤報。同時該方法基于修改影響分析,能夠保證得到的并發(fā)錯誤一定是由修改代碼生成的,不會重復報告以前版本已探測到的并發(fā)錯誤。該方法可有效減小并發(fā)程序錯誤探測的交織空間,提高回歸測試... 

【文章來源】：東南大學江蘇省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：70 頁

【學位級別】：碩士

【部分圖文】：

事件類型

東南大學碩士學位論文8圖2-2(a)是一個實例程序，該程序包含兩個線程(t1,t2)、三個共享變量(a,b,c)、兩個局部變量(r1,r2)和一個鎖對象l。圖2-2(b)是該程序的一條可行執(zhí)行軌跡。該執(zhí)行軌跡滿足順序一致性：（1）對于讀寫一致性要求：讀事件e10讀取共享變量b的值為-1，而該執(zhí)行軌跡中，發(fā)生在e10之前、距離e10最近、訪問共享變量b、且是寫操作的是寫事件e6，寫入的值為-1，滿足讀寫一致性要求。同樣地，讀事件e12以及e17均滿足讀寫一致性要求。（2）對于獨占鎖互斥要求：鎖釋放事件e7之前存在相同線程t1和相同鎖對象l的鎖獲取事件e2與之匹配，同樣鎖釋放事件e11和鎖獲取事件e9也可相互匹配，而且兩組acquire-release事件對未發(fā)生交織，因此滿足獨占鎖互斥要求。（3）對于Happen-Before關(guān)系要求：begin事件e8發(fā)生在fork事件e1之后，并且是線程t2的第一個事件；end事件e15發(fā)生在join事件e16之前，并且是線程t2的最后一個事件；兩者均滿足Happen-Before關(guān)系要求。2.2松弛的可行性公理順序一致性是執(zhí)行軌跡可行的必要條件，即如果某條執(zhí)行軌跡可以由并發(fā)程序?qū)嶋H運行得到，那么這條執(zhí)行軌跡一定符合順序一致性，但是反之則不一定�？尚行怨砜梢苑治瞿硹l可行執(zhí)行軌跡，推導得出其他可行的執(zhí)行軌跡，而且推導過程中無需其他信息。對于某并發(fā)程序P，將所有可以由P實際運行生成的所有執(zhí)行軌跡(無論是完整或者不完整的軌跡)組成的集合稱為Feasible(P)，即Feasible(P)中的執(zhí)行軌跡都是可行的�？尚行怨淼哪康木褪峭茖Й@得一個Feasible(P)。最為常見的可行性公理是由Mazurkiewicz的軌跡理論和Lamport的Happen-Before關(guān)系整合而成的[14,28]。該公理要求Feasible(P)是一個交織閉包，針

東南大學碩士學位論文8圖2-2(a)是一個實例程序，該程序包含兩個線程(t1,t2)、三個共享變量(a,b,c)、兩個局部變量(r1,r2)和一個鎖對象l。圖2-2(b)是該程序的一條可行執(zhí)行軌跡。該執(zhí)行軌跡滿足順序一致性：（1）對于讀寫一致性要求：讀事件e10讀取共享變量b的值為-1，而該執(zhí)行軌跡中，發(fā)生在e10之前、距離e10最近、訪問共享變量b、且是寫操作的是寫事件e6，寫入的值為-1，滿足讀寫一致性要求。同樣地，讀事件e12以及e17均滿足讀寫一致性要求。（2）對于獨占鎖互斥要求：鎖釋放事件e7之前存在相同線程t1和相同鎖對象l的鎖獲取事件e2與之匹配，同樣鎖釋放事件e11和鎖獲取事件e9也可相互匹配，而且兩組acquire-release事件對未發(fā)生交織，因此滿足獨占鎖互斥要求。（3）對于Happen-Before關(guān)系要求：begin事件e8發(fā)生在fork事件e1之后，并且是線程t2的第一個事件；end事件e15發(fā)生在join事件e16之前，并且是線程t2的最后一個事件；兩者均滿足Happen-Before關(guān)系要求。2.2松弛的可行性公理順序一致性是執(zhí)行軌跡可行的必要條件，即如果某條執(zhí)行軌跡可以由并發(fā)程序?qū)嶋H運行得到，那么這條執(zhí)行軌跡一定符合順序一致性，但是反之則不一定�？尚行怨砜梢苑治瞿硹l可行執(zhí)行軌跡，推導得出其他可行的執(zhí)行軌跡，而且推導過程中無需其他信息。對于某并發(fā)程序P，將所有可以由P實際運行生成的所有執(zhí)行軌跡(無論是完整或者不完整的軌跡)組成的集合稱為Feasible(P)，即Feasible(P)中的執(zhí)行軌跡都是可行的�？尚行怨淼哪康木褪峭茖Й@得一個Feasible(P)。最為常見的可行性公理是由Mazurkiewicz的軌跡理論和Lamport的Happen-Before關(guān)系整合而成的[14,28]。該公理要求Feasible(P)是一個交織閉包，針

【參考文獻】：
期刊論文
[1]并發(fā)缺陷暴露、檢測與規(guī)避研究綜述[J]. 蘇小紅,禹振,王甜甜,馬培軍.  計算機學報. 2015(11)
[2]一種Java字節(jié)碼優(yōu)化框架[J]. 張昱,劉玉宇.  計算機工程. 2008(02)

碩士論文
[1]基于并發(fā)程序切片的修改影響分析[D]. 張歡.東南大學 2017
[2]基于約束求解的并發(fā)程序錯誤探測[D]. 周敏敏.東南大學 2016



本文編號：3564130