錢 麗，胡 俊，王美榮，沈桂芳, 陳 平

(安徽新華學院 信息工程學院,安徽 合肥 230088)

基于關聯(lián)維計算的軟件失效混沌識別研究

錢 麗，胡 俊，王美榮，沈桂芳, 陳 平

(安徽新華學院 信息工程學院,安徽 合肥 230088)

針對大數(shù)據(jù)環(huán)境下軟件失效行為的復雜性問題，提出了一種基于關聯(lián)維數(shù)的軟件失效混沌識別算法.通過計算軟件失效數(shù)據(jù)是否具有關聯(lián)維特征來驗證失效的混沌性，利用相空間方法重構軟件失效系統(tǒng)，驗證了軟件失效行為的混沌性.實驗結果表明，混沌關聯(lián)維算法能夠有效識別軟件失效的混沌性，精確地描述軟件失效行為的無序性和無規(guī)則性，同時也能解決復雜軟件系統(tǒng)失效、大數(shù)據(jù)混沌性這類復雜問題.

大數(shù)據(jù)；軟件失效；關聯(lián)維；混沌識別

隨著互聯(lián)網(wǎng)、云計算技術的不斷創(chuàng)新與發(fā)展，數(shù)據(jù)呈現(xiàn)爆炸式的增長，軟件系統(tǒng)也變得日益復雜.軟件安全性問題一直以來都是企業(yè)在運營過程中關注的焦點問題，復雜軟件系統(tǒng)給企業(yè)的軟件安全提出了更高的要求[1-2].目前比較常用的研究方法是通過對軟件失效行為的分析，挖掘出復雜軟件系統(tǒng)內(nèi)在的本質(zhì)演化規(guī)律[3].國內(nèi)研究中，YANG等[4]采用疊加NHPP模型極大似然估計法來研究軟件失效行為；程躍華等[5-6]采用主成分分析法研究軟件失效機理，解決軟件可靠性度量存在的多重共線性問題；臺灣LIN等[7]提出性能模型演示的實驗方法進行軟件失效分析；樓俊鋼等[8]采用主成分回歸算法和支持向量回歸等核函數(shù)回歸估計方法研究軟件失效行為.國外研究中，INOUE等[9]提出離散型軟件可靠性模型，不同于連續(xù)時間上的軟件可靠性模型，較好解釋軟件失效行為；LANDONA等[10]開發(fā)貝葉斯推理模型和強化泊松過程模型，并且實施于實際軟件故障數(shù)據(jù)預測模型的過程；ZHENG等[11-12]研究者提出基于神經(jīng)網(wǎng)絡的非參數(shù)式建模方法研究軟件失效行為，這種方法不同與以往基于一些主觀假設條件的SRGM，對軟件可靠性的度量、預測的精度有很大的提高，但對軟件失效行為的本質(zhì)分析不夠透徹.

以上研究主要基于概率論與數(shù)理統(tǒng)計方法，假定軟件失效行為符合某種概率分布，使用可靠性隨機模型來分析軟件失效過程，這種研究觀點與方法具有一定的主觀性，較難解決軟件失效、復雜軟件系統(tǒng)失效行為的混沌性問題.大數(shù)據(jù)環(huán)境下的軟件失效行為不僅具有隨機性，也具有確定性，軟件失效行為的本質(zhì)與混沌特性是具有相似性的，雖然受到確定規(guī)則的約束，但是其行為卻表現(xiàn)出無序性.因此，本研究將混沌關聯(lián)維特征計算應用到軟件失效行為的分析上，比隨機模型更好地描述軟件失效行為的無序性和無規(guī)則性，同時也能夠解決軟件失效、大數(shù)據(jù)混沌性這類復雜的問題.

1 混沌識別特征量分析

復雜軟件系統(tǒng)失效行為的演化過程中，可以將測試人員、軟件和運行環(huán)境看做一個復雜混沌系統(tǒng)，系統(tǒng)中各個分量之間相互影響作用，復雜軟件系統(tǒng)不斷地向前演化，在此過程中應用混沌時間序列分析軟件失效行為的演化規(guī)律.軟件失效的混沌現(xiàn)象是指系統(tǒng)在確定系統(tǒng)中貌似隨機的不規(guī)則運動，其行為表現(xiàn)出不可預測，無序的狀態(tài).軟件失效行為的混沌特征通常表現(xiàn)為無明顯規(guī)則和次序、非同期性的復雜折疊和扭曲，軟件失效行為的混沌識別通過計算Lyapunov指數(shù)和關聯(lián)維數(shù)等混沌特征量來判斷軟件失效數(shù)據(jù)是否具有混沌性.

1.1 Lyapunov指數(shù)

在對軟件失效行為的分析過程中，所收集的失效數(shù)據(jù)只是整個軟件失效系統(tǒng)的局部觀測值，如果要研究系統(tǒng)的演化規(guī)律，就要計算嵌入維、時間延遲，重構與原空間微分同胚的相空間.相空間是一個六維假想空間，其中動量和空間各占三維.物理學中的相空間由系統(tǒng)的狀態(tài)點組成，相空間的維數(shù)由質(zhì)點系的“自由度”個數(shù)來決定.若用x來表示質(zhì)點所在的位置，那么質(zhì)點速度由x對時間t的一階導數(shù)xdx/dt表示，(x，y)表示系統(tǒng)的一個狀態(tài)點，所有狀態(tài)點的集合就構成了系統(tǒng)的相空間.通過重構相空間可以挖掘系統(tǒng)的演化規(guī)律.

混沌系統(tǒng)的運動軌道具有初值非常敏感性，相空間中初始距離靠近的兩條軌跡以指數(shù)速率發(fā)散，通過Lyapunov指數(shù)形式描述.初始兩點在一維動力系統(tǒng)xn+1=F(xn)中迭代后，它們的分合程度取決于|dF/dx|的值：大于1則兩點分離；反之則靠攏.假設初始點x(t0)附近有一點x(t0)+Δx(t0)，則經(jīng)過n次迭代后，

x(tn+1)+Δx(tn+1)=f[x(tn)+Δx(tn)]≈

f[x(tn)]+Δx(tn)f′[x(tn)]

因此，

Δx(tn+1)=Δx(tn)f′[x(tn)]

(1)

其中，t0和tn分別為初始時間和當前時間.假設相空間兩點軌跡的初始距離為|Δx(t0)|，經(jīng)過n次迭代后兩點的距離為|Δx(tn)|，由上面式(1)得出：

|Δx(t0)|exp(λtn)

系統(tǒng)的Lyapunov指數(shù), 當λ<0時，則系統(tǒng)是穩(wěn)定的；λ=0時，則系統(tǒng)是周期的；λ>0時，則系統(tǒng)是混沌的.

1.2 關聯(lián)維數(shù)與嵌入維數(shù)

大數(shù)據(jù)環(huán)境下的軟件系統(tǒng)是確定的，系統(tǒng)的變化狀態(tài)由若干變量決定，其中變量的個數(shù)即為系統(tǒng)的維數(shù).混沌系統(tǒng)雖然在高維空間上表現(xiàn)無序、無規(guī)則，但是由于相空間的收縮，系統(tǒng)中的自由活動將越來越少，而相空間聯(lián)系和整體約束越來越強，最終趨向于低維空間的極限，也就是所謂的奇異吸引子.如果奇異吸引子存在于軟件失效的觀測時間序列{x(t)}中，關聯(lián)指數(shù)D隨著嵌入維數(shù)m的增大而增加，直至觀測到關聯(lián)指數(shù)D收斂為一飽和值時，那么可以用關聯(lián)維數(shù)描述此吸引子的特征.關聯(lián)維通常采用關聯(lián)積分計算觀測變量前后的相互關聯(lián)性，從而描述信號的確定程度和規(guī)律.

本研究借助G-P算法計算大數(shù)據(jù)環(huán)境下的軟件失效數(shù)據(jù)的關聯(lián)維數(shù)，其算法主要思想是選擇不同的領域半徑r，分別計算相應的C(r)，從而得到D.當求得數(shù)據(jù)的飽和值后，根據(jù)失效數(shù)據(jù)的嵌入維數(shù)(m≥2d+1)，即可確定維數(shù)m.復雜軟件環(huán)境下混沌系統(tǒng)在高維空間是無序的，但當其投射到低維空間時，就會得到規(guī)律性的軌跡，在這個過程中，系統(tǒng)的軌跡也會產(chǎn)生變化.混沌運動表現(xiàn)出的特征在很多方面，例如，某些點雖然在高維空間中相鄰，但是投射到低維空間后卻不相鄰；而某些在高維空間不相鄰的點投射到低維空間時卻相鄰，這也是混沌運動表現(xiàn)出的特征.在重構系統(tǒng)相空間的時候，通常去除這些偽鄰居點，根據(jù)復雜環(huán)境下混沌系統(tǒng)的這種幾何原理來計算嵌入維，其計算步驟如下：假設{Xn}為混沌時間序列，τ為時間延遲參數(shù)，針對某個維數(shù)d，可以重構向量序列{yi(d)}，

yi(d)表示d維重構所得到的第i個向量.這里定義：

其中i= 1，2，…，N-dτ，||…||為無窮范數(shù).n(i,d)為大于等于1且小于N-d的整數(shù).：yn(i,d)(d)為離yi(d+1)最近的向量.a(i,d)均值定義為).

為了解E(d)的變化，定義：

E1(d)=E(d+1)/E(d)

若吸引子被包含在時間序列中，當維數(shù)d大于某個初始值d0時，E1(d)就會停止變化.那么最小嵌入維數(shù)為d0+1.

在實際復雜環(huán)境中得不到系統(tǒng)的所有分量，所以只有將系統(tǒng)投影到平面或直線上觀測，進而采集系統(tǒng)局部的一個到兩個分量的時間序列，空間維數(shù)的估算可以通過嵌入維靠近關聯(lián)維數(shù)算出.軟件失效的混沌識別，在于關聯(lián)維數(shù)隨著嵌入維數(shù)的增大最終是否收斂，如果收斂于一個穩(wěn)定值則系統(tǒng)是混沌的；如果不收斂，則是隨機的.軟件可靠性建模通常先收集軟件的失效數(shù)據(jù)來進行混沌識別，然后通過計算特征量來驗證失效行為的混沌性.

2 軟件失效行為的混沌識別

大數(shù)據(jù)環(huán)境下的復雜軟件系統(tǒng)需要滿足數(shù)據(jù)量大，數(shù)據(jù)類型多、運算速度高的特點，并且軟件系統(tǒng)本身具有復雜性和不透明性等特點，使得軟件失效行為變得不確定和難以預測.在實際軟件系統(tǒng)運行過程中，軟件失效的無序性、無規(guī)則性，不僅僅具有隨機的特點，更具有混沌的性質(zhì)，正如現(xiàn)實中大多數(shù)系為也是如此.復雜環(huán)境下軟件失效行為的混沌性識別過程中，首先收集失效數(shù)據(jù)，然后驗證失效數(shù)據(jù)的混沌性，進而分析與預測軟件失效行為.

軟件失效行為的分析和預測的前提是對軟件失效數(shù)據(jù)的驗證，通過驗證軟件失效數(shù)據(jù)來分析軟件失效行為的混沌性.失效數(shù)據(jù)的收集一般在軟件實際運行中進行，分為完全數(shù)據(jù)和不完全數(shù)據(jù)兩種類型：

(1)數(shù)據(jù)集合{y(i) |y(0) =0，i= 1, 2, …, n }為完全數(shù)據(jù)集合，如果：?：i(i∈{1, 2, …,n}→y(i)-y(i-1) = 1)，其中y(i)為直到時間t(i)時的累積故障數(shù).

(2)數(shù)據(jù)集合{y(i) |y(0) =0，i= 1, 2, …,p}為不完全數(shù)據(jù)集合，如果：?i(i∈{1,2,…，p}→y(i)-y(i-1)> 1).

復雜環(huán)境下軟件失效行為雖然表現(xiàn)為無序、隨機，但其本質(zhì)上是具有一定的確定性的，通過計算混沌特征量來判斷軟件失效行為是否具有混沌性，并且借助G-P算法計算關聯(lián)維和嵌入維數(shù)，進而驗證失效行為的確定性，具體計算過程如下：

(1)對于時間序列x1,x2,…,xn, 假設其中m0為一個較小值，則重構相應的相空間為Yi=(xi,xi+τ,…,xi+(m-1) τ), i = 1, 2, 3,…,M.

(2)計算關聯(lián)函數(shù)

其中θ(·)為Heaviside函數(shù)

(3)當r→0時，關聯(lián)積分與r存在以下關系：

上式參數(shù)r的選取需要考慮D能否描述奇異吸引子的自相似結構.

D=lnC(r)/lnr

維數(shù)D與函數(shù)C(r)需要滿足對數(shù)線性關系，并且通過最小二乘法擬合，求出一條最佳直線，該直線的斜率即是對應于m0的關聯(lián)維數(shù)的估計值d(m0).

(4)重復以上步驟(2)和(3)，繼續(xù)增加嵌入維數(shù)m，直至關聯(lián)維數(shù)d(m)不再隨m的增加而增大，并且收斂于一個穩(wěn)定值狀態(tài)，此時求到的d值即為吸引子的關聯(lián)維數(shù).如果d值隨m的增長而增長，并不收斂，則表明系統(tǒng)是隨機的.

3 仿真實驗驗證

本次實驗軟件編程環(huán)境：Windows7；MATLAB7.0；硬件環(huán)境處理器: Intel(R) Core(TM)2 Duo CPU E4500 @2.20GHz.本實驗采用記錄累計失效時間來描述軟件失效行為.首先收集公共測試(Beta)軟件運行過程中的失效數(shù)據(jù)，然后通過MATLAB7.0語言編程，實現(xiàn)對失效數(shù)據(jù)關聯(lián)維數(shù)的仿真，最后分析軟件失效行為是否具有混沌性.

實驗數(shù)據(jù)1[13]采用美國海軍戰(zhàn)術數(shù)據(jù)系統(tǒng)NTDS(Naval Tactical DataSystem)公開發(fā)表的失效數(shù)據(jù).這些數(shù)據(jù)是從美國海軍戰(zhàn)術數(shù)據(jù)系統(tǒng)保存的一個實時多處理機系統(tǒng)軟件開發(fā)過程的資料中提取的，包括38個不同的模塊，每個程序模塊都經(jīng)過了開發(fā)階段、測試階段和使用階段，數(shù)據(jù)見表1.

表1 NTDS數(shù)據(jù)集1
Tab.1 NTDS failure dataset 1

失效序號失效間隔/d失效序號失效間隔/d1918982211910433220105436211165432214964523156750242478582524996326250107027337117128384127729396137830405148731540159132798169233814179534849

實驗數(shù)據(jù)集2[13]來源于Musa數(shù)據(jù)集，由Musa發(fā)表(Musa 1990).失效數(shù)據(jù)由實時命令與控制系統(tǒng)的測試得來，數(shù)據(jù)集2源于貝爾實驗室，由9個程序員對包含21700條指令的系統(tǒng)的測試得來，系統(tǒng)運行時間為24.6 h，經(jīng)歷的日歷時間為92 d.數(shù)據(jù)集包含了72個失效數(shù)據(jù)，描述了每個失效的CPU時間.整個失效數(shù)據(jù)集記錄了失效發(fā)生的CPU時間，是失效時間數(shù)據(jù)集，具體見表2.

根據(jù)失效數(shù)據(jù)，利用G-P算法計算失效數(shù)據(jù)的關聯(lián)維和嵌入維，部分編程如下：

G-P算法計算關聯(lián)維數(shù)

form=min_m:max_m

Y=reconstitution(data,N,m,tau);

%重建矢量空間

M=N-(m-1)*tau;%矢量空間的點數(shù)

表2Musa失效數(shù)據(jù)集2
Tab.2Musafailuredataset2

失效序號失效間隔/s失效序號失效間隔/s失效序號失效間隔/s失效序號失效間隔/s13191872375565551098223320198638562356111753146212311396080571141142272223664063805811442534223260841647759118116351242676426740601255973532530984371926112559844426327844744762127919556273288457644631312110571284434467837641348611709295034477843651470812759305049487922661525113836315085498738671526114860325089501008968152771596833508951102376915806161056345097521025870161851717263553245310491711622918184636538954106257216358

fori=1:M-1

forj=i+1:M

max(abs(Y(:,i)-Y(:,j)));

%計算其余點到點Xi的距離

end

end

max_d=max(max(d));%求出距離最遠的點

d(1,1)=max_d;

min_d=min(min(d));%求出距離最近的點

delt=(max_d-min_d)/ss;%計算r的步長

for k=1:ss

r=min_d+k*delt;

C(k)=correlation_integral(Y,M,r);

%計算關聯(lián)積分函數(shù)

ln_C(m,k)=log(C(k));%lnC(r)

ln_r(m,k)=log(r);%lnr

end

plot(ln_r(m,:),ln_C(m,:));

hold on;

end

使用Matlab軟件工具運行NTDS 數(shù)據(jù)集1和Musa數(shù)據(jù)集2，結果分別如圖1和圖2所示.

圖1 NTDS 數(shù)據(jù)的關聯(lián)維數(shù)Fig.1 The correlation dimension of NTDS data

圖1是NTDS 數(shù)據(jù)集的運行結果，關聯(lián)維數(shù)d(m)隨m的增加而增大，最終沒有收斂于一個穩(wěn)定值，并且關聯(lián)維數(shù)中間有間斷，說明系統(tǒng)是隨機的.因此，NTDS 數(shù)據(jù)所表示的系統(tǒng)不具有混沌性.

圖2 Musa數(shù)據(jù)集的關聯(lián)維數(shù)Fig.2 The correlation dimension of Musa dataset

圖2是Musa數(shù)據(jù)集2的運行結果，關聯(lián)積分曲線隨著嵌入維m的增大而發(fā)生相應變化，對其進行線性擬合計算，求得關聯(lián)積分曲線斜率就是關聯(lián)維.關聯(lián)維數(shù)d(m)隨m的增加而增大，當m在[1-20]的范圍內(nèi)增長時，關聯(lián)維d最終收斂于一個穩(wěn)定值.因此，Musa數(shù)據(jù)集具有混沌性，表明了軟件系統(tǒng)失效行為具有混沌性.

4 結束語

大數(shù)據(jù)環(huán)境下的軟件失效行為不僅具有隨機性，也具有確定性，軟件失效行為的本質(zhì)與混沌特性是具有相似性的，雖然受到確定規(guī)則的約束，但是其行為卻表現(xiàn)出無序性.

本文提出一種基于關聯(lián)維數(shù)的軟件失效混沌識別算法，通過計算軟件失效數(shù)據(jù)是否具有關聯(lián)維特征來驗證失效的混沌性，利用相空間方法來重構軟件失效系統(tǒng)，定性定量地驗證了軟件失效行為的混沌性.實驗表明，混沌特征量算法能夠有效識別軟件失效的混沌性，突破了軟件失效分析一貫使用隨機理論和數(shù)理統(tǒng)計方法的局限, 更加精準地描述大數(shù)據(jù)環(huán)境下的軟件失效行為的無規(guī)則性和無序性，并且解決了軟件失效、大數(shù)據(jù)混沌性等軟件可靠性復雜問題，為大數(shù)據(jù)環(huán)境下的軟件失效行為的研究帶來了新的方法和思路.

[1]苗放.面向數(shù)據(jù)的軟件體系結構初步探討[J]. 計算機科學與探索,2016, 10(10):1351-1364.

[2]李國杰, 程學旗. 大數(shù)據(jù)研究:未來科技及經(jīng)濟社會發(fā)展的重大戰(zhàn)略領域——大數(shù)據(jù)的研究現(xiàn)狀與科學思考[J]. 中國科學院院刊, 2012, 27(6):5-15.

[3]汪北陽, 呂金虎. 復雜軟件系統(tǒng)的軟件網(wǎng)絡結點影響分析[J]. 軟件學報, 2013, 24(12):2814-2829.

[4]YANG J F, ZHAO M. Maximum likelihood estimation for software reliability with masked failure data[J]. Journal of Systems Engineering & Electronics, 2013, 35(12):2665-2669.

[5]程躍華, 崔艷. 組合模型在軟件可靠性預測中的建模與仿真[J]. 計算機仿真, 2011, 28(6):371-374.

[6]劉克,單志廣,王戟,等.“可信軟件基礎研究”重大研究計劃綜述[J]. 中國科學基金, 2008, 22(3):145-151.

[7]LIN C T, HUANG C Y. Enhancing and measuring the predictive capabilities of testing-effort dependent software reliability models[J]. Journal of Systems & Software, 2008, 81(6):1025-1038.

[8]樓俊鋼, 蔣云良, 申情,等. 軟件可靠性預測中不同核函數(shù)的預測能力評估[J]. 計算機學報, 2013, 36(6):1303-1311.

[9]INOUE S, HAYASHIDA S, YAMADA S. Toward Practical Software Reliability Assessment with Change-Point Based on Hazard Rate Models[C]//Computer Software and Applications Conference.IEEE Computer Society, 2013:268-273.

[10]LANDON J,OZEKICI S, SOYER R. A Markov modulated Poisson model for software reliability[J]. European Journal of Operational Research, 2013, 229(2):404-410.

[11]ZHENG J. Predicting software reliability with neural network ensembles[J]. Expert Systems with Applications An International Journal, 2009, 36(2):2116-2122.

[12]BARU C, BHANDARKAR M, CURINO C, et al. Discussion of BigBench: A Proposed Industry Standard Performance Benchmark for Big Data[M].[s.l.]:Springer International Publishing, 2014:44-63.

[13]LYU M R. Handbook of Software Reliability Engineering[M/OL].Hong Kong: Department of computer science and engineering, Chinese University Hong Kong,2005[2016-11-23].http://www.cse.cuhk.edu.hk/～lyu/book/reliability/.

Researchonthechaosidentificationofsoftwarefailurebehaviorbaseoncorrelationdimensioncalculation

QIAN Li，HU Jun，WANG Mei-rong,SHEN Gui-fang，CHEN Ping

(Institute of Information Engineering，Anhui Xinhua University, Hefei 230088, China)

In view of the disorder of software failure behavior in large data environment, a software failure identification method based on chaotic correlation dimension is proposed. With the help of the G-P algorithm, the characteristics of the correlation dimension and the embedding dimension of the failure data are calculated, and the uncertainty of the software failure data is determined by the chaotic characteristic quantity. The experimental results show that the chaos correlation dimension algorithm not only can effectively identify software failure,and accurately describe the software failure behavior disorder and irregular, but also can solve the complex software system failure, and big data chaos of this kind of complex problem.

big data； software failure；correlation dimension；chaos identification

2016-12-02

安徽省教育廳自然科學基金重點項目(KJ2014A100，KJ2015A300，KJ2016A304)；安徽省質(zhì)量工程項目(2015ckjh113)

錢麗，女, wulianchongjing@qq.com

1672-6197(2018)01-0021-05

TP309.2

A

(編輯：姚佳良)