CPU Scheduling

Kernel
تصمیم میگیره چی اجرا بشه
تا اینجا فهمیدیم چندین Process میتونن همزمان روی سیستم وجود داشته باشن
ولی یه سوال مهم داریم
اگه فقط یه CPU Core داشته باشیم و 10p تا Process آماده اجرا باشن
کدومشون باید CPU رو بگیره
اینجاست که CPU Scheduling وارد ماجرا میشه

Scheduler
توی Kernel بخشی وجود داره که وظیفه اش اینه تصمیم بگیره کدوم Process یا Thread برای اجرا انتخاب بشه

به این بخش میگیم
Scheduler
خیلی ساده

Ready Processes
│
├── Process A
├── Process B
├── Process C
└── Process D
│
▼
Scheduler
│
▼
CPU

Scheduler
در اصل داره جواب این سوال رو پیدا میکنه
الان چه چیزی باید روی CPU اجرا بشه

Ready Queue
Process
هایی که آماده اجرا هستن ولی فعلا CPU در اختیارشون نیست رو به صورت مفهومی داخل چیزی به اسم Ready Queue در نظر میگیریم

مثلا:

Ready Queue

┌─────────┐
│ Process A│
├─────────┤
│ Process B│
├─────────┤
│ Process C│
├─────────┤
│ Process D│
└─────────┘
│
▼
Scheduler
│
▼
CPU

البته توی سیستم عامل واقعی داستان خیلی پیچیده تر از یه صف ساده است

Scheduler
باید چیزهای مختلفی رو در نظر بگیره و ساختارهای داخلیش هم بسته به سیستم عامل و سیاست زمان بندی فرق میکنه
آیا یک Process میتونه برای همیشه CPU رو بگیره
فرض کنید یه برنامه داشته باشیم

while (1) {
// do something
}

این برنامه هیچ وقت تموم نمیشه
اگه سیستم عامل هیچ کنترلی روی CPU نداشت ممکن بود این Process تا مدت خیلی زیادی CPU رو اشغال کنه و برنامه های دیگه فرصت اجرا پیدا نکنن
برای همین سیستم عامل های مدرن از Preemptive Scheduling استفاده میکنن

Preemption
یعنی سیستم عامل بتونه اجرای واحد فعلی رو متوقف کنه و CPU رو به یه واحد دیگه بده

مثلا:

Process A
│
│ Running
▼
Scheduler تصمیم میگیرد
│
▼
Context Switch
│
▼
Process B
│
│ Running
▼

اینجا Process A لزوما تموم نشده
فقط فعلا CPU رو از دست داده
بعدا میتونه دوباره ادامه اجراش رو از همون جایی که متوقف شده دنبال کنه

Timer Interrupt
اینجا وارد میشه
یکی از چیزهایی که به سیستم عامل کمک میکنه کنترل CPU رو پس بگیره Timer هست
سیستم عامل یک Timer سخت افزاری رو تنظیم میکنه
بعد از گذشت یک بازه مشخص Timer میتونه یک Interrupt ایجاد کنه

به صورت ساده

CPU
│
│ اجرای Process A
│
▼
Timer
│
│ زمان تموم شد
▼
Interrupt
│
▼
Kernel
│
▼
Scheduler
│
▼
Process B

پس یه Process نمیتونه به سادگی بگه
CPU
مال منه و پسش نمیدم😁

Kernel
بالاخره میتونه وارد ماجرا بشه

Context Switch اینجا چه نقشی داره

یادتون هست قبلا گفتیم Context Switch یعنی وضعیت اجرای واحد فعلی ذخیره بشه و وضعیت واحد بعدی برای اجرا آماده بشه
حالا اینا رو کنار هم بذارید

Timer Interrupt
↓
Kernel
↓
Scheduler
↓
انتخاب واحد جدید
↓
Context Switch
↓
Thread یا Process Running جدید

این زنجیره یکی از پایه های مهم برای فهمیدن Scheduling هست

Scheduler
بر چه اساسی انتخاب میکنه
اینکه کدوم واحد اجرا بشه میتونه به سیاست ها و الگوریتم های مختلفی بستگی داشته باشه

چند نمونه کلاسیک رو ببینیم
FIFO یا FCFS

هر Process که زودتر وارد شده زودتر اجرا میشه

A → B → C → D

ساده است
ولی همیشه باعث بهترین عملکرد نمیشه

Shortest Job First
اگه مدت اجرای کارها رو بدونیم میتونیم کار کوتاه تر رو زودتر اجرا کنیم

مثلا:

A = 10ms
B = 2ms
C = 7ms

B → C → A

از نظر تئوری جالبه
ولی سیستم عامل معمولا از قبل دقیقا نمیدونه هر Process یا Thread قراره چقدر CPU مصرف کنه

Round Robin
اینجا هر واحد برای یه مقدار زمان مشخص CPU میگیره

مثلا

A → B → C → A → B → C

فرض کنید هرکدوم 10ms زمان داشته باشن

A 10ms
B 10ms
C 10ms
A 10ms
B 10ms

این مدل برای سیستم های تعاملی میتونه مناسب تر باشه

چرا Scheduling برای Reverse Engineering مهمه؟

وقتی دارید یه برنامه رو Debug میکنید ممکنه فکر کنید اجرای برنامه باید کاملا خطی باشه

مثلا

Instruction 1
Instruction 2
Instruction 3
Instruction 4

ولی سیستم عامل میتونه وسط اجرای اون Thread اجرای CPU رو ازش بگیره و واحد دیگه ای رو اجرا کنه

مثلا:

Thread A
│
├── Instruction 1
├── Instruction 2

│
▼
Context Switch
│
▼
Thread B
│
├── Instruction X
├── Instruction Y
│
▼
Context Switch
│
▼
Thread A
│
└── Instruction 3

پس ترتیب زمانی اجرای یک برنامه فقط به کد خودش بستگی نداره

Scheduler
و وضعیت کل سیستم هم روی زمان بندی اجرای Threadها تاثیر میذارن

Process یا Thread

اینجا یه نکته خیلی مهم داریم
در سیستم های مدرن معمولا Scheduler چیزی رو که واقعا باید روی CPU اجرا بشه در سطح Thread زمان بندی میکنه
نه اینکه Process رو همیشه به عنوان یک واحد غیرقابل تقسیم در نظر بگیره

مثلا:

Process A
├── Thread 1
├── Thread 2
└── Thread 3

Process B
├── Thread 1
└── Thread 2

Scheduler
میتونه Thread های آماده رو برای اجرا انتخاب کنه یعنی وقتی بعداً وارد مبحث Thread بشیم این موضوع خیلی مهم تر میشه

یک نکته درباره CPU Core
اگه یک Core داشته باشیم در هر لحظه فقط یک Thread میتونه واقعا روی اون Core اجرا بشه ولی با جابه جایی سریع بین Threadها اینطور به نظر میرسه که چند برنامه همزمان دارن اجرا میشن

مثلا:

Time
│
├── Thread A
├── Thread B
├── Thread C
├── Thread A
└── Thread B

اگه چند Core داشته باشیم چند Thread میتونن واقعا به صورت همزمان روی Coreهای مختلف اجرا بشن
اینجاست که تفاوت بین

Concurrency و Parallelism هم مهم میشه


CPU Scheduling
یعنی Kernel تصمیم میگیره کدوم Thread یا Process آماده باید CPU رو دریافت کنه

به صورت ساده

Ready
│
▼
Scheduler
│
▼
Running
│
├── Time Slice تموم میشه
│
▼
Preemption
│
▼
Context Switch
│
▼
Thread یا Process دیگه

مفاهیم مهم این قسمت

Scheduler
انتخاب کننده واحد قابل اجرا

Ready Queue
محل مفهومی واحدهای آماده اجرا

Preemption
گرفتن CPU از واحدی که در حال اجراست

Timer Interrupt
یکی از مکانیزم هایی که میتونه باعث بشه Kernel فرصت بررسی وضعیت و زمان بندی دوباره رو پیدا کنه

Context Switch
جابه جایی وضعیت اجرای واحد فعلی و آماده کردن واحد بعدی

Thread
واحدی که در سیستم های مدرن معمولا مستقیما برای اجرا زمان بندی میشه

@reverseengine

CPU Scheduling

Kernel
Decides what to run
So far we have understood that multiple processes can exist on the system at the same time
But we have an important question
If we only have one CPU Core and 10p to Processes are ready to run
Which one should get the CPU
This is where CPU Scheduling comes into play

Scheduler
There is a part in the Kernel whose job is to decide which Process or Thread to choose to run

We call this part
Scheduler
Very simply

Ready Processes
│
├── Process A
├── Process B
├── Process C
└── Process D
│
▼
Scheduler
│
▼
CPU

Scheduler
Basically, it is finding the answer to this question
What should be run on the CPU now

Ready Queue
Processes that are ready to run but do not currently have the CPU are conceptually considered in something called the Ready Queue

For example:

Ready Queue

┌─
│
▼
Scheduler
│
▼
CPU

Of course, in a real operating system, the story is much more complicated than a simple queue

Scheduler
must consider different things and its internal structures also vary depending on the operating system and scheduling policy

Can a Process take the CPU forever
Suppose we have a program

while (1) {
// do something
}

This program will never finish

If the operating system had no control over the CPU, this Process could occupy the CPU for a very long time and other programs would not have a chance to run

That is why modern operating systems use Preemptive Scheduling

Preemption
means that the operating system can stop the current unit from executing and give the CPU to another unit Give

For example:

Process A
│
│ Running
▼
Scheduler decides
│
▼
Context Switch
│
▼
Process B
│
│ Running
▼

Here Process A is not necessarily finished
It just lost the CPU for now
It can continue its execution from where it stopped later

Timer Interrupt
comes in here
One of the things that helps the operating system regain control of the CPU is Timer
The operating system sets a hardware Timer
After a certain period of time, the Timer can create an Interrupt

Simply

CPU
│
│ Running Process A
│
▼
Timer
│
│ Time is up
▼
Interrupt
│
▼
Kernel
│
▼
Scheduler
│
▼
Process B

So a Process can't simply say
The CPU is mine and I'm not giving it back😁

The Kernel
can finally get involved

What is the role of Context Switch here Yes

Remember we said earlier that Context Switch means saving the state of the current unit and preparing the state of the next unit for execution

Now put these together

Timer Interrupt
↓
Kernel
↓
Scheduler
↓
Selecting a new unit
↓
Context Switch
↓
A new thread or process running

This chain is one of the important foundations for understanding Scheduling

On what basis does the Scheduler choose
Which unit to run can depend on various policies and algorithms

Let's look at some classic examples

FIFO or FCFS

Any process that enters earlier will run earlier

A → B → C → D

It's simple

But it doesn't always lead to the best performance

Shortest Job First
If we know the execution time of the tasks, we can execute the shorter task first

For example:

A = 10ms
B = 2ms
C = 7ms

B → C → A

It's interesting in theory

But the operating system usually doesn't know in advance exactly how much CPU each process or thread is going to consume Do

Round Robin
Here each thread gets CPU for a certain amount of time

For example

A → B → C → A → B → C

Assume each has 10ms of time

A 10ms
B 10ms
C 10ms
A 10ms
B 10ms

This model may be more suitable for interactive systems

Why is Scheduling important for Reverse Engineering?

When you are debugging a program, you may think that the execution of the program should be completely linear

For example

Instruction 1
Instruction 2
Instruction 3
Instruction 4

But the operating system can take the CPU from that thread in the middle of its execution and execute another thread

For example:

Thread A
│
├── Instruction 1
├── Instruction 2

│
▼
Context Switch
│
▼
Thread B
│
├── Instruction X
├── Instruction Y
│
▼
Context Switch
│
▼
Thread A
│
└── Instruction 3

So, the execution timing of a program doesn't depend solely on its own code.

The Scheduler
and the overall system state also influence the scheduling of thread execution.

Process or Thread

There is a crucial point here:
In modern systems, the scheduler typically schedules the entity that actually runs on the CPU at the *thread* level,
rather than always treating the process as an indivisible unit.

For example:

Process A
├── Thread 1
├── Thread 2
└── Thread 3

Process B
├── Thread 1
└── Thread 2

The Scheduler
can select ready threads for execution; this becomes even more significant when we delve deeper into the topic of threads later.

A point regarding CPU Cores:
If we have a single core, only one thread can actually execute on that core at any given moment; however, through rapid switching between threads, it appears as though multiple programs are running simultaneously.

For example:

Time
│
├── Thread A
├── Thread B
├── Thread C
├── Thread A
└── Thread B

If we have multiple cores, multiple threads can actually execute simultaneously on different cores.
This is where the distinction between

Concurrency and Parallelism becomes important.


CPU Scheduling
refers to the kernel deciding which ready thread or process should be allocated the CPU.

Simply put:

Ready
│
▼
Scheduler
│
▼
Running
│
├── Time slice expires
│
▼
Preemption
│
▼
Context Switch
│
▼
Another thread or process

Key concepts in this section:

Scheduler
The component that selects the executable unit.

Ready Queue
The conceptual location for units ready to execute.

Preemption
Taking the CPU away from the currently executing unit.

Timer Interrupt
One of the mechanisms... ...that allow the kernel to check the status and reschedule

Context Switch
Swapping the execution state of the current unit and preparing the next one

Thread
A unit that, in modern systems, is typically scheduled directly for execution

@reverseengine

My New Blog Post

Evading Sysmon Dns Monitoring In 2026 | binary-win

DNSevade : https://github.com/binary-win/DNSevade.git

Sysmon gets its DNS telemetry from the Microsoft-Windows-DNS-Client ETW provider.
Let's hide in plain sight.

#sysmon #bypass

Your Notes are HERE

Prompt Injection in the Wild

https://cybershujin.github.io/Prompt-Injection-in-the-Wild

Introduction to Exploit Development

https://samsclass.info/127/ED_2020.shtml

Scheduling Metrics

از کجا بفهمیم Scheduler خوبه؟

توی قسمت قبل فهمیدیم Scheduler مسئول اینه که مشخص کنه کدوم Thread یا Process نوبتش بشه و روی CPU اجرا بشه

اما یه سؤال مهم داریم:

از کجا بفهمیم یک الگوریتم Scheduling واقعا خوبه؟

فرض کنید سه تا Process داریم:

A
B
C

Scheduler
میتونه این‌ها رو با ترتیب‌های مختلف اجرا کنه

پس باید یه سری معیار داشته باشیم تا بتونیم عملکرد الگوریتم‌های مختلف رو با هم مقایسه کنیم

اینجاست که میرسیم به Scheduling Metrics



Turnaround Time

اولین مفهوم:

Turnaround Time

به زبان ساده یعنی:

از لحظه‌ای که یک Job وارد سیستم میشه تا لحظه‌ای که کارش کاملا تموم میشه چقدر زمان گذشته؟

فرمولش:

Turnaround Time =

Completion Time - Arrival Time

مثلا:

Arrival Time = 0
Completion Time = 10

پس:

Turnaround Time = 10 - 0
= 10

یعنی این Process از لحظه ورود تا پایان 10 واحد زمانی داخل سیستم بوده



Waiting Time

حالا یه سؤال دیگه:

Process
چه مقدار از زمان رو فقط منتظر CPU بوده؟

اینجا میرسیم به:

Waiting Time

فرض کنید وضعیت یک Process این شکلی باشه:

Arrival
↓
Waiting
↓
Running
↓
Waiting
↓
Running
↓
Finished

هر مدتی که Process توی Ready Queue منتظر CPU باشه، جزو Waiting Time حساب میشه

پس خیلی ساده:

Waiting Time =
مدت زمانی که Process منتظر CPU بوده



Response Time

این یکی مخصوصا برای برنامه‌های تعاملی خیلی مهمه

Response Time
از وقتی Job وارد سیستم میشه تا اولین باری که CPU بهش میرسه چقدر طول کشیده؟

مثلا:

Arrival
│
│ 5ms
▼
First Run

پس:

Response Time = 5ms

حالا تفاوتش با Turnaround Time رو خوب دقت کنید

Response Time

فقط تا اولین اجرا:

Arrival → First Run

Turnaround Time

تا اخر کامل کار:

Arrival → Completion

پس ممکنه یک Process خیلی سریع اولین بار اجرا بشه ولی برای تمام شدن کارش مدت زیادی زمان لازم داشته باشه


یک مثال کامل

فرض کنیم سه تا Job داریم:

Job A
Arrival = 0
Runtime = 5

Job B
Arrival = 0
Runtime = 3

Job C
Arrival = 0
Runtime = 2

فرض کنیم Scheduler تصمیم گرفته این ترتیب رو اجرا کنه:

A → B → C

پس Timeline میشه:

0 5 8 10
|--------|--------|--------|
A B C

حالا یکی‌یکی حساب کنیم


Job A

A
از زمان:

0

شروع شده و در:

5

تموم شده

پس:

Turnaround = 5 - 0
= 5

چون A بلافاصله اجرا شده:

Response = 0



Job B

B
در زمان:

5

شروع شده و در:

8

تموم شده.

پس:

Turnaround = 8 - 0
= 8

و چون B از زمان 0 تا 5 منتظر CPU بوده:

Response = 5



Job C

C
در زمان:

8

شروع شده و در:

10

تموم شده

پس:

Turnaround = 10 - 0
= 10

و:

Response = 8

چون C تا زمان 8 منتظر مونده تا بالاخره CPU بهش برسه


میانگین هم مهمه

معمولا قرار نیست فقط یک Process رو بررسی کنیم

میخوایم ببینیم الگوریتم ما در مجموع چه عملکردی داشته

پس میانگین میگیریم

مثلا:

Turnaround:

A = 5
B = 8
C = 10

میانگین:

(5 + 8 + 10) / 3
= 7.67

پس:

Average Turnaround Time = 7.67

همین کار رو میتونیم برای معیارهای دیگه مثل Response Time هم انجام بدیم



مشکل یک Scheduler ساده

حالا یه حالت جالب‌تر رو ببین.

فرض کنید داریم:

A = 100ms
B = 2ms
C = 2ms

و Scheduler هم بگه:

A → B → C

Timeline
میشه:

0 100 102 104
|------------------------------|------|------|
A B C

یعنی B و C باید منتظر بمونن تا A کارش تموم بشه

در نتیجه:

Response Time B = 100ms
Response Time C = 102ms

در حالی که خود B و C فقط 2ms کار دارن

یعنی یه Job سنگین میتونه باعث بشه Jobهای کوچیک مدت زیادی منتظر بمونن



اینجا Shortest Job First جالب میشه

اگر از قبل بدونیم مدت اجرای Job ها تقریبا چقدره می‌تونیم اول Job های کوتاه‌تر رو اجرا کنیم

مثلا:

A = 100ms
B = 2ms
C = 2ms

پس به‌ جای:

A → B → C

میتونیم داشته باشیم:

B → C → A

Timeline:

0 2 4 104
|----|----|--------------------------------|
B C A

حالا B و C خیلی سریع اولین پاسخ خودشون رو میگیرن

این ایده پایه الگوریتم:

Shortest Job First (SJF)

هست


ولی اینجا یک مشکل داریم

سیستم‌عامل معمولا از قبل دقیقا نمیدونه:

این Process قراره چند میلی‌ثانیه CPU مصرف کنه؟

مثلا یک برنامه ممکنه مدام بین CPU و I/O جا به‌ جا بشه:

CPU
↓
I/O
↓
CPU
↓
I/O
↓
CPU

یا مدت اجرای برنامه به ورودی کاربر وابسته باشه

پس اینکه از قبل دقیقا بدونیم هر Job چقدر CPU لازم داره همیشه ممکن نیست

اینجاست که Scheduling از یک صف ساده خیلی پیچیده‌ تر میشه



چرا این موضوع برای ما مهمه؟

شاید اولش فکر کنید این بحث چه ربطی به Reverse Engineering داره

ولی وقتی یک برنامه چند تا Thread داشته باشه اجرای واقعی برنامه فقط به ترتیب دستورهای داخل Binary بستگی نداره

مثلا:

Thread A
↓
Running
↓
Preempted

همزمان:

Thread B
↓
Running
↓
Blocked

بعد دوباره:

Thread A
↓
Running

یعنی اجرای برنامه میتونه بین Thread های مختلف جابه‌جا بشه

این موضوع وقتی مهم‌ تر میشه که با چیزهایی مثل این‌ها طرف باشیم:

Multi-threading
Race Condition
Deadlock
Timing Bug
Synchronization

مثلا ممکنه یک Bug فقط زمانی اتفاق بیفته که دو Thread تقریبا همزمان به یک بخش خاص از برنامه برسن

پس فقط نباید بپرسیم:

این دستور چی کار میکنه

باید بپرسیم:

این Thread کی اجرا شده؟ قبلش چه Thread ی اجرا شده؟ چرا اجرای این Thread متوقف شده و بعد دوباره برگشته؟

این دید بعدا برای تحلیل Bug های مربوط به Concurrency خیلی مهم میشه




فعلاً این سه معیار رو خوب یاد بگیرید:

Turnaround Time

Arrival → Completion

یعنی کل زمانی که Job از ورود تا پایان داخل سیستم بوده

Waiting Time

مدت انتظار برای CPU

یعنی چه مقدار از زمان Process در Ready Queue منتظر CPU بوده

Response Time


Arrival → First Run

یعنی چقدر طول کشیده تا Process برای اولین بار CPU بگیره.

به شکل خلاصه:

Arrival
│
├──── Waiting ────┐
│ │
▼ ▼
First Run Running
│ │
│ │
└── Response │
│
▼
Completion

Turnaround = Arrival → Completion

پس وقتی میخوایم دو الگوریتم Scheduling رو با هم مقایسه کنیم فقط نمیگیم:

کدوم سریع‌تره؟

باید ببینیم:

چقدر منتظر موندیم؟
چقدر سریع اولین جواب رو گرفتیم؟
چقدر طول کشید کار کامل بشه؟

این‌ها همون معیار هایی هستن که کمک میکنن بفهمیم یک Scheduler واقعا چقدر خوب عمل میکنه

@reverseengine

Scheduling Metrics

How do we know if a Scheduler is good?

In the previous section, we learned that the Scheduler is responsible for determining which Thread or Process will get its turn and run on the CPU

But we have an important question:

How do we know if a Scheduling algorithm is really good?

Suppose we have three Processes:

A
B
C

Scheduler
can run these in different orders

So we need to have a set of criteria so that we can compare the performance of different algorithms

This is where we come to Scheduling Metrics

Turnaround Time

The first concept:

Turnaround Time

In simple terms, it means:

How much time has passed from the moment a Job enters the system to the moment its work is completely completed?

The formula is:

Turnaround Time =

Completion Time - Arrival Time

For example:

Arrival Time = 0

Completion Time = 10

So:

Turnaround Time = 10 - 0
= 10

That means this Process has been in the system for 10 time units from the moment it entered until the end

Waiting Time

Now another question:

How much time did the Process
just wait for the CPU?

Here we come to:

Waiting Time

Assume the state of a Process is as follows:

Arrival
↓
Waiting
↓
Running
↓
Waiting
↓
Running
↓
Finished

Any time the Process waits in the Ready Queue for the CPU is counted as Waiting Time

So very simple:

Waiting Time =
The amount of time the Process has been waiting for the CPU

Response Time

This one is especially important for interactive programs

Response Time
How long did it take from the time the Job entered the system until the first time the CPU reached it?

For example:

Arrival
│
│ 5ms
▼
First Run

So:

Response Time = 5ms

Now pay close attention to the difference with Turnaround Time

Response Time

Only until the first run:

Arrival → First Run

Turnaround Time

Until the complete end of the job:

Arrival → Completion

So a Process may run very quickly the first time, but it may take a long time to finish its work

A complete example

Let's assume we have three Jobs:

Job A
Arrival = 0
Runtime = 5

Job B
Arrival = 0
Runtime = 3

Job C
Arrival = 0
Runtime = 2

Let's assume the Scheduler decides to run in this order:

A → B → C

So the Timeline becomes:

0 5 8 10
|--------|--------|--------|
A B C

Now let's calculate one by one

Job A

A
started at:

0

and finished at:

5

So:

Turnaround = 5 - 0

= 5

Since A was executed immediately:

Response = 0

Job B

B
started at:

5

and finished at:

8

.

So:

Turnaround = 8 - 0
= 8

And since B waited for the CPU from time 0 to 5:

Response = 5

Job C

C
started at time:

8

and finished at:

10

So:

Turnaround = 10 - 0
= 10

And:

Response = 8

Because C waited until time 8 to finally get the CPU

The average is also important

Usually we are not going to examine just one Process

We want to see how our algorithm performed overall

So we take the average

For example:

Turnaround:

A = 5

B = 8

C = 10

Average:

(5 + 8 + 10) / 3
= 7.67

So:

Average Turnaround Time = 7.67

We can do the same for other metrics like Let's do Response Time too

A Simple Scheduler Problem

Now let's look at a more interesting case.

Suppose we have:

A = 100ms
B = 2ms
C = 2ms

And the Scheduler says:

A → B → C

Timeline
It becomes:

0 100 102 104
|-------------------------|------|------|
A B C

That means B and C have to wait until A finishes its work

As a result:

Response Time B = 100ms
Response Time C = 102ms

While B and C themselves only have 2ms of work

That means a heavy job can make small jobs wait for a long time

This is where Shortest Job First comes in handy

If we know in advance how long the jobs will take, we can execute the shorter jobs first

For example:

A = 100ms
B = 2ms
C = 2ms

So instead of:

A → B → C

we can have:

B → C → A

Timeline:

0 2 4 104
|----|----|--------------------------------|
B C A

Now B and C get their first response very quickly

This is the basic idea of ​​the algorithm:

Shortest Job First (SJF)

But here we have a problem

The operating system usually does not know in advance exactly:

How many milliseconds of CPU is this process going to consume?

For example, a program might be constantly switching between CPU and I/O:

CPU
↓
I/O
↓
CPU
↓
I/O
↓
CPU

Or the execution time of the program depends on user input

So it is not always possible to know in advance exactly how much CPU each job will need

This is where Scheduling becomes much more complex than a simple queue

9. Why is this important to us?

At first you might think what does this have to do with Reverse Engineering

But when a program has multiple threads, the actual execution of the program does not depend only on the order of the instructions in the binary

For example:

Thread A
↓
Running
↓
Preempted

Simultaneously:

Thread B
↓
Running
↓
Blocked

Then again:

Thread A
↓
Running

That is, the execution of the program can be switched between different threads

This becomes more important when we are dealing with things like:

Multi-threading

Race Condition

Deadlock

Timing Bug

Synchronization

For example, a bug may only occur when two threads reach a specific part of the program almost simultaneously

So we should not just ask:

What does this instruction do

We should ask:

When did this thread run? What thread ran before it? Why did this thread stop and then start again?

This view will be very important later for analyzing concurrency-related bugs

For now, learn these three metrics well:

Turnaround Time

Arrival → Completion

The total time the Job spent in the system from entry to completion

Waiting Time

The waiting time for CPU

How much time the Process spent in the Ready Queue waiting for the CPU

Response Time

Arrival → First Run

How long it took for the Process to get the CPU for the first time.

In summary:

Arrival
│
├─── Waiting ─────┐
│ │
▼ ▼
First Run Running
│ │
│ │
└── Response │
│
▼
Completion

Turnaround = Arrival → Completion

So when we want to compare two scheduling algorithms, we don't just say:

Which one is faster?

We need to see:

How long did we wait?

How fast did we get the first response?

How long did it take to complete the task?

These are the metrics that help us understand how well a Scheduler really performs

@reverseengine

قسمت سی و سوم بافر اورفلو

Taint Analysis on Binary

در Assembly از کجا بفهمیم داده کجا میره

میخوایم Taint Analysis رو روی باینری اجرا کنیم
اینجا دیگه خبری از اسم متغیر های مثل input و buffer نیست
باید با Registerها و ادرس‌های حافظه کار کنیم


پیدا کردن Source
اول باید بفهمیم داده از کجا وارد برنامه شده مثلا داخل یک برنامه لینوکسی ممکنه به این برسیم

call read

یا

call recv

فرض کنید قبلش اینو داریم

lea rsi,[rbp-40h]
mov edx,40h
call read

اینجا میتونیم مسیر ساده‌ای داشته باشیم

External Input
↓
read()
↓
[rbp-40h]

پس داده ورودی داخل [rbp-40h] قرار میگیره
این نقطه میتونه Source ما باشه


دنبال کردن داده

حالا چند دستور پایین‌ تر میبینیم

mov rax,[rbp-40h]
mov rcx,rax

پس مقدار از حافظه اومده داخل RAX
بعد وارد RCX شده
مسیر فعلا اینه

[rbp-40h]
↓
RAX
↓
RCX


دنبال کردن انتقال داده

فرض کنید بعدش اینو ببینیم

mov rdx,rcx
call process_data

حالا

[rbp-40h]
↓
RAX
↓
RCX
↓
RDX
↓
process_data()

یعنی داده‌ای که از بیرون اومده وارد process_data شده
حالا باید داخل اون تابع ادامه مسیر رو دنبال کنیم



رسیدن به Sink
فرض کنید داخل تابع به این برسیم

mov [rdi],rax

اینجا یک Memory Write داریم
پس مسیر کلی ما میشه

Input
↓
read()
↓
Stack / Memory
↓
Register
↓
Function
↓
Memory Write

این نقطه میتونه Sink موردنظر ما باشه
البته رسیدن داده به یک Write به تنهایی به معنی وجود آسیب‌ پذیری نیست
باید اندازه و محدوده دسترسی هم بررسی بشه

Taint
کردن Register ها

فرض کنید

mov rax,[rbp-40h]
و [rbp-40h] شامل داده خارجی باشه
پس
RAX = Tainted
بعد
mov rcx,rax
حالا
RCX = Tainted
بعد
add rcx,8

مقدار RCX تغییر کرده ولی همچنان به داده اولیه وابسته است
پس مسیر Taint قطع نشده
اما یک نکته مهم
همه دستورها باعث انتقال ساده Taint نمیشن

مثلا:
cmp rax,10h
اینجا داده مستقیما به Register دیگری منتقل نشده
ولی مقدار RAX روی تصمیم برنامه تاثیر گذاشته

مثلا:

cmp rax,10h
ja invalid

پس اینجا یک Control Dependency داریم یعنی داده خارجی روی مسیر اجرای برنامه اثر گذاشته

یک مثال کامل تر:
lea rsi,[rbp-40h]
mov edx,40h
call read

movzx eax,byte ptr [rbp-40h]

cmp eax,20h
ja invalid

mov edi,eax
call process_data

مسیر رو مرحله به مرحله ببینید

read()
↓
[rbp-40h]
↓
EAX
↓
cmp
↓
Control Flow
↓
process_data()

اینجا مقدار ورودی هم روی داده تاثیر گذاشته
هم روی مسیر اجرای برنامه

در Ghidra چه کار میکنیم
وقتی به یک مقدار مشکوک رسیدیم
اول References اون مقدار رو بررسی میکنیم بعد استفاده‌های بعدی رو پیدا میکنیم

مثلا:
Source
↓
Reference
↓
Register
↓
Memory Access
↓
Function Call

بعد همین کار رو برای تابع بعدی ادامه میدیم تا مسیر کامل مشخص بشه یک نکته مهم لازم نیست همیشه کل Taint Analysis رو دستی انجام بدید
در برنامه‌ های بزرگ این کار خیلی سخت میشه برای همین ابزارهای مختلفی وجود دارن که میتونن این کار رو تا حدی خودکار کنن

مثلا:
angr
Triton
DynamoRIO
Intel Pin

هرکدوم روش و کاربرد خودشون رو دارن

@reverseengine

Part 33 Buffer Overflow

Taint Analysis on Binary

In Assembly, how do we know where the data goes

We want to run Taint Analysis on binary
Here, there is no more mention of variable names like input and buffer

We have to work with registers and memory addresses

Finding the Source
First, we need to find out where the data entered the program from, for example, in a Linux program, we might get this

call read

or

call recv

Suppose we have this before

lea rsi,[rbp-40h]

mov edx,40h
call read

Here we can have a simple path

External Input
↓
read()
↓
[rbp-40h]

So the input data is placed in [rbp-40h]

This point can be our Source

Following the data

Now we see a few commands below

mov rax,[rbp-40h]

mov rcx,rax

So the value came from memory Inside RAX
Then entered RCX
The current path is

[rbp-40h]
↓
RAX
↓
RCX

Following data transfer

Suppose we see this later

mov rdx,rcx
call process_data

Now

[rbp-40h]
↓
RAX
↓
RCX
↓
RDX
↓
process_data()

That is, the data that came from outside entered process_data
Now we have to continue the path inside that function

Reaching Sink
Suppose we reach this inside the function

mov [rdi],rax

Here we have a Memory Write
So our general path becomes

Input
↓
read()
↓
Stack / Memory
↓
Register
↓
Function
↓
Memory Write

This point can be our desired Sink
Of course, reaching a Write alone does not mean there is a vulnerability
The size and access range should also be checked

Taint
Registers

Assuming

mov rax,[rbp-40h]

and [rbp-40h] contains external data

so
RAX = Tainted

then
mov rcx,rax

now
RCX = Tainted

then
add rcx,8

The RCX value has changed but is still dependent on the original data

so the Taint path is not broken

but one important point

not all instructions cause a simple Taint transfer

for example:

cmp rax,10h

here the data is not directly transferred to another register

but the RAX value affects the program's decision

for example:

cmp rax,10h
ja invalid

so here we have a Control Dependency, that is, the external data affects the program's execution path

A more complete example:

lea rsi,[rbp-40h]

mov edx,40h
call read

movzx eax,byte ptr [rbp-40h]

cmp eax,20h
ja invalid

mov edi,eax
call process_data

See the path step by step

read()
↓
[rbp-40h]
↓
EAX
↓
cmp
↓
Control Flow
↓
process_data()

Here the input value affects both the data and the execution path

What do we do in Ghidra
When we reach a suspicious value
First we check the References of that value, then we find the next uses

For example:
Source
↓
Reference
↓
Register
↓
Memory Access
↓
Function Call

Then we continue the same for the next function to determine the full path. One important point is that you don't always have to do the entire Taint Analysis manually
In large programs, this can be very difficult, so there are various tools that can automate this task to some extent

For example:

angr
Triton
DynamoRIO
Intel Pin

Each has its own method and application

@reverseengine

Memory Allocation
و تغییر RW → RX

تا اینجا درباره‌ی Call Stack گفتیم حالا یک لایه پایین‌ تر میریم سراغ خود حافظه

یکی از چیزهایی که EDR ها در تحلیل رفتار Processها زیر نظر میگیرن

Permission
حافظه و تغییراتشه

اصلا RW و RX یعنی چی؟

هر بخش از حافظه میتونه Permission های مختلفی داشته باشه:

R = Read
W = Write
X = Execute

مثلا:

RW

یعنی:

Read + Write

برنامه میتونه اطلاعات داخل این قسمت رو بخونه و تغییر بده ولی قرار نیست از همون قسمت کد اجرا کنه

یا:

RX

یعنی:

Read + Execute

میتونه اطلاعات رو بخونه و از اون قسمت دستورهای CPU رو اجرا کنه ولی نباید بتونه محتوای اون صفحه رو تغییر بده

به‌صورت مفهومی ممکنه چنین زنجیره‌ای ببینیم:

Memory Allocation
↓
RW
↓
Write Data
↓
Permission Change
↓
RX
↓
Execution

یعنی یک بخش از حافظه اول قابل نوشتن بوده و بعد Permission اون به حالتی تغییر کرده که قابلیت Execute داشته باشه

همین تغییر به‌تنهایی به معنی Malware بودن نیست مثلا بعضی نرم‌افزارهای کاملا legitimate هم به دلایل مختلف کد تولید یا کامپایل میکنن

JIT
یکی از مثال‌های مهمه

بعضی Runtime ها از تکنولوژی‌ به اسم:

JIT = Just-In-Time Compilation

استفاده میکنن اینجا برنامه ممکنه در زمان اجرا بخشی از کد رو تولید کنه و برای اجرای اون نیاز به حافظه‌ی مناسب داشته باشه

پس:

RW → RX

میتونه در یک نرم‌ افزار سالم هم اتفاق بیفته

بنابراین یک EDR خیلی خوب نباید بگه:

RW → RX = Malware

چون این مدل منطق تقریبا همونقدر درسته که بگیم هر کسی هودی پوشید هکره 😂

چیزی که مهمه Context هست

EDR
معمولا قط یک Event رو نگاه نمیکنه
مثلا فرض کنید چنین زنجیره‌ای وجود داشته باشه:

Process
↓
Memory Allocation
↓
Write
↓
Protection Change
↓
RX Memory
↓
Thread Activity
↓
Call Stack
↓
Network Activity

هرکدوم به‌ تنهایی ممکنه کاملا عادی باشه
ولی وقتی چند رفتار غیرمعمول کنار هم قرار میگیرن ارزش تحلیلی بیشتری پیدا میکنن

به همین ددلیل Detection مدرن بیشتر شبیه اینه:

Event
+
Context
+
Process History
+
Memory Information
+
Thread Information
+
Call Stack


RWX
بعضی وقتا ممکنه Permission یک بخش به شکل زیر باشه:

RWX

یعنی:

Read
Write
Execute

در این حالت همون Memory Region هم قابل تغییر و هم قابل اجراست

از دید امنیتی این وضعیت معمولا حساس‌ تره چون اصل مهمی به نام:

W^X

وجود داره

یعنی:

Writable XOR Executable


به زبان ساده:

یک Memory Region بهتره همزمان هم Writable و هم Executable نباشه

البته باز هم:

RWX ≠ Malware

و:

RW → RX ≠ Malware

این‌ها فقط Signal هستن نه کار پایانی

DEP
یکی از مکانیزم‌ های مهم Windows:

Data Execution Prevention

هدفش اینه که بخش‌هایی از Memory که نباید کد اجرا کنن قابل Execute نباشن

مثلا اگر یک بخش فقط:

RW

باشه انتظار نداریم CPU از اونجا مثل یک Code Region معمولی دستور اجرا کنه
پس Permission های Memory بخشی از مدل امنیتی سیستم‌ عامل هستن نه صرفا یک عدد داخل Debugger

EDR
دقیقا به چه چیزهایی توجه میکنه؟
برای تحلیل یک Memory Region ممکنه اطلاعاتی مثل اینها اهمیت داشته باشه:


Process
├── Memory Type
├── Protection
├── Allocation History
├── Thread
├── Thread Start Address
├── Call Stack
├── Loaded Modules
├── Parent Process
└── Process Behavior

مثلا این دو وضعیت از نظر تحلیلی یکی نیستن:

Application
↓
JIT Activity
↓
RW → RX

در مقایسه با:

Unknown Process
↓
Private Memory
↓
Write
↓
RW → RX
↓
Suspicious Thread Activity

EDR
دقیقا به همین تفاوت Context اهمیت میده


نکته مهم
وقتی داخل Debugger یا Memory Viewer یک Region میبینید فقط به Address نگاه نکنید

این موارد رو هم بررسی کنید:

Address
Size
Protection
Type
State
Backing
Owner Process
Thread Relation

مثلا:

0x000001A...
Size: 0x5000
Protection: RX
Type: ...
State: ...

این اطلاعات کمک میکنن بفهمید با چه نوع Memory Region طرف هستید


پس فعلا این مدل ذهنی رو داشته باشید:

Memory
│
├── R
├── W
└── X

و یک تغییر Permission به‌ تنهایی چیزی رو ثابت نمیکنه