Static Taint Analyser

Inspiration

• Sensitive data leaks often happen through control flow, not just assignments
  
• Most beginner taint analyzers miss implicit flows
  
• We wanted a hands on way to learn data flow analysis and CFG based reasoning
  
• Building a real static analyzer felt like the best way to understand compiler theory
  

What it does

• Performs static taint analysis on a custom imperative language
  
• Detects explicit flows from inputExpr to sinkExpr
  
• Detects implicit flows through if and while conditions
  
• Builds a control flow graph using basic blocks
  
• Normalizes code into three address form
  
• Reports leaks with line numbers
  

How we built it

• Designed a small language grammar
  
• Built the lexer using JFlex
  
• Built the parser using Java CUP
  
• Constructed an AST in Java
  
• Converted the AST into a CFG with basic blocks
  
• Implemented taint propagation using a lattice based analysis
  
• Used the Kildall worklist algorithm to reach a fixed point
  
• Added a brute force solver for validation
  
• Implemented post dominator optimization to reduce false positives
  

Challenges we ran into

• Correctly modeling implicit flows without excessive false positives
  
• Designing a clean and correct CFG for nested control flow
  
• Ensuring the fixed point algorithm converged efficiently
  
• Debugging CUP grammar and shift reduce conflicts
  
• Balancing soundness and precision in the analysis
  

Accomplishments that we're proud of

• Built a complete end to end static taint analysis tool
  
• Correctly handles both explicit and implicit information flow
  
• Implemented multiple analysis strategies for comparison
  
• Reduced false positives using post dominator theory
  
• Created a reusable framework for future data flow analyses
  

What we learned

• How real static analyzers reason about programs
  
• Why control dependencies are critical for security analysis
  
• How lattices and join operations affect precision
  
• How CFGs and dominance relationships work in practice
  
• Practical experience with compiler construction tools
  

What's next for Functional NN

• Add interprocedural taint analysis
  
• Support user defined sanitizers
  
• Improve flow and context sensitivity
  
• Visualize CFGs and taint propagation
  
• Extend the language toward real world code
  

Built With

• java