English subtitles

← Automated Inferring - Software Debugging

Get Embed Code
4 Languages

Showing Revision 3 created 05/24/2016 by Udacity Robot.

  1. Let me show you how this works on an example.
  2. Here is a square root function.
  3. It takes x and returns the square root.
  4. Let's assume we invoke this with the values 2, 4, and 16.
  5. When we invoke the square root with the value of 2,
  6. we could infer that x has a value of 2 and eps has a value of 10^-7.
  7. However, these patterns would also be instantiated:
  8. x is smaller or equal than two, and x is greater or equal than 2,
  9. because these patterns also hold for the values that we observed.
  10. In the next iteration, we invoke the square root with the number of four,
  11. and now, the invariant of x always being 2 is eliminated.
  12. What we get now, however, is that x being less or equal than 4 still holds.
  13. We can do so by merging the earlier invariant with a new one.
  14. And x greater or equal than 2 still holds for the new value.
  15. When we invoke the square root of 16, we now retain the invariant
  16. that x is less or equal than 16 and greater or equal than 2,
  17. and this is what we get in the end:
  18. x is between 2 and 16, and eps is always 10^-7.
  19. For the postcondition, we get similar ranges for the return value.
  20. The return value is between the square root of 2 and 4,
  21. which is the square root of 16.
  22. However, what we also get is that the return value squared is equal to x,
  23. and we get this because Daikon has an appropriate pattern for that,
  24. namely a pattern where the multiplication of any two variables equals a third variable,
  25. and this is instantiated with a return value, again with a return value and with x
  26. and this pattern then holds for all runs--
  27. at least for all runs with integer numbers.
  28. If we put in floating point numbers, then eps also comes into play,
  29. because of rounding errors, and then this pattern would no longer be discovered.
  30. So whatever Daikon can produce is constrained to the pattern library it has,
  31. but if you add more patterns, then you'll be able to discover more properties,
  32. which will take Daikon a bit longer, though, to discover them.
  33. Still, even with a perfect set of patterns,
  34. approaches like these are dependent on the actual numbers
  35. that are being fed in there.
  36. What Daikon produces is relevant for all the runs observed,
  37. but we all know that the real precondition for the square root
  38. does not have specific range constraints on x
  39. except that x should be greater or equal than 0.
  40. Likewise, the return value of square root is not necessarily between the square root of 2
  41. and the square root of 16,
  42. but it can actually be anything that's, again, greater than 0.
  43. So, tools for dynamic inference of invariants can work well
  44. if they do have a good test suite in the beginning.
  45. How can we get the correct ranges for x and the return value?
  46. By invoking square root with a value of 0?
  47. By invoking square root with a value of 1?
  48. By invoking square root with a value of maxint, where maxint is the highest available integer?
  49. Or by invoking square root with a negative value?
  50. Hint: you need multiple invocations.
  51. Check those which you need to get the correct ranges. Over to you.