Şekil analizi (program analizi) - Shape analysis (program analysis)

İçinde program analizi, şekil analizi bir statik kod analizi özelliklerini keşfeden ve doğrulayan teknik bağlantılı, dinamik olarak tahsis edilmiş veri yapıları (genellikle zorunlu ) bilgisayar programları. Genellikle derleme sırasında yazılım hatalarını bulmak veya programların üst düzey doğruluk özelliklerini doğrulamak için kullanılır. İçinde Java programları, bir sıralama yönteminin bir listeyi doğru şekilde sıraladığından emin olmak için kullanılabilir. C programları için, bir bellek bloğunun düzgün biçimde serbest bırakılmadığı yerleri arayabilir.

Başvurular

Şekil analizi çeşitli sorunlara uygulanmıştır:

Misal

Şekil analizi bir biçimdir işaretçi analizi tipik işaretçi analizinden daha kesin olmasına rağmen. İşaretçi analizi, bir işaretçinin işaret edebileceği nesne kümesini belirlemeye çalışır (işaretçinin kümelenecek noktaları olarak adlandırılır). Ne yazık ki, bu analizler zorunlu olarak yaklaşıktır (çünkü tamamen kesin bir statik analiz, durdurma sorunu ). Şekil analizi, daha küçük (daha kesin) noktaları-kümeleri belirleyebilir.

Aşağıdaki basit C ++ programını düşünün.

Öğe *öğeler[10];için (int ben = 0; ben < 10; ++ben) {    öğeler[ben] = yeni Öğe(...); // satır 1]}process_items(öğeler); // hat 2]için (int ben = 0; ben < 10; ++ben) {    sil öğeler[ben]; // satır [3]}

Bu program bir dizi nesne oluşturur, bunları rastgele bir şekilde işler ve sonra siler. Varsayarsak process_items işlev hatasızdır, programın güvenli olduğu açıktır: hiçbir zaman serbest belleğe başvurmaz ve oluşturduğu tüm nesneleri siler.

Ne yazık ki, işaretçi analizlerinin çoğu bu programı tam olarak analiz etmekte zorluk çekiyor. Noktaları kümelere belirlemek için, bir işaretçi analizi, isim bir programın nesneleri. Genel olarak, programlar sınırsız sayıda nesne tahsis edebilir; ancak sonlandırmak için, bir işaretçi analizi yalnızca sınırlı bir isim kümesi kullanabilir. Tipik bir yaklaşım, programın belirli bir satırında tahsis edilen tüm nesnelere aynı adı vermektir. Yukarıdaki örnekte, [1] satırında oluşturulan tüm nesneler aynı ada sahip olacaktır. Bu nedenle, ne zaman sil ifadesi ilk kez analiz edildiğinde, analiz [1] adlı nesnelerden birinin silinmekte olduğunu belirler. İfade ikinci kez analiz edildiğinde (döngü içinde olduğu için) analiz olası bir hataya karşı uyarır: dizideki nesneleri ayırt edemediği için, ikinci olabilir sil ilkiyle aynı nesneyi siliyor sil. Bu uyarı sahtedir ve şekil analizinin amacı bu tür uyarılardan kaçınmaktır.

Özetleme ve somutlaştırma

Şekil analizi, nesneler için daha esnek bir adlandırma sistemi kullanarak işaretçi analizinin sorunlarının üstesinden gelir. Bir nesneye bir program boyunca aynı adı vermek yerine, nesneler programın eylemlerine bağlı olarak adları değiştirebilir. Bazen, farklı adlara sahip birkaç farklı nesne özetlendi, veya birleştirilmiş, böylece aynı ada sahip olurlar. Ardından, özetlenmiş bir nesne program tarafından kullanılmak üzereyken, gerçekleştirilmiş—Yani, özetlenen nesne, biri tek bir nesneyi, diğeri geri kalan özetlenmiş nesneleri temsil eden farklı adlara sahip iki nesneye bölünür. Şekil analizinin temel buluşsal yöntemi, program tarafından kullanılan nesnelerin benzersiz maddileştirilmiş nesneler kullanılarak temsil edilmesi ve kullanılmayan nesnelerin özetlenmesidir.

Yukarıdaki örnekteki nesne dizisi [1], [2] ve [3] satırlarında ayrı şekillerde özetlenmiştir. [1] satırında, dizi yalnızca kısmen oluşturulmuştur. 0..i-1 dizi öğeleri, oluşturulmuş nesneleri içerir. Dizi öğesi i inşa edilmek üzere ve aşağıdaki öğeler başlatılmamış. Şekil analizi, aşağıdaki gibi, ilk öğe kümesi için bir özet, öğe i için somutlaştırılmış bir bellek konumu ve kalan başlatılmamış konumlar için bir özet kullanarak bu durumu tahmin edebilir:

0 .. i-1beni + 1 .. 9
oluşturulmuş nesneye işaretçi (özet)başlatılmamışbaşlatılmamış (özet)

Döngü sona erdikten sonra, [2] satırında herhangi bir şeyin gerçekleştirilmesine gerek yoktur. Şekil analizi, bu noktada tüm dizi elemanlarının başlatıldığını belirler:

0 .. 9
oluşturulmuş nesneye işaretçi (özet)

[3] satırında, ancak dizi öğesi ben tekrar kullanımda. Bu nedenle, analiz diziyi [1]. Satırdaki gibi üç parçaya ayırır. Ancak bu sefer, önceki ilk bölüm ben silindi ve kalan öğeler hala geçerli ( sil ifadesi henüz yürütülmedi).

0 .. i-1beni + 1 .. 9
ücretsiz (özet)inşa edilmiş nesneye işaretçioluşturulmuş nesneye işaretçi (özet)

Bu durumda, analizin indeksteki işaretçinin ben henüz silinmedi. Bu nedenle, çifte silme konusunda bir uyarıda bulunmaz.

Ayrıca bakınız

Referanslar

  1. ^ Rinetzky, Noam; Sagiv, Mooly (2001). "Yinelemeli Programlar İçin İşlemler Arası Şekil Analizi" (PDF). Derleyici İnşaatı. Bilgisayar Bilimlerinde Ders Notları. 2027. pp.133–149. doi:10.1007/3-540-45306-7_10. ISBN  978-3-540-41861-0.
  2. ^ a b Berdine, Josh; Calcagno, Cristiano; Cook, Byron; Distefano, Dino; o'Hearn, Peter W .; Wies, Thomas; Yang, Hongseok (2007). "Bileşik Veri Yapıları için Şekil Analizi" (PDF). Bilgisayar Destekli Doğrulama. Bilgisayar Bilimlerinde Ders Notları. 4590. sayfa 178–192. doi:10.1007/978-3-540-73368-3_22. ISBN  978-3-540-73367-6.

Kaynakça

  • Neil D. Jones; Steven S. Muchnick (1982). "İşlemler arası veri akışı analizine ve yinelemeli veri yapılarına sahip programlara esnek bir yaklaşım". POPL '82 9. ACM SIGPLAN-SIGACT Programlama Dilleri İlkeleri Sempozyumu Bildirileri. ACM: 66–74. doi:10.1145/582153.582161. ISBN  0897910656.
  • Wilhelm, Reinhard; Sagiv, Mooly; Reps, Thomas (2007). "Bölüm 12: Şekil Analizi ve Uygulamaları". Srikant, Y. N .; Shankar, Priti (editörler). Derleyici Tasarım El Kitabı: Optimizasyonlar ve Makine Kodu Üretimi, İkinci Baskı. CRC Basın. sayfa 12–1–12–44. ISBN  978-1-4200-4382-2.