O’zbekiston Respublikasi Samarqand Davlat Universiteti Raqamli texnologiyalar fakulteti Amaliy

Xavfsizlik 

Ba'zi hisoblash muhitlari steklardan ularni xavfsizlik buzilishi va hujumlarga qarshi himoyasiz holga keltirishi mumkin bo'lgan usullardan foydalanadi. Bunday muhitda ishlaydigan dasturchilar ushbu ilovalarning tuzoqlaridan qochish uchun alohida e'tibor berishlari kerak.

Masalan, ba'zi dasturlash tillari chaqirilgan protseduraga mahalliy ma'lumotlarni va protsedurani chaqiruvchiga qaytarish imkonini beruvchi bog'lovchi ma'lumotlarni saqlash uchun umumiy stekdan foydalanadi. Bu shuni anglatadiki, dastur ma'lumotlarni protsedura chaqiruvlari uchun muhim qaytish manzillarini o'z ichiga olgan bir xil stekga ko'chiradi va chiqaradi. Agar ma'lumotlar stekdagi noto'g'ri joyga ko'chirilgan bo'lsa yoki katta hajmli ma'lumotlar elementi uni o'z ichiga olish uchun etarlicha katta bo'lmagan stek joyiga ko'chirilgan bo'lsa, protsedura chaqiruvlari uchun qaytarish ma'lumotlari buzilgan bo'lishi mumkin, bu esa dasturning ishlamay qolishiga olib keladi.

Zararli tomonlar kirish uzunligini tekshirmaydigan dasturga katta hajmdagi ma'lumotlarni kiritish orqali ushbu turdagi amalga oshirishdan foydalanadigan stekni buzish hujumiga urinishi mumkin . Bunday dastur ma'lumotlarni to'liq hajmda stekdagi biror joyga nusxalashi va shu bilan uni chaqirgan protseduralar uchun qaytish manzillarini o'zgartirishi mumkin. Tajovuzkor dasturga taqdim etilishi mumkin bo'lgan ma'lum turdagi ma'lumotlarni topish uchun tajriba o'tkazishi mumkin, shunda joriy protseduraning qaytish manzili stek ichidagi (va tajovuzkor tomonidan taqdim etilgan ma'lumotlar ichida) hududga ishora qilish uchun qayta o'rnatiladi. bu o'z navbatida ruxsatsiz operatsiyalarni amalga oshiradigan ko'rsatmalarni o'z ichiga oladi.

Hujumning bu turi buferdan oshib ketish hujumining o'zgarishi bo'lib, dasturiy ta'minotdagi xavfsizlik buzilishining juda tez-tez uchraydigan manbasi hisoblanadi, chunki ba'zi eng mashhur kompilyatorlar ma'lumotlar va protsedura chaqiruvlari uchun umumiy stekdan foydalanadilar va ularning uzunligini tekshirmaydilar. ma'lumotlar elementlari. Ko'pincha dasturchilar ma'lumotlar elementlari hajmini tekshirish uchun kod yozmaydilar va katta yoki kichik o'lchamdagi ma'lumotlar stekga ko'chirilganda, xavfsizlik buzilishi sodir bo'lishi mumkin.

3. 
   ASOSIY QISM
   

1. 
   Minimal stek / Minimal navbat
   

Ushbu maqolada biz uchta muammoni ko'rib chiqamiz: birinchi navbatda biz stekni eng kichik elementni topishga imkon beradigan tarzda o'zgartiramiz keyin biz xuddi shu narsani navbat bilan qilamiz va nihoyat biz ushbu ma'lumotlar tuzilmalaridan massivdagi qat'iy uzunlikdagi barcha pastki massivlarda minimalni topish uchun foydalanamiz.

Stack modifikatsiyasi

Biz stekdagi eng kichik elementni topish mumkin bo'lgan tarzda stek ma'lumotlar strukturasini o'zgartirmoqchimiz. stekdan elementlarni qo'shish va olib tashlash uchun bir xil asimptotik xatti-harakatni saqlab, vaqt. Tezkor eslatma, stekda biz faqat bir uchida elementlarni qo'shamiz va olib tashlaymiz.

Buning uchun biz faqat elementlarni stekda saqlamaymiz, balki ularni juft-juft qilib saqlaymiz: elementning o'zi va stekdagi minimal bu elementdan boshlab va pastda.

stack
> st;

Ma'lumki, butun stekda minimalni topish faqat qiymatga qarashdan iborat stack.top().second.

Bundan tashqari, stekga yangi element qo'shish yoki o'chirish doimiy vaqt ichida amalga oshirilishi mumkinligi aniq.

Amalga oshirish:

• 
  Element qo'shish:
  
• 
  int new_min = st.empty() ? new_elem : min(new_elem, st.top().second);
  
• 
  st.push({new_elem, new_min});
  
• 
  Elementni olib tashlash:
  
• 
  int removed_element = st.top().first;
  
• 
  st.pop();
  
• 
  Minimalni topish:
  
• 
  int minimum = st.top().second;
  

Navbatni o'zgartirish (1-usul)

Endi biz navbat bilan bir xil operatsiyalarga erishmoqchimiz, ya'ni elementlarni oxirida qo'shish va ularni old tomondan olib tashlashni xohlaymiz.

Bu erda biz navbatni o'zgartirishning oddiy usulini ko'rib chiqamiz. Uning katta kamchiligi bor, chunki o'zgartirilgan navbat aslida barcha elementlarni saqlamaydi.

Asosiy g'oya - faqat minimalni aniqlash uchun kerak bo'lgan narsalarni navbatda saqlash. Ya'ni, biz navbatni kamaymaydigan tartibda ushlab turamiz (ya'ni, eng kichik qiymat boshda saqlanadi) va, albatta, hech qanday o'zboshimchalik bilan emas, haqiqiy minimal har doim navbatda bo'lishi kerak. Shunday qilib, eng kichik element har doim navbatning boshida bo'ladi. Navbatga yangi element qo'shishdan oldin "kesish" qilish kifoya: biz yangi elementdan kattaroq bo'lgan barcha keyingi elementlarni olib tashlaymiz va keyin navbatga yangi elementni qo'shamiz. Shunday qilib, biz navbat tartibini buzmaymiz, shuningdek, agar keyingi bosqichda minimal bo'lsa, joriy elementni yo'qotmaymiz. Biz olib tashlagan barcha elementlarning o'zi hech qachon minimal bo'la olmaydi, shuning uchun bu operatsiyaga ruxsat beriladi. Biz boshdan elementni chiqarmoqchi bo'lganimizda, u aslida u erda bo'lmasligi mumkin (chunki biz uni kichikroq element qo'shganda olib tashlagan edik). Shuning uchun navbatdan elementni o'chirishda biz elementning qiymatini bilishimiz kerak. Agar navbatning boshi bir xil qiymatga ega bo'lsa, biz uni xavfsiz olib tashlashimiz mumkin, aks holda biz hech narsa qilmaymiz.

Yuqoridagi operatsiyalarni amalga oshirishni ko'rib chiqing:

deque q;

• 
  Minimalni topish:
  
• 
  int minimum = q.front();
  
• 
  Element qo'shish:
  
• 
  while (!q.empty() && q.back() > new_element)
  
• 
  q.pop_back();
  
• 
  q.push_back(new_element);
  
• 
  Elementni olib tashlash:
  
• 
  if (!q.empty() && q.front() == remove_element)
  
• 
  q.pop_front();
  

Ko'rinib turibdiki, o'rtacha bu operatsiyalarning barchasi faqat oladi vaqt (chunki har bir elementni faqat bir marta surish va ochish mumkin).

Navbatni o'zgartirish (2-usul)

Bu 1-usulning modifikatsiyasi. Biz qaysi elementni olib tashlashimiz kerakligini bilmasdan elementlarni olib tashlashni xohlaymiz. Buni navbatdagi har bir element uchun indeksni saqlash orqali amalga oshirishimiz mumkin. Shuningdek, biz allaqachon qancha elementlarni qo'shganimiz va olib tashlaganimizni eslaymiz.

deque
> q;

int cnt_added = 0;

int cnt_removed = 0;

Minimalni topish:

int minimum = q.front().first;

• 
  Element qo'shish:
  
• 
  while (!q.empty() && q.back().first > new_element)
  
• 
  q.pop_back();
  
• 
  q.push_back({new_element, cnt_added});
  
• 
  cnt_added++;
  
• 
  Elementni olib tashlash:
  
• 
  if (!q.empty() && q.front().second == cnt_removed)
  
• 
  q.pop_front();
  
• 
  cnt_removed++;
  

Navbatni o'zgartirish (3-usul)

Bu erda biz minimalni topish uchun navbatni o'zgartirishning yana bir usulini ko'rib chiqamiz. Bu usulni amalga oshirish biroz murakkabroq, ammo bu safar biz barcha elementlarni saqlaymiz. Shuningdek, biz elementni uning qiymatini bilmasdan old tomondan olib tashlashimiz mumkin.

G'oya muammoni biz allaqachon hal qilgan steklar muammosiga kamaytirishdir. Shunday qilib, biz faqat ikkita stek yordamida navbatni simulyatsiya qilishni o'rganishimiz kerak.

Biz ikkita stek hosil qilamiz s1va s2. Albatta, bu stek o'zgartirilgan shaklda bo'ladi, shuning uchun biz minimalni topishimiz mumkin . Biz stekga yangi elementlar qo'shamiz s1va stekdan elementlarni olib tashlaymiz s2. Agar istalgan vaqtda stek s2bo'sh bo'lsa, biz barcha elementlarni dan s1ga o'tkazamiz s2(bu elementlarning tartibini o'zgartiradi). Nihoyat, navbatdagi minimalni topish ikkala stekning minimalini topishni o'z ichiga oladi.

Shunday qilib, biz barcha operatsiyalarni bajaramiz o'rtacha (har bir element bir marta stekga qo'shiladi s1, bir marta ga o'tkaziladi s2va bir marta dan chiqariladi s2)

Amalga oshirish:

stack
> s1, s2;

• 
  Minimalni topish:
  
• 
  if (s1.empty() || s2.empty())
  
• 
  minimum = s1.empty() ? s2.top().second : s1.top().second;
  
• 
  else
  
• 
  minimum = min(s1.top().second, s2.top().second);
  
• 
  Element qo'shish:
  
• 
  int minimum = s1.empty() ? new_element : min(new_element, s1.top().second);
  
• 
  s1.push({new_element, minimum});
  
• 
  Elementni olib tashlash:
  
• 
  if (s2.empty()) {
  
• 
  while (!s1.empty()) {
  
• 
  int element = s1.top().first;
  
• 
  s1.pop();
  
• 
  int minimum = s2.empty() ? element : min(element, s2.top().second);
  
• 
  s2.push({element, minimum});
  
• 
  }
  
• 
  }
  
• 
  int remove_element = s2.top().first;
  

s2.pop();

2.