——————————————————————————-

پیچیدگی محاسباتی یا همون Computational Complexity یکی از مهم ترین مسائل توی علوم کامپیوتره
با استفاده از پیچیدگی محاسباتی میتونیم میزان منابع مورد نیاز برای حل مسائل رو تخمین بزنیم.
منظور از منابع زمان و فضا(حافظه) هستش...

ما برای نشون دادن پیچیدگی محاسباتی هر الگوریتم از نماد های Asymptotic Notation یا O/Ω/Θ استفاده میکنیم.

حالا اینا چین؟
نماد O(f(n)) کران بالای رشد الگوریتمو نشون میده ، یعنی حداکثر منابعی که ممکنه مصرف بشه. معمولاً ازش برای نشون دادن بدترین حالت ممکن استفاده میکنیم...
نماد Ω(f(n)) کران پایین رو نشون میده ، یعنی حداقل منابعی که الگوریتم در هر حال باید مصرف کنه. معمولاً برای بهترین حالت ممکن استفاده میشه.
نماد Θ(f(n)) کران دقیق الگوریتم رو نشون میده. زمانی به کار میاد که هم کران بالا و هم کران پایین یکی باشن (یا تقریبا اندازه همدیگه باشن)

خلاصه کران بالا (بدترین حالت ممکن) رو با او (O) ، کران پایین (بهترین حالت ممکن) رو با امگا (Ω) و حالت کران دقیق(متوسط) رو با تتا (Θ) نشون میدیم

خب حالا چطوری کار میکنن؟
برای بهتر متوجه شدنتون ی کد پایتون نوشتم که سعی میکنه توی ی لیست ، ی عددی که ما بهش میدیم رو پیدا کنه :

def search(lst, num):
    for i in range(len(lst)):
        if lst[i] == num:
            return i
    return -1

این فانکشن لیست و عددی که باید دنبالش بگرده رو از ما میگیره و یکی یکی اعداد رو از اول لیست پیمایش میکنه تا به عددی که بهش دادیم برسه.
حالا کد زیر رو در نظر بگیرید :

search([1, 2, 3, 4, 5], 10)

خب اینجا توی لیستی که بهش دادیم عدد 10 وجود نداره و مجبوره تا اخر لیست رو پیمایش کنیم ، پس کران بالای رشد این الگوریتمو با O(n) نشون میدیم ، یعنی در بدترین حالت ممکن این الگوریتم باید کل لیست رو طی کنه تا به عدد مد نظر برسه

حالا کد زیر رو در نظر بگیرید :

search([1, 2, 3, 4, 5], 1)

اینجا اولین عدد رو بررسی میکنه و میبینه همون عددیه که دنبالشه ، پس دیگه نیازی نیست تا آخر لیست رو پیمایش بکنه
کران پایین این الگوریتمو میتونیم با Ω(1) نشون بدیم ، یعنی این الگوریتم در بهترین حالت ممکن با یک بار اجرا شدن به عدد میرسه

و در آخر تتا...
واسه تتا میتونیم ی همچین مثالی بزنیم :

search([3, 7, 12, 15, 18, 22], 15)

اینجا بطور میانگین الگوریتم ما نصف لیستو پیمایش کرده تا تونسته به 15 برسه ، اگه فرض کنیم که داده ها در موقعیت های مختلفی از لیست بطور یکنواخت قرار گرفتن اونوقت میانگین زمان اجرا تقریباً Θ(n) میشه...

پس توی مثالای بالا Ω(1) یعنی عدد اولین عنصر لیست بوده ، O(n) یعنی آخر لیست بوده یا اصلا وجود نداشته و Θ(n) یعنی عدد ما ی جاهایی از وسطای لیست بوده

حالا شما کران پایین و کران بالای الگوریتم زیر رو تو کامنتا بهم بگید و دلیلشو برام بنویسید :

def getFirstElement(lst: list):
    if isinstance(lst, list) and len(lst):
        return lst[0]

——————————————————————————-

🤔 واقعا پیچیدگی زمانی switch/case برابر با O(1) یا نه؟
این همیشه واسه من سوال بوده که چطوری switch/case میاد این کار رو میکنه ، مگه نباید مقایسه انجام بشه؟
بخاطر همین از روی کنجکاوی رفتم سراغ بررسی کردن کدای Assembly 🗿😂
اومدم همچین کدی نوشتم :

#include <stdio.h>

int main() {
    int x = 5;

    switch (x) {
        case 0: printf("its 0"); break;
        case 1: printf("its 1"); break;
        case 2: printf("its 2"); break;
        case 3: printf("its 3"); break;
        case 4: printf("its 4"); break;
        case 5: printf("its 5"); break;
        case 6: printf("its 6"); break;
        case 7: printf("its 7"); break;
        case 8: printf("its 8"); break;
        case 9: printf("its 9"); break;
        default: printf("default case"); break;
    }

    return 0;
}

کدی که با C زده بودم رو کامپایل کردم و با GDB فانکشن main رو disassemble کردم و خروجی زیر رو گرفتم :

   0x0000000140001450 <+0>:     push   %rbp
   0x0000000140001451 <+1>:     mov    %rsp,%rbp
   0x0000000140001454 <+4>:     sub    $0x30,%rsp
   0x0000000140001458 <+8>:     call   0x140001610 <__main>
   0x000000014000145d <+13>:    movl   $0x5,-0x4(%rbp)
   0x0000000140001464 <+20>:    cmpl   $0x9,-0x4(%rbp)
   0x0000000140001468 <+24>:    ja     0x140001544 <main+244>
   0x000000014000146e <+30>:    mov    -0x4(%rbp),%eax
   0x0000000140001471 <+33>:    lea    0x0(,%rax,4),%rdx
   0x0000000140001479 <+41>:    lea    0x2bcc(%rip),%rax        # 0x14000404c
   0x0000000140001480 <+48>:    mov    (%rdx,%rax,1),%eax
   0x0000000140001483 <+51>:    cltq
   0x0000000140001485 <+53>:    lea    0x2bc0(%rip),%rdx        # 0x14000404c
   0x000000014000148c <+60>:    add    %rdx,%rax
   0x000000014000148f <+63>:    jmp    *%rax
   0x0000000140001491 <+65>:    lea    0x2b68(%rip),%rax        # 0x140004000
   0x0000000140001498 <+72>:    mov    %rax,%rcx
   0x000000014000149b <+75>:    call   0x140002640 <printf>
   0x00000001400014a0 <+80>:    jmp    0x140001554 <main+260>
   0x00000001400014a5 <+85>:    lea    0x2b5a(%rip),%rax        # 0x140004006
   0x00000001400014ac <+92>:    mov    %rax,%rcx
   0x00000001400014af <+95>:    call   0x140002640 <printf>
   0x00000001400014b4 <+100>:   jmp    0x140001554 <main+260>
   0x00000001400014b9 <+105>:   lea    0x2b4c(%rip),%rax        # 0x14000400c
   0x00000001400014c0 <+112>:   mov    %rax,%rcx
   0x00000001400014c3 <+115>:   call   0x140002640 <printf>
   0x00000001400014c8 <+120>:   jmp    0x140001554 <main+260>
   0x00000001400014cd <+125>:   lea    0x2b3e(%rip),%rax        # 0x140004012
   0x00000001400014d4 <+132>:   mov    %rax,%rcx
   0x00000001400014d7 <+135>:   call   0x140002640 <printf>
   0x00000001400014dc <+140>:   jmp    0x140001554 <main+260>
   0x00000001400014de <+142>:   lea    0x2b33(%rip),%rax        # 0x140004018
   0x00000001400014e5 <+149>:   mov    %rax,%rcx
   0x00000001400014e8 <+152>:   call   0x140002640 <printf>
   0x00000001400014ed <+157>:   jmp    0x140001554 <main+260>
   0x00000001400014ef <+159>:   lea    0x2b28(%rip),%rax        # 0x14000401e
   0x00000001400014f6 <+166>:   mov    %rax,%rcx
   0x00000001400014f9 <+169>:   call   0x140002640 <printf>
   0x00000001400014fe <+174>:   jmp    0x140001554 <main+260>
   0x0000000140001500 <+176>:   lea    0x2b1d(%rip),%rax        # 0x140004024
   0x0000000140001507 <+183>:   mov    %rax,%rcx
   0x000000014000150a <+186>:   call   0x140002640 <printf>
   0x000000014000150f <+191>:   jmp    0x140001554 <main+260>
   0x0000000140001511 <+193>:   lea    0x2b12(%rip),%rax        # 0x14000402a
   0x0000000140001518 <+200>:   mov    %rax,%rcx
   0x000000014000151b <+203>:   call   0x140002640 <printf>
   0x0000000140001520 <+208>:   jmp    0x140001554 <main+260>
   0x0000000140001522 <+210>:   lea    0x2b07(%rip),%rax        # 0x140004030
   0x0000000140001529 <+217>:   mov    %rax,%rcx
   0x000000014000152c <+220>:   call   0x140002640 <printf>
   0x0000000140001531 <+225>:   jmp    0x140001554 <main+260>
   0x0000000140001533 <+227>:   lea    0x2afc(%rip),%rax        # 0x140004036
   0x000000014000153a <+234>:   mov    %rax,%rcx
   0x000000014000153d <+237>:   call   0x140002640 <printf>
   0x0000000140001542 <+242>:   jmp    0x140001554 <main+260>
   0x0000000140001544 <+244>:   lea    0x2af1(%rip),%rax        # 0x14000403c
   0x000000014000154b <+251>:   mov    %rax,%rcx
   0x000000014000154e <+254>:   call   0x140002640 <printf>
   0x0000000140001553 <+259>:   nop
   0x0000000140001554 <+260>:   mov    $0x0,%eax
   0x0000000140001559 <+265>:   add    $0x30,%rsp
   0x000000014000155d <+269>:   pop    %rbp
   0x000000014000155e <+270>:   ret

توی پستای بعدی تیکه تیکه کد اسمبلی بالا رو کوت میکنم و توضیحش میدم واستون تا براتون جا بیوفته دقیقا چطوری این اتفاق داره میوفته.
الگوریتمش که واسه من خیلی جالب بود...

این قسمت رو نادیده بگیرید واسه تنظیمات استک و... اس که به ما ربطی ندارن😁

این قسمت داره همون متغیرمون رو سیو میکنه
توی کد سی گفته بودیم که :

int x = 5;

اینجا داره همون x رو تعریف میکنه...
دستور movl توی اسمبلی واسه انتقال ی مقدار استفاده میشه که سینتکسش به این شکل هستش :
movl x, y
اینجا مثلا مقدار x رو داریم به y منتقل میکنیم ، اون l آخر این دستور به معنی long هستش و به این معنیه که این دستور 4 بایت دیتا رو منتقل میکنه...

حالا اینجا کدی که ما داریم گفته
movl $0x5, -0x4(%rbp)

اینجا داره 0x5 یا همون 5 دهدهی رو به آدرس -0x4(%rbp) منتقل میکنه.

اینجا توی خط اول داره مقدار عددی که توی متغیر x هست رو با 0x9یا همون 9 دهدهی مقایسه میکنه
خط بعدی اومده گفته که اگه 9 < x بود به انتهای تابع بپر...
دستور ja یعنی jump if above ، موقعی پرش انجام میشه که مقایسه ای که انجام شده نشون بده ی مقدار بزرگتر از ی مقدار دیگس ، پس اگه x از 9 بزرگتر باشه کد یهو میپره به آخر تابع و بقیه کدای دیگه رو درنظر نمیگیره...

اینجا داره switch/case ای که نوشتیم رو پردازش میکنه ، این قسمت رو توی پستای بعدی بیشتر شرح میدم ، اول میخوام تقسیم بندی هارو انجام بدم واسه هر بخش تا بعد برگردم روی این قسمت و جزئی تر بهش بپردازیم ;)

اینجا داره آدرس ی رشته(string) خاص رو توی %rax میزاره و اونو به %rcx میده تا تابع printf اونو پرینت کنه و بعدش پرش میزنه به آخر تابع

دقیق تر بخوام بگم دستور lea مخفف Load Effective Address هستش ، اینجا مقدار
%rip + 0x2b68
داره محاسبه میشه و داخل رجیستر rax ریخته میشه ، پس توی رجیستر rax الآن ما ی رشته رو داریم ، کدوم رشته؟ ما توی کد C که زده بودیم توی هر case اومدیم ی مقدار رو پرینت کردیم ، مثلا واسه case 1 اومدیم گفتیم مقدار its 1 رو پرینت کن ، حالا ما استرینگ "its 1" رو توی رجیستر rax داریم...
توی خط بعدی اومده مقداری که توی رجیستر rax هستش رو با دستور mov به رجیستر rcx منتقل کرده
اینجا چونکه من توی ویندوز کد C رو کامپایل کردم داره این مقدارو توی رجیستر rcx میریزه چونکه توی ABI استاندارد ویندوز اولین آرگومان تابع توی رجیستر rcx قرار میگیره... ولی رو لینوکس توی رجیستر rdi قرار میگیره
بعدش داره با دستور call تابع printf رو فراخوانی میکنه ، حالا فهمیدین چرا مقدار رشته رو از rax ریخته توی rcx؟ :)
چون الآن اولین مقدار آرگومانی که داره به printf داده میشه همون رجیستر rcx هستش ، مثل اینه که گفته باشیم printf(rcx)
خلاصه اینجا داریم ی رشته رو پرینت میکنیم
توی لاین بعدی هم که پریدیم به آخر تابع...

و بعدش هم که دوباره و دوباره و دوباره دقیقا همون کار رو انجام داده (ی رشته رو لود کرده داده به printf تا برامون پرینتش کنه)
اینا همون کدای بدنه case هاییه که نوشتیم
ولی فقط یکی از اینا قراره اجرا بشه...

به تعریف بلوک case ها ادامه میده تا میرسه به این قسمت...
این قسمت واسه خروج از تابع هستش که داره فضای stack رو آزاد میکنه و... که اینم به ما مربوط نمیشه و زیاد توضیحش نمیدم

خب بریم واسه توضیح این بخش ، خیلی حاشیه رفتیم دیگه وقتشه بریم سر اصل موضوع😁

بیاید ی دور خط به خط دقیقا این بخش که داره switch/case مارو اجرا میکنه رو بررسی کنیم
خط اول کد mov -0x4(%rbp),%eax رو اجرا میکنه ، یعنی چی؟
داره مقدار متغیر x رو میریزه توی eax

خط دوم کد lea 0x0(,%rax,4),%rdx رو اجرا میکنه ، داره مقدار rdx رو ضرب در 4 میکنه
چرا 4؟ چونکه آدرسا توی jump table یا همون جدول پرش 4 بایتی هستن...
جدول پرش بصورت ی آرایه از int32 یا int معمولیه که هر خونش یه offset به کد مربوطه(همون بلوک case هایی که نوشتیم) داره
یعنی مثلا جدولمون به این شکله :

jump_table = {
  offset_to_case0,   // x = 0
  offset_to_case1,   // x = 1
  offset_to_case2,   // ...
  offset_to_case5,   //  x = 5
  ...
}

خط سوم داره کد lea 0x2bcc(%rip),%rax رو اجرا میکنه ، به زبون ساده بخوام بگم داره آدرس پایه اون jump table رو میده به rax
خط چهارم کد mov (%rdx,%rax,1),%eax رو اجرا میکنه ، یعنی از آدرس rax + rdx مقدار 4 بایتی رو بخون و بریز توی eax :)
اینجا جایی بود که من جواب سوالمو گرفتم...
الگوریتمشو میتونم به چیزی مثل این کد تشبیه کنم :

eax = jump_table[x]

یعنی داره مقدار بلوک case مورد نظر رو محاسبه میکنه و از jump table ای که داریم میگیره و میریزتش توی eax ، اینجا مقایسه ای انجام نشده ، فقط ی سری محاسبات انجام شده...
مثلا :

jump_table[5] = 0x00000080;

یعنی case 5 فاصلش از بیس 128 بایته

احساس میکنم یکم گیج شدین با این توضیحات... بزارید ی بار دیگه با مثال بهتر بهتون توضیحش بدم چون تمام این مسئله به درک همین ی خط کد وابستس
ما ی همچین کدی رو داریم :
mov (%rdx,%rax,1), %eax
میخوایم بفهمیم داره چیکار میکنه؟
اول از همه بگم که این کد به زبان ساده داره میگه که برو به آدرسی که برابر با rdx + rax * 1 هست و مقدار 4 بایتی که اونجا هست رو بخون و بریز توی eax
ولی چرا rax و rdx؟
برای درک بهتر باید خطای قبلش هم بررسی کنیم که بهتون توضیح دادم خطای قبل چیکار میکنن...
پس آدرس offset توی جدول (چون هر entry توی جدول 4 بایته) برابره با : rdx = x * 4
الآن ما توی rdx مقدار offset رو داریم و توی rax مقدار base رو
پس این خط کدی که داریم یعنی برو به آدرس base + x * 4 یا همون rax + rdx و مقدار 4 بایتی که اونجاست (یعنی offset مقصد case مربوطه) رو بریز تو eax.

با اعداد واستون مثال میزنم تا خوب متوجه بشید :
توی کد C که نوشته بودیم مقدار متغیر x برابر بود با 5 پس اینجا داریم x = 5
حالا فرض کنیم که jump table از آدرس 0x140004054 شروع میشه که این همون rax ما هستش
پس :
x * 4 = 20
چونکه هر ورودی 4 بایته اومدیم مقدار x رو در 4 ضرب کردیم...
حالا بیایم محاسبش کنیم
مقدار بیس جدول پرشمون 0x140004054 بود پس به علاوه 20 اش میکنیم که نتیجه میشه 0x140004068 ، الآن ما اینجا offset رو داریم
حالا توی 0x140004068 ی مقدار 4 بایتی ذخیره شده که میتونه این باشه : 0x00000080 این عدد در مبنای ده برابر با 128 هستش...
حالا فهمیدید چرا گفتم :

jump_table[5] = 0x00000080;

یعنی case 5 فاصلش از بیس 128 بایته

این یعنی کدی که مربوط به case 5 هستش ، 128 بایت جلوتر از base اصلی قرار داره...

بریم واسه ادامه کد ها ، خط پنجم داره کد cltq رو اجرا میکنه ، اینجا داره eax ⁧32 بیتی رو به rax ⁧64 بیتی برای آدرس دهی دقیق تر تبدیل میکنه
خط ششم کد lea 0x2bc8(%rip), %rdx رو اجرا میکنه که آدرس base برنامه (مثل base اصلی main) رو میگیره
خط هفتم هم کد add %rdx, %rax رو اجرا میکنه که داره درواقع همچین عملی رو انجام میده :
base + offset
یعنی مثلا اگه :
base = 0x140001400
offset = 0x00000080
الآن ما توی rax مقدار 0x140001480 رو داریم ، جایی که مربوط به بلوک کد case 5 هستش
کد خط هشتمم ی همچین چیزیه jmp *%rax که داره میگه برو پرش بزن به کد مربوطه ای آدرسش توی rax هستش
یعنی درواقع داره میگه برو بلوک کد case 5 رو اجرا کن ;)
بعدش هم که توی اون بلوک کد میاد رشته ای که مربوط بهش هستش رو میگیره لود میکنه میریزه توی rcx و بعدش هم printf رو صدا میزنه تا rcx رو چاپ کنه و بعدم میپره میره آخر تابع
به همین سادگی
امیدوارم واضح توضیح داده باشم ، اگه واستون نامفهوم بود چندبار متن رو بخونید متوجه میشید❤️

ولی ی سری استثنا ها هم وجود داره واسش ، همیشه پیچیدگی زمانی switch/case برابر با O(1) نیست ، گاهی هم برابر با O(n) میشه... درباره اونم بعدا ی پست جداگونه میزارم

——————————————————————————-

حمله CSRF چیه؟
یکی از حملات جالب وبه که مخفف Cross Site Request Forgery هستش.
هدف از این حمله اینه که بدون دسترسی داشتن به کوکی های کاربر با اکانتشون توی سایت موردنظر ی سری اقدامات انجام بشه...
بزارید اینطوری واستون مثال بزنم :
فرض کنید شما ادمین ی سایت فروشگاهی هستید ، ی روزی یکی میاد پیویتون میگه این لینکو چک کن ، میرید توی لینکی که داده بود و ی وب سایت معمولی میبینید و همه چیز نرمال به نظر میرسه
ولی یهو وارد سایتتون میشید و میبینید عه! سایتتون هک شده😂
این همون چیزیه که داریم دربارش حرف میزنیم.
لینکی که بهتون داده بود ی لینک مخرب بوده.
چطوری کار میکنه؟
وقتی وارد لینک شدید سایت هکر ی درخواست با مرورگر شما سمت ی قسمت مخصوص از سایتتون که مثلا مخصوص اضافه کردن محصول به سایته ارسال کرده ، و خب مرورگر شما هم بطور خودکار وقتی درخواست رو ارسال میکنه کوکی های شما رو هم همراه باهاش سمت سایتتون ارسال میکنه ، پس اون درخواست به عنوان اکانت شما ارسال شده و محصولی که هکر خواسته توی سایت شما اضافه شده و حالا مثلا با ی سری باگای دیگه مثل xss ترکیب شده و سایتتون دیفیس شده ، یا اینکه هکر کلا روی سرورتون ی بکدور نصب کرده و دسترسی کامل داره...

اینم پیاده سازی csrf attack بصورت عملی :()

——————————————————————————-

هکر ها چطوری اطلاعاتمون رو از عکسای ظاهرا بی اهمیت در میارن؟

فرض کنید اومدین ی عکسی که کاملا سیاهه فرستادین تو ی گروه ولی یهو یکی میاد آدرس خونتونو از روی همون عکس در میاره
خب این چطوری اتفاق میوفته؟
اینجاست که Photo Metadata وارد میشه🗿
این Photo Metadata چیه؟
خیلی ساده بخوام بگم وقتی‌که عکسی میگیرید ی سری اطلاعات هم همراه اون عکس توی فایل عکسی ذخیره میشه و همه داستان اون چیزی نیست که شما دارید توی برنامه img viewer میبینید. اطلاعاتی مثل مدل گوشی ، مدل دوربین ، زمان و تاریخ دقیق گرفته شدن اون عکس ، اینکه اون عکس با فلش گرفته شده یا نه ، موقعیت مکانی اونجایی که عکس گرفته شده و......
بله همه اینا ذخیره میشن ، البته لازم نیست نگران باشید همه اینارو میتونید از توی تنظیمات دوربینتون خاموش کنید ، و واسه اکثر گوشی ها اینکه لوکیشن سیو بشه توی عکس خاموشه بصورت پیشفرض
و اینم بگم که تو اکثر پیام‌رسان ها مثل تلگرام وقتی که عکسی ارسال میکنید تلگرام برای اینکه هم اطلاعاتی از شما به جایی درز نکنه و هم حجم فایلو کمتر شه میاد متادیتاشو حذف میکنه
ولی اگه همون عکس رو بصورت فایلی بفرستید دیگه متادیتاشو حذف نمیکنه :)
با ابزار های زیادیم میتونید این متادیتا رو از عکس استخراج کنید ، معروف ترینش exiftool هستش که اکثرا استفاده میکنن.
ی مثال میزنم واستون ، ی عکس توی ی گروه تلگرامی دیدم که ی بنده خدایی فرستاده بود 👇🏼