Ensuring the correctness of reducers is critical in distributed systems, as their non-commutative nature can lead to order-sensitive and non-deterministic behavior. This issue becomes particularly challenging in large-scale data processing frameworks like MapReduce, where the unordered nature of input data can exacerbate correctness risks. Existing approaches, such as static analysis or heuristic-based testing, often fail to distinguish between harmless and problematic reducers, leading to excessive false positives that burden developers. To address this, we introduce a novel framework that combines the semantic reasoning capabilities of Large Language Models (LLMs) with the systematic path exploration of symbolic execution. By standardizing the reduce function under test, our framework ensures a consistent representation for analysis. Symbolic execution complements this by systematically generating diverse inputs that maximize path coverage, while LLMs refine these inputs into meaningful test cases by incorporating data properties extracted from requirements. This synergy enables the precise identification of genuine correctness issues, addressing the limitations of existing methods. Experimental results demonstrate that our approach, termed LLMTest, achieves an accuracy of 79.47% and a recall of 89.58%, while significantly reducing the false positive rate to 30.85%. In comparison, traditional methods such as DirectTest (symbolic execution only) have a lower accuracy of 63.16% and a much higher false positive rate of 55.32% (RandTest) or 65.96% (CT[x]). This integration not only enhances the reliability of distributed systems, but also provides developers with actionable insights by minimizing unnecessary warnings. Beyond MapReduce, the framework has potential applications in other data-intensive scientific workflows and AI-driven systems where order-sensitivity or data property preservation is critical.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

LLMTest: Combining Symbolic Execution and LLM Capabilities for Commutativity Test of Reduce Functions

  • Xuan Zhang,
  • Peng Zhang,
  • Qin Liu,
  • Fengshan Zhao

摘要

Ensuring the correctness of reducers is critical in distributed systems, as their non-commutative nature can lead to order-sensitive and non-deterministic behavior. This issue becomes particularly challenging in large-scale data processing frameworks like MapReduce, where the unordered nature of input data can exacerbate correctness risks. Existing approaches, such as static analysis or heuristic-based testing, often fail to distinguish between harmless and problematic reducers, leading to excessive false positives that burden developers. To address this, we introduce a novel framework that combines the semantic reasoning capabilities of Large Language Models (LLMs) with the systematic path exploration of symbolic execution. By standardizing the reduce function under test, our framework ensures a consistent representation for analysis. Symbolic execution complements this by systematically generating diverse inputs that maximize path coverage, while LLMs refine these inputs into meaningful test cases by incorporating data properties extracted from requirements. This synergy enables the precise identification of genuine correctness issues, addressing the limitations of existing methods. Experimental results demonstrate that our approach, termed LLMTest, achieves an accuracy of 79.47% and a recall of 89.58%, while significantly reducing the false positive rate to 30.85%. In comparison, traditional methods such as DirectTest (symbolic execution only) have a lower accuracy of 63.16% and a much higher false positive rate of 55.32% (RandTest) or 65.96% (CT[x]). This integration not only enhances the reliability of distributed systems, but also provides developers with actionable insights by minimizing unnecessary warnings. Beyond MapReduce, the framework has potential applications in other data-intensive scientific workflows and AI-driven systems where order-sensitivity or data property preservation is critical.