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

基于統(tǒng)一無窮理論的軟件測試可窮盡性研究

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

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

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

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

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

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

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

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

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

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

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

眾所周知，軟件系統(tǒng)的行為可以被抽象為一個用例集合，而用例集合可以通過一個映射變換成為測試用例集合。因此，軟件測試可被抽象為這樣一個過程，即針對軟件系統(tǒng)的構(gòu)成和行為設計和執(zhí)行測試用例，并據(jù)此發(fā)現(xiàn)和處理軟件缺陷的過程。同時軟件缺陷與測試用例間存在嚴格對應關系。

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

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

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

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

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

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

1 3種主要無窮觀

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

1.1 現(xiàn)有的3種主要無窮觀

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

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

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

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

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

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

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

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

1.2 層次無窮理論

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

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

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

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

超窮數(shù)理論的要點是：

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

②第2生成（窮竭）原則：規(guī)定自然數(shù)集合｛0，1，2，3，…，n，n＋1，…｝的基數(shù)0是最小的超窮序數(shù)ω0。以ω0為生成基繼續(xù)延伸，ω0＋1，ω0＋2，ω0＋3，…可生成越來越大的超窮序數(shù)，其中沒有最大元出現(xiàn)，它們?nèi)繉儆冢郐?數(shù)類］。［ω0數(shù)類］中的每一個超窮序數(shù)的基數(shù)都是0。

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

2 統(tǒng)一無窮理論研究現(xiàn)狀

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

2.1 統(tǒng)一無窮理論要點

1）計數(shù)器的編碼規(guī)律。根據(jù)數(shù)的理想計數(shù)器模型可歸納出計數(shù)器的編碼規(guī)律如下：

①有窮非負整（?。?shù)只需要用有窮位的編碼表示，有窮位的編碼只能表示有窮非負整（小）數(shù)，不可能越界表示趨近無窮正整（?。?shù)。

②趨近無窮正整（小）數(shù)需要用趨近無窮位的編碼表示，趨近無窮位的編碼可表示非負正整（?。?shù)和趨近無窮正整（小）數(shù)，不可能越界表示實無窮大（小）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 統(tǒng)一無窮理論與軟件測試可窮盡性研究

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

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

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

當P（x）屬于第1類（內(nèi)蘊類）性質(zhì)時：

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

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

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

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

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

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

因此，軟件測試可被抽象為這樣一個過程，即依據(jù)軟件設計說明或軟件需求規(guī)格說明，針對軟件系統(tǒng)的邏輯構(gòu)成或系統(tǒng)行為設計測試用例集合，在被測軟件上執(zhí)行測試用例集合，并據(jù)此發(fā)現(xiàn)和處理軟件缺陷的過程，同時軟件缺陷與測試用例間存在著對應關系。

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

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

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

被測軟件，記為S′，即編碼實現(xiàn)后的軟件。

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

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

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

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

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

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

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

期望軟件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的軟件特征是軟件特征全相關時，依據(jù)軟件特征全相關定義，則有Γ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的所有子集，這與冪集定義相矛盾，因此本證明中假設是錯誤的。

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

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

證明：略。

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

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

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

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

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

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

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

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

定義9 軟件測試需求。經(jīng)過一個映射TR，軟件需求ΓS轉(zhuǎn)換為軟件測試需求，記為TR（ΓS）。

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

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

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

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

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

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

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

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

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

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

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

4 軟件測試可窮盡性研究

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

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

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

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

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

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

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

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

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

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

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

在測試版本有限次的演化過程中，軟件特征集合從初始特征集合ΓS開始演化，每次的測試版本演化帶來新增的軟件特征集合△i（ΓS），i∈N，N為非負整數(shù)集。依據(jù)定理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′?的勢的最大值為

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

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

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

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

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

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

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

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

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

①當P（TSk′）屬于第2類（排序類）性質(zhì)時，可通過有限步操作在理論上窮盡所有的可能性?？衫糜邢薜拈_銷自動獲得直達∞效果，從而判斷持續(xù)演化中的軟件測試過程是絕對可信的。

②當P（TSk′）屬于第1類（內(nèi)蘊類）性質(zhì)時，

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

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

依據(jù)以上的討論結(jié)果，總結(jié)如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 論

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

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

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

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

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

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

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

［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］丁博，王懷民，史殿習，等.一種支持軟件可信演化的構(gòu)件模型［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］張順燕.數(shù)學的源與流［M］.北京：高等教育出版社，2000：12?46.

［9］何華燦，何智濤.無窮概念的重新統(tǒng)一［J］.智能系統(tǒng)學報，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.康托的無窮的數(shù)學和哲學［M］.鄭毓信，劉曉力，譯.大連：大連理工大學出版社，2008：108?109.

［12］何華燦，何智濤.統(tǒng)一無窮理論［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人工智能基礎專業(yè)委員會委員，主要研究方向為軟件測試建模、軟件測試過程管理、知識工程和泛邏輯。國內(nèi)外發(fā)表學術論文10余篇。

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

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

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時代以來，軟件系統(tǒng)就作為計算機系統(tǒng)的重要支撐子系統(tǒng)登上了歷史舞臺，人類自此開始逐步進入信息科學時代。

TP311；O144.1

A

1673?4785（2014）06?0641?012

何智濤，何華燦，劉超.基于統(tǒng)一無窮理論的軟件測試可窮盡性研究［J］.智能系統(tǒng)學報，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.