第十章 數(shù)據(jù)流測(cè)試

第十章數(shù)據(jù)流測(cè)試東北大學(xué)軟件學(xué)院什么是數(shù)據(jù)流測(cè)試？東北大學(xué)軟件學(xué)院數(shù)據(jù)流測(cè)試指關(guān)注變量接收值的點(diǎn)和使用（或引用）這些值的點(diǎn)的結(jié)構(gòu)性測(cè)試形式。數(shù)據(jù)流測(cè)試指關(guān)注可以用作路徑測(cè)試的“真實(shí)性檢查”。數(shù)據(jù)流測(cè)試兩種基本方法：一組基本定義和一種統(tǒng)一的測(cè)試覆蓋指標(biāo)結(jié)構(gòu)測(cè)試；基于“程序片”的概念的測(cè)試。定義/使用測(cè)試東北大學(xué)軟件學(xué)院定義引用擁有程序圖G（P）的程序P和一組程序變量v。P中的所有路徑集合是PATHS（P）。定義節(jié)點(diǎn)東北大學(xué)軟件學(xué)院定義

節(jié)點(diǎn)n∈G（P）是變量v∈V的定義節(jié)點(diǎn)，記做DEF（v，n），當(dāng)且僅當(dāng)變量v的值由對(duì)應(yīng)節(jié)點(diǎn)n的語句片段處定義。

輸入語句、賦值語句、循環(huán)控制語句和過程調(diào)用，都是定義節(jié)點(diǎn)語句的例子。如果執(zhí)行對(duì)應(yīng)這種語句的節(jié)點(diǎn)，那么與該變量關(guān)聯(lián)的存儲(chǔ)單元的內(nèi)容就會(huì)改變。

使用節(jié)點(diǎn)東北大學(xué)軟件學(xué)院定義

節(jié)點(diǎn)n∈G（P）是變量v∈V的使用節(jié)點(diǎn)，記做USE（v，n），當(dāng)且僅當(dāng)變量v的值在對(duì)應(yīng)節(jié)點(diǎn)n的語句片段處使用。語句、賦值語句、條件語句、循環(huán)控制語句和過程調(diào)用，都是使用節(jié)點(diǎn)語句的例子。如果執(zhí)行對(duì)應(yīng)這種語句的節(jié)點(diǎn)，那么與該變量關(guān)聯(lián)的存儲(chǔ)單元的內(nèi)容會(huì)保持不變。

謂詞使用和計(jì)算使用東北大學(xué)軟件學(xué)院定義

使用節(jié)點(diǎn)USE（v，n）是一個(gè)謂詞使用（記做P-use），當(dāng)且僅當(dāng)語句n是謂詞語句；否則，USE（v，n）是計(jì)算使用（記做C-use）。

對(duì)應(yīng)于謂詞使用的節(jié)點(diǎn)永遠(yuǎn)有外度>=2，對(duì)應(yīng)于計(jì)算使用的節(jié)點(diǎn)永遠(yuǎn)有外度<=1。

定義-使用路徑東北大學(xué)軟件學(xué)院定義

關(guān)于變量v的定義一使用路徑（記做du-path）是PATHS（P）中的路徑，使得對(duì)某個(gè)v∈V，存在定義和使用節(jié)點(diǎn)DEF（v，m）和USE（v，n），使得m和n是該路徑的最初和最終節(jié)點(diǎn)。

定義-清除路徑東北大學(xué)軟件學(xué)院定義

關(guān)于變量v的定義清除路徑（記做dc-path），是具有最初和最終節(jié)點(diǎn)DEF（v，m）和USE（v，n）的PATHS（P)中的路徑，使得該路徑中沒有其他節(jié)點(diǎn)是v的定義節(jié)點(diǎn)。

傭金問題的程序圖891011127131415161718192122232425202627282930343132333538363739404142傭金問題變量的定義/使用節(jié)點(diǎn)東北大學(xué)軟件學(xué)院變量定義節(jié)點(diǎn)使用節(jié)點(diǎn)lockPrice724stockPrice825barrelPrice926totalLocks10,1616,21,24totalStocks11,1717,22,25totalBarrels12,1818,23,26locks13,1914,16stocks1517barrels1518lockSales2427stockSales2527barrelSales2627sales2728,29,33,34,37,38commission31,32,33,36,37,3832,33,37,41lockPrice、stockPrice和barrelPrice定義/使用路徑東北大學(xué)軟件學(xué)院變量路徑節(jié)點(diǎn)是定義清除嘛？lockPrice7，…，24是stockPrice8，…，25是barrelPrice9，…，26是locks、stocks和barrels的定義/使用路徑東北大學(xué)軟件學(xué)院變量路徑節(jié)點(diǎn)是定義清除嘛？locks13，14是locks13，14，15，16是locks19，20，14是locks19，20，14，15，16是stocks15，…，17是barrels15，…，18是totalLocks的定義/使用路徑東北大學(xué)軟件學(xué)院變量路徑節(jié)點(diǎn)是定義清除嘛？totalLocks10，16是totalLocks10，21否totalLocks10，24否totalLocks16，16totalLocks16，21是totalLocks16，24是sales的定義/使用路徑東北大學(xué)軟件學(xué)院變量路徑節(jié)點(diǎn)是定義清除嘛？sales27，28是sales27，29是sales27，33是sales27，28，29，34是sales27，28，29，34，35，36，37是sales27，28，29，38是commission的定義/使用路徑變量路徑節(jié)點(diǎn)是否可行？是定義清除嘛？commission31，32是是commission31，33是否commission31，37否-commission31，41是否commission32，32是是commission32，33是是commission32，37否-commission32，41是否commission33，32否-commission33，33是是commission33，37否-commission33，41是是commission36，32否-commission36，33否-commission36，37是是commission36，41是否commission37，32否-commission37，33否-commission37，37是是commission37，41是是commission38，32否-commission38，33否-commission38，37否-commission38，41是是全定義準(zhǔn)則東北大學(xué)軟件學(xué)院定義

集合T滿足程序P的全定義準(zhǔn)則，當(dāng)且僅當(dāng)所有變量v∈V，T包含從v的每個(gè)定義節(jié)點(diǎn)到v的一個(gè)使用的定義清除路徑。

T是擁有變量集合V的程序p的程序圖G（p）中的一個(gè)路徑集合。全使用準(zhǔn)則東北大學(xué)軟件學(xué)院定義

集合T滿足程序p的全使用準(zhǔn)則，當(dāng)且僅當(dāng)所有變量v∈V，T包含從v的每個(gè)定義節(jié)點(diǎn)到v的所有使用，以及到所有USE（v，n）后續(xù)節(jié)點(diǎn)的定義清除路徑。

全謂詞使用／部分計(jì)算使用準(zhǔn)則

東北大學(xué)軟件學(xué)院定義集合T滿足程序p的全謂詞使用／部分計(jì)算使用準(zhǔn)則，當(dāng)且僅當(dāng)所有變量v∈V，T包含從v的每個(gè)定義節(jié)點(diǎn)到v的所有謂詞使用的定義清除路徑，并且如X-v的一個(gè)定義沒有謂詞使用，則定義清除路徑導(dǎo)致至少一個(gè)計(jì)算使用。全計(jì)算使用／部分謂詞使用準(zhǔn)則

東北大學(xué)軟件學(xué)院定義集合T滿足程序P的全計(jì)算使用／部分謂詞使用準(zhǔn)則，當(dāng)且僅當(dāng)所有變量v∈v，T包含從v的每個(gè)定義節(jié)點(diǎn)到v的所有計(jì)算使用的定義清除路徑，并且如果v的一個(gè)定義沒有計(jì)算使用，則定義清除路徑導(dǎo)致至少一個(gè)謂詞使用。全定義-使用路徑準(zhǔn)則

東北大學(xué)軟件學(xué)院定義集合T滿足程序p的全定義一使用路徑準(zhǔn)則，當(dāng)且僅當(dāng)所有變量v∈V，T包含從v的每個(gè)定義節(jié)點(diǎn)到v的所有使用，以及到所有USE(v，n)后續(xù)節(jié)點(diǎn)的定義清除路徑，并且這些路徑要么有一次的環(huán)經(jīng)過，要么沒有環(huán)路。數(shù)據(jù)流覆蓋指標(biāo)Rapps/Weyuker層次結(jié)構(gòu)東北大學(xué)軟件學(xué)院全路徑全定義-使用路徑全使用全計(jì)算使用/部分謂詞使用全謂詞使用/部分計(jì)算使用全定義全謂詞使用全邊全節(jié)點(diǎn)基于程序片的測(cè)試東北大學(xué)軟件學(xué)院定義給定一個(gè)程序P和P中的一個(gè)變量集合V，變量集合V在語句n上的一個(gè)片，記做S(V，n)，是P中對(duì)V中的變量值作出貢獻(xiàn)的所有語句集合。定義給定一個(gè)程序P和一個(gè)給出語句及語句片段編號(hào)的程序圖G(P)，以及P中的一個(gè)變量集合V，變量集合V在語句片段n上的一個(gè)片，記做S(V，n)，是P中在n以前對(duì)V中的變量值作出貢獻(xiàn)的所有語句片段編號(hào)的集合。使用節(jié)點(diǎn)和定義節(jié)點(diǎn)東北大學(xué)軟件學(xué)院USE關(guān)系適合五種形式的使用：謂詞使用用在謂詞(判斷)中。計(jì)算使用用在計(jì)算中。輸出使用用于輸出。定位使用用于定位(指針、下標(biāo))。迭代使用迭代(內(nèi)部計(jì)數(shù)器、循環(huán)指示)。標(biāo)識(shí)兩種定義節(jié)點(diǎn)：輸入定義通過輸入定義。賦值定義通過賦值定義。變量locks上的片

東北大學(xué)軟件學(xué)院S1：S(locks，13)={13)S2：S(locks，14)={13，14，19，20}S3：S(locks，16)={13，14，16，19，20)S4：S(locks，19)={19}變量stocks和barrels上的片

東北大學(xué)軟件學(xué)院S5：S(stocks，15)={13，14，15，19，20}S6：S(stocks，17)={13，14，15，17，19，20}S7：S(barrels，15)={13，14，15，19，20}S8：S(barrels，18)={13，14，15，18，19，20}totalLocks、totalStocks和totalBarrels的片

東北大學(xué)軟件學(xué)院S9：S(totalLocks，10)={10}S10：S(totalLocks，16)={10，13，14，16，19，20}S11：S(totalLocks，21)={10，13，14，16，19，20}S12：S(totalStocks，11)={11}S13：S(totalStocks，17)={11，13，14，15，17，19，20}S14：S(totalStocks，22)={11，13，14，15，17，19，20}S15：S(totalBarrels，12)={12}S16：S(totalBarrels，18)={12，13，14，15，18，19，20}S17：S(totalBarrels，23)={12，13，14，15，18，19，20}賦值定義東北大學(xué)軟件學(xué)院S18：S(lockPrice，24)={7}S19：S(stockPrice，25)={8}S20：S(barrelPrice，26)={9}S21：S(lockSales，24)={7，10，13，14，16，19，20，24}S22：S(stockSales，25)={8，11，13，14，15，17，19，20，25}S23：S(barrelSales，26)={9，12，13，14，15，18，19，20，26}Sales上的片東北大學(xué)軟件學(xué)院S24：S(sales，27)={7，8，9，10，11，12，13，14，15，16，17，18，19，20，24，25，26，27}S25：S(sales，28)={7，8，9，10，11，12，13，14，15，16，17，18，19，20，24，25，26，27}S26：S(sales，29)={7，8，9，10，11，12，13，14，15，16，17，18，19，20，24，25，26，27}S27：S(sales，33)={7，8，9，10，11，12，13，14，15，16，17，18，19，20，24，25，26，27}S28：S(sales，34)={7，8，9，10，11，12，13，14，15，16，17，18，19，20，24，25，26，27}S29：S(sales，37)={7，8，9，10，11，12，13，14，15，16，17，18，19，20，24，25，26，27}S30：S(sales，38)={7，8，9，10，11，12，13，14，15，16，17，18，19，20，24，25，26，27}S30=S10∪

S13∪

S16∪

S21∪

S22∪

S23Commission上的片東北大學(xué)軟件學(xué)院S31：S(commission，31)={31}S32：S(commission，32)={31，32}S33：S(commission，33)={7，8，9，10，11，12，13，14，15，16，17，18，19，20，24，25，26，27，29，30，31，32，33}S34：S(commission，36)={36}S35：S(commission，37)={7，8，9，10，11，12，13，14，15，16，17，18，19，20，24，25，26，27，36，37}S