Interview Aptitude Question

Given a linked list of infinite length. Write a function to return a random node.

Constraints:

1 You can traverse a singly linked list only once.
2 You can not use any extra space.
3. You don't know the length of the linked list in advance.

Probable solution:

For each node in the linked list, generate a random number and as u traverse it keep track of the node address which is allotted minimum random number and then finally return that node's address as the ans.

Operating Systems by Silberschatz

The link for "Operating System Concepts" by Silberschatz, Galvin, Gagne is,

http://adf.ly/C05tx

The link to solutions is,

http://adf.ly/C06HM

The solutions link given above is a zip file hosted on Google Docs. So download the zip file to your hard-drive before using it.

Networking

Introduction to ALGORITHMS (2ed)

Its one of the important books suggested in my college for the course "Design and Analysis Of Algorithms". The review for this book can be found at,


Here is the link to the book "Introduction to Algorithms" by Thomas H Cormen,

http://adf.ly/Bzw9f

The solutions for this book can be found at,

http://adf.ly/BzxQA

Notify me in comments if any of the links is removed or broken.

Mobile Apps

Absolute Minesweeper

This is the mobile version of Minesweeper game in Windows. It is free and has no ads. One of my personal favourites. Download this from,

http://www.malathi.byethost7.com/dictionary.zip

Dictionary for Mobiles

A quick Oxford dictionary mobile version. It is a jar file and hence is almost supported on all mobile phones that has java support. Download and enjoy!!!!

http://malathi.byethost7.com/dictionary.zip

Notify me in the comments if any of the link  is removed or broken.

SQL Injection


SQL Injection:
            It is an attack of giving malicious input in the form of SQL to a web-application which is passed to the database server for parsing and execution. They allow attackers to obtain unrestricted access to the databases underlying the applications and to the potentially sensitive information these databases contain.

The main reason for SQL injection vulnerability is insufficient validation of user input.

Possible ways of injection:

  •  Injection through user input
  •   Injection through cookies
  •           Injection through server variables
  •   Second-order injection


Attack Intent:
Attacks can also be characterized based on the goal, or intent,
of the attacker.

   ü Identifying injectable parameters
   ü Performing database finger-printing
   ü Determining database schema
   ü Extracting data
   ü Adding or modifying data
   ü Evading detection
   ü Bypassing authentication
   ü Executing remote commands
   ü Performing privilege escalation

Example for illustration:
           
The below example shows the implementation of a servlet which is used to illustrate the various types of SQL injection attacks discussed below:


1. String login, password, pin, query
2. login = getParameter("login");
3. password = getParameter("pass");
3. pin = getParameter("pin");
4. Connection conn.createConnection("MyDataBase");
5. query = "SELECT accounts FROM users WHERE login=’" +
6. login + "’ AND pass=’" + password +
7. "’ AND pin=" + pin;
8. ResultSet result = conn.executeQuery(query);
9. if (result!=NULL)
10. displayAccounts(result);
11. else
12. displayAuthFailed();

Types of SQL injection attacks:

  ü Tautologies
  ü Illegal/Logically Incorrect Queries
  ü Union Query
  ü Piggy-Backed Queries
  ü Stored Procedures
  ü Inference
     o   Blind Injection
     o   Timing Attacks
  ü Alternate Encodings

Tautologies:

Attack Intent: Bypassing authentication, identifying injectable parameters,
extracting data.

Description: The general goal of a tautology-based attack is to inject code in one or more conditional statements so that they always evaluate to true.

Example: In this example attack, an attacker submits “ ’ or 1=1 - -” for the login input field. The resulting query is:

SELECT accounts FROM users WHERE
login=’’ or 1=1 -- AND pass=’’ AND pin=
Because the conditional is a tautology, the query evaluates to true for each row in the table and returns all of them. In our example, the returned set evaluates to a ‘non-null’ value, which causes the application to conclude that the user authentication was successful. Therefore, the application would invoke method displayAccounts() and show all of the accounts in the set returned by the database.

Illegal/Logically Incorrect Queries:

Attack Intent: Identifying injectable parameters, performing database finger-printing, extracting data.

Description: This attack lets attacker gather important information about the type and structure of the back-end database of a Web-applicationAlthough this attack is preliminary, information gathering step for other attacks. The vulnerability leveraged by this attack is that the default error page returned by application servers is often overly descriptive. An attacker tries to inject statements that cause a syntax, type conversion, or logical error into the database.

  ü Syntax errors can be used to identify injectable parameters.
  ü Type errors can be used to deduce the data types of certain columns or to extract data.
  ü Logical errors often reveal the names of the tables and columns that caused the error.

Example: This example attack’s goal is to cause a type conversion error that can reveal relevant data. To do this, the attacker injects the following text into input field pin: “convert(int,(select top 1 name from sysobjects where xtype=’u’))”. The resulting query is:

SELECT accounts FROM users WHERE login=’’ AND pass=’’ AND pin= convert (int,(select top 1 name from sysobjects where xtype=’u’))

In the attack string, the injected select query attempts to extract the first user table (xtype=’u’) from the database’s metadata table. The query then tries to convert this table name into an integer. Because this is not a legal type conversion, the database throws an error. For Microsoft SQL Server, the error would be: ”Microsoft OLE DB Provider for SQL Server (0x80040E07) Error converting nvarchar value ’CreditCards’ to a column of data type int.”

From this the attacker infers the following:
  ü The database is an SQL Server database
  ü First user-defined table in the database: “CreditCards.”

Union Query:

Attack Intent: Bypassing Authentication, extracting data.

Description: With this technique, an attacker can trick the application into returning data from a table different from the one that was intended by the developer.

Example: An attacker could inject the text “’ UNION SELECT cardNo from CreditCards where acctNo=10032 - -” into the login field, which produces the following query:

SELECT accounts FROM users WHERE login=’’ UNION SELECT cardNo from CreditCards where acctNo=10032 -- AND pass=’’ AND pin=

The original first query returns the null set, whereas the second query returns data from the “CreditCards” table.

Piggy-Backed Queries

Attack Intent: Extracting data, adding or modifying data, performing denial of service, executing remote commands.

Description: In this attack type, an attacker tries to inject additional queries into the original query.

Example: If the attacker inputs “’; drop table users - -” into the pass field, the application generates the query:

SELECT accounts FROM users WHERE login=’doe’ AND
pass=’’; drop table users -- ’ AND pin=123

Stored Procedures:

Attack Intent: Performing privilege escalation, performing denial of service, executing remote commands.

Description: Today, most database vendors ship databases with a standard set of stored procedures that extend the functionality of the database and allow for interaction with the operating system. Therefore, once an attacker determines which back-end database is in use, SQL Injection Attacks can be crafted to execute stored  procedures provided by that specific database, including procedures that interact with the operating system.

Inference:

Attack Intent: Identifying injectable parameters, extracting data,  determining database schema.

Description: Some applications are so secure that no usable feedback is available via database error messages. By carefully noting when the site behaves the same and when its behavior changes, the attacker can deduce not only whether certain parameters are vulnerable, but also additional information about the values in the database. There are two well known attack techniques that are based on inference.
  ü Blind Injection
  ü Timing Attacks

Example:

Identifying injectable parameters using blind injection:

Consider two possible injections into the login field. The first being “legalUser’ and 1=0 - -” and the second, “legalUser’ and 1=1 - -”. These injections result in the following two queries:

SELECT accounts FROM users WHERE login=’legalUser’
and 1=0 -- ’ AND pass=’’ AND pin=0
SELECT accounts FROM users WHERE login=’legalUser’
and 1=1 -- ’ AND pass=’’ AND pin=0

If the application is secure, we get error messages for both the queries. However if it is not secure we get an error message for the first query and login success page for the second one.

Timing based inference attack to extract a table name from the database:

In this attack, the following is injected into the login parameter:
‘legalUser’ and ASCII(SUBSTRING((select top 1 name from sysobjects),1,1)) > WAITFOR 5 --’. This produces the following query:

SELECT accounts FROM users WHERE login=’legalUser’ and  ASCII(SUBSTRING((select top 1 name from sysobjects),1,1)) > X WAITFOR 5 -- ’ AND pass=’’ AND pin=0

In this attack the SUBSTRING function is used to extract the first character of the first table’s name. Using a binary search strategy, the attacker can then ask a series of questions about this character. In this case, the attacker is asking if the ASCII value of the character is greater-than or less-than-or-equal-to the value of X. If the value is greater, the attacker knows this by observing an additional 5 second delay in the response of the database. The attacker can then use a binary search by varying the value of to identify the value of the first character.

Alternate Encodings:

Attack IntentEvading detection.

Description: In this attack, the injected text is modified so as to avoid detection by defensive coding practices and also many automated prevention techniques.

Example: In this attack, the following text is injected into the login field: “legalUser’; exec(0x73687574646f776e) - - ”. The resulting query generated by the application is:
SELECT accounts FROM users WHERE login=’legalUser’;
exec(char(0x73687574646f776e)) -- AND pass=’’ AND pin=

This example makes use of the char() function and of ASCII hexadecimal encoding. The char() function takes as a parameter an integer or hexadecimal encoding of a character and returns an instance of that character. The stream of numbers in the second part of the injection is the ASCII hexadecimal encoding of the string “SHUTDOWN.” Therefore, when the query is interpreted by the database, it  would result in the execution, by the database, of the SHUTDOWN command.

Head First Design Patterns

Head First Design Patterns by  Eric Freeman, Elisabeth Robson, Bert Bates, Kathy Sierra is really a wonderful book to start learning the design principles of OO Programming. The book is interactive and that there is ver little chance that the reader will be bored. I got this book from Flipkart for Rs.469/-
This is a link to the scanned copy of the book.


http://adf.ly/BzxnF
But my suggestion is to buy this book. Its a good book to refer all the time.

If the link is removed or broken notify in the comments section :-)