測試原語：存儲器故障最小檢測序列的統一特征

肖寅東，王恩笙，路杉杉，戴志堅

（電子科技大學自動化工程學院，成都 611731）

1 引言

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

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

本文以故障原語為基礎，定義了新的測試原語，用于描述覆蓋對應故障所需March 算法的共性特征，提出的測試原語具有完備性、唯一性和簡約性的特點。研究了測試原語的構建方法，建立了涵蓋非連接性靜態故障的測試原語庫。通過對測試原語模型的討論，將存儲器的功能級故障模型與測試原語聯系起來，簡化對March 算法故障覆蓋率的分析。

2 故障模型及其測試原語

2.1 存儲器故障模型

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

單一單元故障的故障原語表達式為，其中S 代表觸發存儲器故障行為的操作或狀態，F 代表故障單元的狀態值，R 代表讀操作的邏輯輸出電平[9]。雙單元耦合故障的故障原語表達式為，其中Sa 和Sv 分別代表觸發存儲器故障時攻擊單元和受害單元的狀態或操作。Sa 和Sv 不能同時為操作[10]。

2.2 測試原語

隨著制造工藝的持續演進，存儲器出現了許多新型故障，需要March 算法持續適應新的故障類型。高測試復雜度的測試算法使算法的分析、驗證和生成都面臨困難。

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

測試原語與故障原語有相同的敏化操作集，因此，推導測試原語的關鍵在于研究檢測操作特征描述符的適用情況。檢測操作特征描述符包括檢測故障的讀操作（稱為檢測操作）和描述檢測操作位置的特殊符號。采用類似正則表達式的符號來表示檢測操作位置，測試原語中常用的符號及其含義如表1 所示。檢測操作特征描述符按地址變化方向分為兩種情況，a?v表示地址變化方向為攻擊單元向受害單元遍歷，v?a則相反。在本文提出此表示方法之前，一般使用a>v 和a

表1 測試原語中常用的符號及其含義

按照下述方法推導測試原語，其中雙單元耦合故障的故障單元指受害單元。

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

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

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

而針對攻擊單元在敏化時是操作這種情況，測試原語的生成較為復雜，通過干擾耦合故障舉例說明。故障原語CFdsrx中的敏化條件集為，攻擊單元的敏化是操作Rx，受害單元的敏化是狀態y，所以檢測操作是Ry，因為攻擊單元在敏化時是操作，所以在敏化操作之后增加0 個或多個任意訪存操作都不影響故障檢測，故添加“*”，在這里要注意的是，添加的多個訪存操作行進完最后的狀態要保持和受害單元敏化前的狀態相同。根據上述規則可得D 的表達式為

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

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

3 測試原語性質證明

本文提出的測試原語針對目標故障原語而言具有完備性、唯一性與簡約性的特點。若不具備完備性則無法保證其對任一March 算法均可進行故障覆蓋率分析的能力。唯一性保證某March 算法滿足測試原語描述時，一定能夠檢測到對應的故障。簡約性保證測試原語可直接應用于測試序列的最優化生成。

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

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

由檢測操作特征描述符的定義可知，當D≠? 時，D 中的操作集Od 與敏化操作集Os 的關系包含以下可能：

其中，“;”為March 算法行進一次的結束標志，“[...]”表示括號內的內容可選。上面4 式可描述20 種可能出現的位置關系，加上D=?，一共有21 種需討論的情況。

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

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

3.1 單一單元故障測試原語完備性證明

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

2）根據式（7）可知，位置關系有4 種：①O1 和O2都存在，位置關系為O1RxO2；②O1 存在，O2 不存在，位置關系為O1Rx；③O1 不存在，O2 存在，位置關系為RxO2；④O1 和O2 都不存在，位置關系為Rx。在O1 存在時，在故障敏化之后的多個訪存操作可能會改變故障單元的狀態，所以這類位置關系形成的測試原語不能檢測狀態故障，即①和②中的位置關系形成的測試原語不能檢測此故障。而③和④的位置關系形成的測試原語可以檢測狀態故障，因為在檢測操作之后的訪存操作對故障檢測沒有影響，將③和④中位置關系形成的測試原語合并為Rx。

3）根據式（8）可得，O1 存在，此時的位置關系為O1;Rx，在故障敏化之后的訪存操作可能改變故障單元的狀態，使得故障不能被檢測。O1 不存在，此時的位置關系為;Rx，此位置關系形成的測試原語可以檢測狀態故障。

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

讀破壞故障是讀操作導致故障單元的狀態發生翻轉，此讀操作將錯誤狀態讀出，所以敏化故障的讀操作可以直接檢測出故障，此故障的測試原語為，即其測試原語的D 為?。因為只有Rx 一個操作，并不需要指定其位置，也不管其前后是否有訪存操作，所以可以得到其最后的測試原語為，證明了測試原語的完備性。錯誤讀故障測試原語完備性分析與讀破壞故障測試原語分析類似，在這里不再過多描述。

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

本文分3 種不同的情況對雙單元耦合故障測試原語的完備性進行證明：1）攻擊單元與受害單元在敏化時都是狀態；2）攻擊單元在敏化時是操作；3）受害單元在敏化時是操作。

3.2.1 攻擊單元與受害單元在敏化時都是狀態

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

1）根據式（6）可知，O2 存在的位置關系為;RyO2O3 和;RyO2，按照這兩種位置關系形成的測試原語可以檢測x≠y 時攻擊單元在CAC 情況下的狀態耦合故障。O2 不存在的位置關系為;RyO3 和;Ry，按其形成的測試原語可以檢測x=y 時攻擊單元在CAC 時的狀態耦合故障。因為檢測操作之后的訪存操作不影響故障檢測，所以上述位置關系形成的測試原語可總結為^Ry*。

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

3）根據式（8）可知，O1 存在時的位置關系為O1;Ry，按此位置關系形成的測試原語在故障敏化之后增加了多個訪存操作，這些操作如果改變了故障單元的狀態，將導致其不能被檢測。O1 不存在時的位置關系為;Ry，按其形成的測試原語，在x=y 時可以檢測受害單元在CAC 時的狀態耦合故障，而在x≠y 時，敏化條件不能得到保證，因為在一個March 元素開始前，存儲陣列會被寫為相同的狀態。

經過上述分析，將形成的位置關系Ry 和^Ry*合并，得到測試原語：

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

3.2.2 攻擊單元在敏化時是操作

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

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

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

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

經過上述分析，得到可檢測CFdsrx 故障的測試原語為

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

3.2.3 受害單元敏化時是操作

1）根據式（6）可以得到4 種位置關系，因為不能保證故障檢測在時間上滯后于故障敏化，因此這4 種位置關系形成的測試原語不能檢測轉換耦合故障。

4 測試原語的使用

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

4.1 狀態元組的定義及生成

測試原語的狀態元組表示的是故障檢測需要的狀態條件，March 算法的狀態元組表示的是March 算法行進到某一訪存操作的存儲陣列的狀態。狀態元組的表達式為，其中LAS 表示低地址單元狀態，CAS 表示當前地址單元狀態，HAS 表示高地址單元狀態。LAS/CAS/HAS∈{0,1,x}，其中0 表示存儲單元的狀態為0，1 表示存儲單元的狀態為1，x 表示不關心存儲單元是什么狀態。

4.1.1 測試原語狀態元組的生成

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

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

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

4.1.2 March 算法中狀態元組的生成

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

March 元素中第一個訪存操作狀態元組的推導需要明確March 元素的初始狀態和結束狀態，并可以得到以下結論。如果March 元素的地址遍歷順序為↑，則狀態元組為<結束狀態，初始狀態，初始狀態>。如果March 元素的地址遍歷順序為↓，則狀態元組為<初始狀態，初始狀態，結束狀態>。如果March 元素的地址遍歷順序為?，則狀態元組可以為以上兩種的任意一種。

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

4.2 March 算法的分析過程

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

圖2 分析過程框圖

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

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

5 結論

本文提出了新的測試原語，測試原語作為故障原語與測試算法之間的橋梁，形成高靈活度且可擴展的分析單元，予以簡化March 算法的分析過程。針對本文所涉及的故障集，給出了其測試原語庫，并使用反證法證明了測試原語的完備性，其完備性得到保證，測試原語的唯一性和簡潔性也得到保證。本文所涉及的測試原語通過拓展狀態元組的方式運用在March算法的分析過程中，并對March C+算法進行分析，將來會將測試原語用在自動生成March 算法中，以達到簡化這些過程的目的。