HEAP'İ ANLAMAK Part 2

HEAP'İ ANLAMAK - GLIBC Part 2

Heapi anlamak serisinin 2. yazısına hoşgeldiniz.

Bu serinin ilk yazısına şuradan ulaşabilirsiniz. HEAP'İ ANLAMAK Part 1

İlk yazıda malloc ve free fonksiyonlarının basit davranışını açıkladık. Aynı şekilde malloc ile ayrılan chunkta sadece kullanıcı verisinin bulunmadığını, bunun yanında metadata verisininde bulunduğunu gördük. Aynı şekilde heap yöneticisinin bir chunkı nasıl ayırdığını yani ayırma stratejilerini inceledik.

Bu yazıda ise chunkların nasıl tekrardan kullanıldığından, chunkların nasıl free edildiğinden, free edilmiş chunkların nasıl tekrardan kullanıldığından bahsedeceğiz. Birçok heap exploit bu iç sistemi bozmayı amaçlar. Heap nasıl exploit edelir başka bir yazının konusu olacak fakat bu yazıda bu iç işlemlerin nasıl çalıştığını inceleyeceğiz.

free Nasıl Çalışır

Programcı malloc fonksiyonu ile aldığı hafıza işini bitirdiği zaman free fonksiyonu ile bu hafızayı heap yöneticisine iade eder. C standardı free(NULL) çağrısını hiç bir şey yapma olarak tanımlar. Diğer free fonksiyon çağrılarında ise heap yöneticisinin ilk işi fonksiyona geçirilen pointerin ait olduğu chunkı bulmak. Heap yöneticisi bu işlemi free fonksiyonuna geçirilen adresten metadata boyutunu çıkararak bulur.

Pointerdan chunka olan bu dönüşün sorunsuz bir şekilde çalışır çünkü metadata boyutu sabittir ve user datası metadata alanından hemen sonra gelir. malloc dan elde edilen pointerlar free işlemiyle sorunsuz bir şekilde heap yöneticisine iade edilirler. Eğer malloc ile elde edilmeyen bir pointer free fonksiyonuna sokulursa hafıza alanlarında bozulmalar meydana gelebilir, program normal şartlarda ulaşmaması gereken bir hafıza alanına ulaşmaya çalışabilir, buna bağlı olarak program çökebilir yada bir saldırgan tarafından bu durum kötüye kullanılarak sistem üzerinde komut çalıştırmayı başarabilir.

Bu nedenlerden dolayı free fonksiyonu herhangi bir işlem yapmadan önce bir takım kontroller yapar. Eğer bu kontrollerden birisi başarısız olursa işlen sonlandırılır (abort). Bu kontrolleri şu şekilde listeleyebiliriz:

1. Ayrılan alanın hizalanmış olup olmadığını kontrol eder. 32 bit sistemlerde hizalama 8 byte, 64 bit sistemlerde hizalama 16 bytedır.
2. Chunk boyutunun geçersiz bir değer olmadığından emin olur. Yani chunkın çok küçük olmadığını, çok büyük olmadığını, hizalanmış olup olmadığını, processin adres alanının dışında olmadığından emin olmaya çalışır.
3. Chunkın geçerli bir arenanın içinde olup olmadığını kontrol eder.
4. Sonraki chunkın P bayrağına bakarak mevcut chunkın free olup olmadığını kontrol eder.

Burada yapılan kontroller ayrıntılı kontroller değildir. Yani bir saldırgan bu kontrolleri aşarak hafıza bozulması oluşturabilir. Buna daha sonraki yazılarımda değineceğim.

Free Chunk Metadata

Bir önceki yazımda bir chunkın içerisinde chunka ait metadatanın olduğunu, bu metadatanın yanında kullanıcı verisi için gerekli alanın bulunduğundan bahsetmiştik. Buradaki metadata bin önceki chunkbyutunu, mevcut chunk boyutunu, "A", "M", "P" bayraklarının bulunduğunu görmüştük. Bu metadata heap yöneticisinin chunk hakkında bilgi sahibi olmasını sağlar: chunk main-arenada mı, chunk mmap ile mi ayrıldı, chunk daha önceden free edildi mi?

Free chunklar da metadata bilgisi tutarlar. Free chunklar chunk boyutu, A ve P bilgilerini metadatalarında saklarlar fakat M alanını kullanmazlar. mmap ile elde edilmiş chunklar ise munmap ile doğrudan işletim sistemine iade edilirler, heap yöneticisine değil.

Free chunkların bir liste yapısında tutulduğundan bahsetmiştik. Bu liste yapısı için gereken pointerlar free chunkın userdata kısmında tutulur. fwd pointer sonraki free chunkın adresini taşır, bck pointer ise bir önceki free chunkın adresini taşır. Ayrıca buna benzer diğer bilgileri userdata kısmında saylayabilir.

NOT: Chunk kullanıcı tarafından free edildiği için heap yöneticisinin userdata alanını kullanmasında bir sakınca yoktur.

Binler İle Hafıza Geri Dönüşümü

"bin" için güzel bir çeviri bulamadım. Bu yüzden olduğu gibi kullanacağım. Kusura bakmayın :(

Heap yöneticisi kendi iç sisteminde free chunkları takip etmelidir. Bu sayede yeni bir hafıza isteği geldiği zaman daha önceden free edilmiş chunkları tekrardan kullanabilir. Heap yöneticisi bunu tüm free chunkları bir bağlı listede tutarak yapabilir. Bu yöntem çalışacaktır fakat bu yöntem malloc fonksiyonunun yavaş çalışmasına neden olacaktır. malloc gibi fonksiyonların programlarda oldukça yoğun kullanıldığını düşünürsek, bu yavaşlık çalışan programın yada sistemin performansını oldukça etkileyecektir.

Performansı arttırmak için heap yöneticisi, bin isminde çaşitli listeler kullanarak malloc ve free performansını maksimum seviyeye çıkarmaya çalışır.

Toplamda 5 tür bin vardır. Theread başına: 62 küçük (small) bin, 63 büyük (large) bin, 1 tane sırasız (unsorted) bin, 10 tane hızlı (fast) bin vardır.

Küçük, sırasız ve büyük binler en eski bin türleridir ve bu yazı boyunca bunlar üzerinde duracağız. Fast binler ve tcache binler bunlar üzerine kurulan optimizasyonlardır.

Şaşırtıcı bir şekilde heap yöneticisinin kaynak kodunda küçük (small), büyük (large) ve sırasız (unsorted) binler aynı array üzerinde tutulurlar. 0. index kullanılmaz, 1. index sırasız bin, 2-64 arası küçük bin, 65-127 arası büyük bindir.

Chunklar Geri Dönüşüm Stragejisi

Tcache ve fastbinlere girmeden önce heap yöneticisinin chunkları nasıl geri dönüştürdüğünü anlamaya çalışalım.

Hatırlatma: free algoritması şu şekilde çalışıyordu:

1. Chunk matadatasında M bayrağı işaretlenmişse, chunk off-heap ile ayrılmıştır ve munmap kullanılmalıdır.
2. Free edilmek istenen chunktan bir önceki chunk free ise, bu chunk bir önceki chunk ile birleştirerek daha büyük bir chunk oluşturulabilir.
3. Benzer şekilde free edilecek chunktan sonraki chunk free ise, sonraki chunk ile birleştirilir ve daha büyük bir chunk oluşturulur.
4. Eğer chunk heapin en yukarısında ise chunk heapin sonuna eklenir.
5. Aksi halde chunk free olarak işaretlenir ve uygun bin içerisine yerleştirilir.

Küçük (Small) Binler

Küçük binler anlaması en kolay bin türüdür. 62 tane küçük bin vardır ve her bin sabit uzunlukta chunkları barındırır. 32 bit sistemlerde 512 bytetan (64 bit sistemlerde 1024 byte) küçük chunkar için uygun bir küçük bin vardır. Her küçük bin sabit belirli uzunlukta chunkları tuttuğundan, chunklar sıralıdır ve binler üzerine ekleme ve kaldırma işlemleri oldukça hızlıdır.

Büyük (Large) Binler

Küçük chunk boyutları için küçük bin yapısı oldukça uygundur fakat biz her boyuttaki chunk için bu stratejiyi uygulamayayız. 512 bytedan büyük (64 bit sistemlerde 1024) chunklar için heap yöneticisi büyük (large) binler kullanır.

63 büyük bin çoğunlukla küçük binler ile aynı şekilde çalışır. Fakat büyük binlerde olduğu gibi chunkları aynı boyutta saklamak yerine bir boyut aralığında saklarlar. Bu özellik büyük binleri küçük binlere göre biraz daha yavaş yapar. Fakat büyük chunklar çoğu programda küçük chunklara göre daha az kullanılırlar. Aynı şekilde küçük chunkarın kullanılma sıklığı büyük chunklara göre oldukça fazladır.

Sırasız (Unsorted) Binler

Heap yöneticisi "unsorted bins" isminde bir yapı ile önbellek katmanı sağlayarak performansı arttırmaya çalışır. Bu önbellek aynı boyuttaki chunkların devamlı olarak free edilmesi ve ayrılması durumunda oldukça performans artışı sağlayacaktır.

Bu tarz durumlarda bir chunkın bir önceki chunk ile birleştirilip ardından bir bin içerisine yarleştirilmesi performansı olumsuz olarak etkileyecekti. Unsorted bin ile bunlarak gerek kalmadan chunklar oldukça hızlı bir şekilde geri dönüştürülüp tekrardan kullanılabiliyorlar.

Heap yöneticisi unsorted bini kullanarak bu durumdan faydalanmaya çalışır. Free edilen chunkları hemen uygun bine koymak yerine, genel amaçlı sırasız bir bin içerisine yerleştirir. malloc çalışırken sırasız binlerdeki chunklar isteği karşılamaya uygun chunk varmı diye kontrol edilir. Eğer var ise malloc bu chunkı kullanır. Eğer yoksa malloc chunkı uygun bin içerisine yerleştirir.

Hızlı (Fast) Binler

Hızlı binler normal binler üzerine kurulan bir optimizasyondur. Bu binler temel olarak yeni free edilmiş küçük chunkları "hızlı geri dönüşüm kuruğu (fast-turnaround queue)" isminde bir listede tutar. Heapin iç sisteminde chunkın komşuları (önceki yada sonraki chunk) ile birleştirilmezler. Bu sayede yeni bir istek geldiği zaman hemen tekrardan kullanılabilirler.

Küçük binler gibi, her hızlı (fast) bin sabit uzunluktaki chunkları barındırır. Toplamda 10 tane fast bin vardır. Bunlar: 16, 24, 32, 40, 48, 56, 64, 72, 80, 88 (metadata boyutu dahil değil) dir.

Fast bin chunklar komşuları ile asla birleşmezler. Bu yöntem heap yöneticisinin sonraki chunkın P bayrağını işaretlemediğinden dolayı çalışır. Biraz düşünürsek heap yöneticisinin gerçek anlamda chunkı free etmediğini anlayabiliriz.

Küçük binlerde olduğu gibi hızlı binler tek boyutta chunk taşırlar. Bu nedenle ekleme ve silme işlemleri oldukça hızlı gerçekleşir. Komşuları ile birleştirilme ihtimali olmadığı için tek bağlantılı listelerde tutulurlar.

Hızlı binlerin eksi yönü ise şudur. Hızlı binler gerçek manada free edilmediklerinden dolayı zamanla processin hafıza alanlarının çakışmasına neden olacak yada işlemin zamanla şişmesine neden olacaktır. Heap yöneticisi bunu çözmek için periyodik olarak düzenleme yapar, chunkları gerçek manada free eder ve komşuları ile birleştirir ve uygun bin içerisine yerleştirir.

Tcache Binler

Heap yöneticisinin optimizasyon için kullandığı son yöntem tcache (per-thread cache) dir. Öncelikle tcache nin hangi probleme çözüm bulmaya çalıştığını anlamaya çalışalım.

Çoğu program kendi içerisinde birden fazla thread çalıştırır. Çoklu thread desteği programa aynı anda birden çok işlem yapmasına olanak sağlar. Örneğin bir web server kendisine gelen http requestleri işlerken her isteği ayrı bir threadde işleyerek aynı anda birden çok isteğe cevap verebilir. İstekleri sıraya koyup tek tek işlemesine gerek kalmaz.

Threadler işlemin adres alanını paylaşırlar. Yani her thread işlem içerisindeki bilgileri ve kodları görür. Her threadin yerel değişkenlerini saklayacağı stack alanı ve registerleri vardır fakat her thread aynı heap alanını paylaşırlar aynı global değişkenleri kullanırlar.

Çoklu thread ile çalışan programlarda global kaynaklara ve heap erişim dikkatli bir şekilde denetlenmelidir. Aksi halde programın çökmesine neden olabilir yada racec-ondition gibi sorunlara neden olabilir. Bu tür zafiyetlerin debug edilmesi ve çözülmesi zordur. Aynı şekilde saldırganlar tarafından kullanılma ihtimali de vardır.

Genel olarak bir thread bir global kaynağı kullanacağı zaman kaynağın sahipliğini alır. Yani kaynağı kullanımda olarak işaretler. Thread işlemlerini tamamladıktan sonra kaynağın işaretini kaldırır. Eğer bir başka thread kaynağın kullanımda olduğunu görürse kaynak boşa çıkasıya kadar bekler. Elbette bu zaman kaybına yok açar.

Birçok global kaynak için bu kabul edilebilir bir maliyettir. Fakat heap gibi çok sık kullanılan bir kaynak düşünüldüğünde bu bekleme programda ciddi bir yavaşlamaya ve performans kaybına neden olacaktır.

Heap yöneticisi bu problemi her thread için bir arena ayırmaya çalışarak çözmeye çalışır. Tabiki arena sayısının bir üst limiti vardır. Buna ek olarak tcache bu kilitleme işlemindeki maliyeti azaltmaya çalışır çünkü bir kaynağın kilitlenmesi maliyetlidir. Bu özellik Glibc'ye 2.26 sürümüyle eklenmiştir ve varsayılan olarak aktif olarak gelir.

Özetle tcache binler çoklu thread ile çalışan uygulamalarda kilitleme (lock) durumlarından kaynaklanan performans kaybını minimuma indirmeye çalışırlar.

Chunklar Tcache Nasıl Yerleştirilir

Her ne zaman bir chunk free edildiğinde heap yöneticisi bu chunkın boyutunun tcache için uygun olup olmadığına bakar. Hızlı (fast) binlerde olduğu gibi tcachedeki chunklar gerçek manada free edilmemiştir ve komşuları ile birleştirilmezler.

Eğer chunk boyutu tcache için uygun değilse (mesela chunk çok büyükse) heap yöneticisi heap kilidini alır, chunkı gerçek manada free eder, uygun bin içerisine yerleştirir. Bu yöntem tcache göre elbette yavaş çalışır.

Tcache üzrinden chunk alımı oldukça basittir. Eğer gelen isteği karşılamaya uygun bir chunk tcache içerisinde varsa heap kilidini almadan chunk temin edilebilir.

Özet

Bu yazıyla beraber Glibc içerisindeki malloc ve free nin davranışlarını öğrendik. Aynı şekilde kullanılan algoritmaların neden kullanıldığını anladık.

Programcı heapden hafıza talep ettiği zaman, heap yöneticisi chunk boyutununun ne kadar olduğuna bakar ve buna göre işlem yapmaya çalışır. Heapi şu sırayla arar:

1. Eğer tcache de isteği karşılamaya uygun bir chunk var ise isteği bu chunk ile karşılar.
2. Eğer istenilen hafıza çok büyükse mmap ile istek karşılanır.
3. Gerekli arenanın kilidi (lock) alınır ve sırasıyla şu operasyonlar yapılmaya çalışılır:
   1. Fastbin ve Smallbin geri dönüşüm stratejisi
      • Eğer fastbin içerisinde uygun bir chunk var ise onu kullan.
      • Eğer smallbin içerisinde uygun bir chunk var ise onu kullan.
   2. Ertelenen free leri bul
   3. Temel geri dönüşüm stratejilerine dön
      • Eğer aranan chunk büyük bine uyuyorsa, büyük bin içerisinde arama yap
   4. Yeni bir chunk oluştur
   5. Eğer bunların hepsi başarısız olursa NULL dön.

Free stratejiside şu şekildedir:

1. Eğer free fonksiyonuna verilen pointer NULL ise hiç bir şey yapma.
2. Pointeri metadata boyutunu çıkararak chunka dönüştür.
3. Güvenlik kontrolleri yap, eğer biri başarısız olursa işlemi sonlandır.
4. Eğer chunk tcache e uygun ise oraya yerleştir.
5. Eğer chunkın M bayrağı etkin ise munmap ile chunkı işletim sistemine iade et.
6. Heapden gerekli arenanın kilidini (lock) al.
   1. Eğer chunk bir fastbine uyuyorsa oraya yerleştir ve işlemi tamamla.
   2. Eğer chunk boyutu 64KB dan büyükse, fastbinleri birleştir ve birleştirilen chunkı unsorted bine yerleştir.
   3. Eğer chunk heapin sonunda ise chunkı heapin sonuna ekle. Bir bine yerleştirme.
   4. Aksi halde chunkı unsorted bin içerisine yerleştir.

EOF

Bu şekilde bu yazıyıda tamamlamış olduk. Sorularınız için bana twitterdan ulaşabilirsiniz. Daha sonra görüşmek üzere …

Kaynaklar:

• PART 2: UNDERSTANDING THE GLIBC HEAP IMPLEMENTATION
• Understanding glibc malloc