On Flooding Attacks and its Mitigation

BCP38 talks about flooding attacks and some simple ways of mitigating them. First it explains, how an attacker can target victims:

  1. by inundating a server with so many syn requests
  2. by spoofing the address of a legitimate host thereby causing the host to be black listed
  3. by inundating more than one host with syn-ack packets by spoofing IP addresses.

1 and 3 are somewhat related. The BCP (Best Current Practices) says that if routers have a very simple rule at their end to:

  • Allow traffic originating from its known prefixes (i.e. SA of all the traffic is from known prefixes), then forward as usual
  • Drop all the remaining traffic

then most of the source IP spoofing attacks can be mitigated. The DDoS attack of type 1 (mentioned above) can still happen, but since the source IP address cannot be spoofed or can be spoofed only to a limited extent (in the allowed range of prefixes), it will be easier to track down the source of attack. This “ingress traffic filtering” is best implemented at the edge routers of Internet.

Advertisements

The N-Queens Problem

The N-Queens Problem goes as follows: In a NxN square chess board, place all the queens so that they cannot kill each other – technically, it means no two queens can be in the same row/column/diagonal. As they say, part of the problem is solved by properly (mathematically or otherwise) phrasing the problem.

What does it mean to say the two queens are in the same row/column/diagonal? If we take $latex (r1, r2 .. r8)$ to be the row numbers of the queen for the columns 1 to 8, then for any i,j such that i is not equal to j, then if ri not equal to rj, it means that the two queens in question are not in the same column and same row. But how to make sure they are not in the same diagonal? Note that (ri, i) represents the co-ordinate for a queen on the chessboard. Two queens are in the same diagonal if one of the following is true: ri + i = rj + j or rii = rj – j. I took a 3×3 square and worked out to understand this.

Once these conditions are met, then it is more or less straight forward to do the actual check – loop over all values of column and row – if there is any failure, backtrack and start fresh with new values. Backtracking is one of the most elegant (may not be efficient) solutions to this problem.

A slightly related problem is detecting cycles in a di-graph (or a simple graph for that matter): This again takes a node, puts it in the list and tries to find its neighbors and adds them to the list, when it sees any neighbor (to be added) as the initial node, there is a cycle and it is noted. I will shortly come up with code for both of these problems.

Some Interesting Questions to Keep in Mind

when studying probability. Coursera’s course on Biostatistical bootcamp highlights the importance of asking the following questions:

  • What is being modeled as random?
  • Where does this attributed randomness arise from?
  • Where did the systematic model components arise from?
  • How did observational units come to be in the study and is there importance to the missing data points?
  • Do the results generalize beyond the study in question?
  • Were important variables unaccounted for in the model?
  • How drastically would inferences change depending on the answers to the previous questions?

Asking these questions will help us truly understand the subject of probability and statistics in the context of problem being modeled.

Deep Procrastination

All my post-graduation I was confused whether I am in deep procrastinating mode or suffer from anxiety and depression. But as I moved on, I found that the former is true. Deep procrastination is a killer. At the same time, it is a show stopper kind of thing in life that signals that something is not good. Cal Newport explains it:

Deep procrastination is not the standard urge to goof off that afflicts every college student. It’s much more powerful. A student suffering from deep procrastination will delay important work to an excessive degree. He won’t start studying until late the night before or will delay paper writing until the sun is about the rise. After a while, he might begin to chronically miss deadlines, and find himself constantly negotiating with professors about extensions. Sometimes it gets so bad that he misses the extended deadlines — failing courses instead of completing the required assignment. No matter how dire the stakes, starting work becomes an insurmountable prospect.

The only cure, as I understand, to this problem is to answer the biggest and the most important question of our lives:

figure out what you really want to accomplish at college, then choose your path based on an honest answer to this question.

Whatever is said of college is true about profession and life in general.

Calibrating Loops Per Jiffy in Linux Kernel

I was going through the kernel code of calibrating the delay loop and was just amazed at the beauty of it. Thought, would share my joy here. Here is the source code for the warm up before calculation:

        while ((loops_per_jiffy <<= 1) != 0) {
            /* wait for "start of" clock tick */
            ticks = jiffies;
            while (ticks == jiffies)
                /* nothing */;
            /* Go .. */
            ticks = jiffies;
            __delay(loops_per_jiffy);
            ticks = jiffies - ticks;
            if (ticks)
                break;
        }

The above loop tries to set the most possible significant bit in loops_per_jiffy variable such that the resultant number (loops_per_jiffy) when passed to __delay function, will cause the __delay to take more than one jiffy to execute. In other words, starting from LSB, it moves the bit to the left (in effect doubling loops_per_jiffy) in every iteration such until this number is big enough to cause __delay function to take more than one jiffy. The void while loop inside is basically to let go of the current jiffy – that is, to start at the beginning of the next jiffy time window, by letting go of the current jiffy window (we don’t know where in the current jiffy window we are so if we start __delay now, then our loops_per_jiffy calculation is skewed).

Lets take a small notation here: lpj_x is loops_per_jiffy variable with only bit x set. And LPJ be the closest value of the variable that can cause the __delay function to lapse exactly jiffy unit of time.

When we come out of loop, the following assertion is true: lpj_x causes __delay to cross a jiffy and lpj_(x-1) does not. Does this mean that lpj_x is the exact delay that can cause a jiffy to pass? No. That exact LPJ is somewhere between lpj_x and lpj_(x-1). So, starting from here we have to find LPJ further.

And here in comes another piece of beauty.

        loops_per_jiffy >>= 1;
        loopbit = loops_per_jiffy;
        while (lps_precision-- && (loopbit >>= 1)) {
            loops_per_jiffy |= loopbit;
            ticks = jiffies;
            while (ticks == jiffies)
                /* nothing */;
            ticks = jiffies;
            __delay(loops_per_jiffy);
            if (jiffies != ticks)   /* longer than 1 tick */
                loops_per_jiffy &= ~loopbit;
        }

Since lpj_x is a loose upper bound on LPJ, we proceed to calculate a tighter upper bound. The above loop does it. To understand this, consider x to be 3. Then lpj_3 8 – it is 1000 in binary. And lpj_2 4 is 100. The more precise LPJ is between lpj_3 and lpj_2. We would start from 4 and proceed to 8. We start from lpj_2 and set further lsbs and see it comes close. That is, we start with 4, make it 6 and then 7 (100, 110 and 111). Although we miss out on some numbers, this is apparently considered to be good enough an approximation.

That is what the loop does exactly. As usual, the inner void while loop is to align ourselves to the beginning of a jiffy window.

At the end, we will have lpj close to LPJ.

The only other magic sauce here seems to be __delay. It is just an instruction that is used to some CPU intensive (or CPU only) operation for so many iterations. We use that as a tool to tune loops_per_jiffy.