唐小峰，許愛強(qiáng)，李文海

（1.海軍航空工程學(xué)院科研部，山東煙臺264001；2. 92514部隊(duì)，山東煙臺264007）

?

多層次模擬電路隨機(jī)變異生成方法研究

唐小峰1，2，許愛強(qiáng)1，李文海1

（1.海軍航空工程學(xué)院科研部，山東煙臺264001；2. 92514部隊(duì)，山東煙臺264007）

摘要：針對目前復(fù)雜電路測試、診斷過程中故障樣本獲取困難的問題，提出一種隨機(jī)變異生成策略。首先定義適用于隨機(jī)方法的8種限定變異算子，可覆蓋實(shí)際電路中的大多數(shù)真實(shí)故障；然后應(yīng)用層次分析法（AHP），分別考慮電路組成元素間的相對故障概率和故障類型，計算出不同變異位置以及對應(yīng)變異算子的被選權(quán)重；考慮連續(xù)型故障參數(shù)的分布，通過隨機(jī)采樣確定具體的參數(shù)值，使故障模型更為真實(shí)；最后，以一個串聯(lián)調(diào)整型穩(wěn)壓電路為實(shí)例，為其生成500個隨機(jī)變異體。實(shí)驗(yàn)結(jié)果表明：該方法能夠快速有效地為多層次模擬電路生成大規(guī)模、高質(zhì)量的故障樣本。

關(guān)鍵詞：自動故障注入；隨機(jī)變異生成；變異算子；層次分析法

0　引言

評價測試方案的質(zhì)量、驗(yàn)證診斷算法的效果以及分析電路的故障行為等研究都需要獲取大量符合實(shí)際的故障電路樣本。當(dāng)前常用的做法是基于電子設(shè)計自動化（electronic design automation，EDA）技術(shù)實(shí)現(xiàn)電路的自動故障注入。一種方法是為常見電子元件定義故障模型，并將其封裝為PSpice仿真模型庫（.lib或.olb文件），然后通過替換無故障電路中的對應(yīng)元件模型，達(dá)到故障注入的目的[1-2]。針對多層次電路的故障注入，繩偉光等[3]設(shè)計了Spice LL（k）解析器，能夠在故障注入前對層次狀的Spice網(wǎng)表進(jìn)行展平操作。源于軟件測試領(lǐng)域的變異分析技術(shù)[4]為硬件的故障注入提供了新的思路，其主要特點(diǎn)是通過變異算子控制變異體的生成，可提高故障注入的靈活性及自動化程度。Straube等[5]在其開發(fā)的混合層次模擬電路仿真器aFSIM中提出了若干基本的故障生成算子，通過操作電路網(wǎng)表實(shí)現(xiàn)故障注入。Xu等[6]基于電路的Spice描述提出了8種模擬電路變異算子，實(shí)現(xiàn)了大規(guī)模變異體的快速生成，并能覆蓋實(shí)際電路中的大多數(shù)真實(shí)故障。目前，相關(guān)研究主要存在兩點(diǎn)不足：1）故障模型通常采用簡化的理想模型，如零阻值短路和無窮大阻值開路等[7-8]，未考慮實(shí)際故障參數(shù)的分布；2）故障注入時很少考慮不同電路元素間的相對故障概率，故障樣本的質(zhì)量不高。本文對傳統(tǒng)的模擬電路變異生成方法進(jìn)行改進(jìn)，提出了一種適用于多層次復(fù)雜模擬電路的隨機(jī)變異生成技術(shù)，考慮樣本選取中的故障概率差異以及具體故障的參數(shù)分布，為提高故障電路樣本的品質(zhì)提供一種解決方案。

1　變異算子

從結(jié)構(gòu)上看，電路可視為由功能元件及其互聯(lián)構(gòu)成的網(wǎng)絡(luò)。單個功能元件及其端口構(gòu)成了最簡單的電路。令二元組c=（C，N）為電路c的遞歸定義，其中C是c中所含子級電路（統(tǒng)稱為元件）的集合；N為本級電路中節(jié)點(diǎn)的集合（不含子電路內(nèi)部的節(jié)點(diǎn)）。元件和節(jié)點(diǎn)均包含若干端口，端口間相互連接構(gòu)成電路網(wǎng)絡(luò)。

定義元件和節(jié)點(diǎn)上端口的數(shù)量為它們各自的度。變異的實(shí)質(zhì)是對c的一種變換，即改變電路的屬性或拓?fù)浣Y(jié)構(gòu)，以模擬故障發(fā)生時的情形。下面首先引入隨機(jī)變異生成所使用的變異算子。

定義1一般變異算子（general mutation operator）。一般變異算子T是一個目標(biāo)電路c到一個有窮電路集合的映射：T（c）={ci|i=1，2，…，n}，使得ci包含c的一個或多個故障，其中ci稱為c的一個變異體，且ci≠cj（i≠j）；n為算子T對應(yīng)的變異體數(shù)量。若每個ci中僅包含一個故障，則稱T為一階變異算子，否則稱為高階變異算子[4]。

定義2限定變異算子（restricted mutation operator）。若一般變異算子T在條件cond的限定下，滿足Tcond（c）=c＇，則稱Tcond為限定變異算子，其中下標(biāo)cond表示變異發(fā)生的位置或方式。

限定變異算子是對一般變異算子的特化，將其變異體規(guī)模鎖定為n=1。本文只研究一階限定變異算子，并基于常見的電路故障模型，提出如表1所示的8種算子，給出了它們各自的限定條件和實(shí)現(xiàn)方法。

2　隨機(jī)變異生成

隨機(jī)變異生成主要包括3個步驟：1）隨機(jī)確定變異發(fā)生的位置；2）從該位置上可用的變異算子中隨機(jī)選擇一個算子；3）根據(jù)所選算子的約束條件和實(shí)現(xiàn)方法隨機(jī)生成一個特定的變異體。重復(fù)上述過程，直到生成規(guī)定數(shù)量的隨機(jī)變異體為止。

為得到接近實(shí)際的變異體樣本集，需考慮目標(biāo)電路中各類故障發(fā)生的概率對隨機(jī)變異生成過程的影響，例如不同種類元件間的故障率對變異位置選擇的影響，元件上不同故障的發(fā)生概率對變異算子選擇的影響等。然而，受各種因素制約，往往難以獲得這些故障發(fā)生概率的準(zhǔn)確統(tǒng)計信息。下面介紹一種半經(jīng)驗(yàn)方法：層次分析法（AHP）[9]，用于確定隨機(jī)選擇過程中各類要素的權(quán)重。

表1　限定變異算子

2.1層次分析法

層次分析法特點(diǎn)是可利用不完整的統(tǒng)計數(shù)據(jù)和經(jīng)驗(yàn)信息，在兩類要素間做出相對容易和準(zhǔn)確的權(quán)衡，再將要素間的相對權(quán)重轉(zhuǎn)換為絕對權(quán)重。多次兩兩比較盡管增加了工作量，但能有效平滑模糊經(jīng)驗(yàn)帶來的誤差。

2.2變異位置的隨機(jī)選擇

選擇變異位置的關(guān)鍵是確定目標(biāo)電路中不同類型的部位發(fā)生故障的概率，故障概率越高則被選中的概率應(yīng)越大。應(yīng)用層次分析法可知，該問題域中的要素為目標(biāo)電路中不同類型的元素，即元件、節(jié)點(diǎn)和節(jié)點(diǎn)對，進(jìn)一步可將元件分為單個功能元件，如電阻、電容、電感等，以及子電路兩類。首先統(tǒng)計出目標(biāo)電路中所有類型元素及其數(shù)量，再對這些類型上的故障概率進(jìn)行兩兩比較得到權(quán)重判斷矩陣，最后計算得出各個類型的變異權(quán)重。

變異權(quán)重表示當(dāng)電路表現(xiàn)異常時，將其歸咎于某一類元素的置信度。由于考慮了實(shí)例數(shù)量，因此類型間的兩兩比較可理解為該目標(biāo)電路中這兩類元素平均故障概率的比較。操作時，可首先各自隨機(jī)抽樣出一個實(shí)例，如電阻R1、節(jié)點(diǎn)1等，再對這兩個具體樣本進(jìn)行比較。

一般情況下，當(dāng)類型選定后，電路中屬于同一類型的實(shí)例有相同的概率被隨機(jī)選中作為具體的變異位置。若選中的類型為節(jié)點(diǎn)或子電路，則應(yīng)進(jìn)一步考慮節(jié)點(diǎn)的度和子電路的規(guī)模對隨機(jī)選擇過程的影響。通常可以認(rèn)為，節(jié)點(diǎn)的度越高越容易發(fā)生故障；子電路的規(guī)模越大其內(nèi)部發(fā)生故障的概率也越大。

2.3變異算子的隨機(jī)選擇

變異位置的類型決定了可用的變異算子，記為候選算子集O。參考表1中所示各算子的限定條件，可以了解每個電路元素類型對應(yīng)的候選算子集。例如，對節(jié)點(diǎn)類型有O={OPN，NSP}，對節(jié)點(diǎn)對類型有O={GRB}等。由于每個算子代表了一類能在當(dāng)前變異位置上發(fā)生的故障，因此這些故障發(fā)生的概率決定了算子的權(quán)重。同樣可以應(yīng)用層次分析法計算算子權(quán)重，此時問題域中的要素變?yōu)樘囟ㄗ儺愇恢蒙系暮蜻x算子，其步驟與變異位置的隨機(jī)選擇相同。不同之處僅在于這些要素實(shí)例的數(shù)量均為1。

值得注意的是子電路上的候選算子分為外部和內(nèi)部兩種。外部算子主要用于模擬子電路的全局參數(shù)故障或接口故障，如PCH、OPN、LRB、CNM等；內(nèi)部算子則是將子電路作為新的目標(biāo)電路進(jìn)行處理，可根據(jù)其中元素類型的不同使用相應(yīng)的候選算子，這是一個遞歸過程。

2.4變異體的隨機(jī)生成

當(dāng)變異位置和算子確定后，在生成特定的變異體之前，需要考慮變異體的具體實(shí)現(xiàn)形式。對于連續(xù)型故障參數(shù)，如PCH的參數(shù)、OPN的開路阻值和容值、LRB和GRB的橋接阻值等，需根據(jù)這些參數(shù)服從的分布取具體數(shù)值。由于電路模型中絕大多數(shù)參數(shù)為正實(shí)數(shù)，因此可采用截斷的正態(tài)分布[10]：設(shè)數(shù)值參數(shù)為x，x是一個隨機(jī)變量，按正態(tài)分布N（μ，σ2）對其進(jìn)行采樣，若x≤0則x←δ，其中δ是一個接近0的小值。就PCH而言，考慮到一個元件可能有多個參數(shù)，為凸顯變異效果，應(yīng)從對元件性能影響最顯著的參數(shù)中進(jìn)行隨機(jī)選取。此外，LRB、CNM、NSP等算子的實(shí)現(xiàn)需要選擇特定的端口，此時按均等概率隨機(jī)指定一對或一組端口即可。

3　變異生成工具

為實(shí)現(xiàn)隨機(jī)變異生成的自動化，基于C#語言實(shí)現(xiàn)了一個計算機(jī)輔助工具：電路變異工具（circuit mutation laboratory，CMLab）。如圖1所示，CMLab采用了可擴(kuò)展的層次架構(gòu)，自底向上共包含4層，分別是電路描述層、變異層、輸入輸出層和應(yīng)用層。其中電路描述層定義了電路在計算機(jī)中的數(shù)據(jù)結(jié)構(gòu)模型，包括節(jié)點(diǎn)、節(jié)點(diǎn)對、元件的仿真計算模型以及電路的遞歸描述等；變異層由變異算子類組成，主要負(fù)責(zé)限定變異算子的實(shí)現(xiàn)；輸入輸出層包括將外部格式（目前主要指Spice網(wǎng)表）轉(zhuǎn)換為內(nèi)部模型的解析器和將變異體重新轉(zhuǎn)化為可仿真描述的轉(zhuǎn)換器；應(yīng)用層可實(shí)現(xiàn)多種基于變異的應(yīng)用，這里主要關(guān)注隨機(jī)變異生成應(yīng)用，由隨機(jī)變異生成器完成。

圖1　CMLab框架結(jié)構(gòu)

4　實(shí)例

以圖2所示的串聯(lián)調(diào)整型穩(wěn)壓電路為例，電路中包含7個電阻（RES）、3個電容（CAP）、3個三極管（BJT）、1個穩(wěn)壓二極管（D）、10個節(jié)點(diǎn)（NODE）、23個全局節(jié)點(diǎn)對（NPAIR）和1個子電路（SUBCKT）（電位器RP1）。由此可得變異位置類型及其數(shù)量的向量分別為TP=[RES，CAP，BJT，D，NODE，NPAIR，SUBCKT] 和m=[7，3，3，1，10，23，1]。

將TP中的類型進(jìn)行兩兩比較。簡單起見，比較時可以任意選擇每個類型中的某個實(shí)例樣本，如[R1，C1，Q1，D1，1，＜1，6＞，RP1]，再兩兩比較這些樣本間故障發(fā)生的相對容易程度。最終可得如圖3所示的變異權(quán)重判斷矩陣。按層次分析法可算得各元素類型的變異權(quán)重向量為ω=[0.14，0.32，0.12，0.06，0.10，0.16，0.10]。

選定變異位置后，進(jìn)一步的工作是計算其候選算子集中各個算子的權(quán)重。假設(shè)當(dāng)前變異位置為穩(wěn)壓二極管D1，則通過表1中的相關(guān)描述可確定其候選算子集為O={PCH，OPN，LRB，CNM}。仍通過兩兩比較其相對權(quán)重可得如圖4所示的權(quán)重判斷矩陣，最終可得D1上各算子的權(quán)重向量為ω1=[0.14，0.50，0.28，0.08]。

變異算子確定后，按2.4節(jié)所示方法，生成一個變異體即可。例如，假設(shè)選中了D1上的OPN算子，且隨機(jī)選中的端口為1號端口（與節(jié)點(diǎn)4相連），則將在目標(biāo)電路中添加一個由阻值為ROPN的電阻和容值為COPN的電容并聯(lián)構(gòu)成的復(fù)合元件，該元件一端與D1的1號端口相連，一端與節(jié)點(diǎn)4相連。

最后，使用CMLab工具為實(shí)例電路生成500個隨機(jī)變異體。圖5給出本次隨機(jī)變異生成實(shí)驗(yàn)的統(tǒng)計結(jié)果。就變異體類型而言，OPN變異體的規(guī)模最大，其次是PCH和LRB變異體；就變異發(fā)生的位置類型而言，電容被選中的次數(shù)最多，共計163次，其次是電阻（70次）、三極管和全局節(jié)點(diǎn)對（同為68次），基本與ω中的權(quán)重一致。另外值得注意的是，設(shè)定的變異體總數(shù)越大，生成重復(fù)或等價變異體的概率也越高。在下一步的變異體仿真分析中，為提高仿真效率，應(yīng)避免等價變異體的重復(fù)仿真。然而，等價變異體的數(shù)量對統(tǒng)計分析結(jié)果的影響仍應(yīng)考慮在內(nèi)。

圖2　串聯(lián)調(diào)整型穩(wěn)壓電路

圖3　實(shí)例電路的變異位置權(quán)重判斷矩陣

圖4　二極管的變異算子權(quán)重判斷矩陣

圖5　500次隨機(jī)變異實(shí)驗(yàn)統(tǒng)計結(jié)果

5　結(jié)束語

本文提出一種能夠處理多級子電路的模擬電路隨機(jī)變異生成方法，其特點(diǎn)是應(yīng)用變異算子實(shí)現(xiàn)故障注入，所提算子能夠有效覆蓋電路中的真實(shí)故障模式；此外，應(yīng)用層次分析法較好地解決了變異位置、變異算子的隨機(jī)選擇問題；基于文中所提方法開發(fā)的工具CMLab能夠自動、快速地生成大規(guī)模、符合客觀實(shí)際的變異體樣本，為今后進(jìn)一步研究電路的故障行為奠定基礎(chǔ)。

參考文獻(xiàn)

[1]宋麗蔚，李剛.基于PSpice的電子設(shè)備故障自動注入平臺研究[J].中國測試，2012，38（4）：99-102.

[2]丁國寶，婁建安，云超，等.基于PSpice的模擬電路故障知識獲取新方法[J].計算機(jī)測量與控制，2010，18（2）：286-288.

[3]繩偉光，肖立伊，毛志剛.用于電路級仿真軟故障注入的自動化方法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2009，21（3）：346-353.

[4] JIA Y，HARMAN M. An analysis and survey of the development of mutation testing [J]. IEEE Transactions on Software Engineering，2011，37（5）：649-678.

[5] STRAUBE B，VERMEIREN W，SPENKE V. Multilevel hierarchical analogue fault simulation[J]. Microelectronics Journal，2002，33（10）：815-821.

[6] XU A Q，TANG X F，YANG Z Y. Mutant Generation for Analog Circuit Designs[C]∥Proceedings of the IEEE 5th International Conference on Software Engineering and Service Science.Beijing，2014：916-920.

[7]冉躍龍，閆英敏，呂秀平.裝備虛擬維修中的電路故障仿真研究[J].計算機(jī)仿真，2013，30（11）：20-23.

[8]郭梁，馬立元，郭利，等.基于仿真的電子元器件故障模型研究[J].工程設(shè)計學(xué)報，2008，15（2）：145-148.

[9]邱靜，劉冠軍，楊鵬.裝備測試性建模與設(shè)計技術(shù)[M].北京：科學(xué)出版社，2012：59-63.

[10] ENGELKE P，POLIAN I，RENOVELL M，et al. Simulating resistive -bridging and stuck -at faults [J]. IEEE Transactions on Computer -Aided Design of Integrated Circuits and Systems，2006，25（10）：2181-2192.

（編輯：李剛）

A stochastic mutant generation method for multi-level analog circuits

TANG Xiaofeng1，2，XU Aiqiang1，LI Wenhai1
（1. Department of Scientific Research，Naval Aeronautical and Astronautical University，Yantai 264001，China；2. Unit 92514 of the PLA，Yantai 264007，China）

Abstract:A stochastic mutant generation method has been proposed to acquire automatically multiple fault samples from complex circuits for testing and diagnostic purposes. First，eight restricted mutation operators are defined to cover the majority of actual circuit faults. Analytical hierarchy process（AHP）is used to analyze the relative fault probabilities and fault types of circuit elements and evaluate the weights of different mutation locations and operators selected. Then，the probability distributions of continuous fault parameters are considered and the fault model is made more realistic by random sampling of fault parameter values. In the end，500 stochastic mutants are generated for a regulator circuit. The experimental results show that the proposed method can rapidly generate massive high-quality fault samples for multi-level analog circuits fast and well.

Keywords:automatic fault injection；stochastic mutant generation；mutation operator；AHP

作者簡介：唐小峰（1984-），男，重慶市人，助理工程師，博士，主要從事電子信息系統(tǒng)測試與診斷技術(shù)研究。

基金項(xiàng)目：中國博士后科學(xué)基金項(xiàng)目（2013M542535）

收稿日期：2015-06-09；收到修改稿日期：2015-07-27

doi：10.11857/j.issn.1674-5124.2016.01.003

文獻(xiàn)標(biāo)志碼：A

文章編號：1674-5124（2016）01-0012-04