偽距定位程序的蛻變測試方法

張 侹，廖 斌，李 奎，吳 娟，王德龍

(1.地理信息工程國家重點實驗室，陜西 西安 710054；2.西安測繪研究所，陜西 西安 710054)

0 引 言

全球衛星導航定位系統，通常由導航衛星(星座)、地面運控系統、用戶終端設備(也稱接收機)組成，可為全球用戶提供性能優異的導航、測速、授時服務[1]。接收機進行定位過程的基本工作原理是：當同時接收到至少4顆導航衛星信號時，就可以計算偽距，并通過衛星坐標、鐘差和不同頻點間相對于接收機的時延偏差即可最終計算用戶的三位位置信息。因此，偽距作為衛星導航系統的基本觀測值，直接決定了接收機的定位精度[2]。

由于偽距定位程序是典型的數值計算程序，且涉及衛星鐘差、用戶終端設備的鐘差以及無線電信號經過電離層和對流層中的延遲等大量復雜因素，傳統情況下只能通過選用標準樣例進行比對的方式開展測試，然而由于測試樣本數據通常不夠充分，所以很難甚至無法通過輸入給出預期的輸出結果，從而為軟件測試人員在測試過程中造成了極大的困難。

由此可見，偽距定位程序的測試屬于軟件測試中典型的測試判定問題(testing oracle)[3]。因此，如果繼續使用傳統的軟件測試方法對此類難以測試的程序進行測試，其測試效果就難以保證，從而也無法確保此類軟件的質量。

1 蛻變測試

1.1 基本原理與概念

Chen等在文獻[3]中提出了蛻變測試(metamorphic testing，MT)技術，該技術能夠有效解決軟件測試過程中遇到的測試判定問題，并進一步驗證了其有效性與可行性。

通常情況下，由于測試人員本身的原因，會導致測試用例的設計質量產生不同的偏差，從而出現在測試用例執行后未發現軟件問題的情況，對于此類測試用例而言，其本身也包含了大量被測試人員所忽視的信息，而這些信息同樣可用于對被測試軟件的進一步測試工作。

然而，蛻變測試技術主要依據被測試軟件特點構造蛻變關系(relation of metamorphic，具體定義見文獻[3])，通過最初設計的測試用例(即：原始測試用例，original test case)，結合所構造的蛻變關系生成衍生測試用例(derivatives test case，具體定義見文獻[3])，采用對比不同測試用例之間測試執行結果關系的方式對被測試軟件開展測試工作。

因此，該技術在應用過程中無需按照傳統的軟件測試方法，僅通過構造被測試軟件輸入及其期望輸出的方法，即可對被測試程序的執行結果進行正確性判定，從而達到軟件測試的目的，同時，該技術也是一種測試用例的生成方法。

1.2 蛻變測試的基本過程

通常情況下，蛻變測試的主要過程可以分為如下4個步驟[3]：①結合其它測試用例生成方法為被測程序生成原始測試用例；②如果這些原始測試用例沒有發現被測軟件的問題，則可基于被測程序自身特性構造對應的蛻變關系；③依據構造的蛻變關系計算并生成衍生測試用例；④針對執行原始測試用例和衍生測試用例后的被測試軟件結果進行對比，通過檢查是否滿足所構建的蛻變關系得到最終的測試結果。

蛻變測試方法的流程如圖1所示。

圖1 蛻變測試方法的流程

下面以余弦函數cos(α)為例，概要介紹蛻變測試方法的基本過程。假設被測試程序P為余弦函數的實現，那么，當α=36.7°時，則P(α)=0.8018。 根據余弦定理cos(α)=-cos(180°-α)， 可以構造蛻變關系MR，則可得到原始測試用例α基于MR的衍生用例為α′=36.7°-180°=143.3°， 以α′為輸入，執行被測試程序P，若所得結果P(α′)=0.8098， 則通過對比P(α)與P(α′)后發現P(α)≠P(α′)， 即兩者不滿足蛻變關系MR，進而可以進一步證明被測試程序P中存在缺陷。

目前，蛻變測試技術已廣泛應用于數值計算程序、地理信息系統、機器學習、圖形圖像處理、數據挖掘、網絡仿真、生物信息學等各個專業領域的軟件測試工作。Kari-shma和Srinvasan分別在文獻[5]和文獻[6]中采用蛻變測試技術就矩陣計算的測試判定問題進行了研究；陽小華等采用蛻變測試技術針對科學計算程序的層次分類模型進行了研究[7]；黃松等針對地理信息系統中坡度、坡向量算程序中的測試判定問題研究了蛻變測試技術的有效性[8]；張芷祎在其博士論文中采用蛻變測試技術就機器學習軟件的測試技術展開了研究[9]；蔣超等提出了用蛻變測試框架來解決圖像區域增長程序中的測試判定問題[10]；吳金波等利用蛻變測試方法針對數據分類應用程序在正確性測試方面的問題開展了研究，緩解數據挖掘算法程序測試上的“Oracle”問題[11]；韓育珍等利用蛻變測試方法驗證了擁有龐大數據信息條件下篩選搜索時帶來的測試判定問題[12]。

通過蛻變測試的基本原理與概念可知，構建蛻變關系是蛻變測試能否有效實施并取得良好應用效果的關鍵和前提；此外，蛻變測試技術在不同專業領域，特別是數值計算程序領域中的成功應用，也說明該技術是一種測試程序計算是否正確的有效方法，同時也是一種有效的測試用例生成技術。因此，偽距定位程序作為一種典型的數值計算程序，也可嘗試性地將蛻變測試技術應用在此類軟件的測試過程中。

2 偽距定位及其基本算法

2.1 偽距與偽距定位

由于衛星鐘差、用戶終端設備的鐘差以及無線電信號經過電離層和對流層中的延遲，實際測出的距離與衛星到用戶終端設備的幾何距離有一定的差值，因此，將這一量測值稱之為偽距[13]。

偽距定位程序是位置解算中的核心程序之一，也是衛星導航接收機軟件系統的重要組成部分，該程序實現的正確性對接收機充發揮其使用效能至關重要。衛星導航系統中偽距定位程序的工作原理如圖2所示。

圖2 偽距定位程序基本工作原理

偽距作為衛星導航系統中的重要概念之一，是接收機對衛星導航信號的一個核心的觀測值，也是接收機定位的集成量值，其計算公式如式(1)所示

(1)

利用偽距進行定位是衛星導航系統中常用的定位方式之一，結合式(1)即可解算出接收機的具體位置。

(2)

2.2 偽距定位的基本算法

由式(2)可知，求解偽距定位過程本質上是一個求解四元非線性方程組的過程，而“牛頓迭代-最小二乘法”是>一種傳統偽距定位的解算方法。采用該方法可得到式(2)在 [xk-1，δtu，k-1]T處線性化處理后的求解矩陣，如式(3)所示

(3)

其中

(4)

(5)

(6)

3 偽距定位程序的蛻變測試方法

3.1 偽距定位程序的蛻變測試流程

偽距定位程序的蛻變測試基本流程主要包括測試準備、蛻變關系正確性判斷和有效性判斷3個階段。偽距定位程序的蛻變測試流程基本框架如圖3所示。

圖3 偽距定位程序的蛻變測試流程框架

第一階段為測試準備階段，主要包括測試用例生成、蛻變關系構造和衍生測試用例生成3個內容。首先，測試人員采用傳統的測試用例生成方法針對被測試程序P及軟件需求規格說明生成原始測試用例集T；其次，進一步結合被測試程序P的特點等構造蛻變關系MRi；最后，針對所構造的蛻變關系MRi生成原始測試用例集T的衍生測試用例集T′。

第二階段為蛻變關系正確性判斷階段，主要包括測試執行和正確性判斷兩個內容。首先，針對被測試程序P分別執行原始測試集T和衍生測試集T′，并記錄相應的測試執行結果；其次，依據構造的蛻變關系MRi，比較原始測試集T和衍生測試集T′的測試執行結果RP和R′P，并進行正確性判斷，即判定其是否滿足蛻變關系，如果滿足蛻變關系，則轉入第三階段，開展蛻變關系有效性判斷工作；反之，則重新進入第一階段，并結合偽距定位程序特點重新構建蛻變關系MRi。

第三階段為蛻變關系有效性判斷階段。由于，變異分析技術是一種對測試用例質量及其充分性進行判斷的有效方法，同時也可對蛻變測試的有效性進行評價[14]。因此，在這一階段中，本文采用變異分析技術對構造的蛻變關系進行有效性判斷。該階段主要包括程序變異、測試執行和蛻變關系判定(即判斷測試用例是否殺死變異體)3個內容。首先，結合程序P的特點選擇不同變異算子對被測試程序P進行變異得到P′；其次，針對變異后的程序P′，分別執行原始測試集T和衍生測試集T′，得到的測試執行結果RP′和R′P′；最后，通過比對測試執行結果RP′和R′P′一致性對變異體的有效性進行判斷，若執行結果一致，則說明構造的蛻變關系MRi有效，反之，則說明所構造的蛻變關系無效，需返回第一階段選擇下一個構造關系MRi進行判斷。

本文重點就第一階段中蛻變構造進行重點論述，并就第三階段中變異算子的選擇進行說明。

3.2 偽距定位程序蛻變關系的構造

蛻變關系構造的有效性是決定蛻變測試方法是否成功的關鍵，同時也是該方法與傳統軟件測試方法的區別所在[14]。但是，由于蛻變測試技術和蛻變關系的構造并不具備普適性，且沒有統一的標準與方法，因此，在構造蛻變關系時就必須結合被測試程序的具體特點(如算法特點、程序求解過程等)及其需求規格說明等文件，有針對性的構造被測試程序的蛻變關系[15]。

依據偽距定位程序的基本工作原理及自身算法和求解過程的特性，本文從空間立體幾何變換屬性以及算法的數值計算特性等方面構造偽距定位程序相應的蛻變關系。

3.2.1 構造蛻變關系MR1

由圖2可知，衛星導航系統中偽距定位程序及其計算方式的空間立體幾何變換屬性可以看作是由地心、接收機以及導航衛星所構建的空間距離關系決定的，其中地心可視為該空間距離關系的坐標原點(即圓心)，因此，可以基于空間關系特性中的對稱關系構建偽距定位程序的蛻變關系MR1，具體構造情況見表1。

表1 蛻變關系MR1的構造

從表1中可以看出蛻變關系MR1總計包含三大類7個空間對稱關系。具體可以分為三大類空間對稱關系：蛻變關系MR1_1是滿足以地心o為中心對稱原點的中心對稱關系；MR1_2、MR1_3、MR1_4等3個蛻變關系是分別滿足以xoy、xoz和yoz這3個平面為對稱面的平面對稱關系；MR1_5、MR1_6、MR1_7等3個蛻變關系是分別滿足以x軸、y軸和z軸3個坐標軸為對稱軸的軸對稱關系。

3.2.2 構造蛻變關系MR2

在空間立體幾何變換屬性中，除了對稱關系外，縮放比例關系也是其中重要的特性之一。當接收機和衛星的空間坐標位置同時延x、y和z這3個坐標軸正向按照比例縮放k(k>0)時，從而接收機的定位結果與衛星在空間坐標位置成對應的縮放比例關系。

此外，在通過空間幾何縮放比例構建蛻變關系時，在不考慮衛星鐘差、用戶終端設備的鐘差以及無線電信號經過電離層和對流層中的延遲等因素影響的情況下，導航信號在空間傳播距離與傳輸時間之間的比例關系，滿足空間等比例縮放關系。從而，可以針對式(2)按照空間幾何縮放比例關系得到如式(7)所示的偽距定位程序。

得到如式(7)所示的基于空間幾何縮放比例變換后的偽距定位程序

(7)

其中，k>0。

綜上，可以基于空間距離關系特性中的空間幾何縮放比例關系構造蛻變關系MR2，具體見表2。

通常而言，為確保空間縮放關系構造的有效性，蛻變關系MR2_1中的縮放比例系數k一般為k>0。

3.2.3 構造蛻變關系MR3

由于在接收機接收軟件中的偽距定位程序中涉及到電離層時延、對流層時延等諸多復雜因素，因此，為了明確蛻變測試技術在偽距定位程序中的典型應用，本文僅對與空間位置計算相關程序的部分進行分析。

在偽距定位的基本算法中，求解方程常用的關鍵方法是采用最小二乘法。結合最小二乘法的基本公式，可以得到式(5)的最小二乘法解為

(8)

由式(8)可以發現，偽距定位程序中所用算法的核心思想是進行矩陣變換工作并開展矩陣乘法計算，且該矩陣通常具備稀疏矩陣的特性。因此，在求解接收位置信息的過程中，可以構造基于矩陣變換原理的蛻變關系MR3，具體見表3。

表3 蛻變關系MR3的構造

從表3中可以看出蛻變關系MR3總計包含了3個不同的矩陣計算等價關系。蛻變關系MR3_1滿足矩陣相乘的轉置計算等價關系；蛻變關系MR3_2滿足逆矩陣相乘的轉置計算等價關系；蛻變關系MR3_3滿足稀疏矩陣逆矩陣的轉置等價關系。

3.3 變異算子選擇

采用變異分析技術進行蛻變關系有效性判斷，通常是通過選取不同變異算子的方式開展的。通常而言，常系數替換、比較關系替換、邏輯比較替換、數值運算符替換以及插入絕對值等5種算子是較為常見的變異算子，且其幾乎可以覆蓋所有計算機程序的語法類型：語句、謂詞表達、算數表達和關系運算等。

變異算子的選擇是應用變異分析技術開展蛻變關系有效性判斷的核心。通常而言，常數替換、比較關系替換、邏輯運算符替換、數學運算符替換和絕對值插入等5種變異算子，幾乎可覆蓋所有的編程語法類型，即：語句、謂詞、算術表達式、關系運算符等。

因此，結合偽距定位程序的程序及算法特性，選擇常系數替換(變異算子1)和數值運算符(變異算子2)兩種變異算子，并植入被測試程序中。

針對偽距定位程序中的式(2)植入上述兩種變異算子，即可得到變異后的偽距定位程序計算公式，具體如式(9)和式(10)所示，并為后續變異分析提供變異后的程序P′。

變異算子1

(9)

變異算子2

(10)

在各類數值計算算法實際實現過程中，上述兩種變異算子所體現在編程中的錯誤是較為常見且會使得程序輸出結果難以判斷正確與否，因此，很難通過傳統測試方法和內部測試進行檢驗。

4 實驗分析

4.1 實驗對象及環境

為驗證蛻變測試技術在偽距定位程序軟件測試中的可行性，本文以相關北斗衛星導航系統接收機設備中的偽距定位算法程序P為被測試程序開展實驗，實驗環境為被測試程序運行所依賴的嵌入式操作系統環境。同時，在實驗過程中不考慮衛星鐘差、用戶終端設備的鐘差以及無線電信號經過電離層和對流層中的延遲等復雜因素。

4.2 實驗步驟

實驗步驟依據偽距定位程序的蛻變測試流程實施：

在測試準備階段，首先，通過傳統方法從測試樣例庫中選取標準定位結果作為本次實驗被測試程序P的原始測試用例集T0；其次，基于原始測試用例集T并結合3.1節中的3類11個蛻變關系，生成對應衍生測試用例集T′={T′MR1_1，T′MR1_2，T′MR1_3，T′MR1_4，T′MR1_5，T′MR1_6，T′MR1_7，T′MR2_1，T′MR3_1，T′MR3_2，T′MR3_3}。

在蛻變關系正確性判斷階段，首先針對被測試程序P分別執行原始測試用例集T和衍生測試用例集T′，分別得到測試執行結果RP和R′P，通過判斷測試結果是否一致進行蛻變關系正確性判斷。

在蛻變關系有效性判斷階段，針對被測試程序P依據變異算子得到的式(9)和式(10)生成變異程序P′1和P′2，并分別執行原始測試集T和衍生測試集T′，得到的測試執行結果RP′1、R′P′1和RP′2、R′P′2，通過判斷測試結果是否相同來確定是否殺死變異體，從而對構造的蛻變關系有效性進行判斷，最終完成本次實驗。

4.3 實驗結果

本次實驗執行的具體測試執行情況見表4。表格中(a，b)表示一組執行結果，其中第一個數值a表示執行測試用例的個數，第二個數值b表示未通過的測試用例數的個數。

表4 偽距定位程序的測試執行情況

4.4 結果比對

從表4所給出的不同蛻變關系的測試執行情況來看，基于空間立體幾何變換屬性中的對稱關系所構建的蛻變關系MR1，對于變異體1和變異體2而言，其平均檢錯率分別約為70.78%和77.39%，蛻變關系MR1整體檢測率約為74.09%；而基于空間立體幾何變換屬性中的空間幾何縮放比例關系所構建的蛻變關系MR2，則無法檢測出兩個變異體中的缺陷與不足；基于矩陣變換原理所構建的蛻變關系MR3，對于變異體1和變異體2而言，其平均檢錯率分別約為96.01%和95.02%，蛻變關系MR3整體檢測率約為95.52%。

圖4給出了本文中構造的3類11個蛻變關系對被測試程序P的檢錯率統計示意圖。

圖4 蛻變關系的檢錯率統計

4.5 結論分析

第一，在程序檢錯能力方面。由于該方法檢驗出了無法滿足蛻變關系的原始測試用例和衍生測試用例，因此，實驗結果表明：只要有針對性的構建并選擇合理的蛻變關系，采用蛻變測試的方法，就可以發現偽距定位程序中所隱含的缺陷和問題。就本次具體實驗對象而言，程序中偽距定位相關算法存在的主要缺陷體現在空間關系轉換及矩陣計算過程中算術表達式及關系運算符的錯誤等。

第二，在蛻變關系檢測能力方面。首先，蛻變關系MR3的檢測能力明顯強于蛻變關系MR1和MR2的檢測能力，這是因為蛻變關系MR1和MR2是基于空間立體幾何變換屬性(空間對稱關系和空間縮放比例關系)而構造的，其蛻變關系強度相對簡單，因此檢錯能力較弱；而蛻變關系MR3則是基于矩陣運算關系進行構造的，這一類蛻變關系的構造更接近于程序算法本身，且運用了較為復雜的矩陣計算數學關系式，因此，也就滿足了在構造蛻變關系時應“優先選擇較為復雜的表達式”這一首要原則。綜上，蛻變關系MR1和MR2較之蛻變關系MR3更弱。其次，對于同屬于空間立體幾何變換屬性構造的蛻變關系MR1和MR2而言，MR1的檢錯能力較MR2而言相對較強。這是因為MR2作為比例關系而言，其在計算過程中僅進行了等比縮放，其運算復雜程度較蛻變關系MR1明顯更為簡單，因此，蛻變關系MR2的檢錯能力較之蛻變關系MR1而言，也相對較弱。

5 結束語

本文提出將蛻變測試方法應用于衛星導航接收機軟件中偽距定位程序的測試中，通過分析被測試程序中幾何變換屬性、算法實現和數值計算等具體特點，構建了3類11個蛻變關系，并通過實驗驗證了該方法對解決此類程序中“測試判定”問題的有效性。該方法在擴大蛻變測試應用范圍的同時，也有效解決了傳統測試方法在開展此類程序測試過程中所面臨的不足與缺陷。