Blocking of SQL Injection Attacks by Comparing Static and Dynamic Queries

Published Online February 2013 in MECS

Due to the easy access to the internet nowadays most of services consist of web services. But the increasing use of internet for important applications poses a greater risk of attacks on the web. SQL-Injection Attack (SQLIA) is not affecting the systems like other attacks, but the ability of SQLIAs to obtain sensitive information, such as military systems, e-business, and banks, etc results into great security risk. The SQLIA occurs when an intruder changes the structure of the query by inserting any SQL keywords. Any secret information can be easily retrieved from database by using these attacks. Variety of techniques are available to detect SQL injection Attacks. Most preferred are Web Framework, Static Analysis, Dynamic Analysis, Combined Static and Dynamic Analysis and Machine Learning Technique. Web Framework[1] provides filters to filter special characters but other attacks are not detected. Static Analysis[2],[3] method checks the input parameter type, but fails to detect attacks with correct input type. Dynamic Analysis[4],[5] technique is capable of scanning vulnerabilities of Web application but is not able to detect all types of SQLIAs. Combined Static and Dynamic Analysis[6]-[9] includes the benefits of both but this method is very complex. Machine learning method[10] can detect all types of attacks but results in number of false positives and negatives. This paper proposes a very simple and effective method to detect SQL Injection Attacks which uses Combined Static and Dynamic Analysis technique. The method is a combination of SQL Query attribute values removal and combined Static and Dynamic Analysis technique. The rest of the paper is organized in the form of different sections. Section 2 describes the categories of SQLIAs. Section 3 discusses the related work. Section 4 explains the proposed method to detect SQLIAs. Section 5 describes the experimental results. Section 6 concludes this paper.

• II.    Categories of SQL injection attacks

There are a number of different methods of SQL Injection Attacks which are serious threat for any database. For a successful SQLIA the attacker should append a syntactically correct command to the original SQL query. Now the following classification of SQLIAs in accordance to the Halfond, Viegas and Orso[11] researches is presented.

• A.    Tautologies

This type of attack injects SQL tokens to the conditional query statement which always evaluates true. This type of attack is used to bypass authentication control and access to data by exploiting vulnerable input field which use WHERE clause.

"Select * from loan where loan_no ='L11' and branch ='aaa' OR '1'='1' "

As the tautology statement (l = 1) has been added to the query statement so it is always true.

• B.    IlIegal/Logically Incorrect Queries

When any query is rejected, an error message is returned by SQL Oracle engine. This error messages help attacker to find vulnerable parameters in the Database.

• C.    Union Query

By using this technique, attackers join SQLIA to safe query by using word UNION and then can get data about other tables from the application. Consider the following example

Select loan_no,branch from loan where loan_no=$loan_no

By injecting the following loan_no value:

$loan_no=L11 UNION select cust_name from customers We will have the following query:

Select loan_no,branch from loan where loan_no=L11 UNION select cust_name from customers which will join the result of the original query with all the customer names.

• D.    Piggy-backed Queries

In this type of attack, intruders exploit database by using query delimiter, such as ";" by appending extra query to the original query. In this attack database receives and execute a multiple distinct queries. Normally the first query is legitimate query, whereas following queries could be illegitimate. So attacker can inject any command related to SQL to the database. In the following example, attacker inject " PO; drop table branch" into the designation input field instead of logical value. Then the application would produce the query:

Select salary from employee where emp_code='23467' AND designation=’PO’; drop table branch

Because of ";" character, database accepts both queries and executes them. The second query is not legitimate and can drop branch table from the database.

• E.    Stored Procedure

Stored procedure is a part of database that programmer could set an extra abstraction layer on the database. By using stored procedure a user can store its own function according to the need. In stored procedure, a collection of SQL queries are included. As stored procedure could be coded by programmer, so, this is also one of the causes of SQLIA. Depending on specific stored procedure in the database there are number of different ways to attack.

Create procedure dbo @emp_code varchar2, @desi varchar2 AS

Exec(“select * from employee where emp_code =’”+@emp_code+”’ and designation=’”+ desi”+”’);

GO

If the intruder adds one more query after the legitimate query, then the normal query is converted into piggy backed query which is a type of SQLIA.

Select * from employee where emp_code=’23451’ and designation=’PO’;Shutdown;

After the execution of original query the second query which is illegitimate is executed and causes database shut down .

• F.    Alternate Encoding

In this type of attack the regular strings and characters are converted into hexadecimal, ASCII and Unicode. Because of this the input query is escaped from filter which scans the query for some bad characters which results in SQLIAs i.e. the converted SQLIA is considered as normal query.

• G.    Inference

By this type of attack, intruders change the behaviour of a database or application. There are two well known attack techniques that are based on inference: blind injection and timing attacks.

• •    Blind Injection: Sometimes developers hide the error details which help attackers to compromise the database. In this situation attacker face to a generic page provided

by developer, instead of an error message. So the SQLIA would be more difficult but not impossible. An attacker can still steal data by asking a series of True/False questions through SQL statements. Consider two possible injections into the login field:

SELECT accounts FROM users WHERE user_name='abc' and 1 =0 -- AND password= AND pin=0

SELECT accounts FROM users WHERE user_name='abc' and 1 = 1 -- AND password = AND pin=0

If the application is secured, both queries would be unsuccessful, because of input validation. But if there is no input validation, the attacker can try the chance. First the attacker submit the first query and receives an error message because of "1=0". So the attacker does not understand the error is for input validation or for logical error in query. Then the attacker submits the second query which always true. If there is no login error message, then the attacker finds the user_name field vulnerable to injection.

• •    Timing Attacks: A timing attack lets attacker gather information from a database by observing timing delays in the database's responses. This technique by using if-then statement cause the SQL engine to execute a long running query or a time delay statement depending on the logic injected. This attack is similar to blind injection and attacker can then measure the time the page takes to load to determine if the injected statement is true. WAITFOR is a keyword along the branches, which causes the database to delay its response by a specified time. For example, in this attack the following query is inserted into user_name field:

‘‘legalUser’ and ASCII (SUBSTRING ((select top 1 name from sysobjects),1,1)) >  X WAITFOR 5 --’’

Following query is produced from this-

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

This query is used to extract a table name from the database. In this attack substring function is used to extract first character of first table’s name. If the ASCII value of character is greater than X, the attacker can get the character by using 5 seconds time delay in the response of database.

• III.    Related work

Order to detect and prevent SQLIAs a number of detection methods are available. This section explains the related work.

• A.    Web Framework

A Web Framework is a software framework that is designed to support the development of dynamic websites, web applications and web services. Some Web Frameworks offer SQL Injection Attack prevention methods. PHP provides magic quotes[1]. Magic quotes is a special feature of PHP language in which special characters ‘,”,/,NULL are pre pended with a backslash before being passed on to detect SQLIAs. But magic quotes support only four special symbols. SQLIAs with other symbols are not detected.

• B.    Static Analysis

Static Analysis method analyzes the SQL query sentences to detect SQLIAs. This method verifies user’s input type to reduce SQLIAs. JDBC checker[2] validates user input to prevent SQLIAs by using JSA. But if the malicious query has correct syntax and type, attack cannot be detected. Combined Automated Reasoning and Static Analysis method by Wasserman[3] uses FSA to detect SQLIAs. The use of FSA under approximation of the SQL grammar makes this technique too restrictive to remove some possible malicious queries from the represented set. The main problem with all static analysis techniques is that these require source code modification and most of the techniques are just used for web applications written in java.

• C.    Dynamic Analysis

Dynamic Analysis can locate vulnerabilities of SQLIAs without any source code modification. Paros[4] is a tool written in java used to locate vulnerabilities in web applications. Through its proxy nature all HTTP and HTTPS data between server and client, including cookies and form fields, can be intercepted and modified. Paros is not perfect because it uses predetermined attack codes to scan and uses HTTP response to the success-rate of the attack. Sania[5] finds and collects all the SQL Injection vulnerabilities between web application and database and automatically generate elaborate attacks according to the syntax and semantics. Then the Sania compares the parse tree of intended SQL query and those resulting after attack to assess the safety of vulnerable spots. Due to the use of parse tree Sania is more accurate to detect SQLIAs than any other dynamic analysis technique. Dynamic Analysis methods are useful because no source modification is required. But the vulnerabilities found in web application must be manually fixed by developer and not all of them can be found before predefined attack.

• D.    Combined Static and Dynamic Analysis

Combined Static and Dynamic Analysis includes the advantages of both Static and Dynamic Analysis techniques. SQLCheck[7] presents the definition of command injection attacks and gives a sound and complete algorithm for preventing SQLIAs based on context-free grammars and compiler parsing techniques. AMNESIA[6] is a model based approach to detect SQLIAs. This technique builds a model of all legitimate queries. Then each dynamic query is compared with this model to detect SQLIAs. Parse Tree[8] is used to compare static SQL query with dynamic SQL query to detect SQLIAs. Wei[9] proposed a technique to detect attacks in stored procedure using Control flow graph.

Webapplicalion

Steck crafting core tree validation

Santa

Fig.1. Structure of Sania

• E.    Instruction-Set Randomization

In Instruction set Randomization SQL query is encoded by inserting a random value in the query. SQLrand[12] uses this technique to protect the query from SQLIAs. But this method is not effective if the random key is predicted.

Fig.2. Sqlrand System Architecture

• F.    Machine Learning

Machine Learning is a technique in which training set i.e. a model is prepared which contain all the legitimate queries belonging to any web application. At run time all the requested queries are compared with queries in the training set to detect SQLIAs. Intrusion Detection System (IDS) by Valeur and colleagues[10] is based on this technique. But this technique results in number of false positives and negatives if the poor training set is used.

• G.    Prepare Statements

Prepare statements[13] are used in SQL to separate the values in query from the structure of query. In this the skeleton of SQL query is defined and then the values are filled at run time. SQLIA is detected if there is any change in the structure of query. But the main limitation of this method is that the whole web application needs to be modified in order to apply this method.

Fig.3. Overview of AMNESIA

TABLE I SQLIAs Detection Symbols

Symbo l	Description
I {t,f}	User input data { t : normal input , f :abnormal input }
f	SQL attribute value removing function
fn	Function to calculate total number of tokens in static and dynamic query
SQ	Static SQL query
DQ {t,f}	Generated dynamic SQL query from user Input { t : normal query , f :abnormal query }
DDQ {t,f }	Removed attribute values of dynamic SQL Query { t : normal query , f :abnormal query }
SQT	Total number of tokens in static query
DDQT { t,f}	Total number of tokens in dynamic quer { t : normal query , f :abnormal query }

H. Taint Based Technique

Java Dynamic Tainting[14] is a tool implemented in java. This tool chases string for taint information instead of character and then sanitizes query strings which are generated using tainted input. But the primary limitation of this tool is that this is not able to detect SQLIAs in numeric fields.

• IV.    Proposed method

In this research work combined static and dynamic analysis technique is used to reduce false positives and false negatives. The static query structure is compared with dynamic query. In this database is maintained to store the valid query structure. These valid queries are also known as static queries. The attribute values of dynamic queries are removed during run time and compared with previously stored static queries having same number of tokens as in dynamic query. The symbols needed in the proposed algorithm are given in Table I.

Consider an example to explain the symbols used in Table I.

In algorithm 2 and algorithm 3, the function fn , calculates the total number of tokens in static and dynamic queries.

Algorithm f(One SQL query)

Enumerate Quotation_Status= { Quot_Start,

Quot_End}

Input String=One SQL query;

Output_String=Null;

Do while( not empty of Input String)

{

Char=Get_Token(Input_String);

If Char is a quotation character and if Char is in between Quot_Start and Quot_End

{

Replace Char with ‘?’

}

Else {

Add Char to Output_String;

}}

Return Output_String;

Algorithm 1: Algorithm which removes attributes

SQ:  select * from users where user_id=? and password=? DQt: select * from users where user_id=’admin’ and password=’123456’

DQ f : select * from users where user_id=’’ or ‘1’=’1’— and password=’123456’

The detection method proposed in this paper will utilize the function f given in equation 1, which has the capability to remove the attribute values and replace the attribute values with ‘?’ in SQL queries.

DDQ = f (DQ)                               (1)

Another function used in this paper fn given in equation 2 calculates the total number of tokens in static and dynamic queries.

SQT = fn(SQ),      DDQt = fn(DDQ)           (2)

In algorithm 1, the function f , replaces the values within quotes (‘’) with symbol ‘?’.

Algorithm fn(SQ,Total_Token_S)

//SQ is static query

//Total_Token_S returns the total numbers of tokens in a static query

Input String=SQ;

Total_Token_S=0;

Do while( not empty of Input String) {

Char=Get_Char(Input_String);

If Char is a space character

{

Total_Token_S++;

}

Algorithm 2: Proposed Algorithm for token calculation in static query

Algorithm fn(DDQ,Total_Token_D)

//DDQ is a dynamic query generated after removing attribute values

//Total_Token_D returns the total numbers of tokens in a dynamic query

Input String=DDQ;

Total_Token_D=0;

Do while( not empty of Input String)

{

Char=Get_Char(Input_String);

If Char is a space character

{

Total_Token_D++;

}

Algorithm 3:  Proposed Algorithm for token calculation in dynamic query

The following example shows the result of functions f and fn. DQ 1 is a normal dynamic query and DQ 2 is an abnormal dynamic query.

SQ = select * from users where user_id=? and password=?

DQ 1 = select * from users where user_id =’admin’ and password=’123456’

DDQ 1 =f(DQ 1 )=select * from users where user_id=? and password=?

Total number of tokens in dynamic query DDQT 1 = fn(DDQ 1 ) = 8

DQ 2 = select * from users where user_id=’’ or

‘1’=’1’—and password=’abc’

DDQ2=f(DQ2)=select   * from users where user_id=’??=?—and designation=?

Total number of tokens in dynamic query DDQT 2 = fn(DDQ 2 ) = 7

Following formula is applied regardless of whether a query is normal or abnormal.

If (DDQT=SQT) then// if tokens are same

If (DDQ=SQ) // if queries are same

Then

Result=Normal

Else

Result=Abnormal

N: Total number of fixed SQL queries

SQi: i ’th static SQL query

DQi: Dynamic SQL query generated from SQi f : Function to delete value of attribute in SQL query SQ = {SQ 1 , . . . , SQ n }, // Static analysis

• 1.    For i=1 to N

• 2.    Get SQ i

• 3.    SQT i =fn(SQ i ) //returns total number of tokens in i^th static query and store numeric value in variable SQT i

• 4.    End {For}

  // Dynamic analysis (running time)

• 6.    While(Normal & ∀k ∈ N)

• 7.    Get DQ k with input values

• 8.    DDQ k = f (DQ k ) //Remove attribute values 9.DDQT k =fn(DDQ K ) //returns total number of tokens in k^th dynamic query and store numeric value in variable DDQT k

• 10.I f (DDQT k =SQT k )then //if number of tokens in static and dynamic queries are same

• 11.    Result = Normal

• 12.    Else

• 13.    Result = Abnormal

• 14.    End {If}

• 15.    End {While}

If (DDQ k =SQ k )       //if queries are same

Algorithm 4: Proposed Algorithm for comparison of queries

After removing attribute values this method locates for static queries having same number of tokens as in dynamic query. Then the dynamic query is compared character by character only with that static queries having same number of tokens. The technique of comparing dynamic queries only with that static queries having same number of tokens improves response time. If match is found requested dynamic query is valid query otherwise it is SQL Injection Attack.

V. Experiment and Evaluation

• A.    Experimental Result Analysis

This section shows the results of experiment. The main advantage of proposed method is its simplicity. The complexity of the algorithm is divided into two parts-first token calculation and second searching for dynamic query. In token calculation complexity depends upon the database we are using because each database has its own syntax but this token calculation technique is same for all databases. In searching for a query best case occurs when the algorithm finds the query in first comparison and the worst case occurs when the query is not in the list. The complexity for searching is O(n). But the best part of this method is that the whole list of static queries is divided according to the number of tokens. The dynamic query is

TABLE II Sample Input SQL Database

S.No.	SQL Statements
1	Select * from branch
2	Select emp_code from employee union select emp_code from branch
3	Select branch_name from branch where emp_code=’20496’
4	Select emp_code,branch_name,address from branch
5	Select * from branch where branch_name like ‘S%’
6	Select * from employee where designation=’PO’
7	Select designation,department,salary from employee where emp_code=’19961’
8	Select address from branch where branch_name=’STATE BANK OF PATIALA KAPURTHALA’
9	Select * from employee where salary between ‘20000’ and ‘50000’
10	Delete from employee where designation=’APRO’
11	Update employee set designation=’PO’ where designation=’APRO’
12	Update branch set branch_name=’STATE BANK OF PATIALA’ where emp-code=’20496’
13	Create or replace procedure abc(Vdesignation in char)is emp_no number;begin select emp_code into emp_no from employee where designation=Vdesignation;insert into branch values(emp_no,’OFFICE OF THE GENERAL MANAGER RAIL COACH FACTORY’,’RAIL COACH FACTORY KAPURTHALA’);end;
14	Select emp_code,branch_name,address from branch where emp_code in(select emp_code from employee where designation=’PO’)
15	Select E.emp_code,designation,department,salary,B.emp_code,branch_name, address from employee E inner join branch B on E.emp_code=B.emp_code where designation=’PO’
16	delete from branch where emp_code=’17589’
17	delete from employee where department=’DEPARTMENT OF POST’
18	Select branch_name from branch where emp_code=’20496’
19	Select E.emp_code,designation,department,salary,B.emp_code,branch_name, address from employee E right join branch B on E.emp_code=B.emp_code where designation=’PO’
20	select emp_code,salary from employee where designation like ’_P%’
21	select avg(salary) from employee group by department having department=’THE MALL KAPURTHALA’
22	select designation,salary from employee union select branch_name,address from branch
23	select max(salary) from employee group by designation having designation=’PO’
24	Select designation from employee where salary=’9200’
25	Select designation,count(designation) “no of designations” from employee group by designation

TABLE IV Experiment Results

Total no. of Static queries	No. of inserted SQL queries	Valid SQL queries	Detected SQL Injection attacks	Total time taken (milliseconds)	Average time per query (milliseconds)
255	109	48	61	8580	78.7

TABLE V Accuracy Results

Total no. of inserted queries	Total false positives	Total false negatives
48(Valid queries)+61(SQLIAs)	0	0

TABLE VI Performance Analysis

Total no. of inserted queries	Total time taken by base paper method (Milliseconds)	Total time taken by proposed method (Milliseconds)
109	25318	8580

‘о ’ defines that detection and prevention is partially possible ‘N/A’ Not Applicable ‘ X ’ defines that detection and prevention is impossible ‘ND’ defines that attack is not defined

Table VII Detection and Prevention methods of various SQLIAs

Symbols: ‘ • ’ defines that detection and prevention is possible

Detection/Preventi on Methods	Tautologies	Illegal/Incorrect Queries	Union Queries	Piggy Backed Querie s	Stored Procedures	Inference	Alternate Encoding	White Space Manipulati on Attack
AMNESIA[6]	•	•		•	X	•	•	ND
CSSE[15]	•	•		•	X	•	X	ND
Java Dynamic Tainting[14]	N/A	N/A	N/A	N/A	N/A	N/A	N/A	N/A
SQLCheck[7]	•	•		•	X	•	•	ND
SQLGuard[8]	•	•		•	X	•	•	ND
SQLrand[12]		X			X		X	ND
Tautology Checker[3]	•	X	X	X	X	X	X	ND
Web App. Hardening[16]	•	•	•	•	X	•	X	ND
IDS[10]	о	о	о	о	о	о	о	ND
JDBC-Checker[2]	N/A	N/A	N/A	N/A	N/A	N/A	N/A	N/A
Java Static Tainting[17]	•	•	•	•	•	•	•	ND
Safe Query Objects[18]	•	•	•	•	X	•	•	ND
Security Gateway[19]	N/A	N/A	N/A	N/A	N/A	N/A	N/A	N/A
SecuriFly[13]	N/A	N/A	N/A	N/A	N/A	N/A	N/A	N/A
SQL DOM[20]	•	•		•	X	•	•	ND
WAVES[21]	о	о	о	о	о	N/A	о	ND
WebSSARI[22]	•	•		•		•	•	ND
Base paper method[23]	•	•	•	•	•	•	•	ND
Proposed method	•	•		•	•	•	•	•

Compared character by character only with that static queries having same number of tokens. This results in less number of comparisons. Table II shows the sample database. Table III shows the sample injected SQL statements. Table IV, Table V and Table VI shows the experimental results.

• B.    Comparison of various detection and prevention methods by attack types

Table VII shows the comparison of various detection and prevention methods according to various attack types. Halfond[11] classified SQL Injection attacks into seven major categories- Tautologies, Incorrect queries, Union queries, Piggy-Backed queries, Stored procedures, Inference and Alternate encodings. As shown in table VII one more category of SQLIAs is defined named White Space Manipulation Attack which is not defined in any other detection and prevention method. In this type of attack an attacker can manipulate white spaces to prevent an attack from detection.

This paper proposes a very simple method to detect SQLIAs which compares static SQL queries with dynamic SQL queries after removing attribute values. To minimize the response time incoming queries are compared character by character only with that static queries having same number of tokens. In this one more attack known as white space manipulation attack other than existing classification of SQLIAs is defined and detected by proposed method. Removing of attribute values makes a SQL query independent of the database. So this method is used for any database. Future work will focus on to detect other types of attacks like cross site scripting attacks.

Acknowledgment

The authors also wish to thank many anonymous models.