Combinatorial Security Testing (CST)

Motivation

  • We cannot test everything
  • Exhaustive search of search space increases time needed exponentially
  • Automated detection of security vulnerabilities

Combinatorial Testing (CT)

  • Provide 100% coverage of t-way combinations of input parameters; faults depend on t parameters
  • Ensure automation during test generation
  • Fault localization, coverage measurement

Technical Challenges

  • Generation of such test suites is a hard combinatorial problem
  • Modeling parameters, values, constraints (domain specific)
  • Deploy CT to all application layers of information security

Web Security Interaction Testing

  • Focus: Exploitation of vulnerabilities (XSS, SQL-i, RFI)
  • Modelling: Combinatorial attack grammars via IPM
    • Automated translation layers -> largest repository of XSS attack vectors (ahead of IBM AppScan, OWASP Xenotix)
  • XSSInjector: Prototype tool for automated mounting of XSS attacks
  • Real-World Vulnerabilities: XSS in tidy service (HTML validation) of W3C portal (vulnerability found with t-way testing)
    • In process of publishing CVEs for popular web applications

Combinatorial Kernel Testing

  • Focus: Reliability and quality assurance of kernel software
  • Modelling: Linux system call API via categories
    • Automated t-way testing and translation layers
  • ERIS: Highly configurable testing framework encompassing CT, execution environment, logging and database infrastructure
  • Evaluation: Various kernel crashes for RCs and distribution kernels
  • Future Extensions: Android APIs targeting mobile security

Security Protocol Interaction Testing

  • Motivation: Major security breaches recently; FREAK, POODLE, Heartbleed; ensure proper error handling
    • NIST is currently revising the RFCs (standards)
  • SUTs: TLS, SSL, SSH, IKE (c.f. Internet Protocol Suite)
  • Goal: Quality assurance of protocol implementations
  • Certificate Testing: Attack vectors have the purpose to forge certificates; check whether the server/client accepts them as valid
  • Handshakes: Model the event sequences of TLS handshakes with t-way sequence testing

Combinatorial Testing for Hardware Malware

  • Goal: Hardware Trojan horse (HTH) detection
  • Scenario: Trojans reside inside cryptographic circuits that perform encryption & decryption in FPGA technologies Triggering Sequence: Trojans monitor less than k key bits of AES-128
    • Instance of a combinational Trojan; when all k key bits are set to ”1” the payload is activated and reverses the mode of operation
  • Attack Vectors: Model triggering sequences of the Trojan (black-box testing); input space is 2128 = 3.4 × 1038 combinations
  • Finding a Key in the Haystack: CT can detect a 4-bit key triggering sequence using just 111 tests (ensuring 100% 4-way coverage)