基于統一無窮理論的軟件測試可窮盡性研究

何智濤，何華燦，劉超（.北京航空航天大學計算機學院，北京009；.西北工業大學計算機學院，陜西西安7007）

基于統一無窮理論的軟件測試可窮盡性研究

何智濤1，何華燦2，劉超1
（1.北京航空航天大學計算機學院，北京100191；2.西北工業大學計算機學院，陜西西安710072）

傳統認為只要繼續測試，總能發現新的軟件缺陷，這使軟件測試可信失去了理論基礎。針對軟件測試可窮盡性開展理論研究，將討論范圍從有窮領域擴展到無窮領域。首先從最新的實無窮理論研究成果統一無窮理論入手，得出了利用有限開銷來判斷無窮過程可信性的基本方法，從軟件特征定義入手，形式化定義了軟件測試用例集合，得出了軟件特征與測試用例／軟件缺陷之間的對應關系；基于統一實無窮理論研究成果和統一數學歸納法，討論了軟件測試版本持續演化過程中，測試用例集合可窮盡性與軟件測試質量的關系，回答了當測試用例集合是一個無窮集合時，軟件測試該如何開展軟件測試是否能窮盡的理論問題，并剖析測試可窮盡性的舊有認識。該文研究成果初步回答了困擾軟件測試理論界多年的軟件測試可窮盡性問題，為軟件測試可信性研究奠定了堅實的理論基礎。關鍵詞：軟件測試；統一無窮理論；軟件特征；測試用例集合；測試可窮盡性；測試可信性；軟件缺陷；軟件測試演化過程；統一數學歸納法

隨著計算機的普及應用，軟件系統的重要性不斷提高。然而，與計算機系統同一天誕生的軟件系統，自始至終都飽受軟件缺陷的困擾。計算機發展史上著名的千年蟲問題，曾經給全球造成6 000億美元的損失，人類航天史上也曾經由于軟件缺陷造成多次發射或探測任務的失敗，如1999年的NASA火星探測器登陸火星表面時失敗。而自20世紀80年來以來，商業或軍事應用系統中含有的軟件缺陷所造成的軟件質量問題，給用戶／軍方帶來的損失更是不可估量。

軟件缺陷作為主要因素之一，曾經導致了20世紀60年代的軟件危機并由此引出了軟件工程學科。在21世紀的今天，軟件測試的重要性已得到計算機業界的廣泛共識。軟件測試的概念從早期Myers的“測試是為了發現錯誤而執行的一個程序或系統的過程”［1］，即“測試目的是發現軟件缺陷”，發展成為今天的IEEE610.12標準中的更為全面的面向軟件質量的測試定義：“測試是在規定條件下運行系統或構件的過程，也是分析評估項目質量特性的過程”［2］，即測試目的是為了確保軟件質量。自此，軟件測試領域的相關研究也成為軟件工程領域的持續研究熱點。

隨著模塊化、構件化、面向對象技術和中間件技術的應用普及，軟件系統向著集成化、規?；确较蜓杆侔l展，軟件系統復雜性不斷上升，軟件代碼規模日益龐大，復雜軟件系統的軟件代碼規模已經達到了千萬行以上級別，軟件系統日益表現出開放性、動態性、不可預測性和潛在不安全性等諸多特性，為進行軟件測試所設計的測試用例數量呈組合爆炸趨勢。軟件測試的難度與成本在不斷快速攀升的同時，軟件正面臨著嚴重的信任危機，即可信性危機。

產生軟件可信性危機的根源來自軟件系統日益表現出的開放性、動態性、不可預測性和潛在不安全性等諸多特性。從系統角度出發，ISO／IEC 15408（信息安全評估準則）認為一個可信的組件，其操作或過程的行為在任意操作條件下是可預測的，并能很好地抵抗由其他應用軟件、病毒以及一定的物理干擾造成的破壞［3］。當前軟件工程領域內對軟件可信性危機的解決方法也是遵循這樣一個基本原則，即意在證明一個軟件系統的行為總是與預期一致。由此主旨引申出了幾個與軟件可信性相關的研究熱點，即高可信軟件程序語言與可信編程、可信軟件開發方法、軟件可靠性測試與評估等［4?7］。

在可信軟件開發方法研究領域中，可信軟件測試過程的研究是其中的核心內容之一?？尚跑浖y試過程的研究目標旨在研究軟件測試的理論與方法，使軟件測試過程成為一個可預期的過程，這種可預期的軟件測試過程將對軟件測試的質量有決定性作用，并進而確保軟件質量和軟件可信性。

回顧人類近5 000年的科學歷史不難發現，在一門學科的基礎理論上出現危機之時，就是該學科領域的學者需要反思之日。歷史上的科學家們在解決危機時一般都有2個完全不同方向的選擇：1）在原有理論基礎上進行修補完善；2）返回概念的原點進行重新的描述和探索，尋求變革之道?？茖W實踐證明，在面臨重大而深刻的理論危機時，變革往往是解決理論危機的最好方法和必由之路，它有可能開啟新興學科并使人類的科學認識發生跨越式變化。

通過對軟件測試可信性追根溯源的系統研究中，發現在軟件測試的實踐中，一般都假設軟件中的潛伏缺陷是有限的。但是無法確認通過有限的測試過程是否能夠發現所有的缺陷。其內在原因是有限的測試不一定能夠窮盡所有可能的輸入狀態，也不一定能夠窮盡所有可能的執行路徑，從而把所有軟件缺陷全部挖掘干凈，因為在軟件中潛伏的缺陷不是靜止不變的，為了排除已經發現的缺陷需要修改軟件，但在升級軟件版本的過程中又可能引入新的潛伏缺陷，這是一個此消彼長的過程，它有可能收斂，也可能發散。這種認知狀況導致任何現實可能的測試過程都無法確保發現軟件中潛藏的所有缺陷。于是就形成這樣一種信念：只要繼續測試下去，總有可能發現新的軟件缺陷。

這就是說，軟件系統的缺陷在理論上是不可被窮盡的，軟件測試只能被局限在一個有限的過程內而無法進行到底，真正把軟件缺陷全部發現完畢只是一個潛在的不可達的理想目標，而不是現實目標。這樣的認識影響了軟件測試的可信性概念本身，阻礙了軟件可信性危機的解決。因為既然在現實中發現一個軟件系統的所有軟件缺陷是不可能的，那就根本無法通過軟件測試保證軟件是沒有缺陷的。既然通過軟件測試無法保證軟件沒有缺陷，那么剩余軟件缺陷的影響范圍和嚴重性將無法預知，軟件系統的質量也不可預知，軟件測試的可信性失去了理論上的保障！

在此背景下，筆者認為目前在軟件業界面臨著一個不可回避的有關軟件測試質量的基本科學問題有待研究解決，即通過軟件測試，一個軟件系統中的軟件缺陷發現過程是否可以被窮盡？

眾所周知，軟件系統的行為可以被抽象為一個用例集合，而用例集合可以通過一個映射變換成為測試用例集合。因此，軟件測試可被抽象為這樣一個過程，即針對軟件系統的構成和行為設計和執行測試用例，并據此發現和處理軟件缺陷的過程。同時軟件缺陷與測試用例間存在嚴格對應關系。

由于被測軟件系統不是靜止不變的，而是在持續不斷地演化，與生物在演化方面有一定的相似性。被測軟件在其生命周期中為了獲取更好的軟件質量和適應用戶需求的不斷變化，其自身在不斷演化并產生一系列的軟件測試版本，這些軟件測試版本帶有遺傳和變異的特征：新測試版本帶有舊測試版本的絕大多數特征——遺傳，而外界環境的刺激會給被測軟件系統帶來變異，這些刺激主要來源于用戶方對軟件需求的變更或軟件測試者在測試過程中所揭示的軟件缺陷（實質是不符合既定需求）。

因此，對于上述基本科學問題，利用測試用例集合、測試用例與軟件缺陷的關系及其軟件測試演化的概念，可進一步描述為：在軟件需求固定不變或持續變化的場景下，軟件測試版本相應處于不斷的演化過程中，假如針對軟件測試的投入是足夠的和持續不斷的，軟件測試是否可以窮盡測試用例全集中的所有測試用例，使被測軟件系統達到理想的質量狀況？

這雖然是一個理論問題，但也是探討系列工程技術問題的基礎。它刻畫的是一個理想極限狀態，是揭示各種測試方法和技術的共性特征和差異的基礎。對這個問題的解答需要分不同情況來討論：

第1種情況，在用戶需求和被測軟件功能不變的情況下，由于軟件缺陷規模本身是有限的，困難在于測試用例集合的動態變化。要回答這個基本科學問題，其實質是探索是否存在這樣的軟件測試質量評價函數和測試用例集合動態生成機制，它能夠通過有限步操作來解決測試用例集合的可窮盡性問題。具體說就是尋找這樣的軟件測試質量評價函數P（x），對于任何規模軟件系統的測試用例集合，都嚴格用非負整數n遞增編號，要求P（n）能夠保證如下軟件缺陷遞減條件：1）確認n0號測試用例集合已經發現了軟件缺陷，能夠使P（n0）為真；2）確認測試用例集合動態生成機制能夠保證，只要n號測試用例集合已發現軟件缺陷，能夠使P（n）為真，則生成的下一個n＋1號測試用例集合一定可發現軟件缺陷，使P（n＋1）為真；3）則軟件測試過程可在有限步操作之內窮盡所有的軟件缺陷；否則軟件系統中的軟件缺陷將不可能在本測試用例集合動態生成機制中被窮盡。

第2種情況，被測軟件在測試過程中需要不斷被修改，以克服已發現的軟件缺陷，形成新的測試版本。新測試版本主要遺傳了老測試版本的基本特征，也帶有某些新的變異，可能是一個持續演化過程，將帶來軟件功能的變化和新軟件缺陷的潛入。所以，在研究測試用例集合動態生成機制和軟件測試質量評價函數P（x）時，必須考慮被測軟件演化因素，在軟件測試用例集合中反映出演化前后的差異，這些差異來源于對已發現的軟件缺陷的消除，以及在消除軟件缺陷過程中有可能潛入的新軟件缺陷。當然，為最大限度減少在軟件測試版本升級過程中新軟件缺陷的潛入，對軟件測試版本升級的過程也應該進行嚴格質量控制。它需要統一反映在P（x）中，不過這不是軟件測試者的職責，而是軟件開發者的職責，所以本文沒有深入展開討論。

針對第1種情況的問題解決，只需要在有窮域內討論即可，而針對第2種情況的問題解決，則需要在無窮域內進行討論，因為持續的軟件測試演化使軟件缺陷發現過程進入一個無窮過程，無窮理論有助于用有限／無限的開銷來判定一個軟件測試過程的窮盡性和可信性，數學基礎理論中有關無窮的研究成果對本論文的研究將起到關鍵性作用。因此有必要在本論文中引入無窮理論的最新研究成果，在此基礎上再依據軟件測試用例集合的形式化模型對本論文提出的科學問題進行深入討論。

1 3種主要無窮觀

人類認識數至少已有30萬年的歷史，到19世紀末，在實無窮意義下的一種實數概念和理論已基本形成，其間經歷了自然數、分數、數字“0”、負數和無理數等5個主要認識階段，近100多年來對數系的進一步深入認識主要表現在2個方面：1）繼續探索實無窮的可能概念，以最終完成對實數本質的深入認識，建立更簡捷的實數概念和理論；2）通過對實數的組合運用，形成更復雜的數，如復數（加入虛數）、狹義數（加入超復數）和廣義數（加入向量、張量、矩陣等）［8］.

1.1 現有的3種主要無窮觀

歷史上出現過各種各樣的無窮觀，主要是3種。前2種是在2 300多年前就已出現的相互完全對立的無窮假設，第3種是100多年前才提出的無窮假設，并已形成了完整的理論體系，在現代數學中占據統治地位。

1）潛無窮觀：假設無窮是一個永無終止的增長過程，無窮大不是數，不能參加運算。也就是說無窮只是一種說話方式而已，它表示對任何一個自然數，都能找到一個比它更大的自然數，但決不可能窮舉所有的自然數。這就是說潛無窮過程的基本特征是“此外永有”。

2）統一實無窮觀：假設實無窮大是一個惟一存在的特殊數，能夠參與運算，它不僅比任何有限數都大，而且不存在比實無窮大更大的數，實無窮大的任何運算結果都不會大于實無窮大，它是能夠包容一切增長過程的理論極限。這就是說實無窮過程的基本特征是“此外永無”。

3）層次實無窮觀：層次實無窮觀是現行的實無窮觀，它假設實無窮過程可以自我完成，實無窮大是一個數，能夠參與運算。但又假設實無窮大有無限多的分層，最小的實無窮大是可數無窮0，更高一級的實無窮大是不可數無窮1，1＝20，其他以此類推。可見層次實無窮觀中雖然給出了實無窮大數，這些數都可以參與運算，但是與統一實無窮觀“此外永無”的無窮主張不同，這些實無窮大仍然具有潛無窮觀“此外永有”的基本特征，所以層次實無窮觀實際上是潛無窮觀和實無窮觀的混合物。

總體來看，這3種無窮觀都承認需要有無窮概念存在，差別僅僅是無窮大是否是數以及有多少個無窮大數：

潛無窮觀認為在正整數域中只有不斷增大的自然數（［0數類］）和一個不可達的潛無窮大符號ω，沒有數類質變，也就沒有實無窮大∞存在。

統一實無窮觀認為除了潛無窮過程（其中沒有數類質變）外，還有實無窮過程（其中存在數類質變），所以在非負整數域中，除有窮的自然數（屬于［0數類］）外，還有超窮的趨近無窮正整數（屬于［ω數類］）和一個實無窮大∞。

層次實無窮觀認為無窮過程中存在數類質變，所以在非負整數域中，除有窮的自然數（［0數類］）外，還有超窮的［ωi數類］（i＝0，1，...），［0數類］集合的基數是實無窮大0，［ωi數類］集合的基數是實無窮大i＋1，實無窮大∞被分解為一個無窮數列0，1，2，3，…。這些無窮觀反映了在不同數域模型假設中，數域的大小及其基本性質是完全不同的，可以適應不同的應用環境。

1.2 層次無窮理論

康托爾為了把他的層次無窮主張建立在嚴格的邏輯框架內，成為能夠自圓其說的學說，建立了樸素集合論，無窮集合理論是樸素集合論的重要組成部分之一，其要點如下［8，10?12］：

1）有窮集合和無窮集合：如果在集合A的元素和集合B的元素之間能夠建立一一對應的關系，則稱集合A和集合B等勢，記作｜A｜＝｜B｜。如果一個集合能夠和它自己的真子集等勢，則這個集合稱為無窮集合，否則稱為有窮集合.

2）無窮集合的大小關系：規定自然數集合N是最小的無窮集合，稱為可數集合，其基數是可數無窮大0。如果能找到一種一一對應方式證明無窮集合A與自然數集合N等勢，則A也是可數集合，其勢是可數無窮大0。如果所有的方式都不能證明A與N等勢，則A是更大的無窮集合，稱為不可數集合，不可數集的勢大于可數集的勢0.康托爾利用對角線法證明單位區間實數集合R1是不可數集合，規定它的勢為1＝20，并假定在0和1之間沒有其他無窮集合的勢存在（即連續統假設）。這就是說，單位區間實數集合R1是0級不可數集合，利用公式i＋1＝2i還可獲得越來越大的高級不可數集合，這些集合的勢分別是2，3，4..。

3）超窮數理論：康托爾為了解釋他的實無窮理論為什么在沒有最大元存在的自然數集合之外（上），還能夠有更大的超窮數存在，引入了序數的3個生成原則和配套的概念及規定，建立了超窮序數理論和超窮基數理論。在自然數中，任一數n既是序數，也是基數，序數和基數可以通過后繼操作同步增大。在超窮數中，任一超窮序數n?有可能是超窮基數，也有可能不是，超窮序數和超窮基數不能通過后繼操作同步增大。

超窮數理論的要點是：

①第1生成（延伸）原則：0是自然數的（即有窮序數）的生成基，1是生成元，從0開始相繼＋1能夠生成所有的自然數（有窮序數），其中沒有最大元出現。自然數既是有窮序數，也是有窮基數，屬于［0數類］。

②第2生成（窮竭）原則：規定自然數集合｛0，1，2，3，…，n，n＋1，…｝的基數0是最小的超窮序數ω0。以ω0為生成基繼續延伸，ω0＋1，ω0＋2，ω0＋3，…可生成越來越大的超窮序數，其中沒有最大元出現，它們全部屬于［ω0數類］。［ω0數類］中的每一個超窮序數的基數都是0。

③第3生成（限制）原則：規定［ωi數類］中所有超窮序數組成的集合的勢i＋1是更大的超窮序數ωi＋1，ωi＋1大于［ωi數類］中的所有超窮序數，但本身不在［ωi數類］中（i＝0，1，2，3，…）。

2 統一無窮理論研究現狀

在何華燦和何智濤共同提出的統一實無窮數域模型假設中，利用數的理想計數器模型，證明了在位數保持一致的情況下（包括有窮位、趨近無窮位和實無窮位），非負整數的編碼和非負小數的編碼永遠保持一樣多，差別僅僅是小數點的位置不同而已。所以，如果按照傳統思想認為所有的非負整數總共有∞個，所有的非負小數總共有2∞個，那么一定有2∞＝∞的關系成立，實無窮大∞惟一存在，并且它不可能再繼續增大了。這就是說，在統一實無窮數域模型假設中，所謂的“不可數集合”根本不存在，困擾數學界多年的連續統假設可以排除，由于不可數集合的排除，統一無窮理論也可以作為軟件測試可信性理論的重要理論基礎使用。［9，12］

2.1 統一無窮理論要點

1）計數器的編碼規律。根據數的理想計數器模型可歸納出計數器的編碼規律如下：

①有窮非負整（?。抵恍枰糜懈F位的編碼表示，有窮位的編碼只能表示有窮非負整（?。?，不可能越界表示趨近無窮正整（小）數。

②趨近無窮正整（?。敌枰泌吔鼰o窮位的編碼表示，趨近無窮位的編碼可表示非負正整（?。岛挖吔鼰o窮正整（?。?，不可能越界表示實無窮大（?。?/p>

③實無窮大∞只能用∞位的特殊編碼（1；0..0；0...0）（進位溢出信號）表示，∞位的編碼可以表示有窮非負整（?。?、趨近無窮正整（?。岛蛯崯o窮大∞（實無窮小δ＝1／∞）。對應的編碼是∞＝（1；0...0；0...0），δ＝（0.0..0；0..0；1）。

2）統一數學歸納法。由于潛無窮過程只能停留在［0數類］內不能達到自我完成的狀態。而實無窮過程中∞可達，非負整數的生成過程可以跨越［0數類］和［ω數類］直達∞，達到自我完成的狀態。所以有可能把局限于有窮自然數范圍的數學歸納法進一步與超窮數中的數學歸納法結合，形成統一數學歸納法，其結論不是對任意的自然數n，P（n）為真，而是直接獲得在實無窮大時P（∞）為真的結果。

3）非負整數的生成三原則。為了建立統一無窮理論的公理系統，原則上繼承了康托爾生成超窮數的三原則，并進行了必要的修改，作為生成整個非負整數域的原則，其具體內容如下：

①第1生成（延伸）原則：從0開始相繼＋1生成的所有非負整數都是自然數，其中沒有最大元出現，屬于［0數類］。生成過程中的自然數集合是一個0級潛無窮開集，用變量符號?表示。

②第2生成（窮竭）原則：生成完畢的自然數集合是所有自然數組成的并集，是最小的趨近無窮閉集合，用常量符號ω表示，它是最小的趨近無窮正整數。以ω為生成基繼續延伸，可生成越來越大的趨近無窮正整數ω＋1，ω＋2，ω＋3，…，其中沒有最大元。趨近無窮正整數既是超窮序數，也是超窮基數，屬于［ω數類］。生成過程中的趨近無窮正整數集合是一個1級潛無窮開集，用變量符號∝表示。

③第3生成（終止）原則：生成完畢的趨近無窮正整數集合是所有自然數和所有趨近無窮正整數組成的并類，規定它是惟一的實無窮真類（實無窮大）∞，所有的集合（數）包含于（小于）∞。

在統一實無窮數域模型中，非負整數是一個封閉域，其中0是最小的非負整數，稱為左極限非負整數，它沒有前趨，有后繼；ω是中極限非負整數，它沒有前趨，有后繼，是承前啟后的非負整數；∞是最大的非負整數，稱為右極限非負整數，它沒有前趨，也沒有后繼。?和∝是表示開集的符號，可理解為正在不斷增大、沒有上限的有窮非負整數變量和超窮正整數變量。

4）無窮編碼的不變性原理ICI（infinite codes in?variation，ICI）。ICI原理由∞位計數器生成的編碼數仍然是∞個，2∞＝∞。理由如下：

①一個數既可看成是幾何點，也可看成是進位制編碼，兩者一一對應。

②∞個幾何點可在一條直線上從頭到尾地排列，每一個點可以擁有一個惟一的進位制編碼。

③由于實無窮大∞可達，所以完整的∞位進位制編碼可按照計算器的生成順序從小到大地排列，與直線上的點形成一一對應關系。

于是從編碼的角度看∞位的二進制編碼共有2∞個，從幾何點的角度看，這些編碼能夠與∞個整數一一對應。結果必然是2∞＝∞，這是有窮和無窮的本質差別。

5）非負整數的內蘊性質和排序性質。有一個定義在非負整數集合上的性質P（x），它如滿足：①P（n0）為真，②任意P（n）為真，則P（n＋1）一定為真，稱P（x）為第2類（排序類）性質。反之，它如滿足：①P（n0）為真，②任意P（n）為真，P（n＋1）不一定為真，稱P（x）為第1類（內蘊類）性質。

在涉及非負整數的第1類性質的無窮性時，進入的是一個潛無窮過程，它只能遍歷有窮的自然數域，潛無窮大是一個只能無限接近，但永遠不可達到的目標。即有窮自然數不可窮盡，潛無窮過程不能自我完成，無法進入超窮的正整數域。

在涉及非負整數的第2類性質的無窮性時，進入的是一個實無窮過程，它可以自我完成，到達無窮大∞。即全部的有窮自然數、趨近無窮自然數和∞都可以自動生成出來。

2.2 統一無窮理論與軟件測試可窮盡性研究

統一無窮理論的研究成果為本文的軟件測試可窮盡性研究提供了重要的數學基礎。ICI原理為可參與數學運算的惟一實無窮大∞提供了理論基礎，而基于實無窮大∞可達的統一數學歸納法使得討論趨于無窮場景下的軟件測試可窮盡性有了相應方法支持，即實無窮過程中實無窮大∞具有可達性，在一定條件下可以獲得P（∞）為真的結果，可幫助用有限的開銷來判定一個軟件測試過程的可信度。

在討論一個無窮過程的性質P（x），x→∞時，由于人的認識和計算機的操作都只能是有限步的，不能直接去窮盡所有的可能性，所以區分P（x）的性質屬于哪一類十分重要：

當P（x）屬于第2類（排序類）性質時，可通過有限步操作在理論上窮盡所有的可能性；

當P（x）屬于第1類（內蘊類）性質時：

①如果P（x）具有收斂性，則可在有限步操作內、在小于允許失誤概率的意義下窮盡所有的可能性；

②如果P（x）發散或者震蕩，則不可能窮盡所有的可能性。

所以，如果能夠在軟件測試質量評價的模型中把軟件測試質量評價函數P（x）控制在第2類性質中，就可以利用有限的開銷自動獲得窮盡所有可能性的效果，判斷這個軟件測試過程是絕對可信的。如果能夠證明P（x）是第1類函數，它能夠收斂，而且允許軟件有一定的失誤概率，那么就可以利用有限開銷來判定這個軟件是可信的。如果P（x）不收斂，是發散或者震蕩的，那么也可以利用有限開銷來判定這個軟件是不可信的。

3 測試用例集合形式化定義

本節將通過概念剖析，對測試用例集合進行形式化定義，以便于基于統一無窮理論來研究測試用例集合的可窮盡性問題。

依據軟件工程理論，軟件系統與軟件需求規格說明（軟件設計說明）之間存在著對應關系。軟件需求規格說明（軟件設計說明）中描述的軟件特征最終在被測軟件系統中獲得展現。而軟件需求規格說明中的軟件用例則對軟件需求說明中描述的軟件特征進行了覆蓋（軟件設計說明中的說明描述是軟件需求規格說明中用例的一個變換，在理論上可構造一一對應關系）。所有軟件用例組成的集合形成了軟件系統行為空間。軟件系統的行為可以被抽象為一個用例集合，而用例集合可以通過一個映射變換成為測試用例集合。

因此，軟件測試可被抽象為這樣一個過程，即依據軟件設計說明或軟件需求規格說明，針對軟件系統的邏輯構成或系統行為設計測試用例集合，在被測軟件上執行測試用例集合，并據此發現和處理軟件缺陷的過程，同時軟件缺陷與測試用例間存在著對應關系。

軟件測試中依據從軟件需求轉換而來的軟件測試需求，將軟件用例集合轉換成為軟件測試用例集合，在被測軟件上對期望軟件中的軟件特征進行覆蓋和驗證。

為了便于后續的形式化定義［13］，這里將首先對期望軟件和被測軟件做出定義。

定義1 期望軟件和被測軟件。期望軟件，記為S，即軟件需求和軟件設計所描述的軟件。

被測軟件，記為S′，即編碼實現后的軟件。

定義2 軟件特征。軟件特征來自于軟件需求說明或軟件設計說明，是對期望軟件自身固有的或者所表現出的一個具體特點的描述。

形式化上，軟件特征可以被看做是關于期望軟件S的一個命題，記作fs。說明該期望軟件具備某個具體特征，并且存在著相對簡明的方法判定其命題真值（真／假），特別是通過有限的測試用例的測試、自動審查或人工評審等方法。

定義3 軟件特征域。由期望軟件S的具有某些相同性質的特征組成的集合被稱作該期望軟件的一個軟件特征域，記作式中：fi表示期望軟件S的某個軟件特征，N表示非負數集合。

定義4 軟件特征集合與軟件需求。期望軟件S的所有軟件特征組成的集合稱作期望軟件S的軟件特征集合，記作ΓS。

根據軟件工程中軟件需求的概念，期望軟件S的軟件特征集合ΓS是軟件需求的一種理論抽象。

期望軟件S的軟件特征之間存在著相互關系，軟件特征之間既可能全部都有關聯，也可能只是部分特征之間有關聯。

期望軟件S的軟件特征之間全部都有關聯是一種極限狀態。在現實中，由于軟件規模普遍都比較龐大，期望軟件S的軟件特征之間基本只是部分特征之間有關聯，而在某些軟件模塊內部的全部軟件特征之間可能存在關聯。

期望軟件S中，顯然軟件特征之間是有層次關系的。在抽象為集合概念的層面上，可以對這種層次關系進行展平，使所有軟件特征以某一種順序在集合ΓS中排列。

定義5 軟件特征全相關與軟件特征部分相關。對于期望軟件S的軟件特征集合ΓS或其子集，如果ΓS或其子集中的每一個子集都與期望軟件S的一個用例或程序邏輯路徑存在一一對應關系，則稱ΓS或其子集中的軟件特征是軟件特征全相關的。

例如，期望軟件S的軟件特征集合ΓS中有n個軟件特征，即｛f1，f2，f3，…，fn｝。則ΓS的所有子集為｛｝，｛f1｝，｛f2｝，…，｛f1，f2｝，｛f2，f3｝，｛f3，f4｝，…，｛f1，f2，f3，…，fn－1｝，｛f2，f3，…，fn－1，fn｝，…，｛f1，f2，f3，…，fn｝，軟件特征集合ΓS中的軟件特征全相關則指其每一個子集都對應惟一的一個用例。

對于期望軟件S的軟件特征集合ΓS或其子集，如果ΓS或其子集中的軟件特征不是軟件特征全相關的，只有其中的部分軟件特征是軟件特征全相關的，則稱ΓS或其子集中的軟件特征是軟件特征部分相關的。

定義6 軟件特征集合冪集合。軟件特征集合ΓS的所有子集作為元素組成的冪集，稱作軟件特征集合冪集合，記作2ΓS。

定理1 當期望軟件S的軟件特征全相關時，期望軟件S的期望行為全集是軟件特征集合ΓS的冪集合2ΓS。

證明：對本定理的證明將使用反證法。

當期望軟件S的軟件特征是軟件特征全相關時，依據軟件特征全相關定義，則有ΓS的冪集2ΓS的每一個元素都與一個用例存在一一對應關系，冪集2ΓS是期望軟件S的行為集合。

假設期望軟件S的行為集合2ΓS不是其期望行為全集，那么必定存在期望軟件S的某一個用例TC1，TC1與期望軟件S中某些軟件特征元素的一個并集∪fi對應，fi∈ΓS，但∪fi卻不是軟件特征集合冪集合2ΓS中一個元素。

由于∪fi是ΓS是期望軟件S中某些軟件特征元素的一個并集并必定是ΓS的某一個子集，由此推出，軟件特征集合冪集合2ΓS中并沒有包含軟件特征集合ΓS的所有子集，這與冪集定義相矛盾，因此本證明中假設是錯誤的。

根據反證法，當期望軟件S的軟件特征全相關時，期望軟件S的期望行為全集是軟件特征集合冪集合2ΓS成立。

推論1 當期望軟件S的軟件特征部分相關時，期望軟件S的期望行為全集是軟件特征集合ΓS冪集合2ΓS的一個不完全子集。

證明：略。

在工程實踐中，用于描述軟件系統輸入與輸出之間關系的因果圖／判定表方法已經間接指明了在極限條件下，軟件系統的輸入行為全集是其輸入條件的冪集。

依據軟件工程中的概念，用例是軟件工程或系統工程中對系統如何反應外界請求的描述，是一種通過用戶的使用場景來獲取需求的技術。每個用例提供了一個或多個場景，該場景說明了系統是如何同最終用戶或其他系統交互的，也就是誰可以用系統做什么，從而獲得一個明確的業務目標。

基于本文定義2、3和4中的軟件特征、軟件特征域和軟件特征集合的概念，基于軟件工程中用例的概念內涵，可以說，一個用例描述了軟件特征或特征域的某種組合對外界請求的響應，即軟件響應請求的能力通過針對軟件特征或特征域的某種陳述（命題）表現出來。

抽象來看，一個用例就是一種陳述，也就是一個命題，是針對期望軟件S的軟件特征或軟件特征組合的一個命題。因此得到以下軟件用例的定義。

定義7 軟件用例。設期望軟件S是軟件特征全相關的，軟件用例是對期望軟件S的軟件特征集合ΓS冪集合2ΓS某個子集ui的一個命題，記作Cui，ui∈2ΓS，ΓS是期望軟件S的軟件特征集合。

定義8 軟件用例集合與軟件需求規格說明。期望軟件S的所有軟件用例Cui組成的集合，稱為軟件用例集合，記為C，即

軟件用例集合C形式化定義了期望軟件S的行為空間，任何對用戶請求的系統響應都是軟件用例集合C的一個元素。依據軟件需求規格說明的定義，軟件用例集合C是軟件需求規格說明的一種實例化展開，羅列了所有滿足（也包括不滿足／違反）需求規格說明的（命題）實例。

依據軟件測試理論，軟件測試需求來源于軟件需求（包括顯性的，即明確定義的，和隱含的，即雖沒有明確定義，但卻是“應當”或必需滿足的），是測試者依據測試委托方要求，對軟件需求的重新闡述，也就是說是一種形式變換，在理論上兩者是一一對應的。

定義9 軟件測試需求。經過一個映射TR，軟件需求ΓS轉換為軟件測試需求，記為TR（ΓS）。

在理論上ΓS與TR（ΓS）中的元素是一一對應的，也就是說測試中需要覆蓋期望軟件S的所有軟件需求（軟件特征）。但是在某些工程實踐場景中，TR（ΓS）中的元素與ΓS中的元素并不需要是滿射關系。例如，只需覆蓋部分軟件需求的回歸測試。

在測試設計與實現活動中，測試者依據軟件測試需求，參考軟件需求規格說明中的軟件用例，設計一系列測試用例并試圖覆蓋軟件測試需求。

測試用例是為某個測試目標而編制的一組測試輸入、執行條件以及預期結果，以便測試被測軟件的某個程序路徑或核實是否滿足某個特定測試需求。測試用例概念的實質，是通過一個測試輸入序列來對一組軟件特征進行覆蓋來確定其是否滿足需求／設計的要求。

由于軟件用例集合C形式化預定義了期望軟件S的期望行為空間，則在測試設計與實現活動中，測試者依據需要驗證的測試需求TR（ΓS），選取2TRΓS()的某個子集ui′，從軟件用例集合C中選取相應的軟件用例Cui，通過一個轉換TD，形成測試用例。

基于以上的分析，得出軟件測試用例和軟件測試用例集合的定義如下。

定義10 軟件測試用例。依據軟件測試需求TR（ΓS）的冪集2TRΓS()的某個子集ui′所設計的軟件測試用例是對應軟件用例Cui的一個TD變換。記作Cui′，

定義11 軟件測試用例集合。針對軟件測試需求TRΓS()的冪集2TRΓS()所有子集所設計的軟件測試用例Cui′所組成的集合，稱為軟件測試用例集合，記為C′，

性質1 當｜ΓS｜＝｜TR(ΓS)｜，軟件用例集合C中的元素和軟件測試用例集合C′中的元素是一一對應的。

證明 顯然，根據軟件測試用例集合C′的定義，C′中每一個元素Cui′都是依據2TR(ΓS)中惟一的子集ui′在2ΓS中尋找相應子集ui所對應惟一元素Cui變換而來，而｜ΓS｜＝｜TR(ΓS)｜，ui和ui′將配對出現，因此軟件用例集合C中的元素和軟件測試用例集合C′中的元素是一一對應的成立。

本節的研究中對軟件特征與軟件用例，軟件用例與軟件測試用例、軟件測試用例與軟件缺陷之間的關系進行了形式化表述。

在軟件特征集合為ΓS的情況下，軟件用例集合的最大可能規模為2ΓS，而軟件測試用例集合與軟件用例集合中元素存在一一對應關系，軟件測試用例集合的最大可能規模也是2ΓS，而由于測試過程中，軟件缺陷與測試用例之間存在的單映射對應關系（即若存在一個軟件缺陷，必有惟一的一個測試用例對應；而一個測試用例可能對應一個軟件缺陷，也可能沒有對應的軟件缺陷存在），軟件缺陷的最大可能規模小于

4 軟件測試可窮盡性研究

基于以上的研究成果，在討論本文提出的基本科學問題前，需要對軟件測試演化過程和軟件特征集合有窮性進行討論。

軟件測試演化過程可分為測試過程中測試版本無演化、測試版本有限次演化和測試版本持續演化3種情況。

初始軟件特征集合的有窮性，可分為有窮集合和無窮集合2種情況。由于期望軟件S的初始特征集合是通過一個有限次迭代過程所獲得的，不存在一個無窮迭代過程，因此不存在初始特征集合是無窮集合情況，即只需考慮初始軟件特征集合為有窮集合。

根據以上討論結果，以下分3種情況來研究本文提出的基本科學問題：

1）軟件測試的理想情況。

在軟件測試的理想情況下，軟件測試版本無演化，期望軟件S的初始特征集合為有窮集合。

基于本文的定義11，由于測試版本無演化，則意味著測試過程中既沒有新提出的用戶需求，也沒有發現需要修復的軟件缺陷，測試用例Cu′i執行過程中全部通過。期望軟件S的初始特征集合ΓS為有窮集合，其勢｜ΓS｜＝n，n∈N，N為非負整數集，測試用例集合C′的勢｜C′｜＝2n，即測試用例集合C′仍然是一個有窮集合。

顯然在此情況下，由于軟件測試用例集合理論上是一個有窮集合，軟件缺陷數量是有限的，理論上測試投入充足可以窮盡此測試用例集合，相應的軟件缺陷發現過程也可以終止。

2）軟件測試的現實情況：軟件測試版本有限次演化，期望軟件S的初始特征集合為有窮集合。

由于測試版本有限次演化，則意味著測試過程既可能由于用戶需求增加而增加了新的軟件特征，也可能發現了需要修復的軟件缺陷，并因此進行了測試版本的更新，在第k個測試版本中，測試用例集合中的測試用例執行全部通過，且無任何新增用戶需求，因此不再有新的測試版本產生，軟件測試版本演化過程終止。

期望軟件S的初始特征集合ΓS為有窮集合，其勢｜ΓS｜＝n，n∈N，N為非負整數集，初始測試用例集合C′的勢｜C′｜＝2n。即初始測試用例集合C′是一個有窮集合。

在測試版本有限次的演化過程中，軟件特征集合從初始特征集合ΓS開始演化，每次的測試版本演化帶來新增的軟件特征集合△i（ΓS），i∈N，N為非負整數集。依據定理1，相應的新增軟件特征集合勢的增量為，｜△i（ΓS）｜＝mi，i＝1，2，3，…，k。進行有限次變化后的軟件特征全域為ΓS∪△1（ΓS）∪△2（ΓS）∪△3（ΓS）…∪△k（ΓS）。假設每次測試版本演化后都進行代表最大工作量的全面測試，則進行一次測試版本演化后的測試用例集合的勢為2n＋m1，而測試演化過程中總的測試用例集合的勢為2n＋2n＋m1。則進行有限k次測試版本演化后，測試演化過程中總的測試用例集合C′?的勢的最大值為

顯然，當初始特征集合為有窮集合，軟件系統測試版本經過有限k次演化后，測試用例集合C′?仍然是一個有窮集合，軟件缺陷數量仍是有限的，軟件測試用例集合在此情況下，理論上測試投入充足是可窮盡的，即投入有窮的成本可窮盡，那么相應的軟件缺陷發現過程也可以終止。

3）軟件測試的極限情況：軟件測試版本持續演化，期望軟件S的初始特征集合為有窮集合。

測試版本持續演化，則意味著測試版本的持續更新和新的軟件特征的持續增加，軟件測試過程進入了一個無窮過程。

當期望軟件S的初始特征集合ΓS為有窮集合時，其勢｜ΓS｜＝n，n∈N，N為非負整數集，初始測試用例集合C′的勢｜C′｜＝2n。即初始測試用例集合C′是一個有窮集合。

在測試版本持續演化過程中，軟件特征集合從初始特征集合ΓS開始演化，每次的測試版本演化帶來新增的軟件特征集合△i（ΓS），i∈N，N為非負整數集。依據定理1，相應的新增軟件特征集合勢的增量為，｜△i（ΓS）｜＝mi，i＝1，2，3，…，∞。進行持續演化后的軟件特征全域為ΓS∪△1（ΓS）∪△2（ΓS）∪△3（ΓS）…∪△∞（ΓS）。假設每次測試版本演化后都進行代表最大工作量的全面測試，則持續測試版本演化后，測試演化過程中總的測試用例集合C′?的勢的最大值為

｜C′?｜＝2n＋2n＋m1＋2n＋m1＋m2＋…＋2n＋m1＋m2…＋m∞由于n＋m1＋m2…＋m∞＝∞，依據統一無窮理論中的ICI原理，有2∞＝∞成立，則有

這說明，當初始特征集合為有窮集合，測試版本持續演化后，測試用例集合將演化成為一個無窮集合，其勢是實無窮大∞，相應的軟件缺陷數量也是實無窮大∞。

由于人的認識和計算機的操作都只能是有限步的，不能直接去處理無窮的可能性。因此面對測試用例集合是一個無窮集合這樣一個問題時，在軟件測試過程中，可通過觀察軟件測試質量評價函數的性質來判定軟件測試的可窮盡性。

設軟件測試版本持續演化過程中，軟件測試版本的質量評價函數為P（TSk′），k＝1，2，…，∞。

①當P（TSk′）屬于第2類（排序類）性質時，可通過有限步操作在理論上窮盡所有的可能性。可利用有限的開銷自動獲得直達∞效果，從而判斷持續演化中的軟件測試過程是絕對可信的。

②當P（TSk′）屬于第1類（內蘊類）性質時，

a）如果P（TSk′）具有收斂性，則可在有限步操作內，在小于允許失誤概率的意義下獲得直達∞效果，可利用有限開銷來判定處于持續演化中的軟件測試過程是可信的；

b）如果P（TSk′）發散或者震蕩，則不可能窮盡C′?中的所有測試用例，可利用有限開銷來判定持續演化中的軟件測試過程是不可信的。

依據以上的討論結果，總結如下：

1）軟件測試的理想情況：測試版本無演化，測試用例集合C′?是一個有窮集合，測試用例可被窮盡，軟件缺陷數量是有限的，軟件測試可窮盡。

2）軟件測試的現實情況：測試版本有限次演化，測試用例集合C′?是一個有窮集合，測試用例可被窮盡，軟件缺陷數量是有限的，軟件測試可窮盡。

3）軟件測試的極限情況：測試版本持續演化，測試用例集合C′?是一個無窮集合，軟件缺陷數量為無窮大∞，需要借助軟件測試質量評價P（TSk′）來輔助判定軟件測試可信性。

5 對以往測試可窮盡性認識的分析

從本文的研究結果來看，軟件測試從理論上可以窮盡其軟件缺陷發現過程。但是在實際的軟件測試中，總是會有這樣的感覺，只要繼續進行測試，軟件缺陷似乎總是不斷出現。換句話說，在傳統測試觀念中，軟件測試中總是能找到新增的測試用例，測試用例是層出不窮的，軟件缺陷也是層出不窮的。

1）理論層面的定性分析。

依據本文研究成果，軟件測試中測試用例集合的大小與預先定義的軟件特征數量直接相關，預先定義的軟件特征數量越多越細致，軟件測試中可生成的測試用例則越多，據此可發現的軟件缺陷也就越多。軟件特征數量的增加使得測試用例集合中測試用例數量的增加呈幾何級數方式增長，軟件缺陷的增長規模也類似。因此若在測試中不斷細化軟件特征的定義（這種情況常見于軟件需求說明不完整的軟件測試中，測試人員對被測軟件系統的理解是不斷深入的），顯然將獲取快速增長的測試用例集合，顯然也將依據新的軟件特征定義而不斷發現新的軟件缺陷。

另一個方面，從測試過程來看，一般遵循從單元測試、集成測試到系統測試的幾個階段。由簡入繁，自上而下的層次化測試方式占主導模式。單元測試由于代碼或單元規模小，若投入測試成本充分，白盒測試中尚有可能覆蓋一個軟件單元的行為全集，而在集成測試階段，測試重點轉向軟件單元間的接口集成，對多個軟件單元的軟件特征集合并集之冪集的覆蓋遠遠不夠充分，造成大量軟件缺陷的遺留。而在系統測試階段，測試時依據軟件需求規格說明，但是由于測試的分工，測試也將首先從各個模塊入手，其次是模塊間組合，最終到系統的整體；或者從軟件系統整體核心模塊／流程入手，逐步向模塊細節深入，這兩種系統測試方式都會在某個層面上忽視了對不同模塊間特征的組合關系的完整覆蓋。這種對完整覆蓋的忽視，注定了軟件測試中實際覆蓋的測試用例集合只是初始測試用例集合C′的一個非常小的子集。

2）從定量角度對軟件缺陷可能規模和軟件測試投入的分析。

在工程實踐中，以一般的信息管理軟件系統規模來看，含有100個軟件特征的期望軟件S是一個小規模軟件，顯然這100個軟件特征不可能是全相關的而只能是部分相關的。

假設一個期望軟件S含有100個軟件特征，這100個軟件特征分布在5個軟件模塊中，每個軟件模塊含有20個軟件特征，1／5模塊內的軟件特征是全相關的，其余模塊中軟件特征是部分相關的，例如只有10個軟件特征是全相關的，這樣的模塊共有8個。則S的初始測試用例集合的勢｜C′｜≈220＋8× 210≈1.1E＋6。

依據測試實踐經驗，針對含有100個軟件特征的小型軟件系統，使用手工測試方式，投入測試成本至多約為4個人月，其中有2個人月測試執行（22天／人月，每天有效工作8 h，每小時輸入不同的測試用例約10個），其他成本為測試需求分析、測試設計和測試總結等環節。測試過程中測試人員實際運行的不同的測試用例約為2×22×8×10＝3 520個測試用例，發現的軟件缺陷約200－300個。實際投入測試的測試用例集合的勢僅為其初始測試用例集合勢｜的約1／300，差距懸殊。因此手工測試中所投入的測試用例規模遠不及與被測軟件依據軟件特征定義所期望的測試用例全集規模。而若使用更高效率的自動化測試工具來形式化生成測試用例全集，并自動化執行，則有可能達成對軟件測試用例集合的測試覆蓋。

同時，還可以從軟件缺陷規模的角度來分析。軟件工程領域有一個經驗說法，即“80%的軟件缺陷集中在20%的區域中”，這符合“80／20”原則。這個說法也可以換一下闡述角度，即運行期望軟件20%的軟件特征的冪集所對應的測試用例集合可以發現被測軟件80%的軟件缺陷。

仍以含有100個特征項的小規模軟件系統為例，發現軟件系統總缺陷規模的80%所需的測試用例數量為220＝1 048 576，為百萬量級，而憑經驗，隨被測軟件質量的高低，軟件缺陷規模與測試用例規模的比率在1／10～1／100間，即1萬到10萬量級。而依據以上的討論，正常投入情況下，測試中只能發現約200～300個軟件缺陷，約為實際規模的1／30～1／300，差距也是非常巨大的。這就可以解釋為什么在軟件測試實踐過程，一個較有規模的被測軟件，只要持續測試，總能發現新軟件缺陷的現象了。并不是軟件缺陷數量無限多，而是軟件缺陷數量巨大，即使是一個規模不大的軟件系統，在正常傳統手工測試情況下，即使加倍投入下，也幾乎沒有可能將軟件缺陷全部發現出來。

綜合本節的討論，在軟件測試實際過程中，由于傳統手工測試方法的局限性，由于軟件特征集合規模龐大、軟件缺陷規模龐大等因素的影響，在手工測試方法和正常投入的測試成本約束下，軟件測試已可能達到軟件缺陷的全發現和處理。因此若想達成或趨近于被測軟件中軟件缺陷的全發現，使用高效率的基于軟件特征的測試用例自動生成技術和自動化測試技術將更有可能和實際意義。

同時，由于軟件規模日益龐大，其所對應的測試用例集合規模已經是天文數字，即使采用自動化測試用例生成與自動執行，仍需考慮測試用例集合的覆蓋策略問題，以節省測試成本。因此需要進一步研究如何在軟件測試過程中優選測試用例，以期在有限測試成本中盡快提高軟件測試覆蓋，確保重要軟件缺陷的優先發現。

6 論

“通過軟件測試，一個軟件系統中的軟件缺陷發現過程是否可以被窮盡？”是軟件工程業界面臨的一個不可回避的有關軟件測試可信性的基本科學問題。本文圍繞此科學問題開展研究，獲取了以下4個方面的研究成果：

1）從數的無窮大概念入手，將本文的討論范圍從有窮領域擴展到無窮領域，基于最新的實無窮理論研究成果，獲取了利用有限開銷來判斷無窮軟件測試過程可信性的基本方法；

2）從軟件特征定義入手，對軟件測試用例集合等相關概念進行了形式化定義，得出了軟件特征全相關條件下，期望軟件的軟件特征、軟件測試用例和軟件缺陷三者之間的對應關系，該成果為被測軟件需投入的測試用例規模和軟件缺陷規模的估算提供了理論模型；

3）基于統一實無窮理論研究成果、統一數學歸納法和測試用例集合形式化定義，證明了在軟件測試版本無演化和有限次演化情況下，軟件測試用例集合是一個有窮集合，軟件缺陷數量是有限的，軟件測試過程是可窮盡的；在軟件測試極限情況下，軟件測試版本持續演化，軟件測試用例集合成為一個無窮集合，測試用例數量和軟件缺陷數量均為實無窮大∞，軟件測試該如何開展的理論問題。

4）基于本文的上述成果，對軟件測試中軟件缺陷是無法窮盡的舊有認識進行了剖析，分析了產生此種認識的根源，闡明了在軟件測試過程中注重測試用例選擇策略以盡快提高軟件測試質量的重要性。

本文的一系列研究成果初步回答了困擾軟件測試理論界多年的軟件測試可窮盡性基本問題，證明了在軟件測試的理想和現實情況下軟件測試是可被窮盡的；而在軟件測試的極限情況下，在被測軟件版本持續演化進入一個無窮過程時，可通過新數學歸納法并借助軟件測試質量評價函數來軟件測試可信性。

科學理論應該走在具體實踐的前面！我們相信本文的研究成果將在未來的軟件工程實踐中有應用價值——隨著互聯網技術不斷發展、網構軟件的出現與網構軟件系統開放性的增強，軟件系統規模將空前增大，遠期可能出現超大規模軟件系統頻繁演化甚至持續高速演化現象，已有出現軟件測試極限情況的可能性，因此本文的研究成果可為近期軟件測試可信性和遠期軟件測試可信性研究提供一定的理論支持。

［1］MYERSG J.The art of software testing［M］.Wiley Inter?science，1979：42?46.

［2］IEEE STD 610.12.1990.IEEEStandard Glossary of Software Engineering Terminology［S］.IEEE，1990.

［3］ISO／IEC 15408?1：2009.Information technology—Security techniques—Evaluation criteria for IT security—Part 1：In－troduction and general model［S］.International Organi?zation of Standardization，2009.

［4］謝曉園，許蕾，徐寶文，等.演化測試技術的研究［J］.計算機科學與探索，2008，2（5）：449?466.XIE Xiaoyuan，XU Lei，XU Baowen，et al.Survey of evolu?tionary testing［J］.Journal of Frontiers of Computer Science and Technology，2008，2（5）：449?466.

［5］丁博，王懷民，史殿習，等.一種支持軟件可信演化的構件模型［J］.軟件學報，2011，22（1）：17?27.DING Bo，WANG Huaimin，SHIDianxi，et al.Component model supporting trustworthiness?oriented software evolution［J］.Journal of Software，2011，22（1）：17?27.

［6］WANG H M，TANG Y B，YIN G，et al.Trustworthiness of Inter?net?based software［J］.Science in China：Series E，2006，36（10）：1156?1169.

［7］鄭志明，馬世龍，李未，等.軟件可信性動力學特征及其演化復雜性［J］.中國科學：F輯，信息科學，2009，39（9）：946?950.

［8］張順燕.數學的源與流［M］.北京：高等教育出版社，2000：12?46.

［9］何華燦，何智濤.無窮概念的重新統一［J］.智能系統學報，2010，5（3）：202?220.HE Huacan，HE Zhitao.Reunifying concepts of infinity［J］.CAAI Transactions on Intelligent Systems，2010，5（3）：202?220.

［10］彭漪漣，馬欽榮.邏輯學大辭典［M］.上海：上海辭書出版社，2004：431，481.

［11］DAUBEN JW.康托的無窮的數學和哲學［M］.鄭毓信，劉曉力，譯.大連：大連理工大學出版社，2008：108?109.

［12］何華燦，何智濤.統一無窮理論［M］.北京：科學出版社，2011：11.

［13］HE Zhitao，LIU Chao，YAN Haihua，etal.A formal defi?nition of software testing based on fuzzy measure［C］／／2013 Fourth World Congress on Software Engineering，2013，12：59?63.

何智濤，1972年生，講師，博士，CAAI人工智能基礎專業委員會委員，主要研究方向為軟件測試建模、軟件測試過程管理、知識工程和泛邏輯。國內外發表學術論文10余篇。

何華燦，1938年生，教授，博士生導師。中國人工智能學會發起人，曾任常務理事和副理事長，現任CAAI人工智能基礎專業委員會主任。主要研究方向為人工智能應用、人工智能基礎和泛邏輯學、實無窮理論。發表學術論文160余篇，出版《人工智能導論》、《泛邏輯學原理》和《統一無窮理論》等專著，主編出版《信息、智能與邏輯》叢書。

劉超，1958年生，教授，博士生導師，北京航空航天大學軟件工程研究所所長，CCF會員。主要研究方向為軟件測試和軟件工程。國內外發表論文近百篇。

Research on exhaustive character of software testing based on the unified infinity theory

HE Zhitao1，HE Huacan2，LIU Chao1
（1.School of Computer Science and Engineering，Beihang University，Beijing 100191，China；2.School of Computer，Northwestern Polytechnical University，Xi’an 710072，China）

A traditional concept of software testing is that the defect of new software can always be detected if further software testing is conducted.This idea eliminates the theoretical basis of the dependability of software testing，which is a hot topic in the software engineering field.The exhaustive character of software testing is studied in theory in this paper.The discussion range extends from finite field to infinite field.Firstly，starting from the latest research results of actual infinity theory named unified infinity theory，a basic method to determine the dependability of an infinite software testing processwith limited costwas obtained.Next，with the definition ofsoftware features，the software test cases setwasdefined and the corresponding relationshipsamong software features，software testcases and software de?fectswere obtained.Based on the unified infinity theory and unified mathematics inductivemethod，the relationship between the exhaustive character of software test cases set and software testing quality in continuous software testing e?volution process was discussed.The theoretical question，＂if a software test cases set is an infinite set，how to con?duct the software testing and whether the software testing can be exhausted＂was answered and the old thoughts on the exhaustive character of software testing were analyzed.A series of achievements in this paper preliminarily answered the question that has been nagging the theory field of software testing formany years related to the exhaustive charac?ter of software testing，establishing a basis for the dependability of software testing.

dependability of software testing；software defects；software testing evolution process；unified mathe?matical in?duction時代以來，軟件系統就作為計算機系統的重要支撐子系統登上了歷史舞臺，人類自此開始逐步進入信息科學時代。

TP311；O144.1

A

1673?4785（2014）06?0641?012

何智濤，何華燦，劉超.基于統一無窮理論的軟件測試可窮盡性研究［J］.智能系統學報，2014，9（6）：641?652.

英文引用格式：HE Zhitao，HE Huacan，LIU Chao.Research on exhaustive character of software testing based on the unified infini?

ty theory［J］.CAAI Transactions on Intelligent System s，2014，9（6）：641?652.

10.3969／j.issn.1673?4785.201308040

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1673?4785.201308040.htm l

2013?08?28.

日期：2014?09?30. 自1946年第1臺計算機誕生，人類邁進計算機

何智濤.E?mail：zhitaohe＠vip.sina.com.