SQL injection in Cybersecurity - Time & Space Complexity

Time Complexity: SQL injection

O(n)

Understanding Time Complexity

When analyzing SQL injection, we want to understand how the attack's effort grows as the input size changes.

We ask: How does the number of operations needed to exploit or detect SQL injection scale with input length?

Scenario Under Consideration

Analyze the time complexity of the following vulnerable SQL query construction.

user_input = get_input()
query = "SELECT * FROM users WHERE username = '" + user_input + "'"
execute(query)

This code builds a SQL query by directly inserting user input, which can be exploited by attackers.

Identify Repeating Operations

Look for repeated actions that affect performance or attack effort.

• Primary operation: Scanning the database for matching rows based on the input.
• How many times: Once per query, but the query complexity depends on input length and injected commands.

How Execution Grows With Input

Longer inputs can cause the database to process more complex queries, especially if injection adds conditions.

Input Size (n)	Approx. Operations
10	Simple query, few operations
100	More complex query, more operations
1000	Very complex query, many operations

Pattern observation: As input grows, the database work grows roughly in proportion to input length and complexity.

Final Time Complexity

Time Complexity: O(n)

This means the work to process the query grows linearly with the length of the user input.

Common Mistake

[X] Wrong: "SQL injection attacks always take constant time regardless of input size."

[OK] Correct: Longer or more complex injected inputs can cause the database to do more work, increasing execution time.

Interview Connect

Understanding how input size affects SQL injection helps you explain risks clearly and shows you grasp how attacks scale in real systems.

Self-Check

What if the code used prepared statements instead of string concatenation? How would the time complexity change?

Practice

1. What is SQL injection in cybersecurity?

easy

A. A method to speed up database queries

B. A way to backup database data securely

C. A technique to trick databases into running harmful commands

D. A process to encrypt database connections

Solution

1. Step 1: Understand SQL injection meaning

   SQL injection is a cyberattack where harmful commands are inserted into database queries.

2. Step 2: Identify correct description

   Only the technique to trick databases into running harmful commands describes this attack method accurately.

3. Final Answer:

   A technique to trick databases into running harmful commands -> Option C

4. Quick Check:

   SQL injection = harmful commands trick [OK]

Hint: SQL injection tricks databases with harmful commands [OK]

Common Mistakes:

• Confusing SQL injection with database backup
• Thinking SQL injection speeds up queries
• Mixing SQL injection with encryption

2. Which of the following is a correct way to prevent SQL injection?

easy

A. Using parameterized queries or prepared statements

B. Directly inserting user input into SQL queries without checks

C. Ignoring user input validation

D. Allowing all user inputs without restrictions

Solution

1. Step 1: Review prevention methods

   Safe coding practices include using parameterized queries to separate code from data.

2. Step 2: Identify correct prevention

   Using parameterized queries or prepared statements correctly states using parameterized queries or prepared statements to prevent injection.

3. Final Answer:

   Using parameterized queries or prepared statements -> Option A

4. Quick Check:

   Safe queries = parameterized/prepared [OK]

Hint: Use parameterized queries to stop SQL injection [OK]

Common Mistakes:

• Directly inserting unchecked user input
• Skipping input validation
• Assuming all inputs are safe

3. Consider this SQL query in a login system:
SELECT * FROM users WHERE username = 'admin' AND password = 'password123';
What happens if an attacker inputs ' OR '1'='1 as the password?

medium

A. The query returns no results

B. The query causes a syntax error

C. The query only returns the admin user

D. The query returns all users, bypassing password check

Solution

1. Step 1: Analyze injected input effect

   The input ' OR '1'='1' changes the WHERE clause to always true, bypassing password check.

2. Step 2: Understand query result

   Because '1'='1' is always true, the query returns all users, ignoring password.

3. Final Answer:

   The query returns all users, bypassing password check -> Option D

4. Quick Check:

   Injection ' OR '1'='1' = bypass password [OK]

Hint: Injection ' OR '1'='1' bypasses password check [OK]

Common Mistakes:

• Thinking it causes syntax error
• Assuming it returns no results
• Believing it returns only admin user

4. A developer wrote this SQL query:
query = "SELECT * FROM users WHERE name = '" + user_input + "';"
What is the main problem with this code?

medium

A. It concatenates user input directly into the query, risking SQL injection

B. It prevents SQL injection by validating input

C. It properly escapes user input

D. It uses parameterized queries correctly

Solution

1. Step 1: Examine query construction

   The code builds the SQL query by adding user input directly into the string.

2. Step 2: Identify security risk

   This direct concatenation allows attackers to inject malicious SQL commands.

3. Final Answer:

   It concatenates user input directly into the query, risking SQL injection -> Option A

4. Quick Check:

   Direct concatenation = SQL injection risk [OK]

Hint: Never concatenate user input directly into SQL queries [OK]

Common Mistakes:

• Assuming concatenation is safe
• Thinking input is automatically escaped
• Believing this code validates input

5. You have a web form that accepts a username to search a database. Which approach best protects against SQL injection when building the query?

hard

A. Use string concatenation with manual input cleaning

B. Use parameterized queries with placeholders for user input

C. Allow all input and filter results after query

D. Disable database error messages only

Solution

1. Step 1: Evaluate protection methods

   Parameterized queries separate code from data, preventing injection regardless of input.

2. Step 2: Compare options

   Use parameterized queries with placeholders for user input uses placeholders safely; other options either rely on unsafe cleaning or do not prevent injection.

3. Final Answer:

   Use parameterized queries with placeholders for user input -> Option B

4. Quick Check:

   Best protection = parameterized queries [OK]

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

Common Mistakes:

• Relying on manual input cleaning
• Filtering results after query is unsafe
• Only hiding error messages does not protect