Linux Calling...: 2014

Tuesday, June 3, 2014

Merge Sort

Merge sort is one of the efficient sorting algorithms compared to other sorts as Insertion, Selection or Bubble Sort. The algorithm is divide and conquer. We divide the array into 2, sort the 2 arrays and then merge them to form the final result. This is of course a recursive technique. As you can see in the below code, the function merge_sort() is called recursively.
The time complexity is O(nlogn).
In this example, the array is self populated with random values with the help of srand() series of functions after taking the size of the array from the user.

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "time.h"

typedef enum _return_type
{
  ERROR,
  SUCCESS
}return_type_t;

#define NULL_CHECK(x) { if(!x) return ERROR; }

static int merge(int *a1, int n1, int *a2, int n2, int *a)
{

  int i=0, j=0, k=0;

  while(i<n1 && j<n2){
    if(a1[i] <= a2[j]){
      a[k] = a1[i];
      i++;
    }
    else{
      a[k] = a2[j];
      j++;
    }
    k++;
  }

  while(i<n1){
    a[k] = a1[i];
    i++;
    k++;
  }

  while(j<n2){
    a[k] = a2[j];
    j++;
    k++;
  }
  return SUCCESS;
}

static int merge_sort(int *a, int m)
{
  int *a1, *a2;
  int n1, n2;

  if(m<2) return SUCCESS;

  n1 = m >> 1;
  n2 = m - n1;

  a1 = malloc(sizeof(int) * n1);
  NULL_CHECK(a1);
  a2 = malloc(sizeof(int) * n2);
  NULL_CHECK(a2);

  int i=0;
  for(i=0; i<n1; i++)
    a1[i] = a[i];

  for(i=0; i<n2; i++)
    a2[i] = a[i+n1];

  merge_sort(a1, n1);
  merge_sort(a2, n2);

  merge(a1, n1, a2, n2, a);
  free(a1);
  free(a2);

  return 0;

}

static void display(int *a, int n)
{
  int i;
  for(i=0; i<n; i++){
    printf("%d ", a[i]);
  }
  printf("\n");
  return;
}

int main(int argc, char **argv)
{
  int *a;
  int i,n,num;

  scanf("%d", &n);
  a = malloc(sizeof(int) * n);
  NULL_CHECK(a);

  srand ( time(NULL) );

  for(i=0; i<n; i++){
    num = rand() %1000 + 1;
    a[i] = num;
  }

  //display(a, n);
  merge_sort(a, n);
  //display(a, n);

  free(a);
  return 0;
}

Monday, April 14, 2014

Squid HTTPS/SSL Proxy

A customer was reporting poor performance with one of the product I am working on when he routes the traffic via squid proxy. What is a proxy? Why Squid? Just google it :). Let's get down to business.

Below is the topology. This is a basic setup so that you can get started.

All the machines here are running Kali Linux.

root@maximus:~# uname -a
Linux maximus 3.12-kali1-686-pae #1 SMP Debian 3.12.6-2kali1 (2014-01-06) i686 GNU/Linux

Important while installing the Squid Proxy
Try to get the source file and compile it. While configuring, make sure to give the following switches to ensure SSL is supported.

--enable-ssl --enable-ssl-crtd --enable-icap-client --with-default-user=squid

--with-default-user
You can specify any user you want, just make sure after the installation is done, that user is created and necessary permissions are given. Mainly "that user" will require permission to write to the log directories which is by default /var/logs/

Follow these to get the Squid Proxy installed

wget http://www.squid-cache.org/Versions/v3/3.4/squid-3.4.4.tar.gz
tar -xzvf squid-3.4.4.tar.gz
cd squid-3.4.4
./configure --prefix=/ --enable-icap-client --enable-ssl --enable-ssl-crtd --with-default-user=squid
make
make install

Once done, execute squid -v and squid -h to ensure we have ssl enabled and also to know the path of the configuration file

root@maximus-neptune-21:~# squid -v
Squid Cache: Version 3.4.4
configure options:  '--enable-ssl' '--enable-icap-client' '--enable-ssl-crtd' '--with-default-user=squid' '--prefix=/' --enable-ltdl-convenience

root@maximus-neptune-21:~# squid -h
Usage: squid [-cdhvzCFNRVYX] [-s | -l facility] [-f config-file] [-[au] port] [-k signal]
       -a port   Specify HTTP port number (default: 3128).
       -d level  Write debugging to stderr also.
       -f file   Use given config-file instead of
                 /etc/squid.conf
       -h        Print help message.

We are good to go!

This is what happens when the client tries to connect to the proxy server.

Client tries to connect to the proxy server via https://172.20.73.172:3128
The proxy server, intercepts this and establishes a secure connection between the Client and itself. Then the proxy server creates another secure back-end connection to the actual server.

Though this is transparent mode, you can see that it is not "entirely" transparent to the the client. The reason I am connecting to the proxy server and port explicitly is because I didn't want the readers to get confused with the iptables. This is known as ssl-bump or man in the middle. The original connection from the client is intercepted by the proxy server. So, if anyone hacks into the proxy server, he can get all the data easily. Like, I have already said, this is only for lab testing purpose.

Below is the minimal configuration file /etc/squid.conf

visible_hostname maximus-neptune-21

# This acl will allow anyone. Add the required acl's you want to restrict the access.
acl EVERYONE src all

# This is to tell the Proxy that do not cache the pages. This is not generally used.
cache deny all

# This is where the acl is getting into action
http_access allow EVERYONE
http_access deny all

# 3128 is the https port squid proxy will listen to. You need to generate the key and certificate, these are used to create a secure connection with the client. I am using SSLv3 and hence version=3
https_port 3128 intercept ssl-bump cert=/etc/squid/ssl/public.pem key=/etc/squid/ssl/private.pem version=3

# This is where we specify the server list. I am using SSLv3 and hence sslversion=3
cache_peer 100.1.1.11 parent 443 0 no-query originserver ssl sslversion=3 ssloptions=NO_SSLv2,NO_TLSv1_1,NO_TLSv1_2

# I had some issues with the CA, hence disabled the verification. I don't recommend you do this if it a live environment.
sslproxy_cert_error allow all
sslproxy_flags DONT_VERIFY_PEER,NO_DEFAULT_CA

# This will ensure that the connection is send/created to the actual server.
never_direct allow all

Start the Squid Proxy in foreground mode with certain debug level enabled. This will help in finding any configuration syntax errors or any handshake failures etc

squid -NCd1

Check /var/logs/access.log for more debugging information.

For more information, please check http://www.squid-cache.org/
Reference : http://www.squid-cache.org/

Friday, February 21, 2014

Convert UTC Date to Seconds

One of the primary ways used to compare dates is to convert the date to seconds and then do the comparison. The GNU date has an option +%s to convert the given date to seconds since epoch. But sometimes GNU date is not available in all the systems and they can't install it due to restrictions in the working environment. The next option is to use strftime() of gawk or perl. The same issue may exist with gawk/perl also, i.e. they may not have the required libs or things of that sort.

The following script which I call utc_to_sec will convert the given UTC date to seconds using the basic arithmetic.

#!/bin/bash
# utc_to_sec v1.0
# Script to convert time to seconds
# TZ should be UTC
#
# ./utc_to_sec 2014-02-20  01:42:02
# 1392860522

EXE=${0#*/}
usage()
{
  echo -e "\nConvert date to seconds since epoch"
  echo "  Usage : $EXE yyyy-mm-dd hh:mm:ss"
  echo -e "  ** TZ default UTC **\n"
  exit
}

do_everything()
{
  echo $1 $2 | awk '

    BEGIN{
      year=hh=1; mon=mm=2; day=ss=3
      m_lo[4]=m_lo[6]=m_lo[9]=m_lo[11]=1
      m_hi[1]=m_hi[3]=m_hi[5]=m_hi[7]=m_hi[8]=m_hi[10]=m_hi[12]=1
    }

    function no_of_days_in_year(input)
    {
      leap=0
      if ( input%4 == 0 ){
        if ( input%100 == 0 ){
          if ( input%400 == 0 ){
            leap=1
          }
        }
        else{
          leap=1
        }
      }

      return (365+leap)
    }

    function no_of_days_in_month(in_mon, in_year)
    {
      if(m_hi[in_mon]) val=31
      else if(m_lo[in_mon]) val=30
      else {
        val= no_of_days_in_year(in_year)>365?29:28
      }
      return val
    }

    function validate(a_date, a_time)
    {
      if( a_date[year]<1970 || a_date[mon]<=0 || a_date[mon]>12 ||
          a_date[day]<=0 || a_date[day]>31 ||
          ( m_lo[a_date[mon]] && (a_date[day]>30) ) ||
          ( a_date[mon]==2 && a_date[day]>29 ) ||
          a_time[hh]<0 || a_time[hh]>23  ||
          a_time[mm]<0 || a_time[mm]>=60 ||
          a_time[ss]<0 || a_time[ss]>=60 ){
        print -1
        exit
      }
      if(no_of_days_in_year(a_date[year])<=365 && a_date[mon]==2 && a_date[day]>28){
        print -2
        exit
      }
    }

    END{
      split($1, a_date, /-/)
      split($2, a_time, /:/)
      validate(a_date, a_time)

      #no of days in a year
      for(i=1970; i<a_date[year]; i++)
        sum_days+=no_of_days_in_year(i)

      for(i=1; i<a_date[mon]; i++)
        sum_days+=no_of_days_in_month(i, a_date[year])

      sum_days=sum_days+a_date[day]-1
      seconds = (sum_days*24*60*60) + (a_time[hh] * 3600) + (a_time[mm] * 60) + a_time[ss]
      print seconds
    }
  '
}

( [[ $# -ne 2 ]] ) && usage
seconds=$( do_everything $* )
[[ ${seconds:-0} -lt 0 ]] && echo "Invalid data..." && usage
echo $seconds

Output

root@maximus:~/scripts# ./utc_to_sec 2037-12-31 23:59:59
2145916799
root@maximus:~/scripts# date +%s -d "2037-12-31 23:59:59 UTC"
2145916799
root@maximus:~/scripts# ./utc_to_sec 2014-02-19 12:13:56
1392812036
root@maximus:~/scripts# date +%s -d " 2014-02-19 12:13:56 UTC"
1392812036
root@maximus:~/scripts# ./utc_to_sec 1970-01-01 00:00:00
0
root@maximus:~/scripts# date +%s -d "1970-01-01 00:00:00 UTC"
0
root@maximus:~/scripts# date +%s -d "1990-01-01 23:40:44 UTC"
631237244
root@maximus:~/scripts# ./utc_to_sec 1990-01-01 23:40:44
631237244

Execution time

root@maximus:~/scripts# time date +%s -d "2037-12-31 23:59:59 UTC"
2145916799

real    0m0.010s
user    0m0.004s
sys     0m0.008s

root@maximus:~/scripts# time ./utc_to_sec 2037-12-31 23:59:59
2145916799

real    0m0.023s
user    0m0.012s
sys     0m0.004s

HTH

Wednesday, January 29, 2014

Determining IP address range from Subnet/CIDR

Script to find the IP address range from the given Subnet.

There are few functions which can be reused like
1. Convert IP to Decimal ip_to_int()
2. Convert Decimal to IP int_to_ip()
3. Netmask to CIDR to_cidr()

#!/bin/bash
# http://linuxcalling.blogspot.in/
# Script to find the IP address range
# Script : ip_range
# Usage  : ip_range <IP> <Subnet> [0|1 print range]
# Ahamed (ahamed.en@gmail.com)

usage()
{
  EXE=${0#*/}
  echo "Usage: $EXE <IP> <Subnet> [0|1]<print range>"
  echo "   eg: To display the IP address range"
  echo "       $EXE 192.168.1.1 255.255.140.0"
  echo "   eg: To display the IP address range with entire range"
  echo "       $EXE 192.168.1.1 255.255.140.0 1"
  exit
}

[ $# -lt 2 ] && usage

echo $1 $2 $3 | awk '

  BEGIN{
    BITS=8
    mask_add[0]=valid_subnet[0]=0
    for(i=BITS-1;i>=0;i--){
      k=or(k,lshift(1,i))
      mask_add[k]=BITS-i
      valid_subnet[BITS-i]=k
    }
  }
  function validate_subnet(input)
  {
    split(input, oc, ".")

    if(oc[4] > oc[3] || oc[3] > oc[2] || oc[2] > oc[1]){
        print "Invalid Subnet: ",input
        exit
    }
    for(j=1; j<=BITS/2; j++){
      for(i=0;i<=BITS;i++){
        if(!xor(oc[j],valid_subnet[i])){
          break;
        }
        err++
      }
      if(err == (BITS+1)){
        print "Invalid Subnet: ",input
        exit
      }
      err=0
    }
  }

  function to_cidr(input)
  {
    split(input, oc, ".")
    ret=mask_add[oc[1]]+mask_add[oc[2]]+mask_add[oc[3]]+mask_add[oc[4]]
    return ret
  }

  function ip_to_int(input)
  {

    split(input, oc, ".")
    ip_int=(oc[1]*(256^3))+(oc[2]*(256^2))+(oc[3]*(256))+(oc[4])
    return ip_int

  }

  function int_to_ip(input)
  {
    str=""
    num=input
    for(i=3;i>=0;i--){
      octet = int (num / (256 ^ i))
      str= i==0?str octet:str octet "."
      num -= (octet * 256 ^ i)
    }
    return str
  }
  {
    ip=$1
    mask=$2
    range=$3

    validate_subnet(mask)

    cidr=to_cidr(mask)
    diff=32-cidr
    no_of_ip=2^diff

    ip_int=ip_to_int(ip)
    ip_mask=and(ip_int, (2^32 - 2^diff))

    ip_start=ip_mask
    ip_end=ip_mask+no_of_ip-1

    print "No of IPs\t"(no_of_ip-2)
    print "First IP\t" int_to_ip(ip_start+1)
    print "Last IP\t\t" int_to_ip(ip_end-1)
    print "Subnet\t\t" int_to_ip(ip_mask)
    print "Broadcast\t" int_to_ip(ip_end)

    if(range){
      print "\nIP address range -- START --\n"
      curr=ip_start
      i=0
      while(curr<=ip_end){
        printf int_to_ip(curr)"\t"
        if(j++%4 == 0) printf "\n"
        curr+=1
      }
      print "\nIP address range -- END --"
    }
  } '

Script Usage

[root@maximus] → ./ip_range 192.168.1.1 255.255.255.224
No of IPs       30
First IP        192.168.1.1
Last IP         192.168.1.30
Subnet          192.168.1.0
Broadcast       192.168.1.31


[root@maximus] → ./ip_range 192.168.1.1 255.255.255.224 1
No of IPs       30
First IP        192.168.1.1
Last IP         192.168.1.30
Subnet          192.168.1.0
Broadcast       192.168.1.31

IP address range -- START --

192.168.1.0     192.168.1.1     192.168.1.2     192.168.1.3
192.168.1.4     192.168.1.5     192.168.1.6     192.168.1.7
192.168.1.8     192.168.1.9     192.168.1.10    192.168.1.11
192.168.1.12    192.168.1.13    192.168.1.14    192.168.1.15
192.168.1.16    192.168.1.17    192.168.1.18    192.168.1.19
192.168.1.20    192.168.1.21    192.168.1.22    192.168.1.23
192.168.1.24    192.168.1.25    192.168.1.26    192.168.1.27
192.168.1.28    192.168.1.29    192.168.1.30    192.168.1.31

IP address range -- END --

[root@maximus] → ./ip_range 192.168.1.1 255.255.0.0
No of IPs       65534
First IP        192.168.0.1
Last IP         192.168.255.254
Subnet          192.168.0.0
Broadcast       192.168.255.255