Distributed Denial of Service Attack - DDoS

DDoS Nedir ?
Distributed Denial of Service saldırısının amacı hedef sistemin kaynaklarını tüketerek tepki veremeyecek hale getirmektir. Açıklaması şöyle.

A conventional distributed denial of service attack (DDos) is a class of denial of service (DoS) attacks in which a distributed system (botnet) consisting of nodes controlled via some application (Mirai, LizardStresser, gafgyt, etc.) is used to consume the resources of the target system or systems to the point of exhaustion.

Bulut tabanlı DDoS saldırı platformları kurmak ilginç bir fikir. Ancak DDoS saldırısında esas amaç başka bir sistemi ele geçirip silah olarak kullanmak.

PDoS Nedir ?
Permanent Denial of Service (PDoS) saldırısının amacı hedef sistemi tekrar kullanılamayacak hale getirmektir. Yani bir anlamda tahrip etmektir. Açıklaması şöyle.

DDoSes are ephemeral. Once the attack vector is removed or the DDoS stops the device works. (Or in the case of Mirai, the rest of the internet works.)

PDoSes update the device so it cannot work, ever again.

DDoS ve TCP
Sadece TCP protokolünü kullanarak saldırıda bulunmak pek elverişli değil. Açıklaması şöyle.

There are a few other TCP based DDoS attacks, but they aren't very common due to the fact that TCP is by design quite inefficient for performing (simple) DDoS attacks. Application layer attacks (exhausting CPU, database, disk, etc) are often done based on TCP (for example by generating a lot of HTTP requests to a webserver), and there are few known attacks which try to abuse the TCP protocol, for example by sending illegal combinations of TCP flags or incorrect fragmenting. The 'teardrop attack' was a well known example of that, which used overlapping fragments to crash devices receiving the packets when reassembling them.

Attack Nedir
Açıklaması şöyle.

An event is something that has triggered notice. An event need not be an indication of wrongdoing. Someone successfully logging in is an event.

An incident is something that indicates a problem, however you define "problem". It carries from an event but has a layer of interpretation on top. Someone successfully logging in when they are on long-term sick leave and should be unable to use a computer is an incident.

An attack is an incident with malicious intent. Someone brute-forcing the credentials of someone on long-term sick leave is an attack. A manager asking the person on long-term sick leave for their password so that they can gain access to the person's work product for the benefit of the business is not an attack. It might be an incident, depending on your policies.

A threat is anything that has the potential to cause an incident. People, weather, machines, etc.

execv metodu

Giriş
execv ailesini çağırırken dikkat edilmesi gereken nokta, argv parametrelerinin sonuncusunun NULL'a eşitlenmesi. Böylece shell parametre listesinin nerede bittiğini anlayabiliyor.

Örnek
myprog uygulamaasını sıfır argc ile çağırmak için şöyle yaparız.

char *args[] = { NULL };
execv("./myprog", args);

GoF Tasarım Örüntüleri

Giriş
Tasarım örüntüleri ile ilgili unutulmaması gereken ilk kural şu:

Design patterns are not building blocks!

GoF kitabındaki şu cümle önemli. Örüntüyü kullanmadan önce nasıl kullanılmaması gerektiğini öğrenmek gerekir.

"No discussion of how to use design patterns would be complete without a few words on how not to use them. Design patterns should not be applied indiscriminately. Often they achieve flexibility and variability by introducing additional levels of indirection, and that can complicate a design and/or cost you some performance. A design pattern should only be applied when the flexibility it affords is actually needed."

Tasarım örüntülerinin nasıl kullanılacağına dair yapılan bir söyleşide GoF ekibi de tüm tasarım örüntülerinin bilinçsizce kullanılmasının kötü bir şey olduğunu söylüyor.

"Trying to use all the patterns is a bad thing, because you will end up with synthetic designs—speculative designs that have flexibility that no one needs. These days software is too complex. We can't afford to speculate what else it should do. We need to really focus on what it needs. That's why I like refactoring to patterns. People should learn that when they have a particular kind of problem or code smell, as people call it these days, they can go to their patterns toolbox to find a solution."

Bir şeyin bilinçsize yapılması denince aklıma hep Cargo Cult Programming geliyor :)

Tasarım Örüntüsü Niçin Lazım
1. Ortak Dil
Tasarım örüntülerinin gerçek gücü, geliştiriciler arasında ortak bir dil kullanılmasını sağlayarak iletişimi artırmasında kaynaklanıyor. Örneğin FooBuilder isimli bir sınıf görünce bu sınıfı Foo nesnesi yarattığını hemen anlayabiliyoruz.

2. Bakım ve İdame
Tasarım örüntüleri yazılımın yaşam döngüsü boyunca daha kolay değiştirilebilmesini sağlar. Açıklaması şöyle

You can certainly optimize for product creation-- generate a ton of monolithic code as quickly as possible, without worrying about organizing it. As you have already noticed, this can be very, very fast. The alternative is to optimize for maintenance-- make creation a touch more difficult, but make modifications easier or less risky. That is the purpose of structured code.

Tasarım Örüntüleri Yok Olur mu?
Prosedürel dillerin kullanımın azalmasıyla birlikte bazı tasarım örüntülerinin de kayboldu. Örneğin 1950'lerdeki "subroutine call" örüntüsü artık bilinmiyor. GoF tasarım örüntüleri de Nesneye Yönelik Programlama ile çok iç içe. Nesneye Yönelik Programlamanın eksikliklerini (shortcoming) kapatmaya yarıyorlar. Nesneye Yönelik Programlama da yerini yavaş yavaş Functional Programming'e bıraktıkça bu örütünler de unutulabilirler.

Pattern ve Principle Arasında Ne Fark Var?
Pattern (örüntü) kelimesi genellikle programlama dünyasında kullanılıyor. Principle (prensip, kural) ise genel kavramlar, programlama ile ilgili olması şart değil. Örneğin SOLID, DRY gibi kurallar test dokümanı yazarken bile kullanılabilir.

Pattern ve Best Practice Arasında Ne Fark Var?
Yukarıdaki Pattern ve Principle arasındaki fark ile aynı.

GoF Kitabı
Kitabın yazılmasında Christopher Alexander'ın The Timeless Way of Building (1979) kitabının etkisi olduğu söyleniyor. Alexander'ın kitabından bir alıntı

Almost everybody feels at peace with nature: listening to the ocean waves against the shore, by a still lake, in a field of grass, on a windblown heath. One day, when we have learned the timeless way again, we shall feel the same about our towns, and we shall feel as much at peace in them, as we do today walking by the ocean, or stretched out in the long grass of a meadow.
-- Christopher Alexander, The Timeless Way of Building (1979)

Kitap 3 ana başlığa bölünmüş, toplam 22 tane örüntü var.

1. Creational Patterns
2. Structural Patterns
3. Behavioural Patterns

Tüm örüntüleri bilmek mümkün değil. Hatta bir aralar sürekli yeni örüntüleri bulmak modaydı. Örüntüler en çok aynı şeyi konuşup anlarken işe yarıyor.

Patterns are not lessons about how to code. They are a vocabulary we use to describe patterns we recognize in code.

Örüntüler
Örüntülerin en sık kullanılanlarının görsel hali şöyle.

Küçük Bir Eleştiri

Bu örüntüler arasında Filter Design Pattern yok. Niye yok bilmiyorum. Aslında sıkça kullanılan bir örüntü.

1. Yaratışsal Örüntüler
Açıklaması şöyle.

Creational patterns deal with the creation of objects.

2.1 Adapter - Yapısal Örüntü

1.1 Singleton - Yaratışsal Örüntü
Singleton yazısına taşıdım.

1.2. Factory - Yaratışsal Örüntü
Factory yazısına taşıdım.

1.3 Abstract Factory - Yaratışsal Örüntü

Abstract Factory yazısına taşıdım.

1.4 Builder - Yaratışsal Örüntü
Builder yazısına taşıdım.

1.4 Prototype - Yaratışsal Örüntü
Prototype yazısına taşıdım.

2. Yapısal Örüntüler

Açıklaması şöyle.

Structural patterns deal with the composition of objects.It deals with questions such as:

1.What does a class contain?
2. What are the relationships of a class with other classes? Is it inheritance or composition?

2.1 Adapter - Yapısal Örüntü
Adapter yazısına taşıdım.

2.2 Bridge - Yapısal Örüntü
Bridge yazısına taşıdım.

2.3 Composite - Yapısal Örüntü
Composite yazısına taşıdım.

2.4 Decorator - Yapısal Örüntü
Decorator yazısına taşıdım.

2.5 Proxy - Yapısal Örüntü
Proxy yazısına taşıdım.

2.6 Facade (Cephe) Yapısal Örüntü
Facade yazısına taşıdım.

2.7 Flyweight (Tüy Sıklet) Yapısal Örüntü
Flyweight yazısına taşıdım.

3. Davranışsal Örüntüler
Açıklaması şöyle.

Behavioral patterns focus more on the behavior of objects, or more precisely, interactions between objects.

Davranışsal örüntüler nesne grupları arasındaki iletişimi sağlayarak daha karmaşık akış kontrollerinin yapılabilmesini sağlar. GoF kitabındaki davranışsal örüntülerin sayısı, yapısal ve yaratışssal örüntülerden daha fazladır.

3.1 Chain of Responsibility - Davranışsal Örüntü
Chain of Responsibility yazısına taşıdım.

3.2 Command - Davranışsal Örüntü
Command yazısına taşıdım.

3.3 Mediator - Davranışsal Örüntü
Mediator yazısına taşıdım.

3.4 Memento - Davranışsal Örüntü
Memento yazısına taşıdım.

3.5 Iterator - Davranışsal Örüntü
Iterator yazısına taşıdım.

3.6 Observer - Davranışsal Örüntü
Observer yazısına taşıdım.

3.7 Template Method - Davranışsal Örüntü
Template Method yazısına taşıdım.

3.8 Visitor - Davranışsal Örüntü
Visitor yazısına taşıdım.

3.9 Strategy - Davranışsal Örüntü
Strategy yazısına taşıdım.

3.10 State - Davranışsal Örüntü
State yazısına taşıdım.

Algoritma Analizi - O (n) Linear

Giriş
Lineer grafik anlamına gelir.

ArrayList'e Eleman Ekleme
ArrayList'e yeni elemen ekleme veya çıkarma diğer tüm elemanların kaydırılmasını gerektirdiği için O(n)'dir.

Array'i Döndürme
Şöyle yaparız.

/* Function to left rotate arr[] of size n by d */
void leftRotate(int arr[], int d, int n)
{
  rvereseArray(arr, 0, d-1);
  rvereseArray(arr, d, n-1);
  rvereseArray(arr, 0, n-1);
}

/*Function to reverse arr[] from index start to end*/
void rvereseArray(int arr[], int start, int end)
{
  int temp;
  while (start < end)
  {
    temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    start++;
    end--;
  }
}

Array'i XOR'layarak Dolaşma
Soru şöyle

Consider an array of integers, where all but one of the integers occur in pairs. In other words, every element in occurs exactly twice except for one unique element.

Given the array find and print the unique element. [2,3,1,3,2] -> result is 1

Şöyle yaparız.

private static int lonelyInteger(int[] a) {
  int b = a[0];

  for(int i = 1; i < a.length; i++){
    b ^= a[i];
  }
  return b;       
}

Least Common Multipe - En Büyük Ortak Kat

Şöyle hesaplarız. Aslında bu O(1) 'dir. 

static BigInteger lcm(BigInteger a, BigInteger b) {
    return a.multiply(b).divide(a.gcd(b));
}

Ancak bir dizi için hesaplamak gerekiyorsa döngü kurmak gerekir çünkü formül şöyle

LCM(a, b, c) = LCM(LCM(a, b), c)

Greatest Common Divisor - En Büyük Ortak Bölen

Hata durumlarını ele almazsak en basit hali işe şöyledir. p çok büyük ve q çok küçük ise en kötü durumda (worst case) şaşırtıcı bir şekilde O(n)'dir.

gcd(p,q)
  if (p == q)
    return q
  if (p < q)
    gcd(q,p)
  while (q != 0)
    temp = p % q
    p = q
    q = temp
  return p

Aynı şeyi özyinelemeli olarak şöyle yaparız. Bu aynı zamanda GCD bulmak için "Euclid's Algorithm" olarak ta bilinir.

public static long gcd(long a, long b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

Döngülü çözümü C++ ile gerçekleştirmek için şöyle yaparız.

int gcd(int a, int b) const {
  int temp{};

  a = std::abs(a);
  b = std::abs(b);

  if (b > a) {
    temp = a;
    a = b;
    b = temp;
  }

  while(b != 0) {
    temp = b;
    b = a % b;
    a = temp;
  }

  return a;
}

RetainAll
Hash kullanan collection'lardaki retainAll(Collection) metodu (elde tut). Bu metod ile verilen collection'daki elemanlar hariç geri kalan herşey silinir. hash aramanın maliyeti O(1)'dir. İşlem verilen collection'daki her eleman için tekrarlanınca maliyeti O(n) olur.

Piramit
Piramit çıktısını yazdırmak için şöyle yaparız. En dıştaki döngü sayısı önemlidir. İçteki döngü sayısı n'e bağımlı olduğu için dikkate alınmaz.

for i from 1 to n
  for j from 1 to i
    print "$j "
  print "\n"

Çıktı olarak şunu alırız

1
1 2
1 2 3

Turnuva Eşleşmesi
Biraz piramite benziyor. Şöyle yaparız.

for(int i = 0; i < players.length-1; i+=2)
    System.out.println(players[i] + " - " + players[i+1]);
for(int i = 1; i < players.length-1; i+=2)
    System.out.println(players[i] + " - " + players[i+1]);

for(int dist = 2; dist < players.length; dist++)
for(int i = 0; i + dist < players.length; i++)
    System.out.println(players[i] + " - " + players[i+dist]);

Çıktı olarak şunu alırız

0 - 1, 2 - 3, 4 - 5, 
1 - 2, 3 - 4, 5 - 6, 
0 - 2, 1 - 3, 2 - 4, 3 - 5, 4 - 6, 
0 - 3, 1 - 4, 2 - 5, 3 - 6, 
0 - 4, 1 - 5, 2 - 6, 
0 - 5, 1 - 6, 
0 - 6, 

Remove Duplicates From Sorted Array - Two pointer technique
Algoritma şöyle. Piramit örneğinde olduğu gibi en dıştaki döngü önemlidir. Two pointer technique kullanır. i slow runner, j ise fast runner olarak adlandırılır. j tüm diziyi dolaştığı için O(n)'dir.

public int removeDuplicates(int[] nums) {

    if (nums.length == 0) return 0;

    int i = 0;

    for (int j = 1; j < nums.length; j++) {

        if (nums[j] != nums[i]) {

            i++;

            nums[i] = nums[j];

        }

    }

    return i + 1;

}

HasCycle - Two pointer technique
Şöyle yaparız. Slow teker teker ilerler. fast ise ikişer ikişer ilerler. Eğer fast slow'a yetişirse döngü vardır.

public boolean isCyclic(Node first) {
  if(first == null) {
    return false;
  }
  Node fast = first;
  Node slow = first;
  while(fast.getNext() != null && fast.getNext().getNext() != null) {
    slow = slow.getNext();
    fast = fast.getNext().getNext();
    if(slow == fast) {
      return true;
    }
  }
  return false;
}

Diğer seçenekleri de görmek adına hash set kullanarak O(n)'de çözmek için şöyle yaparız.

bool check_for_cycle_short(const Node *p)
{
  std::unordered_set<const Node*> mm;
  for (; p && mm.insert(p).second; p = p->next);
  return p != nullptr;
}

Diğer seçenekleri de görmek adına O(n^2) olarak çözmek için şöyle yaparız.

bool check_for_cycle_long(const Node *p)
{
  for (; p; p = p->next)
  {
    for (const Node *q = p->next; q; q = q->next)
    {
      if (q == p)
        return true;
      }
  }
  return false;
}

Determine if an array is the reverse of a second array

İlk diziyi soldan sağa, ikinci diziyi sağdan sola dolaşır her elemanı karşılaştırırız. Şöyle yaparız.

public boolean areReversed(int[] array1, int[] array2) {
  if (array1.length != array2.length) {
    return false;
  }
  int length = array1.length;
  for (int i = 0; i < length; i++) {
    if (array1[i] != array2[length - i - 1]) {
      return false;
    }
  }
  return true;
}

Diziyi Sağdan ve Soldan Başlayarak Dolaşma
Diziyi Sağdan ve Soldan Başlayarak Dolaşma yazısına taşıdım.

Diğer
Bazen O(n) gibi görünen ancak bir hata durumunda erkenden biten kodlar olabiliyor. 

Örnek

Elimizde şöyle bir kod olsun. Bu kod da sanırım O (n)

do {
  // some operation with time complexity O(N)
} while (errorMetric > 0.01) // if this is false, we've reached convergence

Örnek

Elimizde şöyle bir kod olsun

int foo(int x){
  if (x == 0) return x;
  if (x == 42) return foo(42);        
  if (x > 0) return foo(x-1);            
  return foo(x/2);
}

Açıklaması şöyle. Eğer 42 ile çağrılmayacağını varsayarsak, bu değerler arasında en büyüğünü seçmek gerekir. Yani O (n) olur

- Don't ever call it with x >= 42.

- O(1) if x==0

- O(x) if x>0

- O(ln(x)) if x < 0