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)
