Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Skeletal Program Enumeration for Rigorous Compi...

Skeletal Program Enumeration for Rigorous Compiler Testing

Liang Gong

April 30, 2018
Tweet

More Decks by Liang Gong

Other Decks in Research

Transcript

  1. Presented by Liang Gong Skeletal Program Enumeration for Rigorous Compiler

    Testing Qirun Zhang, Chengnian Sun, Zhendong Su Liang Gong, Electric Engineering & Computer Science, University of California, Berkeley.
  2. Motivation Liang Gong, Electric Engineering & Computer Science, University of

    California, Berkeley. • Test generation for compilers • Existing works: • Program generation (Csmith) • Generate test from scratch • Program mutation (EMI) • Randomly remove statements Random  Opportunistic Favor large/complex programs 2
  3. Program Enumeration Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. • Observation • Bug-triggering programs are small • ~30 LOC (Sun et al. ISSTA’16) • Program mutation • mutations of statements • Change variable names • Search space is bounded  enumeration • Confirmed Bugs: • GCC/Clang (217),CompCert (29), Scala (42) 3
  4. Change Identifiers Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. mutate identifiers can trigger optimizations 4 Original Test Mutated Test • Constant propagation • Dead code elimination
  5. Motivating Example Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. 5 Mutated program triggers a bug related to alias in GCC.
  6. Motivating Example Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. 6 Mutated program triggers a bug related to constant folding. GCC crash
  7. Program Enumeration Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. Goal: Enumerate all identifier mutations • Step-1: Convert an existing test into skeleton 7 Test Skeleton
  8. Program Enumeration Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. Goal: Enumerate all identifier mutations • Step-1: Convert an existing test into skeleton 8 Syntax rule of program Correspond rule of transformation
  9. Program Enumeration Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. Goal: Enumerate all identifier mutations • Step-2: fill in the holes in a skeleton 9 Generated Test Skeleton Generated Test
  10. Program Enumeration Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. Goal: Enumerate all identifier mutations • Step-2: fill in the holes in a skeleton 10 Generated Test Skeleton Generated Test <b, a, b, b, b, a> <a, b, b, b, a, b> 2 1 3 4 5 6
  11. Program Enumeration Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. Goal: Enumerate all identifier mutations • Step-2: fill in the holes in a skeleton 11 Generated Test Skeleton Generated Test 2 1 3 4 5 6 <b, a, b, b, b, a> <a, b, a, a, a, b> α-equivalent
  12. Program Enumeration Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. Goal: Enumerate all identifier mutations • Step-2: fill in the holes in a skeleton • Formulate as a set partition problem (well-known) 12 Generated Test Skeleton Generated Test 2 1 3 4 5 6 <b, a, b, b, b, a> <a, b, a, a, a, b> { {1,3,4,5}, {2, 6} } { {1,3,4,5}, {2, 6} } 64 (naive)  31 (set partition) 
  13. Stirling Partition Number Liang Gong, Electric Engineering & Computer Science,

    University of California, Berkeley. 13 The number of ways to partition n elements into k subsets
  14. Stirling Partition Number Liang Gong, Electric Engineering & Computer Science,

    University of California, Berkeley. 14 The number of ways to partition n elements into k subsets
  15. Stirling Partition Number Liang Gong, Electric Engineering & Computer Science,

    University of California, Berkeley. 16 Partition n+1 elements into k subsets
  16. Stirling Partition Number Liang Gong, Electric Engineering & Computer Science,

    University of California, Berkeley. 17 Partition n+1 elements into k subsets • The selected element is partitioned to a set s, where | s | = 1
  17. Stirling Partition Number Liang Gong, Electric Engineering & Computer Science,

    University of California, Berkeley. 18 Partition n+1 elements into k subsets • The selected element is partitioned to a set s, where | s | = 1 • The selected element is partitioned to a set s, where | s | > 1
  18. Stirling Partition Number Liang Gong, Electric Engineering & Computer Science,

    University of California, Berkeley. 19 • Now we can get all partitions recursively: function par(n, k) { ... // handle base cases return union( add(n, par(n-1, k)), par(n-1, k-1)); }
  19. Time Complexity Liang Gong, Electric Engineering & Computer Science, University

    of California, Berkeley. 20 • A skeleton with n holes and k variables. Olver et al. NIST Handbook of Mathematical Functions.
  20. Set Partition (with Scopes) Liang Gong, Electric Engineering & Computer

    Science, University of California, Berkeley. Each hole in a skeleton can be filled with a different set of variables. 21 Global scope hole local scope
  21. Set Partition (with Scopes) Liang Gong, Electric Engineering & Computer

    Science, University of California, Berkeley. Naïve approach: 22
  22. Set Partition (with Scopes) Naïve approach does not completely enumerate

    X Locally: <a,c> = <c,a> Globally: <a,a,a,c,b> ≠ <a,a,c,a,b> { {3}, {4} } { {1,2,3}, {4}, {5} } ≠ { {1,2,4}, {3}, {5} } 27
  23. Set Partition (with Scopes) Liang Gong, Electric Engineering & Computer

    Science, University of California, Berkeley. promote local holes to be global holes 28
  24. Set Partition (with Scopes) Liang Gong, Electric Engineering & Computer

    Science, University of California, Berkeley. 29 , { 3 }, { 4 }, { 3, 4 } promote local holes to be global holes
  25. Set Partition (with Scopes) Liang Gong, Electric Engineering & Computer

    Science, University of California, Berkeley. 30 , { 3 }, { 4 }, { 3, 4 } X promote local holes to be global holes
  26. Set Partition (with Scopes) Liang Gong, Electric Engineering & Computer

    Science, University of California, Berkeley. 31 , { 3 }, { 4 }, { 3, 4 } X X { 3 } promote local holes to be global holes
  27. Set Partition (with Scopes) Liang Gong, Electric Engineering & Computer

    Science, University of California, Berkeley. 32 , { 3 }, { 4 }, { 3, 4 } X X { 3 } X { 4 } { 3, 4 } promote local holes to be global holes
  28. Evaluation: size reduction • 94 orders of reduction • Still

    too large in practice Liang Gong, Electric Engineering & Computer Science, University of California, Berkeley. 33
  29. Evaluation: size reduction • 94 orders of reduction • Still

    too large in practice • Throw away tests with > 10K variants Liang Gong, Electric Engineering & Computer Science, University of California, Berkeley. 34
  30. Evaluation: size reduction • 94 orders of reduction • Still

    too large in practice • Throw away tests with > 10K variants Liang Gong, Electric Engineering & Computer Science, University of California, Berkeley. 35
  31. Evaluation: size reduction • 94 orders of reduction • Still

    too large in practice • Throw away tests with > 10K variants • Retained 90% of the original tests Liang Gong, Electric Engineering & Computer Science, University of California, Berkeley. 36
  32. Evaluation: size reduction • Throw away tests with > 10K

    variants • Retained 90% of the original tests Characteristics of tests after filtering Liang Gong, Electric Engineering & Computer Science, University of California, Berkeley. 37
  33. Evaluation: coverage GCC: ~30% Clang: ~20% GCC Clang (PM-X: EMI

    deletes X statements) Liang Gong, Electric Engineering & Computer Science, University of California, Berkeley. 38