Cyclomatic karmaşıklık - Cyclomatic complexity

Siklomatik karmaşıklık , bir programın karmaşıklığını belirtmek için kullanılan bir yazılım metriğidir . Bir programın kaynak kodu aracılığıyla doğrusal olarak bağımsız yolların sayısının nicel bir ölçüsüdür . 1976'da Thomas J. McCabe, Sr. tarafından geliştirilmiştir .

Döngüsel karmaşıklık, programın kontrol-akış grafiği kullanılarak hesaplanır : grafiğin düğümleri , bir programın bölünmez komut gruplarına karşılık gelir ve ikinci komut ilk komuttan hemen sonra yürütülebilirse, yönlendirilmiş bir kenar iki düğümü birbirine bağlar. Siklomatik karmaşıklık, bir program içindeki bireysel işlevlere , modüllere , yöntemlere veya sınıflara da uygulanabilir .

İlk öneren McCabe tarafından temel yol testi olarak adlandırılan bir test stratejisi, program boyunca doğrusal olarak bağımsız her yolu test etmektir; bu durumda, test senaryolarının sayısı programın döngüsel karmaşıklığına eşit olacaktır.

Açıklama

Tanım

Basit bir programın kontrol akış grafiği. Program kırmızı düğümde çalışmaya başlar, ardından bir döngüye girer (kırmızı düğümün hemen altındaki üç düğümden oluşan grup). Döngüden çıkıldığında, bir koşullu ifade vardır (döngünün altındaki grup) ve son olarak program mavi düğümden çıkar. Bu grafiğin 9 kenarı, 8 düğümü ve 1 bağlantılı bileşeni vardır , dolayısıyla programın döngüsel karmaşıklığı 9 - 8 + 2 * 1 = 3'tür.

Kaynak kodun bir bölümünün döngüsel karmaşıklığı, içindeki doğrusal olarak bağımsız yolların maksimum sayısıdır - burada "doğrusal olarak bağımsız", her yolun diğer yollardan birinde olmayan en az bir kenara sahip olduğu anlamına gelir. Örneğin, kaynak kodu hiçbir kontrol akışı ifadesi içermiyorsa (koşullu veya karar noktaları), kod boyunca yalnızca tek bir yol olacağından karmaşıklık 1 olacaktır. Kodun bir tek koşullu EĞER ifadesi varsa, kodda iki yol bulunur: Biri EĞER ifadesinin DOĞRU olarak değerlendirildiği ve diğeri YANLIŞ olarak değerlendirildiği, dolayısıyla karmaşıklık 2. İki iç içe geçmiş tek koşullu EĞER veya iki koşullu bir EĞER 3'lük bir karmaşıklık üretecektir.

Matematiksel olarak, yapılandırılmış bir programın döngüsel karmaşıklığı, programın kontrol akış grafiğine , programın temel bloklarını içeren yönlendirilmiş bir grafiğe göre tanımlanır; eğer kontrol , ilkinden diğerine geçebiliyorsa , iki temel blok arasında bir kenar ile ikinci. Karmaşıklık M daha sonra şu şekilde tanımlanır:

M = E - N + 2 P ,

nerede

E = grafiğin kenar sayısı.

N = grafiğin düğüm sayısı.

P = bağlı bileşenlerin sayısı .

Her çıkış noktasının giriş noktasına geri bağlandığı alternatif formülasyon kullanılarak temsil edilen yukarıdaki ile aynı işlev. Bu grafiğin 10 kenarı, 8 düğümü ve 1 bağlantılı bileşeni vardır , bu da alternatif formülasyon kullanılarak 3'ün siklomatik karmaşıklığına neden olur (10 - 8 + 1 = 3).

Alternatif bir formülasyon, her çıkış noktasının giriş noktasına geri bağlandığı bir grafik kullanmaktır. Bu durumda, grafik güçlü bir şekilde bağlantılıdır ve programın döngüsel karmaşıklığı , grafiğinin döngüsel sayısına ( ilk Betti numarası olarak da bilinir ) eşittir.

M = e - N + p .

Bu , grafikte var olan doğrusal olarak bağımsız döngülerin , yani kendi içlerinde başka döngüleri içermeyen döngülerin sayısının hesaplanması olarak görülebilir . Her çıkış noktası giriş noktasına geri döndüğünden, her çıkış noktası için en az bir adet böyle döngü vardır.

Tek bir program (veya alt program veya yöntem) için, P her zaman 1'e eşittir. Dolayısıyla, tek bir alt program için daha basit bir formül

M = E - N + 2.

Bununla birlikte, siklomatik karmaşıklık, aynı anda bu tür birkaç programa veya alt programa uygulanabilir (örneğin, bir sınıftaki tüm yöntemlere) ve bu durumlarda , her bir alt programda P , söz konusu programların sayısına eşit olacaktır. grafiğin bağlantısız bir alt kümesi olarak görünecektir.

McCabe, yalnızca bir giriş noktası ve bir çıkış noktası olan herhangi bir yapılandırılmış programın döngüsel karmaşıklığının, o programda yer alan karar noktalarının (yani, "eğer" ifadeleri veya koşullu döngülerin) sayısına eşit olduğunu gösterdi. Ancak bu, yalnızca en düşük makine düzeyindeki talimatlarda sayılan karar noktaları için geçerlidir. Bu gibi yüksek seviyeli dillerde bulunanlar gibi bileşik tahminleri içeren kararlar, ilgili IF cond1 AND cond2 THEN ... tahmin değişkenleri açısından sayılmalıdır, yani bu örnekte biri iki karar noktası sayılmalıdır, çünkü makine seviyesinde eşdeğerdir IF cond1 THEN IF cond2 THEN ... .

Siklomatik karmaşıklık, birden çok çıkış noktası olan bir programa genişletilebilir; bu durumda eşittir

π - s + 2,

burada program programdaki karar noktalarının sayısıdır ve s , çıkış noktalarının sayısıdır.

Cebirsel topoloji açısından açıklama

Bir grafiğin çift bir alt grafiği ( Euler alt grafiği olarak da bilinir ), her köşenin çift sayıda kenara sahip olduğu bir tablodur ; bu tür alt grafikler, döngü birlikleri ve izole köşelerdir. Aşağıda, alt grafikler bile kenar kümeleriyle tanımlanacaktır; bu, yalnızca tam grafiğin tüm köşelerini içeren çift alt grafikleri dikkate almaya eşdeğerdir.

Bir grafiğin tüm çift alt grafiklerinin kümesi simetrik fark altında kapatılır ve bu nedenle GF (2) üzerinde bir vektör uzayı olarak görülebilir ; bu vektör uzayına grafiğin döngü uzayı denir . Tümevarımcı grafiğin bu alan boyut olarak tanımlanır. GF (2) iki elemana sahip olduğundan ve döngü uzayı zorunlu olarak sonlu olduğundan, döngüsel sayı da döngü uzayındaki eleman sayısının 2-logaritmasına eşittir.

Döngü alanı için bir temel , önce grafiğin genişleyen bir ormanı sabitlenerek ve ardından ormanda olmayan bir kenarın oluşturduğu döngüler ve ormandaki bu kenarın uç noktalarını birbirine bağlayan yol göz önünde bulundurularak kolayca oluşturulabilir; bu döngüler, döngü alanı için bir temel oluşturur. Dolayısıyla, siklomatik sayı aynı zamanda bir grafiğin maksimal yayılma ormanında olmayan kenarların sayısına da eşittir. Bir grafiğin maksimal yayılma ormanındaki kenarların sayısı, köşe sayısı eksi bileşenlerin sayısına eşit olduğundan, yukarıdaki siklomatik sayı için formül aşağıdadır. ${\ displaystyle E-N + P}$

Topolojik olarak daha eğimli olanlar için, siklomatik karmaşıklık alternatif olarak göreceli bir Betti sayısı , göreceli bir homoloji grubunun boyutu olarak tanımlanabilir :

{\ displaystyle M: ​​= b_ {1} (G, t): = \ operatöradı {sıra} H_ {1} (G, t),}

" terminal düğümlerine t göre, G grafiğinin birinci homoloji grubunun sıralaması" olarak okunur . Bu, "girişten çıkışa akış grafiği boyunca doğrusal olarak bağımsız yolların sayısı" demenin teknik bir yoludur, burada:

"doğrusal olarak bağımsız", homolojiye karşılık gelir ve birinin geriye doğru izlemeyi iki kez saymayacağı anlamına gelir;
"yollar", birinci homolojiye karşılık gelir : bir yol, 1 boyutlu bir nesnedir;
"göreli", yolun bir giriş veya çıkış noktasında başlaması ve bitmesi gerektiği anlamına gelir.

Bu, sezgisel siklomatik karmaşıklık kavramına karşılık gelir ve yukarıdaki gibi hesaplanabilir.

Alternatif olarak, bu, belirli bir bileşendeki tüm terminal düğümlerini tanımlayarak (birbirine yapıştırarak) (veya eşdeğer olarak, çıkışları girişe bağlayan yolları çizerek) mutlak Betti sayısı (mutlak homoloji - göreceli değil) aracılığıyla hesaplanabilir, bu durumda (arama yeni, artırılmış grafik , yani) elde edilen ${\ displaystyle {\ tilde {G}}}$

{\ displaystyle M = b_ {1} ({\ tilde {G}}) = \ operatöradı {sıra} H_ {1} ({\ tilde {G}}).}

Aynı zamanda homotopi ile de hesaplanabilir . Bir 1-boyutlu olarak kontrol akış grafiğini gördüğü takdirde kompleks CW adı daha sonra, temel grup arasında olacaktır . Değeri , siklomatik karmaşıklıktır. Temel grup, grafikte homotopi'ye kadar kaç döngü olduğunu sayar ve bu nedenle sezgisel olarak beklediğimiz şeyle aynı hizaya gelir. ${\ displaystyle X}$ ${\ displaystyle X}$ ${\ displaystyle \ pi _ {1} (X) = \ mathbb {Z} ^ {n}}$ ${\ displaystyle n + 1}$

Bu, siklomatik karmaşıklığın "döngü sayısı artı bileşen sayısı" olarak nitelendirilmesine karşılık gelir.

Başvurular

Geliştirme sırasında karmaşıklığı sınırlama

McCabe'nin orijinal uygulamalarından biri, program geliştirme sırasında rutinlerin karmaşıklığını sınırlamaktı; programcıların geliştirdikleri modüllerin karmaşıklığını saymalarını ve modülün döngüsel karmaşıklığı 10'u aştığında bunları daha küçük modüllere ayırmalarını tavsiye etti. Bu uygulama, McCabe'nin orijinal yayınından bu yana NIST Yapılandırılmış Test metodolojisi tarafından benimsenmiştir. , 10 rakamı önemli ölçüde destekleyici kanıtlar almıştı, ancak bazı durumlarda kısıtlamayı gevşetmek ve 15'e varan karmaşıklığa sahip modüllere izin vermek uygun olabilir. Metodoloji, üzerinde anlaşılanın ötesine geçmek için ara sıra nedenlerin olduğunu kabul etti. sınır üzerine, tavsiyesini "Her modül için, siklomatik karmaşıklığı [üzerinde anlaşılan sınırla] sınırlandırın veya sınırın neden aşıldığına dair yazılı bir açıklama sağlayın" şeklinde ifade etti.

Bir programın "yapısallığını" ölçme

McCabe'nin 1976 tarihli makalesinin VI. Bölümü, yapılandırılmamış programların kontrol akış grafiklerinin (CFG'ler), McCabe'nin tanımladığı , alt grafikleri açısından neye benzediğini belirlemekle ilgilidir. (Bu bölümle ilgili ayrıntılar için yapılandırılmış program teoremine bakın .) McCabe, belirli bir programın yapılandırılmış programlama idealine ne kadar yakın olduğuna, yani McCabe'nin neolojizmini kullanan "yapılandırılmışlığına" ilişkin sayısal bir ölçüm önererek bu bölümü sonlandırır. McCabe, bu amaç için tasarladığı önlemi temel karmaşıklık olarak adlandırdı .

Bu ölçüyü hesaplamak için, orijinal CFG, daha sonra tek bir düğümle değiştirilen tek girişli ve tek çıkışlı alt grafiklerin tanımlanmasıyla yinelemeli olarak küçültülür. Bu azalma, bir insanın daha büyük kod parçasından bir alt yordamı çıkarması durumunda ne yapacağına karşılık gelir. (Günümüzde böyle bir süreç yeniden düzenleme şemsiyesi altına girecektir .) McCabe'nin indirgeme yöntemi daha sonra bazı ders kitaplarında yoğunlaştırma olarak adlandırıldı , çünkü bu, grafik teorisinde kullanılan bileşenlere yoğunlaşmanın bir genellemesi olarak görülüyordu . Bir program yapılandırılmışsa, McCabe'nin azaltma / yoğunlaştırma süreci onu tek bir CFG düğümüne indirger. Aksine, program yapılandırılmamışsa, yinelemeli süreç indirgenemez kısmı belirleyecektir. McCabe tarafından tanımlanan temel karmaşıklık ölçüsü, basitçe bu indirgenemez grafiğin döngüsel karmaşıklığıdır, bu nedenle tüm yapılandırılmış programlar için tam olarak 1 olacaktır, ancak yapılandırılmamış programlar için birden büyük olacaktır.

Yazılım testi için çıkarımlar

Siklomatik karmaşıklığın başka bir uygulaması, belirli bir modülün kapsamlı test kapsamını elde etmek için gerekli olan test senaryolarının sayısını belirlemektir.

Belirli bir modül için siklomatik karmaşıklığın ( M) iki özelliği nedeniyle kullanışlıdır :

M , tam bir branş kapsamı elde etmek için gerekli olan test senaryolarının sayısı için bir üst sınırdır .
M , kontrol akış grafiğinden (CFG) geçen yol sayısı için alt sınırdır. Her test senaryosunun bir yol izlediğini varsayarsak, yol kapsamına ulaşmak için gereken olay sayısı, gerçekte alınabilecek yolların sayısına eşittir. Ancak bazı yollar imkansız olabilir, bu nedenle, CFG'den geçen yolların sayısı, yol kapsamı için gereken test senaryolarının sayısının açık bir üst sınırı olsa da, bu son sayı ( olası yolların) bazen M'den daha azdır .

Yukarıdaki sayıların üçü de eşit olabilir: dal kapsamı siklomatik karmaşıklık yolların sayısı. ${\ displaystyle \ leq}$ ${\ displaystyle \ leq}$

Örneğin, iki sıralı if-then-else deyiminden oluşan bir program düşünün.

if (c1())
    f1();
else
    f2();

if (c2())
    f3();
else
    f4();

Yukarıdaki kaynak kodun kontrol akış grafiği; kırmızı daire, fonksiyonun giriş noktasıdır ve mavi daire, çıkış noktasıdır. Çıkış, grafiğin güçlü bir şekilde bağlanmasını sağlamak için girişe bağlanmıştır.

Bu örnekte, tam bir şube kapsamı elde etmek için iki test durumu yeterliyken, tam yol kapsamı için dört test gereklidir. Programın döngüsel karmaşıklığı 3'tür (programın güçlü bağlantılı grafiği 9 kenar, 7 düğüm ve 1 bağlı bileşen içerdiğinden) (9 - 7 + 1).

Genel olarak, bir modülü tam olarak test etmek için, modül boyunca tüm yürütme yolları uygulanmalıdır. Bu, karmaşıklık numarası yüksek bir modülün, daha düşük bir değere sahip bir modüle göre daha fazla test çabası gerektirdiği anlamına gelir, çünkü karmaşıklık sayısı daha yüksek, kodda daha fazla yolu gösterir. Bu aynı zamanda, daha karmaşık bir modülün, programcının farklı yolları ve bu yolların sonuçlarını anlaması gerektiğinden, bir programcı için anlaması daha zor olduğu anlamına gelir.

Ne yazık ki, bir program aracılığıyla tüm olası yolları test etmek her zaman pratik değildir. Yukarıdaki örneği göz önünde bulundurarak, her ek bir if-then-else ifadesi eklendiğinde, olası yolların sayısı 2 kat artar. Program bu şekilde büyüdükçe, tüm yolları test etme noktasına hızla ulaşır. pratik değil.

Örneğin NIST Yapılandırılmış Test metodolojisi tarafından benimsenen yaygın bir test stratejisi, modülün yeterli kapsamını elde etmek için gereken beyaz kutu testlerinin sayısını belirlemek için bir modülün döngüsel karmaşıklığını kullanmaktır . Hemen hemen tüm durumlarda, böyle bir metodolojiye göre, bir modülün en az siklomatik karmaşıklığı kadar çok testi olmalıdır; çoğu durumda, bu sayıda test, işlevin tüm ilgili yollarını uygulamak için yeterlidir.

Doğru bir şekilde test etmek için sadece dal kapsamından fazlasını gerektiren bir işleve örnek olarak, yukarıdaki işlevi tekrar düşünün, ancak bir hatanın oluşmasını önlemek için f1 () veya f3 () 'ü çağıran herhangi bir kodun da diğerini çağırması gerektiğini varsayın. C1 () ve c2 () sonuçlarının bağımsız olduğunu varsayarsak, bu, yukarıda sunulan işlevin bir hata içerdiği anlamına gelir. Şube kapsamı, yöntemi yalnızca iki testle test etmemize izin verir ve olası bir test seti aşağıdaki durumları test etmek olacaktır:

c1() true c2() değerini döndürür ve true değerini döndürür
c1() yanlış döndürür ve c2() yanlış döndürür

Bu durumların hiçbiri hatayı açığa çıkarmaz. Bununla birlikte, ihtiyaç duyduğumuz testlerin sayısını belirtmek için döngüsel karmaşıklık kullanırsak, sayı 3'e çıkar. Bu nedenle aşağıdaki yollardan birini test etmeliyiz:

c1() doğru döndürür ve c2() yanlış döndürür
c1() yanlış döndürür ve c2() doğru döndürür

Bu testlerden herhangi biri hatayı ortaya çıkaracaktır.

Kusur sayısıyla ilişki

Bir dizi çalışma, McCabe'nin döngüsel karmaşıklık sayısı ile bir işlev veya yöntemde meydana gelen kusurların sıklığı arasındaki ilişkiyi araştırmıştır. Bazı çalışmalar, siklomatik karmaşıklık ve kusurlar arasında pozitif bir korelasyon bulmaktadır: en yüksek karmaşıklığa sahip olan işlevler ve yöntemler, aynı zamanda en çok kusuru da barındırma eğilimindedir. Bununla birlikte, döngüsel karmaşıklık ile program boyutu (tipik olarak kod satırlarıyla ölçülür) arasındaki ilişki birçok kez gösterilmiştir. Les Hatton , karmaşıklığın kod satırlarıyla aynı öngörü yeteneğine sahip olduğunu iddia etti. Program boyutunu kontrol eden çalışmalar (yani, farklı karmaşıklıklara sahip ancak benzer boyuta sahip modülleri karşılaştırmak) genellikle daha az kesin sonuç verirken, birçoğu önemli bir korelasyon bulmazken, diğerleri korelasyon bulmuştur. Alan üzerinde çalışan bazı araştırmacılar, herhangi bir korelasyon bulamayan çalışmaların kullandığı yöntemlerin geçerliliğini sorgulamaktadır. Bu ilişki muhtemelen doğru olsa da, kolayca kullanılamaz. Program boyutu ticari yazılımın kontrol edilebilir bir özelliği olmadığı için McCabes'in sayısının kullanışlılığı sorgulanmaya başlandı. Bu gözlemin özü, daha büyük programların daha karmaşık olma ve daha fazla kusura sahip olma eğiliminde olmasıdır. Kodun döngüsel karmaşıklığını azaltmanın, bu koddaki hata veya hataların sayısını azalttığı kanıtlanmamıştır . Bununla birlikte, ISO 26262 gibi uluslararası güvenlik standartları , düşük kod karmaşıklığını zorunlu kılan kodlama yönergelerini zorunlu kılar.

Yapay zeka

Siklomatik karmaşıklık, yapay zeka programlarının anlamsal karmaşıklığının değerlendirilmesi için de kullanılabilir.

Ultrametrik topoloji

Döngüsel karmaşıklığın, ultrametrik mesafelerin grafiklerine uygulanabileceği gösterildikten sonra coğrafi ve peyzaj-ekolojik analizde yararlı olduğu kanıtlanmıştır .

Languages

In other projects

Cyclomatic karmaşıklık - Cyclomatic complexity

İçindekiler