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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 3種主要無窮觀

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

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

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

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

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

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

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

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

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

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

1.2 層次無窮理論

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

1）有窮集合和無窮集合：如果在集合A的元素和集合B的元素之間能夠建立一一對(duì)應(yīng)的關(guān)系，則稱集合A和集合B等勢(shì)，記作｜A｜＝｜B｜。如果一個(gè)集合能夠和它自己的真子集等勢(shì)，則這個(gè)集合稱為無窮集合，否則稱為有窮集合.

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

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

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

①第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ù)類］中的每一個(gè)超窮序數(shù)的基數(shù)都是0。

③第3生成（限制）原則：規(guī)定［ωi數(shù)類］中所有超窮序數(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ù)的理想計(jì)數(shù)器模型，證明了在位數(shù)保持一致的情況下（包括有窮位、趨近無窮位和實(shí)無窮位），非負(fù)整數(shù)的編碼和非負(fù)小數(shù)的編碼永遠(yuǎn)保持一樣多，差別僅僅是小數(shù)點(diǎn)的位置不同而已。所以，如果按照傳統(tǒng)思想認(rèn)為所有的非負(fù)整數(shù)總共有∞個(gè)，所有的非負(fù)小數(shù)總共有2∞個(gè)，那么一定有2∞＝∞的關(guān)系成立，實(shí)無窮大∞惟一存在，并且它不可能再繼續(xù)增大了。這就是說，在統(tǒng)一實(shí)無窮數(shù)域模型假設(shè)中，所謂的“不可數(shù)集合”根本不存在，困擾數(shù)學(xué)界多年的連續(xù)統(tǒng)假設(shè)可以排除，由于不可數(shù)集合的排除，統(tǒng)一無窮理論也可以作為軟件測(cè)試可信性理論的重要理論基礎(chǔ)使用。［9，12］

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

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

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

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

③實(shí)無窮大∞只能用∞位的特殊編碼（1；0..0；0...0）（進(jìn)位溢出信號(hào)）表示，∞位的編碼可以表示有窮非負(fù)整（?。?shù)、趨近無窮正整（小）數(shù)和實(shí)無窮大∞（實(shí)無窮小δ＝1／∞）。對(duì)應(yīng)的編碼是∞＝（1；0...0；0...0），δ＝（0.0..0；0..0；1）。

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

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

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

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

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

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

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

①一個(gè)數(shù)既可看成是幾何點(diǎn)，也可看成是進(jìn)位制編碼，兩者一一對(duì)應(yīng)。

②∞個(gè)幾何點(diǎn)可在一條直線上從頭到尾地排列，每一個(gè)點(diǎn)可以擁有一個(gè)惟一的進(jìn)位制編碼。

③由于實(shí)無窮大∞可達(dá)，所以完整的∞位進(jìn)位制編碼可按照計(jì)算器的生成順序從小到大地排列，與直線上的點(diǎn)形成一一對(duì)應(yīng)關(guān)系。

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

5）非負(fù)整數(shù)的內(nèi)蘊(yùn)性質(zhì)和排序性質(zhì)。有一個(gè)定義在非負(fù)整數(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)蘊(yùn)類）性質(zhì)。

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

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

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

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

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

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

當(dāng)P（x）屬于第1類（內(nèi)蘊(yùn)類）性質(zhì)時(shí)：

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

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

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

3 測(cè)試用例集合形式化定義

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

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

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

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

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

定義1 期望軟件和被測(cè)軟件。期望軟件，記為S，即軟件需求和軟件設(shè)計(jì)所描述的軟件。

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

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

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

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

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

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

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

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

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

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

例如，期望軟件S的軟件特征集合ΓS中有n個(gè)軟件特征，即｛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中的軟件特征全相關(guān)則指其每一個(gè)子集都對(duì)應(yīng)惟一的一個(gè)用例。

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

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

定理1 當(dāng)期望軟件S的軟件特征全相關(guān)時(shí)，期望軟件S的期望行為全集是軟件特征集合ΓS的冪集合2ΓS。

證明：對(duì)本定理的證明將使用反證法。

當(dāng)期望軟件S的軟件特征是軟件特征全相關(guān)時(shí)，依據(jù)軟件特征全相關(guān)定義，則有ΓS的冪集2ΓS的每一個(gè)元素都與一個(gè)用例存在一一對(duì)應(yīng)關(guān)系，冪集2ΓS是期望軟件S的行為集合。

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

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

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

推論1 當(dāng)期望軟件S的軟件特征部分相關(guān)時(shí)，期望軟件S的期望行為全集是軟件特征集合ΓS冪集合2ΓS的一個(gè)不完全子集。

證明：略。

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

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

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

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

定義7 軟件用例。設(shè)期望軟件S是軟件特征全相關(guān)的，軟件用例是對(duì)期望軟件S的軟件特征集合ΓS冪集合2ΓS某個(gè)子集ui的一個(gè)命題，記作Cui，ui∈2ΓS，ΓS是期望軟件S的軟件特征集合。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 軟件測(cè)試可窮盡性研究

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

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

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

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

1）軟件測(cè)試的理想情況。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

②當(dāng)P（TSk′）屬于第1類（內(nèi)蘊(yùn)類）性質(zhì)時(shí)，

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

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

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

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

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

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

5 對(duì)以往測(cè)試可窮盡性認(rèn)識(shí)的分析

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

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

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

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

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

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

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

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

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

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

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

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

6 論

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

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

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

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

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

本文的一系列研究成果初步回答了困擾軟件測(cè)試?yán)碚摻缍嗄甑能浖y(cè)試可窮盡性基本問題，證明了在軟件測(cè)試的理想和現(xiàn)實(shí)情況下軟件測(cè)試是可被窮盡的；而在軟件測(cè)試的極限情況下，在被測(cè)軟件版本持續(xù)演化進(jìn)入一個(gè)無窮過程時(shí)，可通過新數(shù)學(xué)歸納法并借助軟件測(cè)試質(zhì)量評(píng)價(jià)函數(shù)來軟件測(cè)試可信性。

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

［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］謝曉園，許蕾，徐寶文，等.演化測(cè)試技術(shù)的研究［J］.計(jì)算機(jī)科學(xué)與探索，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］丁博，王懷民，史殿習(xí)，等.一種支持軟件可信演化的構(gòu)件模型［J］.軟件學(xué)報(bào)，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］鄭志明，馬世龍，李未，等.軟件可信性動(dòng)力學(xué)特征及其演化復(fù)雜性［J］.中國科學(xué)：F輯，信息科學(xué)，2009，39（9）：946?950.

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

［9］何華燦，何智濤.無窮概念的重新統(tǒng)一［J］.智能系統(tǒng)學(xué)報(bào)，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］彭漪漣，馬欽榮.邏輯學(xué)大辭典［M］.上海：上海辭書出版社，2004：431，481.

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

［12］何華燦，何智濤.統(tǒng)一無窮理論［M］.北京：科學(xué)出版社，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人工智能基礎(chǔ)專業(yè)委員會(huì)委員，主要研究方向?yàn)檐浖y(cè)試建模、軟件測(cè)試過程管理、知識(shí)工程和泛邏輯。國內(nèi)外發(fā)表學(xué)術(shù)論文10余篇。

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

劉超，1958年生，教授，博士生導(dǎo)師，北京航空航天大學(xué)軟件工程研究所所長，CCF會(huì)員。主要研究方向?yàn)檐浖y(cè)試和軟件工程。國內(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時(shí)代以來，軟件系統(tǒng)就作為計(jì)算機(jī)系統(tǒng)的重要支撐子系統(tǒng)登上了歷史舞臺(tái)，人類自此開始逐步進(jìn)入信息科學(xué)時(shí)代。

TP311；O144.1

A

1673?4785（2014）06?0641?012

何智濤，何華燦，劉超.基于統(tǒng)一無窮理論的軟件測(cè)試可窮盡性研究［J］.智能系統(tǒng)學(xué)報(bào)，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臺(tái)計(jì)算機(jī)誕生，人類邁進(jìn)計(jì)算機(jī)

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