SPIN狀態(tài)壓縮：基于屬性的狀態(tài)向量?jī)?yōu)化.pdf

1、模型檢測(cè)是保證程序正確性的一條重要途徑，它最大的優(yōu)點(diǎn)就是驗(yàn)證過(guò)程完全自動(dòng)化。然而，模型檢測(cè)在規(guī)模大、復(fù)雜度高的系統(tǒng)的應(yīng)用中卻碰到了所謂狀態(tài)空間爆炸問題——對(duì)很多系統(tǒng)來(lái)說(shuō)，其運(yùn)行過(guò)程中所產(chǎn)生的系統(tǒng)狀態(tài)數(shù)目往往隨著系統(tǒng)規(guī)模的擴(kuò)大和及其子模塊數(shù)目的增加而呈現(xiàn)指數(shù)增長(zhǎng)。這直接導(dǎo)致很多系統(tǒng)的規(guī)模超出了當(dāng)前驗(yàn)證工具的能力范圍。 SPIN是貝爾實(shí)驗(yàn)室開發(fā)的面向分布式軟件系統(tǒng)的模型檢測(cè)器。SPIN在應(yīng)用過(guò)程中同樣面臨狀態(tài)空間爆炸問題，它采用偏序

2、歸約策略來(lái)減少狀態(tài)空間中需要遍歷及存儲(chǔ)的狀態(tài)數(shù)目。還有另一種完全不同的策略是減少每個(gè)系統(tǒng)狀態(tài)所需的存儲(chǔ)空間，這屬于內(nèi)存壓縮技術(shù)的范疇。 本文提出了一種基于SPIN的無(wú)損壓縮技術(shù)——基于屬性的狀態(tài)向量?jī)?yōu)化(SOBP)，它利用系統(tǒng)屬性的特點(diǎn)，以一個(gè)變量替換多個(gè)變量的方式對(duì)狀態(tài)向量進(jìn)行優(yōu)化，從而實(shí)現(xiàn)狀態(tài)壓縮。而且，當(dāng)該算法與collapsecompression結(jié)合使用時(shí)，將使collapsecompression更加強(qiáng)大，從而進(jìn)一步