| Translations Blog |

Free Drawings

Rasmiy Tasdiqlash: Mukammal Kod va Haqiqat O'rtasidagi Tafovut

Tarjima qilingan maqola - Formal Verification: The Gap Between Perfect Code and Reality

Muallif(lar) - Ray Wang

Maqolaning manbasi:

https://raywang.tech/2017/12/20/Formal-Verification:-The-Gap-between-Perfect-Code-and-Reality/

2017-yil Kuzida men Turing mukofoti laureatilari Butler Lampson, Nikolay Zeldovich va Frans Kaashoek tomonidan o'qitiladigan MITning 6.826 Kompyuter tizimlari tamoyillarini o'qidim. Uning ibtidoiy nomiga qaramay, u rasman tasdiqlangan tizimlari qurish bo'yicha grad sinf bo'ldi. Coq tilidan foydalanib, biz o'yinchoq tuzilmalarining spesifikasiyalari, qo'llanmalari va dalillarini yozdik: diskda saqlangan disk, atom bloklari va takrorlanadigan disk. Bundan tashqari, biz rasmiy usullardan zamonaviy bir nechta hujjatlarni o'qiymiz.

Sinf ichiga rasmiy tekshirish kelajak — xato va xavfsizlik masalalari bilan dasturiy ta'minot ridden bir dunyo uchun yagona yechim, deb ishonib, ketdi. Ammo so'nggi voqealar va rasmiy usullarini qo'llash uchun harakat bir semestr so'ng, jiddiy bir skeptic qilyapman. Bu post, rasmiy tekshirish borish uchun uzoq yo'l bor, deb o'ylayman nima uchun va u faqat hozir ishlamaydi nima uchun muhokama olaman.

Siz albatta buni sinab ko'rishingiz kerak

Birinchidan, "rasmiy ravishda tasdiqlangan" tamg'aga qanday ega bo'lishimiz haqida gapiraylik.

Simulyatsiya dalillari

Rasmiy tasdiqlangan tizimni yozishning ikki keng usuli mavjud. Birinchi, ko'proq an'anaviy uslublar tizimning ishlash parametrlarini diqqat bilan tuzib, tizimni tatbiq qilishni va keyinchalik amalga oshirilishning spetsifikatsiyaga muvofiqligini tasdiqlovchi qo'lda yozishni o'z ichiga oladi. Bularning barchasi Coq kabi teoremning isboti tilida yozilgan va keyin OCaml yoki Haskellda bajariladigan versiyani bajarish uchun chiqariladi.

6,826 ta laboratoriya bilan shaxsiy tajribadan bu kobus.

Birinchidan, isbot yuki juda katta - FSCQ fayl sistemasi , taxminan 1,5 yil mobaynida Coq yordamida ishlab chiqilgan, butun tizim xuddi shunday tasdiqlanmagan fayl tizimidan 10x ko'proq kodni tashkil etdi .Buni tasavvur qiling - 2000 satr satrlari 20 000 qator dalilga aylang! Bu qisman Cog matematik mantiqqa asoslanish uchun juda ko'p umumiy til bo'lgani uchun va uning murakkab kompyuter tizimlari kabi ixtisoslashtirilgan ilovalar uchun juda kam o'rnatilgan mashinalar mavjud. Shunday qilib, infratuzilmani noldan yaratishimiz, shuningdek, sistemamizni yerdan yuqoriga - bitlardan va baytlardan disklarga aylantirishimiz kerak.

Laboratoriyalar o'qituvchilar tomonidan taqdim etilgan ko'pgina avtomatlashtirish va infratuzilmalar tufayli bu kulgili qiyoslash yukiga katta ta'sir ko'rsatdi. Haqiqatan ham 2700 satr Coq (LoC) liniyalari provayder infrastrukturasiga bag'ishlangan bo'lib, o'yinchoq replikatsiya qilingan disk laboratoriyasi bo'lsa, haqiqiy tizim uchun yana 1500 satr.

Bu yuklarning qaerdan paydo bo'lgan? Xullas, biz "simulyatsiya isboti" deb nomlangan narsani qo'llab-quvvatlashimiz kerak. Ushbu dalil tarzida biz tizimimizda mavjud bo'lgan har bir jarayonni ko'rib chiqamiz va bizning amalga oshirishimizdagi har bir erishish mumkin bo'lgan holat bizning spektaklimizda mos keladigan davlatga ega ekanligini ko'rsatamiz. Har bir protsedura uchun bizning specimiz uchta shartni o'z ichiga oladi: old shart , postkonditsiya va kodimiz to'satdan tushib qolsa, bu to'g'ri. Keyin bizning dalilimiz bir necha narsalarni o'z ichiga oladi:

  1. Bizning protseduramizning oldingi shartlariga amal qilishini belgilang
  2. Jarayonning har bir yo'nalishini / filialini tasdiqlash haqiqiy o'zgarishdir
  3. Jinoiy ishning oxirida hech qanday falokat yo'q bo'lsa, kechiktirishni isbotlang
  4. Amalga oshirilishdan oldin falokatlar ro'y bergan bo'lsa, har bir falokat oldida halokat holatini isbotlang, avariya holatini tiklash amaliyoti joriy o'tish hisoblanadi va postkonditsiya

Bu erda bitta kodning diagrammasi va kod holati va spetsifikatsiya holati o'rtasidagi muvofiqlikni ko'rsatib beradi. Er-xotin o'qlar bizni isbotlashimiz kerak.

FSCQ kodida 32000 dona LoCdan 6000 tasi faqatgina ushbu infratuzilmaga bag'ishlangan.

Shuni ta'kidlashni istardimki, har qanday kodli yo'lni - shartli so'zlar sonining ko'payib borayotganini isbotlashimiz kerak va u har bir nuqtada bir falokatni hisobga olgan holda ikki marta takrorlanadi. Döngüler indüktiv sifatida isbotlanishi kerak. Buning ustiga, agar spetsifik yoki dastur biroz o'zgarib ketsa, unga bog'liq bo'lgan barcha ko'zoynak, impls va dalillar ham o'zgaradi. Bu kichik o'zgarishlarni katta og'riqlarga olib keladi.FSCQ kodida 32000 donadan 6000 tasi faqatgina ushbu infratuzilmaga bag'ishlangan.

O'zingiz o'qiyotganingizdan avval, boshqa yo'l bormi?

Tugma asoslangan dalillar

Boshqa usul esa - "tugma" uslubi bo'lib, unda spetsifikatsiyalar va ilovalar davlatlarni simvolik SMT tenglamalari deb ataladi, ular masalan, Z3ga topshirilishi mumkin. Bu Z3-ni avtomatik tarzda biron-bir al-dalilni yozmasdan tizimni tekshirishga imkon beradi. Z3, masalan, har bir kod amaliyoti kod shtatlari va spetsifikatsiya o'rtasidagi munosabatni belgilaydigan formulani qondiradimi-yo'qligini tekshirishi mumkin.

Bu erda asosiy kuch-quvvat, aslida, ölçeklenebilir bir qator tekshiradigan xususiyatlar dizayni oqilona tarzda tasarlanmaktadır. Z3 uchun muammoni hal qilish mumkinmi yoki yo'qligini aniqlash qiyin, va siz uni amalga oshirish uchun har qanday fokuslarni o'ynashingiz kerak. Misol uchun, Yggdrasil yozuvchilari, bir tugmani tasdiqlangan fayl sistemasida 4 oy davomida tekshiruvlarni o'lchash usullarini, 2-3 oylik tizimini qurishgan va kamida olti oyda optimallashlarni sinab ko'rishgan. Oxir-oqibat, boshqa yirtqich fokuslar orasida, ular beshta qatlamlik abstraktsiyalarga tayanadi, shuning uchun solver faqat bir vaqtning o'zida bir qatlam haqida mulohaza yuritib, yopishmaydi.

Nima noto'g'ri ketmoqda?

Bu harakatlardan so'ng, tugmachani bosib tasdiqlash mumkin bo'lgan texnik xususiyatlarni diqqat bilan aniqlab oladimi yoki Cogda dalillarni yozib qo'yaylik, nima qilamiz? Siz mukammal kod uchun umid qilasiz, lekin haqiqat juda kam qabul qilinadi.

Rasmiy tasdiqlangan tizim kafolati butunlay tizimning taxminlariga, shu jumladan ishonchli hisoblash bazasiga (TCB) bog'liq. Tasdiqlangan tizimning TCB, qo'lda yozilgan va ishonchli (barmoqlarni kesib o'tgan) spetsifikatsiyalarni o'z ichiga oladi To'g'ri, aniqlash vositalari (masalan, Coq mexanizmi, Z3, kompilyator) va ish vaqti infratuzilmasi (OS, apparat). Bu katta qizil bayroq bo'lishi kerak. Misol uchun, agar siz Z3 dan foydalangan bo'lsangiz, siz buni ishlab chiquvchilardan tashqari barcha uchun qora sehr deb qabul qilasiz va mening professorlarim, odatda keng tarqalgan bo'lmagan to'lov qobiliyatiga oid nazariyalarda to'g'riligining xatosini topishni tan oladilar.

Ampirik tadqiqot

Biz o'qiyotgan maqolalardan biri, Rasmiy tasdiqlangan tarqatilgan tizimlarning haqiqiyligini ampirik o'rganish uchta rasmiy ravishda tasdiqlangan tarqatilgan tizimlar - ikkitasi Coq / OCaml asoslangan, uchdan biri esa Dafny / SMT asoslangan. Xulosa shunday deydi:

Kodni tekshirish va testdan o'tkazish natijasida biz ko'plab jiddiy oqibatlarga olib keladigan 16ta xato topdik, jumladan, serverlarni ishdan chiqarib yuborish, mijozlarga noto'g'ri natijalarni qaytarish va tekshiruv kafolatlarini bekor qilish. Ushbu xatolar tasdiqlangan komponentlarga tayanadigan keng miqyosli taxminlarni buzganligi sabab bo'ldi.

Boshqa jiddiy oqibatlar qatori rasmiy ravishda tasdiqlangan tizimlarda buyruqlar va ma'lumotlarni yo'qotish buyrug'i edi!

Bu xatolarning ayrimlarini, shu jumladan qaerda va qanday qilib topishganini muhokama qilmoqchiman.

Ushbu xatolarning aksariyati an'anaviy disk raskadrovka va tarmoq va fayllar tizimini chayqaltirish kabi xususiyatlar va ilovalarni statik tahlil qilish orqali aniqlandi. Ushbu xatolar odatda tasdiqlangan va tasdiqlanmagan komponentlar o'rtasidagi interfeyslarda yuzaga keldi.

Mualliflar nashriyot qatlamini , tizim chaqiruvlarini va boshqa ibtidoiylarni o'z ichiga oluvchi OS interfeysini chaqirgan. Tasdiqlangan komponentlar haqiqiy dunyo OS ni amalga oshirish modelini aniqlay olmasa, jiddiy xatolar paydo bo'ladi. Misol uchun, metakarakteriyalardan qochib qutulolmaslik yoki mumkin bo'lgan barcha syscall xato kodlarini qo'llash noto'g'ri natijalarga olib kelgan, bu buyruq in'ektsiyasi va ma'lumotlar yo'qolishiga olib keladi. Haqiqiy dunyo resurslari chegaralari, masalan, juda katta paketlar yoki tayoq tüketimi, taxminlarni sindirib, tarqatilgan tizimni qulab tushdi yoki osib qo'ydi.

Qolgan xatolar tugallanmagan yoki noto'g'ri spetsifikatsiyalar va tekshirish vositalarining o'zlari bilan bog'liq muhim masalalar tufayli yuzaga kelgan. Ayniqsa, ushbu provayderlar muvaffaqiyatsizlikka uchragan - SIGINTs, istisnolar yoki boshqa tekshiruvlar natijasida proverni tekshirish muvaffaqiyatli bo'lishi haqida xabar berishiga olib kelardi!

Go'yo u etarli emasligi kabi, rasmiy ravishda tasdiqlangan tizimlar ikkita so'nggi sarlavha bor: bir holatda halokatli xavfsizlik oqibatlari.

KRACK va CompCert

Iyul oyida katta yangilik WPA2 himoyalangan WiFi tarmoqlarida KRACK hujumi bo'ldi. Kriptografiya bo'yicha mutaxassis Matt Grin uni yaxshi xulosalaydi . WPA2 ning ikkita qismlari - 4 tomonlama ulanish va shifrlash protokoli - xavfsizlikning isboti; 4-tomonlama qo'l uzatish hatto 2005 yilda rasman tasdiqlangan! Biroq, bu ikki qism haqiqiy dunyo kodi bilan qanday aloqa o'rnatganligi haqida hech kim o'ylamagan, bu sayyorada deyarli har bir amalga oshirilishi Wi-Fi trafigining to'liq parolini va soxtalashtirilishiga olib keladigan halokatli Key Reuse hujumiga zaiflashgan.

Comprert-da, rasmiy ravishda tasdiqlangan kompilyatorda, yaqinda topilgan sintaksiz xatolikdir. Sintaksis bo'yicha mintaqada e'lon qilingan o'zgaruvchining bir xil nomdagi global o'zgaruvchiga ega bo'lgan havaskor maydonda xatolik yuzaga keldi.

CompCert gazetasida ochiq-oydin tahlil qilish bosqichi bilan bir qatorda yig'ish / bog'lanish bosqichlari tasdiqlanmagan bo'lsa-da, bu kabi xato bu rasmiy usullarning ishonchliligiga katta zarba. Albatta, siz qanday xatolar rasmiy tekshirishni qo'lga olish kerak deb o'ylaysiz.

Umid bormi?

Formal tekshirish butunlay kerak bo'lishi mumkin emas. Buning uchun joy borligiga umid qilaman va buni qo'llab-quvvatlash uchun ba'zi dalillar mavjud.

Ampirik tadqiqotda murakkab va xatolarga chidamli tarqatilgan protokollarni (Paxos, RAFT) amalga oshirishda hech qanday xato topilmadi. Bu ishonchlilikni oshirish uchun tekshirishni qo'llash mumkinligini ko'rsatadi. John Regehrning xatolarni aniqlash uchun kompilyator ishida CompCertda 10 ta boshqa kompilyatorda topilgan xato kodlari xatosi mavjud emasligi haqida xabar berilgan edi.

Lekin biz kutgan kafolatlar to'g'ri protokol, qo'l siqish yoki kompilyatorni optimallashtirishdan ko'ra kuchliroqdir. Butun tizim ishonchli bo'lishi kerak va keng tarqalgan farzandlikka olish uchun imkoni boricha minimal bo'lishi uchun dalillar zarur.

Pastki chiziq, uzoq vaqtdan beri haqiqiy, noto'g'ri dunyo bilan bo'shliqni bartaraf eta olmaydigan, ilmiy doiralarda shakllanadigan usullar bilan bog'liq.