Semantic-guided Testing and Bug Discovery in Complex Execution Engines
Dr Liang Zhenkai, Associate Professor, School of Computing
COM3 Level 2
MR24, COM3 02-64
Abstract:
The increasing scale and complexity of modern software infrastructures have accelerated software creation, while making it harder to assure code quality at scale. This thesis investigates how to systematically uncover correctness, robustness, and security bugs in complex execution engines (especially compilers, interpreters, and data systems). We pursue two specific questions: (1) how to generate semantically rich program inputs that drive deep, bug-revealing behaviors beyond syntactic validity, and (2) how to make differential and metamorphic testing practical and scalable for real-world systems in terms of semantic diversity. This thesis contributes four semantic-guided bug discovery approaches for complex execution engines. FlowFusion uses dataflow-aware fusion of developer tests, combined with mutation and interface/environment crossover, to stress the PHP interpreter. It uncovered 158 previously unknown bugs and is now integrated into PHP’s toolchain. ZendDiff targets logic errors in PHP by comparing executions in JIT and non-JIT modes with program-state probing and JIT-aware mutations, surfacing 51 new logic bugs. ACME targets logic bugs and internal errors in emerging database systems via enhanced differential testing against relational systems, using LLM-driven clause mapping to bridge syntactic and semantic gaps across heterogeneous SQL dialects, discovering 59 previously unknown bugs across four systems. GraphGenie detects logic flaws in graph database engines by generating semantically related graph queries that encode equivalence or containment relations, finding 25 unknown bugs across popular graph engines like Neo4j. Together, these approaches show that semantics-aware input generation and principled oracles can deepen exploration and make systematic fuzzing or testing practical at scale for widely deployed execution engines.