View
33
Download
0
Category
Preview:
Citation preview
Printing:Differential Testing and Java Performance Evaluation on BDD
Student: Xia Xiao | Professor: Christian Kästner | Carnegie Mellon University
Binary Decision Diagram (BDD)Binary decision diagram (BDD) or branching program is a data structure torepresent a Boolean Function. It’s a more compressed and abstractrepresentation of sets or relations when compared with other data structures: e.g..Negation normal form(NNF) and Propositional directed acyclic graph (PDAG).
Questions & Ideas
Procedure• Construct a series of BDD objects from
both libraries, and assign them with thesame features(with the same variable, lowand high nodes).
• Run the written program to automaticallygenerate random combination of theexisting BDD with random operations onthem. Assign the constructed new BDDs togroup a and group b.
• Make hypothesis and assume the BDDswith the same data structure are built.
• Use Junit Test and helper MethodisSameBDD to check the features of twogroups of BDDs.
• The helper method isSameBDD would callthe toString method in each library tocheck their equality.
• Prove the hypothesis that the theconstructed BDDs work in the same way.
Differential Testing
Project Overview
Get familiar with theconcepts, theory,and background
knowledge.Understand theimplementation
and functionality intwo different BDD
libraries.
Step 1
ImplementDifferential Testingand write programfor automatically
generatingrandom test cases
for both BDDlibraries
Step 2
Measure therunning time of bothlibraries. Implementthe Java Programfor multiple timesand collect dataduring the JavaPerformance.
Step 3
Compare therunning time fromstep 3; use MinitabExpress to producet-test and histogramfor two BDD library
performance; Makeconclusion.
Step 4
Histogram Comparison
BDD for the function f
• There exists a difference in the running speed between two BDD libraries during the JavaPerformance Evaluation.
• As the numbers of BDD constructed increase (size of 1,10, 20, 30, 40, 50), the histogram showsthat the difference in running time is also increasing.
• The boxplots illustrate that the distribution of the running speed of two libraries. We noticethat when size = 1, the running speed is overlapped.
• However, as the size of BDD constructed increase, the boxplots do not overlap anymore.• The gap between the two boxplots get larger as the size gets larger.• Overall, the JavaBDD library perform a faster running speed than our BDD library.• From data in the t-test statistics, 6 histogram and 6 boxplots generated by Minitab Express,
the results support our hypothesis.
Results / Conclusion
Works Cited• “Binary Decision Diagram.” Wikipedia. Wikimedia Foundation, n.d. Web. 24 July 2016.• William M. McKeeman, “Differential Testing for Software,” Digital Technical Journal 10,
no. 1 (1998).
• Georges, Andy, Dries Buytaert, and Lieven Eeckhout. “Statistically Rigorous Java Performance Evaluation.” ACM SIGPLAN Notices 42, no. 10 (October 21, 2007): 57. doi:10.1145/1297105.1297033.
• This is a graph illustration ofBoolean function frepresented in the datastructure of Binary DecisionDiagram. It’s rooted,directed, and consists ofseveral decision nodes(x1,x2,x3)and two terminalnodes (0,1).
• Each decision node ispointed to a low child and ahigh child. A dotted linerepresents an assignment of0 and the solid linerepresents an assignment of1 instead.
Binary decision tree and truth table for the function f(x1,x2,x3) = ¬(x1x2x3)+ x1x2 + x2x3
Question Ideas of approaches• How to implement Differential Testing on
two different BDD libraries?
• What’s the difference betweenDifferential Testing and other prevalenttesting methods?
• What are the methods/theories would be helpful during Java Evaluation on BDD?
• Which BDD library would have a shorterrunning time during the evaluation? Isthere a significant difference betweentheir each running time?
• What non-determinism factor may effect the BDD Java Performance Evaluation?
• Since we are trying to compare two BDDlibraries, it’s important to consider thedifference in the implementation andfunctionality.
• Statistically rigorous methodology shouldbe included in our Java PerformanceEvaluation in order to avoid misleading oreven incorrect result.
• Confidence intervals can providetheoretical support for the JavaPerformance Evaluation.
• Various system effects may have influenceon the BDD performance, while they donot have large impact on the JavaPerformance Evaluation.
Differential Testing – A form of random testing, is an important testing technology for large software system. Particularly, based on its unique feature of indirectness and comparison,differential testing can bring about swift, efficient testing results and save miscellaneousexpense in time and space.
Box Plot Illustration
• The left figure shows a binary decision tree anda truth table. In the tree on the left, the value of the function can be determined for a given variable assignment by following a path down the graph to a terminal. In the figures above, dotted lines represent edges to a low child, while solid lines represent edges to a high child. Therefore, to find (x1=0, x2=1, x3=1), begin at x1, traverse down the dotted line to x2 (since x1 has an assignment to 0), then down two solid lines (since x2 and x3 each have an assignment to one). This leads to the terminal 1, which is the value of f (x1=0, x2=1, x3=1).
• The binary decision tree of the left figure can be transformed into a binary decision diagram by maximally reducing it according to the two reduction rules. The resulting BDD is shown in the right figure.
Recommended