bijou64: Hız ve Güvenliği Birleştiren Yeni Nesil Varint Kodlaması
Güvenlik alanında çalışırken performans kazanımları elde etmek nadir bir lükstür. İşte bu, Ink & Switch tarafından Subduction CRDT senkronizasyon protokolü için geliştirilen, değişken uzunluklu tam sayı (varint) kodlaması bijou64‘ün hikayesi. Bu küçük kodlama, her sayının yalnızca tek bir şekilde temsil edilmesini sağlayarak, hassas bir imza doğrulama hatasını gidermeyi amaçlıyordu. Ancak ortaya çıktı ki, daha yaygın kullanılan varint LEB128‘den birkaç kat daha hızlı çalışıyor.
Hızlı bir varint yazmak hedefimiz değildi, ancak tasarım kısıtlarımız daha az iş yapması gereken bir kodlama ortaya çıkardı.
Problem: Kanoniklik Olmadan Güvenlik Zafiyetleri
Birçok ikili protokol, genellikle küçük ancak bazen büyük olan tamsayıları kompakt bir şekilde kodlama ihtiyacı duyar. Değişken uzunluklu tamsayı kodlamaları (‘varintler’) bu sorunu çözer, ancak çoğu tasarımda kanoniklik sonradan düşünülmüştür; yani kodlamanın yapısından ziyade, çözücüdaki çalışma zamanı kontrolüyle sağlanan bir özelliktir.
En yaygın varint olduğu için burada LEB128’e biraz değineceğiz. LEB128 birçok proje için harika bir seçimdir ve bizim için uygun olmamasının nedenleri, incelediğimiz diğer formatlar için de geçerlidir. Sadece bizim kullanım durumumuza mükemmel uymadı.
LEB128, bir sayıyı 7 bitlik segmentler dizisi olarak kodlar; her baytın yüksek biti ‘daha fazla baytın takip ettiğini’ işaret eder. Bu, küçük bir sayıyı temsil ederken bile her zaman 8 bayt (64 bit) yazmaktan kaçınmanızı sağlar. Ancak burada bir sorun var: ‘0’ sayısı tek bayt olarak ‘0x00’ şeklinde kodlanabilir, ancak aynı zamanda ‘0x80 0x00’ veya ‘0x80 0x80 0x00’ şeklinde de kodlanabilir. İstediğiniz kadar ‘0x80’ dizisiyle biten bir sıfır baytı kullanarak yine ‘0’ elde edebilirsiniz. Çoğu LEB128 çözücüsü bunları sorunsuzca kabul edecektir. Bu durum sadece sıfıra özgü değildir; LEB128’deki neredeyse her sayı birden fazla şekilde temsil edilebilir.
Bu durum, sıkıştırma gibi işlemler yapmak istediğinizde imzalı veriler için sorunlara yol açar, çünkü imzalanan baytların tam olarak ne olduğunu bilmeniz gerekir. Fazladan bir ‘0x80’ farklı bir imzayla sonuçlanacaktır.
Bir sayıyı temsil etmek için yalnızca tek bir benzersiz yolunuz varsa, depolarken tüm orijinali saklamak zorunda kalmadan sayı dizilerini tekilleştirmek gibi şeyler yapabilirsiniz.
Kanonikleştirme: Ek Yük ve Güvenlik Riski
Bir çözüm, basitçe özel bir ‘kanonik’ formu uygulamaktır. Bir varint kodlarken, kanonik kodlamayı kullandığınızdan emin olmalısınız (tüm kütüphaneler bunu her zaman yapmayacaktır). Çözme sırasında ise, beklenen formatınızla eşleştiğini doğrulamalısınız. Bu ek işi yapmak zorunda kalmamak gerçekten çok hoş olurdu.
Peki Ya Sonuç?
Makul bir şekilde sorulabilir: Kim gerçekten düşmanca varintlerle ortaya çıkar? Cevap, ‘protokolünüzün iki farklı bayt dizesini aynı değer olarak karıştırmasından fayda sağlayacak herkes’tir. İmzalı bir protokol için bu, çok sayıda insan olabilir.
Varintlerle ilgili olmasa da, ders kitabı vakası ASN.1’dir (X.509 sertifikalarının, LDAP’ın ve yaygın olarak bağımlı olunan diğer birçok şeyin arkasındaki soyut sözdizimi notasyonu). Kanonikleştirme saldırıları PKCS#1 v1.5, Mozilla NSS, GnuTLS, JWT‘ler ve Bitcoin işlemlerine karşı kullanılmıştır.
Tüm bunlardaki ortak kalıp şöyledir:
- Spesifikasyon der ki: ‘kanonik kodlama X’tir; başka herhangi bir kodlama reddedilmelidir.’
- Uygulama, bunu zorlayan bir veya daha fazla ‘if’ içerir.
- Kontrol, ayrıştırıcının geri kalanından ‘ayrı olarak silinebilir’ niteliktedir. Onu kaldırmak gidiş-dönüş testlerini bozmaz; dürüstçe kodlanmış verileri kullanan testleri bozmaz; performans kıyaslamalarını bozmaz. Yalnızca, test paketinde nadiren bulunan düşmanca giriş altında bozulur.
- Kontrol unutulur, optimize edilir veya asla taşınmaz. Protokolün güvenlik özelliği sessizce bozulur. İşte bijou64’ün imkansız kılmak için tasarlandığı hata sınıfı budur. Daha fazla kontrol ekleyerek değil, önemli olanı kaldırarak ve formatı öyle bir hale getirerek, hiçbir kanoniklik kontrolü olmadan, belirli bir değer için var olan tek kodlamanın kanonik olan olması sağlanır.
(Neredeyse) Yapısal Olarak Kanonik bijou64
bijou64, her tam sayı için birden fazla kodlama olasılığını ortadan kaldırır. Tıpkı normal yazılı sayı sistemimiz gibi, her sayıyı yazmanın tam olarak tek bir yolu vardır. Bijou iki numara kullanır:
1. İlk Bayt Çift Görevli
İlk bayt 0-247 arasını normal şekilde temsil eder. ‘0x42’ alırsanız, doğrudan ‘0x42’ olarak çözülür. 248-255 arasındaki değerler farklı bir moda geçer: bunlar, ilk bayttan sonra kaç bayt bekleneceğine dair bir ‘etiket’ görevi görür ve bu baytlar sayıyı temsil eder. Bu, çözme için gerçekten harikadır, çünkü ilk baytı okur okumaz ne kadar bellek ayırmamız gerektiğini biliriz (O(1)). Buna karşılık, LEB128, devam bitinin ayarlanmamış olduğu bir bayt görene kadar bayt okumaya devam etmek zorundadır (O(n)).
2. Ofsetler
Yalnızca etiket, kanonikliği garanti etmek için yeterli değildir, ancak yolu gösterir: ikinci baytta 0-247’yi tekrarlamak yerine (‘0xF8 0x00 == 0x00’), bir sonraki baytı 248 (‘0xF8’) ile ‘ofsetleriz’. Bu, ‘0xF8 0x00 == 0xF8 == 248’ anlamına gelir, ‘0’ değil (çünkü ‘0’ zaten ‘0x00’ olarak temsil edilmiştir).
İşte 1738’in çözülmesine ilişkin örnek, etiket artı iki bayt gerektirir:
Bu uzunluktaki tüm sayılar (toplam 3 bayt, yani etiket + 2 veri baytı) 504 (‘0x1F8’) ile ofsetlenir. Her ardışık uzunluk, ofseti öngörülebilir bir düzende artırır. Şuna bir bakın:
- Toplam Uzunluk 1: Ofset 0x00
- Toplam Uzunluk 2: Ofset 0xF8
- Toplam Uzunluk 3: Ofset 0x01F8
- Toplam Uzunluk 4: Ofset 0x0101F8
- Toplam Uzunluk 5: Ofset 0x010101F8
- Toplam Uzunluk 6: Ofset 0x01010101F8
- Toplam Uzunluk 7: Ofset 0x0101010101F8
- Toplam Uzunluk 8: Ofset 0x010101010101F8
- Toplam Uzunluk 9: Ofset 0x01010101010101F8
Bu, ilk bayta dayalı bir arama tablosudur! Bir istisna var: sayılar her zaman ‘aşağı’ ofsetlendiği için, en büyük değerler (9 bayt) sınır içinde olduklarına dair manuel bir kontrol gerektirir. 9 baytlık (etiket + 8 bayt veri) yuva, ofset nedeniyle 2⁶⁴’ten daha büyük sayıları temsil edebilir, ancak bijou64 ‘u64’ü hedeflediği için, orada sınırı belirliyoruz. Bu, daha önceki kanoniklik sorunu değildir; aralıktaki her sayının hala tam olarak tek bir kodlaması vardır, sadece istemediğimiz ekstra payı kırpıyoruz. Bu nedenle etiket 255 olduğunda (en büyük olanı), çözücü değerin kesme noktasının altında olup olmadığını kontrol eder.
Performans Kıyaslamaları: Beklenmedik Hız
Bijou64 tüm bu bit karıştırma, etiket aramaları ve benzeri işlemleri yapmak zorunda. Tüm bunların bir maliyeti olmalı ve normal, sabit uzunluktaki 64 bit sayılara göre bir maliyeti var. Elbette LEB128 gibi yaygın olarak kullanılan kodlamalardan ve çok zekice tasarlanmış vu128‘den daha yavaş, değil mi? ARM (Apple M2 Pro) ve x86 (AMD Zen 5) üzerinde test ettik ve çıkan sonuçlar bizi şaşırttı.
Çözme Performansı
bijou64 oldukça hızlı çıktı! LEB128’in kanonik kontrollerindeki ek yükü dikkate almadığımızda bile, LEB128’den yaklaşık 2-10 kat daha hızlı çözme yapıyor. Küçük sayılar (tek LEB128 baytına kodlananlar) bu kıyaslamalarda yaklaşık iki kat daha hızlıdır. LEB128’i birçok bayt boyunca devam bitlerini taramaya zorlayan daha büyük sayılar ise yaklaşık 8-10 kat daha hızlıdır. Tam bir ‘u64’ dağılımında (bir kıyaslamanın olabileceği en düşmanca senaryo), bijou64 4096 değerlik bir toplu işlemi ~3 µs’de (≈0.75 ns/değer) işlerken, LEB128 ~30 µs (≈7.3 ns/değer) sürer.
Kıyaslamalarda, bijou64’ün kümülatif dağılım fonksiyonları (CDF’ler) neredeyse dikeydir; kaydedilen her toplu işlem zamanlaması medyan etrafında küçük bir bantta yer alır. LEB128’in eğrileri sağa doğru yataylaşır ve uzar, çünkü devam-bit tarama uzunluğu değere bağlıdır ve dal tahmini hiçbir zaman sabitleşme şansı bulamaz.
Tahmin edebileceğiniz gibi, bijou64 en büyük sayılar dışındaki tüm sayılar için bu ‘bedavaya’ elde ettiği kanoniklik sayesinde, ‘kanonik’ çözme yaparken fark daha da büyüktür.
Kodlama Performansı
Kodlama da genellikle daha hızlıdır, ancak bir istisna vardır: ‘küçük’ dağılımda (248 – 65,535), LEB128 yaklaşık 1.24 kat daha hızlıdır.
Kodlanmış Boyut
bijou64 her dağılım için en kompakt varint değildir. Sınır farklılıkları bir yana, bijou64 ve LEB128, gerçekçi iş yüklerinde birbirine birkaç yüzde puanı yakın tel bayt sayıları üretir.
Neden Bu Kadar Hızlı?
Geriye dönüp bakıldığında, bu mantıklı geliyor:
- Uzunluk İlk Bayttan Anlaşılır: Devam biti taraması yoktur. Çözücü kaç bayt okuyacağını hemen bilir; kodlayıcı kaç bayt yazacağını hemen bilir. LEB128’in çözücüsü, sonlandırıcıyı bulana kadar her baytın yüksek bitini taramak zorundadır. Dal tahmincileri bijou64 modeline bayılır; LEB128’inkini ise, özellikle devam zinciri uzun olan büyük değerler için sevmezler.
- Big-endian, Bitişik Yükler: Yük, ara kaydetme bitleri serpiştirilmiş 7 bitlik parçalar değil, tek, bitişik bir big-endian tamsayıdır. Modern CPU’lar tam da bunun için bayt takas talimatlarına sahiptir; derleyici okumayı tek bir yükleme + ‘bswap’ işlemine dönüştürür. LEB128’in bayt başına 7 bitlik düzeni, çözücüyü her baytı maskelemeye ve kaydırmaya zorlar.
- Öngörülebilir Dallar: Katman seçimi küçük, sabit bir eşleşmedir. Herhangi bir iş yükü için, dal tahmini neredeyse anında kararlı bir düzene oturur; dik CDF eğrilerinin gösterdiği de tam olarak budur.
- Aritmetik Ucuzdur: ‘OFFSET[katman]’ eklemek sabit bir yükleme ve bir ‘add’ (veya kodluyorsanız ‘sub’) işlemidir. Önceki bir sürümde bir ‘if’ ve bazı dallanmalar vardı, ancak aritmetik sürüm çoğu modern CPU’da sıcak yolda aslında ‘daha az’ talimat içerir.
bijou64’ü Kullanmalı mısınız?
Belki! Çoğu ilginç soruda olduğu gibi, hedeflerinize bağlıdır. Bu yepyeni bir format ve her büyük dilde olgun, iyi işlenmiş uygulamaları olan LEB128 kadar test edilmemiştir. Kıyaslamalarımız cesaret verici, ancak büyük iddialar büyük kanıt gerektirir; biz şimdiye kadar sadece üç CPU üzerinde test ettik (yayınlanan kıyaslamalarda M2 Pro ve Zen 5; denediğimiz bir Zen 3 Zen 5’e benzer görünüyor).
LEB128 ortadan kalkmayacak ve kalkmamalıdır. Ancak yeni bir format tasarlıyorsanız ve kanoniklik önemliyse (imzalar, içerik adresleme veya ‘iki uygulamanın baytlar konusunda hemfikir olması’ özelliği gibi herhangi bir durum için), yapısal olarak daha güvenli ‘ve’ test ettiğimiz her kıyaslamada daha hızlı çalışan bir alternatif var.
Kütüphane crates.io’da ‘bijou64’ olarak yayınlanmıştır, çift lisans MIT / Apache-2.0 altındadır ve spesifikasyonu CC BY-SA 4.0‘tır, eğer port etmek isterseniz. Bir Wasm/JavaScript sarmalayıcı mevcuttur ve genişlik uzantıları (‘bijou32’, ‘bijou128’) spesifikasyonun gelecek uzantılar bölümünde taslak halinde belirtilmiştir. Bir hata bulursanız veya daha ilginç bir şekilde, bijou64’ün kıyasladığımız bir şeye ‘kaybettiği’ bir iş yükü bulursanız, bunu duymaktan memnuniyet duyarız!
