Archive for the ‘Thoughts’ Category

Posted on June 14, 2013 - by Sarath

megacmd – a mega.co.nz storage service command-line client

Hey everyone,

I have been recently working on a command line client for Mega cloud storage service. If you are not familiar with mega, let me give you a brief intro. Mega (https://mega.co.nz) is a storage service founded by Kim Dotcom exactly one year after MegaUpload was raided by US government and seized his entire property. The case against him was that he hosted an upload service which was being misused by people and become the source of piracy. He recently came up with a nice storage solution out of New Zealand which encrypts data at client side and transfers to the server. At mega server side, nobody will be able to decrypt your data since it is encrypted at client side. Your password is the encryption key used for the data. The downside is that, once you forget the password you will not be able to reset your password or recover you data back.

I started using Mega from day it was launched and was very much impressed by its service. The major factor that impressed me was speed and free storage space. When all the major cloud storage service providers provide 5Gigs of max free quota. Mega provides 50Gigs of quota, which is awesome. The another part of awesomeness is the speed. I compared download/upload speed by downloading same files in Google drive, dropbox, etc. Mega is around 8X faster than all of them. Mega supports multiple parallel connections for download and upload, thereby helps to increase speed further. Currently, Mega.co.nz is a client web application written in Javascript and runs completely out of browser. Chrome and Firefox works perfect for mega. Just signup using just email and password and get started in 2 mins.

Mega provides an open API service for clients to manage mega account. The current Javascript implementation makes use of APIs to perform all actions on mega account within the browser. They have a limited bare minimum developer documentation available at https://mega.co.nz/#developers. I loved the security aspect, storage quota and speed perspective of Mega. But I wanted a command-line client to access Mega, which I found missing. I am used to s3cmd utility, which is a command-line utility to perform file transfers to Amazon S3. I started writing a utility called megacmd in Golang. Go is a statically typed, at the same time highly flexible interesting language that I have been hacking around for sometime. Go is C like language that provides concurrency, synchronization by communication and garbage collection as part of the language. Having looked at AWS S3 protocol, Mega is more complicated to implement than S3 client. S3 provides a simple object store APi to provide object path and value to be stored. But, mega does more sophisticated things like keeping the filesystem tree as metadata.

I will run through a very quick overview of how a client interacts with Mega service and its architecture.

Mega uses json a the unit of API request and response. It uses the following request and response formats:

A user has to initialize a user session by login with username and password. A login request consists of username and a custom hash(password). It responds with sessionId, RSA private key and user master key. All of them encrypted. User master key is a symmetric encryption key for decrypting keys specific to all the files stored by a user account. In order to decrypt the sessionId, first compute the password hash, and decrypt the master key using the password hash. Once master key is decrypted, use that to decrypt the RSA composite key. Composite RSA key contains p,q and d components (Read http://en.wikipedia.org/wiki/RSA_(algorithm)#Operation ), all of them encoded in multi-precision integer format. Once you decode these components, we can decrypt the sessionId. SessionId is also represented as multi precision int (m). Hence, sessionId = (m ^ d) % n where n = p*q. Since mega uses json for request and response, it should be ascii encoded. Hence, all binary data is represented as a specialized base64url encoding with padding characters (=) removed. Hence sessionId is converted into base64url encoding. Once we decode sessionId, it used used for all the mega file operations. For identifying the requests, mega requires a id to be passed along with requests which needs to be incremented everytime. Client requests are post to the url https://eu.api.mega.co.nz/cs?id=seqid&sid=sessId. Mega uses 128 bit block AES encryption all over the place.

Mega stores files in node hierarchical parent-child model like standard filesystems. Mega has three root nodes, either Mega Cloud, Trash or Inbox. Each node can be either a folder type, file type or root. Mega stores each node as a block of bytes with a size, timestamp, key, attribute, parent, node type identified by a hash. Attribute contains encrypted filename by using encrypted file key. User master key is used to decrypt the file key. Using the file key, file content and attribute can be decrypted. The file key is a composite key which contains additional initialization vector and meta-CBC-MAC (Message Authentication Code) data in case of a file node. The actual file content is encrypted in AES counter mode using this init vector. CBC-MAC meta data is used for integrity verification of the file.

Once you get a session ID, we can use file list APi to download meta data about all the nodes in the filesystem tree. The response contain, one metadata entry per node.

To download a file, we should send a request with node Hash. The response will contain a url at which we can download the file. The file should be downloaded in chunks of size, 128K / 384K / 768K / 1280K / 1920K / 2688K / 3584K / 4608K / … (every 1024 KB). This is to allow integrity checks per chunk. While downloading each chunk, it should be decrypted using AES-Counter mode using the file key.

To upload a file, we should generate a random key to be used as file key and initialization vector. An upload request with file size is issued and it returns a response with a url at which we can do uploads. Uploads are done in chunks as download by posting encrypted data at http://uploadurl/chunkstart-chunkend. Once all the uploads are complete, we receive a completion handle. We should post a file upload completion request with completion handle, meta-MAC, attributes, parent hash, etc to finalize the upload.

There are other operations like delete, move, update attribute, etc available.

Since we keep a local copy of entire filesystem, we need a way to update our local cache of filesystem when some other client using the same account updates the filesystem by adding, removing or updating files or folders. For eg, if we login to mega.co.nz account in two browsers with same credential, we can see that if we make any change on one browser that gets reflected in other as well. In order to provide filesystem change notification, mega provides a mechanism for server to talk to the client.

The client should hit an API url, https://eu.api.mega.co.nz/sc?sn=. Sn is received from this API call or from list filesystem API call. This API will respond with a wait url or a list of file node operations. If it provides a wait url. We should perform a get request to that wait url. This get request will block until a filesystem event occurs. Once it returns, it should query the API to get the list of events and perform those events in the local filesystem copy to synchronize with the filesystem at the server side. Since documentation is minimum, I had to download the javascript implementation and had to make out the working myself reading code.

About megacmd utility..
Mega service provides a mechanism to access the Mega FS tree in a model with hash identifiers. But they are not readable and we need a path name representation using resource URIs. So I initially wrote a library for go called go-mega which provides Mega API abstraction in terms of hash and filesystem tree. Then, I wrote another go package called megaclient which abstracts in terms of file path and it provides similar operations as s3cmd. Code for both can be found in my github.

go-mega – https://github.com/t3rm1n4l/go-mega
megaclient – https://github.com/t3rm1n4l/megacmd

megacmd is a command-line utility written on top of megaclient package. The usage for megacmd is as follows:

Downloadable binaries for GNU/Linux and Mac OSX are available.
Please read more and find documentation at https://github.com/t3rm1n4l/megacmd

If you find any bugs or would like to contribute to the project, please feel free to file an issue or send a pull request at github.

Posted on September 24, 2012 - by Sarath

Implementation overview of redirection and pipe operators in shell

I have been always fascinated about the design of UNIX. I am still curious and enjoy the philosophy and the idea of ‘Write programs that do one thing and do it well’. Aim of this blog post is to walk through some interesting aspects on implementation of file descriptors and to illustrate how gracefully that design helps to build interesting unix shell methodologies. For any process, there are three default file descriptors. Stdin – with descriptor number 0, Stdout – with descriptor number 1 and Stderr with descriptor number 2.

Let us go through some basic system calls. All the system calls explained below are not exact syntax. Please refer man for correct function prototype.

1. fork()
The fork system call creates another copy of current process and mark the new process as child of parent process which called fork. This system call returns zero in the child process and return child’s pid in the parent process. It copies everything including file descriptors, and virtual memory. If a process tries to write any virtual memory page, it will do a copy on write to create copy of that particular page for that process space.

2. exec(binary_path)
The exec system call overwrites the current process with executable image from a file. Eg. if you run exec(“/bin/ls”). It will overwrite the memory code image with binary from /bin/ls and execute. The file descriptor table remains the same as that of original process.

3. open(file, mode)
Opens a file and creates a file descriptor associated with the file.
IMPORTANT: By design, when the kernel allocates a file descriptor, it will create the fd with next smallest available file descriptor number.

4. close(fd)
Closes the open file descriptor

5. dup(fd)
The dup system call creates a file descriptor that is duplicate of given fd passed as argument.

6. pipe(int arr[2])
Creates a pipe, and stores the read descriptor in array location zero and write descriptor in array location one.

7. read(fd, buff, len)
Reads len bytes to buff from file descriptor fd.

8. write(fd, buff, len)
Writes len bytes from buff to file descriptor fd.

Let us go through some interesting shell features that we use frequently and look at their implementations.

1. Redirections

$ cmd1 > stdout.txt
The above command redirects stdout to file stdout.txt

For implementing the above operation, we should be able to link stdout of cmd1 with file descriptor of stdout.txt opened with write mode.

Let us look at the code.

 

$ cmd1 2> stdout.txt
The above command redirects stderr to file stdout.txt

 

$ cmd2 > stdout_stderr.txt 2>&1
The above command redirects both stdout and stderr to file stdout_stderr.txt

 

$ cmd3 < input.txt
The above command redirects data from input.txt to stdin for cmd3.

 

2. Pipe

$ cmd1 | cmd2
This command says that cmd2 will receive stdin from stdout of cmd1.

Aren’t you feeling awesome?
With simple design, without making any code change to individual programs, it is possible to connect input and output streams to individual programs. Hats off to designers of UNIX.

Posted on November 28, 2011 - by Sarath

Preparing for your first-job interviews

It has been a long time since i wrote a blog entry. Here is some interesting piece for final year computer science students.

Getting a job is one of the happiest things in the life of a final year guy. I also had such wonderful moments during my final year. I would like to share some bytes of info that can help you out.

University/College studies and your first job

In the long four years of engineering course, you study a lot of things. Lot of junk and little good. In reality very few subjects really help and are useful for a computer science job. For getting a job, you will need even fewer set of subjects among them. Hence, finding a job is easy. But you have to master the subjects that you love. I will list out the few subjects that will help you find a job.

Data structures, Algorithms and Analysis, Operating Systems, Computer Networks, C Programming, Object Oriented Programming, Database Management systems, Compilers (Optional), Distributed Computing (Optional), Microprocessors (Optional)

The perspective of current education system and the industry goals diverge very much. In colleges, we study for obtaining some marks. The teachers also have the goal to help their students to obtain marks rather than learning something that may help gain the ability to solve computer science programs using their skillsets. In industry, the ultimate goal is to produce good quality software within short span of time. That means, the skill requirements are good coding skills, ability to understand and solve problems algorithmically with analysis to validate and come up with optimal and practical solution. To grow up as a software engineer that meets the industry requirements, the education system at college fails.

You have to put good self effort to gain the skillsets and the passion for learning. You should have good coding skills with proficiency in one or more programming languages, understanding of standard algorithm techniques at basic level. Let us have a run through objectives during preparation for a job.

Preparing your CV

Curriculum Vitae is important while applying for a job. Your CV is a blueprint of your personality. It is the first phase during a recruitment that gives the recruiters an overall view of your skillset and your background. Hence, it is worth to spend few days in preparing your CV. Note the following things while preparing your CV.

Use a different layout from other candidates who are applying for job along with you. Make yourself different from others. Write a career objective that states your interest. If you are applying for a specific role, Write a highlights section as the first section in your CV. Highlights should list out important achievements and your skillsets in bullets. This section is indented for HR who screens your resume. The next section can be ‘Skills’, which lists out your skill sets and programming languages. Write in an order separated by commas such that less proficient technologies should come last. You should also mention the operating systems you are familiar with. The next section can be Achievements. But you can move this section to the end of the resume if you think that you do not have considerable good technical achievements for highlighting. The next section should be Projects. This is the most important section in your resume. You should spend some time in writing this section. You should specify the title of the project, duration (optional), the technologies used, a summary of the project describing the project in few words, and project highlights section. The project highlight section should list key features about your project listed as bullets. Write them in an impressive manner stating the facts properly.

Eg.

1. Implemented a H.263 video streaming library for android 2.3

2. Implemented video frames collector and device mapper that converts video stream to v4l linux device

3. Tested on Android 2.3 and found that 25 % performance improvement than the bundled video library

If you have lot of numbers to showcase the benchmarking or awesomeness of your project. that is great. If your project bagged some awards or deployed for some good numbers of users, mention that figures and achievements in the highlights.

I would prefer to order the project in the order of significance rather than chronological order. After the project section, have an achievements section which lists all technical and non-technical achievements. You can split your achievements section into subsections like publications, events, etc. Write the educational background section as the last section of your resume. Because it is the most insignificant portion of a resume if you are looking for a good computer science job. It states few figures that indicate your marks which is not an indicator of your knowledge.

Tips for interview preparation

You should acquire sound knowledge about few of the subjects listed in the earlier section of this article. Usually recruitment process consists of a written test paper followed by a couple of interviews. Focus of your preparation should be based on the job position you are applying for. If you are preparing for a developer interview, you should be sound with Data Structures and Algorithms. You might be bored with the subject since you attended some boring series of lectures from colleges to grab marks. Try again approaching the subject in a different manner. You will definitely enjoy it. Start reading the book ‘Programming Pearls’ before you start preparing. It will give you a wonderful insight you never had before. I will focus on developer interviews.

Companies usually ask some technical aptitude questions, puzzles and questions from the subjects along with the test paper. Most of the questions will be repeated. Search for programmer interview aptitude questions and brain teasers for programmers on Google. You will find a good list. Try to solve them. Learning algorithms are not hard. But understanding the use cases and ability to apply them to solve problems require some effort and practice. Whenever you learn an algorithm, try to implement it using a programming language. For practicing algorithms to coding, you should use some highly object oriented and simple languages. The best language you can learn is python. You can practice coding algorithms with Python without any implementation complexity and it will look like a pseudo code. Learn python today. Seriously it won’t take more than a day to learn things that you will require to implement algorithms. C is a great language. Implementing certain Data structures or algorithms in C gives you a good experience to code well in C. I will write some notes on few algorithms that you should try implement in C. Algorithm analysis for important algorithms should be understood. You should know the worst case complexity (Find out the worst cases in the case of a particular algorithm), Best Case complexity (Also the best case) and the average case complexity (Also the average case example). Space complexity of the algorithm should be known in order to select the best algorithm according to problem environment.

 

Data Structures and Algorithms

Binary Search

This is a very important algorithm you can apply at many different problem environments you never expect.

Understand the runtime complexity for the Binary Search and understand how to derive the complexity from algorithm. Note that it can be applied for only sorted lists. Learn how to apply Binary Search in a Rotated Sorted List by using recursion and how the algorithm complexity varies. Implement Binary Search using C for a list of strings. You should familiarize the terms in place sorting, stable sorting and also should understand which sorts come into these categories.

Insertion Sort

Understand the algorithm and derivation of algorithm analysis. Compare it with Card game in which we move the cards to the suitable position. Keep the example in mind and apply to similar problems. In Insertion sort, we sort the element set by consequently moving the current element to the appropriate position in an already sorted set.

QuickSort
QuickSort is a very important sorting technique. It uses divide and conquer technique. Divide the given set of elements into smaller sets recursively and apply comparison and swap. When comparison and swap is performed to formulated smaller sets, it results in the larger sorted set. Learn algorithm analysis. Learn how to find kth smallest element by modifying the Quicksort algorithm in O(nk) complexity. Find out mean of a set of elements in O(n) by modifying the above problem.

MergeSort
Mergesort is also a divide and conquer sorting technique. The concept is to merge two sorted list to obtain larger sorted set. By dividing the given array into smaller subset by recursion, smaller subsets are formed. Merging the subsets from lower level to higher level, we obtain sorted array. Learn algorithm analysis. Note that merge sort takes an extra array. Hence this is not an in place sorting. It has O(n) space complexity. You should practice problems related to merge sort. Eg. You are given two sorted arrays with size n and 2n. The second array contain n elements in the positions 0 to n-1. Now without using extra space, formulate the elements in 1st and 2nd array into 2nd array and return a sorted array of size 2n.

HeapSort
Heapsort is an interesting sorting technique. Heap is a tree in which parent node is always >= child nodes (called as max-heap) or parent node is always <= child nodes (called as min-heap). This is the basic property for a heap. Let us have an overview of how to create a heap and manage it. When we need to add an element into an existing heap, we add the element as root or to the rightmost bottom element in the heap. Then apply heapify operation. Heapify operation can be of two types: shiftup and shift down. When we add a new element to an existing heap as root element, we perform shift down operation. Shift down operation performs a traversal from root level to bottom level, at each level of traversal, it compares whether heap property is violated, if so it will perform swap between parent node and child node to obey the heap property. Hence the element we added as root will move to the accurate position when the traversal reaches the bottom level. If we add a new element to the bottom right element, we need to perform a shift up to position the element to the right position. We traverse from parent in the bottom level to the root, by checking the heap property at each level and swapping elements to meet the heap property, we get a balanced heap when traversal reaches the top element.

Heapsort makes use of these operations to obtain a sorted set. Let us assume we have a heap (1,n). the root element will be the highest value (max-heap). Hence it will be the last element in the sorted list. We swap the root and the last element. Now the heap property is lost. But the nth position of array has the correct element in the sorted list. So we exclude nth element and heapify the heap(1,n-1) by using shift down operation. Because the root element is the one breaking the heap balance. After doing heapify 2nd time, we get 2nd highest element as root element. Now swap root element with n-1 element. Hence n-1, nth elements are 2nd largest and largest elements. Now exclude the n-1 and nth element, heapify heap(1,n-2). Follow the procedure until the newly formed heap size become one. You will get a sorted list. Read the chapter Heaps from Programming Pearls (It will give you a wonderful insight). Practice the problems: Find kth largest element from a given unsorted array. Implement priority queues.

External Sorting

External sorting is an important sorting technique used when the amount of data we need to process is greater than the available memory. For eg, we have 1GB of integers and 256MB of RAM. Hence it is clear that we cannot load entire list of numbers into ram and perform in memory sorting. External sorting techniques are to be used to solve this problem. K-Way merging is one of the simplest methods to solve the problem of RAM < data size. We can split the data into K parts. The part split is performed such that each split is less than the size of RAM. Then we can sort each part individually using any sorting algorithm. Then we can perform a special type of merging to obtain sorted output. Let us see how to perform the merge.

For eg, we split the data into 4 parts and we individually sorted them. Then take the first element from each 4 sorted lists and sort them and find out the lowest element. It will be the first element in the sorted output. Add it to the new list called full sorted array.

Now, from the array from which we obtained the lowest element, take the next element, sort the list again and find out the second lowest element. From the array we obtained 2nd lowest element pop out the next element and sort again to find out the third lowest element. Proceed the process until all arrays becomes empty or one array remains few elements. If an array remains unempty add those elements in the order to the full sorted array. Have a look at implementation code (http://code.google.com/p/kway/)

Bit array technique for solving RAM < Data problem for sorting counting numbers

In a 32 bit system an integer takes 32bits to store an integer and a 64 bit system takes 64bits to store a number. But for storing counting numbers, we can use bit vectors which are formulated by using 64 or 32 bits in an integer. If we set 0th bit in 32 bit we can represent it as 1. If we set 2nd position, we can represent it as 2. If we define an integer array of size N, we can actually represent 32*N numbers using that integer array. In order to sort large number of unique counting numbers we can use, bitsorting by setting and clearing bit positions. If we need to represent 1 to 68 numbers we need only 68 bits. We can represent it using an integer array of size 3. Ie, 32*3 = 96 bits. To set 68^th bit, we know that 68^th bit is situated in the array offset 2. To obtain the array offset, divide the number by 32. (68/32 = 2). Now we need to know which bit position needs to be set in the 32 bits available in array[2]. For that, findout modulus by 32. 68%32 = 4. Hence set the 4^th bit in the array[2]. This can be performed without division and modulus operators by using bit shift operators.

Here we find out i/32 using right shift operator (Each right shift causes division by two. Five times rightshift = division by 2^5 (32) ). By using AND operation with 0x1F, we get 5 Least significant bits, the value of 5 LSB returns in the position in 32 bits. Hence we shift 1 towards that much positions to left and is ORed to do the bit set operation.

Have a look at the implementation code. http://cm.bell-labs.com/cm/cs/pearls/bitsort.c

 

Bit manipulation problems

By using bit manupulation, we can do lot of tricks over numbers. See http://graphics.stanford.edu/~seander/bithacks.html for lot of interesting bit twiddling hacks.

One of the very common problems, is counting the number of set bits in a number.

n&(n-1) will return a number obtained by setting rightmost set bit in number n to zero.

Another problem is to check whether a number is power of 2. For a number which is power of 2, there will be only one set bit in the number. Hence if we do n=n&(n-1), we will obtain zero. Using a single line operation we can identify power of 2 or not.

Hashing

Hash is an important data structure that can be used to solve different problems. When you are asked to find the number of occurrence of numbers in a given list of numbers, you can simply use hash for solving the problem. Iterate through the list of numbers, like:

We can solve many problems in O(n) using hash.
Implementing a hashtable in C is not easy at a first attempt. Try to code yourself a hashtable in C using pointer to pointer.

Binary Tree and Traversals

Binary trees are common interview questions. There are lot of BT based questions. Have understanding of common questions like the following.

* Difference between full binary tree and complete binary tree

* Find out Maximum/Minimum height of a tree (Recursive and Non-Recursive)

* What is the maximum number of elements in a tree with height H.

* Nth smallest/largest element in a binary tree

* Algorithm to find out Least Common Ancestor (LCA)

For your information, Least Common Ancestor is the common node in a binary tree which is obtained by traversing from two selected leaf nodes to the root element.

Linked list problems

- Reversing linked list

Linked lists are also very common interviewer question. First practice to be done for linked list problem is to write a linked list structure in C yourself and implement linked list traversal. Then add functions to reverse the linked list in place as well as by creating new linked list. If you do not want a new linked list, but you only need to print the elements of linked list in reverse order, use a recursive function that can do recursive calls till the end of linked list and print the elements.
Eg.

- Cycle in a linked list

Test for cycle/loop in a linked list is a commonly asked problem. You can initialize two variables as start node for linked list and traverse in a while loop such that while loop ends when one of them becomes null or both variables becomes equal. In the while loop, we traverse two variables with different speed.
(varA=varA->next, varB=varB->next->next)

Have a look at well explained tutorial, ?http://ostermiller.org/find_loop_singly_linked_list.html

Tree traversals

It is very important to understand all the tree traversals and implementation.

1. Preorder traversal

2. Post order traversal

3. Inorder traversal

Traversals can be easily implemented using recursion. But interviewers might ask about non-recursive algorithm. In that case, use stack based algorithm to explain inorder traversal. You can easily implement inorder traversal using stack.

Graph Traversals

Graph traversals are commonly asked in interviews. Have the understanding of Shortest path algorithms.

Depth First Search

In depth first search initially traversal goes deep into deepest node and traversal proceeds. You can use a stack to implement depth first search or else ?you can use recursion to implement this.

Breadth First Search

In breadthwise traversal, you can use it to print the tree in the sorted order. You can use the same algorithm used for depth first search by changing stack into queue to obtain the algorithm for BFS.

Dynamic programming
Dynamic programming is an important algorithm technique to solve a large problem by splitting into smaller overlapping problems. When overlapping small problems are solved, the larger problem solution is obtained. Problems like finding shortest path can be solved using dynamic programming. It usually involves using a storage of subsolutions so that they are used in solving bigger problems which overaps the subsolutions. The dynamic programming is difficult to identify as well as apply to solve problem scenarios. It requires considerable spending of time to learn and master it. When you look into some problems and look at its solutions, you may feel it is not that hard. But when you are given a different problem you may not be even able to identify it can be solved using dynamic programming. Even if you identify, you will find hard to code the problem solution. Hence, give considerable time to work on this one.

Try to learn the problem to find subsets of a set using dynamic programming

Trie data structure
Trie is an interesting data structure that can be used to implement autocomplete feature. You can read more about trie from my older blog post. (Implementing autocomplete with trie data structure)

Conceptual Questions

Lot of conceptual questions are being asked during interviews. It will test your basic knowledge and understanding. Find some of the commonly asked topics

* CPU Scheduling algorithms

* Layers of TCP and OSI network stack

* Understand how Virtual Memory/Paging works

* Understand what happens when you enter a URL on web browser and how website is loaded

* Understand how a computer boots and explain the story

* What is the difference between 32 bit and 64 bit machine and OS

* Understanding TCP/UDP protocol

* Understanding ARP/RARP

* Understand DHCP

* Understand DNS (Recursive, Iterative resolution)

* Understand how email works (POP, SMTP)

* Understand Web 2.0, REST, Thrift, RPC

* Understand IPV4 vs IPV6

Books/References

1. Programming Pearls
Programming pearls is a great book you should read as a computer enthusiast. You will be inspired to learn about data structures and algorithms.

2. Cracking the Code interview
It is a nice book consisting of lots of interesting questions

3. Glassdoor.com
Glassdoor is a great website consisting of lots of questions being asked for different companies. As a first programming exercise, write a perl/python/bash script to parse questions into a text file. I had a python script that I had written long time ago. (Lost that somewhere)

Choosing your first job

Every job interview is a great experience. In my life, i had attended three job inteviews and ended up in receiving 3 offers. Each of the interviews were different experiences. Once you face interviews build positive approach in finding feedback yourself. When you receive multiple offers, put enough effort to understand about what you are going to do with each of the job offers your receive. Choose the job you love to do, so that you never have to work a day in life. Thanks and all the wishes.

You can find few posts about interviews from this blog here, http://www.sarathlakshman.com/category/interview/
I dedicate this blog post to all my juniors in Computer Science Dept, Model Engineering College, Cochin

Image credit: http://www.flickr.com/photos/stevefrog8/

Posted on May 26, 2011 - by Sarath

Protecting yourself from Facebook vulnerabilities

Facebook is a great social networking platform in which each of users have got a profile and wall. Over the recent month, facebook has been flooded with lot of malware applications and spammers. In such a risky environment on Facebook, it is very important to understand how to protect ourself from being the target.

Spam and Malware
To keep away from spammers and malware, the best mode of protection is to keep away from clicking untrusted and doubtful links and posts. Do not click ‘Allow’ blindly when some of application asks for permissions to access. Always read the type of permissions that an application uses, when it pops up ‘Allow’ – ‘Deny’ window. Give Allow permissions only to the trusted users. If you are not aware of how a facebook application works, here is short description. Facebook is a platform which provides several interfaces to the application developer to access the data related to users, pages, friends, events, photos, etc (The SocialGraph API). The application developer uses the API and writes the program that can manipulate the data provides through Facebook. They applications are hosted on the developer’s own servers. The facebook team doesn’t look at the application code to see what are these applications doing internally. Using the data access limits specified by the Application permissions, the developer can do any manipulations using the data.

Facebook Mobile – Vulnerabilities
Facebook mobile is an additional interface that Facebook facilities to use you mobile device to update wall, add friends, reply to friends, comment, upload, etc. There are good number of activities that facebook mobile can perform. See the facebook mobile page http://www.facebook.com/mobile/

There are a few open vulnerabilities in Facebook. Two of them are Facebook Upload via Email and Facebook via Text Message.

Facebook via Text Message – The real villian ( Post on Anyone’s wall vulnerability)
I became a victim of Facebook via Text Message last day. Frankly, I never used Facebook via Text Message before and I didn’t sign up for the feature until today. Yesterday, It happened to see a new post on my facebook wall. It was just a ‘.’ in the post and seen that Posted using Text Message. I recently had installed Facebook app for android on my Nexus S. I thought that it is some bug in the Facebook App on mobile made the wall post. I tried to regenerate the same post on the wall using mobile. Later I understood that the badguy used the feature called Facebook via Text Message which I never used. I signed up for the service and tried out how it works.

I found that, once we link a mobile number to a facebook profile, if we send SMSmessages to 92FACEBOOK (9232232665) from our linked mobile number, the message will be posted on the wall. I was shocked to see such an insecure procedure. Even if you are not signed up with Facebook mobile – Text Message feature, your profile is exposed for vulnerability. If you had added a contact mobile number and verified it through facebook mobile verification process, that means you have subscribed vulnerability from facebook

The Facebook via Text Message system uses the sender’s mobile number to identify to which profile’s wall the text message is to be posted. Not only we can manipulate wall but also we can perform several activities through Facebook via Text Message. That means the vulnerability facilities the attacker to have complete control over your facebook activities.

SMS spoofing is one of the vulnerabilities in the SMS design. It is easy to send SMS messages to a person by changing the identity of the sender. In India, though all the SMS gateways do not allow spoofing of SMS message senders ID, there are still many paid and free SMS spoofing services from outside India. You can easily send SMS by tampering the Identity to anyone else.

If you have access to such an SMS spoofing service, you can set the mobile number (sender) corresponding to the facebook user whose wall is to be updated. By sending a spoofed SMS, we can easily update another one’s wall.

Protection:
Facebook should really introduce some additional authentication token along with the SMS (Eg. a temporary authentication passcode along with SMS). From a user end, the best mode of protection is to remove the mobile number linked to the profile.
If you want to show your contact number along with the profile, add the contact number. But do not confirm the verification of the contact number asked by Facebook verification system. Thus your profile will be able to display your mobile number, at the same time you are protected from the attack.

Facebook Upload via Email
Facebook upload via E-mail is comparitively secure feature. If you navigate to the facebook mobile website, you can see a email address similar to darner986injure@m.facebook.com. This is a secret email address. By sending email to the specific email address attached with the facebook profile, the email messages will be posted to the wall. It is important to keep this e-mail address as secret and should not be exposed to your friends and strangers. Incase, you feel that it got exposes to someone you can reset the special email address linked with the account. Click find out more -> Refresh your upload email.

I request everyone to be aware of this serious vulnerabilities on Facebook and take preventive measures to protect your profile and your identity over internet.

Thank you.

Posted on April 1, 2011 - by Sarath

The story of my job interviews with Taggle.com and Yahoo!

It has been a while since I thought of writing my previous job interview experiences with different companies.

Taggle.com came to our campus in month of July 2010. It was CTO, Tej Arora who came to the campus for the recruitment. First of all there was a Presentation about Taggle Internet ventures and how it works.

Taggle.com is a group buying website where you get goods for reduced prices, with greater than 50 % off when there are a group of people to buy it. We had a objective multiple choice test of around 40 questions. It consisted of few aptitude questions, data structure questions, etc. It was a good question paper. By evening 5 pm, the result of the technical test came out. There were around eleven guys shortlisted for the next programming test. The eleven selected candidates were send for the programming round. We were allowed to write code on our own laptop and use any programming language we liked. He gave us two set of questions. Set 1 consisted of 1 difficult question and other set consisted of 2 easy questions. We were able to choose one set for coding. I chose the question to implement text auto completion functionality (set 1) and wrote the code in Python. He verified my program and told me to wait and come back once the programming round is completed by others. My friend Fayaz also had written autocomplete functionality. There were other two girls Nishita Suresh and Legena P.K who had worked on the other set of problems. Four of us had personal interviews. He didn’t ask me any technical interview questions but we had a very friendly conversation about the work and benefits at Taggle Internet ventures.

Once interviews were completed, the results were announced. Fayaz and Me got placed in Taggle.com.

Yahoo! came to our campus on October 30th, 2010. It was a day before seventh semester university exams started. Yahoo was considered as the superstar company that comes to MEC campus with highest pay and perks. The day when placement cell announced ‘Yahoo’ is visiting campus, everyone looked with wow. Placement cell members gave us the info that Yahoo! is going to recruit for Service Engineering team where they look for guys who live and feed in UNIX environment. In the following days placement cell posted specifications and info on what they are looking for and their requirements. There were a lot of XMECians working in Yahoo and they send us some materials they studied during their time. Everyone started seriously preparing for Yahoo with lot of effort. I also wanted to get into Yahoo. It was the time I was working on my book and I had hectic schedules. Some of my seniors who got into Yahoo were famous for Shell Scripting and sed. So I had thought of seriously looking into SED. I spend few days on SED and AWK. It was really nice writing sed scripts, which looks very awkward but performs incredible text processing operations in single line of code. To brush up my shell scripting skills, I went through the first draft of my incomplete book. But, that helped me a lot to fix bugs in my book. I also brushed up few conceptual things like How E-mail works, Networking basics, etc. The day of Yahoo interview came. The cut-off percentage was 70%. There was a presentation on Yahoo! and what they are looking for? Benefits and perks at yahoo. Then we attended the screening test. The test consisted of few aptitude questions, lot of Perl questions, networking questions, questions from OS scheduling, SQL and few other things. But it was not that difficult. After the test, in about an hour the results were out. 15 guys were in. The next was programming round.

They gave two questions, To write an intruder detection system script by parsing the auth.log log file and program for generating random sequence of n numbers from single random seed. I wrote the script for intrusion detection and basic implementation of random sequence generator (I had uncertainty about the question and what I had done was slightly different from what they had meant). After the programming round, they shortlisted four candidates. Joju John Joseph, Subeen N, Neha Mahadevan and me. They announced that there will be three rounds of interviews (two technical and 1 HR round).

My turn for the interview came. They scanned through my Resume and were impressed with my work and Book. Interviewers asked about my interests. I told them that I live in GNU/Linux. One of the interviewer asked me to narrate the story of a computer from the time we press power button until it boots up. I had a long narration of the story of computer boot ups including in-depth explanation of Ramdisk and all (Actually Linux boot was one of my favorite things which I had worked on). Then he asked few questions like What happens when a user browse a Web page, DNS query, DNS records, and few other questions. The interview went through topics like GDB, Core file, Debugging, Killing processes, Init, Signals, Orphaned processes, SSH, SSH Auto-login, and many other questions. I don’t recall most of them. At the end of the interview, they told that they were pretty impressed and satisfied. The next round of interview was HR interview. It was very friendly in nature asking me usual HR questions. He was busy noting down my details on a form during the interview. After the HR interview I went for the second technical interview. They told that there is nothing to ask and we were having friendly conversation about college and environment. The interviewer told me about his college, Yahoo recruitment experience and few things about work environment. When my interviews were over, I had to wait outside with Placement cell volunteers until the three rounds of interview gets finished for other three guys. It took lot of hours. Finally they announced the result. Joju John Joseph and I got the placement offers for Service Engineering team. Neha and Subeen got internship offers.

I will write about my Zynga interview experience soon. Stay tuned!