Software Security Verification with Formal Methods

TL;DR

This guide shows you how to use automated tools to check if your existing software follows its security rules (policies). We’ll cover static analysis, model checking, and symbolic execution. These methods help find bugs *before* attackers do.

1. Understanding Formal Methods

Formal methods use maths to prove or disprove that a piece of software behaves as expected. For security, this means verifying your code meets its security policy. Unlike testing (which shows presence of bugs), formal methods aim to show *absence* of certain types of bugs.

2. Static Analysis

Static analysis examines your code without running it. It’s like a very thorough code review, but done by a tool. It can find potential vulnerabilities like buffer overflows or SQL injection flaws.

1. Choose a Tool: Popular options include SonarQube (commercial/open-source), Coverity (commercial), and Semgrep (open-source).
2. Integrate with your Build Process: Most tools have plugins for common build systems like Maven, Gradle, or Jenkins. This means the analysis runs automatically every time you build your software.
3. Configure Rulesets: Tell the tool which security rules to check for (e.g., OWASP Top 10).
4. Review Results: The tool will highlight potential issues with line numbers and explanations. Investigate each finding carefully – not everything is a real bug!

Example using Semgrep to find hardcoded passwords:

semgrep --config auto -t yaml ./your-code/

3. Model Checking

Model checking explores all possible states of your software to see if it violates its security policy. It’s good for verifying complex protocols or state machines.

1. Create a Formal Model: This is the hardest part! You need to represent your software’s behaviour in a language the model checker understands (e.g., Promela for Spin, TLA+).
2. Specify Security Properties: Write down what you want to prove about your system (e.g., “a user can never access another user’s data”). This is often done using temporal logic.
3. Run the Model Checker: The tool will explore all possible states and tell you if it finds a violation of your properties. If it does, it provides a counterexample – a sequence of steps that leads to the error.

Example using Spin (very simplified):

spin -a your_model.smv

gcc -o pan pan.c

./pan -a

4. Symbolic Execution

Symbolic execution runs your code with symbolic inputs instead of concrete values. This allows it to explore multiple paths through the code at once.

1. Choose a Tool: KLEE (open-source), Angr (open-source) and S2E (open-source) are popular choices.
2. Instrument your Code: The tool needs to modify your code slightly to track symbolic values.
3. Run the Symbolic Executor: The tool will explore different execution paths, trying to find inputs that trigger specific conditions (e.g., a vulnerability).
4. Analyze Results: The tool generates concrete examples that demonstrate vulnerabilities.

Example using KLEE (very simplified):

clang -cc1 your_code.c -emit-llvm -o your_code.ll

klee your_code.ll --output-dir klee-results

5. Combining Techniques

These techniques aren’t mutually exclusive! You can use static analysis to quickly find obvious bugs, then use model checking or symbolic execution for more complex areas.

• Static Analysis + Symbolic Execution: Use static analysis to narrow down the search space for symbolic execution.
• Model Checking + Static Analysis: Use static analysis to generate a simplified model for model checking.

6. Important Considerations

• False Positives: All these tools can produce false positives – reports that aren’t real bugs. Careful review is essential.
• Scalability: Formal methods can be computationally expensive, especially for large codebases. Choose the right tool and focus on critical parts of your system.
• Model Accuracy: The accuracy of model checking depends on how well you represent your software in the formal model.