HEAP'İ ANLAMAK Part 1

HEAP'İ ANLAMAK - GLIBC Part 1

Stack ve stack overflow gibi kavramları duymuşsunuzdur. Bu kavramlar stack belleğini ve bu bellek üzerindeki zafiyetleri tanımlar. Stack tabanlı zafiyetler "stack canaries", "read only memory", "ASLR" gibi korumalar üretilmesiyle gün geçtikçe daha zor exploit edilebilir hale geldi. Tabiki de bu korumalar geliştirilirken saldırganlarda bu teknikleri aşmak ya da bypass etmek için yeni teknikler geliştirmeye çalıştılar. Bu korumalar bazı hackerları başka bir bellek alanı olan heapa yöneltti. Heap tabanlı saldırılar geliştirerek stack ile ulaşılamayan yada ulaşılması zorlaştırılan saldırı tekniklerini hayata geçirmeye çalıştılar. Bunlardan bazıları "use after free", "double free", "heap overflow" zafiyetleridir.

Heap tabanlı saldırılar, stack tabanlı saldırılara nazaran anlaşılması ve exploit edilmesi daha zordur. Çünkü hem heap uygulaması hemde saldırı vektörü heap implemantasyonuna göre değişmektedir. Programın kullanıdığı heap programına göre, işletim sistemine göre heap algoritması değişir ve buna bağlı olarak heap üzerine uygulanmaya çalışılan saldırılar da değişir. Yani her heap implementasyonu için özel saldırı teknikleri vardır.

Heap'in çalışma mantığı platform ve implementasyon bağımlıdır ve bir çok heap implementasyonu vardır. Örneğin: Google chrome nin PartitionAlloc implementasyonu, FreeBSD de kullanılan jemalloc implementasyonundan oldukça farklıdır. Linux sistemlerdeki glibc içerisinde varsayılan olarak bulunan heap implemantosyonu ile windows içerisinde bulunan heap implementasyonundan oldukça farklıdır.

Biz bu yazı serisi boyunca glibc heap uygulamasına odaklanacağız. Bu heap uygulaması ptmalloc uygulamasından türetilmiştir (fork edilmiştir). Ptmalloc ise Dlmalloc dan türetilmiştir. Ptmalloc ve Dlmalloc da aynı şekilde birer heap implementasyonudur. Aynı şekilde Linux dağıtımlarında C/C++ programları içerisinde heapın nasıl çalıştığını inceleyeceğiz.

Heap Nedir ??

Heap programlar içerisinde istenildiği zaman hafıza taleb edilebilen, kullanım işlemi bittikten sonra tekrar işletim sistemine geri iade edilebilen hafıza alanıdır. Heap içerisinden bellek alanı talebi için malloc gibi fonksiyonlar kullanılır. Bu tür fonksiyonlar gerekli hafıza alanını ayırdıktan sonra bu hafızaya işaret eden bir pointer döndürürler. Bu işlemin tersi olan ayrılan heap alanını tekrardan sisteme iade etmek için ise free kullanılır.

Yani program çalışma süreci içerisinde hafızaya ihtiyaç duyarsa, malloc gibi bir fonksiyon ile heap yöneticisinden (heap manager) hafıza talep eder. Bu hafıza ile işi bittikten sonra ise free fonksiyonu ile heap yöneticisine iade eder.

Neden Heap

Heap dinamik olarak alınabilen ve kullanılabilen bellek alanıdır. Bazı programlar çalıştıkları zaman değişen miktarlarda belleğe ihtiyaç duyarlar. Mesela bir tarayıcı çalışırken her web sayfasında aynı bellek miktarını kullanmaz yada aynı sayfayı ziyaret ettiğinizde aynı miktarda bellek kullanmayabilir. Bazen daha az bazen daha çok bellek kullanabilir. Bu miktar programın çalışma zamanında belirlenir.

Bu tür bir durumda stack bu ihtiyacı karşılayamayacaktır. Çünkü stack sabit uzunluktaki verileri barındırır. Yani stack boyutu program her çalıştığında sabittir ve önceden belirlenmiştir. Dinamik işlemler için uygun değildir.

Kurallar

Heap dinamik bir bellek alanı olduğu için ve çalışma zamanına göre değiştiği için kullanılırken bir takım kurallara uyulması gerekir.

Programcı birtakım basit kuralları takip ettiği sürece heap yöneticisi, heap alanlarının birbirlerini etkilemediğinden ve bozmadığından emin olur. Bu özellik sayesinde heap performanslı ve çok kullanışlı bir hafıza alanı olarak karşımıza çıkar.

Aşağıdaki kurallar heap kullanan her programcının kesinlikle uyması gereken kuralları listeler. Aksi takdirde heap tabanlı zafiyetler meydana gelecektir. Bu zafiyetlere daha sonradan değineceğiz. Şimdi kuralları şu şekilde listeleyelim.

1. Heap yöneticisi ile aldığınız hafıza pointerini free fonksiyonu ile iade ettikten sonra tekrardan kullanmaya çalışmayın.
   • Aksi taktirde use after free zafiyeti ortaya çıkar.
2. Ayrılan hafıza alanından daha fazla veri okumaya yada yazmaya çalışmayın.
   • Aksi taktirde heap overflow ve read beyond bounds gibi zafiyetler ortaya çıkacaktır.
3. malloc ile aldığınız hafızayı gösteren pointeri 1 defadan fazla free fonksiyonunda kullanmayın.
   • Aksi taktirde double free zafiyeti ortaya çıkar.
4. Ayrılan hafıza alanından daha öncesinde okumaya ya da yazmaya çalışmayın.
   • Aksi taktirde heap overflow zafiyeti ortaya çıkar.
5. malloc fonksiyonu ile elde edilmeyen hiç bir pointeri free fonksiyonuna sokmayın.
   • Aksi taktirde invalid free zafiyeti ortaya çıkar.
6. malloc ile dönen pointerin NULL değerine eşit olup olmadığını kontrol etmeden kullanmayın.
   • Aksi taktirde arbitrary write zafiyeti ortaya çıkar.

Elbette malloc C ve C++ programcılarının heap ile iletişim için kullandığı tek yol değildir. C++ programcıları new yada new[] operatörleri ile hafıza ayırmayı da tercih edebilirler. Aynı şekide delete veya delete[] ile ayrılan bellek alanı heap yöneticisine iade edilebilir. Aynı şekilde malloc gibi çalışan realloc, calloc memalign gibi fonksiyonlar da kullanılabilir. Bu fonksiyonlar ile alınan hafıza alanları heap ile iade edilebilir.

Basit olması açısından bu yazı boyunca heap malloc ve free üzerinden anlatılacaktır. Bir defa bu iki fonksiyonu anladığınız zaman diğer fonksiyonlar da size oldukça kolay gelecektir.

Chunk ve Chunk Ayırma Stratejileri

Bir programcının program içerisinde hafızaya ihtiyacı olduğunu düşünelim. Varsayalım ki programcının ihtiyacı 10 byte. Bu hafızayı malloc ile heap yöneticisinden isteyebilir. Bu isteği karşılayabilmesi için heap yöneticisinin 10 byte'tan daha fazla hafıza alanına ihtiyacı vardır. Heap yöneticisi ayrılmak istenen bu hafıza alanı ile ilgili üstbilgi (metadata) bilgisi tutması gerekir. Bu üst bilgi ayrılmak istenen 10 byte'ın hemen yanında tutulur.

Heap yöneticisi aynı zamanda ayrılan hafıza alanının 32 bit sistemlerde 8 byte ve katları, 64 bit sistemlerde 16 byte ve katları olduğundanda emin olmalıdır. Ayrılan hafızanın hizası eğer programcı sadece basit bit text yada array saklamak istiyorsa önemli değildir. Fakat programcı komplex bir veri saklamak istiyorsa, hizalama performans ve verinin doğruluğu açısından önemli etkilere sahip olabilir. malloc programcının ayrılan alanda ne saklamak istediğini bilemez. Bundan dolayı heap yöneticisi default olarak hafızanın hizalı olduğundan emin olmalıdır.

Ayrılan hafıza için kullanılan metadata ve 8 byte hizalama için kullanılan padding ayrılan hafıza ile birlikte tutulur. Bu yüzden, heap yöneticisi ayrılan alanı "chunk" denilen hafıza alanı olarak tanımlar ve bu hafıza alanı programcının istediği hafızadan biraz daha fazladır. Bir programcı 10 byte heap alanı ayırmak istediğinde heap yöneticisi 10 byte alan, bu ayrılan alan için metadata ve 8 byte hizalama için padding alanını hesaplar ve hepsinin tutulabileceği bir hafıza alanı ayırır. Daha sonra heap yöneticisi bu "chunk" alanını ayrıldı/kullanımda olarak işaretler ve ardından programcıya 10 byte alan için pointer geri döner. Bütün bu işlemlerin sonucunda programcı sadece malloc fonksiyonundan dönen pointeri görür.

Chunk Ayırma

Heap yöneticisi kendi içinde chunkları nasıl ayırır?

Öncelikle heap yöneticisinin chunkları nasıl ayırdığına bakacağız. Küçük boyuttaki chunkların nasıl ayrıldığını şu şekilde özetleyebiliriz.

1. Eğer daha önceden free ile sisteme (heap yöneticisine) iade edilmiş chunk var ise ve bu chunk yeni gelen isteği karşılayacak kadar büyükse, heap yöneticisi bu chunkı yeni gelen isteği karşılamak için kullanır.
2. Aksi taktirde, eğer heapin en üstünde yeterli alan var ise heap yöneticisi yeni gelen isteği karşılamak için bu alanı kullanır.
3. Eğer bu da işe yaramazsa heap yöneticisi kernelden (işletim sisteminden) heapin sonuna eklemek üzere hafıza ister ve isteği bu yeni gelen hafızadan karşılar.
4. Eğer bütün bu işlemler başarısızlıkla sonuçlanırsa heap yöneticisi isteği kerşılayamaz ve malloc NULL döner.

Temel olarak heap yöneticisi bu listelenen yöntemler ile isteği karşılamaya çalışır. Şimdi bu maddeleri daha detaylı olarak inceleyelim.

Free Edilmiş Chunkdan Hafıza Ayırma

Heap yöneticisinin gelen bir isteği karşılamak için kullandığı ilk yöntem daha önceden free edilmiş chunkı kullanmaktır.

Daha önceden free edilmiş bir chunk tan chunk ayırmak oldukça kolaydır. Free fonksiyonu ile heap yöneticisine iade edilen chunklar liste veri yapıları kullanılarak "bins" isminde listelerde tutulur. Her ne zaman allocation isteği geldiği zaman heap yöneticisi bu bins ler içerisinde isteği karşılayacak büyüklükte bir chunk arar. Eğer bir tane bulursa bin (yani liste) içerisinden o chunkı siler, ayrıldı olarak işaretler, kullanıcı datasını saklayacağı alan için bir pointer döndürür.

Performans sebebiyle farklı türlerde bin ler vardır. Bunlar: "fast bins", "unsorted bins", "small bins", "large bins" ve "per-thread tcache". Bunların ne olduğunu daha sonra ayrıntılı olarak konuşacağız. O yüzden şimdilik geçiyorum.

Heapin En Yukarısından Ayırmak

Eğer gelen isteği karşılayabilecek daha önceden free edilmiş bir chunk yoksa, heap yöneticisi yeni bir chunk oluşturur. Bunu yapmak için heap yöneticisi heap üzerinde yeterli yer olup olmadığını öğrenmek için heapin sonuna bakar. Eğer yeterli yer var ise yeni bir chunk oluşturur.

Kernelden Hafıza Alarak Heape Eklemek

Heap alanı içerisinde boş alan kalmadığı taktirde, heap yöneticisi kernelden heapin sonuna eklenmek üzere hafıza talep eder.

Eğer istenen hafıza kernel tarafından alınabilirse heap yöneticisi yeni gelen hafıza ile chunk oluşturur. Eğer kernelden (yada işletim sisteminden) hafıza talebi olumlu sonuçlanmaz ise chunk oluşturulamaz ve malloc NULL döner.

Heap ilk defa oluşturulurken, heap yöneticisi sbrk ile heap alanına fazladan hafıza ekler. Bu işlem çoğu linux tabanlı sistemde brk sistem çağrısıyla yapılır. Bu sistem çağrısının isminden yaptığı işi anlamak biraz karışıktır çünkü açılımı "change the program break location" anlamına gelir. Bu ise "bu alanın sonuna hafıza ekle" nin daha karışık şekilde söylenişidir. Program çalıştırıldığında ilk heap alanı oluşturulurken heap alanının sonuna fazladan hafıza eklenir.

Heape devamlı olarak sbrk ile hafıza eklemek eninde sonunda başarısız olacaktır. Çünkü işlem (process) içerisindeki diğer hafıza alanları ile çakışma ihtimali oluşacaktır. Bu hafıza alanı paylaşımlı kütüphaneler yada stack olabilir. Böyle bir durum meydana gelmesi durumunda heap yöneticisi işlem içerisindeki hafıza alanlarını mmap ile tekrardan hizalamaya çalışacaktır.

Eğer mmap de başarısız olursa istek karşılanamaz ve malloc NULL döner.

MMAP İle Off-Heap Allocation

Büyük hafıza talepleri heap yöneticisi tarafından özel bir durum ile değerlendirilir. Bu durumda heap yöneticisi mmap sistem çağrısı ile doğrudan kernelden hafıza talep eder. Bu durum chunk metadatasından bir flagin işaretlenmesi ile saklanır. Daha sonrasında free ile heap yöneticisine iade edilirse, heap yöneticisi munmap sistem çağrısı ile bu hafızayı doğrudan kernele iade eder.

Varsayılan olarak bu büyük hafıza miktarı 32 bit sistemlerde 128 ile 512 KB arasında, 64 bit sistemlerde ise 32 MB dır. Eğer heap yöneticisi bu tarz büyük hafıza miktarlarının sıklıkla kullanıldığını saptarsa treshold miktarını arttırabilir.

Arenalar

Çok thread ile çalışan programlarda heap yöneticisi, race condition gibi durumları kontrol etmelidir. Aksi taktirde program çalışma esnasında hata üretip çökebilir. ptmalloc2 den önce heap yöneticisi global bir mutex yapısı kullanarak heap ile sadece bir threadin iletişimine izin veriyordu.

Bu yöntem çalışmasına rağmen çok fazla sayıda thread kullanan programlarda ciddi bir performans sorununa yol açacaktır. Bu duruma çözüm olması için ptmalloc2 "arena" isminde yeni bir konsept ortaya çıkardı. Her bir "arena" temel olarak kendisine ait heape sahiptir. Bu heap ile chunkları ve binleri kendi içerisinde yönetir. Diğer arenalar bundan etkilenmez. Her bir arenanın kendine ait bir mutexi vardır. Bu sayede her bir thread farklı arenalar üzerinde işlem yaptığı sürece birbirlerini etkilemezler.

Program çalıştığında ilk oluşturulan heap (main) arena olarak adlandırılır. Tek thread ile çalışan programlarda sadece main arena kullanılır. Eğer yeni bir thread oluşturulursa heap yöneticisi bu thread için bir arena oluşturur. Bu sayede malloc ve free gibi heap işlemlerinde threadler birbirlerini bekletmemiş olur.

Programa yeni bir thread katıldığında, heap yöneticisi başka bir threadin kullanmadığı bir arena bulmaya çalışır. Eğer bulursa thread ile arenayı ilişkilendirir. Eğer bütün arenalar doluysa heap yöneticisi yeni bir arena oluşturmaya çalışır. Max arena sayısı 32 bit tabanlı sistemlerde cpu-core sayısının 2 katı, 64 bit tabanlı sistemlerde ise cpu-core sayısının 8 katıdır. Eğer bu limite ulaşılırsa heap yöneticisi yeni arena oluşturmayı bırakır ve yeni oluşturulan threadlerin varolan arenaları paylaşması gerekir. Bu durumda ise heap işlemleri sırasında her arena için mutex ile race condition kontrolü yapılır ve bir heap işlemi bitmeden devam ederken diğer threadler beklemek zorunda kalır.

Peki bu sonradan oluşturulan arenalar nasıl çalışır? Program ilk defa belleğe yüklendiği zaman ilk heap alanı oluşturuluyordu ve brk sistem çağrısı ile hafıza ekleniyordu. Fakat bu durum sonradan oluşturulan arenalar için geçerli olmayacak. Bu durumda mmap ve mprotect sistem çağrıları kullanılarak ilk oluşturulan heap gibi "subheap" denilen heap alanları oluşturacaktır.

SUBHEAPS

Subheaps main heap ile çoğu durumda aynı şekilde çalışır fakat temelde 2 farkı vardır. Program ram e yüklendikten hemen sonra ilk heap alanının oluşturulduğunu hatırlayın. Main heapin aksine, subheap ler belleğer mmap kullanılarak yerleştirilir ve heap yöneticisi mprotect kullanarak bu subheap alanının korunmasını sağlar.

Her ne zaman heap yöneticisi subheap oluşturmak istediği zaman öncelikle kernelden subheapin içinde mmap ile büyüyebileceği bir miktar bellek alanı alır. Aslında bu çağrı ile doğrudan bellek alanı ayrılmaz. Bu çağrı ile bu alanın başka işlemlerde kullanılmaması gerektiğini kernele bildirir.

Bu ayrılan alan içerisinde subheap gerekli sistem çağrıları ile büyüyebilir. Eğer mmap ile ayrılan alan tükenirse heap yöneticisi yeni bir subheap oluşturur. Bu sayede subheaplar processin adres alanı bitmediği sürece ve kernelden hafıza talebi karşılandığı sürece istenildiği kadar büyüyebilir.

Chunk Metadata

Artık bir chunkın nasıl allocate edildiğini biliyoruz. Ve chunk üzerinde sadece kullanıcı verisi için alan bulunmadığını aynı zamanda o chunk için metadata bilgisininde bulunduğunu biliyoruz.

Chunk metadatası heap yöneticisinin kendi iç sisteminde kullandığı bir alandır. Bir programcının özel bir sebebi olmadığı müddetçe bu alanlarla ilgilenmez. Heap yöneticisi chunk ve heap işlemlerini yönetirken bu metadata bilgisine bakar. Mesela bir chunkın boyutunu, chunkın kullanımda olup olmadığı bilgisini, bu chunktan önceki chunkın boyutunu ve daha fazla bilgiyi bu metadata içerisinde saklar. Bu yüzden chunk metadatası heap işlemleri için kritik öneme sahiptir.

Bir chunka ait metadata alanı biraz kafa karıştırıcı olablir. Chunka ait bazı metadata alanları sadece bazı durumlar için kullanılıyor olabilir, bazı heap implemantasyonlarında chunkın başında, bazılarında ise sonunda bulunabilir.

size_t değeri, 32 bit sistemde 4 byte tam sayı ve 64 bit sistemde 8 byte tam sayıdır.

chunk_size alanı 4 bilgiyi taşır. Bunlar chunk boyutu, A M P isminde 3 bit. Bütün bu bilgiler chunk_size alanında saklanır. Çünkü chunk boyutu her zaman 8 byte ve katlarıdır (8 byte aligned). 64 bit sistemlerde ise bu 16 bytetır. Bu yüzden chunk_size alanının son 3 bitlik alanı chunk boyutu için kullanılmaz.

A bayrağı chunkın ilk arenaya değil de, ikincil yani sonradan oluşturulan bir arenaya ait olduğunu belirtir. Bir chunk free işlemine girdiği zaman heap yöneticisi chunkın hangi arenaya ait olduğunu anlamaya çalışır. Eğer bu bayrak işaretlenmişse heap yöneticisi bütün arenaları arayarak chunkın hangi arenaya ait olduğunu bulmaya çalışır. Eğer bu bayrak set edilmemişse heap yöneticisi bu chunkın program çalıştırıldığında oluşturulan ilk arenaya (initial arena) ait olduğunu anlar.

M bayrağı bu chunkın büyük olduğunu ve mmap ile alındığını (allocate) belirtir. Daha sonradan bu chunk free fonksiyonuna sokulduğunda heap yöneticisi bu chunkı munmap ile doğrudan işletim sistemine iade eder.

P bayrağı bir önceki chunka ait bilgiyi taşır. Bu yüzden biraz kafa karıştırıcı olabilir. Bu bayrak bir önceki chunkın free olduğunu belirtir. Eğer bu chunk free işlemine tabi tutulursa bir önceki chunk ile birleştirilerek daha büyük chunklar oluşturulabilir.

EOF

Şimdilik bu kadar. Bir sonraki yazımda daha detaya girerek devam edeceğim. Eğer daha fazla okuyacak bir şeyler arıyorsanız şu linkleri inceleyebilirsiniz:

• Once upon a free()
• Arm Heap Exploitation PART 1: UNDERSTANDING THE GLIBC HEAP IMPLEMENTATION
• Understanding glibc malloc