發(fā)布時(shí)間：2022-01-02 11:54

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

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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

事件類型

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

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

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

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



本文編號(hào)：3564130