測(cè)試原語：存儲(chǔ)器故障最小檢測(cè)序列的統(tǒng)一特征

肖寅東，王恩笙，路杉杉，戴志堅(jiān)

（電子科技大學(xué)自動(dòng)化工程學(xué)院，成都 611731）

1 引言

March 算法作為一類測(cè)試向量生成算法，在存儲(chǔ)器測(cè)試領(lǐng)域被廣泛使用，因其卓越的測(cè)試效率和高效的故障覆蓋能力被國內(nèi)外學(xué)術(shù)界廣泛研究[1]。業(yè)界對(duì)March 算法的理解也在不斷深化，每一次新角度、高層次理論的誕生都帶來了應(yīng)用層面的進(jìn)步。近年來，JIDIN 等人提出了基于地址方向和前一存儲(chǔ)單元狀態(tài)的單元趨勢(shì)理論[2]，并將該理論用于March 算法的非連接性靜態(tài)故障覆蓋率分析和任務(wù)自動(dòng)生成，取得了顯著進(jìn)展[3-4]。然而，F(xiàn)inFET 等工藝帶來的動(dòng)態(tài)故障問題仍存在挑戰(zhàn)。

應(yīng)用層面上需求的變化也引領(lǐng)了March 算法理論研究的方向。隨著分層存儲(chǔ)器診斷技術(shù)越來越受業(yè)界關(guān)注[5]，業(yè)界對(duì)具有可擴(kuò)展性和靈活性的測(cè)試原語提出了更高的要求。2000 年，GOOR 等人[6]提出了故障原語的概念，其可用于表達(dá)各類行為級(jí)故障，該模型被廣泛用于描述存儲(chǔ)器故障。在此基礎(chǔ)上，AL-ARS 等人提出了測(cè)試原語的概念，希望構(gòu)建一套具有擴(kuò)展性和靈活性的專用于檢測(cè)故障的模型，以解決故障原語模型無法直接用于測(cè)試診斷的問題。然而，AL-ARS 等人提出的測(cè)試原語理論[7]重點(diǎn)在于保證原語的唯一性和簡約性，并將被測(cè)單元狀態(tài)和測(cè)試算法的敏化、檢測(cè)操作進(jìn)行聯(lián)動(dòng)分析，這種特性導(dǎo)致其完備性難以證明，因此無法應(yīng)用在算法分析和任務(wù)生成中。

本文以故障原語為基礎(chǔ)，定義了新的測(cè)試原語，用于描述覆蓋對(duì)應(yīng)故障所需March 算法的共性特征，提出的測(cè)試原語具有完備性、唯一性和簡約性的特點(diǎn)。研究了測(cè)試原語的構(gòu)建方法，建立了涵蓋非連接性靜態(tài)故障的測(cè)試原語庫。通過對(duì)測(cè)試原語模型的討論，將存儲(chǔ)器的功能級(jí)故障模型與測(cè)試原語聯(lián)系起來，簡化對(duì)March 算法故障覆蓋率的分析。

2 故障模型及其測(cè)試原語

2.1 存儲(chǔ)器故障模型

存儲(chǔ)器的故障模型按照敏化故障的操作數(shù)可以分為靜態(tài)故障和動(dòng)態(tài)故障[8]。靜態(tài)故障根據(jù)故障之間是否會(huì)相互影響分為簡單故障和連接性故障。本文要考慮非連接性靜態(tài)故障，非連接性靜態(tài)故障包含單一單元故障和耦合故障，耦合故障涉及多個(gè)存儲(chǔ)單元，本文只考慮涉及兩個(gè)存儲(chǔ)單元的情況，即雙單元耦合故障。單一單元故障是指存儲(chǔ)器故障獨(dú)立地存在于某一存儲(chǔ)單元，不會(huì)影響其他單元。雙單元故障涉及兩個(gè)耦合的存儲(chǔ)單元，通常把它們稱為攻擊單元a 和受害單元v。

單一單元故障的故障原語表達(dá)式為，其中S 代表觸發(fā)存儲(chǔ)器故障行為的操作或狀態(tài)，F(xiàn) 代表故障單元的狀態(tài)值，R 代表讀操作的邏輯輸出電平[9]。雙單元耦合故障的故障原語表達(dá)式為，其中Sa 和Sv 分別代表觸發(fā)存儲(chǔ)器故障時(shí)攻擊單元和受害單元的狀態(tài)或操作。Sa 和Sv 不能同時(shí)為操作[10]。

2.2 測(cè)試原語

隨著制造工藝的持續(xù)演進(jìn)，存儲(chǔ)器出現(xiàn)了許多新型故障，需要March 算法持續(xù)適應(yīng)新的故障類型。高測(cè)試復(fù)雜度的測(cè)試算法使算法的分析、驗(yàn)證和生成都面臨困難。

定義測(cè)試原語來描述可檢測(cè)對(duì)應(yīng)故障原語的March 算法的共性特征，可從故障原語直接得到每一個(gè)故障原語對(duì)應(yīng)的一個(gè)測(cè)試原語。測(cè)試原語的定義基于故障原語，用形如D 的形式描述檢測(cè)對(duì)應(yīng)故障所需操作的特征，其中為敏化操作集，是故障原語的集合，D 為檢測(cè)操作特征描述符，用于描述可檢驗(yàn)敏化后單元狀態(tài)的檢測(cè)操作集特征。同樣，雙單元故障可用形如D 的測(cè)試原語進(jìn)行檢測(cè)。

測(cè)試原語與故障原語有相同的敏化操作集，因此，推導(dǎo)測(cè)試原語的關(guān)鍵在于研究檢測(cè)操作特征描述符的適用情況。檢測(cè)操作特征描述符包括檢測(cè)故障的讀操作（稱為檢測(cè)操作）和描述檢測(cè)操作位置的特殊符號(hào)。采用類似正則表達(dá)式的符號(hào)來表示檢測(cè)操作位置，測(cè)試原語中常用的符號(hào)及其含義如表1 所示。檢測(cè)操作特征描述符按地址變化方向分為兩種情況，a?v表示地址變化方向?yàn)楣魡卧蚴芎卧闅v，v?a則相反。在本文提出此表示方法之前，一般使用a>v 和a

表1 測(cè)試原語中常用的符號(hào)及其含義

按照下述方法推導(dǎo)測(cè)試原語，其中雙單元耦合故障的故障單元指受害單元。

1）如果故障單元在敏化時(shí)是讀操作，且此讀操作的期望狀態(tài)和故障原語中的R 不同時(shí)，D=?（空集），否則在檢測(cè)操作描述符中一定有檢測(cè)操作。2）檢測(cè)操作的期望狀態(tài)由故障單元敏化的狀態(tài)確定，即敏化操作后的狀態(tài)或者敏化狀態(tài)的狀態(tài)。3）單一單元故障無論故障單元的敏化是狀態(tài)還是操作，檢測(cè)操作前都加“#”。4）雙單元故障根據(jù)攻擊單元和受害單元敏化的不同方式，分為以下三種情況。a.如果攻擊單元在敏化時(shí)是操作，在a?v 時(shí)，檢測(cè)操作前加“^”，檢測(cè)操作后加“*”，v?a 時(shí)檢測(cè)操作前加“;”，在敏化操作之后加“*”。b.如果受害單元在敏化時(shí)是操作，在a?v 和v?a時(shí)，檢測(cè)操作都在敏化操作之后，檢測(cè)操作前加“#”。c.如果攻擊單元和受害單元在敏化時(shí)都是狀態(tài)，又分為兩種情況，即攻擊單元和受害單元分別在當(dāng)前地址單元（CAC），當(dāng)前地址單元是March 元素行進(jìn)到的單元，即訪存操作即將施加到的單元。當(dāng)攻擊單元在CAC 時(shí)，檢測(cè)操作前加“^”，其后加“*”；當(dāng)受害單元在CAC 時(shí)，檢測(cè)操作在敏化之后。

這里需要解釋的是，如果攻擊單元在敏化時(shí)是操作，那么在a?v 和v?a 兩個(gè)方向上檢測(cè)操作位置的不同是為了保證檢測(cè)操作在時(shí)間上滯后于故障敏化。以上測(cè)試原語的獲得方法也適用于動(dòng)態(tài)故障，因?yàn)閯?dòng)態(tài)故障的檢測(cè)也是在保證故障敏化條件之后通過讀操作完成的，只要其檢測(cè)操作滿足以上生成規(guī)則的條件，也能很容易地表示出其測(cè)試原語。

例如，錯(cuò)誤讀故障的故障原語為，由其故障原語可知，故障單元的敏化是讀操作，且讀操作之后的狀態(tài)與故障原語中的R 不同，所以D=?，其敏化操作集為，所以得到故障原語的測(cè)試原語為。

而針對(duì)攻擊單元在敏化時(shí)是操作這種情況，測(cè)試原語的生成較為復(fù)雜，通過干擾耦合故障舉例說明。故障原語CFdsrx中的敏化條件集為，攻擊單元的敏化是操作Rx，受害單元的敏化是狀態(tài)y，所以檢測(cè)操作是Ry，因?yàn)楣魡卧诿艋瘯r(shí)是操作，所以在敏化操作之后增加0 個(gè)或多個(gè)任意訪存操作都不影響故障檢測(cè)，故添加“*”，在這里要注意的是，添加的多個(gè)訪存操作行進(jìn)完最后的狀態(tài)要保持和受害單元敏化前的狀態(tài)相同。根據(jù)上述規(guī)則可得D 的表達(dá)式為

由上述規(guī)則得到本文涉及的故障集的測(cè)試原語庫，如表2 所示。

需要注意兩種特殊情況：1）CFdsrx 故障中當(dāng)x=y時(shí)，檢測(cè)為空，但是敏化的讀操作必須在March 元素的第一個(gè)位置，根據(jù)上述描述，其測(cè)試原語可表達(dá)為(x=y)；2）CFst 故障中受害單元在CAC 時(shí)，當(dāng)x=y 時(shí)的一個(gè)測(cè)試原語為;Ry。

3 測(cè)試原語性質(zhì)證明

本文提出的測(cè)試原語針對(duì)目標(biāo)故障原語而言具有完備性、唯一性與簡約性的特點(diǎn)。若不具備完備性則無法保證其對(duì)任一March 算法均可進(jìn)行故障覆蓋率分析的能力。唯一性保證某March 算法滿足測(cè)試原語描述時(shí)，一定能夠檢測(cè)到對(duì)應(yīng)的故障。簡約性保證測(cè)試原語可直接應(yīng)用于測(cè)試序列的最優(yōu)化生成。

測(cè)試原語在敏化操作的基礎(chǔ)上最多增加一個(gè)讀取操作，因此其簡約性較易得到保證。針對(duì)測(cè)試原語的完備性問題，本文采用反證法證明，可假設(shè)存在某測(cè)試原語無法涵蓋的March 算法，但該算法能夠檢測(cè)該原語對(duì)應(yīng)的故障，分析這類算法的存在性，若不存在，則可證明測(cè)試原語的完備性。測(cè)試原語的唯一性只需同時(shí)保證以下三個(gè)條件就能得到證明：敏化操作集與故障原語的敏化操作集相同；檢測(cè)操作在時(shí)間上滯后于敏化操作；在敏化操作完成之后、檢測(cè)操作進(jìn)行之前，不能對(duì)故障單元做任何改變狀態(tài)的操作。在推導(dǎo)測(cè)試原語時(shí)，其唯一性得到證明，在此不再贅述。

March 算法由多個(gè)March 元素M 構(gòu)成，每個(gè)March 元素由地址變化方向（可能取值為{?,?,?}）和訪存操作集（O={op0,op1,...}，opn∈{W0,W1,R0,R1}）組成。

由檢測(cè)操作特征描述符的定義可知，當(dāng)D≠? 時(shí)，D 中的操作集Od 與敏化操作集Os 的關(guān)系包含以下可能：

其中，“;”為March 算法行進(jìn)一次的結(jié)束標(biāo)志，“[...]”表示括號(hào)內(nèi)的內(nèi)容可選。上面4 式可描述20 種可能出現(xiàn)的位置關(guān)系，加上D=?，一共有21 種需討論的情況。

在以上檢測(cè)操作與敏化操作的21 種關(guān)系中，假設(shè)式（2）中O1 存在，即;O1Od[O2]Os[O3]，如果O1 為一個(gè)讀操作，且讀操作的期望狀態(tài)與故障單元狀態(tài)不一樣時(shí)，這樣的讀寫序列是不符合March 規(guī)則的；如果O1 為讀操作，且其期望的狀態(tài)與故障單元相同時(shí)，那么此時(shí)O1 就是Od；如果O1 中有寫操作，那么寫操作會(huì)改變故障單元狀態(tài)，將無法檢測(cè)故障，所以O(shè)1 存在的式子不滿足測(cè)試原語的條件。式（5）中O2 存在時(shí)也是同樣的狀況。式（3）中所有式子都不能滿足檢測(cè)操作在時(shí)間上滯后于敏化操作，故也不符合測(cè)試原語的條件。綜上所述，將以上位置關(guān)系化簡為

式（6）～（8）再加上D=?，只需考慮剩余的11 種組合。現(xiàn)采用反證法來證明本文涉及的故障集的測(cè)試原語的完備性。

3.1 單一單元故障測(cè)試原語完備性證明

1）式（6）可分為4 種情況：①O2 和O3 都存在；②O2 存在，O3 不存在；③O2 不存在，O3 存在；④O2 和O3 都不存在。針對(duì)這4 種情況的位置關(guān)系分別為;RxO2O3，;RxO2，;RxO3，;Rx。這幾種位置關(guān)系形成的測(cè)試原語都不能保證故障檢測(cè)在故障敏化之后，故其不可檢測(cè)狀態(tài)故障。

2）根據(jù)式（7）可知，位置關(guān)系有4 種：①O1 和O2都存在，位置關(guān)系為O1RxO2；②O1 存在，O2 不存在，位置關(guān)系為O1Rx；③O1 不存在，O2 存在，位置關(guān)系為RxO2；④O1 和O2 都不存在，位置關(guān)系為Rx。在O1 存在時(shí)，在故障敏化之后的多個(gè)訪存操作可能會(huì)改變故障單元的狀態(tài)，所以這類位置關(guān)系形成的測(cè)試原語不能檢測(cè)狀態(tài)故障，即①和②中的位置關(guān)系形成的測(cè)試原語不能檢測(cè)此故障。而③和④的位置關(guān)系形成的測(cè)試原語可以檢測(cè)狀態(tài)故障，因?yàn)樵跈z測(cè)操作之后的訪存操作對(duì)故障檢測(cè)沒有影響，將③和④中位置關(guān)系形成的測(cè)試原語合并為Rx。

3）根據(jù)式（8）可得，O1 存在，此時(shí)的位置關(guān)系為O1;Rx，在故障敏化之后的訪存操作可能改變故障單元的狀態(tài)，使得故障不能被檢測(cè)。O1 不存在，此時(shí)的位置關(guān)系為;Rx，此位置關(guān)系形成的測(cè)試原語可以檢測(cè)狀態(tài)故障。

經(jīng)過上述分析，存在兩種測(cè)試原語Rx 和;Rx，可以檢測(cè)狀態(tài)故障，而這兩種測(cè)試原語可以合并為#Rx。經(jīng)分析，除了#Rx 以外的其他形式的測(cè)試原語均不能檢測(cè)狀態(tài)故障，狀態(tài)故障測(cè)試原語的完備性得到證明。

讀破壞故障是讀操作導(dǎo)致故障單元的狀態(tài)發(fā)生翻轉(zhuǎn)，此讀操作將錯(cuò)誤狀態(tài)讀出，所以敏化故障的讀操作可以直接檢測(cè)出故障，此故障的測(cè)試原語為，即其測(cè)試原語的D 為?。因?yàn)橹挥蠷x 一個(gè)操作，并不需要指定其位置，也不管其前后是否有訪存操作，所以可以得到其最后的測(cè)試原語為，證明了測(cè)試原語的完備性。錯(cuò)誤讀故障測(cè)試原語完備性分析與讀破壞故障測(cè)試原語分析類似，在這里不再過多描述。

3.2 雙單元耦合故障測(cè)試原語完備性證明

本文分3 種不同的情況對(duì)雙單元耦合故障測(cè)試原語的完備性進(jìn)行證明：1）攻擊單元與受害單元在敏化時(shí)都是狀態(tài)；2）攻擊單元在敏化時(shí)是操作；3）受害單元在敏化時(shí)是操作。

3.2.1 攻擊單元與受害單元在敏化時(shí)都是狀態(tài)

狀態(tài)耦合故障在敏化時(shí)攻擊單元和受害單元都是狀態(tài)，其故障原語為。假設(shè)存在其他形式的測(cè)試原語可以檢測(cè)狀態(tài)耦合故障。

1）根據(jù)式（6）可知，O2 存在的位置關(guān)系為;RyO2O3 和;RyO2，按照這兩種位置關(guān)系形成的測(cè)試原語可以檢測(cè)x≠y 時(shí)攻擊單元在CAC 情況下的狀態(tài)耦合故障。O2 不存在的位置關(guān)系為;RyO3 和;Ry，按其形成的測(cè)試原語可以檢測(cè)x=y 時(shí)攻擊單元在CAC 時(shí)的狀態(tài)耦合故障。因?yàn)闄z測(cè)操作之后的訪存操作不影響故障檢測(cè)，所以上述位置關(guān)系形成的測(cè)試原語可總結(jié)為^Ry*。

2）根據(jù)式（7）可知，O1 存在的位置關(guān)系為O1RyO2 和O1Ry，都在故障敏化之后增加了多個(gè)訪存操作，這些操作如果改變了故障單元的狀態(tài)，將導(dǎo)致其不能被檢測(cè)。O1 不存在的位置關(guān)系為RyO2 和Ry，按這兩種位置關(guān)系形成的測(cè)試原語可檢測(cè)受害單元在CAC 時(shí)的狀態(tài)耦合故障。經(jīng)過分析與合并，得到測(cè)試原語為Ry。

3）根據(jù)式（8）可知，O1 存在時(shí)的位置關(guān)系為O1;Ry，按此位置關(guān)系形成的測(cè)試原語在故障敏化之后增加了多個(gè)訪存操作，這些操作如果改變了故障單元的狀態(tài)，將導(dǎo)致其不能被檢測(cè)。O1 不存在時(shí)的位置關(guān)系為;Ry，按其形成的測(cè)試原語，在x=y 時(shí)可以檢測(cè)受害單元在CAC 時(shí)的狀態(tài)耦合故障，而在x≠y 時(shí)，敏化條件不能得到保證，因?yàn)樵谝粋€(gè)March 元素開始前，存儲(chǔ)陣列會(huì)被寫為相同的狀態(tài)。

經(jīng)過上述分析，將形成的位置關(guān)系Ry 和^Ry*合并，得到測(cè)試原語：

由此可知，除給出的測(cè)試原語的形式外，不存在其他形式的測(cè)試原語可以檢測(cè)狀態(tài)耦合故障，其完備性得到證明。

3.2.2 攻擊單元在敏化時(shí)是操作

干擾耦合CFdsrx 在敏化時(shí)，攻擊單元的敏化是操作，其故障原語為，測(cè)試原語在表2 中可以得到。假設(shè)存在其他形式的測(cè)試原語可以檢測(cè)CFdsrx，分析過程如下。

1）根據(jù)式（6）可知，O2 存在時(shí)的位置關(guān)系為;RyO2O3 和;RyO2，按其形成的測(cè)試原語，在x≠y 時(shí)可以檢測(cè)a?v 方向上的CFdsrx。O2 不存在的位置關(guān)系為;RyO3 和;Ry，按其形成的測(cè)試原語，在x=y 時(shí)可以檢測(cè)a?v 方向上的CFdsrx。將上述位置關(guān)系形成的測(cè)試原語進(jìn)行整理，發(fā)現(xiàn)在Ry 之后添加訪存操作可檢測(cè)x≠y 時(shí)a?v 方向上的CFdsrx，不添加訪存操作可檢測(cè)x=y 時(shí)a?v 方向上的CFdsrx，可以加入“*”得到測(cè)試原語^Ry*（a?v）。

2）根據(jù)式（7）可以得到4 種位置關(guān)系，但是這幾種位置關(guān)系中敏化操作與檢測(cè)操作在相同的March 元素中，而在當(dāng)前地址單元中操作的是攻擊單元，敏化操作和檢測(cè)操作都操作在攻擊單元上，而故障檢測(cè)時(shí)應(yīng)該保證檢測(cè)操作操作在受害單元上，所以這4 種位置關(guān)系形成的測(cè)試原語不能檢測(cè)CFdsrx 故障。

3）根據(jù)式（8）可知，O1 存在時(shí)的位置關(guān)系為O1;Ry，按其形成的測(cè)試原語，在x≠y 時(shí)可檢測(cè)v?a方向上的CFdsrx 故障。O1 不存在時(shí)的位置關(guān)系為;Ry，按其形成的測(cè)試原語，在x=y 時(shí)可檢測(cè)v?a 方向上的CFdsrx 故障。將2 種位置關(guān)系形成的測(cè)試原語合并得*;Ry（v?a）。

經(jīng)過上述分析，得到可檢測(cè)CFdsrx 故障的測(cè)試原語為

由此可得，不存在其他形式的測(cè)試原語可檢測(cè)此故障，證明了其測(cè)試原語的完備性。CFdsxwx

3.2.3 受害單元敏化時(shí)是操作

1）根據(jù)式（6）可以得到4 種位置關(guān)系，因?yàn)椴荒鼙ＷC故障檢測(cè)在時(shí)間上滯后于故障敏化，因此這4 種位置關(guān)系形成的測(cè)試原語不能檢測(cè)轉(zhuǎn)換耦合故障。

4 測(cè)試原語的使用

測(cè)試原語的作用是作為故障原語與March 算法之間的橋梁來簡化對(duì)March 算法的研究。測(cè)試原語描述的是故障原語對(duì)應(yīng)的最小測(cè)試序列。為了將單元狀態(tài)與故障敏化、檢測(cè)操作解耦，在測(cè)試原語的基礎(chǔ)上，生成其狀態(tài)元組，來表示滿足最小檢測(cè)序列檢測(cè)故障所需的狀態(tài)要求。同時(shí)也針對(duì)March 算法生成其在行進(jìn)過程中的狀態(tài)元組，來描述其行進(jìn)到某一訪存操作時(shí)整個(gè)存儲(chǔ)陣列的狀態(tài)。在此基礎(chǔ)之上，將測(cè)試原語與March 算法進(jìn)行匹配，完成對(duì)March 算法的分析。

4.1 狀態(tài)元組的定義及生成

測(cè)試原語的狀態(tài)元組表示的是故障檢測(cè)需要的狀態(tài)條件，March 算法的狀態(tài)元組表示的是March 算法行進(jìn)到某一訪存操作的存儲(chǔ)陣列的狀態(tài)。狀態(tài)元組的表達(dá)式為，其中LAS 表示低地址單元狀態(tài)，CAS 表示當(dāng)前地址單元狀態(tài)，HAS 表示高地址單元狀態(tài)。LAS/CAS/HAS∈{0,1,x}，其中0 表示存儲(chǔ)單元的狀態(tài)為0，1 表示存儲(chǔ)單元的狀態(tài)為1，x 表示不關(guān)心存儲(chǔ)單元是什么狀態(tài)。

4.1.1 測(cè)試原語狀態(tài)元組的生成

測(cè)試原語狀態(tài)元組的生成主要取決于攻擊單元與受害單元的敏化，耦合故障測(cè)試原語的推導(dǎo)步驟可以總結(jié)如下。1）獲得測(cè)試原語的敏化操作集。2）敏化操作集中有操作，將操作所需的狀態(tài)放置在狀態(tài)元組中當(dāng)前地址單元，作為其敏化狀態(tài)，敏化操作集中無操作，將其中任意狀態(tài)放置在當(dāng)前地址單元。去掉敏化操作集中當(dāng)前已使用的敏化條件。3）根據(jù)攻擊單元和受害單元的相對(duì)地址位置，使用敏化操作集中剩余的敏化條件確定高地址單元狀態(tài)或低地址單元狀態(tài)，另一個(gè)元素被置為x。4）得到其狀態(tài)元組之后，保留其敏化時(shí)所需的操作以及測(cè)試原語中的D，將狀態(tài)元組放在操作之前，形成帶狀態(tài)元組的測(cè)試原語。如果敏化是狀態(tài)，只保留狀態(tài)元組和D 即可。

單一單元故障測(cè)試原語的狀態(tài)元組只需將狀態(tài)元組中的當(dāng)前地址單元狀態(tài)改為故障敏化時(shí)所需的狀態(tài)，高、低地址單元狀態(tài)置為x。其中敏化操作所需的狀態(tài)可以分以下情況討論：①當(dāng)敏化操作是讀操作時(shí)，那么敏化操作所需狀態(tài)為此讀操作期望讀出的操作，如r0 中的狀態(tài)0；②當(dāng)敏化操作是寫操作時(shí)，敏化操作所需的狀態(tài)為寫操作進(jìn)行前的狀態(tài)，如0w1 中的狀態(tài)0；③當(dāng)敏化操作是狀態(tài)時(shí)，敏化操作所需的狀態(tài)為當(dāng)前狀態(tài)，如狀態(tài)0 中的0。

狀態(tài)故障敏化操作為0 時(shí)，測(cè)試原語為<0>#R0，其測(cè)試原語的狀態(tài)元組為，得到帶狀態(tài)元組的測(cè)試原語為#R0。轉(zhuǎn)化耦合故障在故障敏化時(shí)，攻擊單元為0，受害單元為1w0 時(shí)的測(cè)試原語為<0;1w0>#R0，可以得到其敏化故障集為<0;1w0>，在故障敏化時(shí)是有操作的，那么狀態(tài)元組的CAS 為1，此時(shí)CAS 表示的是受害單元敏化所需的狀態(tài)，假設(shè)攻擊單元和受害單元的相對(duì)地址關(guān)系為攻擊單元地址高于受害單元地址，那在狀態(tài)元組中的HAS 寫入攻擊單元敏化所需的狀態(tài)即為1，LAS 置為x，所以其狀態(tài)元組為，得到帶狀態(tài)元組的測(cè)試原語w0#R0。

4.1.2 March 算法中狀態(tài)元組的生成

March 算法中的狀態(tài)元組包括每個(gè)訪存操作進(jìn)行前后的狀態(tài)元組和訪存操作組合起來形成帶狀態(tài)的March 表達(dá)式。整個(gè)March 算法狀態(tài)元組的生成要以March 元素為單位，每個(gè)March 元素中第一個(gè)訪存操作前后的狀態(tài)元組生成較為復(fù)雜，從第二個(gè)訪存操作開始，其前面的狀態(tài)元組為上一個(gè)訪存操作的操作后狀態(tài)元組，為了簡潔表達(dá)，只寫每個(gè)訪存操作前的狀態(tài)元組。操作后狀態(tài)元組根據(jù)操作不同而不同，如果是讀操作，不會(huì)改變存儲(chǔ)單元狀態(tài)，其操作后狀態(tài)元組與操作前狀態(tài)元組相同。若是寫操作，其只會(huì)改變當(dāng)前地址單元，所以其操作后狀態(tài)元組的高、低地址單元狀態(tài)不變，只將當(dāng)前地址單元狀態(tài)改寫為寫操作進(jìn)行之后的狀態(tài)，如進(jìn)行w0 操作，那么當(dāng)前地址狀態(tài)為0。在這里介紹兩個(gè)概念，March 元素的初始狀態(tài)和結(jié)束狀態(tài)。March 算法中從第二個(gè)March 元素開始，其初始狀態(tài)為前一March 元素的結(jié)束狀態(tài)，March 算法中第一個(gè)March 元素的初始狀態(tài)為設(shè)定的狀態(tài)或者為x。March 元素的結(jié)束狀態(tài)為March 元素中最后一個(gè)訪存操作操作后的狀態(tài)，如有March 元素↑(r0,r0)，最后一個(gè)訪存操作為r0，那么March 元素的結(jié)束狀態(tài)為0。

March 元素中第一個(gè)訪存操作狀態(tài)元組的推導(dǎo)需要明確March 元素的初始狀態(tài)和結(jié)束狀態(tài)，并可以得到以下結(jié)論。如果March 元素的地址遍歷順序?yàn)椤?，則狀態(tài)元組為<結(jié)束狀態(tài)，初始狀態(tài)，初始狀態(tài)>。如果March 元素的地址遍歷順序?yàn)椤?，則狀態(tài)元組為<初始狀態(tài)，初始狀態(tài)，結(jié)束狀態(tài)>。如果March 元素的地址遍歷順序?yàn)?，則狀態(tài)元組可以為以上兩種的任意一種。

March C+的表達(dá)式為?(w0);↑(r0,w1,r1);↑(r1,w0,r0);↓(r0,w1,r1);↓(r1,w0,r0);?(r0)，第一個(gè)March元素的地址遍歷順序?yàn)?，初始狀態(tài)為x，結(jié)束狀態(tài)為0，得到其狀態(tài)元組為<0,x,x>。第二個(gè)March 元素的地址遍歷順序?yàn)椤跏紶顟B(tài)為第一個(gè)March 元素的結(jié)束狀態(tài)，即為0，結(jié)束狀態(tài)為最后一個(gè)訪存操作操作后的狀態(tài)，最后一個(gè)訪存操作為r1，所以其結(jié)束狀態(tài)為1，那么第二個(gè)March 元素第一個(gè)訪存操作的狀態(tài)元組為<1,0,0>，圖1 為第一個(gè)訪存操作的狀態(tài)元組生成示意圖。其中March 表達(dá)式上方的方框記錄的是March 元素的結(jié)束狀態(tài)，表達(dá)式下的帶箭頭的線表示了狀態(tài)元組中狀態(tài)的來源。接下來的訪存操作的狀態(tài)元組為前一個(gè)訪存操作的操作后狀態(tài)元組。所以將第二個(gè)March 元素↑(r0,w1,r1);中的訪存操作與其狀態(tài)元組組合在一起，可以得到（此時(shí)每個(gè)訪存操作前都添加相同的地址遍歷順序）<1,0,0>↑r0<1,0,0>↑w1<1,1,0>↑r1。對(duì)March C+中的每個(gè)March 元素都進(jìn)行上述操作，得到帶狀態(tài)的March 表達(dá)式，表達(dá)式前的序號(hào)表示其為March 算法的第幾個(gè)元素，各March 元素之間用“;”分割，即

4.2 March 算法的分析過程

March 算法的分析過程就是將帶狀態(tài)元組的測(cè)試原語和帶狀態(tài)元組的March 表達(dá)式匹配，若是測(cè)試原語能得到匹配，那么測(cè)試原語能檢測(cè)的故障原語都能被March 檢測(cè)出。測(cè)試原語與March 算法的匹配要保證其狀態(tài)元組、敏化操作集、檢測(cè)操作特征描述符都得到匹配。其分析過程的框圖如圖2 所示。

圖2 分析過程框圖

測(cè)試原語的狀態(tài)元組想要得到匹配，要保證狀態(tài)元組中不為x 的狀態(tài)在March 算法的某個(gè)狀態(tài)元組中保持相同的狀態(tài)，而值為x 的狀態(tài)可以是任何狀態(tài)進(jìn)行匹配。保證敏化操作集匹配，要保證其所需操作及操作的順序都是相同的。而檢測(cè)操作特征描述符要得到匹配，要保證檢測(cè)操作特征描述符中的檢測(cè)操作和特殊符號(hào)都得到匹配。特殊符號(hào)“^”“#”“；”都是表征檢測(cè)操作與敏化操作位置關(guān)系的，只要二者的位置關(guān)系得到保證，這些符號(hào)就得到匹配，其各自表征的位置關(guān)系見表1。再加入“*”的位置，加入不改變敏化狀態(tài)的訪存操作即視為匹配。進(jìn)行匹配時(shí)，一般先進(jìn)行敏化操作和檢測(cè)操作的匹配，再進(jìn)行狀態(tài)元組的匹配，最后再進(jìn)行特殊符號(hào)的匹配。

4.1 節(jié)給出了March C+算法并給出了其帶狀態(tài)元組的表達(dá)式。根據(jù)表2 得到非連接性靜態(tài)故障的所有故障原語及其測(cè)試原語，并按照得到狀態(tài)元組的方法，共得到86 種帶狀態(tài)元組的測(cè)試原語，將其與帶狀態(tài)元組的March C+算法按照描述的匹配方法進(jìn)行匹配，可以得到March C+算法可檢測(cè)的故障原語，如表3 所示。其中每一行代表的是一種故障類型，中間一列是March C+算法能檢測(cè)此種故障類型的故障原語，耦合故障的故障原語后的a>v、a

5 結(jié)論

本文提出了新的測(cè)試原語，測(cè)試原語作為故障原語與測(cè)試算法之間的橋梁，形成高靈活度且可擴(kuò)展的分析單元，予以簡化March 算法的分析過程。針對(duì)本文所涉及的故障集，給出了其測(cè)試原語庫，并使用反證法證明了測(cè)試原語的完備性，其完備性得到保證，測(cè)試原語的唯一性和簡潔性也得到保證。本文所涉及的測(cè)試原語通過拓展?fàn)顟B(tài)元組的方式運(yùn)用在March算法的分析過程中，并對(duì)March C+算法進(jìn)行分析，將來會(huì)將測(cè)試原語用在自動(dòng)生成March 算法中，以達(dá)到簡化這些過程的目的。