测试原语：存储器故障最小检测序列的统一特征

肖寅东，王恩笙，路杉杉，戴志坚

（电子科技大学自动化工程学院，成都 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 种组合。现采用反证法来证明本文涉及的故障集的测试原语的完备性。

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 算法中，以达到简化这些过程的目的。