static-analysis

Static Analysis Skill

This skill covers static program analysis techniques using LLVM infrastructure for security research, vulnerability detection, and code quality assessment.

Analysis Categories

Dataflow Analysis

• Forward Analysis: Track values from definitions to uses
• Backward Analysis: Track from uses back to definitions
• May/Must Analysis: Conservative vs precise approximations

Control Flow Analysis

• Dominator Trees: Identify code dominance relationships
• Post-Dominator Trees: Control dependence analysis
• Loop Analysis: Detect and characterize loops

Pointer Analysis

• Flow-Insensitive: Andersen's, Steensgaard's algorithms
• Flow-Sensitive: Track pointer values at each program point
• Context-Sensitive: Distinguish calling contexts

LLVM Analysis Infrastructure

Using Built-in Analyses

#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/DominatorTree.h"

void analyze(llvm::Function& F, llvm::FunctionAnalysisManager& FAM) {
    // Get dominator tree
    auto& DT = FAM.getResult<llvm::DominatorTreeAnalysis>(F);
    
    // Get loop info
    auto& LI = FAM.getResult<llvm::LoopAnalysis>(F);
    
    // Get alias analysis
    auto& AA = FAM.getResult<llvm::AAManager>(F);
    
    // Check if two pointers may alias
    llvm::AliasResult AR = AA.alias(Ptr1, Ptr2);
}

Implementing Custom Analysis

class TaintAnalysis {
    std::set<llvm::Value*> taintedValues;
    
public:
    void markTainted(llvm::Value* V) {
        taintedValues.insert(V);
    }
    
    bool isTainted(llvm::Value* V) {
        return taintedValues.count(V) > 0;
    }
    
    void propagate(llvm::Instruction* I) {
        // Propagate taint through operations
        for (auto& Op : I->operands()) {
            if (isTainted(Op)) {
                markTainted(I);
                break;
            }
        }
    }
};

Taint Analysis

Source-Sink Model

// Define taint sources (user input, network, files)
bool isTaintSource(llvm::CallInst* CI) {
    llvm::Function* F = CI->getCalledFunction();
    if (!F) return false;
    
    static const std::set<std::string> sources = {
        "read", "recv", "fread", "getenv", "gets", "scanf"
    };
    return sources.count(F->getName().str()) > 0;
}

// Define sensitive sinks (SQL queries, system calls, format strings)
bool isSensitiveSink(llvm::CallInst* CI) {
    llvm::Function* F = CI->getCalledFunction();
    if (!F) return false;
    
    static const std::set<std::string> sinks = {
        "system", "exec", "printf", "strcpy", "memcpy", "sql_query"
    };
    return sinks.count(F->getName().str()) > 0;
}