How SQL injection exploits queries - Performance & Efficiency

Time Complexity: How SQL injection exploits queries

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a SQL query changes when someone tries to exploit it with SQL injection.

How does adding malicious input affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of this vulnerable SQL query:

SELECT * FROM users WHERE username = '' OR '1'='1';
    

This query returns all users because the injected condition always matches.

Identify Repeating Operations

Look at what the database does repeatedly:

• Primary operation: Scanning the users table rows to check the condition.
• How many times: Once for each row in the users table.

How Execution Grows With Input

As the number of users grows, the database checks more rows because the injected condition matches all rows.

Input Size (n)	Approx. Operations
10	10 row checks
100	100 row checks
1000	1000 row checks

Pattern observation: The work grows directly with the number of rows in the table.

Final Time Complexity

Time Complexity: O(n)

This means the database work grows linearly with the number of rows because it must check each one.

Common Mistake

[X] Wrong: "SQL injection only affects security, not performance."

[OK] Correct: Injected queries can cause the database to do much more work, slowing down the system as it checks many rows.

Interview Connect

Understanding how SQL injection affects query time helps you see why protecting queries is important for both security and performance.

Self-Check

"What if the query used an index on username? How would that change the time complexity when under SQL injection?"

Practice

1. What is the main risk of SQL injection attacks on a database?

easy

A. Slower query performance

B. Unauthorized access to or manipulation of data

C. Syntax errors in SQL queries

D. Increased storage space usage

Solution

1. Step 1: Understand what SQL injection does

   SQL injection allows attackers to insert malicious SQL code into queries to manipulate the database.

2. Step 2: Identify the main consequence

   This manipulation can lead to unauthorized access or changes to data, which is a serious security risk.

3. Final Answer:

   Unauthorized access to or manipulation of data -> Option B

4. Quick Check:

   SQL injection = Unauthorized data access [OK]

Hint: SQL injection lets attackers access or change data illegally [OK]

Common Mistakes:

• Confusing SQL injection with performance issues
• Thinking it only causes syntax errors
• Assuming it increases storage use

2. Which of the following SQL query snippets is vulnerable to SQL injection if user input is not sanitized?
SELECT * FROM users WHERE username = '" + userInput + "';

easy

A. SELECT * FROM users WHERE username = '" + userInput + "';

B. SELECT * FROM users WHERE username = ?;

C. SELECT * FROM users WHERE username = 'admin';

D. SELECT * FROM users WHERE username = 'admin' AND password = 'pass';

Solution

1. Step 1: Identify how user input is used

   The query concatenates userInput directly into the SQL string without sanitization.

2. Step 2: Recognize vulnerability

   This direct insertion allows attackers to inject malicious SQL code, making it vulnerable.

3. Final Answer:

   SELECT * FROM users WHERE username = '" + userInput + "'; -> Option A

4. Quick Check:

   Direct input concatenation = Vulnerable [OK]

Hint: Directly adding user input to query string is unsafe [OK]

Common Mistakes:

• Choosing parameterized queries as vulnerable
• Confusing safe hardcoded queries with vulnerable ones
• Ignoring the role of input sanitization

3. Given the vulnerable query:
SELECT * FROM users WHERE username = '" + userInput + "';
If userInput is admin' OR '1'='1, what will the query become and what is the likely result?

medium

A. Syntax error due to unmatched quotes

B. SELECT * FROM users WHERE username = 'admin OR 1=1'; -- Returns no users

C. SELECT * FROM users WHERE username = 'admin'; -- Returns only admin user

D. SELECT * FROM users WHERE username = 'admin' OR '1'='1'; -- Returns all users

Solution

1. Step 1: Substitute userInput into the query

   The query becomes: SELECT * FROM users WHERE username = 'admin' OR '1'='1';

2. Step 2: Understand the effect of OR '1'='1'

   The condition '1'='1' is always true, so the WHERE clause matches all rows.

3. Final Answer:

   SELECT * FROM users WHERE username = 'admin' OR '1'='1'; -- Returns all users -> Option D

4. Quick Check:

   Injected OR '1'='1' returns all rows [OK]

Hint: OR '1'='1' always true returns all rows [OK]

Common Mistakes:

• Thinking it causes syntax error
• Assuming it returns only admin user
• Misreading the injected condition

4. You have this vulnerable SQL query in your code:
query = "SELECT * FROM users WHERE username = '" + userInput + "';"
Which fix correctly prevents SQL injection?

medium

A. Remove the WHERE clause entirely

B. Escape single quotes in userInput manually

C. Use parameterized queries or prepared statements

D. Convert userInput to uppercase before using

Solution

1. Step 1: Identify secure coding practice

   Parameterized queries separate code from data, preventing injection.

2. Step 2: Evaluate other options

   Manual escaping is error-prone, removing WHERE breaks logic, uppercase conversion doesn't prevent injection.

3. Final Answer:

   Use parameterized queries or prepared statements -> Option C

4. Quick Check:

   Parameterized queries = Safe from injection [OK]

Hint: Always use parameterized queries to stop injection [OK]

Common Mistakes:

• Relying on manual escaping only
• Removing query conditions instead of fixing
• Thinking input case changes prevent injection

5. Consider a login system using this vulnerable query:
SELECT * FROM users WHERE username = '" + userInput + "' AND password = '" + passInput + "';
If an attacker inputs admin' -- as username and anything as password, what happens and why?

hard

A. Login succeeds without password check because -- comments out rest

B. Login fails due to syntax error from unmatched quotes

C. Login succeeds only if password matches exactly

D. Login fails because input is rejected by the system

Solution

1. Step 1: Substitute attacker input into query

   The query becomes: SELECT * FROM users WHERE username = 'admin' --' AND password = 'anything';

2. Step 2: Understand effect of -- comment

   The -- makes the rest of the query a comment, so password check is ignored.

3. Step 3: Result of query

   The query checks only username = 'admin', allowing login without password.

4. Final Answer:

   Login succeeds without password check because -- comments out rest -> Option A

5. Quick Check:

   -- comments out password check = Login bypass [OK]

Hint: SQL comment -- skips password check for login bypass [OK]

Common Mistakes:

• Assuming syntax error occurs
• Thinking password is still checked
• Believing input is blocked automatically